Есть блок длиной 16Кбит. Нужно состряпать из него уникальную сигнатуру, типа контрольной суммы, длиной 32-128 бит, чтобы отличие на единицу в любом разряде блока всегда приводило к отличию сигнатуры на единицу (младшего разряда) и при этом вероятность совпадения сигнатур полностью различных блоков была того же порядка, что и для обычной суммы по мод.2.
Как сделать алгоритм типа контрольной суммы, чтобы:07.03.02 05:34 Автор: + <Mikhail> Статус: Elderman
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
Нужно сравнивать блоки данных, содержащие небольшое (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
Извини, я си не знаю - может, что не понял, но, судя по всему, у тебя нечто вроде реперных контрольных суммочек для каждого фрагмента последовательности, так ? И ты хочешь как-то потом по ним отдельно проверять фрагменты полученной последовательности ?
(А ты проверил насчет случая, если ВСЕ кривые биты будут в одном слове ?!)
Если так, то чем это отличается вот от чего: передаем, например, четность каждых 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
только это не инженерная, а научная задачка. Может даже на кандидатскую потянет.
Если работодатель пытается в втюхать такое задание - его сразу посылать нужно.
> > а мне надо наоборот - чтобы контрольная сумма не > > менялась при различии менее, чем на 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
подробно о проекте
Анализ криптографических сетевых...
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
