Криптография: Базовые знания о науке шифрования. История возникновения криптографии

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

Первый период (приблизительно с 3-го тысячелетия до н.э.) характеризуется господством моноалфавитных шифров (основной принцип - замена алфавита исходного текста другим алфавитом через замену букв другими буквами или символами).

Второй период (хронологические рамки - с IX века на Ближнем Востоке (Ал-Кинди) и с XV века в Европе (Леон Баттиста Альберти) - до начала XX века) ознаменовался введением в обиход полиалфавитных шифров.

Третий период (с начала и до середины XX века) характеризуется внедрением электромеханических устройств в работу шифровальщиков. При этом продолжалось использование полиалфавитных шифров.

Четвёртый период - с середины до 70-х годов XX века - период перехода к математической криптографии. В работе Клода Шеннона появляются строгие математические определения количества информации, передачи данных, энтропии, функций шифрования. Обязательным этапом создания шифра считается изучение его уязвимости к различным известным атакам - линейному и дифференциальному криптоанализу. Однако до 1975 года криптография оставалась "классической", или же, более корректно, криптографией с секретным ключом.

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

Историю криптографии условно можно также разделить на 4 этапа .

• 1. Наивная криптография.
• 2. Формальная криптография
• 3. Научная криптография
• 4. Компьютерная криптография

Для наивной криптографии (до нач. XVI века) характерно использование любых (обычно примитивных) способов запутывания противника относительно содержания шифруемых текстов. На начальном этапе для защиты информации использовались методы кодирования и стеганографии, которые родственны, но не тождественны криптографии. Большинство из используемых шифров сводились к перестановке или моноалфавитной подстановке. Одним из первых зафиксированных примеров является шифр Цезаря, состоящий в замене каждой буквы исходного текста на другую, отстоящую от нее в алфавите на определенное число позиций. Другой шифр, полибианский квадрат, авторство которого приписывается греческому писателю Полибию, является общей моноалфавитной подстановкой, которая проводится с помощью случайно заполненной алфавитом квадратной таблицей (для греческого алфавита размер составляет 5x5). Каждая буква исходного текста заменяется на букву, стоящую в квадрате снизу от нее.

Этап формальной криптографии (кон. XV века - нач. XX века) связан с появлением формализованных и относительно стойких к ручному криптоанализу шифров. В европейских странах это произошло в эпоху Возрождения, когда развитие науки и торговли вызвало спрос на надежные способы защиты информации. Важная роль на этом этапе принадлежит Леону Батисте Альберти, итальянскому архитектору, который одним из первых предложил многоалфавитную подстановку. Данный шифр, получивший имя дипломата XVI века Блеза Вижинера , состоял в последовательном "сложении" букв исходного текста с ключом (процедуру можно облегчить с помощью специальной таблицы). Его работа "Трактат о шифре" считается первой научной работой по криптологии. Одной из первых печатных работ, в которой обобщены и сформулированы известные на тот момент алгоритмы шифрования является труд "Полиграфия" немецкого аббата Иоганна Трисемуса. Ему принадлежат два небольших, но важных открытия: способ заполнения полибианского квадрата (первые позиции заполняются с помощью легко запоминаемого ключевого слова, остальные - оставшимися буквами алфавита) и шифрование пар букв (биграмм).

Простым, но стойким способом многоалфавитной замены (подстановки биграмм) является шифр Плейфера, который был открыт в начале XIX века Чарльзом Уитстоном. Уитстону принадлежит и важное усовершенствование - шифрование "«двойным квадратом". Шифры Плейфера и Уитстона использовались вплоть до первой мировой войны, так как с трудом поддавались ручному криптоанализу. В XIX веке голландец Керкхофф сформулировал главное требование к криптографическим системам, которое остается актуальным и поныне: секретность шифров должна быть основана на секретности ключа, но не алгоритма.

Наконец, последним словом в донаучной криптографии, которое обеспечили еще более высокую криптостойкосить, а также позволило автоматизировать (в смысле механизировать) процесс шифрования стали роторные криптосистемы. Одной из первых подобных систем стала изобретенная в 1790 году Томасом Джефферсоном, будущим президентом США механическая машина. Многоалфавитная подстановка с помощью роторной машины реализуется вариацией взаимного положения вращающихся роторов, каждый из которых осуществляет "прошитую" в нем подстановку. Практическое распространение роторные машины получили только в начале XX века.

Одной из первых практически используемых машин, стала немецкая Enigma, разработанная в 1917 году Эдвардом Хеберном и усовершенствованная Артуром Кирхом. Роторные машины активно использовались во время второй мировой войны. Помимо немецкой машины Enigma использовались также устройства Sigaba (США), Турех (Великобритания), Red, Orange и Purple2 (Япония). Роторные системы - вершина формальной криптографии так как относительно просто реализовывали очень стойкие шифры. Успешные криптоатаки на роторные системы стали возможны только с появлением ЭВМ в начале 40-х годов.

Главная отличительная черта научной криптографии (30-е - 60-е годы XX века) - появление криптосистем со строгим математическим обоснованием криптостойкости. К началу 30-х годов окончательно сформировались разделы математики, являющиеся научной основой криптологии: теория вероятностей и математическая статистика, общая алгебра, теория чисел, начали активно развиваться теория алгоритмов, теория информации, кибернетика. Своеобразным водоразделом стала работа Клода Шеннона "Теория связи в секретных системах", где сформулированы теоретические принципы криптографической защиты информации. Шеннон ввел понятия "рассеивание" и "перемешивание", обосновал возможность создания сколь угодно стойких криптосистем.

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

