История криптографии

Видеолекцию "История криптографии" профессора Дэна Боне (Стэнфордский Университет) в рамках курса по криптографии можно найти здесь:
https://class.coursera.org/crypto/lecture/3

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



Прежде чем мы перейдем к техническим материалам, я хочу рассказать вам немного об истории криптографии. Есть замечательная книга по этой теме Дэвида Кана, называется “Взломщики кодов” (Codebreakers). Она охватывает историю криптографии на всем пути своего развития от Вавилона до настоящего времени. Здесь же я приведу несколько примеров исторических шифров, каждый из которых уже взломан.

[слайд] Симметричные шифры
Есть Алиса и Боб. На слайде два квадратика-алгоритма - Е и D. Шифрованием занимается Алиса (алгоритм Е), расшифрованием - Боб (алгоритм D). Оба обладают одни и тем же общим ключом. Алиса, используя ключ К, шифрует сообщение М, получая шифротекст С. Боб, используя ключ К, расшифровывает сообщение С, получая исходный текст М.
[слайд]


Раз уж разговор пойдет о шифрах, первое, что я собираюсь сделать, это представить наших друзей Алису и Боба. Те самые, кто пробудет с нами до окончания курса. Итак, Алиса и Боб, которые пытаются безопасно пообщаться, а также есть злоумышленник, который пытается подслушать их разговор. Таким образом, чтобы безопасно общаться, им нужен общий секретный ключ, который я буду обозначать K. Они оба знают секретный ключ. Но злоумышленник ничего не знает об этом ключе. И теперь они собираются использовать шифр, который представляет собой пару алгоритмов. Алгоритм шифрования обозначим Е. И алгоритм расшифрования - D. Эти алгоритмы работают следующим образом. Алгоритм шифрования Е получает сообщение M в качестве входных данных. И он же принимает в качестве входных данных, ключ K. Мы собираемся вклиниться (профессор рисует стрелку на квадратике с алгоритмом Е) вышеописанным ключом, и просто отметить тот факт, что этот вход действительно ввод ключа. В результате алгоритм шифрования выводит зашифрованный текст - зашифрованное сообщение М с помощью ключа К.

С : = Е(К, М)

Я всегда буду писать ключ в формулах в первую очередь.И когда я пишу “: =” я имею в виду, что выражение определяет переменную С, стоящую слева. Далее шифротекст каким-то образом передается через интернет Бобу. На самом деле шифротекст действительно может быть передан через Интернет. А может быть передан с использованием зашифрованной файловой системы, это не важно, как зашифрованный текст достигает Боба. Далее шифротекст отправляется в алгоритм расшифрования, и расшифровывается с тем же ключом К. И снова я собираюсь вклинится. Ключ тоже используется как входной параметр, и на выходе после расшифрования получаем оригинальный текст. И по этой причине мы говорим, что это симметричный шифр, где шифровальщик и расшифровальщик (Encrypter и Decrypter) фактически используют один и тот же ключ К. Как мы увидим позже, есть такие шифры, где шифрование использует один ключ, а расшифровка использует другой ключ. Но здесь мы просто сосредоточимся на симметричных шифрах, где обе стороны используют один и тот же ключ.

[слайд] Несколько исторических примеров (все они давно уже взломаны)
1. Шифр простой замены (подстановочный шифр).
C := E(K, “bcza”) = “wnac”
D(K,C) = “bcza”
[слайд]


А сейчас я приведу несколько исторических примеров шифров. Первый пример простейший - называется шифром простой замены (подстановочный шифр). Я уверен, что все вы в детстве игрались с подстановочными шифрами. По сути ключом в таком шифре является таблица подстановки, в которой для каждой буквы открытого текста существует единственная сопоставленная ей буква шифротекста. Например, букве А соответствует С, B -> W, C -> N и т.д. И наконец Z в A. Это один из примеров формирования ключа для шифра простой замены. Просто для практики, зашифруем определенное сообщение с помощью этого ключа, скажем, сообщение bcza, шифрование будет происходить простой заменой каждой буквы сообщения. Таким образом, вместо B станет W, вместо C станет N, Z в A, A в C. Таким образом, bcza станет wnac, и это и есть шифрованный текст. Таким же способом происходит расшифровка, используя тот же самый ключ, и мы вернемся к исходному сообщению.

[слайд] Шифр Цезаря (нет ключа)
[слайд]


