От Николай Поникаров
К All
Дата 07.08.2014 13:56:42
Рубрики 11-19 век; Спецслужбы;

[Вулкану] Франсуа Виет и шифры

День добрый.

http://vif2ne.ru/nvk/forum/2/co/2598067.htm

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

ФАПСИ Филиппа II называлось Despacho Universal. Оно разрабатывало два сеймейства шифров - cifra general для связи короля с посольствами и cifra particular для связи короля с прочими абонентами.

Франсуа Виет работал над шифрами с 1588 по 1594, сломал несколько испанских и итальянских шифров.

28 октября 1589 Генрих IV дал Виету задание ломануть номенклатор испанского посольства в Париже. Виет справился с этой задачей 15 марта 1590 - на следующий день после битвы при Иври, то есть поздновато :) Тем ни менее, когда Филипп II узнал о взломе шифра, то был взбешен. Он накатал телегу Папе, обвиняя Виета в колдовстве. Однако у Папы тоже были криптоаналитики, и квалификация Виета им была прекрасно известна, так что обвинениям против Виета Папа ходу не дал.

Перед смертью Франсуа Виет написал мемуар о дешифровке, адресованный премьер-министру Генриха IV. Из него видно, что секрет успеха Виета - методичная и упорядоченная работа. Он советовал систематично искать часто повторяющиеся триады символов, а не пытаться угадать вероятные слова.

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

С уважением, Николай.
От Adekamer
К Николай Поникаров (07.08.2014 13:56:42)
Дата 07.08.2014 21:16:31

а когда появились шифроблокноты ? (-)
От Zevs
К Adekamer (07.08.2014 21:16:31)
Дата 07.08.2014 22:22:17

Re: а когда...

Ave!

Если одноразовые, то идея предложена в конце 19-ого века.

А так "Шифр Вернама" это 1917 или 1918, сейчас уже не помню точно.

В принципе, это абсолютно стойкий шифр. Только летит напрочь при компроментации блокнота.

Vale!
От Dargot
К Zevs (07.08.2014 22:22:17)
Дата 07.08.2014 22:35:51

Re: а когда...

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

>Если одноразовые, то идея предложена в конце 19-ого века.
>А так "Шифр Вернама" это 1917 или 1918, сейчас уже не помню точно.
>В принципе, это абсолютно стойкий шифр. Только летит напрочь при компроментации блокнота.
 Прошу прощения, "абсолютно стойкий" он только при одноразовом использовании каждой ключевой последовательности.
Если одна и та же последовательность используется для шифрования разных сообщений - все начинает сыпаться и без попадания блокнота в руки противника. В этом проблема данного метода - пользователей надо постоянно снабжать новыми ключевыми последовательностями.

С уважением, Dargot.
От Zevs
К Dargot (07.08.2014 22:35:51)
Дата 07.08.2014 22:51:09

Re: а когда...

Ave!

> Прошу прощения, "абсолютно стойкий" он только при одноразовом использовании каждой ключевой последовательности.

Естественно

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

Само собой.

> В этом проблема данного метода - пользователей надо постоянно снабжать новыми ключевыми последовательностями.

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

Vale!
От Dargot
К Dargot (07.08.2014 22:35:51)
Дата 07.08.2014 22:47:05

Да, еще...

Приветствую!
>>В принципе, это абсолютно стойкий шифр. Только летит напрочь при компроментации блокнота.
> Прошу прощения, "абсолютно стойкий" он только при одноразовом использовании каждой ключевой последовательности.
...и при полной случайности ключа. Если случайная величина "следующий символ ключа" имеет распределение, отличное от равномерного - появляются варианты.

С уважением, Dargot.
От Zevs
К Dargot (07.08.2014 22:47:05)
Дата 07.08.2014 22:53:47

Re: Да, еще...

Ave!

>> Прошу прощения, "абсолютно стойкий" он только при одноразовом использовании каждой ключевой последовательности.
>...и при полной случайности ключа. Если случайная величина "следующий символ ключа" имеет распределение, отличное от равномерного - появляются варианты.

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

Vale!
От Вулкан
К Николай Поникаров (07.08.2014 13:56:42)
Дата 07.08.2014 17:09:54

Добалю сюда из архива ссылку

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

http://vif2ne.ru/nvk/forum/0/archive/2478/2478421.htm

Ром, плеть и содомия - вот и все традиции Королевского флота
От Андрей Чистяков
К Николай Поникаров (07.08.2014 13:56:42)
Дата 07.08.2014 16:07:29

Ах, хорошо! Спасибо, Николай, прочитал с удовольствием. (-)
От alexio
К Николай Поникаров (07.08.2014 13:56:42)
Дата 07.08.2014 16:03:01

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

Спасибо за интересное дополнение. Заодно - может знаете, когда наконец шифровальщики осознали необходимость банальной смены шифра с достаточной регулярностью ? Против статистических методов это дело хорошо работает.
От Вулкан
К alexio (07.08.2014 16:03:01)
Дата 07.08.2014 17:02:19

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

Приветствую!
>Спасибо за интересное дополнение. Заодно - может знаете, когда наконец шифровальщики осознали необходимость банальной смены шифра с достаточной регулярностью ? Против статистических методов это дело хорошо работает.

Ключ испанцы меняли постоянно - не помогло. Виет нашел алгоритм смены ключа.

Ром, плеть и содомия - вот и все традиции Королевского флота
От alexio
К Вулкан (07.08.2014 17:02:19)
Дата 07.08.2014 17:27:03

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

>Ключ испанцы меняли постоянно - не помогло. Виет нашел алгоритм смены ключа.

Скорее применил один раз отработанный алгоритм ко всем остальным письмам. Но с другой стороны в этом вашем посте - http://vif2ne.ru/nvk/forum/0/archive/2478/2478421.htm сообщается об одном дешифрованом письме. То есть другие дешифровать не получилось, не смотря на понимание алгоритма. Возможно трудоёмкость дешифровки всё же была значительной.
От Booker
К alexio (07.08.2014 16:03:01)
Дата 07.08.2014 16:46:07

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

> ... когда наконец шифровальщики осознали необходимость банальной смены шифра с достаточной регулярностью ? Против статистических методов это дело хорошо работает.

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

С уважением.
От alexio
К Booker (07.08.2014 16:46:07)
Дата 07.08.2014 17:23:41

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!
От erno
К Николай Поникаров (07.08.2014 13:56:42)
Дата 07.08.2014 14:28:49

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

Спасибо, интересно!
Но шифр шифром, а как физически перехватывались депеши?
От Accounter
К erno (07.08.2014 14:28:49)
Дата 07.08.2014 20:49:59

В худ литературе все описано :)

А ткачиха с поварихой,
С сватьей бабой Бабарихой,
Обобрать его велят;
Допьяна гонца поят
И в суму его пустую
Суют грамоту другую ...
От Николай Поникаров
К erno (07.08.2014 14:28:49)
Дата 07.08.2014 15:03:52

Не знаю

День добрый.

>Но шифр шифром, а как физически перехватывались депеши?

Наверно, депеши перевозились обычной курьерской службой, и на территории Франции перехватить их было достаточно просто.

С уважением, Николай.