информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Атака на InternetSpanning Tree Protocol: недокументированное применениеПортрет посетителя
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Три миллиона электронных замков... 
 Doom на газонокосилках 
 Умер Никлаус Вирт 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / programming
Имя Пароль
ФОРУМ
если вы видите этот текст, отключите в настройках форума использование JavaScript
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Не частот - количеств в блоке 11.03.02 08:24  Число просмотров: 976
Автор: Zef <Alloo Zef> Статус: Elderman
<"чистая" ссылка>
<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
<"чистая" ссылка>
1




Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2024 Dmitry Leonov   Page build time: 1 s   Design: Vadim Derkach