Главная > Разное > Введение в криптографию
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

Глава 7. Олимпиады по криптографии для школьников

Предисловие

С 1991 г. Институт криптографии, связи и информатики Академии ФСБ Российской Федерации проводит ежегодные олимпиады по криптографии и математике для школьников г. Москвы и Подмосковья. Год от года растет популярность этих олимпиад, о чем свидетельствует, например, то, что в последней из них приняло участие более пятисот школьников 9-11 классов. Олимпиады по криптографии и математике вызывают интерес у школьников необычностью своего жанра. Кроме того, призерам предоставляются льготы при поступлении в Институт.

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

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

1. Введение

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

Сообщение, которое вы хотите передать адресату, будем называть открытым сообщением. Например, в задаче 2.5 (раздел «Условия задач») одним из открытых сообщений является фраза:

КОРАБЛИ ОТХОДЯТ ВЕЧЕРОМ

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

ЮПЯТБНЩМСДТЛЖГПСГХСЦЦ

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

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

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

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

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

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

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

Используя понятие ключа, процесс зашифрования можно описать в виде соотношения

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

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

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

Среди всех шифров можно выделить два больших класса: шифры перестановки и шифры замены.

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

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

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

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

Под стойкостью шифра, как правило, понимается способность противостоять попыткам провести его вскрытие. При анализе шифра обычно исходят из принципа, сформулированного голландцем Огустом Керкгоффсом (1835-1903). Согласно этому принципу при вскрытии криптограммы противнику известно о шифре все, кроме используемого ключа. Одной из естественных характеристик шифра является число его возможных ключей. Ведь вскрытие шифра можно осуществлять перебором всех возможных его ключей. Мы уже говорили, что в приводимых ниже задачах олимпиад, как правило, шифр известен, но неизвестен выбранный ключ, что соответствует принципу Керкгоффса. Так, в задаче 4.4 все дело сводится к перебору 24 различных вариантов ключа, из которых только один дает читаемый текст. Поэтому многие участники олимпиады смогли восстановить сообщение на латинском языке, даже не зная этого языка.

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

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

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

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

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

<< Предыдущий параграф Следующий параграф >>
Оглавление