www.wikidata.uk-ua.nina.az

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

Шифр XOR

Шифр 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. Ініціалізація змінних
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. Генадій Гулак, Володимир Бурячок, Павло Складанний - Швидкий алгоритм генерації підстановок багатоалфавітної заміни. 
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
Shifr XOR algoritm shifruvannya yakij yak klyuch vikoristovuye klyuchove slovo ta mozhe buti zapisanij formuloyuCi Pi XOR Kj de Kj j ta litera klyuchovogo slova predstavlena v koduvanni ASCII Klyuchove slovo povtoryuyetsya poki ne otrimano gamu rivnu dovzhini povidomlennya Zmist 1 Istoriya 2 Na osnovi GPVCh 3 Vikoristannya 4 Priklad 5 Kriptoanaliz 6 PosilannyaIstoriya red Nabuv 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 GPVCh red Nehaj S displaystyle S nbsp vnutrishnij stan GPVCh g K displaystyle g K nbsp funkciya peretvorennya stanu f K displaystyle f K nbsp funkciya shifruvannya nbsp 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 nbsp generatora Cej vnutrishnij stan peretvoryuyetsya funkciyeyu peretvorennya stanu g K displaystyle g K nbsp pislya kozhnogo kroku shifruvannya Generator skladayetsya z komponentiv S displaystyle S nbsp ta g K displaystyle g K nbsp Bezpechnist takogo shifru zalezhit vid chisla vnutrishnih staniv S displaystyle S nbsp j skladnosti funkciyi peretvorennya g K displaystyle g K nbsp Vidpovidno harakteristiki poslidovnih shifriv zalezhat vid vlastivostej generatoriv psevdovipadkovih chisel Z inshoyi storoni sama funkciya shifruvannya f K displaystyle f K nbsp 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 nbsp komirok pam yati todi vin mozhe prijmati 2 n displaystyle 2 n nbsp riznih vnutrishnih staniv S displaystyle S nbsp Funkciya peretvorennya staniv g K displaystyle g K nbsp 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 nbsp 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 nbsp ye prostim chislom napriklad pri m 3 2 3 1 7 displaystyle m 3 quad 2 3 1 7 nbsp to filtrovana poslidovnist mozhe mati period 2 m 1 displaystyle 2 m 1 nbsp pri vibori strukturi zsuvovogo registru u vidpovidnosti iz nezvidnim trivialnim mnogochlenom h X displaystyle h X nbsp stepeni m displaystyle m nbsp Do takih m displaystyle m nbsp 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 nbsp iz logichnoyu kombinaciyeyu kon yunkciyi vihidnih signaliv dvoh inshih kaskadiv S j displaystyle S j nbsp ta S k displaystyle S k nbsp 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 nbsp 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 nbsp 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 Vikoristannya red Dzherelom gami shifru mozhe buti blokovij shifr yakij pracyuye u rezhimi zvorotnogo zv yazku j na osnovi diyuchogo klyucha K displaystyle K nbsp ta vektoru inicializaciyi I V displaystyle IV nbsp Yaksho NSD chisel n d N displaystyle n delta in mathbb N nbsp n gt 1 n d 1 displaystyle n gt 1 n delta 1 nbsp to l Z n displaystyle forall l in mathbb Z n nbsp u rivnyannil k d x k m o d n displaystyle l k cdot delta x k mathrm mod n nbsp dlya riznih k Z n displaystyle k in mathbb Z n nbsp usi znachennya x k Z n displaystyle x k in mathbb Z n nbsp ye riznimi Nehaj k 1 k 2 displaystyle k 1 neq k 2 nbsp ale x 1 x 2 displaystyle x 1 x 2 nbsp Todil 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 nbsp abo k 1 k 2 d 0 m o d n displaystyle k 1 k 2 cdot delta 0 mathrm mod n nbsp Ostannye superechit vimozi vzayemnoyi prostoti chisel n d 1 displaystyle n delta 1 nbsp tobto k 1 k 2 x 1 x 2 displaystyle forall k 1 neq k 2 Rightarrow x 1 neq x 2 nbsp Algoritm generaciyi pidstanovki stepeni n displaystyle n nbsp 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 nbsp 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 nbsp Vibir velichini n displaystyle n nbsp 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 nbsp de m 2 4 8 displaystyle m 2 4 8 nbsp Koeficiyent imitostijkosti dlya n 2 2 displaystyle n 2 2 nbsp ye najmenshim a zastosuvannya n 2 8 256 displaystyle n 2 8 256 nbsp 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 nbsp de p i j P i j i j 1 n displaystyle p ij P i j i j overline 1 n nbsp umovna jmovirnistpoyavi na vihodi vuzla znaku j displaystyle j nbsp v razi nadhodzhennya znaku i displaystyle i nbsp X i displaystyle bar X i nbsp pidstanovochna matricya yaka vidpovidaye generovanij pidstanovci X i S n displaystyle X i in S n nbsp 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 nbsp ye nezalezhnoyu u sukupnosti ta maye rivnomirnij rozpodil algoritm zabezpechuye formuvannya S n displaystyle S n nbsp simetrichnoyi grupi pidstanovok stepeni n displaystyle n nbsp Jmovirnist poyavi poslidovnosti j 0 j 1 j n 1 Z n displaystyle j 0 j 1 j n 1 in mathbb Z n nbsp 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 nbsp 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 nbsp 1 Krok Formalnij opis Komentar1 k j k m 1 A displaystyle k j k m 1 mathcal A emptyset nbsp Inicializaciya zminnih2 x k j m displaystyle x k j m nbsp Viznachennya chergovogo perehodu3 A A x k displaystyle mathcal A mathcal A cup x k nbsp Perelik viznachenih perehodiv 4 k k 1 m o d n displaystyle k k 1 mathrm mod n nbsp Nomer nastupnogo perehodu5 m m 1 displaystyle m m 1 nbsp Nomer chergovogo vipadkovogo chisla6 Yaksho m n displaystyle m n nbsp to vikonuyetsya krok 10 yaksho ni krok 7 Umovnij perehid u kinec 7 Yaksho j m A displaystyle j m notin mathcal A nbsp 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 nbsp 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 nbsp Zavershennya roboti algoritmu Priklad red Vidkritij 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 11100000Klyuch q 01110001Shifrotekst 10010001po pravilu 0 0 0 0 1 1 1 0 1 1 1 0Kriptoanaliz red Kriptoanaliz 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 generator istinno vipadkovih chisel to u comu razi mi mayemo spravu z shifrom Vernama yedinoyu kriptografichnoyu sistemoyu dlya yakoyi teoretichno dovedena absolyutna kriptografichna stijkist Posilannya red shifr Ksor Genadij Gulak Volodimir Buryachok Pavlo Skladannij Shvidkij algoritm generaciyi pidstanovok bagatoalfavitnoyi zamini Otrimano z https uk wikipedia org w index php title Shifr XOR amp oldid 38224872