Примерно в 1900 году до н. э. древние египтяне начали видоизменять и искажать иероглифы, чтобы закодировать определенные сообщения. порядков более высокую криптостойкость, чем "ручные" и "механические" шифры. Первым классом криптосистем, практическое применение которых стало возможно с появлением мощных и компактных вычислительных средств, стали блочные шифры. В 70-е годы был разработан американский стандарт шифрования DES (принят в 1978 году). Один из его авторов, Хорст Фейстел (сотрудник IBM), описал модель блочных шифров, на основе которой были построены другие, более стойкие симметричные криптосистемы, в том числе отечественный стандарт шифрования ГОСТ 28147-89.

С появлением DES обогатился и криптоанализ, для атак на американский алгоритм был создано несколько новых видов криптоанализа (линейный, дифференциальный и т.д.), практическая реализация которых опять же была возможна только с появлением мощных вычислительных систем.

В середине 70-х годов произошел настоящий прорыв в современной криптографии - появление асимметричных криптосистем, которые не требовали передачи секретного ключа между сторонами. Здесь отправной точкой принято считать работу, опубликованную Уитфилдом Диффи и Мартином Хеллманом в 1976 году под названием "Новые направления в современной криптографии". В ней впервые сформулированы принципы обмена шифрованной информацией без обмена секретным ключом. Независимо к идее асимметричных криптосистем подошел Ральф Меркли.

Несколькими годами позже Рон Ривест, Ади Шамир и Леонард Адлеман открыли систему RSA, первую практическую асимметричную криптосистему, стойкость которой была основана на проблеме факторизации больших простых чисел. Асимметричная криптография открыла сразу несколько новых прикладных направлений, в частности системы электронной цифровой подписи (ЭЦП) и электронных денег.

В 80-90-е годы появились совершенно новые направления криптографии: вероятностное шифрование, квантовая криптография и другие. Осознание их практической ценности еще впереди. Актуальной остается и задача совершенствования симметричных криптосистем.

В 80-90-х годах были разработаны нефейстеловские шифры (SAFER, RC6 и др.), а в 2000 году после открытого международного конкурса был принят новый национальный стандарт шифрования США - AES.

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

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

Некоторые из сохранившихся глиняных табличек позволяют предположить что древним был известен прием когда исходное письмо, написанное на глиняной табличке и закрепленное обжигом, покрывалось вторым слоем глины на котором писалось сообщение не содержащие секретных сведений. Подобный прием использовал строитель Александрийского маяка Сострат, который по указанию правителя Египта Птолемея Филадельфа установил в стене табличку с его именем, но сделал ее из штукатурки покрашенной под мрамор. Спустя многие годы слой штукатурки рассыпался и открыл подлинное имя автора одно из чудес света выбитое на камне. Другой подобный прием использовался при отправки писем: рабу брили наголо волосы, писали на голове послание а когда волосы отрастали, отправляли к адресату с маловажным сообщением.

Таким образом, уже в древнем мире люди использовали два основных приема используемых до сих пор:

скрытия самого факта передачи (наличия) тайного сообщения – стеганография ;

шифрования сообщения – криптография .

Первые шифры

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

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

Криптография в государствах Азии

Сведения о способах шифрования применявшихся в государствах Азии в нашей литературе встречаются не часто.

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

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

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

Термины

Для начала давай определимся с терминологией:

• Криптография - это наука о том, как обеспечить секретность сообщения.
• Криптоанализ - это наука о том, как вскрыть зашифрованное сообщение, не зная ключа.
• Дешифровка - это процeсс получения открытого текста средствами криптоанализа.
• Расшифрование - это процесс получения открытого текста с использованием ключа и алгоритма расшифрования, предусмотренного для данного шифра.

В мире криптографии путаться в этих словах - ужасный моветон.

Зачем мне знания о криптографии?

Предположим, криптография очень нужна, но пусть ей займутся дядьки с усами математики. Зачем же мне знания по криптографии?

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

Если ты программист или специалист по ИБ, то здесь вообще от криптографии никуда не скрыться. Любой крупный проект требует обеспечения безопасности информации. Неважно, что ты разрабатываешь: контентный сервис, почтовик, мессенджер, соцсеть или просто интернет-магазин, - везде есть критичные данные, которые надо защищать от перехвата или угона БД. Каждая операция должна быть защищена криптографическими протоколами. В этом случае криптография - подходящий инструмент. Если ты еще с ней не столкнулся, будь уверен - это на 100% лишь вопрос времени.

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

Зачем изучать старые шифры?

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

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

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

Исторические шифры и первые шифраторы

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

Первым шифром, зародившимся в древних цивилизациях и актуальным, в некотором роде, и по сей день, можно считать шифр замены. Чуть позже был придуман шифр сдвига, который применялся Юлием Цезарем, почему и был назван в его честь.

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

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

Шифр сдвига

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

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
d	e	f	g	h	i	j	k	l	m	n	o	p	q	r	s	t	u	v	w	x	y	z	a	b	c

Как видишь, во втором ряду символы алфавита сдвинуты на три позиции «назад». Чтобы зашифровать сообщение, для каждого символа исходного текста нужно взять соответствующий ему символ из таблицы подстановки.

Пример шифра

Исходный текст: Hi, Brut! How are you?
Шифрованный текст: Kl, Euxw! Krz duh brx?

Расшифрование

На этапе расшифрования мы имеем шифрованный текст и ключ, равный трем. Чтобы получить исходный текст, ищем для каждого символа сдвиг на три позиции к началу алфавита. Так, для первого символа K сдвиг три будет означать символ H. Далее посимвольно расшифровываем текст, пока не получаем исходную фразу Hi, Brut! How are you? .

Криптоанализ

Легче всего такой шифр взломать простым перебором всех возможных значений ключа - их всего 25. Здесь все просто, и останавливаться смысла нет.

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

e 0,12702	s 0,06327	u 0,02758	p 0,01929	q 0,00095
t 0,09056	h 0,06094	m 0,02406	b 0,01492	z 0,00074
a 0,08167	r 0,05987	w 0,02360	v 0,00978
o 0,07507	d 0,04253	f 0,02228	k 0,00772
i 0,06966	l 0,04025	g 0,02015	j 0,00153
n 0,06749	c 0,02782	y 0,01974	x 0,00150

