Алгоритм GTEA - новый симметричный криптоалгоритм

GTEA 6/9/32
ENT: 263.92 (1,0309375)
CRC32 -e: 1.0309


GTEA 4/5/16
ENT: 258.29 (1,0089453125)
CRC32 -e: 1.0089


Кстати, радует то, у вас достаточно шустро считает и отображает нагляднее, уже в пересчете CHI/256. Подумываю ENT перекомпилировать с пересчетом и буферизацией.

Не думали добавить Monte Carlo PI, Arithmetic mean value, Serial correlation coefficient и тд.? Все есть в исходниках того же ENT. Есть еще просто чудесная программа - DieHarder, аналог знаменитого DIEHARD, в исходниках, там еще целый ряд довольно продвинутых тестов.

 

Модифицировал ENT - убрано все лишнее, процесс значительно ускорен за счет буферизации (ранее данные читались посимвольно), для удобства результат выводится в файл.

 

особо шустро не может, поскольку там 64-битные типы. Но зато должно работать для длинных файлов.
попробуйте еще crc32 -e -m

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

энтропия отличает файлы непожатые и пожатые,
хи-кватрат отличает файлы пожатые и шифрованные (если заголовки не слишком велики)

Что еще можно придумать, чтобы выражалось одной цифрой и было полезно на практике?
Может думаю Дюрбин-Ватсон туда вставить? Но забыл, зачем он нужен...

Что касается Пи, так монекарло его вычисляет три знака максимум... Неинтересно.

А что там у нас с биграммами? По биграммам энтропию 100.0% (т.е. с точностью 3-4 знака) довольно трудно получить. У меня получалось для RSA и для Рида-Соломона, а так может и 99.8% выскочить. Ну и файл разумеется должен быть довольно длинным.

 

Обязьянки, дни рождения и иной набор в духе diehard можно применять иногда для статистического тестирования поточных шифров на базе ГПСЧ, Г(П)СЧ и прочего выявения слабых генераторов и откровенно слабых шифров. Конечно, SQUEEZE, BITSTREAM, COUNT 1's, RANK 6x8 тоже четко обозначат просто упакованный файл.

Добавил тут в ENT ряд упрощенных тестов из diehard, просто для доп. информации. Толком пока не проверял. См. вложение.

Результат выглядит так:

Код (Text):

1. ENT pseudorandom test battery.
2. Recoded edition by Alexander Myasnikov.
3. Web: www.darksoftware.narod.ru
4.  
5. Test results for file rnd.
6. Entropy = 8.000000 bits per byte.
7.  
8. Optimum compression would reduce the size
9. of this 1073741824 bytes file by 0 percent.
10.  
11. Chi square distribution for 1073741824 samples is 258.29 (factor 1.0089386), and randomly
12. would exceed this value 43.07 percent of the times.
13.  
14. Arithmetic mean value of data bytes is 127.4991 (127.5 = random).
15. Monte Carlo value for Pi is 3.141625900 (error 0.00 percent).
16. Serial correlation coefficient is 0.000005 (totally uncorrelated = 0.0).
17.  
18.  
19. BIRTHDAY TEST p-value: 0.832306
20.  
21. BITSTREAM TEST p-value: 0.502218
22.  
23. CDPARK TEST p-value: 0.136555
24.  
25. COUNT 1's TEST p-value: 0.670955
26.  
27. CRAP TEST p-value: 0.855198
28.  
29. MINDIST TEST p-value: 0.334692
30.  
31. OSUM TEST p-value: 0.362233
32.  
33. RANK 31x31 TEST p-value: 0.723333
34.  
35. RANK 32x32 TEST p-value: 0.152956
36.  
37. RANK 6x8 TEST p-value: 0.563515
38.  
39. RUNS TEST p-value: 0.176336
40.  
41. SPHERE 3D TEST p-value: 0.144516
42.  
43. SQUEEZE TEST p-value: 0.290108

Автокорреляция, d-тест Дурбина-Ватсона

или в En-WIKI: Durbin–Watson_statistic

Используется и для тестирования Г(П)СЧ.

Кстати, у вас есть исходники?


P.S. алгоритма компрессии PAQ/LPAQ, по крайней мере 8 редации (см. мой плагин для TC - PPMPackTC), вроде бы часто показывает хороший хи квадрат (по крайней мере для не очень больших файлов и значительно лучше WinRar), бывает и проходит ряд тестов diehard (особенно, если сжимать, к примеру, PE файлы). Это очень сильно отличает PAQ от других алгоритмов комрессии.

 

