Шифр XOR — алгоритм шифрування, який як ключ використовує ключове слово та може бути записаний формулою
Ci = Pi XOR Kj.
де Kj - j-та літера ключового слова представлена в кодуванні ASCII.
Ключове слово повторюється поки не отримано гаму, рівну довжині повідомлення.
Набув широкого застосування у комп'ютерних мережах 90-х років у зв'язку зі простотою реалізації. Застосовувався для шифрування документів Microsoft Word в середовищі Windows 95.
Нехай S {\displaystyle S} - внутрішній стан ГПВЧ, g ( K ) {\displaystyle g(K)} - функція перетворення стану, f ( K ) {\displaystyle f(K)} - функція шифрування.
Функція шифрування може змінюватися випадковим чином з кожним символом, тому вихід цієї функції повинен залежати не лише від поточного вхідного символу, але й від внутрішнього стану S {\displaystyle S} генератора. Цей внутрішній стан перетворюється функцією перетворення стану g ( K ) {\displaystyle g(K)} після кожного кроку шифрування. Генератор складається з компонентів S {\displaystyle S} та g ( K ) . {\displaystyle g(K).} Безпечність такого шифру залежить від числа внутрішніх станів S {\displaystyle S} й складності функції перетворення g ( K ) . {\displaystyle g(K).} Відповідно характеристики послідовних шифрів залежать від властивостей генераторів псевдовипадкових чисел. З іншої сторони, сама функція шифрування f ( K ) {\displaystyle f(K)} є достатньо простою і може складатися лише з логічної операції ХОР.
Схематично генератори ПВЧ можуть бути реалізовані у вигляді скінченних автоматів, які включають двійкові тригерні комірки пам'яті. Якщо скінченний автомат має n {\displaystyle n} комірок пам'яті, тоді він може приймати 2 n {\displaystyle 2^{n}} різних внутрішніх станів S . {\displaystyle S.} Функція перетворення станів g ( K ) {\displaystyle g(K)} представляється за допомогою комбінаторної логіки.
У загальному, процес шифрування полягає у генерації відправником за допомогою ГПВЧ гами шифру й накладанні отриманої гами на відкритий текст таким чином, наприклад з використанням операції додавання по модулю 2, що в результаті отримується шифрований текст. Процес розшифрування зводиться до повторної генерації гами шифру отримувачем повідомлення й накладення цієї гами на зашифровані дані.
В якості ключового потоку можна використовувати нелінійно "відфільтровани" вміст зсувного регістру, а для отримання послідовності максимальної довжини - лінійний зворотний зв'язок.
Функція f обирається таким чином, щоб забезпечити баланс між нулями та одиницями, а фільтрована послідовність мала розподіл, близький до рівномірного. Також потрібно, щоб фільрована послідовність мала великий період. Якщо 2 m − − --> 1 {\displaystyle 2^{m}-1} є простим числом (наприклад, при m = 3 , 2 3 − − --> 1 = 7 {\displaystyle m=3,\,\,\,\quad \,\,2^{3}-1=7} ), то фільтрована послідовність може мати період 2 m − − --> 1 {\displaystyle 2^{m}-1} при виборі структури зсувового регістру у відповідності із незвідним тривіальним многочленом h ( X ) {\displaystyle h(X)} степені m . {\displaystyle m.} До таких m {\displaystyle m} відносяться 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 607, 1279, 2203, 2281, а отримані таким чином чила є простими числами Мерсенна.
В колі зворотного зв'язку може використовуватися нелінійна логіка. Типовий нелінійний генератор із регістром зсуву представляє собою генератор, у схемі зворотного зв'язку якого засосовується нелінійна логіка. У лінійному генераторі використовувався лише зворотний зв'язок по модулю 2; цей зворотний зв'язок можна розглядати як "лінійну логіку". Прикладом нелінійної логіки може бути додавання по модулю 2 вихідного сигналу одного каскаду S i {\displaystyle S_{i}} із логічною комбінацією кон'юнкції вихідних сигналів двох інших каскадів ( S j {\displaystyle S_{j}} та S k {\displaystyle S_{k}} ). Це можна записати наступним чином:
Логіка зворотного зв'язку = S i + S j S k . {\displaystyle {\text{Логіка зворотного зв'язку = }}S_{i}+S_{j}S_{k.}}
Основною перевагою такого нелінійного генератора із регістром зсуву (у порівнянні із лінійним генератором й нелінійними генераторами інших типів) є те, що він дає більше "максимальних" послідовностей (довжиною 2 n {\displaystyle 2^{n}} ) при даному числі n каскадів регістру.
Якщо період гами шифру перевищує довжину тексту, який шифрується й нападнику невідома жодна частина відкритого тексту, то такий шифр можна відкрити лише прямим перебором усії варіантів ключа. У цьому випадку криптостійкість шифру визначається довжиною ключа, яка може бути достатньо великою.
Джерелом гами шифру може бути блоковий шифр, який працює у режимі зворотного зв'язку й на основі діючого ключа K {\displaystyle K} та вектору ініціалізації I V {\displaystyle IV} .
Якщо НСД чисел n , δ δ --> ∈ ∈ --> N {\displaystyle n,\delta \in \mathbb {N} } ( n > 1 : ( n , δ δ --> ) = 1 {\displaystyle n>1:(n,\delta )=1} ), то ∀ ∀ --> l ∈ ∈ --> Z n {\displaystyle \forall l\in \mathbb {Z} _{n}} у рівнянні
l + k ⋅ ⋅ --> δ δ --> = x k m o d n , {\displaystyle l+k\cdot \delta =x_{k}\mathrm {mod} \,n,}
для різних k ∈ ∈ --> Z n {\displaystyle k\in \mathbb {Z} _{n}} усі значення x k ∈ ∈ --> Z n {\displaystyle x_{k}\in \mathbb {Z} _{n}} є різними.
Нехай k 1 ≠ ≠ --> k 2 , {\displaystyle k_{1}\neq k_{2},} але x 1 = x 2 . {\displaystyle x_{1}=x_{2}.} Тоді
l + k 1 ⋅ ⋅ --> δ δ --> = l + k 2 ⋅ ⋅ --> δ δ --> m o d n , {\displaystyle l+k_{1}\cdot \delta =l+k_{2}\cdot \delta \,\mathrm {mod} \,n,}
або
( k 1 − − --> k 2 ) ⋅ ⋅ --> δ δ --> = 0 m o d n . {\displaystyle (k_{1}-k_{2})\cdot \delta =0\,\mathrm {mod} \,n.}
Останнє суперечить вимозі взаємної простоти чисел ( n , δ δ --> ) = 1 , {\displaystyle (n,\delta )=1,} тобто ∀ ∀ --> k 1 ≠ ≠ --> k 2 ⇒ ⇒ --> x 1 ≠ ≠ --> x 2 . {\displaystyle \forall k_{1}\neq k_{2}\Rightarrow x_{1}\neq x_{2}.}
Алгоритм генерації підстановки степені n {\displaystyle n} , X = ( 0 . . . n − − --> 1 x 0 . . . x n − − --> 1 ) {\displaystyle X={\begin{pmatrix}0&...&n-1\\x_{0}&...&x_{n-1}\end{pmatrix}}} , формулюється за допомогою послідовності випадкових чисел j 0 , j 1 , . . . , j n − − --> 1 ∈ ∈ --> Z n . {\displaystyle j_{0},j_{1},...,j_{n-1}\in \mathbb {Z} _{n}.} Вибір величини n {\displaystyle n} - розміру підстановки заміни можна прийняти довільним. Для забезпечення зручної реалізації алгоритму доцілно обирати значення, які відповідають розрядній сітці мікропроцесорів, а саме: n = 2 m , {\displaystyle n=2^{m},} де m = 2 , 4 , 8 , . . . {\displaystyle m=2,4,8,...} Коефіцієнт імітостійкості для n = 2 2 {\displaystyle n=2^{2}} є найменшим, а застосування n = 2 8 = 256 {\displaystyle n=2^{8}=256} призведе до суттєвого сповільнення процесу шифрування.
Матриця перехідних ймовірностей для вузла накладання шифру обчислюється формулою:
P = ( p 11 . . . p 1 n . . . . . . . . . p n 1 . . . p n n ) = ∑ ∑ --> x i ∈ ∈ --> S n p x i ⋅ ⋅ --> X ¯ ¯ --> i , {\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},}
де p i j = P ( i / j ) , i , j = 1 , n ¯ ¯ --> {\displaystyle p_{ij}=P(i/j),\,\,\,i,j={\overline {1,n}}} - умовна ймовірністьпояви на виході вузла знаку j {\displaystyle j} в разі надходження знаку i ; {\displaystyle i;} X ¯ ¯ --> i {\displaystyle {\bar {X}}_{i}} - підстановочна матриця, яка відповідає генерованій підстановці X i ∈ ∈ --> S n . {\displaystyle X_{i}\in S_{n}.}
Якщо послідовність випадкових чисел j 0 , j 1 , . . . , j n − − --> 1 ∈ ∈ --> Z n {\displaystyle j_{0},j_{1},...,j_{n-1}\in \mathbb {Z} _{n}} є незалежною у сукупності та має рівномірний розподіл, алгоритм забезпечує формування S n {\displaystyle S_{n}} - симетричної групи підстановок степені n . {\displaystyle n.} Ймовірність появи послідовності j 0 , j 1 , . . . , j n − − --> 1 ∈ ∈ --> Z n {\displaystyle j_{0},j_{1},...,j_{n-1}\in \mathbb {Z} _{n}}
P ( j 0 , j 1 , . . . , j n − − --> 1 ∈ ∈ --> Z n ) = ( 1 n ) n ≠ ≠ --> 0 , {\displaystyle P(j_{0},j_{1},...,j_{n-1}\in \mathbb {Z} _{n})=({\frac {1}{n}})^{n}\neq 0,}
в тому числі такої, яка утворює нижню стрічку підстановки без коригування послідовності.
Відкритий текст: "алгоритм шифрування, який як ключ використовує ключове слово"
Ключ: "qwertyqwertyqwertyqwertyqwertyqwertyqwertyqwertyqwertyqwertyqwertyqwerty"
Шифротекст:"‘њ†њ„‘ѓ›EЉњЌЃ„‡’™”Ћ[EЌћ‘*W–R‹“џ†—БТ“љ‰’’T›™ќ‹‚њ€ѓ™‡ЃОY›њ›…љ›”W”™љ›џ"
по правилу
0+0=0 0+1=1 1+0=1 1+1=0
Криптоаналіз шифру XOR аналогічний криптоаналізу шифра Віженера .
Ще ефективніша атака з відомим відкритим текстом, у разі якщо відомо частину відкритого тексту: Для приведеного прикладу, якщо стало відомо що повідомлення починається зі слова "алгоритм"
"алгоритм" XOR "‘њ†њ„‘ѓ›" ="qwertyqw" .
Таким чином ключ відновлено.
Якщо використовується ключ довжиною, як найменше, рівний довжині повідомлення, то шифр XOR стає значно більш криптостійким, ніж при використанні ключа, що повторюється. У разі, якщо для утворення такого ключа використовується генератор псевдовипадкових чисел, то результатом буде потоковий шифр.
Якщо для утворення ключа використовується генератор істинно випадкових чисел, то у цьому разі ми маємо справу з шифром Вернама - єдиною криптографічною системою, для якої теоретично доведена абсолютна криптографічна стійкість.
шифр Ксор
Lokasi Pengunjung: 3.142.53.211