Криптография
Часть 4. ИЗ ИСТОРИИ КРИПТОГРАФИИ
Криптография - тайнопись. Термин ввел Д. Валлис. Потребность шифровать и передавать шифрованные сообщения возникла очень давно. Так, еще в V-IV вв. до н. э. греки применяли специальное шифрующее устройство. По описанию Плутарха, оно состояло из двух палок одинаковой длины и толщины. Одну оставляли себе, а другую отдавали отъезжающему. Эти палки называли скиталами. Когда правителям нужно было сообщить какую-нибудь важную тайну, они вырезали длинную и узкую, вроде ремня, полосу папируса, наматывали ее на свою скиталу, не оставляя на ней никакого промежутка, так чтобы вся поверхность палки была охвачена этой полосой. Затем, оставляя папирус на скитале в том виде, как он есть, писали на нем все, что нужно, а написав, снимали полосу и без палки отправляли адресату. Так как буквы на ней разбросаны в беспорядке, то прочитать написанное он мог, только взяв свою скиталу и намотав на нее без пропусков эту полосу.
Аристотелю принадлежит способ дешифрования этого шифра. Надо изготовить длинный конус и, начиная с основания, обертывать его лентой с шифрованным сообщением, постепенно сдвигая ее к вершине. В какой-то момент начнут просматриваться куски сообщения. Так можно определить диаметр скиталы.
В Древней Греции (||в. до н. э.) был известен шифр, называемый "квадрат Полибия". Это устройство представляло собой квадрат 5x5, столбцы и строки которого нумеровали цифрами от 1 до 5. В каждую клетку этого квадрата записывалась одна буква. (В греческом варианте одна клетка оставалась пустой, в латинском - в одну клетку помещали две буквы i и j.) В результате каждой букве открытого текста (ОТ) отвечала пара чисел и шифрованный текст (ШТ) превращался в последовательность пар чисел. Например,
Я мыслю, следовательно, существую ОТ (рус.)
Это сообщение записано при использовании латинского варианта "квадрата Полибия ", в котором буквы расположены в алфавитном порядке.
В I в. н.э. Ю. Цезарь во время войны с галлами, переписываясь со своими друзьями в Риме, заменял в сообщении первую букву латинского алфавита (А.) на четвертую (D), вторую (В) - на пятую (Е), наконец, последнюю - на третью:
|
Сообщение об одержанной им победе выглядело так:
Император Август (I в. н. э.) в своей переписке заменял первую букву на вторую, вторую - на третью и т. д., наконец, последнюю - на первую:
|
Его любимое изречение было:
Торопись медленно ОТ (рус.)
Квадрат Полибия, шифр Цезаря входят в класс шифров, называемых "подстановка" или "простая замена". Это такой шифр, в котором каждой букве алфавита соответствует буква, цифра, символ или какая-нибудь их комбинация.
В известных рассказах Пляшущие человечки (Конан Дойля) и Золотой жук (Эдгара По) используемые шифры относятся к указанному классу шифров. В другом классе шифров - "перестановка" - буквы сообщения каким-нибудь способом переставляются между собой. К этому классу принадлежит шифр скитала.
К классу "перестановка" относится шифр "маршрутная транспозиция" и его вариант "постолбцовая транспозиция". В каждом из них в данный прямоугольник [n х т] сообщение вписывается заранее обусловленным способом, а столбцы нумеруются или обычным порядком следования, или в порядке следования букв ключа - буквенного ключевого слова. Так, ниже в первом прямоугольнике столбцы нумеруются в обычном порядке следования - слева направо, а во втором - в порядке следования букв слова "Петербург".
Используя порядок извлечения букв этого ключа из алфавита, получим набор чисел [5 3 8 4 6 1 9 7 2]. Нумерация букв – цифрами из {1,2,…,9}
«Прилепляяся премудрум, премудр будешь» (из послания Даниила Зоточенаго к в.к. Ярославу Всеволодичу)
В первом случае шифрованный текст найдем, если будем выписывать буквы очередного столбца в порядке следования столбцов (прямом или обратном) во втором, - если будем выписывать буквы столбца в порядке следования букв ключа. Таким образом, будем иметь:
(Из послания Даниила Зоточенаго к великому князю Ярославу Всеволодичу)
К классу "перестановка" принадлежит и шифр, называемый "решетка Кардано". Это прямоугольная карточка с отверстиями, чаще всего квадратная, которая при наложении на лист бумаги оставляет открытыми лишь некоторые его части. Число строк и столбцов в карточке четно. Карточка сделана так, что при ее последовательном использовании (поворачивании) каждая клетка лежащего под ней листа окажется открытой. Карточку сначала поворачивают вдоль вертикальной оси симметрии на 180°, а затем вдоль горизонтальной оси также на 180°. И вновь повторяют ту же процедуру:
3 поворота (на 180°), 16 белых кв-ов.
Если решетка Кардано - квадрат, то возможен второй вариант самосовмещений фигуры, а именно, последовательные повороты вокруг центра квадрата на 90°:
Рассмотрим примеры:
квадрат поворачивать последовательно
Легко прочесть зашифрованное квадратной решеткой Кардано сообщение:
Второе сообщение:
также нетрудно расшифровать, пользуясь прямоугольной решеткой.
Термин "шифр" арабского происхождения. В начале XV в. арабы опубликовали энциклопедию Шауба Аль-Аща, в которой есть специальный раздел о шифрах. В этой энциклопедии указан способ раскрытия шифра простой замены. Он основан на различной частоте повторяемости букв в тексте. В этом разделе есть перечень букв в порядке их повторяемости на основе изучения текста Корана. Заметим, что в русском тексте чаще всего встречается буква "О", затем буква "Е" и на третьем месте стоят буквы "И" и "А". Более точно: на 1000 букв русского текста в среднем приходится 90 букв "О", 72 буквы "Е" или "Ё" и по 60 букв "И" и "А" и т.д.
Неудобство шифров типа "подстановка" ("простая замена") в случае использования стандартного алфавита очевидно. Таблица частот встречаемости букв алфавита позволяет определить один или несколько символов, а этого иногда достаточно для дешифрования всего сообщения Пляшущие человечки (Конан Дойля) или Золотой жук (Эдгара По). Поэтому обычно пользуются разными приемами, чтобы затруднить дешифрование. Для этой цели используют многобуквенную систему шифрования - систему, в которой одному символу отвечает одна или несколько комбинаций двух и более символов. Другой прием - использование нескольких алфавитов. В этом случае для каждого символа употребляют тот или иной алфавит в зависимости от ключа, который связан каким-нибудь способом с самим символом или с его порядком в передаваемом сообщении.
В процессе шифрования (и дешифрования) используется таблица ("таблица Виженера"), которая устроена следующим образом: в первой строке выписывается весь алфавит, в каждой следующей осуществляется циклический сдвиг на одну букву. Так получается квадратная таблица, число строк которой равно числу столбцов и равно числу букв в алфавите. Ниже представлена таблица, составленная из 31 буквы русского алфавита 2 (без букв Ё и Ъ). Чтобы зашифровать какое-нибудь сообщение, поступают следующим образом. Выбирается слово - лозунг (например, "монастырь") и подписывается с повторением над буквами сообщения.
Чтобы получить шифрованный текст, находят очередной знак лозунга, начиная с первого в вертикальном алфавите (ВА), а ему соответствующий знак сообщения в горизонтальном (ГА). В данном примере сначала находим столбец, отвечающий букве "м" лозунга, а затем строку, соответствующую букве "р" открытого текста. На пересечении выделенных столбца и строки находим букву "э". Так продолжая дальше, находим шифрованный текст полностью:
Таблица Виженера
Наконец, к сообщению можно применять несколько систем шифрования.
Аббат Тритемиус - автор первой печатной книги о тайнописи (1518 г.) - предложил несколько шифров и среди них шифр, который можно считать усовершенствованием шифра Цезаря. Этот шифр устроен так. Все буквы алфавита 1 нумеруют по порядку (от 1 до 33 в русском варианте). Затем выбирают какое-нибудь слово, называемое "ключом", например "Вологда", и подписывают под сообщением с повторением, как показано ниже:
Чтобы получить шифрованный текст, складывают номер очередной буквы с номером соответствующей буквы ключа. Если полученная сумма больше 33, то из нее вычитают 33. В результате получают последовательность чисел от 1 до 33. Вновь заменяя числа этой последовательности соответствующими буквами, получают шифрованный текст. Разбивая этот текст на группы одной длины (например, по 5), получают шифрованное сообщение:
Если под ключом шифра понимать однобуквенное слово "В" (в русском варианте), то мы получим шифр Цезаря. В этом случае для того же текста шифрованное сообщение принимает вид
Появившийся в XVIII в. шифр "по книге" можно рассматривать как дальнейшее усовершенствование шифра Ю. Цезаря. Чтобы воспользоваться этим шифром, два корреспондента договариваются об определенной книге, имеющейся у каждого из них. Например, Гашек Я. Похождения бравого солдата Швейка. М., 1977. В качестве ключа каждый из них может выбрать "слово" той же длины, что и передаваемое сообщение. Этот ключ кодируется парой чисел, а именно номером страницы и номером строки на ней, и передается вместе с шифрованным сообщением. Например, (287,2) определяет "слово", т. е. текст избранной книги: "Внимательно прочитав эту страницу, офицеры ничего не поняли..." Этому ключу отвечает последовательность чисел:
Зная этот ключ, можно легко расшифровать сообщение:
(Заметим, что в названной книге на указанной странице описывается вариант шифра "по книге".)
Примером нераскрываемого шифра может служить "одноразовый шифровальный блокнот" - шифр, в основе которого лежит та же идея, что и в шифре Цезаря. Назовем расширенным алфавитом 4 совокупность букв алфавита, знаков препинания {.,:;?!()-"}и знака пробела между словами. Число символов расширенного алфавита в русском варианте равно 44. Занумеруем символы расширенного алфавита числами от 0 до 43. Тогда любой передаваемый текст можно рассматривать как последовательность {аn} чисел множества А = {0, 1, 2, ..., 43}.
Предположим, что имеем случайную последовательность {сn} из чисел множества А той же длины, что и передаваемый текст (ключ). Складывая по модулю 44 число ап передаваемого текста с соответствующим числом сn ключа
получим последовательность {bn} знаков шифрованного текста. Чтобы получить передаваемый текст, можно воспользоваться тем же ключом:
У двух абонентов, находящихся в секретной переписке, имеются два одинаковых блокнота. В каждом из них на нескольких листах напечатана случайная последовательность чисел множества А. Отправитель свой текст шифрует указанным выше способом при помощи первой страницы блокнота. Зашифровав сообщение, он уничтожает использованную страницу и отправляет его второму абоненту, получатель шифрованного текста расшифровывает его и также уничтожает использованный лист блокнота. Нетрудно видеть, что одноразовый шифр нераскрываем в принципе, так как символ в тексте может быть заменен любым другим символом и этот выбор совершенно случаен.
Случайная последовательность чисел множества А может быть получена при помощи "вертушки со стрелкой" (рис.2.1). Обод вертушки разделен на 44 равные части (дуги). Каждая из них помечена числами от 0 до 43. Запуская вертушку, получим какое-нибудь из чисел множества А. Так продолжая дальше, можем получить случайную последовательность любой длины.
Рис. 4.1
С появлением радио- и телеграфных линий всякую информацию удобно передавать, используя двоичный код, например азбуку Морзе. В современных системах шифрования обычно шифруют сообщения, записанные двоичным кодом. Далее будет рассмотрена система шифрования двоичной последовательности, в которой идея шифра Цезаря получает дальнейшее развитие.