Окей. Только в силу исторических причин, есть еще один пример, связанный с подстановочным шифром - он называется шифр Цезаря. Шифр Цезаря, на самом деле, в действительности не является шифром как таковым. А причина в том, что он не имеет ключа. Шифр Цезаря - в основном это подстановочный шифр, где подстановка фиксированная. В частности, это сдвиг на три. Таким образом, А станет D, В в Е, С в F и так далее и так далее. И наконец, Y станет B, Z станет C. Это фиксированная подстановка, которая распространяется на все текстовые сообщения. Опять же, это не шифр, потому что нет ключа, ключ - константа. Таким образом, если злоумышленник не знает, как наша схема шифрования работает, он может легко расшифровать сообщение. Ключ не является случайным, и, следовательно, процесс расшифрования проста, если вы понимаете, как схема действительно работает.

[слайд] Вопрос: Какое количество возможных ключей в подстановочном шифре на алфавите из 26 букв?
Ответ: 26! (примерно равно 2 в 88 степени)
[слайд]


Итак, сейчас, вернемся к шифру простой замены, где ключи действительно выбираются случайным образом, таблица подстановки выбирается случайно. И посмотрим, как взломать этот подстановочный шифр. Оказывается, очень легко. Первый вопрос, какое наибольшее количество возможных ключей? Сколько различных ключей можно создать, предполагая, что у нас есть 26 букв? Таким образом, я надеюсь, что все вы знаете ответ. Количество ключей составляет 26! факториал, потому что, ключ, подстановочный ключ, простая таблица, варианты перестановки всех 26 букв. Число всех возможных перестановок из 26 букв, составляет 26! факториал. Если вы посчитаете факториал, 26! - это около 288, а это значит, что ключ в подстановочном шифре занимает около 88 бит.

[слайд] Вопрос: Как взломать шифр простой замены?
Какая самая распространенная буква в тексте на английском языке?
Ответ: “Е”
[слайд]


Итак, каждый ключ представляет собой около 88 бит. Т.е., размер для ключей - прекрасный. На самом деле, мы увидим, что существует достаточно безопасных шифров с ключами, примерно такого размера. Однако, несмотря на то, что шифр простой замены имеет большой размер ключа (88 бит), он очень небезопасный. Итак, давайте посмотрим, как взломать его. И взлом его основан на частотном анализе символов. Первый вопрос, какая самая распространенная буква в тексте на английском языке? Я думаю, все вы знаете, что это буква E - наиболее распространенная буква. И если мы применим количественный анализ, то он поможет нам взломать подстановочный шифр. И имея только на руках шифротекст, мы уже можем восстановить исходный текст. И делаем мы это, прежде всего, используя частоты появления английских букв в тексте.

[слайд] Вопрос: Как взломать шифр простой замены?
(1) Используя частоты английских букв в тексте
“е”: 12.7% “t”: 9.1% “a”: 8.1% ..
(2) Используя частоты пар символов (диграммы)
“he” “an” “in” “th”
[слайд]


