От alexio
К Booker
Дата 07.08.2014 17:23:41
Рубрики 11-19 век; Спецслужбы;

Re: [Вулкану] Франсуа...

>А что вы понимаете под сменой шифра? Смену алгоритма щифрования или смену ключа?

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

Тем не менее - суть вопроса именно в понимании математиками деления шифров на классы с очевидным выводом о сроках смены ключей или же алгоритмов. По сути - когда математика доросла до понимания шифрования в современном смысле ?
От Booker
К alexio (07.08.2014 17:23:41)
Дата 08.08.2014 00:08:04

Re: [Вулкану] Франсуа...

>Насколько я знаю, некоторые виды (алгоритмы) шифров предполагают большую статистическую обработку даже в случае простой смены ключа. Вопрос только в объёме этой обработки. Видимо в те далёкие времена ещё не было серьёзной классификации шифров и скорее всего про этот самый критический объём особо не задумывались, когда меняли ключи.
>Тем не менее - суть вопроса именно в понимании математиками деления шифров на классы с очевидным выводом о сроках смены ключей или же алгоритмов. По сути - когда математика доросла до понимания шифрования в современном смысле ?

Пролистайте "Взломщики кодов" Дэвида Кана, он довольно много пишет именно о временах Виета (и о самом Виете в т.ч.). Классика, т.ск. жанра, популярное изложение истории и техники от античности до бегства в СССР двух АНБ-шников в 1960. :))

Коротко - со статистическим анализом (в примитивном понимании) боролись уже тогда (в XVI веке и несколько раньше), используя а) гомофоны (когда одни и те же буквы кодируются несколькими наборами цифр/букв, которые используются, можно сказать, случайно; и б) номенклаторы - словари кодов для отдельных слов, имён и т.п. Собственно, до шифроблокнотов отсюда рукой подать. )))

А шифр Виженера (многоалфавитная замена) - это уже вполне борьба со статанализом. Его изобрели где-то в XV веке итальянцы.

Имхо, по настоящему математики взялись за криптографию, начиная с Шеннона (конец 40-х). А самая красивая математически-криптографическая идея - односторонние функции - это уже 70-е годы где-то.

С уважением.
От alexio
К Booker (08.08.2014 00:08:04)
Дата 08.08.2014 12:22:59

Re: [Вулкану] Франсуа...

>Пролистайте "Взломщики кодов" Дэвида Кана

Скачал, интересно. Спасибо.

>Коротко - со статистическим анализом (в примитивном понимании) боролись уже тогда (в XVI веке и несколько раньше), используя а) гомофоны (когда одни и те же буквы кодируются несколькими наборами цифр/букв, которые используются, можно сказать, случайно; и б) номенклаторы - словари кодов для отдельных слов, имён и т.п. Собственно, до шифроблокнотов отсюда рукой подать.

Эта борьба шла случайным образом или некая классификация в математике уже сформировалась ?

Ну и про Шеннона - до него энигмы всякие надеюсь со знанием дела сочинялись. Значит всё же криптография немного старше. Здесь важно - что считать началом, что ключевого и крайне важного открыл/доказал Шеннон и этого ни кто до него не знал ?
От Booker
К alexio (08.08.2014 12:22:59)
Дата 08.08.2014 15:08:23

Re: [Вулкану] Франсуа...

>Эта борьба шла случайным образом или некая классификация в математике уже сформировалась ?

Нет, во всяком случае об этом ничего неизвестно. Нет опубликованных работ, хотя, например, где-то мне попадалась статья о вкладе математиков МГУ в криптографическую проблематику в годы ВОВ. А так - Зйлер (когда работал на Академию Наук), например, привлекался к расшифровке перехваченных дипломатических шифровок. Но работ по криптоанализу у него нет.

>Ну и про Шеннона - до него энигмы всякие надеюсь со знанием дела сочинялись. Значит всё же криптография немного старше. Здесь важно - что считать началом, что ключевого и крайне важного открыл/доказал Шеннон и этого ни кто до него не знал ?

