Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
| | |
такого не бывает 05.03.02 15:32 Число просмотров: 954
Автор: ukv Статус: Незарегистрированный пользователь
|
> а мне надо наоборот - чтобы контрольная сумма не
> менялась при различии менее, чем на 4 бита в любых
> позициях.
Если контрольная сумма не меняется СОВСЕМ при замене 4 бит - то такая контрольная сумма просто константа (N раз по 4 бита - можно заменить блок любой длины без изменения контрольной суммы). То же самое и в постановке "различие на 1 бит блока - отличие сигнатуры в младшем разраде". По-моему, задачка неразрешима.
|
|
<programming>
|
Как сделать алгоритм типа контрольной суммы, чтобы: 03.03.02 09:10
Автор: Zef <Alloo Zef> Статус: Elderman
|
|
Есть блок длиной 16Кбит. Нужно состряпать из него уникальную сигнатуру, типа контрольной суммы, длиной 32-128 бит, чтобы отличие на единицу в любом разряде блока всегда приводило к отличию сигнатуры на единицу (младшего разряда) и при этом вероятность совпадения сигнатур полностью различных блоков была того же порядка, что и для обычной суммы по мод.2.
|
|
Как сделать алгоритм типа контрольной суммы, чтобы: 07.03.02 05:34
Автор: + <Mikhail> Статус: Elderman
|
|
A pochemu ne ispolzovat` kod s ispravleniem oshibok??
|
| |
Мне не нужно содержимое блока, 07.03.02 08:03
Автор: Zef <Alloo Zef> Статус: Elderman
|
|
мне надо только проверить его наличие на своем месте
|
| | |
OK, algoritm . .. 07.03.02 22:25
Автор: + <Mikhail> Статус: Elderman
Отредактировано 08.03.02 03:51 Количество правок: 1
|
tvoi original block zacodirovan s izbytochnym codom, no
kontrolnuu sum vychisliaesh ot originalnogo coda. itogda skolko by ne proishodilo korrektiruemyh oshibok kontrolnaia sum ORIGINALNOGO koda budet ta zhe.
|
| | | |
Net tam izbytochnogo! Ya by ego i Uzal! 08.03.02 10:30
Автор: Zef <Alloo Zef> Статус: Elderman
|
|
|
|
А чем CRC плох ? 04.03.02 09:54
Автор: PS <PS> Статус: Elderman
|
|
|
| |
Сучность вопроса: 05.03.02 06:31
Автор: Zef <Alloo Zef> Статус: Elderman
|
|
Нужно сравнивать блоки данных, содержащие небольшое (1-4) кол-во ошибок. Чтобы не хранить копии блоков я хочу сделать что-то на подобие CRC, но классическая CRC делается так, чтобы как можно меньшие изменения в блоке вызывали как можно большие изменения сигнатуры (и на эту тему есть куча инфы), а мне надо наоборот - чтобы контрольная сумма не менялась при различии менее, чем на 4 бита в любых позициях.
|
| | |
такого не бывает 05.03.02 15:32
Автор: ukv Статус: Незарегистрированный пользователь
|
> а мне надо наоборот - чтобы контрольная сумма не
> менялась при различии менее, чем на 4 бита в любых
> позициях.
Если контрольная сумма не меняется СОВСЕМ при замене 4 бит - то такая контрольная сумма просто константа (N раз по 4 бита - можно заменить блок любой длины без изменения контрольной суммы). То же самое и в постановке "различие на 1 бит блока - отличие сигнатуры в младшем разраде". По-моему, задачка неразрешима.
|
| | | |
такого не бывает: да не, бывает ... но как ? 05.03.02 18:07
Автор: Chingachguk <Chingachguk> Статус: Member
|
> > а мне надо наоборот - чтобы контрольная сумма не
> > менялась при различии менее, чем на 4 бита в любых
> > позициях.
Как-то можно сделать ...
У меня вот была такая мысля: вот переданный поток бит. Каждый бит несет инфу: нуль он или не нуль, плюс свой нумер. Пусть это будет график функции = значение бита(номера бита) (значения 0 или 1 соответственно). Как и всякую функцию, ее можно разложить в ряд(интеграл Фурье) до какого-там знака. Коэффициенты выслать как CRC. Потом (при получении) опять-таки разложить полученный поток и сравнить каким-нибудь критерием(Хи-квадрат ?) c присланными коэффициентами.
Это так, слова. Но, видимо, решение быть должно...
|
| | | | |
А если так? 06.03.02 12:57
Автор: Zef <Alloo Zef> Статус: Elderman
|
for(i = 0; i < 588; i += 4)
{//подсчитываем кол-во единиц в каждом разряде
code = *((unsigned int*)&buff[i]);
for(j = 0; j < 32; j++)
{
if(code >= 0x8000)
crc[j]++;
code <<= 1;
}
}
for(i = 0; i < 32; i++)
{//округляем к ближайшему на2 разряда
//"остатки" от округления суммируем
//и так же округляем, чтобы не пропустить
//больше 3х ошибок в разных разрядах
c = crc[i] & 0x03;
crc[32] += c;
crc[i] >>= 1;
if(c > 2)
crc[i]++;
}
if(crc[32] & 0x03 > 2)
crc[32] += 4;
crc[32] >>= 1;
//получили сигнатуру из 33 слов, которые можно
//дальше еще"сжать"
|
| | | | | |
А если так? - Хм... А чем это отличается от... 06.03.02 13:17
Автор: Chingachguk <Chingachguk> Статус: Member
|
Извини, я си не знаю - может, что не понял, но, судя по всему, у тебя нечто вроде реперных контрольных суммочек для каждого фрагмента последовательности, так ? И ты хочешь как-то потом по ним отдельно проверять фрагменты полученной последовательности ?
(А ты проверил насчет случая, если ВСЕ кривые биты будут в одном слове ?!)
Если так, то чем это отличается вот от чего: передаем, например, четность каждых 16-ти байтовых блоков. Т.е. фактически - побитно. Получаем на каждые 256 бит 1 бит четности. И стандартный CRC(-какой-нибудь обычный хэш).
Получив присланные байты и получив на них правильный хэш(совпадающий с присланным), проблем не имееем. Однако если хэш не совпал, то мы начианем рыскать по четности с целью определить, где дыра(дырки). Потом перебором(что не должно занять много времени - можно размер блока уменьшить) пытаемся менять по 1-4 битика в том куске(кусках), где четность неверна ... Если вдруг совпало(поменяли 2 бита - получился верный хэш), то считаем присланную инфу OK.
ps Я вот в книжке по криптографии глянул - нифига такого нету Ж)
|
| | | | | | |
А если так? - Хм... А чем это отличается от... 07.03.02 04:18
Автор: Zef <Alloo Zef> Статус: Elderman
|
На случай, если все кривые биты в одном слове (или в разных разрядах разных слов) я суммирую остатки (см текст проги). А вот от "перескока" бита в одном разряде (т.е. если один из 1 в 0, а др. из 0 в 1) защиты нет. Правда, если учитывать, что биты считываются с устройства, то "перескок" наиболее вероятен для смежных бит, а они попадают в разные разряды.
Сейчас я думаю как раз над этим и над тем, как свернуть сигнатуру дальше.
|
| | | | | | | |
Или так: 08.03.02 14:37
Автор: Zef <Alloo Zef> Статус: Elderman
|
Считаем вхождения в блок 4х битных блоков от 0 до 0f (как в LZW), затем вычисляем среднее, потом дисперсии для каждого числа, обрезаем их до байта и получаем 128бит сигнатуру, к-рая при изменении 1 бита в блоке изменяется на 2 бита.
По-моему, красыва?
Жял, что нэ я придумал, абидна, а?
|
| | | | | | | | |
Или так: А что, это доказано ? 09.03.02 08:14
Автор: Chingachguk <Chingachguk> Статус: Member
|
> Считаем вхождения в блок 4х битных блоков от 0 до 0f (как в
> LZW), затем вычисляем среднее, потом дисперсии для каждого
> числа, обрезаем их до байта и получаем 128бит сигнатуру,
> к-рая при изменении 1 бита в блоке изменяется на 2 бита.
А формулу-то то покажи ?!
Пусть Xi - значения блоков (от 0 до 0f),
Ni - их количества в переданном буфере, и
Если Xсреднее = (Xi*Ni)/N;
N = Ni;
Дисперсия(i) = Di = Ni * (Xi-Xсреднее) ^ 2;
Что дальше означает - обрезаем до байта ? Если ты отнормировал на единицу Ni - это одно, а нет - тогда непонятно, с ростом длины все Ni растут.
В любом случае я не пойму, почему при изменении одного бита меняются ТОЛЬКО ДВЕ дисперсии ?
> По-моему, красыва?
> Жял, что нэ я придумал, абидна, а?
А хто ? ;)
|
| | | | | | | | | |
Почему 2? Смотри: 10.03.02 09:03
Автор: Zef <Alloo Zef> Статус: Elderman
|
|
Если изменился бит, значит 4битная группа, в к-рую он входил тоже изменилась. Тогда одного кода стало на 1 меньше, другого на 1 больше, т.е. сигнатура меняется на 1 в 2байтах.
|
| | | | | | | | | | |
Извини, не понял, ты же... 11.03.02 03:54
Автор: Chingachguk <Chingachguk> Статус: Member
|
Ты вроде про дисперсии говорил частот встречаемости блоков 0..0fh.
Из них - ты грил - состоит сигнатура ?!
Или как ? ;)
|
| | | | | | | | | | | |
Не частот - количеств в блоке 11.03.02 08:24
Автор: Zef <Alloo Zef> Статус: Elderman
|
|
|
| | | |
может и бывает... 05.03.02 16:23
Автор: PS <PS> Статус: Elderman
|
только это не инженерная, а научная задачка. Может даже на кандидатскую потянет.
Если работодатель пытается в втюхать такое задание - его сразу посылать нужно.
> > а мне надо наоборот - чтобы контрольная сумма не
> > менялась при различии менее, чем на 4 бита в любых
> > позициях.
>
> Если контрольная сумма не меняется СОВСЕМ при замене 4 бит
> - то такая контрольная сумма просто константа (N раз по 4
> бита - можно заменить блок любой длины без изменения
> контрольной суммы). То же самое и в постановке "различие на
> 1 бит блока - отличие сигнатуры в младшем разраде".
> По-моему, задачка неразрешима.
|
|
Как сделать алгоритм: нахаляву ?! 03.03.02 15:12
Автор: Chingachguk <Chingachguk> Статус: Member
Отредактировано 03.03.02 15:13 Количество правок: 1
|
> Есть блок длиной 16Кбит. Нужно состряпать из него
> уникальную сигнатуру, типа контрольной суммы, длиной 32-128
> бит, чтобы отличие на единицу в любом разряде блока всегда
> приводило к отличию сигнатуры на единицу (младшего разряда)
> и при этом вероятность совпадения сигнатур полностью
> различных блоков была того же порядка, что и для обычной
> суммы по мод.2.
Почему нельзя:
Сигнатура =
Бит0 = Четность(Блок);
Биты1..XX = MD5(Блок) ; Или что-то в этом роде.
?
|
| |
Хемминг? А вероятность совпадения не увеличится? 04.03.02 05:26
Автор: Zef <Alloo Zef> Статус: Elderman
|
|
|
|
|
подробно о проекте
Анализ криптографических сетевых...
