При вивченні цього шифру корисно також прочитати про шифр Віженера
Загальна ідея
У класичній криптографії досить популярним фокусом є так звана послідовність зрушень. Якщо в ній n елементів (n> 1), то кожен k-ий символ відкритого тексту зсувається на те ж число позицій в алфавіті, що і (k + n) -ий. Шифр Гронсфельда теж використовує цей маневр.
Наприклад, є послідовність {1, 3} (тобто n = 2), тоді перший, третій, п'ятий і інші непарні символи заміняться на наступні за алфавітом. Другий, четвертий і так далі - на ті, які стоять на 3 позиції пізніше за алфавітом. Нумерація символів в алфавіті ведеться з нуля, формула зсуву на q позицій: c = (s + q) mod N, де s - номер символу відкритого тексту в алфавіті, c - номер в алфавіті символу шифрованого тексту, N - кількість символів в алфавіті.
Візьмемо ту ж {1, 3} для прикладу: російський алфавіт (включаючи Е) + пробіл, текст: ЦЕ М'ЯЧ. Замість Е в шифртексту буде Ю, замість Т - Х (порядок: ТУФХ, зрушення на 3 позиції), замість О - П, оскільки П - наступна після О. Пропуск у нас 33-ій (34 символу, нумерація з нуля). Тоді зсув на 3 позиції робиться так: (33 + 3) mod 34 = 36 mod 34 = 2. Оскільки нумеруем з нуля, буде В. Ну далі, напевно, і так всім зрозуміло ...
Підсумок: ЮХПВНБШ. Тобто знову якесь місиво ...
Зауважте: якщо поміняти порядок символів в алфавіті, результат може помінятися.
І ще один важливий момент: якщо кожне число в послідовності може приймати значення від 0 до K-1, де K> 2, то кількість можливих послідовностей довжини n становить НЕ K ^ n (^ - значок ступеня). Як мінімум безглузда всяка послідовність типу {1, 1, 1} або {4, 4}, хоч якісь елементи послідовності повинні відрізнятися.
Різні шифри, які використовують цю гидоту, відрізняються тим, як ці набори зрушень пов'язані з ключем і який вигляд мають ключі. Так, в шифрі Віженера ключ - набір букв, числа отримуємо як номери букв з ключа. Наприклад, російський алфавіт, ключ АВ, тоді набір чисел: {0, 2}.
У нашому шифрі ключ - відразу послідовність цифр (але не чисел!). Яка цифра - на стільки й зрушує. У прикладі з тестом про м'яч ключем шифру Гронсфельда був би 13, Віженера - БГ. Тобто ключі шифру Гронсфельда - числові, шифру Віжерена - літерні, причому зазвичай все-таки у вигляді нормальних людських слів.
Наприклад, є послідовність {1, 3} (тобто n = 2), тоді перший, третій, п'ятий і інші непарні символи заміняться на наступні за алфавітом. Другий, четвертий і так далі - на ті, які стоять на 3 позиції пізніше за алфавітом. Нумерація символів в алфавіті ведеться з нуля, формула зсуву на q позицій: c = (s + q) mod N, де s - номер символу відкритого тексту в алфавіті, c - номер в алфавіті символу шифрованого тексту, N - кількість символів в алфавіті.
Візьмемо ту ж {1, 3} для прикладу: російський алфавіт (включаючи Е) + пробіл, текст: ЦЕ М'ЯЧ. Замість Е в шифртексту буде Ю, замість Т - Х (порядок: ТУФХ, зрушення на 3 позиції), замість О - П, оскільки П - наступна після О. Пропуск у нас 33-ій (34 символу, нумерація з нуля). Тоді зсув на 3 позиції робиться так: (33 + 3) mod 34 = 36 mod 34 = 2. Оскільки нумеруем з нуля, буде В. Ну далі, напевно, і так всім зрозуміло ...
Підсумок: ЮХПВНБШ. Тобто знову якесь місиво ...
Зауважте: якщо поміняти порядок символів в алфавіті, результат може помінятися.
І ще один важливий момент: якщо кожне число в послідовності може приймати значення від 0 до K-1, де K> 2, то кількість можливих послідовностей довжини n становить НЕ K ^ n (^ - значок ступеня). Як мінімум безглузда всяка послідовність типу {1, 1, 1} або {4, 4}, хоч якісь елементи послідовності повинні відрізнятися.
Різні шифри, які використовують цю гидоту, відрізняються тим, як ці набори зрушень пов'язані з ключем і який вигляд мають ключі. Так, в шифрі Віженера ключ - набір букв, числа отримуємо як номери букв з ключа. Наприклад, російський алфавіт, ключ АВ, тоді набір чисел: {0, 2}.
У нашому шифрі ключ - відразу послідовність цифр (але не чисел!). Яка цифра - на стільки й зрушує. У прикладі з тестом про м'яч ключем шифру Гронсфельда був би 13, Віженера - БГ. Тобто ключі шифру Гронсфельда - числові, шифру Віжерена - літерні, причому зазвичай все-таки у вигляді нормальних людських слів.
Приклади по шифру Гронсфельда
Невеликий приклад по шифру Гронсфельда.
Припустимо, є англійський алфавіт, шифруємо текст SOURCE, ключ - 1422. S міняємо на наступний за алфавітом символ, тобто T, O - на той, що на 4 позиції далі в алфавіті, тобто S (порядок OPQRS), U і R зрушуємо на 2 позиції, отримуючи W і T. Тепер знову починаємо з першої цифри і міняємо C на D. Далі беремо другу цифру і міняємо E на I. Підсумок - TSWTDI.
Тепер ще приклад по шифру Гронсфельда. Є англійські символи + ще пробіл, зашіфруем SOURCE CODE (переклад - "вихідний код"). Перші 6 символів шифрованого тексту як і раніше будуть TSWTDI, як в прикладі з слово SOURCE і алфавітом без пробілу. При цьому ми застосували один раз всі цифри ключа +1422, також довелося вдруге задіяти 1 і 4.
Далі за алгоритмом шифру Гронсфельда задіємо двійку. На черзі пробіл, він 26-ій, якщо A - символ номер 0. (26 + 2) mod 27 = 1, тобто замість пробілу ставимо B. Тепер C і друга двійка в ключі. Якщо A - номер 0, то C - номер 2. (2 + 2) mod 27 = 4, тобто це E. Далі шифруємо O, всі цифри ключа використані, знову починаємо зі старшою (найлівішій) цифри, тобто потрібен зсув на 1, замість O буде P. І так далі ...
Припустимо, є англійський алфавіт, шифруємо текст SOURCE, ключ - 1422. S міняємо на наступний за алфавітом символ, тобто T, O - на той, що на 4 позиції далі в алфавіті, тобто S (порядок OPQRS), U і R зрушуємо на 2 позиції, отримуючи W і T. Тепер знову починаємо з першої цифри і міняємо C на D. Далі беремо другу цифру і міняємо E на I. Підсумок - TSWTDI.
| Алфавіт: ABCDE...XYZ | ||||||
| Відкрмтмй текст | S | O | U | R | C | E |
| Застосування ключа | 1 | 4 | 2 | 2 | 1 | 4 |
| Шифрованний текст | T | S | W | T | D | I |
Тепер ще приклад по шифру Гронсфельда. Є англійські символи + ще пробіл, зашіфруем SOURCE CODE (переклад - "вихідний код"). Перші 6 символів шифрованого тексту як і раніше будуть TSWTDI, як в прикладі з слово SOURCE і алфавітом без пробілу. При цьому ми застосували один раз всі цифри ключа +1422, також довелося вдруге задіяти 1 і 4.
Далі за алгоритмом шифру Гронсфельда задіємо двійку. На черзі пробіл, він 26-ій, якщо A - символ номер 0. (26 + 2) mod 27 = 1, тобто замість пробілу ставимо B. Тепер C і друга двійка в ключі. Якщо A - номер 0, то C - номер 2. (2 + 2) mod 27 = 4, тобто це E. Далі шифруємо O, всі цифри ключа використані, знову починаємо зі старшою (найлівішій) цифри, тобто потрібен зсув на 1, замість O буде P. І так далі ...
| Алфавіт: ABCDE...XYZ_ | |||||||||||
| Відкритий текст | S | O | U | R | C | E | _ | C | O | D | E |
| Застосування ключа | 1 | 4 | 2 | 2 | 1 | 4 | 2 | 2 | 1 | 4 | 2 |
| Шифрованний текст | T | S | W | T | D | I | B | E | P | H | G |
Найцікавіший приклад
Тепер знову англійська з пропуском, але текст: MY FAT CAT, ключ: 143.
Підсумок такий:
Даний приклад застосування шифру Гронсфельда - яскрава демонстрація того, як шифри складної заміни затирають статистику входження символів у відкритий текст. Якби у нас був шифр простої заміни, то однакові символи замінилися б однаково. Особливо негативно це позначилося б на прогалинах: дуже часто зустрічається символ шифрованого тексту - напевно "маска" пробілу. За шифру Гронсфельда в нашому прикладі прогалини замінені по-різному.
Такі самі символи в зашифрованому тексті не говорять про частоту символів у відкритому тексті: в табличці вище, наприклад, два різних символу F і C в результаті замінилися одним і тим же G.
Підсумок такий:
| Алфавіт: ABCDE...XYZ_ | ||||||||||
| Відкритий текст | M | Y | _ | F | A | T | _ | C | A | T |
| Застосування ключа | 1 | 4 | 3 | 1 | 4 | 3 | 1 | 4 | 3 | 1 |
| Шифрованний текст | N | B | C | G | E | W | A | G | D | U |
Даний приклад застосування шифру Гронсфельда - яскрава демонстрація того, як шифри складної заміни затирають статистику входження символів у відкритий текст. Якби у нас був шифр простої заміни, то однакові символи замінилися б однаково. Особливо негативно це позначилося б на прогалинах: дуже часто зустрічається символ шифрованого тексту - напевно "маска" пробілу. За шифру Гронсфельда в нашому прикладі прогалини замінені по-різному.
| Алфавіт: ABCDE...XYZ_ | ||||||||||
| Відкритий текст | M | Y | _ | F | A | T | _ | C | A | T |
| Застосування ключа | 1 | 4 | 3 | 1 | 4 | 3 | 1 | 4 | 3 | 1 |
| Шифрованний текст | N | B | C | G | E | W | A | G | D | U |
Такі самі символи в зашифрованому тексті не говорять про частоту символів у відкритому тексті: в табличці вище, наприклад, два різних символу F і C в результаті замінилися одним і тим же G.
Бійка з конкурентом
Раніше не дарма була згадка шифру Віженера. Як вже могли помітити мислячі істоти, ця два шифру звірячому схожі! Чи не здивуємося, якщо їх автори були товаришами по чарці! Ідея у них одна і описана в самому початку цієї сторінки. Різний же вид ключів. У шифрі Віженера символи ключа беруться з ТОГО Ж алфавіту, що і символи відкритого тексту. Це означає, що якщо у алфавіту більше 10 символів, то шифр Віженера надійніше - адже в шифрі Гронсфельда кожен зрушення можна вибрати тільки 10 способами. Хіба що одне тут є підступ - народ не любить паролі, ключі і т.д. у вигляді незрозумілих наборів букв, тому ключами шифру Віженера вибираються зазвичай нормальні слова людської мови, а не з лексикону п'яних тролів. А це сильно скорочує кількість можливих ключів.
Нарешті, ще один момент. Якщо в алфавіті є цифри, і ключем шифру Віженера виявився набір цифр, шифр Віженера не змінює свої правила і не перетворюється таємничим чином в шифр Гронсфельда. Не шукайте містики в настільки суворому справі, як алгоритми.
Нарешті, ще один момент. Якщо в алфавіті є цифри, і ключем шифру Віженера виявився набір цифр, шифр Віженера не змінює свої правила і не перетворюється таємничим чином в шифр Гронсфельда. Не шукайте містики в настільки суворому справі, як алгоритми.
Немає коментарів:
Дописати коментар