Метод підстановки
Розглянемо, як зашифрувати повідомлення шляхом заміни (тобто - шляхом підстановки). Спочатку використовуємо шифр Цезаря. Припустимо, що потрібно зашифрувати повідомлення:
Як відомо, циклічний шифр Цезаря виходить заміною кожної літери відкритого тексту літерами цього ж алфавіту, розташованими попереду через кілька позицій, наприклад через три позиції. Циклічним він називається тому, що при виконанні заміни слідом за останньою літерою алфавіту знову слідує перша літера алфавіту. Запишемо фрагменти українського алфавіту та покажемо, як виконується шифрування:
В результаті проведеного перетворення вийде шифрограма:
У разі ключом є величина зсуву (число позицій між буквами). Число ключів цього шифру невелике (воно дорівнює літерам алфавіту). Не важко розкрити таку шифрограму перебором всіх можливих ключів.
Заміна може здійснюватися на символи іншого алфавіту та з більш складним ключем (алгоритмом заміни). Для простоти знову наведемо лише початкові частини абеток. Лінії показують порядок заміни букв українського алфавіту на букви латинського алфавіту.
В результаті такого шифрування вийде криптограма:
Раціональніше використаний в останньому випадку ключ записати у вигляді таблиці:
При шифруванні літери можуть бути замінені числами (у найпростішому випадку порядковими номерами літер алфавіту). Тоді наше шифрування виглядатиме так:
Заміна символів відкритого тексту може відбуватися на спеціальні символи, наприклад на "танцюючих чоловічків", як у оповіданні К.Дойля.
Довгі повідомлення, отримані методом одноалфавітної заміни (інша назва – шифр простої однолітерної заміни), розкриваються за допомогою таблиць відносних частот. Для цьогопідраховується частота появи кожного символу, поділяється на загальну кількість символів у шифрограмі. Потім з допомогою таблиці відносних частот визначається, яка було зроблено заміна при шифруванні.
Підвищити криптостійкість дозволяють багатоалфавітні заміни шифри (або шифри багатозначної заміни). При цьому кожному символу відкритого алфавіту ставлять у відповідність не один, а кілька символів шифрування.
Нижче наведено фрагмент багатоалфавітного ключа заміни.
За допомогою багатоалфавітного шифру повідомлення "ДЕ АББА" можна зашифрувати кількома способами:
10-99-15-12-4-14-12 і т.д.
Для кожної літери вихідного алфавіту створюється кілька символів шифрограми так, що множини кожної літери не містять однакових елементів. Багатоалфавітні шифри змінюють картину статистичних частот появи букв і цим ускладнюють розтин шифру без знання ключа.
Розглянемо ще один багатоалфавітний шифр заміни, описаний в 1585 році французьким дипломатом Блезом де Віженером. Шифрування проводиться за допомогою так званої таблиці Віженера. Тут, як і раніше, показано лише частину таблиці у тому, щоб викласти лише ідею методу.
Кожен рядок у таблиці відповідає одному шифру простої заміни (типу шифру Цезаря). При шифруванні повідомлення записують його в рядок, а під ним поміщають ключ. Якщо ключ виявляється коротшим за повідомлення, то ключ циклічно повторюють. Шифрування отримують, знаходячи символ у матриці букв шифрограми. Символ шифрограми знаходиться на перетині стовпця з буквою відкритого тексту та рядка з відповідною літерою ключа.
Припустимо, що потрібно зашифрувати повідомлення "ДЕ АББА". Як ключ виберемо слово "ДІВА". В результаті отримаємо:
В результаті перетворень вийде шифрування:
Розглянемо приклади шифрування повідомлення шляхом перестановки.
Ідея цього методу криптографії полягає в тому, що запис відкритого тексту та подальше зчитування шифрування проводиться по різних шляхах деякої геометричної фігури (наприклад, квадрата).
Для пояснення ідеї візьмемо квадрат (матрицю) 8х8, записуватимемо текст послідовно по рядках зверху вниз, а зчитуватимемо по стовпцях послідовно зліва направо.
Припустимо, що потрібно зашифрувати повідомлення:
"НА ПЕРШОМУ КУРСІ ТЯЖКО ВЧИТИСЯ ТІЛЬКИ ПЕРШІ ЧОТИРИ РОКИ ДЕКАНАТ".
У таблиці символом "_" позначено пробіл.
В результаті перетворень вийде шифрування: "НМТЧОРЫ_А_ЯИЛВРД_КЖТЬЫЕПУЕЬКЕ_КЕРЛСО_ГАР СОЯ_ЧОНВЕ__ПЕДАО_УТЕТАТ".
Ключем у разі є розмір матриця, порядок запису відкритого тексту і зчитування шифрограммы. Звичайно, що ключ може бути іншим. Наприклад, запис відкритого тексту по рядках може проводитися в такому порядку: 48127653, а зчитування криптограми може відбуватися по стовпцях у такому порядку: 81357642.
Методи заміни та перестановки окремо не забезпечують необхідну криптостійкість. Тому їх використовують спільно, а також у поєднанні з адитивним методом.
При шифруванні адитивним методом спочатку відкритий текст шифрують методом заміни, перетворюючи кожну букву на число, а потім до кожного числа додають секретну гаму (псевдовипадкову числову послідовність).
У ЕОМ перетворення відкритого тексту відбувається природним шляхом, оскільки кожен символ кодується двійковим числом. Вигляд цього перетворення залежить від операційної системи, що використовується. Для визначення будемо вважати, що відкрите повідомлення в ЕОМ кодується за допомогою кодової таблиці CP-1251 (операційнасистема Windows). Крім того, будемо вважати, що секретна гама додається до відкритого тексту за правилом додавання по модулю два без переносів у старші розряди (логічна операція Виключає АБО). Результати всіх перетворень помістимо до таблиці.
Для наочності результат шифрування переведено за допомогою таблиці CP-1251 у літери.
З таблиці видно, що вихідний текст був записаний великими літерами, а криптограма містить як великі, так і малі літери. Природно, що з реальному (а чи не навчальному) шифруванні набір символів у шифрограмі буде ще багатшим. Крім українських літер будуть присутні латинські літери, розділові знаки, керуючі символи.