Ув. Zevs прав, до Шеннона криптография была ремеслом - ну, или искусством, что довольно близко. Эмпирическим образом усовершенствовались шифры, изобретённые ещё чуть ли не римлянами, и уж точно - арабами. Занимались ей просто неглупые люди :)), тот же Плейфер (автор одноименного шифра) - химик по образованию и роду деятельности, дешифровщик Касиски - археолог, Керкхоффс - филолог, лингвист и изобретатель волапюка :). Шербиус (изобретатель Энигмы) - инженер-электрик. К расшифровке тоже подходили с точки зрения здравого смысла, по крайней мере до 20-х годов, когда уже начали появляться математические работы по криптографии. В расшифровке Энигмы засветились польские математики и Тьюринг. Но считается, что Шеннон - открыватель эры, хотя историки математики наверняка могут аргументированно возразить. В любом случае, ошибка не превысит лет 20 (если мы будем Шеннона считать отцом-основателем). Собственно, его статью можно и самому заценить.

http://pv.bstu.ru/crypto/shannon.pdf

С уважением.
От alexio
К Booker (08.08.2014 15:08:23)
Дата 09.08.2014 15:13:13

Re: [Вулкану] Франсуа...

>К расшифровке тоже подходили с точки зрения здравого смысла, по крайней мере до 20-х годов, когда уже начали появляться математические работы по криптографии.

Подходили на основе научной базы, накопленной к моменту дешифровки. Шеннон же тоже не с луны свалился и открыл нужные закономерности. Была некая цепочка развития знаний, а Шеннон (и научное сообщество США) эту цепочку систематизировали, добавив что-то своё. Наверное именно открытость систематизации стало ключевым - теперь каждый может с умным видом говорить о понимании криптографии :)
От Zevs
К alexio (09.08.2014 15:13:13)
Дата 10.08.2014 00:39:13

Re: [Вулкану] Франсуа...

Ave!

>Подходили на основе научной базы, накопленной к моменту дешифровки. Шеннон же тоже не с луны свалился и открыл нужные закономерности. Была некая цепочка развития знаний, а Шеннон (и научное сообщество США) эту цепочку систематизировали, добавив что-то своё.

Да, именно в этом заслуга Шеннона.
Вообще удивительно, что его работу пропустили цензоры. ;)

> Наверное именно открытость систематизации стало ключевым - теперь каждый может с умным видом говорить о понимании криптографии :)

Ну теперь все разбираются одинаково хорошо в футболе, сельском хозяйстве, дизайне, стрельбе из "Бук"-ов, программировании микроконтроллеров и т.д и т.п.. И животноводстве. (с) И криптографии.

Таков современный мир. :)

Vale!
От alexio
К Zevs (10.08.2014 00:39:13)
Дата 10.08.2014 12:57:39

Re: [Вулкану] Франсуа...

>Да, именно в этом заслуга Шеннона.
>Вообще удивительно, что его работу пропустили цензоры. ;)

Ну так - ничего нового кроме систематизации. Цензор не увидел секрета в обобщении знаний. И в общем-то в обобщении действительно нет секрета. Но польза была и для противников США.
От Zevs
К alexio (08.08.2014 12:22:59)
Дата 08.08.2014 13:48:35

Re: [Вулкану] Франсуа...

Ave!

>Ну и про Шеннона - до него энигмы всякие надеюсь со знанием дела сочинялись. Значит всё же криптография немного старше.

Криптография до Шеннона была больше ремеслом, чем наукой, если очень. грубо.

> Здесь важно - что считать началом, что ключевого и крайне важного открыл/доказал Шеннон и этого ни кто до него не знал ?

Шеннон математически сформулировал, т.е. обобщил все "шифровальные изыски", подвёл мат. базу и сделал криптографию наукой.

Вообще, говорят, что статья вышла в открытую печать случайно. :)

Vale!
От alexio
К Zevs (08.08.2014 13:48:35)
Дата 09.08.2014 15:02:39

