Криптография. Шифр Цезаря и шифр Виженера

Криптография, наука о шифровке и дешифровке информации… На самом деле наука о шифровке посланий существовала задолго до компьютерных времён. Разнообразную тайнопись использовали ещё армии Римской Империи для передачи секретных сообщений. Сейчас наука набрала обороты, и ею пользуются все. Скажем, ваши пароли в Facebook и других социальных сетях хранятся в зашифрованном виде. 

Теоретические сведения

Для начала мы изучим один из простейших шифров — шифр Цезаря, названный в честь римского императора. В этом шифре каждая буква текста заменяется на другую, которая находится на фиксированное число букв дальше в алфавите. Это фиксированное число букв называется ключом. Так, ключ 1 переводит букву латиницы C в букву D, а Z — по циклу в A. Если ключ равен 3, то буква C перейдет в F, а Z — в C. 

Примеры: используем шифр Цезаря с ключом 5 на слове cat.

c -> h
a -> f
t -> y 
Caesar (cat, 5) = hfy

Ключ = 7, слово = computer

c->j
o->v
m->t
p->w
u->b
t->a
e->l
r->y
Caesar(computer,7) = jvtwbaly

Шифр Цезаря прост, но, увы, ненадёжен (это взаимосвязанные вещи!): для английского алфавита — всего 25 вариантов шифровки, перебрать все возможные варианты легко даже без компьютера. Тем не менее, шифр Цезаря часто используют в качестве шага в других шифрах, таких, как шифр Виженера (о нём — в следующем пункте).

«Математизируем» шифр Цезаря. Обозначим незашифрованный текст буквой p, а pi — буква в тексте p, которая находится на позиции с номером i. Назовем секретный ключ буквой k, с — зашифрованный текст, а ci — буква в шифрованном тексте, которая находится на позиции i. Тогда вычислить каждую букву шифра можно по формуле: 

ci = (pi + k) % 26

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

Если ключ k = 13 а изначальный текст p — «Be sure to drink your Ovaltine!», вот какой шифр мы получим:

Or fher gb qevax lbhe Binygvar!

Обратите внимание, O (первая буква в шифрованном тексте) смещена на 13 позиций от буквы B (первая буква в оригинальном тексте). То же самое с буквой r (вторая буква в шифровке) смещена на 13 букв от e (вторая буква в оригинале). Третья буква в шифровке, f, смещена на 13 букв от s (третья в оригинале), тут мы ходим по кругу от z до a.

Шифр Цезаря с ключом 13 имеет специальное название ROT13. Он симметричный: применив его дважды, мы вернемся к изначальному тексту. Конечно, есть еще и ROT26, этот вообще супер-секьюрный, но только если вы нечётко выражаете свои мысли =). 

Шифр Виженера

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

Пример:

p = Meet me in the park at eleven am 
В качестве ключевого слова возьмем 
k = bacon
Длина сообщения p = 25 
В то время как длина k = 5 
Поэтому его нужно повторять 5 раз.

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

Чтобы найти значение для смещения, используем позиции каждой буквы нашего ключа bacon в алфавите (от a до z). Считаем с нуля, как истинные программисты. И каждую букву в оригинальном тексте смещаем на заданное число, как в шифре Цезаря, возвращаясь при надобности после Z в начало алфавита. Таким образом, M сместится на 1, первая e вообще не сместится, а вторая сместится на 2 позиции. Ниже вы видите изначальное сообщение, расписанный ключ и результат его применения.

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

Также можно использовать полный перебор, но вариантов немало: 26^n – 1 где n — длина неизвестного ключа. Но обычно это немало. Правда, для компьютера это не проблема.

А теперь — математика шифра:

Пусть р – некоторый текст, k — ключевое слово, kj — j-я буква ключа, pi — буква под номером i в оригинальном тексте, ci — буква под номером i в шифровке. Тогда:

ci = (pi + kj) % 26