Что касается двухбуквенных сочетаний (биграмм), то можно заметить следующую тенденцию:

Биграмма	Процентное содержание	Биграмма	Процентное содержание
th	3,15	he	2,51
an	1,72	in	1,69
er	1,54	re	1,48
es	1,45	on	1,45
ea	1,31	ti	1,28
at	1,24	st	1,21
en	1,20	nd	1,18

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

Шифр замены

Основной недостаток шифра сдвига заключается в том, что есть всего 25 возможных значений ключа. Даже Цезарь начал подозревать, что его шифр не самая лучшая идея. Поэтому на смену ему пришел шифр замены. Для того чтобы воспользоваться этим алгоритмом, создается таблица с исходным алфавитом и, непосредственно под ним, тот же алфавит, но с переставленными буквами (или любой другой набор знаков):

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
b	e	x	g	w	i	q	v	l	o	u	m	p	j	r	s	t	n	k	h	f	y	z	a	d	c

Пример шифра

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

Исходный текст: Hi, Brut! How are you?
Шифрованный текст: Vl, Enfh!Vrz bnw drf?

Расшифрование

При расшифровании заменяем каждый символ шифротекста соответствующим символом из известной нам таблицы подстановки: v => h, l => i и так далее. После чего получаем исходную строку Hi, Brut! How are you? .

Криптоанализ

Криптоанализ этого шифра также выполняется методом частотного анализа текста. Рассмотрим пример:

MRJGRJ LK HVW XBSLHBM RI QNWBH ENLHBLJ , LHK SRMLHLXBM , WXRJRPLX , BJG XRPPWNXLBM XWJHNW . LH LK RJW RI HVW MBNQWKH XLHLWK LJ HVW ZRNMG BJG HVW MBNQWKH XLHD LJ WFNRSW . LHK SRSFMBHLRJ LK BERFH 8 PLMMLRJ . MRJGRJ LK GLYLGWG LJHR KWYWNBM SBNHK : HVW XLHD , ZWKHPLJKHWN , HVW ZWKH WJG , BJG HVW WBKH WJG . HVW VWBNH RI MRJGRJ LK HVW XLHD , LHK ILJBJXLBM BJG EFKLJWKK XWJHNW . JFPWNRFK EBJUK , RIILXWK , BJG ILNPK BNW KLHFBHWG HVWNW , LJXMFGLJQ HVW EBJU RI WJQMBJG , HVW KHRXU WAXVBJQW , BJG HVW RMG EBLMWD . IWZ SWRSMW MLYW VWNW , EFH RYWN B PLMMLRJ SWRSMW XRPW HR HVW XLHD HR ZRNU . HVWNW BNW KRPW IBPRFK BJXLWJH EFLMGLJQK ZLHVLJ HVW XLHD . SWNVBSK HVW PRKH KHNLULJQ RI HVWP LK HVW KH . SBFM \ "K XBHVWGNBM , HVW QNWBHWKH RI WJQMLKV XVFNXVWK . LH ZBK EFLMH LJ HVW 17HV XWJHFND ED KLN XVNLKHRSVWN ZNWJ . HVW HRZWN RI MRJGRJ ZBK IRFJGWG ED OFMLFK XBWKBN BJG LJ 1066 NWEFLMH ED ZLMMLBP HVW XRJTFWNRN . LH ZBK FKWG BK B IRNHNWKK , B NRDBM SBMBXW , BJG B SNLKRJ . JRZ LH LK B PFKWFP .

Частотный анализ букв этого шифра показывает следующее (читай построчно, буквы сортированы по частоте использования):

W -88 , H -74 , L -67 , J -55 , B -54 , K -52 , R -51 , N -41 , M -36 , V -35 , X -29 , G -27 , F -23 , P -16 , S -16 , I -15 , Z -13 , E -13 , D -11 , Q -10 , U -5 , Y -4 , T -1 , O -1 , A -1

Вероятно, что W => e, так как это самая часто встречающаяся буква в шифре (смотри таблицу среднестатистических частот использования букв для английского языка в предыдущем шифре).

Дальше пробуем найти наиболее короткое слово, куда входит уже известная нам буква W => e. Видим, что сочетание HVW чаще всего встречается в шифре. Нетрудно догадаться, что, скорее всего, это триграмма the, то есть в тексте мы уже определили три символа. Если посмотреть на промежуточный результат, сомнений не остается:

MRJGRJ LK the XBSLtBM RI QNeBt ENLtBLJ , LtK SRMLtLXBM , eXRJRPLX , BJG XRPPeNXLBM XeJtNe . Lt LK RJe RI the MBNQeKt XLtLeK LJ the ZRNMG BJG the MBNQeKt XLtD LJ eFNRSe . LtK SRSFMBtLRJ LK BERFt 8 PLMMLRJ . MRJGRJ LK GLYLGeG LJtR KeYeNBM SBNtK : the XLtD , ZeKtPLJKteN , the ZeKt eJG , BJG the eBKt eJG . the heBNt RI MRJGRJ LK the XLtD , LtK ILJBJXLBM BJG EFKLJeKK XeJtNe . JFPeNRFK EBJUK , RIILXeK , BJG ILNPK BNe KLtFBteG theNe , LJXMFGLJQ the EBJU RI eJQMBJG , the KtRXU eAXhBJQe , BJG the RMG EBLMeD . IeZ SeRSMe MLYe heNe , EFt RYeN B PLMMLRJ SeRSMe XRPe tR the XLtD tR ZRNU . theNe BNe KRPe IBPRFK BJXLeJt EFLMGLJQK ZLthLJ the XLtD . SeNhBSK the PRKt KtNLULJQ RI theP LK the Kt . SBFM \ "K XBtheGNBM , the QNeBteKt RI eJQMLKh XhFNXheK . Lt ZBK EFLMt LJ the 17th XeJtFND ED KLN XhNLKtRSheN ZNeJ . the tRZeN RI MRJGRJ ZBK IRFJGeG ED OFMLFK XBeKBN BJG LJ 1066 NeEFLMt ED ZLMMLBP the XRJTFeNRN . Lt ZBK FKeG BK B IRNtNeKK , B NRDBM SBMBXe , BJG B SNLKRJ . JRZ Lt LK B PFKeFP .

