Парадокс дней рождения и его роль в развитии криптографии и повышении криптоустойчивости систем

 

Ключевые слова: криптография, криптоанализ, криптолог, криптоаналитик, шифрование, шифр, теория вероятности, дисперсия, медиана, криптосистемы, интеллектуальные системы

 

1.              Введение

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

2.              Методология

Проведен анализ источников по практике шифрования на примерах стран Германия, Франция, Италия, Россия, Египет, Греция, Индия, США и прочие в различный временной период. Сделан обзор и приведены результаты исследований 2005–2019 годов российский и зарубежных авторов в части криптоустойчивости различных систем.

3.              Исследование
   1.       Развитие криптографии — ретроспектива
      1.            Появление криптографии. Древний мир

История криптографии берет свое начало в древнем Египте. Именно там впервые воспользовались одним из существенных элементов шифрования — умышленным преобразованием письменных символов. Это применялось при написании надгробных надписей. Со временем изменения в начертании символов становились все более и более изощренными, благодаря чему появлялись новые иероглифы. Однако эти изменения не преследовали цели скрыть какую-либо информацию. Египтяне делали это для того, чтобы произвести впечатление на читателя, либо чтобы показать свое мастерство каллиграфии. Однако с течением времени видоизменения иероглифов стали применятся и для сокрытия смысла написанного. Однако интерес к зашифрованным надгробным надписям очень скоро угас, и от них решили отказаться [1].

Первые настоящие методы шифрования появились в древней Индии. Их существование упоминается в древнеиндийском трактате об искусстве управления государством, написанном между 321 и 300 годом до н. э., в котором главам шпионских организаций рекомендуется использовать тайнопись для передачи сообщений подчиненным. Также трактат косвенно указывает на существование криптоанализа в древней Индии: «При невозможности беседовать с людьми пусть посол осведомится о происходящем у врага из… условных знаков, надписей, рисунков в храмах и местах паломничества». К сожалению, в тексте трактата нет описания конкретных методик криптоанализа [2].

В Европе криптография зарождалась в древнем Риме и древней же Греции. Яркими примерами европейских методов шифрования служат т. н. шифр Цезаря и линейка Энея.

Шифр Цезаря — представитель семейства моноалфавитных шифров. Назван он в честь Гая Юлия Цезаря, римского диктатора, который использовал этот шифр для ведения переписки. В шифре Цезаря каждая буква алфавита циклически сдвигается на определенное число позиций (сам Цезарь использовал сдвиг на 3 буквы). Число сдвига можно считать ключом шифра.

Линейка Энея — первый криптографический инструмент, использующий шифр замены. Создан Энеем Тактиком в IV веке до н. э. Эней Тактик был древнегреческим полководцем, написавшим, по свидетельствам современников, множество трактатов по военному делу. До наших дней, к сожалению, дошел лишь один из них — «О перенесении осад». В этом трактате, помимо всего прочего, также изложена идея т. н. книжного шифра и принцип работы диска и линейки Энея [3].

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

3.1.2.              Средневековье

В средние века развитием криптографии активно занимались арабы — их цивилизация, переживавшая на тот момент свой золотой век, достигла в деле сокрытия информации больших успехов. Заинтересовались криптографией арабы еще в далеком 855 году. Именно тогда арабский ученый по имени Абу Бакр тамед бен-Али бен-Вахшия ан-Набати написал «Книгу о большом стремлении человека разгадать загадки древней письменности», в которую включил описание нескольких классических шифроалфавитов. Именно арабы первыми открыли и описали методы криптоанализа и создали таблицы распространенности букв и слогов в языке. Все познания арабов в различных областях наук (в т. ч. и криптографии) были изложены Шехабом Калкашанди в его 14-титомной энциклопедии, написанной в 1412 году. Там же, в разделе «Относительно сокрытия в буквах тайных сообщений», был впервые применен криптоанализ. История умалчивает о том, применялись ли арабами полученные знания [2].

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

Примерно с XIV века началось непрерывное, хоть и не очень быстрое развитие криптографии в Европе. Доподлинно неизвестно, было ли это развитие следствием соприкосновения с арабской культурой в результате крестовых походов, или же европейская криптография развивалась самостоятельно. Период бурного развития криптографии связан с развитием дипломатических отношений между европейскими странами. Дипломатам необходимо было передавать добытые ими сведения на родину и получать директивы от правительства. Все это должно было быть скрыто от «заклятых друзей», на территории которых находился дипломат. Именно эта необходимость вкупе с развитием математики спровоцировала увеличение темпов развития криптографии.