Итак, вот как это работает. Вы даете мне шифрованное сообщение, зашифрованное подстановочным шифром. Что я знаю: что исходным сообщением был текст на английском языке, и я знаю, что буква Е является наиболее часто встречаемой буквой в тексте на английском языке. И в самом деле, 12,7% - частота появления в стандартных английских текстах. И что я буду делать - я буду смотреть на шифротекст, который вы дали мне, и буду считать, сколько раз встречается каждая буква. Теперь самая распространенная буква в шифротексте - это зашифрованная буква Е с очень высокой вероятностью. Так что, я в состоянии восстановить одну запись в таблице подстановки. Сейчас я знаю, какому символу соответствует буква Е. Далее, следующая распространенная буква в тексте на английском языке - буква T, частота появления в тексте которой равна 9,1%. И я снова подсчитываю число вхождений каждой буквы в шифротексте. И второй букве наиболее часто встречаемой в шифротексте назначаю букву T. Так что, я восстановил вторую запись в таблице подстановки. Продолжаем по той же схеме. Следующая распространенная буква А - ее частота 8,1%. Поэтому я могу предположить, что третьим наиболее распространенным символом в шифротексте будет буква А. Так что, я восстановил третью запись в таблице подстановки. Ну, и что теперь мне делать? Остальные буквы на английском языке появляются примерно одинаковое количество раз, за исключением некоторых редких букв таких, как Q и X. Т.е. мы как бы застряли на этом этапе. Мы выяснили три записи в таблице подстановки, но что нам делать дальше? А следующая идея заключается в том, чтобы использовать частоты последовательностей букв. Иногда их называют биграммы (двухбуквенные последовательности), триграммы (трехбуквенные) и т.д. И что же я сделаю, я посчитаю, сколько раз каждая пара букв появляется в шифротексте, и я знаю, что в английском языке, наиболее распространенные пары букв: HE, AN, IN, TH. И я думаю, что наиболее распространенной паре букв в шифротексте, вероятно, будет соответствовать одна из этих четырех пар. И с помощью метода проб и ошибок можно отсортировать соответствия букв в таблице подстановки, затем также методом проб и ошибок рассмотрим триграммы. Таким образом, я могу на самом деле получить всю таблицу подстановки. Итог: выяснилось, что шифр простой замены уязвим для худшего типа атаки, т.е. достаточно зашифрованного текста, чтобы осуществить атаку на шифр. Имея на руках только шифротекст, можно восстановить ключ шифрования, и соответственно восстановить исходный текст. Поэтому нет никакого смысла шифровать любые данные с помощью подстановочного шифра, поскольку злоумышленник может легко все расшифровать; то же самое, что отправить исходный текст в открытом виде

[слайд] Пример анализа шифра простой замены
UKBYBIPOUZBCUFEEBORUKBYBHOBBRFESPVKBWFOFERVNBCVBZPRUBOFERVNBCVBPCYYFVUFO
FEIKNWFRFIKJNUPWRFIPOUNVNIPUBRNCUKBEFWWFDNCHXCYBOHOPYXPUBNCUBOYNRVNIWN
CPOJIOFHOPZRVFZIXUBORJRUBZRBCHNCBBONCHRJZSFWNVRJRUBZRPCYZPUKBZPUNVPWPCYVF
ZIXUPUNFCPWRVNBCVBRPYYNUNFCPWWJUKBYBIPOUZBCUIPOUNVNIPUBRNCHOPYXPUBNCUB
OYNRVNIWNCPOJIOFHOPZRNCRVNBCUNENVVFZIXUNCHPCYVFZIXUPUNFCPWZPUKBZPUNVR

THE DEPARTMENT OFFERS THE DEGREES OF BACHELOR OF SCIENCE MASTER OF SCIENCE AND DOCTOR OF PHILOSOPHY IT ALSO PARTICIPATES IN THE FOLLOWING UNDER GRADUATE INTER DISCIPLINARY PROGRAMS COMPUTER SYSTEMS ENGINEERING SYMBOLIC SYSTEMS AND MATHEMATICAL AND COMPUTATIONAL SCIENCES ADDITIONALLY THE DEPARTMENT PARTICIPATES IN GRADUATE INTER DISCIPLINARY PROGRAMS IN SCIENTIFIC COMPUTING AND COMPUTATIONAL MATHEMATICS
[слайд]


А сейчас мы быстро перемещаемся в эпоху Возрождения, и рассмотрим шифр разработанный парнем по имени Вижинер (Vigenere), жившим в шестнадцатом веке . Он разработал пару шифров. Я покажу вам вариант одного из них, называемого шифром Вижинера.

[слайд] Шифр Вижинера (16-й век, Рим)
k = C R Y P T O C R Y P T O C R Y P T
(+ mod 26)
m = W H A T A N I C E D A Y T O D A Y
c = Z Z Z J U C L U D T U N W G C Q S !
[слайд]


В этом шифре используется ключ - слово. В нашем примере - это слово “crypto”, длиной 6 символов. И чтобы зашифровать сообщение, мы сообщение пишем под ключом. В нашем случае под сообщением - “whatanicedaytoday” (what a nice day today) - мы повторяем ключ столько раз, сколько необходимо для покрытия всего сообщении - “cryptocryptocrypt”. А само шифрование заключается в том, чтобы сложить символы сообщения и ключа по модулю 26. Только для примера , смотрите, если вы добавите к Y букву А, то получим Z. А если T + A, то получим U. И так делаем для всех символов. И помните, что сложение идет по модулю 26. Т.е. после Z вы вернетесь к А. Так работает шифр Вижинера. А расшифрование такое же легкое. Для расшифровки вы бы написали зашифрованный текст над ключом. Повторяем ключ по всей длине шифротекста, а затем вычитаем символы ключа из символов шифротекста, чтобы получить оригинальный текст.

