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 значень, так як ключ складається з цифр. Оскільки широко відомі алфавіти - російська, англійська і т.д. - зазвичай складаються з декількох десятків символів, шифр Віженера явно міцніше товариша свого при однаковому числі символів в ключі.
Для любителів незрозумілих слів: шифр Цезаря можна вважати окремим випадком шифру Віженера. Але при цьому шифр Цезаря - шифр простої заміни, а шифр Віженера - шифр складної заміни (якщо завгодно, багатоалфавітний шифр).
Для любителів незрозумілих слів: шифр Цезаря можна вважати окремим випадком шифру Віженера. Але при цьому шифр Цезаря - шифр простої заміни, а шифр Віженера - шифр складної заміни (якщо завгодно, багатоалфавітний шифр).
Немає коментарів:
Дописати коментар