Шифр XOR — алгоритм шифрування, який як ключ використовує ключове слово та може бути записаний формулою
Ci = Pi XOR Kj.
де Kj - j-та літера ключового слова представлена в кодуванні ASCII.
Ключове слово повторюється поки не отримано гаму, рівну довжині повідомлення.
Історія
Набув широкого застосування у комп'ютерних мережах 90-х років у зв'язку зі простотою реалізації. Застосовувався для шифрування документів Microsoft Word в середовищі Windows 95.
На основі ГПВЧ
Нехай - внутрішній стан ГПВЧ,
- функція перетворення стану,
- функція шифрування.
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpOW1MMlk0TDBkaFoyRm5ZVzFoTG5ScFppOXNiM056ZVMxd1lXZGxNUzB5TWpCd2VDMUhZV2RoWjJGdFlTNTBhV1l1YW5Cbi5qcGc=.jpg)
Функція шифрування може змінюватися випадковим чином з кожним символом, тому вихід цієї функції повинен залежати не лише від поточного вхідного символу, але й від внутрішнього стану генератора. Цей внутрішній стан перетворюється функцією перетворення стану
після кожного кроку шифрування. Генератор складається з компонентів
та
Безпечність такого шифру залежить від числа внутрішніх станів
й складності функції перетворення
Відповідно характеристики послідовних шифрів залежать від властивостей генераторів псевдовипадкових чисел. З іншої сторони, сама функція шифрування
є достатньо простою і може складатися лише з логічної операції ХОР.
Схематично генератори ПВЧ можуть бути реалізовані у вигляді скінченних автоматів, які включають двійкові тригерні комірки пам'яті. Якщо скінченний автомат має комірок пам'яті, тоді він може приймати
різних внутрішніх станів
Функція перетворення станів
представляється за допомогою комбінаторної логіки.
У загальному, процес шифрування полягає у генерації відправником за допомогою ГПВЧ гами шифру й накладанні отриманої гами на відкритий текст таким чином, наприклад з використанням операції додавання по модулю 2, що в результаті отримується шифрований текст. Процес розшифрування зводиться до повторної генерації гами шифру отримувачем повідомлення й накладення цієї гами на зашифровані дані.
В якості ключового потоку можна використовувати нелінійно "відфільтровани" вміст зсувного регістру, а для отримання послідовності максимальної довжини - лінійний зворотний зв'язок.
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpOHlMekppTDA1dmJteHBibVZoY214dloybGpaMkZ0YldFdWRHbG1MMnh2YzNONUxYQmhaMlV4TFRReE5YQjRMVTV2Ym14cGJtVmhjbXh2WjJsaloyRnRiV0V1ZEdsbUxtcHdadz09LmpwZw==.jpg)
Функція f обирається таким чином, щоб забезпечити баланс між нулями та одиницями, а фільтрована послідовність мала розподіл, близький до рівномірного. Також потрібно, щоб фільрована послідовність мала великий період. Якщо є простим числом (наприклад, при
), то фільтрована послідовність може мати період
при виборі структури зсувового регістру у відповідності із незвідним тривіальним многочленом
степені
До таких
відносяться 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 607, 1279, 2203, 2281, а отримані таким чином чила є простими числами Мерсенна.
В колі зворотного зв'язку може використовуватися нелінійна логіка. Типовий нелінійний генератор із регістром зсуву представляє собою генератор, у схемі зворотного зв'язку якого засосовується нелінійна логіка. У лінійному генераторі використовувався лише зворотний зв'язок по модулю 2; цей зворотний зв'язок можна розглядати як "лінійну логіку". Прикладом нелінійної логіки може бути додавання по модулю 2 вихідного сигналу одного каскаду із логічною комбінацією кон'юнкції вихідних сигналів двох інших каскадів (
та
). Це можна записати наступним чином:
Основною перевагою такого нелінійного генератора із регістром зсуву (у порівнянні із лінійним генератором й нелінійними генераторами інших типів) є те, що він дає більше "максимальних" послідовностей (довжиною ) при даному числі n каскадів регістру.
Якщо період гами шифру перевищує довжину тексту, який шифрується й нападнику невідома жодна частина відкритого тексту, то такий шифр можна відкрити лише прямим перебором усії варіантів ключа. У цьому випадку криптостійкість шифру визначається довжиною ключа, яка може бути достатньо великою.
Використання
Джерелом гами шифру може бути блоковий шифр, який працює у режимі зворотного зв'язку й на основі діючого ключа та вектору ініціалізації
.
Якщо НСД чисел (
), то
у рівнянні
для різних усі значення
є різними.
Нехай але
Тоді
або
Останнє суперечить вимозі взаємної простоти чисел тобто
Алгоритм генерації підстановки степені ,
, формулюється за допомогою послідовності випадкових чисел
Вибір величини
- розміру підстановки заміни можна прийняти довільним. Для забезпечення зручної реалізації алгоритму доцілно обирати значення, які відповідають розрядній сітці мікропроцесорів, а саме:
де
Коефіцієнт імітостійкості для
є найменшим, а застосування
призведе до суттєвого сповільнення процесу шифрування.
Матриця перехідних ймовірностей для вузла накладання шифру обчислюється формулою:
де - умовна ймовірністьпояви на виході вузла знаку
в разі надходження знаку
- підстановочна матриця, яка відповідає генерованій підстановці
Якщо послідовність випадкових чисел є незалежною у сукупності та має рівномірний розподіл, алгоритм забезпечує формування
- симетричної групи підстановок степені
Ймовірність появи послідовності
в тому числі такої, яка утворює нижню стрічку підстановки без коригування послідовності.
Крок | Формальний опис | Коментар |
---|---|---|
1. | Ініціалізація змінних | |
2. | Визначення чергового переходу | |
3. | Перелік визначених переходів. | |
4. | Номер наступного переходу | |
5. | Номер чергового випадкового числа | |
6. | Якщо | Умовний перехід у кінець. |
7. | Якщо | Умовний перехід до визначення наступного переходу. |
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 стає значно більш криптостійким, ніж при використанні ключа, що повторюється. У разі, якщо для утворення такого ключа використовується генератор псевдовипадкових чисел, то результатом буде потоковий шифр.
Якщо для утворення ключа використовується , то у цьому разі ми маємо справу з шифром Вернама - єдиною криптографічною системою, для якої теоретично доведена .
Посилання
- Генадій Гулак, Володимир Бурячок, Павло Складанний - Швидкий алгоритм генерації підстановок багатоалфавітної заміни.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Shifr XOR algoritm shifruvannya yakij yak klyuch vikoristovuye klyuchove slovo ta mozhe buti zapisanij formuloyu Ci Pi XOR Kj de Kj j ta litera klyuchovogo slova predstavlena v koduvanni ASCII Klyuchove slovo povtoryuyetsya poki ne otrimano gamu rivnu dovzhini povidomlennya IstoriyaNabuv shirokogo zastosuvannya u komp yuternih merezhah 90 h rokiv u zv yazku zi prostotoyu realizaciyi Zastosovuvavsya dlya shifruvannya dokumentiv Microsoft Word v seredovishi Windows 95 Na osnovi GPVChNehaj S displaystyle S vnutrishnij stan GPVCh g K displaystyle g K funkciya peretvorennya stanu f K displaystyle f K funkciya shifruvannya Funkciya shifruvannya mozhe zminyuvatisya vipadkovim chinom z kozhnim simvolom tomu vihid ciyeyi funkciyi povinen zalezhati ne lishe vid potochnogo vhidnogo simvolu ale j vid vnutrishnogo stanu S displaystyle S generatora Cej vnutrishnij stan peretvoryuyetsya funkciyeyu peretvorennya stanu g K displaystyle g K pislya kozhnogo kroku shifruvannya Generator skladayetsya z komponentiv S displaystyle S ta g K displaystyle g K Bezpechnist takogo shifru zalezhit vid chisla vnutrishnih staniv S displaystyle S j skladnosti funkciyi peretvorennya g K displaystyle g K Vidpovidno harakteristiki poslidovnih shifriv zalezhat vid vlastivostej generatoriv psevdovipadkovih chisel Z inshoyi storoni sama funkciya shifruvannya f K displaystyle f K ye dostatno prostoyu i mozhe skladatisya lishe z logichnoyi operaciyi HOR Shematichno generatori PVCh mozhut buti realizovani u viglyadi skinchennih avtomativ yaki vklyuchayut dvijkovi trigerni komirki pam yati Yaksho skinchennij avtomat maye n displaystyle n komirok pam yati todi vin mozhe prijmati 2 n displaystyle 2 n riznih vnutrishnih staniv S displaystyle S Funkciya peretvorennya staniv g K displaystyle g K predstavlyayetsya za dopomogoyu kombinatornoyi logiki U zagalnomu proces shifruvannya polyagaye u generaciyi vidpravnikom za dopomogoyu GPVCh gami shifru j nakladanni otrimanoyi gami na vidkritij tekst takim chinom napriklad z vikoristannyam operaciyi dodavannya po modulyu 2 sho v rezultati otrimuyetsya shifrovanij tekst Proces rozshifruvannya zvoditsya do povtornoyi generaciyi gami shifru otrimuvachem povidomlennya j nakladennya ciyeyi gami na zashifrovani dani V yakosti klyuchovogo potoku mozhna vikoristovuvati nelinijno vidfiltrovani vmist zsuvnogo registru a dlya otrimannya poslidovnosti maksimalnoyi dovzhini linijnij zvorotnij zv yazok Funkciya f obirayetsya takim chinom shob zabezpechiti balans mizh nulyami ta odinicyami a filtrovana poslidovnist mala rozpodil blizkij do rivnomirnogo Takozh potribno shob filrovana poslidovnist mala velikij period Yaksho 2 m 1 displaystyle 2 m 1 ye prostim chislom napriklad pri m 3 2 3 1 7 displaystyle m 3 quad 2 3 1 7 to filtrovana poslidovnist mozhe mati period 2 m 1 displaystyle 2 m 1 pri vibori strukturi zsuvovogo registru u vidpovidnosti iz nezvidnim trivialnim mnogochlenom h X displaystyle h X stepeni m displaystyle m Do takih m displaystyle m vidnosyatsya 2 3 5 7 13 17 19 31 61 89 107 127 607 1279 2203 2281 a otrimani takim chinom chila ye prostimi chislami Mersenna V koli zvorotnogo zv yazku mozhe vikoristovuvatisya nelinijna logika Tipovij nelinijnij generator iz registrom zsuvu predstavlyaye soboyu generator u shemi zvorotnogo zv yazku yakogo zasosovuyetsya nelinijna logika U linijnomu generatori vikoristovuvavsya lishe zvorotnij zv yazok po modulyu 2 cej zvorotnij zv yazok mozhna rozglyadati yak linijnu logiku Prikladom nelinijnoyi logiki mozhe buti dodavannya po modulyu 2 vihidnogo signalu odnogo kaskadu S i displaystyle S i iz logichnoyu kombinaciyeyu kon yunkciyi vihidnih signaliv dvoh inshih kaskadiv S j displaystyle S j ta S k displaystyle S k Ce mozhna zapisati nastupnim chinom Logika zvorotnogo zv yazku S i S j S k displaystyle text Logika zvorotnogo zv yazku S i S j S k Osnovnoyu perevagoyu takogo nelinijnogo generatora iz registrom zsuvu u porivnyanni iz linijnim generatorom j nelinijnimi generatorami inshih tipiv ye te sho vin daye bilshe maksimalnih poslidovnostej dovzhinoyu 2 n displaystyle 2 n pri danomu chisli n kaskadiv registru Yaksho period gami shifru perevishuye dovzhinu tekstu yakij shifruyetsya j napadniku nevidoma zhodna chastina vidkritogo tekstu to takij shifr mozhna vidkriti lishe pryamim pereborom usiyi variantiv klyucha U comu vipadku kriptostijkist shifru viznachayetsya dovzhinoyu klyucha yaka mozhe buti dostatno velikoyu VikoristannyaDzherelom gami shifru mozhe buti blokovij shifr yakij pracyuye u rezhimi zvorotnogo zv yazku j na osnovi diyuchogo klyucha K displaystyle K ta vektoru inicializaciyi I V displaystyle IV Yaksho NSD chisel n d N displaystyle n delta in mathbb N n gt 1 n d 1 displaystyle n gt 1 n delta 1 to l Z n displaystyle forall l in mathbb Z n u rivnyanni l k d x k m o d n displaystyle l k cdot delta x k mathrm mod n dlya riznih k Z n displaystyle k in mathbb Z n usi znachennya x k Z n displaystyle x k in mathbb Z n ye riznimi Nehaj k 1 k 2 displaystyle k 1 neq k 2 ale x 1 x 2 displaystyle x 1 x 2 Todi l k 1 d l k 2 d m o d n displaystyle l k 1 cdot delta l k 2 cdot delta mathrm mod n abo k 1 k 2 d 0 m o d n displaystyle k 1 k 2 cdot delta 0 mathrm mod n Ostannye superechit vimozi vzayemnoyi prostoti chisel n d 1 displaystyle n delta 1 tobto k 1 k 2 x 1 x 2 displaystyle forall k 1 neq k 2 Rightarrow x 1 neq x 2 Algoritm generaciyi pidstanovki stepeni n displaystyle n X 0 n 1 x 0 x n 1 displaystyle X begin pmatrix 0 amp amp n 1 x 0 amp amp x n 1 end pmatrix formulyuyetsya za dopomogoyu poslidovnosti vipadkovih chisel j 0 j 1 j n 1 Z n displaystyle j 0 j 1 j n 1 in mathbb Z n Vibir velichini n displaystyle n rozmiru pidstanovki zamini mozhna prijnyati dovilnim Dlya zabezpechennya zruchnoyi realizaciyi algoritmu docilno obirati znachennya yaki vidpovidayut rozryadnij sitci mikroprocesoriv a same n 2 m displaystyle n 2 m de m 2 4 8 displaystyle m 2 4 8 Koeficiyent imitostijkosti dlya n 2 2 displaystyle n 2 2 ye najmenshim a zastosuvannya n 2 8 256 displaystyle n 2 8 256 prizvede do suttyevogo spovilnennya procesu shifruvannya Matricya perehidnih jmovirnostej dlya vuzla nakladannya shifru obchislyuyetsya formuloyu 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 amp amp p 1n amp amp p n1 amp amp p nn end pmatrix sum x i in S n p x i cdot bar X i de p i j P i j i j 1 n displaystyle p ij P i j i j overline 1 n umovna jmovirnistpoyavi na vihodi vuzla znaku j displaystyle j v razi nadhodzhennya znaku i displaystyle i X i displaystyle bar X i pidstanovochna matricya yaka vidpovidaye generovanij pidstanovci X i S n displaystyle X i in S n Yaksho poslidovnist vipadkovih chisel j 0 j 1 j n 1 Z n displaystyle j 0 j 1 j n 1 in mathbb Z n ye nezalezhnoyu u sukupnosti ta maye rivnomirnij rozpodil algoritm zabezpechuye formuvannya S n displaystyle S n simetrichnoyi grupi pidstanovok stepeni n displaystyle n Jmovirnist poyavi poslidovnosti 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 v tomu chisli takoyi yaka utvoryuye nizhnyu strichku pidstanovki bez koriguvannya poslidovnosti Dlya formalnogo opisu algoritmu vikoristovuyetsya operator Bekusa prisvoyennya znachennya deyakoyi zminnoyi mnozhina sformovanih perehodiv poznachena cherez A displaystyle mathcal A Krok Formalnij opis Komentar 1 k j k m 1 A displaystyle k j k m 1 mathcal A emptyset Inicializaciya zminnih 2 x k j m displaystyle x k j m Viznachennya chergovogo perehodu 3 A A x k displaystyle mathcal A mathcal A cup x k Perelik viznachenih perehodiv 4 k k 1 m o d n displaystyle k k 1 mathrm mod n Nomer nastupnogo perehodu 5 m m 1 displaystyle m m 1 Nomer chergovogo vipadkovogo chisla 6 Yaksho m n displaystyle m n to vikonuyetsya krok 10 yaksho ni krok 7 Umovnij perehid u kinec 7 Yaksho j m A displaystyle j m notin mathcal A to vikonuyetsya krok 2 yaksho ni krok 8 Umovnij perehid do viznachennya nastupnogo perehodu 8 j m j m d m o d n displaystyle j m j m delta mathrm mod n Modifikaciya vipadkovogo chisla 9 Dali vikonuyetsya krok 7 Perehid do perevirki u pereliku viznachenih perehodiv 10 Ostannomu perehodovi prisvoyuyetsya znachennya x k Z n A displaystyle x k mathbb Z n setminus mathcal A Zavershennya roboti algoritmu PrikladVidkritij tekst algori tm shifruvannya yakij yak klyuch vikoristovuye klyuchove slovo Klyuch qwerty qwertyqwertyqwertyqwertyqwertyqwertyqwertyqwertyqwertyqwertyqwerty Shifrotekst њ њ ѓ EЉњЌЃ Ћ EЌћ W R џ BT љ T ќ њ ѓ ЃOY њ љ W љ џ Vidkritij tekst a 11100000 Klyuch q 01110001 Shifrotekst 10010001 po pravilu 0 0 0 0 1 1 1 0 1 1 1 0KriptoanalizKriptoanaliz shifru XOR analogichnij kriptoanalizu shifra Vizhenera She efektivnisha ataka z vidomim vidkritim tekstom u razi yaksho vidomo chastinu vidkritogo tekstu Dlya privedenogo prikladu yaksho stalo vidomo sho povidomlennya pochinayetsya zi slova algoritm algoritm XOR њ њ ѓ qwertyqw Takim chinom klyuch vidnovleno Yaksho vikoristovuyetsya klyuch dovzhinoyu yak najmenshe rivnij dovzhini povidomlennya to shifr XOR staye znachno bilsh kriptostijkim nizh pri vikoristanni klyucha sho povtoryuyetsya U razi yaksho dlya utvorennya takogo klyucha vikoristovuyetsya generator psevdovipadkovih chisel to rezultatom bude potokovij shifr Yaksho dlya utvorennya klyucha vikoristovuyetsya to u comu razi mi mayemo spravu z shifrom Vernama yedinoyu kriptografichnoyu sistemoyu dlya yakoyi teoretichno dovedena PosilannyaGenadij Gulak Volodimir Buryachok Pavlo Skladannij Shvidkij algoritm generaciyi pidstanovok bagatoalfavitnoyi zamini