в развитии криптографии.
Во время конфликта между Афинами и Спартой для контроля над Пелопоннесом часто использовалась скитала — прибор, состоящий из цилиндра и обмотанной вокруг него по спирали узкой полоски бумаги, на которой писалось сообщение. Хотя используемый метод (то есть алгоритм шифрования) был известен противнику, не зная точных размеров скиталы, было чрезвычайно трудно расшифровать перехваченное сообщение. Толщина и длина скиталы были, в сущности, ключом к этой системе шифрования. После разматывания бумажной ленты прочитать сообщение было невозможно. На рисунке ниже передаваемое сообщение (М) выглядит так: A message encoded with a scytale («Сообщение, закодированное с помощью скиталы»), но после разматывания бумажной ленты сообщение превратилось в тарабарщину (С): anh mca eos sdc sey adt gwa eil ete. * * *
Использование скиталы основано на криптографическом методе, известном как перестановочное шифрование, когда буквы сообщения переставляются местами. Чтобы получить представление о силе этого метода, рассмотрим простой пример перестановки всего трех букв: А, О и R. Быстрая проверка без каких-либо расчетов показывает, что они могут быть переставлены шестью различными способами: AOR, ARO, OAR, ORA, ROA и RAO. В абстрактных терминах процесс выглядит следующим образом: как только одна из трех возможных букв поставлена на первое место, что дает нам три различных возможности, остаются еще две буквы, которые в свою очередь могут быть переставлены двумя различными способами. Таким образом, общее количество составит 3 x 2 = 6 способов. В случае более длинного сообщения, например, из 10 букв, число возможных перестановок составит 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1. Такое произведение в математике записывается как 10! и дает число 3 628 800. В общем случае для сообщения из n букв существует n! различных способов изменить их порядок. Таким образом, скромное сообщение из 40 символов имеет так много способов изменения порядка букв, что это сообщение практически невозможно расшифровать вручную. Может быть, мы нашли идеальный криптографической метод? Не совсем так. По сути, алгоритм перестановочного шифрования обеспечивает высокий уровень безопасности, но как насчет ключа, который позволяет расшифровать сообщение? Случайность процесса составляет и его силу, и его слабость. Потребовался другой метод шифрования, чтобы генерировать ключи, которые были бы простыми и легкими для запоминания и передачи без потери уровня безопасности. Так начались поиски идеального алгоритма, и первые успехи в этом деле были достигнуты римскими императорами. * * *
Шифры подстановки разрабатывались параллельно с перестановочным шифрованием. В отличие от перестановочного шифрования, строгий шифр подстановки заме няет каждую букву или символ на какой-то другой. В отличие от перестановочного шифрования, шифр подстановки основывается не только на буквах, которые содержатся в сообщении. В перестановочном шифровании буква меняет свое положение, но сохраняет свою роль; одна и та же литера имеет одинаковое значение в исходном сообщении и в зашифрованном. В шифре подстановки буквы сохраняют свои позиции, но меняют роли (одна и та же буква или символ имеет в исходном сообщении одно значение, а в зашифрованном — другое). Одним из первых известных алгоритмов шифра подстановки был шифр Полибия, названный в честь греческого историка Полибия (203–120 гг. до н. э.), который оставил нам его описание. Об этом методе подробно рассказано в Приложении. Спустя примерно 50 лет после появления шифра Полибия, в I в. до н. э., возник другой шифр подстановки, известный под общим названием шифра Цезаря, потому что именно Юлий Цезарь использовал его для секретной переписки со своими генералами. Шифр Цезаря является одним из наиболее изученных в криптографии, и он очень полезен тем, что иллюстрирует принципы модульной арифметики, одной из математических основ кодированного письма. Шифр Цезаря заменяет каждую букву другой, находящейся в алфавите на некоторое фиксированное число позиций правее. Как писал великий историк Светоний в книге «Жизнь двенадцати цезарей», Юлий Цезарь использовал для своей личной переписки следующий алгоритм подстановки: каждая буква исходного сообщения сдвигалась по алфавиту на три позиции, а именно, буква А заменялась на D, В — на Е, и так далее. Буква W превращалась в Z, а X, Y и Z возвращались к А, В и С. * * *
Перестановочное шифрование
Во время конфликта между Афинами и Спартой для контроля над Пелопоннесом часто использовалась скитала — прибор, состоящий из цилиндра и обмотанной вокруг него по спирали узкой полоски бумаги, на которой писалось сообщение. Хотя используемый метод (то есть алгоритм шифрования) был известен противнику, не зная точных размеров скиталы, было чрезвычайно трудно расшифровать перехваченное сообщение. Толщина и длина скиталы были, в сущности, ключом к этой системе шифрования. После разматывания бумажной ленты прочитать сообщение было невозможно. На рисунке ниже передаваемое сообщение (М) выглядит так: A message encoded with a scytale («Сообщение, закодированное с помощью скиталы»), но после разматывания бумажной ленты сообщение превратилось в тарабарщину (С): anh mca eos sdc sey adt gwa eil ete. * * *
КРОШЕЧНЫЕ БУКВЫ В годы холодной войны герои шпионских триллеров часто использовали крошечные микрофильмы для пересылки сообщений, чтобы их было невозможно прочитать невооруженным глазом. Этот стеганографический метод, названный «микроточки», был разработан на несколько лет раньше, в Германии во время Второй мировой войны. Фотография текста сообщения уменьшалась до размеров точки, а затем прикреплялась к безобидному письму в качестве одного из многих типографских символов.* * *
Использование скиталы основано на криптографическом методе, известном как перестановочное шифрование, когда буквы сообщения переставляются местами. Чтобы получить представление о силе этого метода, рассмотрим простой пример перестановки всего трех букв: А, О и R. Быстрая проверка без каких-либо расчетов показывает, что они могут быть переставлены шестью различными способами: AOR, ARO, OAR, ORA, ROA и RAO. В абстрактных терминах процесс выглядит следующим образом: как только одна из трех возможных букв поставлена на первое место, что дает нам три различных возможности, остаются еще две буквы, которые в свою очередь могут быть переставлены двумя различными способами. Таким образом, общее количество составит 3 x 2 = 6 способов. В случае более длинного сообщения, например, из 10 букв, число возможных перестановок составит 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1. Такое произведение в математике записывается как 10! и дает число 3 628 800. В общем случае для сообщения из n букв существует n! различных способов изменить их порядок. Таким образом, скромное сообщение из 40 символов имеет так много способов изменения порядка букв, что это сообщение практически невозможно расшифровать вручную. Может быть, мы нашли идеальный криптографической метод? Не совсем так. По сути, алгоритм перестановочного шифрования обеспечивает высокий уровень безопасности, но как насчет ключа, который позволяет расшифровать сообщение? Случайность процесса составляет и его силу, и его слабость. Потребовался другой метод шифрования, чтобы генерировать ключи, которые были бы простыми и легкими для запоминания и передачи без потери уровня безопасности. Так начались поиски идеального алгоритма, и первые успехи в этом деле были достигнуты римскими императорами. * * *
РУКОВОДСТВО ДЛЯ МОЛОДЫХ ДАМ Камасутра — это пространное руководство, которое посвящено, среди прочего, тому, что необходимо знать каждой женщине, чтобы быть хорошей женой. Созданное около IV в. до н. э. брамином по имени Ватьсьяяна, оно рассказывает о 64 различных навыках, в том числе о музыке, кулинарии и шахматах. Особый интерес для нас имеет навык под номером 45, потому что он представляет собой искусство тайнописи, или млеччхита-викальпа. Древний мудрец рекомендует несколько методов, в том числе такой: разделить алфавит на две части и распределить буквы по парам случайным образом. В этой системе каждое соответствие пар представляет собой ключ. Например, один из ключей может быть следующим:
Чтобы написать тайное послание, нужно просто заменить каждую букву А в оригинальном тексте буквой Е, букву Р, соответственно, буквой С, J — буквой W, и так далее.
Кесарю кесарево
Veni, vidi, vici (пришел, увидел, победил). Юлий Цезарь
Шифры подстановки разрабатывались параллельно с перестановочным шифрованием. В отличие от перестановочного шифрования, строгий шифр подстановки заме няет каждую букву или символ на какой-то другой. В отличие от перестановочного шифрования, шифр подстановки основывается не только на буквах, которые содержатся в сообщении. В перестановочном шифровании буква меняет свое положение, но сохраняет свою роль; одна и та же литера имеет одинаковое значение в исходном сообщении и в зашифрованном. В шифре подстановки буквы сохраняют свои позиции, но меняют роли (одна и та же буква или символ имеет в исходном сообщении одно значение, а в зашифрованном — другое). Одним из первых известных алгоритмов шифра подстановки был шифр Полибия, названный в честь греческого историка Полибия (203–120 гг. до н. э.), который оставил нам его описание. Об этом методе подробно рассказано в Приложении. Спустя примерно 50 лет после появления шифра Полибия, в I в. до н. э., возник другой шифр подстановки, известный под общим названием шифра Цезаря, потому что именно Юлий Цезарь использовал его для секретной переписки со своими генералами. Шифр Цезаря является одним из наиболее изученных в криптографии, и он очень полезен тем, что иллюстрирует принципы модульной арифметики, одной из математических основ кодированного письма. Шифр Цезаря заменяет каждую букву другой, находящейся в алфавите на некоторое фиксированное число позиций правее. Как писал великий историк Светоний в книге «Жизнь двенадцати цезарей», Юлий Цезарь использовал для своей личной переписки следующий алгоритм подстановки: каждая буква исходного сообщения сдвигалась по алфавиту на три позиции, а именно, буква А заменялась на D, В — на Е, и так далее. Буква W превращалась в Z, а X, Y и Z возвращались к А, В и С. * * *
ГАЙ ЮЛИЙ ЦЕЗАРЬ (100-44 гг. до н. э.) Цезарь (на изображении справа) был военным и государственным деятелем, диктатура которого положила конец Римской республике. После службы в качестве магистрата в Дальней Испании он