Читаем 25 этюдов о шифрах онлайн бесплатно

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

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

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

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

Н.Н. Андреев

Президент Академии криптографии Российской Федерации

Настоящая книга является популярным изложением основных понятии и идеи современной криптографии, а точнее — математических вопросов криптографии. Она открывает новую серию «Математические проблемы криптологии».

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

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

Основные термины и понятия при первом своем появлении в тексте выделяются курсивом. Иногда в текст мелким шрифтом «врезается» формальное определение этого понятия.

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

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

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

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

Школьникам, которые решили избрать криптографию своей профессией, рекомендуем один из трех вузов:

—  институт криптографии, связи и информатики (ИКСИ) Академии безопасности ФСК Российской Федерации;

—  механико-математический факультет Московского государственного университета им. М.В. Ломоносова (МГУ);

—  факультет защиты информации Российского государственного гуманитарного университета (РГГУ).

Авторы благодарят сотрудников лаборатории МГУ по математическим проблемам криптографии, которые участвовали в обсуждении этой книги на всех этапах ее написания.

С.А. Дориченко

В.В. Ященко

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

Зачем? Чтобы предотвратить возможный вред от разглашения информации.

Информация — основное понятие научных направлений, изучающих процессы передачи, переработки и хранения различных данных. Суть понятия информации обычно поясняется на примерах. Формальное определение не дается, поскольку понятие информации относится к таким же фундаментальным понятиям, как материя, люди уже давно поняли, что информация может быть настоящим сокровищем, и поэтому часто много усилий затрачивалось как на ее охрану, так и на ее добывание. Вообще говоря, совершенно не обязательно это связано с какими-то «шпионскими» делами. Информация, которая нуждается в защите, возникает в самых разных жизненных ситуациях. Обычно в таких случаях говорят, что информация содержит тайну или является защищаемой, приватной, конфиденциальной, секретной. Для наиболее типичных, часто встречающихся ситуаций такого типа введены даже специальные понятия:

— государственная тайна;

— военная тайна;

— коммерческая тайна;

— юридическая тайна;

— врачебная тайна и т.д.

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

— имеется какой-то определенный круг законных пользователей, которые имеют право владеть этой информацией;

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

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

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

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

Стеганография — набор средств и методов скрытия факта передачи сообщения.

Шифр — способ, метод преобразования информации с целью ее защиты от незаконных пользователей.

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

Подумайте сами:

1. Приведите примеры упомянутых в этюде видов тайны.

2. Для ваших примеров опишите законный пользователей, незаконных пользователей, возможный вред от разглашения защищаемой информации.

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

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

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

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

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

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

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

Подумайте сами:

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

Можно представить так:

Здесь A и B — удаленные законные пользователи защищаемой информации; они хотят обмениваться информацией по общедоступному каналу связи, а П — незаконный пользователь (противник), который может перехватывать передаваемые по каналу связи сообщения и пытаться извлечь из них интересующую его информацию

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

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

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

Вскрытие (взламывание) шифра — процесс получения защищаемой информации (открытого текста) из шифрованного сообщения (шифртекста) без знания примененного шифра.

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

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

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

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

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

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

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