> > Например, пусть f(X) = X % P (остаток от деления X на P). > > Это плохой пример. Нужно смотреть в сторону > collision-resistant (collision-free) хэш-фукнций. Ссылка > внизу. > Пример-то, конечно, плохой... Хотя, разве CRC не есть остаток от деления? Правда полиномы там, но все же.
Почитаю... может пойму чего лишнего.
> > Но, определенно, если взять H[i](X) := X % Pi, и Pi попарно > > различные простые, тогда все намного лучше! Правильно? > > Не факт. Если например положить P равным произведению Pi > (или простому числу того же порядка), то получиться > примерно тоже самое. > Гмм... Да нет же... Видимо я туплю, но:
пусть X == A1 mod P1 и X == A2 mod P2. Я утверждаю, что A1 и A2 не связанны
никаким уравнением не включающим X.
другими словами: Для любых A1 и A2 существует X, что выполняются два вышепривенных равенства. X, например, (A2-A1)P1^(P2-1) + A1
> > Кто нибудь представляет себе, что будет, если f - это MD5? > > Можно ли выразить значение MD5(A*x + B) через MD5(x)? > > Вряд ли. По крайней мере это > криптографический хэш, что, в частности, > подразумевает отсутствие функциональных закономерностей > между MD5(A*x+B) и MD5(x). Хотя это не доказано. > Да-аа... Я так и думал.
MD5 - это круто. Может и правда, закрыть глаза на то, что он в несколько раз
медленнее CRC. За то 128 бит сразу! За то можно линейно портить данные, и получать другие хэш функции...
Правда немножечко я еще сомневаюсь... Разве может быть все так просто?
Собственно проблема состоит в том, что нужно много (хотя бы штук 20) разных хэш функций. CRC вполне устраивает, только я не могу найти ни одного полинома в 32 бита, кроме того, что в ГОСТе, ISO и CCITT. Если есть другие идеи или другие полиномы, очень был бы благодарен...
Спасибо.
легко сгенерировать самому05.12.02 09:39 Автор: RElf <M> Статус: Member Отредактировано 05.12.02 10:16 Количество правок: 1
> Собственно проблема состоит в том, что нужно много (хотя бы > штук 20) разных хэш функций. CRC вполне устраивает, только > я не могу найти ни одного полинома в 32 бита, кроме того, > что в ГОСТе, ISO и CCITT. Если есть другие идеи или другие > полиномы, очень был бы благодарен...
Я тут как-то исследованием CRC64 занимался - много чего интересного нарыл. Посмотри на страничке и дальше по ссылкам:
За ссылку спасибо... Почитал и решил обойтись простыми полиномами...
Сгенерировать их в домашних условиях не получилось (долго это, разве нет?), а вот готовых нашелся список из 2000 шт!
Если интересно, зачем было нужно: Bloom фильтры нужно сделать. На деле, я думаю функциями 6-8 обойдется. Альтернативно, я видел, люди делали так: брали MD5 шириной 128 бит, и резали на 4 куска (по 32, соответственно). Однако, оптимальный случай для 4-х хэш функций дает >5% false positive rate. Мне кажется с CRC32 выдет быстрее и экономнее.
Спасибо, на деле оказался единственный форум из 6, где ответили; помогло, а то я неуверенно седя ощущал.
попробуем...07.12.02 07:41 Автор: RElf <M> Статус: Member
> За ссылку спасибо... Почитал и решил обойтись простыми > полиномами... > > Сгенерировать их в домашних условиях не получилось (долго > это, разве нет?),
Вовсе нет. Например, см. ниже по ссылке.
> а вот готовых нашелся список из 2000 шт!
Тоже вариант.
> Если интересно, зачем было нужно: Bloom фильтры нужно > сделать. На деле, я думаю функциями 6-8 обойдется. > Альтернативно, я видел, люди делали так: брали MD5 шириной > 128 бит, и резали на 4 куска (по 32, соответственно). > Однако, оптимальный случай для 4-х хэш функций дает >5% > false positive rate. Мне кажется с CRC32 выдет быстрее и > экономнее.
Что-то я все равно не понял, что дано и что нужно получить.
> Собственно проблема состоит в том, что нужно много (хотя бы > штук 20) разных хэш функций. CRC вполне устраивает, только > я не могу найти ни одного полинома в 32 бита, кроме того, > что в ГОСТе, ISO и CCITT. Если есть другие идеи или другие > полиномы, очень был бы благодарен... > Спасибо.
Все зависит от задачи. Насколько криптостойкой тебе нужна подпись.
Если просто контроль данных, то можно и crc с разными стартовыми значениями (не FFFFFFFFh, а FFFFFFFE и т.д.)
А вообще можно хоть 4xDES, 5xDES - есть же трайпл DES.
Увеличь число раундовых преобразований в каком-нибудь хэше,
... или...сrc_start=0xfffffffe,0xfffffffd...или число раундов...07.12.02 03:32 Автор: SemenU Статус: Незарегистрированный пользователь
> Все зависит от задачи. Насколько криптостойкой тебе нужна > подпись. Криптостойкость мне совсем не нужна... Хотя я не совсем понимаю, что это значит.
Нужно несколько таких функций H[i], 1<=i<=N, чтоб на разных данных X и Y
значения функций H[i](X) и H[j](Y) были (по возможности) не равны для любых i и j, 1<=i,j<=N.
> Если просто контроль данных, то можно и crc с разными > стартовыми значениями (не FFFFFFFFh, а FFFFFFFE и т.д.) > Согласен с утверждением, что получится H[i](X) = H[i+1](X) + C[i]. Не подходит.
> А вообще можно хоть 4xDES, 5xDES - есть же трайпл DES. > Увеличь число раундовых преобразований в каком-нибудь хэше, Если я правильно понял, предлагается что-то типа:
Пусть H(X) - хэш функция. Положим тогда H[i] = H^i.
А не получится ли так, что если для каких-то i0 и j0 H[i0](X) == H[j0](Y), то
H[i0+n](X) == H[j0+n](Y) для всех n, 1<=n<=min(N-i0, N-j0). Помоему, получится именно так. Это не есть хорошо...
Спасибо.
Предлагал про хэш я другое. С CRC был не прав.09.12.02 16:57 Автор: Chingachguk <Chingachguk> Статус: Member
> > А вообще можно хоть 4xDES, 5xDES - есть же трайпл DES. > > Увеличь число раундовых преобразований в каком-нибудь > хэше, > Если я правильно понял, предлагается что-то типа:
Нет. Я предлагал видоизменить алгоритм какого-нибудь хэша, например MD5. Во многих (которые я видел, я не знаток криптографии) хэш-функциях есть понятие "раундового преобразования". Те на самом деле хэш-функцию можно представить в виде:
h = MD5(text);
h1 = MD5_r(text1) (раундовая функция хэша, text1 - часть text или целая),
h2 = MD5_r(h1),
...
и тд.
Например, в алгоритме MD5 есть часть, которую называют "подбитие дайджеста" - используется, когда входные данные достигают определенной кратности, например 512-ти битам:
> Нет. Я предлагал видоизменить алгоритм какого-нибудь хэша, > например MD5. Во многих (которые я видел, я не знаток > криптографии) хэш-функциях есть понятие "раундового > преобразования". Те на самом деле хэш-функцию можно > представить в виде: > > [skiped] > Я это, боюсь не стандартизованный полином для CRC32 использовать, а вы мне алгоритм менять предлагаете! Не, чур меня, чур... Меня же кошмары по ночам замучают.
Вобшем, поразному портить входные данные к, скажем, MD5 кажется лучше. Например,
H(1)= MD5(X),
H(2) = MD5(X*H(2))
...
H(i) = MD5(X*H(i-1))
где * - XOR, напрмер...
а что если...07.12.02 07:36 Автор: RElf <M> Статус: Member
> Нужно несколько таких функций H[i], 1<=i<=N, чтоб на > разных данных X и Y > значения функций H[i](X) и H[j](Y) были (по возможности) не > равны для любых i и j, 1<=i,j<=N.
А почему бы просто не положить H[i](X) = f(i||X), где f какая-нибудь фиксированная хэш-функция нужной размерности?
Т.е. приписываем i к данным X слева ("конкатинируем" i и X), и от всего этого считаем значение f.
а доказательство?07.12.02 15:45 Автор: SemenU Статус: Незарегистрированный пользователь
> А почему бы просто не положить H[i](X) = f(i||X), где f > какая-нибудь фиксированная хэш-функция нужной размерности? > Т.е. приписываем i к данным X слева ("конкатинируем" i и > X), и от всего этого считаем значение f.
Да, подобная идея была в моей голове. Но я не такой спец в этом вопросе, и боюсь я, что не сработает это. Тут все начинает зависеть от f, не так ли?
Например, пусть f(X) = X % P (остаток от деления X на P). Пусть все X одной длины.
i|X обобщим как A*i + B*X.
H[i](X) = (A*i + B*X) % P
Поищем H[n](X) - H[m](X) по модулю P:
((A*n + B*X) % P - (A*m +B*X) % P) = (A*(n-m)) mod P, т.е.
H[n](X) == H[m](X) + (A*(n-m) % P) + t*P, где t 0, 1 или -1
Вобщем нужны функции, которые бы друг через друга очень сложно выражались...
А лучше никак :), только не понятно, что это значит...
Но, определенно, если взять H[i](X) := A % Pi, и Pi попарно различные простые, тогда все намного лучше! Правильно?
Кто нибудь представляет себе, что будет, если f - это MD5? Можно ли выразить
значение MD5(A*x + B) через MD5(x)? Хмм... Сам подумал и кажется, что нет... Или да?
спасет collision-resistant hash-function08.12.02 00:35 Автор: RElf <M> Статус: Member Отредактировано 08.12.02 00:36 Количество правок: 1
> > А почему бы просто не положить H[i](X) = f(i||X), где f > > какая-нибудь фиксированная хэш-функция нужной размерности? > > Т.е. приписываем i к данным X слева ("конкатинируем" i и > > X), и от всего этого считаем значение f. > > Да, подобная идея была в моей голове. Но я не такой спец в > этом вопросе, и боюсь я, что не сработает это. Тут все > начинает зависеть от f, не так ли? > > Например, пусть f(X) = X % P (остаток от деления X на P).
Это плохой пример. Нужно смотреть в сторону collision-resistant (collision-free) хэш-фукнций. Ссылка внизу.
> Пусть все X одной длины. i|X обобщим как A*i + B*X. > > H[i](X) = (A*i + B*X) % P > > Поищем H[n](X) - H[m](X) по модулю P: > ((A*n + B*X) % P - (A*m +B*X) % P) = (A*(n-m)) mod P, т.е. > H[n](X) == H[m](X) + (A*(n-m) % P) + t*P, где t 0, 1 или -1 > > Вобщем нужны функции, которые бы друг через друга очень > сложно выражались... > А лучше никак :), только не понятно, что это значит... > Но, определенно, если взять H[i](X) := A % Pi, и Pi попарно > различные простые, тогда все намного лучше! Правильно?
Не факт. Если например положить P равным произведению Pi (или простому числу того же порядка), то получиться примерно тоже самое.
> Кто нибудь представляет себе, что будет, если f - это MD5? > Можно ли выразить значение MD5(A*x + B) через MD5(x)?
Вряд ли. По крайней мере это криптографический хэш, что, в частности, подразумевает отсутствие функциональных закономерностей между MD5(A*x+B) и MD5(x). Хотя это не доказано.
Посмотри Chapter 9 "Hash Functions and Data Integrity" в
> > Например, пусть f(X) = X % P (остаток от деления X на P). > > Это плохой пример. Нужно смотреть в сторону > collision-resistant (collision-free) хэш-фукнций. Ссылка > внизу. > Пример-то, конечно, плохой... Хотя, разве CRC не есть остаток от деления? Правда полиномы там, но все же.
Почитаю... может пойму чего лишнего.
> > Но, определенно, если взять H[i](X) := X % Pi, и Pi попарно > > различные простые, тогда все намного лучше! Правильно? > > Не факт. Если например положить P равным произведению Pi > (или простому числу того же порядка), то получиться > примерно тоже самое. > Гмм... Да нет же... Видимо я туплю, но:
пусть X == A1 mod P1 и X == A2 mod P2. Я утверждаю, что A1 и A2 не связанны
никаким уравнением не включающим X.
другими словами: Для любых A1 и A2 существует X, что выполняются два вышепривенных равенства. X, например, (A2-A1)P1^(P2-1) + A1
> > Кто нибудь представляет себе, что будет, если f - это MD5? > > Можно ли выразить значение MD5(A*x + B) через MD5(x)? > > Вряд ли. По крайней мере это > криптографический хэш, что, в частности, > подразумевает отсутствие функциональных закономерностей > между MD5(A*x+B) и MD5(x). Хотя это не доказано. > Да-аа... Я так и думал.
MD5 - это круто. Может и правда, закрыть глаза на то, что он в несколько раз
медленнее CRC. За то 128 бит сразу! За то можно линейно портить данные, и получать другие хэш функции...
Правда немножечко я еще сомневаюсь... Разве может быть все так просто?
выбор богатый10.12.02 00:00 Автор: RElf <M> Статус: Member
> Пример-то, конечно, плохой... Хотя, разве CRC не есть > остаток от деления? Правда полиномы там, но все же.
Это верно.
> > > Но, определенно, если взять H[i](X) := X % Pi, и > > > Pi попарно различные простые, тогда все намного лучше! > > > Правильно?
> > Не факт. Если например положить P равным произведению Pi > > (или простому числу того же порядка), то получиться > > примерно тоже самое. > > > Гмм... Да нет же... Видимо я туплю, но: > > пусть X == A1 mod P1 и X == A2 mod P2. Я утверждаю, что A1 > и A2 не связанны никаким уравнением не включающим X.
Тоже самое справедливо для приведенного мной примера.
> другими словами: Для любых A1 и A2 существует X, что > выполняются два вышепривенных равенства.
Но заметь, что такое X не единственное: X+P1*P2 тоже удовлетворяет равенствам.
[...]
> MD5 - это круто. Может и правда, закрыть глаза на то, что > он в несколько раз медленнее CRC.
Если нужна большая скорость и разрядность, то возможно лучше использовать CRC64 в качестве компромиса.
> За то 128 бит сразу! За то можно линейно > портить данные, и получать другие хэш функции...
> Правда немножечко я еще сомневаюсь... Разве может быть все > так просто?
Проверено электроникой ;-)
и точно, выбор богатый. Но ничего точно пока не выяснилось...10.12.02 08:07 Автор: SemenU Статус: Незарегистрированный пользователь
> > Пример-то, конечно, плохой... Хотя, разве CRC не есть > > остаток от деления? Правда полиномы там, но все же. > > Это верно. > Угу, только там не все так, как у целых чисел. Напрмер, если я не ошибаюсь, существуют неразложимые, но и не простые полиномы. Ну да ладно.
> > > > Но, определенно, если взять H[i](X) := X % Pi, и > > > > Pi попарно различные простые, тогда все намного лучше! > > > > Правильно? > > > другими словами: Для любых A1 и A2 существует X, что > > выполняются два вышепривенных равенства. > > Но заметь, что такое X не единственное: X+P1*P2 тоже > удовлетворяет равенствам. > Это - да... Другими словами, CRC не является ни "preimage resistant", ни "2nd preimage resistant" ни "collision resistant". CRC вообще не OWF ("One Way Function"). CRC - это просто "hash function", def. 9.1 из той самой книги, на которую была ссылка.
> > MD5 - это круто. Может и правда, закрыть глаза на то, что > > он в несколько раз медленнее CRC. > > Если нужна большая скорость и разрядность, то возможно > лучше использовать CRC64 в качестве компромиса. > А я думаю, это еще вопрос для исследования, что быстрее CRC64 или два разных CRC32, чтобы получить 64 бита. Хотя CRC64 должен иметь большую эффективную ширину (есть такой термин?), чем пара < CRC32, CRC32>.
> > За то 128 бит сразу! За то можно линейно > > портить данные, и получать другие хэш функции... > > Правда немножечко я еще сомневаюсь... Разве может быть все > > так просто? > > Проверено электроникой ;-) :-) Я другое имел в виду...
фиолетово10.12.02 11:17 Автор: RElf <M> Статус: Member
> > Если нужна большая скорость и разрядность, то возможно > > лучше использовать CRC64 в качестве компромиса. > > > А я думаю, это еще вопрос для исследования, что быстрее > CRC64 или два разных CRC32, чтобы получить 64 бита. Хотя > CRC64 должен иметь большую эффективную ширину (есть такой > термин?), чем пара < CRC32, CRC32>.
На самом деле CRC64 или два CRC32 - не суть важно. Если CRC32 построены на двух различных неприводимых полиномах p,q 32-й степени, а CRC64 на полиноме r 64-й степени, то между каждое CRC32 есть проекция на F_{2^32} (поле из 2^32 элементов), а CRC64 проекция на F_{2^64}. При этом F_{2^32}xF_{2^32} и F_{2^64} равномощны.
По скорости выигрывает та CRC, чья разрядность совпадает с разрядностью процессора, хотя этот выигрыш незначителен.
В общем, если тебе не важна криптостойкость, наверное, все-таки лучше использовать набор из нескольких CRC-R, где R разрядность процессора.
Использование криптографических хэш-фукнций здесь необосновано и ведет к значительному проигрышу в скорости. Всякой функции - своя область применения ;-)
стартовое значение особой роли не играет05.12.02 09:47 Автор: RElf <M> Статус: Member
> Если просто контроль данных, то можно и crc с разными > стартовыми значениями (не FFFFFFFFh, а FFFFFFFE и т.д.)
Можно показать, что CRC подсчитанные таким образом отличаются (xor) на константу, которая не зависит от данных, а только от начальных значений. Таким образом, использование другого начального значения с тем же полиномом не дает абсолютно ничего.
> А вообще можно хоть 4xDES, 5xDES - есть же трайпл DES. > Увеличь число раундовых преобразований в каком-нибудь хэше,
Тогда уж лучше использовать хеш-функции типа MD5, SHA-1 и т.д. Но все они сильно проигрывают CRC по скорости.
не обольщайтсь23.01.03 18:34 Автор: Persicum Статус: Незарегистрированный пользователь
Не все неприводимые многочлены
являются многочленами максимальной длины!!!
Я вот скачал недавно таблицу 5-битовых 32-разрядных полиномов.
Стал проверять, из них набралось тока сто штук с периодом FFFFFFFF,
из огромного числа.
Не обольщайтесь!!!23.01.03 18:31 Автор: Guest Статус: Незарегистрированный пользователь
Не все неприводимые многочлены
являются многочленами максимальной длины!!!
Я вот скачал недавно таблицу 5-битовых 32-разрядных полиномов.
Стал проверять, из них набралось тока сто штук с периодом FFFFFFFF,
из огромного числа.
подробно о проекте
Анализ криптографических сетевых...
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