Сам взлом - для тех, кто сталкивается с этим шифром - на самом деле, довольно легкий. Позвольте мне показать вам, как это сделать. Первое, что мы должны сделать, мы должны предположить, что мы знаем длину ключа. Так что, просто предположим, что мы ее знаем. В нашем примере длина ключа составляет шесть символов. И что мы делаем, мы разбиваем весь шифротекст на группы из шести символов каждый, окей? Таким образом, мы получаем целую кучу групп, каждая из которых состоит из 6 букв (профессор на слайде делит шифротекст Z Z Z J U C L U D T U N W G C Q S на группы = Z Z Z J U C и L U D T U N и W G C Q S). А затем мы смотрим на первые буквы в каждой группе (Z и L и W). Окей? Да, в данном случае, мы смотрим на первую в каждой группе, т.е. на каждую шестую букву в шифротексте. Итак, что мы знаем о них, о шести буквах? Мы знаем, что, по сути, все они зашифрованы с помощью той же самой буквы в ключе. Все они зашифрованы с помощью буквы С. Другими словами. Z, L,W сдвинуты на три (С=3) буквы относительно исходного текста. Итак, если мы соберем все эти буквы, то самая часто встречаемая буква среди них, вероятно, будет зашифрованная буква Е, не так ли? E является наиболее распространенной буквой в английском языке, поэтому, если я смотрю на каждую шестую букву, то самая часто встречаемая из этого множества, вероятно, будет зашифрованный символ Е. Ха. Допустим мы выяснили, что самая часто встречаемая буква - H. Тогда мы знаем, что E + первый символ ключа = H. Это говорит о том, что первый символа ключа = H - Е. И это символ С. Итак, мы восстановили первый символ ключа. Теперь переходим ко второму символу. Мы смотрим на вторую букву в каждой группе из шести символов и снова повторяем то же самое упражнение. Подсчитываем частоту встречаемых букв, и мы знаем, что самая часто встречаемая буква - Е, поэтому, чтобы получить второй символ ключа, мы вычитаем символ Е из зашифрованной буквы. И так далее и так далее. Берем третью букву в каждой группе из шести символов, считаем, вычисляем символ ключа, берем четвертую и т.д.. И таким образом мы восстановим весь ключ. И он позволит нам расшифровать сообщение. Вспомним нашу оговорку, что мы предположили заранее, что длина ключа равно шести. Но если я не знаю, какая длина ключа раньше времени, то это не проблема. Что бы я сделал - я бы запустить описанную выше процедуру расшифровки, предполагая, что длина ключа равна единице. Затем я бы запустил расшифровку, предполагая, что длина ключа равна двум. Затем, предполагая, что длина равна трем. И т.д, и т.д., пока я, наконец, не получу сообщение. Я получаю расшифрованное сообщение, которое имеет смысл, а не бессмыслицу. И как только я это сделаю, я знаю, что восстановил правильную длину ключа, и также знаю, что также восстановил правильный ключ и, следовательно, правильное сообщение. Окей? Таким образом, очень, очень быстро можно восстановить, расшифровать шифр Вижинера. (На самом деле данный метод расшифровки работает, когда шифрованных сообщений у на на руках достаточно много, т.е. длина шифротекста приличная, чтобы применить частотный анализ. А вот когда сам шифротекст длиной в 15 символов, то в этом случае расшифровка не тривиальная задача, хотя принцип остается тот же - от перев.) И опять же, здесь применена атака на шифр. Самое интересное, сложение по модулю было хорошей идеей. И действительно, сложение по модулю 26 - хорошая идея, и мы увидим это позже, за исключением того, что здесь она реализована очень плохо. И мы исправим это, немного позже.

[слайд] Роторные машины (1870 - 1943)
Первый пример: роторная машина Хеберна - один ротор (Hebern rotor machine)
A B C .. X Y Z
ключ (механический диск - ротор)
K S T .. R N E
сдвиг диска
E K S T .. R N
сдвиг диска
N E K S T .. R
[слайд]