Так, к примеру, герцоги Сфорца, правители Милана, широко пользовались услугами криптоаналитиков, и именно их секретарь по имени Чикко Симонетта в 1474 году написал первый в мире трактат, посвященный исключительно криптоанализу. В нем Чикко установил 13 правил вскрытия шифров простой замены, в которых сохранены разделители слов.

Первым знаменитым западным криптоаналитиком стал венецианец Джованни Соро, в 1506 году назначенный секретарем по шифрам Венецианской республики. Он прославился тем, что успешно вскрывал практически любые шифры того времени. Слава Соро была столь велика, что начиная с 1510 года папская курия присылала ему для вскрытия шифры, с которыми не могли справиться в Риме [2].

Кроме Италии, криптография также активно развивалась и во Франции. Примером служит Великий Шифр или шифр Россиньоли, которым были зашифрованы архивы Людовика XIV. Этот шифр продержался почти 200 лет [4].

3.1.3.              Новое Время

С приходом Нового времени в европейских государствах стали появляться т. н. черные кабинеты — ведомства, занимавшиеся дешифровкой захваченных сообщений. Самым эффективным был венский кабинет — именно ему приписывается чтение переписки Наполеона, Талейрана и других известных политических деятелей.

Однако эра черных кабинетов продлилась недолго — в свете событий XIX века цензура переписки стала невозможна, т. к. шла вразрез с обновленной политикой европейских держав. В 1848 году венский и французский кабинеты закрылись.

Обратим теперь взгляд на Новый Свет: в Америке не было ни платных криптоаналитиков, ни черных кабинетов, однако криптоанализ сыграл важную роль в ее истории. Именно благодаря ему война за независимость завершилась победой колоний. Например, благодаря криптоанализу был рассекречен Бенджамин Чарч — предатель, передававший сведенья об армии повстанцев английским войскам [2].

Однако во время американской революции криптоанализ, в отличие от систем шифрования, переживал застой. Это было связанно с тем, что чаще всего шифрограммы не удавалось перехватить. Лишь к концу войны захваченных сообщений накопилось достаточное для криптоанализа количество. Большинство из них было дешифровано Джеймсом Ловеллом, которого можно по праву назвать отцом американского криптоанализа [2].

Впоследствии именно криптоанализ помог республиканцам победить на выборах 1876 года.

Рассмотрим теперь роль криптографии в первой мировой войне: австрийские и германские криптологи практически мгновенно вскрывали шифры Российской Империи, что приводило к ряду оглушительных поражений российской армии, как-то разгром Самсонова и прорыв Маккензена из окружения осенью 1914 года. В целом успехи стран тройственного союза в криптоанализе сыграли важную роль в поражении Российской Империи [5].

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

Пока на полях сражений сходились в битвах армии Антанты и Тройственного союза, голландцем Хьюго Кохом разрабатывалась роторная шифровальная машина Энигма. Впоследствии она использовалась Германией до 1940 года, после чего была заменена на машину Лоренца.

3.1.4.              Новейшее время

После окончания войны свежесозданный СССР учел ошибки Российской Империи и более ответственно отнесся к применению криптографии для защиты стратегически важных данных. В период с 1920-х по 1930-е СССР помимо постоянного совершенствования своих шифров упражнялся в т. н. практическом криптоанализе, иначе говоря — в воровстве шифров.

Тем временем запад также развивал методики шифрования и взлома шифров. Так, в конце 1930-х годов в Америке была создана шифровальная машина M-209, на основе которой впоследствии были разработаны шифровальные машины Советского Союза.

А потом грянула вторая мировая война. Именно тогда Россия, учтя свои прошлые неудачи, взяла реванш за проигранную в эфире первую мировую войну. Немецкие криптоаналитики оказались неспособны взломать советские шифры стратегического значения, и вынуждены были довольствоваться лишь тактическими успехами.

В то время, когда на восточном фронте шли ожесточенные бои, английские криптоаналитики бились над взломом шифра «Fish». Взломать его удалось только после того, как специально для этого была создана программируемая вычислительная машина [6]. Взлом этого шифра дал англичанам стратегическое преимущество, которым они, однако не захотели делиться с Советским Союзом.

С окончанием войны развитие криптографии даже не думало останавливаться. Напротив, Холодная война увеличила темпы развития соответствующих областей науки. Однако это уже совсем другая история.

3.2.         Парадокс дней рождений и криптоустойчивость

