Шифр XOR

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

C_i = P_i XOR K_j.

де K_j - j-та літера ключового слова представлена в кодуванні ASCII.

Ключове слово повторюється поки не отримано гаму, рівну довжині повідомлення.

Історія

Набув широкого застосування у комп'ютерних мережах 90-х років у зв'язку зі простотою реалізації. Застосовувався для шифрування документів Microsoft Word в середовищі Windows 95.

На основі ГПВЧ

Нехай ${\displaystyle S}$ - внутрішній стан ГПВЧ, ${\displaystyle g(K)}$ - функція перетворення стану, ${\displaystyle f(K)}$ - функція шифрування.

Функція шифрування може змінюватися випадковим чином з кожним символом, тому вихід цієї функції повинен залежати не лише від поточного вхідного символу, але й від внутрішнього стану ${\displaystyle S}$ генератора. Цей внутрішній стан перетворюється функцією перетворення стану ${\displaystyle g(K)}$ після кожного кроку шифрування. Генератор складається з компонентів ${\displaystyle S}$ та ${\displaystyle g(K).}$ Безпечність такого шифру залежить від числа внутрішніх станів ${\displaystyle S}$ й складності функції перетворення ${\displaystyle g(K).}$ Відповідно характеристики послідовних шифрів залежать від властивостей генераторів псевдовипадкових чисел. З іншої сторони, сама функція шифрування ${\displaystyle f(K)}$ є достатньо простою і може складатися лише з логічної операції ХОР.

Схематично генератори ПВЧ можуть бути реалізовані у вигляді скінченних автоматів, які включають двійкові тригерні комірки пам'яті. Якщо скінченний автомат має ${\displaystyle n}$ комірок пам'яті, тоді він може приймати ${\displaystyle 2^{n}}$ різних внутрішніх станів ${\displaystyle S.}$ Функція перетворення станів ${\displaystyle g(K)}$ представляється за допомогою комбінаторної логіки.

У загальному, процес шифрування полягає у генерації відправником за допомогою ГПВЧ гами шифру й накладанні отриманої гами на відкритий текст таким чином, наприклад з використанням операції додавання по модулю 2, що в результаті отримується шифрований текст. Процес розшифрування зводиться до повторної генерації гами шифру отримувачем повідомлення й накладення цієї гами на зашифровані дані.

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

Функція f обирається таким чином, щоб забезпечити баланс між нулями та одиницями, а фільтрована послідовність мала розподіл, близький до рівномірного. Також потрібно, щоб фільрована послідовність мала великий період. Якщо ${\displaystyle 2^{m}-1}$ є простим числом (наприклад, при ${\displaystyle m=3,\,\,\,\quad \,\,2^{3}-1=7}$), то фільтрована послідовність може мати період ${\displaystyle 2^{m}-1}$ при виборі структури зсувового регістру у відповідності із незвідним тривіальним многочленом ${\displaystyle h(X)}$ степені ${\displaystyle m.}$ До таких ${\displaystyle m}$ відносяться 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 607, 1279, 2203, 2281, а отримані таким чином чила є простими числами Мерсенна.

В колі зворотного зв'язку може використовуватися нелінійна логіка. Типовий нелінійний генератор із регістром зсуву представляє собою генератор, у схемі зворотного зв'язку якого засосовується нелінійна логіка. У лінійному генераторі використовувався лише зворотний зв'язок по модулю 2; цей зворотний зв'язок можна розглядати як "лінійну логіку". Прикладом нелінійної логіки може бути додавання по модулю 2 вихідного сигналу одного каскаду ${\displaystyle S_{i}}$ із логічною комбінацією кон'юнкції вихідних сигналів двох інших каскадів (${\displaystyle S_{j}}$ та ${\displaystyle S_{k}}$). Це можна записати наступним чином:

