Немає перевірених версій цієї сторінки; ймовірно, її ще не перевіряли на відповідність правилам проекту.

Шифр XORалгоритм шифрування, який як ключ використовує ключове слово та може бути записаний формулою

Ci = Pi XOR Kj.

де 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. Останньому переходові присвоюється значення   Завершення роботи алгоритму.



Приклад

ред.

Відкритий текст: "алгоритм шифрування, який як ключ використовує ключове слово"

Ключ: "qwertyqwertyqwertyqwertyqwertyqwertyqwertyqwertyqwertyqwertyqwertyqwerty"

Шифротекст:"‘њ†њ„‘ѓ›EЉњЌЃ„‡’™”Ћ[EЌћ‘*W–R‹“џ†—БТ“љ‰’’T›™ќ‹‚њ€ѓ™‡ЃОY›њ›…љ›”W”™љ›џ"

Відкритий текст а 11100000
Ключ q 01110001
Шифротекст 10010001

по правилу

0+0=0
0+1=1
1+0=1
1+1=0

Криптоаналіз

ред.

Криптоаналіз шифру XOR аналогічний криптоаналізу шифра Віженера .

Ще ефективніша атака з відомим відкритим текстом, у разі якщо відомо частину відкритого тексту: Для приведеного прикладу, якщо стало відомо що повідомлення починається зі слова "алгоритм"

"алгоритм" XOR "‘њ†њ„‘ѓ›" ="qwertyqw" .

Таким чином ключ відновлено.

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

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

Посилання

ред.

шифр Ксор

  1. Генадій Гулак, Володимир Бурячок, Павло Складанний - Швидкий алгоритм генерації підстановок багатоалфавітної заміни.