Рассмотрим, как связаны в научных публикациях, в том числе за последние 3–5 лет, парадокс дней рождений и новые идеи развития криптографии и криптоустойчивости систем.

Парадокс дней рождения — утверждение, что если дана группа из 23 или более человек, то вероятность того, что хотя бы у двух из них дни рождения (число и месяц) совпадут, превышает 50 %. Для группы из 60 или более человек вероятность совпадения дней рождения хотя бы у двух её членов составляет более 99 %, хотя 100 % она достигает, только когда в группе не менее 366 человек (с учётом високосных лет — 367).

Рис. 1. Парадокс дней рождений (С. Мария Терехова)

 

Такое утверждение может показаться противоречащим здравому смыслу, так как вероятность одному родиться в определённый день года довольно мала, а вероятность того, что двое родились в конкретный день — ещё меньше, но является верным в соответствии с теорией вероятностей. Таким образом, оно не является парадоксом в строгом научном смысле — логического противоречия в нём нет, а парадокс заключается лишь в различиях между интуитивным восприятием ситуации человеком и результатами математического расчёта.

В работе 2005 года исследователей Augot, D., Finiasz, M., & Sendrier, N. отмечается, что последнее время некоторые коллизии были выставлены для различных криптографических хэш-функций, включая некоторые из наиболее широко используемых сегодня. Однако многие другие хэш-функции, использующие подобные конструкции, все еще можно считать безопасными. Тем не менее, это привлекло внимание к необходимости разработки новых хэш-функций. Исследователями разработано и представлено семейство защищенных хэш-функций, безопасность которых напрямую связана с проблемой декодирования синдрома из теории кодов с исправлением ошибок [7].

Российскими учеными парадоксы в теории вероятностей акцент исследованы в контексте практического применения этой теории в повседневной жизни, в том числе, и в части тривиального вывода, о том, что «логические парадоксы играют важную роль в развитии современной логики» [p.132] [11].

Важным в рамках нашего исследования является вывод о том, что «результатом возникновения каждого нового метода криптоанализа является пересмотр оценок безопасности шифров, что, в свою очередь, влечет необходимость создания более стойких шифров. [p.3] [12]

Реализовать подбор заменяемого при электронной цифровой подписи сообщения можно методом, основанном на упомянутом «парадоксе дней рождения». Этот метод криптоанализа породил требования устойчивости к коллизиям для хеш-функций [12].

В исследовании Мао В. (2009) отмечается, что парадокс дней рождений оказал значительное влияние на разработку криптосистем и криптографических протоколов [p.108] [13] и обусловил возникновение атаки на основе «парадокса дней рождений» (birthday attack) или атаки по методу квадратного корня (square-roof attack) — чтобы с вероятностью более 50 % обнаружить в комнате, заполненной случайными людьми, двух человек, родившихся в один день, достаточно, чтобы в этой комнате находилось 23 человека.

В работе Левина В. Ю. [14] отмечается, что «атака на хеш-функции на основе парадокса дней рождений является одной из самых распространенных атак» [p. 206]

Парадокс дней рождений упоминается и при слайдовой атаке [15], где авторами отмечается, что современные компьютеры позволяют развиваться скоростным алгоритмам шифрования, признавая все «существующие криптоаналитические технологии бесполезными» [p.144] и применении данного парадокса в части Методов Монте-Карло [16].

Универсальная атака на подделку (An universal forgery attack) означает, что для любого заданного сообщения M противник без ключа может подделать соответствующий код аутентификации сообщения (MAC) тега τ, а пара (M,τ) может быть проверена с вероятностью 1. Для идеи MAC универсальная атака подделки должна быть неосуществимой для реализации, сложность которой, как полагают, составляет min(2n, 2k) запросов в классической настройке, где n-длина тега и k-длина ключа MAC, соответственно [8].

Таким образом, криптографические хеш-функции [9] — незаменимый и повсеместно распространенный инструмент, используемый для выполнения целого ряда задач, включая аутентификацию, проверку целостности данных, защиту файлов и даже обнаружение зловредного ПО. Существует масса алгоритмов хеширования, отличающихся криптостойкостью, сложностью, разрядностью и другими свойствами. Считается, что идея хеширования принадлежит сотруднику IBM, появилась около 50 лет назад и с тех пор не претерпела принципиальных изменений. Зато в наши дни хеширование обрело массу новых свойств и используется в очень многих областях информационных технологий. криптографическая хеш-функция, чаще называемая просто хешем, — это математический алгоритм, преобразовывающий произвольный массив данных в состоящую из букв и цифр строку фиксированной длины. Причем при условии использования того же типа хеша длина эта будет оставаться неизменной, вне зависимости от объема вводных данных. Криптостойкой хеш-функция может быть только в том случае, если выполняются главные требования: стойкость к восстановлению хешируемых данных и стойкость к коллизиям, то есть образованию из двух разных массивов данных двух одинаковых значений хеша.

