Генератор случайных чисел

Вашему вниманию представляю свой собственный генератор случайных чисел, который может быть использован при шифровании:

Код (Text):

1. MOV EAX,1 ; или любой другой ключ который != 0, можно генерировать ключ используя анти дебаг/эму-фишки, неверный ключ - расшифруем мусор
2.  
3. @@1:
4. IMUL EAX,123456791 ; большое случайное простое число
5. BSWAP EAX ; можно заменить на ROL EAX,8 или ROR EAX,24
6.  
7. ; в AL - случайный байт, в AX случайное слово
8. XOR [ESI],AL ; Можно использовать ADD,SUB,... или все всместе, также можно использовать и AH, например добавив ADD [ESI],AH
9. ADD ESI,1 ; или INC ESI
10.  
11. LOOP @@1 ; или что-то типа ADD ECX,-1; JNZ @@1

Несмотря на свою простоту генератор достаточно качественный. Также вместо одного умножения можно добавить два:

Код (Text):

1. @@1:
2.   IMUL EAX,123456791
3.   ROL EAX,16
4.   IMUL EAX,345689647
5.   ROR EAX,24 ; BSWAP EAX

 

encode

Кто вам это сказал?

И вооще какой смысл вы вкладываете в слова "качественный" и "может быть использован при шифровании" ?

 

как по мне, так обычный ДПСЧ для вычисленийа гаммы.. ну отличаецо развечто BSWAP'ом

 

Это проверяется просто, сгенерированная цепочка байтов не сжимается. Также у генератора достаточно длинный период. Вконце концов - проверьте сами - результаты напишите здесь.

 

Ну это статистические свойства, не имеющие никакого отношения к криптографическим требованиям.

Как, например, у вашего генератора деля обстоят с возможностью вычислить seed по нескольким последовательным значениям, им выдаваемым?

Хотя 32-битный seed - это вообще несерьезно для криптографии.

 

Можно использовать одновременно сколько угодно генераторов, скажем 8. В каждом генераторе можно использовать свой метод обновления состояния (seed) + разную инициализацию ключа. Также при шифровании, можно использовать не один XOR а набор действий, скажем:

BYTE = BYTE XOR RND
BYTE = BYTE SUB RND
BYTE = BYTE ADD RND
BYTE = BYTE ROL RND
BYTE = BYTE ROR RND
BYTE = BYTE XOR (BYTE SHL RND)
...

 

Это все замечательно, но с чего вы взяли, что любая мешанина XOR/SUB/ADD/ROL/whatever будет обязательно криптографически стойкой? Известно множество примеров обратного свойства, когда генераторы вот так сходу разрабатываемые дилетантами, оказывались (мягко говоря) далеки от заявленных криптографических характеристик.
Дизайн криптографически стойких PRNG - это серьезное занятие, требующее понимание особенной и тонкостей работы известных генераторов, знание их слабостей и практических атак на конкретные недочеты в дизайне.

Из присутствующих на форуме достаточной квалификацией обладает разве что ruptor - сравните для примера его детище (про которое я мог бы сказать "может быть использован при шифровании", но и то, это требует серьезного исследования) http://cryptolib.com/crypto/chaos/ со своим.

 

сгенерил по первому коду 20 мегабайт данных и прогнав через ENT получил

Код (Text):

1. Entropy = 7.079748 bits per byte.
2.  
3. Optimum compression would reduce the size
4. of this 20971520 byte file by 11 percent.
5.  
6. Chi square distribution for 20971520 samples is 220678345.37, and randomly
7. would exceed this value 0.01 percent of the times.
8.  
9. Arithmetic mean value of data bytes is 101.6097 (127.5 = random).
10. Monte Carlo value for Pi is 3.316038066 (error 5.55 percent).
11. Serial correlation coefficient is 0.376713 (totally uncorrelated = 0.0).

причем байт 0 встречается в 66 раз чаще остальных

приводит статистику DIEHARD тут не буду

 

Как-то вы RElf накинулись сразу, вешая ярлыки не зная кто есть кто...

Генератор для своего размера в две инструкции поидее очень даже не плох. И для своих специфических целей вполне сгодися - например как часть шифрования эгзешника, итд итп.

Ладно, не на тот форум забрел видимо...

 

