Захист інформації (стр. 12 из 15)

= ( d - 1, d). (3.5)

Наприклад, якщо дано

= ( 0, 1), то обчислюємо

2 = 0 Å f( 1, 1),

складаємо (

1, 2), знову обчисляємо

3 = 1 Å f( 2, 2),

складаємо (

2, 3) і т.д.,..., до отримання послідовностей d - 1 і d, із котрих і формується криптограма = ( d - 1, d).

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

= ( 0, 1) = ( d - 1, d).

Тоді

,..., ,...,

1 = 3 Å f( 2, 2), 0 = 2 Å f( 1, 1),

= ( 0, 1), що, як очевидно і збігається з вихідним повідомленням.

Є багато різноманітних блокових шифрів, заснованих на структурі Файстеля, що відрізняються вибором функції f і засобом формування розширених ключів

i i=1,2,…,d з основного ключа . Нехай на такий шифр відбувається напад із відомим повідомленням. Тоді, знаючи опис функції f і засіб побудови підключей по основному ключу, опонент може скласти систему нелінійних рівнянь і спробувати її вирішити щодо ключа як невідомого. Стійкість даного типу шифрів грунтується на складності рішення системи нелінійних рівнянь із діями по модулі два. Доведено, що в загальному випадку ця задача відноситься до класу NP - важких задач.

Багатократне шифрування блоків.

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

1, зашифрувати ще раз за допомогою іншого ключа 2, тобто реалізувати процедури шифрування-дешифрування в такий спосіб:

, . (3.6)

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

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

Метод, що у даному випадку використовується для дешифрування, називається "зустріччю в центрі". Нехай є криптограма

, отримана шляхом повторного шифрування.

(3.7)

Для криптоаналізу використовуємо напад із відомим повідомленням, рахуючи, що відомо не менше двох блоків повідомлення і відповідні їм блоки криптограми, наприклад,

1® 1 і 2® 2. (3.8)

Рішення задачі будемо шукати шляхом перебору всіх можливих двоїчних ключів

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

Варіант ключа K	K1	K2	Km	Kn
	E1	E2	Em
	M1	M2	Mn

З співвідношення

очевидно, що для дійсно використаних ключів 1 або 2 якийсь елемент Em другого рядка повинний обов'язково співпасти з яким-небудь елементом Mn третього рядка. У такий спосіб достатньо знайти збіжні елементи в другому і третьому рядках і вибрати відповідні їм ключі Km і Kn у якості кандидатів у дійсні ключі 1 і 2. Проте збіги можливі і не тільки для істинних ключів, тобто кандидатів може виявитися декілька. Тому потрібно спробувати застосувати знайдені ключі до іншої пари повідомлення-криптограми для перевірки другого співвідношення

. (3.9)

Якщо виповниться і ця рівність то, як правило, знайдені ключі називаються істинними.

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

, . (3.10)

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