Окей, мы быстро перемещаемся вперед, из эпохи Возрождения в девятнадцатый век, в эпоху электричества. Логично, что люди хотят проектировать шифры, использующие электродвигатели. В частности, шифры называемые роторными машинами, поскольку они используют роторы. Одним из первых примеров является машина Хеберна с одним ротором. Вот она изображена на картинке (профессор указывает на нее на слайде). Я предполагаю, что ротор здесь. А секретный ключ размещенный на этом диске - вот здесь, ключ встроен внутри этого диска, и ступенчатый механизм вращает диск при каждом нажатии клавиши на пишущей машинке, окей? Таким образом, каждый раз, когда нажимаете клавишу, диск вращается на одно деление (зубец). А теперь, что ключ делает? Ключ на самом деле кодирует таблицу подстановки. И, следовательно, диск на самом деле является секретным ключом. И как я уже сказал, этот диск кодирует таблицу подстановки. В этом случае, когда нажмем C, то в результате будет буква T. И затем диск вращается на одно деление. Как только диск завершит вращение, будет доступна новая таблица подстановки, показана на рисунке (была таблица KST..RNE, после сдвига диска - EKST..RN). Вы видите, что E стала вначале таблицы, а остальные буквы сдвинулись вниз. Затем нажмите на следующую букву. И снова диск вращается. Вы заметили, таблица подстановки снова изменилась (стала NEKST..R). Так, например, если мы три раза подряд нажали С, то в первый раз мы получим Т, во второй раз результат будет S, а в третий раз - К.

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

[слайд] Роторные машины (продолжение)
Самая известная: Энигма (3-5 роторов)
[слайд]


Энигма является своего рода сложной среди роторных машин. Она использует три, четыре или пять роторов. Существуют различные версии Энигмы. На слайде приведен пример Энигмы с тремя роторами. Секретная схема Энигмы заключается в начальной настройке роторов. Окей. Таким образом, в случае трех роторов было бы 26 в кубе возможных различных ключей. Когда вы печатаете на ней, по существу, эти роторы вращаются с разной скоростью, скажем на этой схеме (профессор показывает на слайде) Энигма работает при помощи четырех дисков-роторов. Печатая на машинке, роторы вращаются и Энигма выводит соответствующие введенным символам зашифрованный текст. В этом случае количество ключей равно 26 в 4-й степени, что составляет 2 в 18-й степени, т.е. относительно небольшое пространство ключей. Сегодня вы можете, используя брутфорс (тупой перебор всех ключей) с помощью компьютера найти все 2 в 18-й степени различных ключей - очень, очень быстро. Вы знаете, я думаю мои наручные часы это сделают всего лишь за несколько секунд. Так вот, Энигма использует относительно небольшое пространство ключей. Но я уверен, вы все слышали, что британские криптографы в Блетчли-Парк могли расшифровывать зашифрованные тексты Энигмы. Они могли расшифровать немецкие шифры во время Второй мировой войны. И это обстоятельство сыграло важную роль во многих сражениях во время войны.

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

[слайд] Data Encryption Standard (1974)
DES: пространство ключей = 256, размер блока = 64 бита
Сегодня: AES (2001), Salsa20 (2008) (и многие другие)
[слайд]


Так вот, в 1974 году фирма IBM разработала шифр, который известен как DES (Data Encryption Standard - стандарт шифрования данных). Именно он стал федеральным стандартом для шифрования данных. Пространство ключей для DES составляет 2 в степени 56, что является относительно небольшим в наши дни, но достаточно большое в 1974 году. И еще одна интересная вещь о DES. В отличие от роторных машин, которые шифровали по одному символу, DES шифрует по 64 бит за один раз, а именно по восемь символов за раз. И при дальнейшем изучении курса мы увидим, какое значение играет размер блока. Т.к. DES использует такое небольшое пространство ключей, из-за этого сегодня он считается небезопасным и не должен использоваться в проектах. К сожалению, он используется в некоторых унаследованных системах, но он определенно выходит из обращения, и он определенно не должен использоваться в новых проектах. Сегодня появились новые шифры, такие, как расширенный стандарт шифрования (AES), который использует ключ в 128 байт. Опять же, мы будем говорить о AES более подробно далее. Есть многие, многие другие виды шифров. Я упомянул здесь Salsa20. Мы увидим, почему я это сделал. На этом беглый исторический обзор завершаем и теперь мы готовы перейти к более техническому материалу.


Пока не указано иное, содержимое этой страницы распространяется по лицензии Creative Commons Attribution-ShareAlike 3.0 License