Математика в криптографии (SATve)

SATtva! Для конечных пользователей все нормально. Но не хватает некоего раздела, касающегося самих мат основ криптографии. Что касается информации из книг и интернета, то

1. я до сих пор не нашел даже доказательства бинома Ньютона (вернее, оно имеется, но уже на основе теории вероятностей, которая была разработана позже самого доказательства), когда пирамидка Пифагора может вычисляться и по факториальным формулам. Из школьной программы его не помню. Потом эта хрень используется в Малой Ферма, а затем обобщении Эйлера, а затем в RSA, ESIGN и других, которые базируются на возведении в степень по модулю. Тобишь открытое крипто;
2. Упоминаемый Брюсом Ш. некий NFS, который факторизирует аж логарифмически (если не путаю), мной нигде не найден. Из моих личных догадок, можно применить анализ правой части числа с переменным radix;
3. что касается закрытого крипто, то диффер и др. виды криптоанализа описаны лишь в терминологии, но математики в нете нету )-: При этом "магические" цифры в IDEA, 3DES и других – для меня до сих пор загадка...

Ну вот. Может тут иногда обитают люди, которые напрямую занимаются криптоанализом либо созданием алгоритмов. Типа, бывают, которым это действительно может быть интересно, и они что-то знают. Книжки, увы, не особенно помогают, потому как некоторые доказательства опущены.

Ну еще было бы в итоге (в дальнейшем) неплохо создать компиляцию всей информации в библиотеке (-:

Комментарии

—	SATtva (27/10/2006 20:51, исправлен 27/10/2006 20:58) профиль/связь <#> комментариев: 11558 документов: 1036 редакций: 4118

Интересующиеся могут посмотреть архив IACR (есть в Ссылках) и почитать учебники по математике (кроме того, многое обсуждалось в форуме, можно и здесь поискать ссылки). Не вижу смысла, чтобы дублировать это здесь, но если кто-то возьмётся поработать над этим — оно не повредит. Сайт ведь переведён на wiki не случайно — у меня времени в любом случае не хватит на всё. Поэтому заинтересованные лица могут заниматься и без моего участия.

—	незнайка (27/10/2006 21:10) профиль/связь <#> комментариев: 29 документов: 2 редакций: 8

Угу... ну так просьба создать раздел "Математика" на форуме.
И в Библиотеке тоже.

И если есть возможность создавать подкаталоги, то будет примерно так:

Математика в криптографии:
1. Сама математика
1. 1. История
1. 2. Теоремы и доказательства
2. Криптоанализ
2. 1. Факторизация
2. 2. Линейный
2. 3. Дифференциальный
2. 4. Иные виды
3. Поиск алгоритмов
3. 1. Открытые ключи
3. 2. Закрытые ключи
3. 3. Хэши

—	SATtva (27/10/2006 23:27) профиль/связь <#> комментариев: 11558 документов: 1036 редакций: 4118

В Черновиках можете сами делать всё, что хочется. Создайте новый кластер с подстраницами. Просто введите в браузер что-нибудь, вроде
www.pgpru.com/Библиотека/Черновики/Математика
Так же создаются и подстраницы. Когда наберётся достаточно фактического материала и всё будет достаточно "причёсано", подумаем, где это стоит разместить на ПМЖ.

—	unknown (30/10/2006 09:21, исправлен 30/10/2006 09:34) профиль/связь <#> комментариев: 9796 документов: 488 редакций: 5664

Огромное количество материалов есть в сети, вот самые известные для тех, кому нужно серьёзно изучить теорию крипто с нуля:

Introduction to Modern Cryptography
By: Mihir Bellare and Phillip Rogaway

http://www-cse.ucsd.edu/users/.....e207/classnotes.html

An introduction to cryptography
By; Ed Schaefer

file

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 большой раздел по крипто и соотв. математике. Всё уже сделано до нас. Если только у кого есть время заниматься переводом.

—	незнайка (30/10/2006 19:22) профиль/связь <#> комментариев: 29 документов: 2 редакций: 8

окей... что касается NFS (применение полиндромов и lattice + line sieving) для факторизации,
то он действительно описан в английском в вики. достаточно грамотно. Но можно ли NFS применять для Esign – не вкурсе (там не P*Q, а P*P*Q используется). Вот тута
http://en.wikipedia.org/wiki/General_number_field_sieve

что касается бинома нютона (доказательство не из теории вероятностей, а то, каким путем дошел сам Нютон), не нашел таки (-:

что касается магических чисел IDEA, 3DES, ГОСТ и иже с ними + комментарии с точки зрения див, линейного и иных видов криптоанализа, то тоже пока не нашел....

—	SATtva (30/10/2006 22:27) профиль/связь <#> комментариев: 11558 документов: 1036 редакций: 4118

Если найдёте описание выработки узлов замены для ГОСТа, свистните. Вы станете первым счастливчиком.

—	*Гость* (31/10/2006 03:31) <#>

а что, это так секретно? Где то читал, что, ГОСТ, это упрощенный DES (?). Если не путаю. Там вроде наростили количество рангов, но чего-то убрали. может, именно по этому (посчитали, что сильный криптоанализ может его угробить), публикацию всех данных и заморозили ...

—	*Гость* (31/10/2006 08:45) <#>

узел замены – это P-box? Или что?

—	unknown (31/10/2006 09:03) профиль/связь <#> комментариев: 9796 документов: 488 редакций: 5664

узел замены – это P-box?

S – substitution – замена

P – permutation – перестановка

Для DES S-блоки рассчитывались по эвристическому алгоритму методом перебора возможных вариантов, критерии были опубликованы позднее, но полного описания нет. По ГОСТу нет вообще ничего.

IDEA (и его производные) использует свойства некоммутавности операции умножения с простым числом 2^16+1, сложения по модулю 2^16 и простого XOR. За счёт этого образована нелинейная функция, своего рода алгеьраический S-блок.

Для вычисления подключей, ключевой блок из 128-бит разбивается на 16 подблоков, которые используются как первые из восьми подблоков.

128-битный ключ сдвигается влево на 25 позиций после чего снова разбивается на 16 подблоков и так 8 раз.

Подробности смотрите в описаниях и какие там числа магические я так и не понял.

—	unknown (31/10/2006 09:08) профиль/связь <#> комментариев: 9796 документов: 488 редакций: 5664

+ комментарии с точки зрения див, линейного и иных видов криптоанализа, то тоже пока не нашел....

Да на 3DES все методы анализа опробованы! Насчёт IDEA, тоже много работ, особенно когда она проходила через конкурс CryptoNESSIE и когда создавлаись производные шифры – Mesh и FOX.

Только для ГОСТ работ не очень много, согласен.

Ваша оценка документа [показать результаты]