Зарелизил тест Доктора-Ватсона. Долго думал, делить на 2 или нет, там прекрасная двойка получается, потом решил всештаки пронормировать и его =)))

Код (Text):

1. RAR-архив:
2.  8-bit: 100.0%
3.  Chi^2: 948.5197
4.   DW/2: 1.0020
5. 16-bit: 100.0%
6.  Chi^2: 10.3919
7.   DW/2: 0.9989
8.  
9.  
10. RAR-архив шифрованный:
11.  8-bit: 100.0%
12.  Chi^2: 1.0397
13.   DW/2: 1.0000
14. 16-bit: 100.0%
15.  Chi^2: 0.9986
16.   DW/2: 1.0000
17.  
18. Все ЖЕПЕГИ на диске C:
19. crc32 -e -r c:*.jpg
20.  8-bit: 99.7%
21.  Chi^2: 165422.2529
22.   DW/2: 0.9422
23. 16-bit: 97.9%
24.  Chi^2: 60871.6247
25.   DW/2: 0.9168

 

Спасибо, интересная информация. Интересно, а что относительно доктора ватсона и гпсч?

Протестировал GTEA 1.2ks в режиме OFB:

Код (Text):

1. Total Entropy:
2.  8-bit: 100.0%
3.  Chi^2: 0.9908
4.   DW/2: 1.0000
5. 16-bit: 100.0%
6.  Chi^2: 1.0075
7.   DW/2: 1.0000
8. All OK

 

Отличные показатели, лучше не бывает

 

Не поделитесь примером реализации теста доктора ватсона? Хотелось бы в ENT тоже добавить.

 

Код (Text):

1.  n:=1664525*n+1013904223;

Ну хорошо, пусть имеется к примеру простейший конгруэнтный ГПСЧ.
Каким тестом из коллекции ENT-DieHard можно показать его несостоятельность по сравнению с истинно-случайными числами?

 

persicum
IMHO Chi-Square probability.

 

А кто сказал, что ХИ^2=0.25 это плохо?

 

Как пишет Кнут в своей теории, отдельно взятый тест не дает гарантии случайности, тот же хи-квадрат. Думаю, большая совокупность тестов на случайность, строгие тесты, вроде горилы, битстрима, несколько из первых добавленных мною в ENT - они довольно четко отличают откровенно слабые поточные шифры и ГПСЧ, что становиться заметно по провалу в ряде тестов. Повторю, что они не гарантируют их безопасность - вполне возможно такой шифр ломается тривиально. Но последовательность считается близкой к случайной, что для ГПСЧ уже достаточно в большинстве случаев. Не думаю, что кто-то выделить один единственный тест, дающий гарантированный результат да-нет. Как пишет Кнут, необходим целый ряд дополнительных проверок помимо статистического анализа. В нашем случае, думаю, хорошим подспорьем являются battery of tests, вроде DIEHARD, FIPS, CryptX и Defectoscopy от Ruptor'а, который довольно эффективно отличает слабые шифры, и, вероятно, генераторы.

 

Поскольку простейший КГПСЧ проходит все тесты ENT+DieHard, то зачем вставлять туда еще DW который он тоже проходит?

 

persicum
Chi Square и Chi Square Probability несколько разные вещи.
Воскури Кнута том 2. гл. 3.3.1
С абзаца "Возвратимся к вопросу "Чему равно приемлемое значение V?"." если у тебя в русском переводе.

В итоге:

А чистое значение Chi square бесполезно.

 

Вот-вот, о чем я и говорил. Кнут все еще в силе.

А как вы относитесь к NIST test battery. Что нам предлагает самая уважаемая гос. структура в области криптографии? Насколько можно доверять успешно пройденным тестам?

 

alexanderwm
Сорри, за небольшой оффтопик, но цифер внушаить! Можно сказать, с первого взгляда

 

Проблема Google Groups, перекодировка в КОИ, к-рый используется в fido7

см. здесь

 

Напиши им туда латиницей что твоё исходное сообщение в UTF8 )
А они видят его как KOI8-R

А то там народ уже гадает:

 

Спасибо, я уже ответил в КОИ8 через ньюсридер, проверил, читается нормально.