Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
| | | |
bloom filter это... 07.12.02 15:00 Число просмотров: 3913
Автор: SemenU Статус: Незарегистрированный пользователь
|
> > Сгенерировать их в домашних условиях не получилось (долго
> > это, разве нет?),
> Вовсе нет. Например, см. ниже по ссылке.
>
Спасибо, почитаю...
> > [skiped про bloom фильтр]
> Что-то я все равно не понял, что дано и что нужно получить.Вот ссылка про эти самые фильтры, там все просто...
http://www.cs.wisc.edu/~cao/papers/summary-cache/node8.html
|
|
<theory>
|
полиномы для CRC32 или... 05.12.02 00:47
Автор: SemenU Статус: Незарегистрированный пользователь
|
Собственно проблема состоит в том, что нужно много (хотя бы штук 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 занимался - много чего интересного нарыл. Посмотри на страничке и дальше по ссылкам:
CRC64 и не только
|
| |
попробуем... 07.12.02 03:06
Автор: SemenU Статус: Незарегистрированный пользователь
|
За ссылку спасибо... Почитал и решил обойтись простыми полиномами...
Сгенерировать их в домашних условиях не получилось (долго это, разве нет?), а вот готовых нашелся список из 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 выдет быстрее и
> экономнее.
Что-то я все равно не понял, что дано и что нужно получить.
A fast algorithm for listing all degree n irreducible and primitive polynomials over GF(2)
|
| | | |
bloom filter это... 07.12.02 15:00
Автор: SemenU Статус: Незарегистрированный пользователь
|
> > Сгенерировать их в домашних условиях не получилось (долго
> > это, разве нет?),
> Вовсе нет. Например, см. ниже по ссылке.
>
Спасибо, почитаю...
> > [skiped про bloom фильтр]
> Что-то я все равно не понял, что дано и что нужно получить.Вот ссылка про эти самые фильтры, там все просто...
http://www.cs.wisc.edu/~cao/papers/summary-cache/node8.html
|
|
... или...сrc_start=0xfffffffe,0xfffffffd...или число раундов... 05.12.02 09:37
Автор: Chingachguk <Chingachguk> Статус: Member
|
> Собственно проблема состоит в том, что нужно много (хотя бы
> штук 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-ти битам:
;static void MDTransformF (UINT4 s[4, UINT4 x16])
PFF s0,s1,s2,s3,x0,S11,0d76aa478h ; // 1
PFF s3,s0,s1,s2,x1,S12,0e8c7b756h ; // 2
...
PFF s1,s2,s3,s0,x15,S14,049b40821h ; // 16
; static void MDTransformG (UINT4 s[4, UINT4 x16])
PGG s0,s1,s2,s3,x1,S21, 0f61e2562h ; // 17
PGG s3,s0,s1,s2,x6,S22, 0c040b340h ; // 18
...
PGG s1,s2,s3,s0,x12,S24,08d2a4c8ah ; // 32
; static void MDTransformH (UINT4 s[4, UINT4 x16])
PHH s0,s1,s2,s3,x5,S31, 0fffa3942h ; // 33
PHH s3,s0,s1,s2,x8,S32, 08771f681h ; // 34
...
PHH s1,s2,s3,s0,x2,S34, 0c4ac5665h ; // 48
; static void MDTransformI (UINT4 s[4, UINT4 x16])
PII s0,s1,s2,s3,x0,S41, 0f4292244h ; // 49
PII s3,s0,s1,s2,x7,S42, 0432aff97h ; // 50
...
PII s1,s2,s3,s0,x9,S44, 0eb86d391h ; // 64
Если выкинуть(изменить) часть таких преобразований, то можно получить (в ущерб стойкости ?) совершенно другой хэш.
Про трайпл-дез - совершенно другая была мысль. Собственно, смотри сам трайпл. Можно сделать трайпл-MD5 или дабл-DES.
|
| | | |
боюсь с другими алгоритмами получится, как с CRC 10.12.02 08:17
Автор: SemenU Статус: Незарегистрированный пользователь
|
> Нет. Я предлагал видоизменить алгоритм какого-нибудь хэша,
> например 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-function 08.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" в
Handbook of Applied Cryptography
|
| | | | | |
спасет collision-resistant hash-function 09.12.02 15:45
Автор: SemenU Статус: Незарегистрированный пользователь
|
> > Например, пусть 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,
из огромного числа.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