Re: [Вулкану] Франсуа...

>Криптография до Шеннона была больше ремеслом, чем наукой, если очень. грубо.

Может всё же - была непубличной наукой. А Шеннон отдал её публике (не без пользы для криптографии).
От Zevs
К alexio (09.08.2014 15:02:39)
Дата 10.08.2014 01:37:22

Re: [Вулкану] Франсуа...

Ave!
>>Криптография до Шеннона была больше ремеслом, чем наукой, если очень. грубо.
>
>Может всё же - была непубличной наукой. А Шеннон отдал её публике (не без пользы для криптографии).

Поскольку приходилось читать в своё время много разного из разных годов и переводов с разных языков и наших отечественных работ тоже: было разделение на криптологию (не систематизированные знания) и криптографию (знания систематизированные).

"Не публичность" -- гибель для науки.





Vale!
От alexio
К Zevs (10.08.2014 01:37:22)
Дата 10.08.2014 13:00:10

Re: [Вулкану] Франсуа...

>"Не публичность" -- гибель для науки.

Скорее возможность застоя в локальных экстремумах. Публичность же увеличивает количество вариантов перебора направлений развития, чем повышает вероятность перехода от локального холма к хоть и далёкой, но гораздо более высокой вершине.
От Zevs
К alexio (09.08.2014 15:02:39)
Дата 10.08.2014 00:27:27

Re: [Вулкану] Франсуа...

Ave!

>>Криптография до Шеннона была больше ремеслом, чем наукой, если очень. грубо.

>Может всё же - была непубличной наукой. А Шеннон отдал её публике (не без пользы для криптографии).

Это вопрос философской формулировки понятия "наука".

По современному (пост-позитивистскому) философскому подходу к науке, "наука", а точнее теория или научная концепция д.б. публичными, т.е. максимально фальсифицируемыми. См. философов 20-го века: Кун, Лакатос, Фейерабенд. Только боюсь, уже выхожу за рамки ВИ-тематики. ;)

Проблема криптографии как науки долго крылась в закрытости ("спецслужбы"), что закрывало возможность фальсифицируемости того или иного алгоритма. И для криптографии сейчас считается как раз подтверждением стойкости алгоритма шифрования его полная публичность. Т.е. возможная подверженность для криптоаттак. И чем больше аттак на алгоритм, тем лучше для алгоритма.

Vale!
От Zevs
К Zevs (08.08.2014 13:48:35)
Дата 08.08.2014 13:59:22

Re: [Вулкану] Франсуа...

Ave!

>>Ну и про Шеннона - до него энигмы всякие надеюсь со знанием дела сочинялись. Значит всё же криптография немного старше.

Конечно старше. Но не как наука в философском понимании.

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

Vale!
От Zevs
К Booker (08.08.2014 00:08:04)
Дата 08.08.2014 04:06:23

Re: [Вулкану] Франсуа...

Ave!

>Имхо, по настоящему математики взялись за криптографию, начиная с Шеннона (конец 40-х).

Да собственно статья Шеннона и считается рождением/оформлением симметричной криптографии.

> А самая красивая математически-криптографическая идея - односторонние функции - это уже 70-е годы где-то.

Да, так и есть. Простейшая задача асиметричной криптографии -- это задача "укладки ранца". Что весьма Военно-Исторично. :)

>С уважением.
Vale!
От Dargot
К alexio (07.08.2014 17:23:41)
Дата 07.08.2014 17:38:46

Re: [Вулкану] Франсуа...

Приветствую!

>Тем не менее - суть вопроса именно в понимании математиками деления шифров на классы с очевидным выводом о сроках смены ключей или же алгоритмов. По сути - когда математика доросла до понимания шифрования в современном смысле ?

Смотря что Вы понимаете под "современным смыслом":)
Теоретически математики взялись за криптографию, ЕМНИП, в середине-конце 19-го века.