${\displaystyle {\text{Логіка зворотного зв'язку = }}S_{i}+S_{j}S_{k.}}$

Основною перевагою такого нелінійного генератора із регістром зсуву (у порівнянні із лінійним генератором й нелінійними генераторами інших типів) є те, що він дає більше "максимальних" послідовностей (довжиною ${\displaystyle 2^{n}}$) при даному числі n каскадів регістру.

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

Використання

Джерелом гами шифру може бути блоковий шифр, який працює у режимі зворотного зв'язку й на основі діючого ключа ${\displaystyle K}$ та вектору ініціалізації ${\displaystyle IV}$.

Якщо НСД чисел ${\displaystyle n,\delta \in \mathbb {N} }$ (${\displaystyle n>1:(n,\delta )=1}$), то ${\displaystyle \forall l\in \mathbb {Z} _{n}}$ у рівнянні

${\displaystyle l+k\cdot \delta =x_{k}\mathrm {mod} \,n,}$

для різних ${\displaystyle k\in \mathbb {Z} _{n}}$ усі значення ${\displaystyle x_{k}\in \mathbb {Z} _{n}}$ є різними.

Нехай ${\displaystyle k_{1}\neq k_{2},}$ але ${\displaystyle x_{1}=x_{2}.}$ Тоді

${\displaystyle l+k_{1}\cdot \delta =l+k_{2}\cdot \delta \,\mathrm {mod} \,n,}$

або

${\displaystyle (k_{1}-k_{2})\cdot \delta =0\,\mathrm {mod} \,n.}$

Останнє суперечить вимозі взаємної простоти чисел ${\displaystyle (n,\delta )=1,}$ тобто ${\displaystyle \forall k_{1}\neq k_{2}\Rightarrow x_{1}\neq x_{2}.}$

Алгоритм генерації підстановки степені ${\displaystyle n}$, ${\displaystyle X={\begin{pmatrix}0&...&n-1\\x_{0}&...&x_{n-1}\end{pmatrix}}}$ , формулюється за допомогою послідовності випадкових чисел ${\displaystyle j_{0},j_{1},...,j_{n-1}\in \mathbb {Z} _{n}.}$ Вибір величини ${\displaystyle n}$ - розміру підстановки заміни можна прийняти довільним. Для забезпечення зручної реалізації алгоритму доцілно обирати значення, які відповідають розрядній сітці мікропроцесорів, а саме: ${\displaystyle n=2^{m},}$ де ${\displaystyle m=2,4,8,...}$ Коефіцієнт імітостійкості для ${\displaystyle n=2^{2}}$ є найменшим, а застосування ${\displaystyle n=2^{8}=256}$ призведе до суттєвого сповільнення процесу шифрування.

Матриця перехідних ймовірностей для вузла накладання шифру обчислюється формулою:

${\displaystyle {\mathcal {P}}={\begin{pmatrix}p_{11}&...&p_{1n}\\...&...&...\\p_{n1}&...&p_{nn}\end{pmatrix}}=\sum x_{i}\in S_{n}p_{x_{i}}\cdot {\bar {X}}_{i},}$

де ${\displaystyle p_{ij}=P(i/j),\,\,\,i,j={\overline {1,n}}}$ - умовна ймовірністьпояви на виході вузла знаку ${\displaystyle j}$ в разі надходження знаку ${\displaystyle i;}$ ${\displaystyle {\bar {X}}_{i}}$ - підстановочна матриця, яка відповідає генерованій підстановці ${\displaystyle X_{i}\in S_{n}.}$

Якщо послідовність випадкових чисел ${\displaystyle j_{0},j_{1},...,j_{n-1}\in \mathbb {Z} _{n}}$ є незалежною у сукупності та має рівномірний розподіл, алгоритм забезпечує формування ${\displaystyle S_{n}}$ - симетричної групи підстановок степені ${\displaystyle n.}$ Ймовірність появи послідовності ${\displaystyle j_{0},j_{1},...,j_{n-1}\in \mathbb {Z} _{n}}$

${\displaystyle P(j_{0},j_{1},...,j_{n-1}\in \mathbb {Z} _{n})=({\frac {1}{n}})^{n}\neq 0,}$

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

Для формального опису алгоритму використовується оператор Бекуса присвоєння значення деякої змінної :=, множина сформованих переходів позначена через ${\displaystyle {\mathcal {A}}}$

Крок	Формальний опис	Коментар
1.	${\displaystyle k:=j_{k},\,m:=1,\,{\mathcal {A}}:=\{\emptyset \}.}$	Ініціалізація змінних
2.	${\displaystyle x_{k}:=j_{m}.}$	Визначення чергового переходу
3.	${\displaystyle {\mathcal {A}}:={\mathcal {A}}\cup \{x_{k}\}.}$	Перелік визначених переходів.
4.	${\displaystyle k:=k+1\,\mathrm {mod} \,n.}$	Номер наступного переходу
5.	${\displaystyle m:=m+1.}$	Номер чергового випадкового числа
6.	Якщо ${\displaystyle m=n}$, то виконується крок 10, якщо ні - крок 7	Умовний перехід у кінець.
7.	Якщо ${\displaystyle j_{m}\notin {\mathcal {A}}}$, то виконується крок 2, якщо ні - крок 8	Умовний перехід до визначення наступного переходу.
8.	${\displaystyle j_{m}:=j_{m}+\delta \,\mathrm {mod} \,n.}$	Модифікація випадкового числа.
9.	Далі виконується крок 7.	Перехід до перевірки у переліку визначених переходів.
10.	Останньому переходові присвоюється значення ${\displaystyle x_{k}:=\mathbb {Z} _{n}\setminus {\mathcal {A}}.}$	Завершення роботи алгоритму.

Приклад

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

Ключ: "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. Генадій Гулак, Володимир Бурячок, Павло Складанний - Швидкий алгоритм генерації підстановок багатоалфавітної заміни.