де Kj - j-та літера ключового слова представлена в кодуванні ASCII.
Ключове слово повторюється поки не отримано гаму, рівну довжині повідомлення.
Історія
Набув широкого застосування у комп'ютерних мережах 90-х років у зв'язку зі простотою реалізації.
Застосовувався для шифрування документів Microsoft Word в середовищі Windows 95.
На основі ГПВЧ
Нехай - внутрішній стан ГПВЧ, - функція перетворення стану, - функція шифрування.
Функція шифрування може змінюватися випадковим чином з кожним символом, тому вихід цієї функції повинен залежати не лише від поточного вхідного символу, але й від внутрішнього стану генератора. Цей внутрішній стан перетворюється функцією перетворення стану після кожного кроку шифрування. Генератор складається з компонентів та Безпечність такого шифру залежить від числа внутрішніх станів й складності функції перетворення Відповідно характеристики послідовних шифрів залежать від властивостей генераторів псевдовипадкових чисел. З іншої сторони, сама функція шифрування є достатньо простою і може складатися лише з логічної операції ХОР.
Схематично генератори ПВЧ можуть бути реалізовані у вигляді скінченних автоматів, які включають двійкові тригерні комірки пам'яті. Якщо скінченний автомат має комірок пам'яті, тоді він може приймати різних внутрішніх станів Функція перетворення станів представляється за допомогою комбінаторної логіки.
У загальному, процес шифрування полягає у генерації відправником за допомогою ГПВЧ гами шифру й накладанні отриманої гами на відкритий текст таким чином, наприклад з використанням операції додавання по модулю 2, що в результаті отримується шифрований текст. Процес розшифрування зводиться до повторної генерації гами шифру отримувачем повідомлення й накладення цієї гами на зашифровані дані.
В якості ключового потоку можна використовувати нелінійно "відфільтровани" вміст зсувного регістру, а для отримання послідовності максимальної довжини - лінійний зворотний зв'язок.
Функція f обирається таким чином, щоб забезпечити баланс між нулями та одиницями, а фільтрована послідовність мала розподіл, близький до рівномірного. Також потрібно, щоб фільрована послідовність мала великий період. Якщо є простим числом (наприклад, при ), то фільтрована послідовність може мати період при виборі структури зсувового регістру у відповідності із незвідним тривіальним многочленом степені До таких відносяться 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 607, 1279, 2203, 2281, а отримані таким чином чила є простими числами Мерсенна.
В колі зворотного зв'язку може використовуватися нелінійна логіка. Типовий нелінійний генератор із регістром зсуву представляє собою генератор, у схемі зворотного зв'язку якого засосовується нелінійна логіка. У лінійному генераторі використовувався лише зворотний зв'язок по модулю 2; цей зворотний зв'язок можна розглядати як "лінійну логіку". Прикладом нелінійної логіки може бути додавання по модулю 2 вихідного сигналу одного каскаду із логічною комбінацією кон'юнкції вихідних сигналів двох інших каскадів ( та ). Це можна записати наступним чином:
Основною перевагою такого нелінійного генератора із регістром зсуву (у порівнянні із лінійним генератором й нелінійними генераторами інших типів) є те, що він дає більше "максимальних" послідовностей (довжиною ) при даному числі n каскадів регістру.
Якщо період гами шифру перевищує довжину тексту, який шифрується й нападнику невідома жодна частина відкритого тексту, то такий шифр можна відкрити лише прямим перебором усії варіантів ключа. У цьому випадку криптостійкість шифру визначається довжиною ключа, яка може бути достатньо великою.
Використання
Джерелом гами шифру може бути блоковий шифр, який працює у режимі зворотного зв'язку й на основі діючого ключа та вектору ініціалізації .
Якщо НСД чисел (), то у рівнянні
для різних усі значення є різними.
Нехай але Тоді
або
Останнє суперечить вимозі взаємної простоти чисел тобто
Алгоритм генерації підстановки степені , , формулюється за допомогою послідовності випадкових чисел Вибір величини - розміру підстановки заміни можна прийняти довільним. Для забезпечення зручної реалізації алгоритму доцілно обирати значення, які відповідають розрядній сітці мікропроцесорів, а саме: де Коефіцієнт імітостійкості для є найменшим, а застосування призведе до суттєвого сповільнення процесу шифрування.
Матриця перехідних ймовірностей для вузла накладання шифру обчислюється формулою:
де - умовна ймовірністьпояви на виході вузла знаку в разі надходження знаку - підстановочна матриця, яка відповідає генерованій підстановці
Якщо послідовність випадкових чисел є незалежною у сукупності та має рівномірний розподіл, алгоритм забезпечує формування - симетричної групи підстановок степені Ймовірність появи послідовності
в тому числі такої, яка утворює нижню стрічку підстановки без коригування послідовності.
Для формального опису алгоритму використовується оператор Бекуса присвоєння значення деякої змінної :=, множина сформованих переходів позначена через [1]
Крок
Формальний опис
Коментар
1.
Ініціалізація змінних
2.
Визначення чергового переходу
3.
Перелік визначених переходів.
4.
Номер наступного переходу
5.
Номер чергового випадкового числа
6.
Якщо , то виконується крок 10, якщо ні - крок 7
Умовний перехід у кінець.
7.
Якщо , то виконується крок 2, якщо ні - крок 8
Умовний перехід до визначення наступного переходу.
8.
Модифікація випадкового числа.
9.
Далі виконується крок 7.
Перехід до перевірки у переліку визначених переходів.
10.
Останньому переходові присвоюється значення
Завершення роботи алгоритму.
Приклад
Відкритий текст: "алгоритм шифрування, який як ключ використовує ключове слово"
Якщо використовується ключ довжиною, як найменше, рівний довжині повідомлення, то шифр XOR стає значно більш криптостійким, ніж при використанні ключа, що повторюється. У разі, якщо для утворення такого ключа використовується генератор псевдовипадкових чисел, то результатом буде потоковий шифр.