С уважением, Dargot.
От alexio
К Dargot (07.08.2014 17:38:46)
Дата 08.08.2014 12:28:30

Re: [Вулкану] Франсуа...

> Теоретически математики взялись за криптографию, ЕМНИП, в середине-конце 19-го века.

В смысле если что-то из серии о теории обработки информации, то это середина 20-го века. Но без таких глубоких и многоплановых (не только для криптографии) обобщений шифрованием занимались очень давно и наработали кучу стандартных алгоритмов. Вот на сколько эта куча была систематизирована с течением времени и есть вопрос. Условно - 16+17-й век дал набор сырых алгоритмов, 18-й их систематизировал, 19-й выработал серьёзную базу вокруг темы, ну а 20-й привёл в современный вид с кучей дополнительных приложений помимо шифрования.
От Zevs
К Dargot (07.08.2014 17:38:46)
Дата 07.08.2014 23:13:54

Re: [Вулкану] Франсуа...

Ave!
>>Тем не менее - суть вопроса именно в понимании математиками деления шифров на классы с очевидным выводом о сроках смены ключей или же алгоритмов. По сути - когда математика доросла до понимания шифрования в современном смысле ?

Алгоритмы меняются. В США был когда-то DES. Его вдоль и поперёк изучали, ломали и таки сломали. Сейчас AES.

У нас ГОСТ 27148-89. Пока не отменяют, хотя с 1989-ого года в работе. Живёт за счёт длины ключа и не постулируемой таблицы замен.

> Смотря что Вы понимаете под "современным смыслом":)
> Теоретически математики взялись за криптографию, ЕМНИП, в середине-конце 19-го века.

А фактически криптография в современном понимании как наука родилась (или оформилась) только после Второй Мировой. ;)

Vale!
От NV
К Zevs (07.08.2014 23:13:54)
Дата 08.08.2014 00:02:33

DES никто не сломал

>Ave!
>>>Тем не менее - суть вопроса именно в понимании математиками деления шифров на классы с очевидным выводом о сроках смены ключей или же алгоритмов. По сути - когда математика доросла до понимания шифрования в современном смысле ?
>
>Алгоритмы меняются. В США был когда-то DES. Его вдоль и поперёк изучали, ломали и таки сломали. Сейчас AES.

просто 56-битный ключ сейчас с современными ресурсами можно подобрать методом грубой силы - а это вообще говоря не взлом. А вот Triple DES - это уже 168 бит. Тут Brute force пока бессильна.

Виталий
От Zevs
К NV (08.08.2014 00:02:33)
Дата 08.08.2014 03:33:43

Re: DES никто...

Ave!

http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi?1991/CS/CS0708
http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi?1996/CS/CS0885

И до кучи про алгоритмы шифрования в GSM:

http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi?2003/CS/CS-2003-05


Vale!
От Zevs
К NV (08.08.2014 00:02:33)
Дата 08.08.2014 03:17:32

Re: DES никто...

Ave!
>>Алгоритмы меняются. В США был когда-то DES. Его вдоль и поперёк изучали, ломали и таки сломали. Сейчас AES.
>
>просто 56-битный ключ сейчас с современными ресурсами можно подобрать методом грубой силы - а это вообще говоря не взлом. А вот Triple DES - это уже 168 бит. Тут Brute force пока бессильна.

Вообщето есть методы криптоанализа отличные от brutalforce, ага.

В частности, моя дипломная работа в 2001-ом была на тему дифференциального криптоанализа ГОСТ 28147-89. Применение ДКА для ГОСТ-а делал по успешно проведённой атаке на DES. ГОСТ на ДКА, кстати, не поддался. Точнее поддался, но до определённого числа раундов алгоритма.

Если что, то Triple-DES методом ДКА (DCA) вполне себе ломается.

Всё-таки, DES, хоть основной, хоть 3-DES оказался слабым со временем.

На смену пришла схема "квадрат" (с принятой после публичного обсуждения алгоритма Rijelnal), ставшей основой нового алгоритма AES.

Vale!