Математика в криптографии (SATve)
SATtva! для конечных пользователей все нормально. Но не хватает некоего раздела, касающегося самих мат основ криптографии. Что касается информации из книг и интернета, то
1. я до сих пор не нашел даже доказательства бинома Ньютона (вернее, оно имеется, но уже на основе теории вероятностей, которая была разработана позже самого доказательства), когда пирамидка Пифагора может вычисляться и по факториальным формулам. Из школьной программы его не помню. Потом эта хрень используется в Малой Ферма, а затем обобщении Эйлера, а затем в RSA, ESIGN и других, которые базируются на возведении в степень по модулю. Тобишь открытое крипто;
2. Упоминаемый Брюсом Ш. некий NFS, который факторизирует аж логарифмически (если не путаю), мной нигде не найден. Из моих личных догадок, можно применить анализ правой части числа с переменным radix;
3. что касается закрытого крипто, то диффер и др. виды криптоанализа описаны лишь в терминологии, но математики в нете нету )-: При этом "магические" цифры в IDEA, 3DES и других – для меня до сих пор загадка...
Ну вот. Может тут иногда обитают люди, которые напрямую занимаются криптоанализом либо созданием алгоритмов. Типа, бывают, которым это действительно может быть интересно, и они что-то знают. Книжки, увы, не особенно помогают, потому как некоторые доказательства опущены.
Ну еще было бы в итоге (в дальнейшем) неплохо создать компиляцию всей информации в библиотеке (-:
Интересующиеся могут посмотреть архив IACR (есть в Ссылках[link1]) и почитать учебники по математике (кроме того, многое обсуждалось в форуме, можно и здесь поискать ссылки). Не вижу смысла, чтобы дублировать это здесь, но если кто-то возьмётся поработать над этим — оно не повредит. Сайт ведь переведён на wiki не случайно — у меня времени в любом случае не хватит на всё. Поэтому заинтересованные лица могут заниматься и без моего участия.
Угу... ну так просьба создать раздел "Математика" на форуме.
И в Библиотеке тоже.
И если есть возможность создавать подкаталоги, то будет примерно так:
Математика в криптографии:
1. Сама математика
1. 1. История
1. 2. Теоремы и доказательства
2. Криптоанализ
2. 1. Факторизация
2. 2. Линейный
2. 3. Дифференциальный
2. 4. Иные виды
3. Поиск алгоритмов
3. 1. Открытые ключи
3. 2. Закрытые ключи
3. 3. Хэши
В Черновиках можете сами делать всё, что хочется. Создайте новый кластер с подстраницами. Просто введите в браузер что-нибудь, вроде
www.pgpru.com/Библиотека/Черновики/Математика
Так же создаются и подстраницы. Когда наберётся достаточно фактического материала и всё будет достаточно "причёсано", подумаем, где это стоит разместить на ПМЖ.
Огромное количество материалов есть в сети, вот самые известные для тех, кому нужно серьёзно изучить теорию крипто с нуля:
Introduction to Modern Cryptography
By: Mihir Bellare and Phillip Rogaway
http://www-cse.ucsd.edu/users/.....e207/classnotes.html[link2]
An introduction to cryptography
By; Ed Schaefer
http://math.scu.edu/~eschaefe/crylec.pdf
Handbook of applied cryptograhy
by: Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone
http://www.cacr.math.uwaterloo.ca/hac/
Есть еще слайды, видеокурсы и масса обучающего материала.
У меня к сожалению "out of time" собрать всё это воедино. Google Вам в помощь!
P. S. Собственно даже в английской Wikipedia большой раздел по крипто и соотв. математике. Всё уже сделано до нас. Если только у кого есть время заниматься переводом.
окей... что касается NFS (применение полиндромов и lattice + line sieving) для факторизации,
то он действительно описан в английском в вики. достаточно грамотно. Но можно ли NFS применять для Esign – не вкурсе (там не P*Q, а P*P*Q используется). Вот тута
http://en.wikipedia.org/wiki/General_number_field_sieve
что касается бинома нютона (доказательство не из теории вероятностей, а то, каким путем дошел сам Нютон), не нашел таки (-:
что касается магических чисел IDEA, 3DES, ГОСТ и иже с ними + комментарии с точки зрения див, линейного и иных видов криптоанализа, то тоже пока не нашел....
Если найдёте описание выработки узлов замены для ГОСТа, свистните. Вы станете первым счастливчиком.
а что, это так секретно? Где то читал, что, ГОСТ, это упрощенный DES (?). Если не путаю. Там вроде наростили количество рангов, но чего-то убрали. может, именно по этому (посчитали, что сильный криптоанализ может его угробить), публикацию всех данных и заморозили ...
узел замены – это P-box? Или что?
S – substitution – замена
P – permutation – перестановка
Для DES S-блоки рассчитывались по эвристическому алгоритму методом перебора возможных вариантов, критерии были опубликованы позднее, но полного описания нет. По ГОСТу нет вообще ничего.
IDEA (и его производные) использует свойства некоммутавности операции умножения с простым числом 2^16+1, сложения по модулю 2^16 и простого XOR. За счёт этого образована нелинейная функция, своего рода алгеьраический S-блок.
Для вычисления подключей, ключевой блок из 128-бит разбивается на 16 подблоков, которые используются как первые из восьми подблоков.
128-битный ключ сдвигается влево на 25 позиций после чего снова разбивается на 16 подблоков и так 8 раз.
Подробности смотрите в описаниях и какие там числа магические я так и не понял.
Да на 3DES все методы анализа опробованы! Насчёт IDEA, тоже много работ, особенно когда она проходила через конкурс CryptoNESSIE и когда создавлаись производные шифры – Mesh и FOX.
Только для ГОСТ работ не очень много, согласен.