Зачем изобретать конструкцию не основаную на на одном надежном криптопримитиве, если давным давно существуют схемы стойких PRNG на основе хешей и симмитричных шифров?
Посмотрите дизайн PRNG в составе OpenSSL, посмотрите схемы описаные в fips стандартах.
З.Ы. chaos я бы не считал абсолютно надежным генератором, т.к. он тоже не опирается ни на один известный криптопримитив. Надежная криптографическая конструкция должна быть проверяемой даже непрофессионалами, а это возможно только в том случае, если ее стойкость однозначно сводиться к стойкости уже провереных примитивов.

 

На тот, на тот - где вам еще правду про ваш генератор скажут?

Ярлыков я не вешал, извините, если чем обидел.
А вам на будущее советую не бросаться фразами, смысл которых вы не понимаете. В частности, о пригодности RNG в шифровании. Подучите базу, предложите и обоснуйте дизайн нового генератора (без таких явных дыр как у приведенного выше), и мы с удовольствием продолжим дискуссию.

P.S. В качестве хорошого пособия могу предложить Шнайеровский Self-Study Course in Block Cipher Cryptanalysis.

 

ОК, спасибо!

 

ntldr
К сожалению, абсолютного доказательства стойкости и при отсылке к примитивам достичь не удастся. Потому как сами примитивы - это как аксиомы в математике, в которые верят, но которые могут вдруг оказаться при каких-то условиях неверными (продолжая аналогию с математикой - известный пример: пятый постулат Евклида).

Chaos я защищать не буду, а вот Ruptor возможно захочет (щас позову). Ну а я в сторонке покурю.

 

вот еще одна зарисовка для размышления: Генерация истинно случайных чисел на основе шума звуковых карт

 

Кстати, о проблемах направления "provable security" в криптографии очень хорошо написал в своем эссе известный криптограф и математик (это важно!) Нил Коблиц:

Neal Koblitz "The Uneasy Relationship Between Mathematics and Cryptography".

 

KiNDeR
Там слишком много аппломба. Почитайте более нейтральный обзор подобных генераторов в википедии.

 

Я не заявляю что chaos не стоек, как впрочем не заявляю и обратного. Я просто стараюсь избегать использования конструкций которые не могу проверить сам, исключение тут составляют только широкоизвестные примитивы провереные многими до меня.
К тому же при использовании малоизвестного криптопримитива, будь он даже безопаснее известных, будет очень трудно доказать другим его безопасность. Поэтому не стоит использовать неизвестные примитивы в программах предназначеных не только для себя.

 

Да, спасибо, но это я уже читал неоднократно
В этой статье меня привлекла идея сбора энтропии с железа, идея не нова, но других, подобных, обзоров я не встречал...

 

Я защищать свои шифры не собираюсь. Они и без этого криптостойкие.

Генератор же в первом посте таковым не является и ломается тривиально, как и большинство таких генераторов. Даже с очень большим состоянием его легко сломать если не сделать либо как сделано в Chaos, либо как сделано в EnRUPT. А то, что он проходит тесты на случайность - это ничего не говорит. В основном такие генераторы уязвимы к GD атакам (Guess and Determine) и к угадыванию битов переноса со всеми вытекающими оттуда линейностью и алгебраическими атаками - это даже с большим состоянием, а без него это совсем просто считается через пару формул или таблиц... На таких генераторах надо детей в школах учить как их ломать.

Chaos я с сегодняшнего дня больше не рекомендую за его низкую скорость, повышенную сложность и малую гибкость по сравнению с нашим последним, который я только вчера представил на SASC 2008 после более года поисков и анализа. Слайды тоже выложу когда вернусь домой. Особым параноикам не рекомендую им пока пользоваться конечно, только энтузиастам и тем, кто мне доверяет. После всевозможных оптимизаций он будет отправлен в NIST на SHA-3 competition. Помощь в оптимизации кода и всевозможный криптанализ принимаются.

 

Вообще-то сделать криптостойкий и при этом достаточно быстрый шифр из мешанины ADD-SUB-XOR-ROL-SHR-SHL достаточно легко, если при этом не нарушать особых очень строгих правил. Нарушая или не зная их - невозможно. Большинство конструкций будут либо слишком большими и слишком медленными чтобы быть полезными, либо будут легко ломаемыми, либо и то и другое. Отличить же одну от другой на глаз без большого опыта тестирования их не реально. В этом я согласен с ntldr - лучше даже если понимаешь как оно работает, всё равно не верить автору поделки. Он скорее всего ошибся. Хотя теперь после того как я раздал всем мои тесты и уже четыре бригады академиков взяли их на вооружение и даже опубликовали кое-какие результаты их использования, они очень быстро научатся ими отличать ломаемые шифры от криптостойких и неломаемые шифры теперь будут расти как грибы после дождя... Прощай, паранойя!