Криптографічні системи
1.КРИПТОГРАФІЧНІ СИСТЕМИ, ОСНОВАНІ НА МЕТОДІ ПІДСТАНОВКИ
Криптографічні системи, засновані на методі підстановки, поділяються на чотири основні класи:
У системах класу monoalphabetic символ вихідного тексту замінюється іншим символом таким чином, що між ними існує однозначна відповідність. Тобто, кожен символ вихідного тексту однозначно замінюється його підстановкою. Криптографічним ключем такої системи є таблиця відповідності вихідного алфавіту алфавіту підстановки. Наприклад, для англійської алфавіту існує 26! = 4 * 1026 різних криптографічних систем першого класу. Найбільш прості системи цього класу припускають аналітичний опис підстановок. Так, найпростіший шифратор, заснований на принципі підстановки, зсуває кожну букву англійського алфавіту на k позицій, де є ключем шифру. У так званому алгоритмі Цезаря i-я літера алфавіту замінюється (i+k)-ю літерою за модулем 26. Юлій Цезар використовував подібну систему для k=3. Аналітично криптосистема Цезаря описується виразом
Ek(i) = (i+k) mod 26. (1.1)
Наприклад, відповідно до наведеного виразу буква A вихідного англійського алфавіту, що має номер i=0, замінюється буквою D, що має номер (i+k) mod 26 = (0+3) mod 26 = 3, а буква z (i=25 ) замінюється буквою C, що має номер (i+k) mod 26 = (25+3) mod 26 = 2. Наступний приклад ілюструє алгоритм шифрування Цезаря:
Вихідний текст: CRYPTOGRAPHYANDDATASECURITY.
Алгоритм дешифрування має вигляд
Dk(i) = (i+26-k) mod 26. (1.2)
Існують складніші методи підстановки. Шифратори, засновані на множенні номера кожного символу вихідного тексту значення ключа k, описуються таким отношением:
Ek(i) = (i*k) mod n, (1.3)
де i – номер символу вихідного тексту, n – кількість символів у вихідному алфавіті (n=26 для англійського алфавіту та n=256 для ASCII-кодів), k – ключ, n та k повинні бути взаємно простими.
Шифратори, засновані на зсуві та множенні, описуються виразом
Ek(i) = (i*k1+k0) mod n. (1.4)
Будь-який шифратор класу monoalphabetic може бути представлений у вигляді поліноміального перетворення порядку t:
Ek(i) = (k0 + k1 * i + k2 * i2 +. + kt-1 * it-1 + kt * it) mod n. (1.5)
Алгоритм Цезаря поліноміальним перетворенням нульового порядку.
У криптографічних системах класу homophonic є кілька варіантів заміни вихідного символу. Наприклад, буква A може бути замінена цифрами 24, 35, 37, а буква B - цифрами 41, 17, 76. Тоді слово ABBA може бути зашифроване як (37, 17, 76, 24), або (35, 41, 76, 37) і т. д. Подібні системи характеризуються значно більшою криптографічною стійкістю, ніж системи класу homophonic.
Криптографічні системи класу polyalphabetic засновані на використанні декількох різних ключів. Більшість шифраторів подібного типу є періодичними періодом P. Вихідний текст виду
X = x1 x2 x3 x4. xp xp+1. x2p.
шифрується за допомогою ключів k1, k2, . kp:
Ek(X)= Ek1(x1) Ek2(x2) . Ekp(xp) Ek1(xp+1) . Ekp(x2p) (1.6)
Для p=1 матимемо шифр класу моноалфабетичного.
Один із таких алгоритмів був запропонований у XVI столітті французом Вігеном (Vigenere).
У цьому випадку ключ K є послідовністю
де ki (1 Å ak ai-k, k = 0,1,2., (2.1)
де k – номер такту; ak
Властивості послідовності, що генерується, визначаються постійними коефіцієнтами ai. Їх можна досліджувати, аналізуючихарактеристичний поліном
g(x) = 1 Å a1 x Å a2 x2Å. Å am-1 xm-1 Å am xm.
При відповідному виборі коефіцієнтів генерована послідовність < ai буде мати максимально можливий період, рівний 2m-1, де m - розрядність зсувного регістру і одночасно старший ступінь породжуючого полінома. Послідовність максимально можливого періоду називається M-послідовністю. Основне завдання синтезу генератора аналізованого типу - знаходження характеристичного полінома, що формує М-послідовність.
Поліноми, що формують послідовність максимального періоду, називаються примітивними. Зі зростанням m їх кількість стає дуже великою. Серед множини примітивних поліномів ступеня m можна знайти поліноми з найменшим числом одиничних коефіцієнтів ai. Генератори, побудовані з їхньої основі, мають найпростішу технічну реалізацію. У табл. 2.1 наведено перелік поліномів з мінімальною кількістю ненульових коефіцієнтів для значень m 3 Å x 4 наведена на рис. 2.2; його робота показана у табл. 2.2.
Для формування M-послідовності поряд з примітивним поліномом g(x) може використовуватися і зворотний поліном g -1 (x)=x m g(x -1 ). Отримана у разі послідовність максимальної довжини буде інверсної стосовно послідовності, формованої g(x). Наприклад, для полінома g(x)=1Åx 3 Åx 4 зворотним поліномом буде g -1 (x) = x 4 (1Åx -3 Åx -4 )=1 Å x Å x 4 .
Головна перевага описуваного методу формування псевдовипадкових послідовностей – простота його реалізації. Генератор M-послідовності містить лише m-розрядний регістр зсуву і набір суматорів за модулем два ланцюга зворотного зв'язку. Регістр зсуву виконує функції зберігання m біт M-послідовності та зсуву m-розрядногокоду на один розряд праворуч. Суматори за модулем два обчислюють чергове значення молодшого розряду зсувного регістру.
Стан розрядів регістру кожному такті можна як m-мірних векторів A(k)=a1 (k)a2 (k)a3 (k). am(k), де k=0,1,2. - Номер такту, ai (k) - стан i-го розряду, i = 1, m,
Послідовне застосування співвідношень (1) або (2) для s = 0 дозволяє формувати відповідно одно-або багаторозрядні псевдовипадкові послідовності, які характеризуються рядом статичних властивостей.
Розглянемо найважливіші властивості М-послідовностей.
1. Період послідовності, що описується виразом (1), визначається старшим ступенем породжуючого полінома g(x) і дорівнює L = 2 m -1.
2. Для заданого полінома g(x) існує L різних M-послідовностей, що відрізняються фазовим зсувом. Так, поліному g(x)=1Åx 3 Åx 4 відповідає 15 M-послідовностей.
3. Кількість одиничних та нульових символів ak, k = 0,1. L-1, M-послідовності відповідно дорівнює 2 m-1 та 2 m-1 -1. Імовірнісна оцінка частоти їхньої появи визначається такими виразами: