КРИПТОГРАФИЯ
КРИПТОГРАФИЯ, или криптология, наука и искусство передачи сообщений в таком виде, чтобы их нельзя было прочитать без специального секретного ключа. В отечественном словоупотреблении термин «криптология» объединяет в себе «криптографию», т.е. шифрование сообщений, и «криптоанализ», т.е. несанкционированное расшифровывание сообщений (также широко употребляются термины «дешифровка / взламывание / ломка / взлом(ка) / вскрытие / раскрытие / раскалывание»). Слово «криптограф» происходит от древнегреческих слов kryptos 'секрет' и graphos 'писание'. Исходное сообщение называется в криптографии открытым текстом, или клером. Засекреченное (зашифрованное) сообщение называется шифротекстом, или шифрограммой, или криптограммой. Процедура шифрования обычно включает в себя использование определенного алгоритма и ключа. Алгоритм – это определенный способ засекречивания сообщения, например компьютерная программа или, скажем, список инструкций. Ключ же конкретизирует процедуру засекречивания.
СИСТЕМЫ ШИФРОВАНИЯ
Пусть требуется зашифровать следующее сообщение (открытый текст):
DEAR DAD
SEND MORE MONEY AS SOON AS POSSIBLE TOM
«Дорогой папа. Как можно скорее пришли еще денег. Том.»
Один из способов шифрования – простая замена, при которой каждая буква открытого текста заменяется на какую-то букву алфавита (возможно, на ту же самую). Для этого отправитель сообщения должен знать, на какую букву в шифротексте следует заменить каждую букву открытого текста. Часто это делается путем сведения нужных соответствий букв в виде двух алфавитов, например так, как показано ниже в таблице:
| Алфавит | |
| Открытый | ABCDEFGHIJKLMNOPQRSTUVWXYZ |
| Шифровальный | BLUESTOCKINGADFHJMPQRVWXYZ |
Шифрограмма получается путем замены каждой буквы открытого текста на записанную непосредственно под ней букву шифровального алфавита.
ESBM EBE
HGSBPS PSDE AFMS AFDSY BP PFFD BP HFPPKLGS QFA
Две алфавитные последовательности, используемые в процессе шифрования, называются, соответственно, открытым и шифровальным компонентом системы. Чтобы получатель шифрограммы мог восстановить открытый текст и прочитать сообщение, ему необходимо иметь копию вышеприведенной таблицы. Дешифровщик повторяет в обратном порядке все действия шифровальщика, раскрывая тем самым содержание сообщения.
В вышеприведенном примере использовался алгоритм побуквенной замены. Этот метод называется простой, или моноалфавитной заменой. Ключ к данному шифру состоит из таблицы, содержащей открытый и шифровальный алфавиты, в которой указывается, на какую букву в шифротексте следует заменить букву открытого текста. В такой криптографической системе предполагается, что алгоритм шифрования общеизвестен, тогда как ключ доступен только отправителю и получателю соответствующих сообщений.
В открытом алфавите буквы расположены в их обычной последовательности; такой алфавит называется прямой стандартной последовательностью. Шифровальный же алфавит в нашем примере состоит из 26 букв латинского алфавита, определенным образом переставленных с использованием ключевого слова BLUESTOCKING (букв. «синий чулок»). После ключевого слова (ключевой фразы) ключ далее записывается с опущением всех тех букв, что уже появились в этом слове (или в первом слове этой фразы), а затем вписываются остающиеся буквы алфавита в обычном порядке, опять же с опущением всех ранее появившихся букв. Так, если в качестве ключевой мы используем фразу UNITED STATES OF AMERICA, то шифровальный алфавит будет выглядеть следующим образом:
U N I T E D S A O F M R C B G H J K L P Q V W X Y Z
С помощью ключевого слова (фразы) при шифровании можно перемешать любую алфавитную последовательность. Использование ключевых слов облегчает восстановление открытого и шифровального компонента системы, поскольку при этом необходимо запомнить только соответствующее ключевое слово (фразу). Нет необходимости записывать (или разгадывать) какие бы то ни было таблицы: если помнить ключевое слово, то алфавитную последовательность всегда можно восстановить по памяти.
В вышеприведенной шифрограмме между словами сохранены пробелы, однако шифровку можно сделать более защищенной (или, как говорят криптографы, устойчивой, или стойкой ко взлому; шифр считается тем более стойким, чем дольше он не поддается вскрытию) путем удаления межсловных пробелов из окончательного шифротекста. Согласно установившейся практике, шифротекст принято делить на группы из пяти букв каждая. (Когда-то телеграфные компании при взимании платы каждую группу из пяти букв считали как одно слово открытого текста.) Если убрать пробелы между словами, то нашу шифрограмму можно было бы записать так:
ESBME BEMGS BPSPS DEAFM SAFDS YBPPF FDBPH FPPKL GSQFA
Замена – одно из основных криптографических преобразований. Другим важнейшим шифровальным алгоритмом является перестановка. В шифре перестановки все буквы открытого текста остаются без изменений, но переставляются согласно заранее оговоренному правилу. Здесь также может использоваться ключ, управляющий процедурой шифрования. Так, используя в качестве ключа слово PANAMA, мы могли бы зашифровать вышеупомянутый открытый текст следующим образом:
| Ключ | P A N A M A |
| Числовая последовательность | 6 1 5 2 4 3 |
| Блок перестановки | D E A R D A |
| D P L E A S | |
| E S E N D M | |
| O N E Y A S | |
| S O O N A S | |
| P O S S I B | |
| L E T O M | |
| Шифрограмма | EPSNO OEREN YNSOA SMSSB |
| DADAA IMALE EOSTD DEOSP L |
В этом примере ключевое слово использовано для получения шифровальной числовой последовательности путем нумерации букв ключевого слова (относительно друг друга) в порядке их следования слева направо в стандартном алфавите. Далее под числовой последовательностью в строках, равных по длине ключевому слову, записан открытый текст. В процессе шифрования текст выписывается уже по отдельным столбцам в порядке, определяемом данной числовой последовательностью. Этот метод перестановки называется перестановкой столбцов, но можно избрать и другие «маршруты» перестановки, например выписывать шифротекст следуя по диагонали (слева направо или справа налево, или же чередуя левое и правое направления) или по спирали и т.п. Кроме того, буквы шифротекста могут записываться в виде различных геометрических фигур или любыми другими способами. Один из них состоит в двойном шифровании путем повторной перестановки столбцов. При этом и в первом, и во втором блоках перестановки может быть использовано одно и то же ключевое слово, хотя лучше использовать разные ключевые слова. Такой шифр, называющийся двойной перестановкой, получил широкое распространение в 20 в.
Третьим основным алгоритмом шифрования является дробление. При этом каждой букве открытого текста сопоставляется более одного символа шифротекста, после чего символы перемешиваются (переставляются) в определенном порядке. Ниже приведена система, демонстрирующая процедуру дробления с использованием знаменитого шифра Bifid, авторство которого приписывается французскому криптографу Феликсу Мари Деластеллю.
| Ключевая фраза | UNITED STATES OF AMERICA |
| 1 2 3 4 5 | |
| 1 U N I T E | |
| Полибианский квадрат | 2 D S A O F |
| 3 M R C B G | |
| 4 H K L P Q | |
| 5 V W X Y Z | |
| Открытый текст | DEARDADPLEASESENDMOREMONEY |
| Соответствующая строка | 21232224412212112323132115 |
| Соответствующий столбец | 15321314353252521142514254 |
| Шифротекст | DASOHSNUAAIDEERITGRWWUKVKY |
Сначала составляется шифровальная таблица размером 5ґ5 (т.н. полибианский квадрат), куда построчно вписывается шифровальный алфавит с ключевой фразой UNITED STATES OF AMERICA; причем ради того, чтобы общее число букв алфавита не превышало 25, буква J опускается (поскольку эта буква, с одной стороны, малоупотребительна в английских текстах, а с другой – вполне может быть заменена буквой I, без какого-либо урона для смысла). В данной таблице букве A, например, соответствуют координаты 23, букве B – 34 и т.д.
Далее, в процессе шифрования под каждой буквой открытого текста в столбик записываются ее табличные координаты – номер строки и, ниже, номер столбца, а затем получившаяся цифровая последовательность переводится с помощью той же таблицы обратно в буквенную форму, но на этот раз она читается уже в строчку, т.е. 21 – буква D, 23 – буква A, 22 – буква S и т.д. При таком шифровании координата строки и координата столбца каждой буквы оказываются разъединенными, что характерно именно для раздробляющего шифра.
Замена, перестановка и дробление представляют собой основные криптографические алгоритмы. Эти три базовых преобразования, зачастую в сочетании друг с другом, используются в большинстве систем шифрования для создания очень сложных шифровальных алгоритмов, особенно когда шифрование производится компьютером.
Код отличается от шифра тем, что подходит к преобразованию открытого текста скорее с лингвистической точки зрения, нежели с чисто формальной, как в вышеописанных примерах. (В повседневном употреблении термин «код» обыкновенно путают с термином «шифр».) Кодирование, как правило, включает в себя применение пространной таблицы или кодового словаря, где перечислены числовые соответствия (эквиваленты) не только для отдельных букв, но и для целых слов и наиболее употребительных фраз и предложений. Например, такая кодовая группа, как AABRT, вполне может соответствовать открытому тексту «как можно быстрее». Раньше в дипломатических и военных криптографических системах часто использовались весьма пространные коды. Однако с появлением компьютеров наибольшее распространение получили шифры.
Другие криптографические системы.
Криптография включает в себя и системы тайнописи, отличные от вышеописанных. Для сокрытия исходного сообщения могут использоваться симпатические (невидимые) чернила. Секретные сообщения могут содержаться в нотной партитуре в виде особой записи отдельных нот, а также мелодических и гармонических секвенций. В фотографии для сокрытия сообщения применяется метод микроскопических точек. Сообщение может быть также спрятано в рисунке, чертеже или картине.
ИСТОРИЯ
Ранняя история.
Как только возникло письмо, появились и способы его шифрования. В древних цивилизациях мы находим два вида письма: иератическое, или священное письмо, использовавшееся священнослужителями для тайного общения друг с другом, и демотическое письмо, употреблявшееся всеми остальными. И у греков, и у римлян, и у других сопоставимых с ними по историческому значению народов были свои системы тайного письма. Изобретение первой системы скорописи, которая изначально замышлялась как секретное письмо, приписывается Туллиусу Тиро, вольноотпущенному рабу Цицерона (106–43 до н.э.).
Но только в период позднего Средневековья криптография превратилась в важный фактор дипломатических, торговых и военных сношений. По мере формирования европейских наций-государств возрастала нужда в средствах секретной коммуникации, особенно в сфере дипломатии. Со временем, когда отношения между новыми политическими образованиями установились, каждое государство учредило свою «тайную палату», в чьи функции входили перехват, досмотр и вскрытие шифров и кодов соседних государств. Зачастую это было сопряжено также с подделкой соответствующих документов и печатей. Так родилась наука криптоанализа, более известная под названием «взламывание шифров».
Первая книга по криптографии, называвшаяся Polygraphiae Libri Sex, была написана в 1499 Иоганном Трисемусом, аббатом бенедиктинского монастыря Св. Мартина в Шпанхейме (Германия). Хотя труд Трисемуса был весь пронизан кабалистическими и оккультными аллюзиями, в этой рукописи были описаны многие шифры – как широко бытовавшие в то время, так и изобретенные самим автором. Эта работа была чрезвычайно популярна, первое латинское издание появилось в 1518, а в 1541 книга была переиздана на французском языке. Вскоре последовал и ее перевод на немецкий язык. Книга вызвала гнев многих монарших дворов Европы, полагавших, что Трисемус выдал в ней слишком много секретов, и автор едва избежал сожжения на костре.
В 1550 итальянец Джироламо Кардано опубликовал книгу De subtilitate libri xxi. Кардано изобрел шифр, называемый решеткой, или трафаретом, в котором секретное послание оказывалось сокрыто внутри более длинного и совершенно невинно выглядевшего открытого текста. Секретное сообщение можно было обнаружить, наложив на открытый текст лист пергаментной бумаги с прорезями (трафарет). Cлова, появлявшиеся в прорезях, и составляли секретное послание.
Примерно в то же время о шифрах писал Джамбаттиста делла Порта. Труд Порта был скопирован и слегка переделан французским дипломатом Блезом де Виженером, труд которого Traité des chiffres приобрел широкую известность.
Для периода примерно с 16 по 19 вв. типичным был т.н. номенклатор – шифр, представлявший собой сочетание шифра замены и небольшого кода. Номенклатор обычно содержал кодовые эквиваленты букв алфавита и наиболее употребительных слогов, слов и словосочетаний, а также ряд специальных символов. Чаще всего в нем встречались специально созданные для этой цели символы, но нередко также использовалась астрологическая и оккультная символика.
Номенклатор был разработан как система шифрования, наилучшим образом приспособленная к наиболее употребительным в то время методам криптоанализа, которые, как правило, включали подсчет частоты появления в тексте каждого шифрового символа и поиск в тексте слов и выражений, содержащих характерные для данного языка сочетания букв. Метод частотного анализа букв основан на том, что в любом языке одни буквы встречаются чаще, чем другие. В английском языке, например, чаще других встречается буква Е. Другие наиболее часто встречающиеся буквы – T, A, O, N, R и S. (Целиком эту группу букв легко запомнить в виде слова «SENORITA».) А буквы J, K, X и Z встречаются в английском редко. Поскольку в ходе операции замены частота буквы не меняется, ключ к разгадке истинного значения того или иного шифросимвола заключается иногда в подсчете частоты его появления в шифротексте. Равным образом операция простой замены не вносит изменений и в сочетания букв (буквенные модели). Например, слово ATTACK, будучи зашифрованным, может принять вид XJJXBU. Несмотря на то, что значения букв при этом изменились, буквенная модель слова (а именно две одинаковых буквы, обрамленные слева и справа одной и той же буквой, после чего следуют две другие различные буквы) осталась неизменной.
Чтобы усложнить частотный анализ букв, каждую букву клера стали заменять двумя и более шифросимволами. Такая операция обычно разрушала и буквенные модели, от наличия которых в значительной мере зависел успех криптоанализа. Рассмотрим в качестве иллюстрации, т.н. «малый шифр», использовавшийся в наполеоновской армии для связи между войсками и генеральным штабом.
| A-15 AR-25 AL-39 | M-114 MA-107 |
| B-37 BU-3 BO-35 BI-29 | N-115 NE-94 NI-116 |
| C-6 CA-32 CE-20 | O-90 OT-153 |
| D-23 DE-52 | P-137 PO-152 |
| E-53 ES-82 ET-50 EN-68 | Q-173 QUE-136 |
| F-55 FA-69 FE-58 FO-71 | R-169 RA-146 RE-126 RI-148 |
| G-81 GA-51 | S-167 SA-171 SE-177 SI-134 |
| H-85 HI-77 | SO-168 SU-174 |
| I-119 IS-122 | T-176 TI-145 TO-157 |
| J-87 JAI-123 | U-138 |
| K-? | V-164 VE-132 VI-161 VO-175 |
| L-96 LU-103 LE-117 | W, X, Y-? |
| LA-106 | Z-166 |
Приведенная выше таблица замены была дешифрована французским криптографом Этьеном Базери. В имевшихся в его распоряжении шифровках некоторые буквы клера (K, W, X и Y) не встречались, поэтому он не смог определить их шифровых эквивалентов.
«Малый шифр» содержит числовые эквиваленты для всех букв алфавита, а также для часто встречающихся биграмм (двухбуквенных сочетаний) и некоторых триграмм (трехбуквенных сочетаний). С помощью этого шифра, который специалисты называют силлабарием (слоговым алфавитом), слово NAPOLEON «Наполеон», например, может быть зашифровано по-разному:
| N | A | P | O | L | E | O | N | |
| 115 | 15 | 137 | 90 | 96 | 53 | 90 | 115 | |
| или | ||||||||
| N | A | PO | LE | O | N | |||
| 115 | 15 | 152 | 117 | 90 | 115 | |||
Использование подобных приемов сильно усложняет задачу криптоаналитика. Хотя наполеоновский шифр относительно невелик, в эпоху номенклаторов нередки были также криптосистемы, содержавшие сотни соответствий.
Телеграф и многоалфавитная криптография.
С появлением в 1830-х годов телеграфа номенклатор как практический метод шифрования вышел из употребления. В 1843 Конгресс США одобрил проект строительства первой в мире телеграфной линии, связавшей Вашингтон (округ Колумбия) с Балтимором (штат Мэриленд). В телеграфной связи буквы, цифры и знаки препинания обозначались посредством длинных и коротких электромагнитных сигналов (точек и тире), которые можно было пересылать с одного конца провода на другой. Чтобы увеличить скорость передачи Сэмюэл Ф.Б.Морзе составил свою «азбуку» так, что более часто встречающиеся знаки передавались в ней с помощью более коротких сочетаний точек и тире. Так, часто встречающиеся буквы E и T передавались с помощью одиночной точки и одиночного тире соответственно, тогда как буква Z – с помощью четырех точек.
Телеграф стремительно распространился по США и Европе. Поскольку телеграфные линии легко доступны для несанкционированного подключения, для обеспечения секретности связи стали использовать шифрование. Употреблявшиеся прежде номенклаторы с их специальными символами нельзя было вместить в схему, состоявшую из одних точек и тире. Кроме того, числовые шифры, наподобие наполеоновского «малого шифра», не подходили для этой цели, поскольку в азбуке Морзе цифры передавались с помощью весьма длинных сочетаний точек и тире и передавать числа, записываемые с помощью большого количества цифр, было невыгодно. В значительной мере именно это обстоятельство склонило криптографическую практику в пользу того типа шифров, который ранее предлагали Порта и Виженер.
Тип шифра, изобретенный Порта и Виженером, в современной терминологии называется многоалфавитной заменой. Как следует из самого названия, в этой системе используется целый ряд шифровальных алфавитов. Одна из разновидностей такого шифра, называемая ныне шифром Виженера, включает в себя алфавитный квадрат (квадратную таблицу), состоящий из 26 пошаговых оборотов (ротаций) прямого стандартного алфавита:
| ABCDEFGHIJKLMNOPQRSTUVWXYZ | |
| ----------------------------- | |
| A B C D E F G H I J K L M N O P Q R S T U V W X Y Z |
abcdefghijklmnopqrstuvwxyz bcdefghijklmnopqrstuvwxyzA cdefghijklmnopqrstuvwxyzAB defghijklmnopqrstuvwxyzABC efghijklmnopqrstuvwxyzABCD fghijklmnopqrstuvwxyzABCDE ghijklmnopqrstuvwxyzABCDEF hijklmnopqrstuvwxyzABCDEFG ijklmnopqrstuvwxyzABCDEFGH jklmnopqrstuvwxyzABCDEFGHI klmnopqrstuvwxyzABCDEFGHIJ lmnopqrstuvwxyzABCDEFGHIJK mnopqrstuvwxyzABCDEFGHIJKL nopqrstuvwxyzABCDEFGHIJKLM opqrstuvwxyzABCDEFGHIJKLMN pqrstuvwxyzABCDEFGHIJKLMNO qrstuvwxyzABCDEFGHIJKLMNOP rstuvwxyzABCDEFGHIJKLMNOPQ stuvwxyzABCDEFGHIJKLMNOPQR tuvwxyzABCDEFGHIJKLMNOPQRS uvwxyzABCDEFGHIJKLMNOPQRST vwxyzABCDEFGHIJKLMNOPQRSTU wxyzABCDEFGHIJKLMNOPQRSTUV xyzABCDEFGHIJKLMNOPQRSTUVW yzABCDEFGHIJKLMNOPQRSTUVWX zABCDEFGHIJKLMNOPQRSTUVWXY |
При шифровании с помощью алфавитного квадрата сначала выбирается ключевое слово (или ключевая фраза), которое записывается, циклично повторяясь, над открытым текстом. Затем сообщение может быть зашифровано буква за буквой, для чего в таблице надо найти столбец, обозначенный той же буквой, что и соответствующая буква ключа, и строку, обозначенную той же буквой, что и буква открытого текста, лежащая под данной буквой ключа. Буква, лежащая в таблице на пересечении означенных столбца и строки, и будет искомым шифросимволом. Например, если в качестве ключевого использовать слово MAPLE, то шифрование будет выглядеть следующим образом:
| Ключ | MAPLEMAPLEMAPLEMAPLEMAP |
| Открытый текст | SHIPMENTTOARRIVETONIGHT |
| Шифротекст | EHXAQQNIESMRGTZQTDYMSHI |
| Шифрограмма | EHXAQ QNIES MRGTZ QTDYM SHI |
Шифр Виженера обладает также некоторыми из преимуществ более раннего номенклаторного типа шифра. Каждая буква открытого текста может передаваться в шифротексте таким числом разных шифросимволов, сколько разных букв содержится в ключе. Кроме того, многоалфавитная замена позволяет скрыть повторяющиеся буквы и другие внутрисловные сочетания, характерные для данного открытого текста. При этом в окончательном шифротексте используются только 26 обычных букв алфавита, а какие-либо специальные символы или цифры не нужны.
Из-за своей внешне кажущейся сложности шифр Виженера прослыл «невзламываемым» (не поддающимся дешифровке) и долгие годы пользовался репутацией очень стойкого шифра. Помимо вышеописанной шифровальной таблицы, он может быть исполнен в виде двух картонных или деревянных скользящих пластинок с нанесенными на них определенными алфавитными последовательностями. Эффект сдвигающихся строк шифровальной таблицы достигался за счет правильного наложения этих двух пластинок друг на друга. (Это устройство известно как «скользящие пластинки Св.Сира» – по названию французской военной академии, введшей их в употребление.) В то время как французы предпочитали скользящие пластинки, англичане заменили их на два концентрических шифрующих диска, на каждом из которых по всей длине окружности была нанесена определенная алфавитная последовательность. Один из дисков вращался относительно другого, что давало эффект сдвига алфавита. Сам принцип шифрующих дисков был изобретен гораздо раньше – в 15 в. – итальянским математиком Леоном Баттистой Альберти, который, по-видимому, первым разработал многоалфавитный шифр.
Метод многоалфавитной замены с использованием алфавитного квадрата со временем зарекомендовал себя как весьма универсальная и популярная система. В целях повышения устойчивости к взлому стали прибегать к самым различным ее модификациям. Так, алфавиты в квадрате могут быть перемешанными или выстроенными в обратном порядке; в качестве «скользящего» ключа к шифру может быть использовано некоторое стихотворение или книга, тем самым устраняется необходимость непрерывно повторять один и тот же короткий ключ; в качестве составной части секретного ключа может использоваться сам по себе открытый текст или шифротекст и т.д. Впоследствии идею использования множественных алфавитов открывали для себя многие любители в области шифрования, которые либо не подозревали о том, что подобные шифры уже существуют, либо пытались усовершенствовать базовую методику.
19 столетие.
В 19 в. было изобретено множество систем секретного письма, некоторые из которых получили широкое распространение. Две важнейшие криптографические системы изобрел британский ученый Чарльз Уитстон. Сначала мы опишем шифр Playfair, названный так Уитстоном в честь своего друга барона Плейфэра.
Шифр Playfair оперирует биграммами, или двухбуквенными сочетаниями. Процедура шифрования биграммы обычно заключается в том, что составляющие ее две буквы находят в алфавитном квадрате, после чего в нем мысленно строится прямоугольник так, чтобы эти две буквы лежали в его противоположных вершинах; тогда другие две вершины данного прямоугольника дают буквы шифровки. Если буквы биграммы лежат в одной и той же строке или столбце, берутся две буквы, расположенные, соответственно, справа или внизу (в циклической последовательности) от букв клера. Если биграмма состоит из двух одинаковых букв, то сначала вторую букву в ней заменяют на X, Z или какую-либо другую редкую букву, после чего зашифровывают полученную таким образом новую биграмму.
|
Шифровальный квадрат |
P L A Y F |
| I R B C D | |
| E G H K M (буква J опускается) | |
| N O Q S T | |
| U V W X Z | |
| Открытый текст | ATTACK ENEMY POSITIONS AT ONCE SIGNED FOX |
| Открытый текст, разбитый на биграммы | AT TA CK EN EM YP OS IT IO NS AT ON CE SI GN ED FO XZ |
| Шифротекст | FQ QF KS NU GE FL QT DN RN OT |
| FQ QO IK NC EO MI LT ZU |
Второе изобретение Уитстона заключалось в новаторском использовании шифрующего диска. Криптографическое устройство Уитстона состояло из двух шифрующих дисков, на внешнем из которых было 27 делений (26 букв латинского алфавита плюс «конечный» символ), а на внутреннем – 26 делений с другой алфавитной последовательностью. Каждый диск был снабжен ручкой, указывавшей на то или иное деление. Перед началом шифрования ручка внешнего диска устанавливалась таким образом, что она указывала на «конечный» символ, а прямо под ней устанавливалась ручка внутреннего диска, после чего внутренний диск устанавливался в начальное положение, известное отправителю и получателю шифровки.
Слово зашифровывалось путем поворота внешней ручки так, чтобы она указывала на нужную букву открытого текста. Обе ручки были сцеплены друг с другом, поэтому передвижение внешней ручки заставляло двигаться и внутреннюю ручку, но с другой скоростью, поскольку внутреннее колесо было меньше внешнего. В то время как ручка внешнего колеса указывала на букву клера, ручка внутреннего колеса указывала на соответствующую ей букву шифротекста. Затем внешнюю ручку передвигали к следующей букве открытого текста, и весь процесс повторялся. По окончании слова внешнюю ручку возвращали в положение «конечного» символа. Порождаемый при этом шифр – ввиду разного диаметра колес – не был простой заменой. Так, в тот момент, когда внешняя ручка завершала полный оборот, внутренняя ручка уже заходила на одно деление вперед на второй круг. Криптограф Уитстона был впервые описан в 1867, и вплоть до Первой мировой войны считалось, что он дает практически не взламываемые шифрограммы, пока американский криптоаналитик Уильям Ф.Фридман не продемонстрировал его уязвимые места. Криптографический принцип, лежащий в основе устройства Уитстона, открывался на протяжении истории несколько раз. В 1817 – за несколько десятилетий до Уитстона – аналогичное в основе своей устройство было сконструировано американцем Дишьюсом Уодзуэртом.
Томас Джефферсон, третий по счету президент США, задолго предвосхитил изобретение еще одного широко известного шифровального устройства – цилиндра Базери. Впервые описанное французским криптографом Этьеном Базери в 1891, это устройство состояло из нескольких вращаемых дисков (у самого Базери их было 20), закрепленных на общей оси. На каждый диск была нанесена своя (причем перемешанная) алфавитная последовательность. При шифровании текст разбивался на группы, длина которых соответствовала числу используемых дисков. Каждая группа открытого текста устанавливалась на цилиндре в ряд (в одну строку), а в качестве шифротекста выбирался любой из остальных 25 рядов. Дешифровщик совершал ту же процедуру, но в обратном порядке: на цилиндре поочередно устанавливалась в ряд каждая группа шифротекста, после чего просматривались остальные 25 рядов с целью определить, какой из них содержит открытый текст. Этот тип шифра, в свое время являвшийся одной из лучших криптографических систем, называется мультиплексной системой.
Мультиплексная система широко применялась военными и дипломатическими службами США до, во время и после Второй мировой войны. Диски часто заменяли на узкие металлические пластинки, на каждую из которых была нанесена перемешанная алфавитная последовательность, причем дважды циклически повторенная на той же самой пластинке.
Машинная криптография.
Криптография широко применялась в период Первой мировой войны. Немцы экспериментировали с самыми разнообразными шифрами и кодами. В ходе войны были испробованы практически все известные криптографические системы в различных вариациях. Наиболее способными криптоаналитиками проявили себя в то время французы, неоднократно взламывавшие коды и шифры противника.
Наиболее известным шифром того периода была германская система ADFGX, построенная на сочетании базовых операций замены, дробления и перестановки. Этот шифр был введен в употребление в 1918 Фрицем Небелем, офицером связи, служившим в штабе германской армии. Свое название эта система получила из-за того, что ее шифрограммы содержали только буквы A, D, F, G и X. Впоследствии была добавлена буква V, и шифр стал называться шифром ADFGVX.
Сообщения, зашифрованные этим шифром, первыми перехватили французы в марте 1918. Работа по взламыванию шифра была поручена криптоаналитику капитану Жоржу Пенвену. 1 июня 1918 Пенвен расшифровал знаменитое сообщение, в котором были обозначены цели предстоящего крупного наступления германских войск.
Криптография сыграла важную роль в Первой мировой войне. Одной из причин вступления в войну США стал перехват и вскрытие англичанами знаменитой телеграммы Циммермана. Артур Циммерман, министр иностранных дел Германии, разработал план по привлечению Мексики на сторону Германии в случае войны с США. Циммерман послал телеграмму с изложением подробностей своего плана германскому послу в Вашингтоне с тем, чтобы тот переправил ее германскому послу в Мексике. Телеграмма была перехвачена и вскрыта британским секретным отделом «Комната № 40». Англичане показали телеграмму американцам.
Изобретатели по обе стороны Атлантики разрабатывали новые криптографические системы с использованием электромеханических устройств. Сторонники машинной криптографии надеялись выиграть в скорости и точности, которых так часто недоставало ручным системам, и одновременно достигнуть желаемого уровня сложности. Уже в 1917 американский изобретатель Эдвард Хеберн сконструировал шифровальное устройство, в котором для перемешивания (скремблирования) алфавитов использовались роторные шифрующие колеса (барабаны), снабженные множеством проводов.
Роторное колесо представляло собой небольшой диск, сделанный из электроизоляционного материала. На каждой стороне этого диска располагались по окружности на равном расстоянии друг от друга 26 электрических контактов, каждый из которых соответствовал одной из 26 букв латинского алфавита. Каждый контакт на одной стороне колеса был соединен (более или менее случайным образом) проводом с одним из контактов на другой стороне колеса. С помощью такого ротора можно было воспроизвести механический вариант шифра простой замены. Когда электрический импульс поступал на контакт, соответствовавший букве А на одной стороне колеса и соединявшийся с контактом буквы М на другой его стороне, это можно было рассматривать как замену буквы А на букву М. Для ввода букв обычно использовалась клавиатура обыкновенной пишущей машинки, а результат шифрования ротором либо воспроизводился печатающим устройством, либо высвечивался на световом табло, содержавшем 26 буквенных символов.
Если после шифрования машиной первой буквы ротор проворачивался на один шаг от своей исходной позиции, то итоговый результат простой замены полностью менялся, потому что на один шаг сдвигались и все провода в роторе. (В первой машине Хеберна ротор при шифровании каждой буквы сдвигался на один шаг.) Поскольку шагов (позиций) имелось всего 26, то по мере проворачивания колеса при шифровании первых 26 букв текста порождалось 26 различных шифровальных алфавитов.
После того как первые 26 букв были зашифрованы, ротор снова приходил в исходное положение и последовательность алфавитов повторялась. С криптографической точки зрения, такое повторение является недостатком, так как оно наступает после зашифровывания слишком небольшого количества букв исходного текста. Чтобы усложнить процесс шифрования, стали соединять в ряд несколько роторов. Если, например, использовать 3 ротора, то электрический импульс проходит при шифровании по очереди через каждый из них. Поскольку на каждый ротор приходится по 26 возможных позиций, трехроторное устройство было способно породить 26ґ26ґ26 = 17 576 различных шифровальных алфавитов. После того как была зашифрована каждая буква клера, можно было выбрать новый алфавит путем передвижения одного или более имеющихся роторов так, чтобы изменить переплетение проводов, через которые проходит ток. Хеберн построил машины с четырьмя и пятью роторами. Роторы в них передвигались подобно тому, как это происходит в одометре. Один из роторов вступал в работу при шифровании каждой буквы. Этот ротор считался «быстрым» ротором. Другой ротор вступал в работу только один раз в течение каждого оборота быстрого ротора и назывался «средним» ротором. «Медленный» же ротор вступал в работу один раз за период обращения среднего ротора. Таким образом, машина Хеберна могла порождать огромное множество шифровальных алфавитов, причем для шифрования каждой новой буквы клера использовался полностью новый алфавит. Более того, роторы в машине Хеберна могли, при желании, выниматься и переставляться в сколь угодно произвольном порядке. Еще одной переменной величиной при шифровании того или иного сообщения этой машиной являлось исходное положение роторов.
В то же самое время в Европе разрабатывалось очень похожее роторное устройство. Новую машину окрестили «Энигмой» (т.е. «загадка» в переводе с латыни). К 1923 в Европе уже производились и выставлялись коммерческие модели первоначальной версии Энигмы. От машины Хеберна Энигма отличалась, с криптографической точки зрения, хотя бы тем, что в ней ток проходил через роторы, пока не достигал последнего из них, после чего поворачивал назад, проходя через те же роторы, но по другому пути. В результате в криптограмме Энигмы ни одна буква клера не могла соответствовать самой себе в шифровке, и наоборот. Более того, шифровальные алфавиты, порождаемые этой машиной, все были взаимообратными. Это означает, что если, скажем, буква E при определенной исходной установке машины зашифровывалась как W, то и буква W при этой установке зашифровывалась как E.
В Швеции инженер Арвид Дамм основал компанию «Актиболгет криптограф» с целью внедрения ряда шифровальных машин, спроектированных им после Первой мировой войны. Дамм наладил серийный выпуск этих машин, но продажи шли туго, отчасти из-за громоздкости и ненадежности его продукции. В 1925 Борис Цезарь Хагелин, один из служащих компании Дамма, сконструировал шифровальное устройство, ставшее известным под названием В-211 и составившее конкуренцию Энигме. Со временем Хагелин вступил во владение компанией, переименовал ее в «Крипто AG» и обосновался в Швейцарии.
В преддверии войны.
К началу 1930-х годов большинство стран-участниц в предстоящей войне уже использовали шифровальные машины. В частности, немцы начали широко использовать машину Энигма. После нескольких неудачных попыток немецкие криптографы сконструировали модифицированную версию машины, которая была признана достаточно надежной. Основное изменение заключалось в добавлении коммутационной панели, что значительно повысило устойчивость шифросистемы ко взлому.
В 1920-е годы за изучение новой немецкой машины взялись польские власти. С помощью документации, предоставленной им французами, польские криптоаналитики примерно в 1932 успешно взломали шифры Энигмы, употреблявшиеся в германской армии. Этому событию суждено было сыграть исключительно важную роль в ходе Второй мировой войны.
Японцы, с большим интересом следившие за развитием машинной криптографии, начали применять машины собственной конструкции. В 1935 американские криптоаналитики столкнулись с японским машинным шифром, названным ими RED. В 1936 Фрэнк Роулетт и Соломон Калбэк, криптоаналитики армии США, взломали шифры RED и раскрыли принцип действия японского устройства. Тот же результат был независимо достигнут британскими, немецкими и голландскими криптографами.
В 1939 машина RED была заменена японцами на другую – Angooki Taipu B, или PURPLE, как ее называли американцы. И снова американским криптоаналитикам удалось взломать шифры этой машины и воссоздать ее устройство. PURPLE была первой из целой серии японских шифровальных машин, в конструкции которых вместо роторов применялись телефонные коммутаторы.
Начиная примерно с 1920 немцы начали перестройку своих служб радиоперехвата и криптографической службы. Они медленно, но неуклонно внедрялись в шифры других европейских стран. К середине 1930-х годов для них уже превратилась в открытую книгу вся дипломатическая документация Италии, и с различной долей успеха они могли читать шифры ряда других стран. Ими также была вскрыта криптографическая система, применявшаяся в польских воздушных силах. Немцы постепенно взламывали и прочитывали все больше и больше французских и британских военных шифров, а также дипломатических кодов.
В июле 1939 польские криптографы встретились со своими британскими и французскими коллегами и передали им результаты расшифровки немецкой Энигмы, а также экземпляры этой машины. В сентябре 1939 Польша была захвачена германскими войсками, однако факт успешного взлома поляками кода Энигмы был сохранен в тайне.
Вторая мировая война.
Основываясь на польских результатах работы с Энигмой, англичане на протяжении всей войны расшифровывали сообщения Энигмы. Несмотря на то, что немцы изменили способ передачи и дополнительно усложнили саму машину, англичанам неизменно удавалось проникать в немецкие шифры. Для ускорения процесса расшифровки англичане создали ряд вспомогательных технических приспособлений. Помимо шифров Энигмы, немцы использовали и некоторые другие шифровальные машины дальнего действия, обеспечивавшие высокий уровень связи. Эти машины, имевшие широкое обозначение Geheimschreiber (тайнописные машины), были способны порождать чрезвычайно сложные шифры. Для анализа этих шифров англичане сконструировали целый ряд «протокомпьютеров», с помощью которых они часто успешно взламывали немецкие машинные шифры. Полученные при этом сведения были широко известны под обозначением ULTRA.
Тем временем американцы успешно раскалывали японские шифры. Полученные ими данные были известны широкой публике под кодовым обозначением MAGIC. Вслед за машинами RED и PURPLE криптоаналитики раскрыли устройство японских шифровальных машин JADE и CORAL.
Послевоенный период.
Во время войны искусство вскрытия шифров в течение короткого периода проделало путь от расшифровывания вручную до использования вычислительной техники и работы в команде. Сбор и анализ криптографических данных требовал создания технологии, которая бы обеспечила высокую скорость и точность вычислений. Начатые во время войны попытки поставить технику на службу криптографии продолжались и в мирное время, что в итоге ускорило разработку многоцелевого (универсального) компьютера в США и Великобритании.
Изобретение компьютера добавило новое измерение криптографии. Та легкость, с какой могла быть перехвачена компьютерная информация, будучи пересланной по телефонной линии связи, и уязвимость компьютерных файлов данных перед лицом электронного воровства возвестили о начале новой эры, когда в криптографию стали широко вовлекаться частные лица и компании.
Кроме правительств и военных, крупнейшими пользователями достижений криптографии являются банки. Появление банкоматов привело к широкому распространению техники зашифровывания сообщений, которые идут от банкомата к центральному процессору банка и обратно и дают разрешение на выдачу денежных сумм наличными. Так, например, использование персональных идентификационных номеров (ПИН-кодов) требует применения криптографических методов для подтверждения подлинности (аутентификации) личности владельца компьютерной системе банка.
Желание предоставить возможность пользоваться электронной почтой как можно большему числу пользователей привело к созданию нового типа криптографических систем, а именно шифровальных систем с открытым ключом. С помощью обычной почтовой связи любой человек может переслать конфиденциальное сообщение кому-то другому, чей адрес ему известен. Конверт, содержащий послание, служит одновременно для обеспечения тайны переписки, поскольку содержание сообщения может быть разглашено только в том случае, если конверт будет вскрыт. Подобным же образом два пользователя могут общаться друг с другом и по электронной связи, при этом шифрование сообщения электронным способом служит той же цели, что и конверт в обычной почтовой связи. Однако засекреченная связь этого типа не может быть успешной, если оба пользователя предварительно не договорятся между собой о секретном ключе (равно как, разумеется, и о стандартном алгоритме шифрования). Системы с открытым ключом позволяют решить проблему через использование шифров, в которых как алгоритм, так и ключ для шифрования могут быть вполне общедоступными, тогда как определить ключ для расшифровывания нет практически никакой возможности. В обычных же шифрах, если известны ключ для шифрования и алгоритм, как правило, не составляет труда вычислить и ключ для расшифровывания. Шифрование с открытым ключом до сих пор является новой областью криптологии, и предстоит решить еще целый ряд проблем прежде, чем этот тип криптосистем будет применяться в полную силу.
Принципы Керкхоффса.
Любители всегда играли немаловажную роль в криптографии. И действительно, мир полон изобретателей «невзламываемых» (не поддающихся дешифровке) шифров. Зачастую бывает нелегко определить, насколько та или иная криптографическая система подходит для применения в определенных условиях. Август Керкхоффс (Kerckhoffs), известный голландский лингвист 19 в., сформулировал несколько общих принципов, которым должен удовлетворять любой хороший шифр. Большинство любительских систем не удовлетворяют как минимум одному из принципов Керкхоффса. Эти принципы заключаются в следующем.
Во-первых, шифр должен обеспечивать достаточную стойкость ко взлому. Несмотря на то, что одиночное шифрованное сообщение может быть в принципе невзламываемым, часто бывает необходимо переслать сотни сообщений, зашифрованных в одной и той же системе. И хотя одиночное сообщение может быть трудно или невозможно расшифровать, большое число одинаково зашифрованных сообщений взломать куда проще. «Достаточная» стойкость ко взлому означает также, что разработчику шифра необходимо учитывать фактор времени: на взломку шифра должно требоваться время, достаточное для того, чтобы сообщения успевали потерять ценность для криптоаналитика. Обеспечение абсолютной стойкости шифра редко необходимо, и даже если оно возможно, обычно требует неоправданных затрат.
Во-вторых, шифр должен быть прост в использовании. Опыт показывает, что пользователи избегают пользоваться сложными и громоздкими шифросистемами либо пользуются ими с ошибками.
В-третьих, стойкость шифра ко взлому должна полностью зависеть от обеспечения секретности ключа, а не алгоритма. Опять-таки из опыта известно, что алгоритм, которым пользуется много людей, не может долго оставаться в секрете. Ключ же, напротив, гораздо проще как изменить, так и сохранить в тайне.
«Невзламывамый» шифр
– это целый класс систем, широко известных под названием «одноразовые вкладыши». Соответствующий принцип был, по-видимому, впервые отчетливо сформулирован американским ученым Гилбертом Вернамом примерно в 1917. Вернам занимался разработкой криптографических методов для использования в телетайпных машинах. В этой связи он предложил комбинировать открытый текст, представленный в виде отверстий в бумажной перфоленте, с данными, нанесенными на другую перфоленту и являющимися ключом к шифру. Ключ должен был состоять из отверстий, перфорированных в ленте случайным образом. Комбинация этих двух лент и составляла шифротекст.
Идею Вернама можно проиллюстрировать с привлечением вышеописанного шифра Виженера. Ключ для этого шифра, по мысли Вернама, должен был представлять собой случайную последовательность букв.
| Ключ | EVTIQWXQVVOPMCXREPYZ |
| Открытый текст | ALLSWELLTHATENDSWELL |
| Шифротекст | EGEAMAIBOCOIQPAJATJK |
| Шифрограмма | EGEAM AIBOC OIQPA JATJK |
Без знания ключа такое сообщение не поддается анализу. Даже если бы можно было перепробовать все ключи, в качестве результата мы получили бы все возможные сообщения данной длины плюс колоссальное количество бессмысленных дешифровок, выглядящих как беспорядочное нагромождение букв. Но и среди осмысленных дешифровок не было бы никакой возможности выбрать искомую.
Когда случайная последовательность (ключ) сочетается с неслучайной (открытым текстом), результат этого (шифротекст) оказывается совершенно случайным и, следовательно, лишенным тех статистических особенностей, которые могли бы быть использованы для анализа шифра.
Почему же этот невзламываемый шифр не употребляется повсеместно? Дело в том, что порождение «случайного» ключа – процесс весьма непростой. С помощью математических алгоритмов можно получать последовательности, обладающие многими свойствами, которые присущи «случайности»; однако эти последовательности не являются истинно случайными. Для порождения шифровальных ключей, представляющих собой случайную последовательность, можно использовать также естественные процессы – такие, как радиоактивный распад и электронный шум (статический), причем результаты обычно получаются лучшие, чем в случае с математическими формулами, но необходимость задания производящим перфоленты машинам отборочных уровней – это еще один источник неслучайного отбора.
Легкость порождения ключа – решающий фактор в том, что касается практической применимости шифров типа «одноразовых вкладышей». Ведь ключ должен быть точно такой же длины, что и шифруемое сообщение (это видно из вышеприведенного примера). Более того, никакой ключ нельзя использовать повторно, потому что данный факт часто может быть обнаружен с помощью статистических тестов и тогда те куски сообщения (или сообщений), в которых был использован тот же самый ключ, будут расшифрованы. То обстоятельство, что ключ может быть использован только один раз, и определяет «одноразовость» таких шифров.
Прежде чем пересылать невзламываемую шифрограмму, необходимо передать получателю копию ключа. Поскольку ключ имеет ту же длину, что и открытый текст, одна проблема (надежно засекреченная передача сообщения) оказывается просто замененной на другую такую же (надежно засекреченное распространение ключа). Однако у такого шифра есть и преимущество, которое состоит в том, что ключ может быть распространен заранее, а также по более медленным и надежным каналам связи, после чего шифрограмму можно совершенно безбоязненно пересылать по обычным каналам. В результате появления микропроцессоров и дискет для хранения и распространения компьютерных данных практическая значимость «одноразовых» шифров возросла, потому что порождение и сверка относительно большого числа ключей может теперь производиться автоматически. Еще одной проблемой, связанной с использованием шифров «одноразового вкладыша», является то, что под рукой всегда необходимо иметь достаточное количество ключей, которые могут понадобиться в дальнейшем для шифрования больших объемов открытого текста. Реальный же объем текста зачастую трудно оценить заранее, в особенности это касается дипломатической и военной сферы, где ситуация способна меняться быстро и непредсказуемо. Это может приводить к нехватке ключей, что может заставить шифровальщика либо использовать ключ(и) повторно, либо полностью прервать шифрованную связь.
Жельников В. Криптография: от папируса до компьютера. М., 1997
Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии. М., 2000
Ответь на вопросы викторины «Знаменитые речи»