Шифр XOR

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

C_i = P_i XOR K_j.

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

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

Історія

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

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

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

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

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

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

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

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

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

$\text{Логіка зворотного зв'язку = }{S}_i+S_j{S}_{k.}$

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

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

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

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

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

$l+k\cdot \delta =x_k\mathrm{m}\mathrm{o}\mathrm{d}n,$

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

Нехай $k_1\ne k_2,$ але $x_1=x_2.$ Тоді

$l+k_1\cdot \delta =l+k_2\cdot \delta \mathrm{m}\mathrm{o}\mathrm{d}n,$

або

$(k_1-k_2)\cdot \delta =0\mathrm{m}\mathrm{o}\mathrm{d}n.$

Останнє суперечить вимозі взаємної простоти чисел $(n,\delta )=1,$ тобто $\mathrm{\forall }{k}_1\ne k_2\Rightarrow x_1\ne x_2.$

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

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

$𝒫=\left(\begin{array}{ccc}{p}_{11}& ...& p_{1n}\\ ...& ...& ...\\ p_{n1}& ...& p_{nn}\end{array}\right)=\sum x_i\in S_n{p}_{x_i}\cdot {\overline{X}}_i,$

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

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

$P(j_0,j_1,...,j_{n-1}\in {\mathbb{Z}}_n)=(\frac{1}{n}{)}^n\ne 0,$

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

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

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

Приклад

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

Ключ: "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 стає значно більш криптостійким, ніж при використанні ключа, що повторюється. У разі, якщо для утворення такого ключа використовується генератор псевдовипадкових чисел, то результатом буде потоковий шифр.

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

Посилання

шифр Ксор