7. Перестановочні шифри. Статистичні властивості криптограм перестановок.

Цей метод полягає в тому, що символи шифруємого тексту переставляються за певними правилами всередині шифруємого блоку символів.

Шифрування простою перестановкою.

• вибирається ключове слово з символами, які не повторюються;

• шифруємий текст записується послідовними рядками під символами ключового слова;

• зашифрований текст виписується колонками в тій послідовності, в якій розташовуються в алфавіті літери ключа (або в порядку проходження цифр у натуральном ряду, якщо він цифровий)

Недоліком шифрування простою перестановкою обумовлюється тим, при великій довжині шифруємого тексту в зашифрованому тексті можуть проявитися закономірності символів ключа. Для усунення цього недоліку можна міняти ключ після зашифровки певної кількості знаків. При досить частій зміні ключа якість шифрування можна істотно підвищити. При цьому, однак, ускладнюється організація процесу шифрування і дешифрування.

Ускладнений метод перестановки за таблицями

Ускладнений метод перестановки за таблицями полягає в тому, що для запису символів шифруємого тексту використовується спеціальна таблиця, в яку введено деякі ускладнюють елементи. Таблиця являє собою матрицю, розміри якої можуть бути обрані довільно (наприклад 10 х 10). У неї, як і у випадку простої перестановки, записуються знаки шифруємого тексту. Ускладнення полягає в тому, що певна кількість клітин таблиці не використовується. Кількість і розташування невикористовуваних елементів є додатковим ключем шифрування. Шифруємий текст блоками по mxn - S елементів записується в таблицю (mxn - розміри таблиці, S - кількість невикористовуваних елементів). Далі процедура шифрування аналогічна простий перестановці.

Варіюючи розмірами таблиці, послідовністю символів ключа, кількістю і розташуванням невикористовуваних елементів, можна отримати необхідну стійкість зашифрованого тексту.

Ускладнений метод перестановок за маршрутами

Дуже високу стійкість шифрування можна забезпечити, використовуючи ускладнений метод перестановок за маршрутами типу Гамільтонівського. При цьому для запису символів шифруємого тексту використовуються вершини деякого гіперкуба, а знаки зашифрованого тексту зчитуються за маршрутами Гамільтона, причому використовується кілька різних маршрутів.

Слід зауважити, що всі процедури шифрування і розшифровки за методом перестановки є достатньою мірою формалізованим і можуть бути реалізовані алгоритмічно.

8. Методи генерації псевдовипадкових послідовностей.

Одноразовий блокнот представляат собою дуже довгу послідовність випадкових чисел. Цей блокнот створюється у двох примірниках, один з яких знаходиться у відправника повідомлення. А інший - у його одержувача. Відправник здійснює складання кодів символів повідомлення і випадкової послідовності. Отриманий результат він відправляє одержувачу. Наприклад, відповідно до кодуванням американським стандартним кодом для обміну інформацією слово «Вузол» представляється чотирма числами: 147 167 165 171. Випадкова послідовність видала числа:

342 076 543 132. У результаті додавання за числах першого і другого отриманий результат:

489 243 708 303. Цей результат пересилається одержувачу. Провівши з результату посимвольної віднімання чисел випадкової послідовності одержувач визначає код посланого слова. До сказаного слід додати, що для спрощення викладу вище використовувалися десяткові числа, хоча в реальності програми працюють з двійковими числами.

М-послідовності

Широке поширення отримали генератори на основі зсувного регістра з лінійними зворотними зв'язками. Вони описуються наступним відношенням:

a_i = ^a_k a_i-k, k=0,1,2,... , (2.1)

де k - номер такту; ak {0,1} - біти формованої послідовності; a_i {0,1} - постійні коефіцієнти; ^ - операція підсумовування за модулем 2. Генератор, описуваний відношенням (2.1), показаний на рис. 2.1.

Властивості генерується послідовності визначаються постійними коефіцієнтами a_i. Їх можна дослідити, аналізуючи характеристичний поліном

g(x) = 1  a₁ x  a₂ x² ... a_m-1 x^m-1  a_m x^m.

