Шифр Виженера
А также шифр Цезаря
1. Алгоритм шифра Виженера с примерами
Есть такой шифр - шифр Цезаря. Это частный
случай аффинной системы подстановок. Суть шифра Цезаря - каждый символ текста заменяется на некоторый другой,
причём одинаковые символы заменяются одинаково. Если данный символ - k-ый в N-символьном алфавите,
то он заменяется (k + C) mod N - ым символом алфавита. Нумерация символов начинается с нуля -
не очень привычно для не прогеров, но что поделать... Здесь C - ключ шифра.
Допустим, C = 2, алфавит русский. Зашифруем слово ЯМА. Буква Я имеет номер 32 (не 33, хотя мы не убивали букву Ё).
(32 + 2) mod 33 = 1, то есть берём букву Б (внимание: буква А имеет нулевой номер). Буква М заменяется на то,
что стоит в алфавите на две позиции справа. Для всех адекватных людей это буква О. Буква А заменяется, как уже
можно было додуматься, на В. Болучается шифртекст БОВ. Хорошо, хоть не боров!
Другое дело, что вряд ли Цезарь додумался бы до такого примера, но он и прогать-то не умел. А также
не знал нормального русского языка и компах ничего не понимал.
К чему эта вся ерунда? Зададимся вопросом. А что, если взять несколько ключей C и циклически их применять?
Например, первый символ сдвигать на 1 позицию, второй вообще не сдвигать, третий сдвигать на 3, четвёртый -
снова на 1, пятый не сдвигать. Ну и так далее, пока всё не зашифруем. То как раз-таки и будет шифр Виженера.
Только обычно ключ задают не группой чисел (в только что выданном примере был бы набор {1, 0, 3}), а
в виде слова. Вместо каждой C записывается символ, который стоит C-ым в алфавите (нумерация опять с нуля).
То есть вместо {1, 0, 3} ключом мы пишем слово БАГ (А - символ номер 0, Б - 1, Г - 3). Итак,
в шифре Виженера мы имеем дело с последовательностью сдвигов, циклически повторяющейся.
Теперь примерчик по шифру Виженера. Алфавит - русский. Пусть ключевым словом является БАГ (программисты меня поймут). Зашифруем слово ВЕДРО.
В сдвигаем на 1 позицию, получаем Г.
Е никуда не сдвигаем и вообще оставляем в покое.
Д сдвигаем на 3 позиции. Если не дискриминировать букву Ё, вместо Д будет Ж.
Р меняется на С - то есть следующую по алфавиту букву.
О остаётся на месте.
ВЕДРО превращается в ГЕЖСО.
| Алфавит: АБВ...ЕЁЖ...Я | |||||
| Открытый текст | В | Е | Д | Р | О |
| Применение ключа | Б | А | Г | Б | А |
| Сдвиг | 1 | 0 | 3 | 1 | 0 |
| Шифрованный текст | Г | Е | Ж | С | О |
Такой ключ чисто для простоты примера, вообще не очень хорошо, когда ключ короткий, и при том часть букв ещё и не сдвигается. В приведённом примере по сути поочерёдно брались 3 правила цифра Цезаря. Другое дело, что этот фокус придумал явно не он, даже по названию шифра ясно.
Теперь покажем шифр Виженера на примере помудрёнее. Русский алфавит плюс пробел (34 символа в итоге), ключ БЕГ, шифруем текст МЫ ЗА РОДИНУ.
| Алфавит: АБВ...ЕЁЖ...Я_ | ||||||||||||
| Открытый текст | М | Ы | _ | З | А | _ | Р | О | Д | И | Н | У |
| Применение ключа | Б | Е | Г | Б | Е | Г | Б | Е | Г | Б | Е | Г |
| Сдвиг | 1 | 5 | 3 | 1 | 5 | 3 | 1 | 5 | 3 | 1 | 5 | 3 |
| Шифрованный текст | Н | _ | В | И | Е | В | С | У | Ж | Й | Т | Ц |
Сначала текущий символ ключа - Б (сдвиг 1), потому М сдвигаем на 1 и получаем Н. Потом берём символ ключа Е (сдвиг 5) и применяем к Ы (символ номер 28, если А считать нулевым), (28 + 5) mod 34 = 33, то есть получаем пробел. Теперь на очереди символ ключа Г (сдвиг 3), шифруем пробел (номер 33): (33 + 3) mod 34 = 2, то есть это В, ибо А имеет номер 0. Далее опять переходим к началу ключа, то есть Б (сдвиг 1). Шифруем З, меняя на следующую букву (так как сдвиг = 1). В итоге получаем И. И так далее.
Шифр Виженера тем сильнее, чем длиннее ключ, меньше в нём символов номер ноль, больше символов в алфавите.
Если все символы ключа одинаковые, то это совсем слабый ключ, а шифр Виженера вырождается в шифр Цезаря.
А как же расшифровывать? Если верно, что q = (k + C) mod N, то k = (q - C + N) mod N. Здесь k - номер текущего символа открытого текста в алфавите, С - текущий сдвиг из нашего ключевого набора, q - номер полученного символа шифртекста в алфавите, N - количество символов в алфавите, нумеруемом с нуля. И так для каждого символа.
А что делать, если в тексте есть пробелы? Или заменить их чем-то, или включить в алфавит. Так же можно сделать со всем знаками препинания.
2. Аналоги и частный случай шифра Виженера
Шифр Виженера во многом сходен с шифром Гронсфельда. При этом в шифре Гронсфельда каждый символ ключевого слова может принимать одно из 10 значений, так как ключ состоит из цифр. Поскольку широко известные алфавиты - русский, английский и т.д. - обычно состоят из нескольких десятков символов, шифр Виженера явно крепче товарища своего при одинаковом числе символов в ключе.