Головна | Про нас | Зворотній зв'язок
При шифруванні методом гамування як ключ використовується випадкова рядок бітів, яка об'єднується з відкритим текстом, також представленим в двійковому вигляді (на-приклад, А = 00000, У = 00001, С = 00010 і т.д.), за допомогою побітового додавання по модулю 2, і в результаті виходить Шифр-ний текст. Генерування непередбачуваних довічних після-послідовно великої довжини є однією з важливих про- блем класичної криптографії. Для вирішення цієї проблеми широко використовуються генератори довічних псевдовипадкових по-отже.
Генеруються псевдовипадкові ряди чисел часто називаються вають гамою шифру або просто гамою (за назвою букви g грецького алфавіту, часто використовуваної в математичних фор-мулах для позначення випадкових величин).
Зазвичай для генерації послідовності псевдослів-чайних чисел застосовують комп'ютерні програми, які, хоча і називаються генераторами випадкових чисел, насправді ви-дають детерміновані числові послідовності, які за своїми властивостями дуже схожі на випадкові.
До криптографически стійкого генератору псевдослучайной послідовності чисел (гами шифру) пред'являються три основні вимоги:
1. період гами повинен бути досить великим для Шифр-вання повідомлень різної довжини;
2. гамма повинна бути практично непередбачуваною, що означає неможливість передбачити наступний біт гами, навіть якщо відомі тип генератора і попередній шматок гами;
3. генерування гами не повинно викликати великих техниче-ських складнощів.
Довжина періоду гами є найважливішою характери-стики генератора псевдовипадкових чисел. Після закінчення періоду числа почнуть повторюватися, і їх можна буде передбачити. Требує-травня довжина періоду гами визначається ступенем закритості даних. Чим довше ключ, тим важче його підібрати. Довжина періоду гами залежить від обраного алгоритму отримання псевдовипадкових чисел.
Друга вимога пов'язано з наступною проблемою: як можна достовірно переконатися, що псевдослучайная гамма конкретного генератора є дійсно непередбачуваною? Ще не існують такі універсальні і практично перевіряються критерії та методики. Щоб гамма вважалася непередбачуваною, тобто істинно випадкової, необхідно, щоб її період був дуже великим, а різні комбінації бітів певної довжини були рівномірно розподілені по всій її довжині.
Третя вимога обумовлює можливість практичної реалізації генератора програмним або апаратним шляхом із забезпеченням необхідної швидкодії.
Один з перших способів генерації псевдовипадкових чи-сіл на ЕОМ запропонував в 1946 р Джон фон Нейман. Суть цього способу полягає в тому, що кожне наступне випадкове число утворюється зведенням в квадрат попереднього числа з отбраси-ням цифр молодших і старших розрядів. Однак цей спосіб виявився ненадійним і від нього незабаром відмовилися.
З відомих процедур генерації послідовності псевдовипадкових цілих чисел найбільш часто застосовується так званий лінійний конгруентний генератор. Цей генератор виробляє послідовність псевдовипадкових чисел Y1. Y2. Yi-1. Yi. використовуючи співвідношення
Yi = (a * Yi-1 + b) mod m,
де Yi - i-e (поточний) число послідовності; Yi-1 - попе-ний число послідовності; а, Ь і m - константи; m - модуль;
а - множник (коефіцієнт); b - приріст; Y0 - породжує
число (початкове значення).
Поточне псевдовипадкове число Yi отримують з попе-ного числа Yi-1 множенням його на коефіцієнт а, складанням з приростом b і обчисленням залишку від ділення на модуль m. Дане рівняння генерує псевдовипадкові числа з періодом повторення, який залежить від обираних значень параметрів а, Ь і m і може досягати значення m. Значення модуля m бе-рется рівним 2 n або рівним простому числу, наприклад m = 2 31 -1. Приріст b має бути взаємно простим з m, коефіцієнт а повинен бути непарним числом.
Конгруентні генератори, що працюють за алгоритмом, запропонованим Національним бюро стандартів США, вико-ються, зокрема, в системах програмування. Ці генератори мають довжину періоду 2 24 і мають гарні статистичними властивостями. Однак така довжина періоду мала для криптографії-чеських застосувань. Крім того, доведено, що послідовно-сті, які генеруються конгруентними генераторами, не є криптографически стійкими.
Існує спосіб генерації послідовностей псев-дослучайних чисел на основі лінійних рекурентних співвідношенні-ний.
Розглянемо рекурентні співвідношення та їх різницеві рівняння:
де h0 ¹0, hk = 1 і кожне hi належить полю GF (q).
Рішенням цих рівнянь є послідовність елементів а0, а1, а2. поля GF (q). Соотноше-ня визначає правило обчислення ak по відомим зна-ченіям величин a0, a1, a2. ak-1. Потім за відомими значеннями a0, a1, a2. ak знаходять ak + 1 і т.д. В результаті за початковими зна-ченіям a0, a1, a2. ak-1 можна побудувати нескінченну послідовно-ність, причому кожен її наступний член визначається з k попередніх. Послідовності такого виду легко реализу-ються на комп'ютері, при цьому реалізація виходить особливо простий, якщо все hi і аi. приймають значення 0 і 1 з поля GF (2).
На рис. показана лінійна послідовна пере-ключательная схема, яка може бути використана для обчислення суми і, отже, для обчислення зна-ня ak за значеннями k попередніх членів послідовності. Вихідні величини a0, a1, a2. ak-1 поміщаються в розряди сдви-кового регістра, послідовні зрушення вмісту якого відповідають обчисленню послідовних символів, при цьому вихід після i-ro зсуву дорівнює аi. Цей пристрій генератором послідовності чисел, побудованим на базі зсувного регістру з лінійної зворотним зв'язком.
Рішення лінійних рекурентних співвідношень, реалізуючи-мі генератором з регістром зсуву, описуються наступною теоремою. нехай многочлен
де X - формальна змінна; hj - коефіцієнт при X j. при-приймаються значення 0 або 1; h0 ¹0, hk = 1, і нехай n - найменше ціле позитивне число, для якого многочлен Х n - 1 де-лится на h (X).
Крім того, многочлен g (x) = (X n -1) / h (X)
Тоді рішення зворотних співвідношень
у вигляді послідовності елементів а0, а1, а i. an-1 періодичні з періодом n і сукупність, складена з перших періодів всіх можливих рішень, що розглядаються як многочлени по модулю (Х n -1), тобто.
збігається з ідеалом, породженим многочленом g (X) в алгебрі багаточленів по модулю (Х n - 1). Доказ цієї теореми можна знайти в книзі Пітерсон У, Уелдон Е. «Коди, що виправляють помилки».
Зауважимо, що якщо при такому визначенні многочлена а (Х) елементи а0, а1, а2. обчислюються в порядку зростання номерів, то коефіцієнти многочлена а (Х) обчислюються, почи-ва з коефіцієнтів при ступенях вищих порядків. Слід також зазначити, що вид многочлена
визначає конфігурацію зворотних зв'язків (відводів) hj в генераторі зі зсувними регістром. Іншими словами, якщо у многочлена h (X) коефіцієнт hj = 1, це означає, що відведення hj в схемі генератора присутній, якщо ж у многочлена h (X) коефіцієнт hj = 0, то відведення hj в схемі генератора відсутній. В [Пітерсон У, Уелдон Е. «Коди, що виправляють помилки»] показано, що в якості h (Х) необхідно вибирати не приводиться примітивний многочлен. При такому виборі многочлена h (X) зі старшою ступенем m генератор забезпечує видачу псевдослучайной послідовності двійкових чисел з максі-мально можливим періодом 2 m - 1.
Розглянемо як приклад трьохрозрядний зсувний регістр з лінійної зворотним зв'язком, побудований відповідно до непріводімим примітивним многочленом
h (Х) = X 3 + X 2 + 1,
Нехай ключем є 101. Регістр починає працювати з цього стану; послідовність станів регістра приве-дена на рис.
Регістр проходить через всі сім ненульових со-стоянь і знову повертається в свій початковий стан 101. Це - найбільш довгий період даного регістра з лінійної об-ратної зв'язком. Така послідовність називається послідовно-вательного максимальної довжини для зсувного регістру (Maximal Lenght Shift Register Sequence - MLSRS). Пітерсон і Уелдон показали, що при будь-якому цілому m існує m-бітова послідовність MLSRS з періодом 2 m - 1. В приватно-сти, при m = 100 послідовність матиме період 2 100 - 1 і не повториться 10 16 років при передачі її по лінії зв'язку з бо-ростью 1 Мбіт / с.
В даному прикладі вихідний послідовністю (гамою шифру) ГШ зсувного регістру зі зворотним зв'язком є по-отже 1010011, яка циклічно повторюється. У цій послідовності є чотири одиниці і три нуля, і їх розподіл настільки близький до рівномірного, наскільки це можливо в послідовності, що має довжину 7. Якщо рас-дивитися пари послідовних бітів, то пари 10 і 01 появ-ляють по два рази, а пари 00 і 11 - один раз, що знову оказ-ється настільки близьким до рівномірного розподілу, наскільки це можливо. У разі послідовності максималь-ною довжини для m-розрядного регістра це властивість равнораспре-ності поширюється на трійки, четвірки і т.д. бітів, аж до m-бітових груп. Завдяки такій близькості до одно-мірного розподілу послідовності максимальної дли-ни часто використовуються в якості псевдовипадкових послідовно-ність в криптографічних системах, які імітують роботу крипостійкість системи одноразового шифрування.
Хоча така криптографічний система здійснює ними-цію свідомо крипостійкість системи одноразового шіфрова-ня, сама вона не відрізняється стійкістю і може бути розкрита за кілька секунд роботи комп'ютера за умови наявності Через Вестн відкритого тексту [Діффі У. Хеллман М.Е. «Захищеність і імітостойкость. Введення в криптографію »].
Якщо відводи регістра зі зворотним зв'язком зафіксовані, то для знаходження початкового стану регістра досить знати m бітів відкритого тексту. Щоб знайти m бітів ключового потоку, m бітів відомого відкритого тексту складають по мо. дулю 2 з відповідними m бітами шифртекста. Отримані m бітів дають стан зсувного регістру зі зворотним зв'язком в зворотному напрямку на деякий момент часу. Потім, мо-деліруя роботу регістра назад, можна визначити його початковий стан.
Якщо відводи регістра зі зворотним зв'язком не фіксовані, а є частиною ключа, то досить 2m бітів відомого від-критого тексту, щоб порівняно швидко визначити располо-ються відводів регістра і його початковий стан. Нехай S (i) вектор-стовпець, що складається з m символів 0 і 1, який визна-чає стан регістра в i-й момент часу. тоді
S (i + 1) = A * S (i) mod 2,
де А - матриця розміром m x m, що визначає положення від-водів регістра зі зворотним зв'язком.
Для трехразрядного регістра
Матриця А завжди має наступну структуру: в її пер-виття рядку відображена послідовність відводів в регістрі, що не-посередньо під головною діагоналлю розташовуються одиниці, а в інших позиціях розташовуються нулі.
2m бітів відомого відкритого тексту дозволяють обчислюва-лити 2т послідовних бітів ключового потоку. Для спрощення позначень припустимо, що це - перші 2 m бітів ключового потоку. отже,
• S (1) - перша група m відомих бітів ключового, потоку;
• S (2) - наступна група (починаючи з номера 2) з m відомого-них бітів ключового потоку;
• S (m + 1) - остання група з m відомих бітів ключовий потоку.
Далі можна утворити дві матриці розміром m x m:
які пов'язані співвідношенням X (2) = A * X (1) mod2.
Можна показати, що для будь-якої послідовності мак-симально довжини матриця Х (1) завжди несінгулярна, тому матрицю А можна обчислити як
А = Х (2) [Х (1)] - 1 mod 2.
Звернення матриці Х (1) вимагає (щонайбільше) поряд-ка m 3 операцій, тому легко виконується при будь-якому розумному значенні m.