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.
Есть блок длиной 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
подробно о проекте
Анализ криптографических сетевых...
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
