7.1. Введение

Next: 7.2. Шифры замены Up: 7. Олимпиады по криптографии Previous: Предисловие Contents: Содержание

7.1. Введение

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

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

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

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

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

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

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

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

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

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

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

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

$\begin{displaymath}f_\alpha(А) = B, \end{displaymath}$

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

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

$\begin{displaymath}g_\alpha(B) = A. \end{displaymath}$

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

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

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

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

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

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

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

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

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

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

Next: 7.2. Шифры замены Up: 7. Олимпиады по криптографии Previous: Предисловие Contents: Содержание