При відповідному виборі коефіцієнтів генерується послідовність {a_i} буде мати максимально можливий період, рівний 2m-1, де m - розрядність зсувного регістра і одночасно старша ступінь породжує полінома. Послідовність максимально можливого періоду називається M-послідовністю. Основна задача синтезу генератора розглянутого типу - знаходження характеристичного полінома, що формує М-послідовність.

Поліноми, що формують послідовність максимального періоду, називаються примітивними. Зі зростанням m їх кількість стає дуже великим. Серед безлічі примітивних поліномів ступеня m можна знайти поліноми з найменшим числом одиничних коефіцієнтів a_i. Генератори, побудовані на їх основі, мають найбільш просту технічну реалізацію. У табл. 2.1 наведено перелік поліномів з мінімальною кількістю ненульових коефіцієнтів для значень m <= 16.

Для формування M-послідовності поряд з примітивним поліномом g (x) може використовуватися і зворотний йому поліном g^-1(x)=x^mg(x^-1). Отримана в цьому випадку послідовність максимальної довжини буде інверсної по відношенню до послідовності, що формується g (x). Наприклад, для полінома g(x)=1x³x⁴ зворотнім поліномом буде g^-1(x) = x⁴(1x^-3x^-4 )=1  x  x⁴ .

Головна перевага описуваного методу формування псевдовипадкових послідовностей - простота його реалізації. Генератор M-послідовності містить лише m-розрядний регістр зсуву та набір суматорів за модулем два в ланцюзі зворотного зв'язку. Регістр зсуву виконує функції зберігання m біт M-послідовності і зсуву m-розрядного коду на один розряд вправо. Суматори за модулем два обчислюють чергове значення молодшого розряду сдвигового регістру.

Стан розрядів регістра на кожному такті можна представити у вигляді m-мірних векторів A(k)=a₁(k)a₂(k)a₃(k)...a_m(k), де k=0,1,2,... - номер такту, a_i(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³x⁴ відповідає 15 M-послідовностей.

3. Кількість одиничних і нульових символів a_k, k=0,1,..., L-1, M- послідовності відповідно дорівнює 2^m-1 и 2^m-1 -1. Ймовірна оцінка частоти їх появи визначається наступними виразами:

p(a_k=1)=2^m-1 /(2^m-1)=1/2 + 1/(2^m+1-2),

p(a_k=0)=(2^m-1-1)/(2^m-1) = 1/2-(2^m+1 -2)

і при збільшенні m досягає значень, як завгодно близьких до 1/2.

4. Ймовірності появи серій з r, r {1,2,...,m-1}, однакових символів (нулів чи одиниць) в M-послідовності максимально близькі до відповідних ймовірностями для випадкової послідовності.

5. Для будь-якого значення s ( 1 s<L ) існує таке r s ( 1 r<L), що {a_k} + {a_k-s}={a_k-r}. Дана властивість зазвичай називають властивістю зсуву і складення.

Використання лінійних зсувних регістрів для створення криптосистем передбачає їх вразливість, якщо зломщик має парою: вихідний текст - шифротекст довжиною не менше 2m бит. Дійсно, маючи вихідний текст M=(m₁,m₂,...,m_2m) і відповідний шифротекст C=(c₁,c₂,...,c_2m), ми можемо отримати К=MC=(m₁c₁,m₂c₂,...,m_2mc_2m)=(k₁,k₂,k₃,...,k_2m). Тоді завдання злому криптосистеми при відомому початковому стані зводиться до розв'язання системи з m лінійних рівнянь з m невідомими, де невідомими є коефіцієнти породжує полінома.

Дана система має вигляд

₁k₁  ₂k₂ ₃k₃  ...  _mk_m =k_m+1

₁k₂ ₂k₃ ₃k₄  ...  _mk_m+1 =k_m+2

₁k₃  ₂k₄ ₃k₅  ...  _mk_m+2 =k_m+3

.... ....

₁k_m ₂k_m+1 ₃k_m+2  ...  _mk_m+m-1 =k_2m .