Отлично, уже известны три буквы. Снова ищем наиболее короткие слова с новыми известными нам подстановками. Сочетание it является частоупотребляемым, и, поскольку буква t уже дешифрована (HVW => the), очевидно, что в нашем тексте L => i (LH => it). После этого обращаемся к поиску биграмм is и to, устанавливаем, что K => s, R => o. Затем обращаем внимание на триграммы ~ing и and. Анализ текста показывает, что BJG, скорее всего, шифротекст от and. После замены всех наиболее часто встречающихся символов получаем текст:

Mondon is the XaSitaM oI QNeat ENitain , its SoMitiXaM , eXonoPiX , and XoPPeNXiaM XentNe . it is one oI the MaNQest Xities in the ZoNMd and the MaNQest XitD in eFNoSe . its SoSFMation is aEoFt 8 PiMMion . Mondon is diYided into seYeNaM SaNts : the XitD , ZestPinsteN , the Zest end , and the east end . the heaNt oI Mondon is the XitD , its IinanXiaM and EFsiness XentNe . nFPeNoFs EanUs , oIIiXes , and IiNPs aNe sitFated theNe , inXMFdinQ the EanU oI enQMand , the stoXU eAXhanQe , and the oMd EaiMeD . IeZ SeoSMe MiYe heNe , EFt oYeN a PiMMion SeoSMe XoPe to the XitD to ZoNU . theNe aNe soPe IaPoFs anXient EFiMdinQs Zithin the XitD . SeNhaSs the Post stNiUinQ oI theP is the st . SaFM \ "s XathedNaM , the QNeatest oI enQMish XhFNXhes . it Zas EFiMt in the 17th XentFND ED siN XhNistoSheN ZNen . the toZeN oI Mondon Zas IoFnded ED OFMiFs XaesaN and in 1066 NeEFiMt ED ZiMMiaP the XonTFeNoN . it Zas Fsed as a IoNtNess , a NoDaM SaMaXe , and a SNison . noZ it is a PFseFP .

London is the capital of Great Britain , its political , economic , and commercial centre . It is one of the largest cities in the world and the largest city in Europe . Its population is about 8 million . London is divided into several parts : the City , Westminster , the West End , and the East End . The heart of London is the City , its financial and business centre . Numerous banks , offices , and firms are situated there , including the Bank of England , the Stock Exchange , and the Old Bailey . Few people live here , but over a million people come to the City to work . There are some famous ancient buildings within the City . Perhaps the most striking of them is the St . Paul "s Cathedral , the greatest of English churches . It was built in the 17th century by Sir Christopher Wren . The Tower of London was founded by Julius Caesar and in 1066 rebuilt by William the Conqueror . It was used as a fortress , a royal palace , and a prison . Now it is a museum .

Как видишь, в этом криптоанализе нашим главным инструментом был статистический анализ частот. Идем дальше!

Шифр Рихарда Зорге

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

Давай разберем довольно известный шифр Рихарда Зорге - советского разведчика, который был направлен в Японию. Этот шифр продуман до мелочей. Шифрование ведется на английском языке. Первоначально нужно составить следующую таблицу:

S	U	B	W	A	Y
C	D	E	F	G	H
I	J	K	L	M	N
O	P	Q	R	T	V
X	Y	Z	.	/

Сначала записываем в нее слово SUBWAY, выбранное нами. Затем пишем все остальные буквы алфавита по порядку. Слеш означает новое слово (разделитель), а точка обозначает себя. Далее наиболее часто встречающиеся буквы английского алфавита (A , S , I , N , T , O , E , R) нумеруются в порядке появления в таблице:

0) S	U	B	W	5) A	Y
C	D	3) E	F	G	H
1) I	J	K	L	M	7) N
2) O	P	Q	4) R	6) T	V
X	Y	Z	.	/

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

Далее таблица преобразуется к следующему виду: сначала в строку по столбцам записываются наиболее часто встречаемые буквы в порядке нумерации (S, I, E, …). А затем записываются и все остальные буквы, также по столбцам в строки (С, X, U, D, J, …). Такая таблица обеспечит хорошие перемешивающие свойства и в то же время не «испортит» частотный анализ шифротекста:

	0	1	2	3	4	5	6	7	8	9
-	S	I	O	E	R	A	T	N	-	-
8	C	X	U	D	J	P	Z	B	K	Q
9	.	W	F	L	/	G	M	Y	H	V

Таблица готова. Теперь можно зашифровать сообщение.

Пример шифра

Возьмем исходный текст:

Mr . X will fly tomorrow .

Расставим слеши для разделения слов:

Mr . / X / will / fly / tomorrow .

Разобьем текст на блоки по четыре символа (просто для удобства представления):

Mr . / X / wi ll / f ly / t omor row .

Теперь текст нужно зашифровать по нашей таблице. Алгоритм такой:

1. Для каждого исходного символа ищем соответствующую ему цифру в первом столбце (для M это будет 9).
2. Для каждого исходного символа ищем соответствующую ему цифру в первом ряду (для M это будет 6).
3. Записываем полученные символы один за другим (96). Если вместо символа в первом ряду/столбце стоит прочерк, не пишем ничего:96 4 …
   M R …
4. Переходим к следующему символу. И так далее.

В итоге у нас получится такой шифротекст:

9649094 81 94 911 93939492 9397946 29624 429190 M R . / X / W I L L / F L Y / T OM OR ROW .

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

После перегруппировки у нас получится вот такой шифротекст:

96490 94819 49119 39394 92939 79462 96244 29190

Далее нужно наложить на полученный шифротекст некую гамму. Если упрощенно, то гамма - это последовательность чисел, которая выбирается для сложения с исходным шифротекстом. Например, если у нас есть гамма 1234 5678 9876 , а исходный шифротекст выглядел как 12222 14444 1555 , то конечный шифротекст после наложения гаммы выглядит как их сумма - 1234+12222, 14444+5678, 9876+1555 .

Откуда брать гамму и как незаметно передать ее в штаб? Зорге выбирал гамму из «Немецкого статистического ежегодника». Такое издание не должно было вызвать удивление у японцев, так как Зорге приехал в страну под видом немецкого журналиста. Зорге указывал страницу и столбец, откуда начиналась последовательность, которая была наложена на шифротекст в этом послании. Например, 201-я страница и 43-й столбец. Эти данные он записывал добавочным числом 20143 перед шифротекстом, который, в свою очередь, уже шифровался гаммой.

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

Предположим, мы выбрали 199-ю страницу и четвертую строку, четвертый столбец. Отсюда и начинается нужная гамма:

324 36 380 230 6683 4358 50 2841

В этом случае, чтобы наложить гамму, нужно сделать:

19946 { 96490 + 324 94819 + 36 49119 + 380 39394 + 230 92939 + 6683 79462 + 4358 96244 + 50 29190 + 2841 }

В итоге полученный шифротекст будет:

19946 96814 94855 49499 39624 99622 83820 96294 32031

Расшифрование

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

{ 96814 - 324 94855 - 36 49499 - 380 39624 - 230 99622 - 6683 83820 - 4358 96294 Mr . X will fly tomorrow

Криптоанализ

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

Шифр Вернама

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

Cуть шифра Вернама крайне проста. Для этого нужно вспомнить операцию «исключающее или» или сложение по модулю 2. Итак, для сообщения plaintext шифротекст будет равен:

-- -- - +

G 11011

Во времена Первой мировой войны двоичные коды для символов задавались в Международном телеграфном алфавите № 2 (International Telegraph Alphabet No. 2, ITA2).

На самом деле, несмотря на свою криптостойкость, этот шифр имеет больше минусов, нежели плюсов:

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

Пример шифра

Исходный текст: HELLO
Ключ: AXHJB

Складываем побитово по модулю 2 и ищем, какой букве соответствует полученный код в телеграфном алфавите:

H⊕A = 10100⊕00011 = 10111 => Q
E⊕X = 00001⊕11101 = 11100 => M
L⊕H = 10010⊕10100 = 00110 => I
L⊕J = 10010⊕01011 = 11001 => B
O⊕B = 11000⊕11001 = 00001 => E

Шифрованный текст: QMIBE

Расшифрование

Расшифрование с помощью ключа выполняется аналогично шифровке:

ciphertext⊕key = plaintext

Криптоанализ

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

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

Рассмотрим атаку, которая осуществима, если мы дважды при шифровании используем один и тот же ключ. Она называется атака вставки.

Предположим, нам удалось перехватить зашифрованное сообщение QMIVE. Мы пытаемся взломать шифр и убедили отправителя зашифровать свое сообщение еще раз, но при этом поставить первым символом 1 (конечно, отправитель должен быть безмерным простофилей, чтобы выполнить такое условие, но, предположим, мы умеем убеждать).

Тогда мы получаем шифротекст VDYBJY.

Нам известно, что первый символ 1. Я вычисляю первый символ секретного ключа key:

H⊕D = 10100⊕01001 = 11101 => X

Применяем его к первому тексту и получаем:

M⊕X = 11100⊕11101 = 00001 => E

• складываем символ открытого текста с символом шифротекста => узнаем символ ключа;
• складываем символ ключа с соответствующим символом шифротекста => получаем символ открытого текста

Такая последовательность операций повторяется, пока не станут известны все символы открытого текста.

Шифровальные машины

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

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

Пример работы

Пусть начальное положение диска задает подстановку:

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
b	e	x	g	w	i	q	v	l	o	u	m	p	j	r	s	t	n	k	h	f	y	z	a	d	c

После того как первая буква исходного текста заменена, ротор поворачивается и подстановка сдвигается на один символ:

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
e	x	g	w	i	q	v	l	o	u	m	p	j	r	s	t	n	k	h	f	y	z	a	d	c	b

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

Энигма

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

При шифровании необходимо было учитывать начальное положение роторов, их порядок и положения колец. Для двойной замены букв используется штекерная панель. Рефлектор осуществляет завершающую подстановку для контроля соответствия между операциями зашифрования и расшифрования. Взгляни на конструкцию «Энигмы»:

На рисунке жирной линией выделено, как буква A вводится с клавиатуры, кодируется штекером, проходит через три ротора, заменяется на рефлекторе и выходит зашифрованной буквой D.

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

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

Сигаба

Спустя десять лет американскими военными была разработана роторная шифровальная машина «Сигаба», которая значительно превзошла по характеристикам свою прародительницу. «Сигаба» имеет три блока по пять роторов и печатающий механизм. Шифрование на этой машине использовалось американскими военными и военно-морским флотом вплоть до 1950-х годов, пока ее не сменила более новая модификация KL-7. Как известно, эта роторная машина так и не была взломана.

Purple

Говоря о знаменитых криптографических механизмах, нельзя не упомянуть о японской шифровальной машине Purplе, как ее назвали американцы. Шифрование в Purple также основывалось на движении четырех роторов, а секретный ключ задавался один раз в день. Текст вводился с клавиатуры, при помощи роторов заменялся на шифрованный и выводился напечатанным на бумаге. При расшифровании процесс последовательного прохождения через роторы повторялся в обратном порядке. Такая система является совершенно стойкой. Однако на практике ошибки при выборе ключей привели к тому, что Purple повторила судьбу немецкой «Энигмы». Она была взломана американским отделом криптоаналитиков.

Выводы

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

ссылки:

Это первый урок из цикла «Погружение в крипту». Все уроки цикла в хронологическом порядке:

• Уроки криптографии. Основные шифры. часть 1. Основы, исторические шифраторы, как работают (и анализируются) шифры сдвига, замены, Рихарда Зорге, шифр Вернама и шифровальные машины (ты здесь)
• . часть 2. Что это такое, как выполняется распределение ключей и как выбрать криптостойкий ключ
• Что тaкое сеть Фейстеля, какими бывают отечественные блочные шифры, используемые в современных протоколах, - ГОСТ 28147-89, «Кузнечик»
• Урок 4. Современные зарубежные шифры . Что такое, как работают и в чем разница между 3DES, AES, Blowfish, IDEA, Threefish от Брюса Шнайдера
• Урок 5. Электронная подпись . Виды ЭП, как они работают и как их использовать
• Урок 6. Квантовая криптография . Что это такое, где используется и как помогает в распределении секретных ключей, генерации случайных чисел и электронной подписи

[Всего голосов: 5 Средний: 3.8/5]

Last updated by at Июнь 28, 2016 .

Вопросы тайнописи оказались для человечества столь актуальны, что еще в древности возникла целая наука криптография (от греческого «криптос» - скрытый). Первые специалисты по шифрованию и расшифровке сообщений появились одновременно с первыми рукописными текстами.

Античная секретность

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

Одним из самых известных примеров шифрованных сообщений считается переписка Юлия Цезаря. Знаменитый полководец использовал очень простой, но одновременно вполне надежный способ криптографического текста: вместо правильной буквы писалась та, что находилась в латинском алфавите на три позиции дальше. Это позволяло составлять сообщения очень быстро и так же быстро их расшифровывать. Если учесть, что римляне не делали пробелов между словами, то в итоге письмо превращалось во множество ничем не связанных знаков. Соответственно, враги ничего не могли понять из перехваченного сообщения.

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

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

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

Тайны средневековья

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

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

Одним из самых распространенных способов шифрования писем стало использование гибридной системы.

То есть, например, в донесении сначала использовался алфавитный сдвиг (зачастую по гораздо более сложной системе, чем у Цезаря), а затем латинские буквы заменялись на буквы менее распространенного (допустим, армянского) алфавита или на цифры. При этом для надежности само донесение могло быть составлено на чередовании немецкого и французского языков. Правда, при такой системе работа по подготовке секретных сведений и последующий «перевод» на обычный язык отнимали очень много времени. А простая ошибка или опечатка могли вообще все испортить.

Однако опасения, что враги все же сумеют подобрать ключи и прочитают секретное послание, привели к появлению специальных таблиц. Это было некое подобие паролей, когда слова «ждем хорошей погоды» могли означать просьбу об отправке денег. В таком случае смысл сообщения понимал только обладатель дешифратора. А само письмо при перехвате не вызывало подозрений. У дипломатов отныне имелись толстые книги, в которых были предусмотрены тысячи вариантов для создания секретного текста. Подобный способ получил название стеганография.

От возрождения к новому времени

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

С появлением книгопечатания труды по тайнописи (которые выходили все чаще) стали доступны тысячам читателей. Отцом современной криптографии считается итальянский ученый Леон Альберти. Его трактат о методах шифрования стал своеобразной библией для последующих специалистов-криптологов. Кроме того, Альберти придумал и не-1У сколько технических устройств, которые стали прообразом будущих шифровальных механизмов.

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

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

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

А в 1790-е годы под руководством будущего президента США Томаса Джефферсона была построена машина, с помощью которой удавалось производить шифрование очень быстро. Считается, что победа британских колонистов в войне за независимость, а также успехи армии северян в Гражданской войне во многом были обусловлены работой опытных криптографов в их войсках.

Эпоха электричества

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

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

Так, название одной из самых знаменитых шифровальных машин стало нарицательным. Словом «энигма» называли любую задачу, решение которой выглядело невозможным. Так как во время Второй мировой войны устройства из семейства «Энигма» активно использовали войска и флот Германии, то в Британии создали мощную службу для расшифровки перехвачен-
ных сообщений. На определенном этапе в этом центре работали почти 12 тысяч сотрудников.

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

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

Вообще же во время Второй мировой войны шифровальные машины использовали все воюющие страны.

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

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

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

Единственной трудностью оказалось отсутствие в словаре навахо таких слов, как «подводная лодка» или «взвод». Пришлось придумать около четырехсот словосочетаний (типа «железная рыба» и «черные овцы»), чтобы закрыть проблемы с военной терминологией.

Понятно, что ни Германиями Япония не имели физической возможности создать подобную систему радистов в своих армиях. А вот Советский Союз, чьи солдаты еще во время Зимней войны несли огромные потери из-за скверной работы радистов-шифроваль-
щиков, вполне мог. Ведь в СССР проживали десятки малочисленных народов, чьи сложные языки могли стать надежным средством оперативной связи между штабами самых разных подразделений. По некоторым данным, Иосифу Сталину не раз предлагали привлечь в армию в качестве радистов как представителей народов Крайнего Севера, так и жителей ряда народностей Кавказа. Но будущий генералиссимус, которому заговорщики и предатели гораздо чаще мерещились в среде своих собственных подданных, чем в стане откровенного врага, решительно отверг эту идею.

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

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

Рис.2.4. Сцитала

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

Другим широко известным криптографическим устройством защиты информации был «диск Энея» - инструмент для защиты информации, придуманный Энеем Тактиком в IV веке до н. э. Устройство представляло собой диск диаметром 13-15 см и толщиной 1-2 см с проделанными в нём отверстиями, количество которых равнялось числу букв в алфавите. Каждому отверстию ставилась в соответствие конкретная буква. В центре диска находилась катушка с намотанной на неё ниткой .

Рис.2.5. Диск Энея

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

Прибор получил название «Линейка Энея» . Она представляла собой устройство, имеющее отверстия, количество которых равнялось количеству букв алфавита. Каждое отверстие обозначалось своей буквой; буквы по отверстиям располагались в произвольном порядке. К линейке была прикреплена катушка с намотанной на неё ниткой. Рядом с катушкой имелась прорезь. При шифровании нить протягивалась через прорезь, а затем через отверстие, соответствующее первой букве шифруемого текста, при этом на нити завязывался узелок в месте прохождения её через отверстие; затем нить возвращалась в прорезь и аналогично зашифровывалась вторая буква текста и т. д. После окончания шифрования нить извлекалась и передавалась получателю сообщения. Получатель, имея идентичную линейку, протягивал нить через прорезь до отверстий, определяемых узлами, и восстанавливал исходный текст по буквам отверстий. Такой шифр является одним из примеров шифра замены: когда буквы заменяются на расстояния между узелками с учетом прохождения через прорезь. Ключом шифра являлся порядок расположения букв по отверстиям в линейке. Посторонний, получивший нить (даже имея линейку, но без нанесенных на ней букв), не сможет прочитать передаваемое сообщение.

1 Розеттский камень - плита из гранодиорита, найденная в 1799 г. в Египте возле небольшого города Розетта (теперь Рашид), недалеко от Александрии, с выбитыми на ней тремя идентичными по смыслу текстами, в том числе двумя на древнеегипетском языке и одним на древнегреческом языке. Древнегреческий был хорошо известен лингвистам, и сопоставление трёх текстов послужило отправной точкой для расшифровки египетских иероглифов.

2.3. Формальная криптография

Этап формальной криптографии (конец XV – начало XX вв.) связан с появлением формализованных и относительно стойких к ручному криптоанализу шифров. В европейских странах это произошло в эпоху Возрождения, когда развитие науки и торговли вызвало спрос на надежные способы защиты информации.

К концу XIV в. между итальянскими городами-государствами в переписке уже применялись 2 (лат. nomen - «имя» и calator - «раб», «слуга»). Они состояли из кодовых обозначений для слогов, слов и имен, а также алфавитов шифрозамен. Вплоть до XIX в. номенклаторы оставались самой широко используемой системой сокрытия содержания сообщений .

Симеоне де Крема (Simeone de Crema) был первым (1401 г.), кто использовал таблицы омофонов для сокрытия частоты появления гласных в тексте при помощи более чем одной шифрозамены ().

Отцом западной криптографии называют учёного эпохи Возрождения Леона Баттисту Альберти. Изучив методы вскрытия использовавшихся в Европе моноалфавитных шифров (), он попытался создать шифр, который был бы устойчив к частотному криптоанализу. Его «Трактат о шифрах» был представлен в папскую канцелярию в 1466 г. и считается первой научной работой по криптографии. Он предложил вместо единственного секретного алфавита, как в моноалфавитных шифрах, использовать два или более, переключаясь между ними по какому-либо правилу.

Рис.2.6. Фрагмент первой страницы «Трактата о шифрах» Леона Баттисто Альберти

Однако флорентийский учёный так и не смог оформить своё открытие в полную работающую систему, что было сделано уже его последователями (Блез Вижинер). Другой работой, в которой обобщены и сформулированы известные на тот момент алгоритмы шифрования, является труд «Полиграфия» (1518 г.) немецкого аббата Иоганна Трисемуса (Тритемия). Он же первым заметил, что шифровать можно и по две буквы за раз - биграммами (хотя первый был предложен лишь в XIX веке).

Рис.2.7. Первый печатный труд по криптографии - «Полиграфия» Иоганна Трисемуса [Национальный музей криптографии, США ]

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

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

В 1863 г. Фридрих Касиски (англ. Friedrich Kasiski) опубликовал метод, впоследствии названный его именем, позволявшим быстро и эффективно вскрывать практически любые шифры того времени, в т.ч. . Метод состоял из двух частей - определение периода шифра и дешифровка текста с использованием .

Рис.2.8. Титульный лист «Тайнописи и искусство дешифрования» Фридриха Касиски

В 1883 г. голландец Огюст Керкгоффс 3 опубликовал труд под названием «Военная криптография» (фр. «La Cryptographie Militaire»). В нём он описал шесть требований, которым должна удовлетворять защищённая система. Хотя к некоторым из них стоит относиться с подозрением, стоит отметить труд за саму попытку:

1. шифр должен быть физически, если не математически, невскрываемым;

2. система не должна требовать секретности, на случай, если она попадёт в руки врага;

3. ключ должен быть простым, храниться в памяти без записи на бумаге, а также легко изменяемым по желанию корреспондентов;

4. зашифрованный текст должен (без проблем) передаваться по телеграфу;

5. аппарат для шифрования должен быть легко переносимым, работа с ним не должна требовать помощи нескольких лиц;

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

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

Рис.2.9. Титульный лист брошюры «Военная криптография» Огюста Керкгоффса

В 1920 г. вышла монография американского криптографа российского происхождения Уильяма Ф. Фридмана «Индекс совпадения и его применение в криптографии» (англ. «Index of Coincidence and Its Applications in Cryptography»). Работа вышла в открытой печати, несмотря на то, что была выполнена в рамках военного заказа. Двумя годами позже Фридман ввёл в научный обиход термины и .

Криптография оказала влияние и на литературу . Упоминания о криптографии встречаются ещё во времена Гомера и Геродота, хотя они описывали искусство шифрования в контексте различных исторических событий. Первым вымышленным упоминанием о криптографии можно считать роман «Гаргантюа и Пантагрюэль» французского писателя XVI века Франсуа Рабле, в одной из глав которого описываются попытки чтения зашифрованных сообщений. Упоминание встречается и в «Генрихе V» Шекспира. Впервые как центральный элемент художественного произведения криптография используется в рассказе «Золотой жук» Эдгара Аллана По 1843 г. В нём писатель не только показывает способ раскрытия шифра, но и результат, к которому может привести подобная деятельность - нахождение спрятанного сокровища. Одним из лучших описаний применения криптографии является рассказ 1903 г. Артура Конан Дойля «Пляшущие человечки». В рассказе великий сыщик Шерлок Холмс сталкивается с разновидностью шифра, который не только прячет смысл написанного, но, используя символы, похожие на детские картинки, скрывает сам факт передачи секретного сообщения. В рассказе герой успешно применяет частотный анализ, а также предположения о структуре и содержании открытых сообщений для разгадывания шифра.

Перед началом Второй мировой войны ведущие мировые державы имели электромеханические шифрующие устройства, результат работы которых считался невскрываемым. Эти устройства делились на два типа - роторные машины и машины на цевочных дисках. К первому типу относят «Энигму» , использовавшуюся войсками Германии и её союзников, второго типа - американская M-209 . В СССР производились оба типа машин.

Рис.2.11. Шифровальные устройства [en.wikipedia.org , www.cryptomuseum.com ]

Успешные криптоатаки на подобного рода криптосистемы стали возможны только с появлением ЭВМ.

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

3 Огюст Керкгоффс (Auguste Kerckhoffs, 1835 - 1903 гг.) - голландский лингвист и криптограф, профессор Парижской высшей школы коммерции во второй половине XIX века. В русских источниках встречаются разные переводы фамилии - Керкхофф, Кирхгоф, Керкгоффс, Керхофс, Керкхоффс. Полное имя, полученное при крещении, - Жан Вильгельм Губерт Виктор Франсуа Александр Огюст Керкгоффс фон Ниувенгоф .

2.4. Математическая криптография

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

Ключевой вехой в развитии криптографии является фундаментальный труд Клода Шеннона «Теория связи в секретных системах» (англ. Communication Theory of Secrecy Systems) - секретный доклад, представленный автором в 1945 г., и опубликованный им в «Bell System Technical Journal» в 1949 г. В этой работе, по мнению многих современных криптографов, был впервые показан подход к криптографии в целом как к математической науке.

Рис.2.12. Сборник со статьей «Теория связи в секретных системах» Клода Шеннона

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

В 1967 г. выходит книга Дэвида Кана «Взломщики кодов». Хотя книга не содержала сколько-нибудь новых открытий, она подробно описывала имеющиеся на тот момент результаты в области криптографии, большой исторический материал, включая успешные случаи использования криптоанализа, а также некоторые сведения, которые правительство США полагало всё ещё секретными. Но главное - книга имела заметный коммерческий успех и познакомила с криптографией десятки тысяч людей. С этого момента начали понемногу появляться работы и в открытой печати.

Рис.2.13. Обложка первого издания «Взломщиков кодов» Дэвида Кана

Примерно в это же время Хорст Фейстель переходит из Военно-воздушных сил США на работу в лабораторию корпорации IBM. Там он занимается разработкой новых методов в криптографии и разрабатывает , являющуюся основой многих современных шифров, в том числе шифра Lucifer, ставшего прообразом шифра – бывшего стандарта шифрования США, первого в мире открытого государственного стандарта на шифрование данных. На основе ячейки Фейстеля были созданы и другие блочные шифры, в том числе TEA (1994 г.), Twofish (1998 г.), IDEA (2000 г.), а также бывший () и действующий () российские стандарты шифрования.

В 1976 г. публикуется работа Уитфилда Диффи и Мартина Хеллмана «Новые направления в криптографии» (англ. «New Directions in Cryptography»). Данная работа открыла новую область в криптографии, теперь известную как . Также в работе содержалось описание , позволявшего сторонам сгенерировать общий секретный ключ, используя открытый канал связи.

Рис.2.14. Начало статьи «Новые направления в криптографии» Уитфилда Диффи и Мартина Хеллмана

Хотя работа Диффи-Хеллмана создала большой теоретический задел для открытой криптографии, первой реальной криптосистемой с открытым ключом считают алгоритм (названный по имени авторов - Рон Ривест (R. Rivest), Ади Шамир (A. Shamir) и Леонард Адлеман (L. Adleman)). Опубликованная в августе 1977 г., работа позволила сторонам обмениваться секретной информацией, не имея заранее выбранного секретного ключа. Стоит отметить, что и , и были впервые открыты в английских спецслужбах, но не были ни опубликованы, ни запатентованы из-за секретности.

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

Создание асимметричных криптосистем подтолкнуло математиков и криптоаналитиков к изучению способов , операций над в конечном поле и т.д.

Относительно новым методом является . Вероятностное шифрование предложили Шафи Гольдвассер (Goldwasser) и Сильвио Микэли (Micali). Шифрование было названо «вероятностным» в связи с тем, что один и тот же исходный текст при шифровании с использованием одного и того же ключа может преобразовываться в совершенно различные шифротексты. При использовании криптосистем с открытым ключом существует возможность подбора открытого текста сопоставлением перехваченного шифротекста с результатом шифрования. Вероятностное шифрование позволяет на порядки увеличить сложность такого вида атаки.

Чарльз Беннет (Charles Bennet) и Жиль Брассард (Gilles Brassard), опираясь на работу Стивена Уиснера (Stephen Wiesner), разработали теорию , которая базируется скорее на квантовой физике, нежели на математике. Процесс отправки и приёма информации выполняется посредством объектов квантовой механики (например, при помощи электронов в электрическом токе, или фотонов в линиях волоконно-оптической связи). Основанная на принципах квантовой механики, эта система, в отличие от обычной криптографии, теоретически позволяет гарантированно защитить информацию от злоумышленника, даже если тот обладает самой современной технологией и неограниченными вычислительными мощностями. На данный момент, разрабатываются только прототипы квантовых криптосистем.

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

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

Вопросы для самопроверки