В новейшем исследовании Celewicz P. [10] парадокс дней рождений и развитии криптографии рассматривается с точки зрения темы функционирования современных мегаполисов, таких как Smart Dubai, как следствие цивилизационного прогресса, происходящего в настоящее время на основе новейших технических решений с помощью электроники и программного обеспечения. Автор представил инновационные идеи использования цифровой криптографии-блокчейна, которая повышает эффективность взаимодействий, происходящих внутри структур современных городов или их фрагментов, между их пользователями, в финансовых операциях, общественном участии и управлении и широко понимаемых сервисах, использующих новые цифровые медиа. Большинство представленных примеров относятся к разработке идей, которые находятся на стадии тестирования и которые возможно использовать в качестве наиболее оптимальных.

4.                                                                                     Заключение

Таким образом, сравнивая интуитивную оценку вероятности нарушения криптоустойчивости и ее математическую оценку можно сделать вывод о том, что однозначно криптоустойчивых систем не существует. Математическая вероятность взлома системы всегда выше, чем инуитивная оценка этой вероятности. Данный вывод справедлив для всех видов и типов криптосистем. Для авторов особую значимость представляют дальнейшие исследования криптоустойчивости функционирования современных мегаполисов.

5.               Благодарности

Тереховой Марии Юрьевне, ученице 8 класса МАОУ СОШ 56 г. Калининграда и ученице Детской художественной школы г. Калининграда за помощь в подготовке иллюстративного материала статьи,

Ногтиковой Наталье Юрьевне и Авраменко Марине Владимировне (педагогам по математике) ГБОУ 507 г. Москвы

Ереминой Людмиле Александровне, педагогу по математике МАОУ ШИЛИ, Карповой Татьяне Олеговне, педагогу по ИВТ МАОУ ШИЛИ, Калининград

 

Литература:

 

1.     Коростовцев М. А. Введение в египетскую филологию. — М., 1963
2.     David Kahn. The Codebreakers — The Story of Secret Writing. — New York City: Charles Scribner's Sons, 1967. — 473 с.
3.     Тактик, Э. (2003). О перенесении осад. Военное искусство античности. М.: Эксмо, 38–106.
4.     Singh S. The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography— New York City: Doubleday, 1999. — 416 p.
5.     Барбара Такман. Первый блицкриг. Август 1914 = The Guns of August. — М.: АСТ, 1999. — 640 с.
6.     Sale, T. (2017). The Lorenz cipher and how Bletchley Park broke it. Codes and Ciphers.
7.     Augot, D., Finiasz, M., & Sendrier, N. (2005, September). A family of fast syndrome based cryptographic hash functions. In International Conference on Cryptology in Malaysia (pp. 64–83). Springer, Berlin, Heidelberg.
8.     Liu, F., & Liu, F. (2017). Universal Forgery with Birthday Paradox: Application to Blockcipher-based Message Authentication Codes and Authenticated Encryptions. IACR Cryptology ePrint Archive, 2017, 653.
9.     https://www.kaspersky.ru/blog/the-wonders-of-hashing/3633/
10. Celewicz P. et al. Blockchain–system operacyjny nowoczesnego miasta //Środowisko Mieszkaniowe. — 2018. — Т. 2018. — №. 23/2018. — С. 102–109.
11. Комарова К. М. Парадоксы в теории вероятностей //В мире научных открытий. — 2014. — С. 132–134.
12. Авдошин С. М., Савельева А. А. Криптоанализ и криптография: история противостояния //Бизнес-информатика. — 2009. — №. 2.
13. Мао В. Современная криптография: теория и практика. — Издательский дом Вильямс, 2005.
14. Лёвин В. Ю. О повышении криптостойкости однонаправленных хеш-функций //Интеллектуальные системы. — 2010. — Т. 14. — №. 1–4. — С. 203–212.
15. Бабенко Л. К., Ищукова Е. А. Анализ симметричных криптосистем //Известия Южного федерального университета. Технические науки. — 2012. — Т. 137. — №. 12 (137).
16. Пригарин С. М. Модели случайных процессов и полей в методах Монте-Карло //Saarbruecken: Palmarium Academic Publishing. — 2014.