Шифр Гілла — поліграмний шифр підстановки, заснований на лінійній алгебрі. Лестер Гілл винайшов цей шифр в 1929, і це був перший шифр, який дозволяв на практиці (хоча і з труднощами) оперувати більш ніж з трьома символами за раз. Подальше обговорення шифру передбачає початкові знання матриць.
Шифрування
Кожній букві спершу зіставляється число. Для латинського алфавіту часто використовується найпростіша схема: A = 0, B = 1, …, Z = 25, але це не є істотною властивістю шифру. Блок з n букв розглядається як n-мірний вектор і множиться на n × n матрицю по модулю 26. (Якщо як основа модуля використовується число більше ніж 26, то можна використовувати іншу числову схему для зіставлення буквах чисел і додати прогалини і знаки пунктуації.) Матриця повністю є ключем шифру. Матриця повинна бути оборотною в , щоб була можлива операція розшифрування.
У наступних прикладах використовуються латинські літери від A до Z, відповідні їм чисельні значення наведені в таблиці.
A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 |
Розглянемо повідомлення 'DOG' і представлений нижче ключ (GYBNQKURP в буквеному вигляді):
Оскільки букві 'D' відповідає число 3, 'O' — 14, 'G' — 6, то повідомлення — це вектор
Тоді зашифрований вектор буде
що відповідає шифротексту 'WLY'. Тепер припустимо, що наше повідомлення було 'GOD' або
Тепер зашифрований вектор буде
що відповідає шифротексту 'LUN'. Видно, що кожна буква шифротекста змінилася. Шифр Гілла досяг дифузії по Шеннону, і n-розмірний шифр Гілла може досягати дифузії n символів за раз.
Розшифрування
Для того, щоб розшифрувати повідомлення, необхідно звернути шифротекст назад в вектор і потім просто помножити на зворотню матрицю ключа (IFKVIVVMI в буквеному вигляді). (Існують стандартні методи обчислення зворотніх матриць, дивіться для подробиць.) В зворотна матриця до використаної в прикладі шифрування буде
Візьмемо шифротекст з попереднього прикладу 'WLY'. Тоді ми отримаємо
що повертає нас до повідомлення 'DOG', як ми й розраховували.
Необхідно обговорити деякі складнощі, пов'язані з вибором шифрувальної матриці. Не всі матриці мають обернену (див. Обернена матриця). Матриця матиме обернену в тому і тільки в тому випадку, коли її детермінант не дорівнює нулю і не має спільних дільників з основою модуля. Таким чином, якщо ми працюємо з основою модуля 26 як в прикладах вище, то детермінант повинен бути ненульовим і не ділитися на 2 і 13. Якщо детермінант матриці дорівнює нулю або має спільні дільники з основою модуля, то така матриця не може використовуватися в шифрі Гілла, і повинна бути обрана інша матриця (в іншому випадку шифротекст буде неможливо розшифрувати). Однак, матриці, які задовольняють вищенаведеним умовам, існують в достатку.
Детермінант матриці з прикладу:
Отже, детермінант дорівнює 25 по модулю 26. Так число 25 не має спільних дільників з числом 26, то матриця з таким детермінантом може використовуватися в шифрі Гілла.
Небезпека того, що детермінант матриці ключа буде мати загальні дільники з основою модуля може бути усунена шляхом вибирання простого числа як основи модуля. Наприклад, в більш зручному варіанті шифру Гілла в алфавіт додають 3 додаткових символи (такі як пробіл, крапка і знак питання), щоб збільшити основу модуля до 29.
Криптостійкість
На жаль, стандартний шифр Гілла вразливий до атаки по обраному відкритому тексту, тому що він повністю лінійний. Криптоаналітик, який перехопить пар символ повідомлення / символ шифротекста зможе скласти систему лінійних рівнянь, яку зазвичай не складно вирішити. Якщо виявиться, що система не вирішувана, то необхідно всього лише додати ще кілька пар символ повідомлення/символ шифротекста. Такого роду розрахунки засобами звичайних алгоритмів лінійної алгебри вимагає зовсім небагато часу.
Довжина ключа
Довжина ключа — це двійковий логарифм від кількості всіх можливих ключів. Існує матриць розміру n × n. Значить, або приблизно — верхня грань довжини ключа для шифру Гілла, що використовує матриці n × n. Це тільки верхня грань, оскільки не кожна матриця обернена, а тільки такі матриці можуть бути ключем. Кількість обернених матриць може бути розрахована за допомогою Китайської теореми про залишки. Тобто матриця обернена по модулю 26 тоді і тільки тоді, коли вона обернена і по модулю 2 і по модулю 13. Кількість обернених по модулю 2 матриць розміру n × n одно порядку лінійної групи GL (n, 'Z' 2 ). Це
Аналогічно, кількість обернених по модулю 13 матриць (тобто Порядок GL (n,Z13)) рівно
Кількість обернених по модулю 26 матриць дорівнює добутку цих двох чисел. значить,
Крім того, буде розумно уникати занадто великої кількості нулів у матриці-ключі, оскільки вони зменшують дифузію. У підсумку виходить, що ефективний простір ключів стандартного шифру Гілла становить близько . Для шифру Гілла 5 × 5 це складе приблизно 114 біт. Очевидно, повний перебір — не найефективніша атака на шифр Гілла.
Механічна реалізація
При роботі з двома символами за раз, шифр Гілла не надає ніяких конкретних переваг перед шифром Плейфера, і навіть поступається йому за криптостійкістю і простоті обчислень на папері. У міру збільшення розмірності ключа шифр швидко стає недоступним для розрахунків на папері людиною. Шифр Гілла розмірності 6 був реалізований механічно. Гілл з партнером отримали патент на цей пристрій (U.S. Patent 1,845,947), які виконувало множення матриці 6 × 6 по модулю 26 за допомогою системи шестерень і ланцюгів. Розташування шестерень (а значить і ключ) не можна було змінювати для конкретного пристрою, тому з метою безпеки рекомендувалося потрійне шифрування. Така комбінація була дуже сильною для 1929 року, і вона показує, що Гілл безсумнівно розумів концепції конфузії і дифузії. Його машина не мала успіху.
Примітки
Ця стаття не містить . (квітень 2015) |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Shifr Gilla poligramnij shifr pidstanovki zasnovanij na linijnij algebri Lester Gill vinajshov cej shifr v 1929 i ce buv pershij shifr yakij dozvolyav na praktici hocha i z trudnoshami operuvati bilsh nizh z troma simvolami za raz Podalshe obgovorennya shifru peredbachaye pochatkovi znannya matric ShifruvannyaKozhnij bukvi spershu zistavlyayetsya chislo Dlya latinskogo alfavitu chasto vikoristovuyetsya najprostisha shema A 0 B 1 Z 25 ale ce ne ye istotnoyu vlastivistyu shifru Blok z n bukv rozglyadayetsya yak n mirnij vektor i mnozhitsya na n n matricyu po modulyu 26 Yaksho yak osnova modulya vikoristovuyetsya chislo bilshe nizh 26 to mozhna vikoristovuvati inshu chislovu shemu dlya zistavlennya bukvah chisel i dodati progalini i znaki punktuaciyi Matricya povnistyu ye klyuchem shifru Matricya povinna buti oborotnoyu v Z 26 n displaystyle mathbb Z 26 n shob bula mozhliva operaciya rozshifruvannya U nastupnih prikladah vikoristovuyutsya latinski literi vid A do Z vidpovidni yim chiselni znachennya navedeni v tablici A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 Rozglyanemo povidomlennya DOG i predstavlenij nizhche klyuch GYBNQKURP v bukvenomu viglyadi 6 24 1 13 16 10 20 17 15 displaystyle begin pmatrix 6 amp 24 amp 1 13 amp 16 amp 10 20 amp 17 amp 15 end pmatrix Oskilki bukvi D vidpovidaye chislo 3 O 14 G 6 to povidomlennya ce vektor 3 14 6 displaystyle begin pmatrix 3 14 6 end pmatrix Todi zashifrovanij vektor bude 6 24 1 13 16 10 20 17 15 3 14 6 360 323 388 22 11 24 mod 26 displaystyle begin pmatrix 6 amp 24 amp 1 13 amp 16 amp 10 20 amp 17 amp 15 end pmatrix begin pmatrix 3 14 6 end pmatrix begin pmatrix 360 323 388 end pmatrix equiv begin pmatrix 22 11 24 end pmatrix pmod 26 sho vidpovidaye shifrotekstu WLY Teper pripustimo sho nashe povidomlennya bulo GOD abo 6 14 3 displaystyle begin pmatrix 6 14 3 end pmatrix Teper zashifrovanij vektor bude 6 24 1 13 16 10 20 17 15 6 14 3 375 332 403 11 20 13 mod 26 displaystyle begin pmatrix 6 amp 24 amp 1 13 amp 16 amp 10 20 amp 17 amp 15 end pmatrix begin pmatrix 6 14 3 end pmatrix equiv begin pmatrix 375 332 403 end pmatrix equiv begin pmatrix 11 20 13 end pmatrix pmod 26 sho vidpovidaye shifrotekstu LUN Vidno sho kozhna bukva shifroteksta zminilasya Shifr Gilla dosyag difuziyi po Shennonu i n rozmirnij shifr Gilla mozhe dosyagati difuziyi n simvoliv za raz RozshifruvannyaDlya togo shob rozshifruvati povidomlennya neobhidno zvernuti shifrotekst nazad v vektor i potim prosto pomnozhiti na zvorotnyu matricyu klyucha IFKVIVVMI v bukvenomu viglyadi Isnuyut standartni metodi obchislennya zvorotnih matric divitsya dlya podrobic V Z 26 n displaystyle mathbb Z 26 n zvorotna matricya do vikoristanoyi v prikladi shifruvannya bude 8 5 10 21 8 21 21 12 8 displaystyle begin pmatrix 8 amp 5 amp 10 21 amp 8 amp 21 21 amp 12 amp 8 end pmatrix Vizmemo shifrotekst z poperednogo prikladu WLY Todi mi otrimayemo 8 5 10 21 8 21 21 12 8 22 11 24 471 1054 786 3 14 6 mod 26 displaystyle begin pmatrix 8 amp 5 amp 10 21 amp 8 amp 21 21 amp 12 amp 8 end pmatrix begin pmatrix 22 11 24 end pmatrix equiv begin pmatrix 471 1054 786 end pmatrix equiv begin pmatrix 3 14 6 end pmatrix pmod 26 sho povertaye nas do povidomlennya DOG yak mi j rozrahovuvali Neobhidno obgovoriti deyaki skladnoshi pov yazani z viborom shifruvalnoyi matrici Ne vsi matrici mayut obernenu div Obernena matricya Matricya matime obernenu v tomu i tilki v tomu vipadku koli yiyi determinant ne dorivnyuye nulyu i ne maye spilnih dilnikiv z osnovoyu modulya Takim chinom yaksho mi pracyuyemo z osnovoyu modulya 26 yak v prikladah vishe to determinant povinen buti nenulovim i ne dilitisya na 2 i 13 Yaksho determinant matrici dorivnyuye nulyu abo maye spilni dilniki z osnovoyu modulya to taka matricya ne mozhe vikoristovuvatisya v shifri Gilla i povinna buti obrana insha matricya v inshomu vipadku shifrotekst bude nemozhlivo rozshifruvati Odnak matrici yaki zadovolnyayut vishenavedenim umovam isnuyut v dostatku Determinant matrici z prikladu 6 24 1 13 16 10 20 17 15 6 16 15 10 17 24 13 15 10 20 1 13 17 16 20 441 25 mod 26 displaystyle begin vmatrix 6 amp 24 amp 1 13 amp 16 amp 10 20 amp 17 amp 15 end vmatrix equiv 6 16 cdot 15 10 cdot 17 24 13 cdot 15 10 cdot 20 1 13 cdot 17 16 cdot 20 equiv 441 equiv 25 pmod 26 Otzhe determinant dorivnyuye 25 po modulyu 26 Tak chislo 25 ne maye spilnih dilnikiv z chislom 26 to matricya z takim determinantom mozhe vikoristovuvatisya v shifri Gilla Nebezpeka togo sho determinant matrici klyucha bude mati zagalni dilniki z osnovoyu modulya mozhe buti usunena shlyahom vibirannya prostogo chisla yak osnovi modulya Napriklad v bilsh zruchnomu varianti shifru Gilla v alfavit dodayut 3 dodatkovih simvoli taki yak probil krapka i znak pitannya shob zbilshiti osnovu modulya do 29 KriptostijkistNa zhal standartnij shifr Gilla vrazlivij do ataki po obranomu vidkritomu tekstu tomu sho vin povnistyu linijnij Kriptoanalitik yakij perehopit n 2 displaystyle n 2 par simvol povidomlennya simvol shifroteksta zmozhe sklasti sistemu linijnih rivnyan yaku zazvichaj ne skladno virishiti Yaksho viyavitsya sho sistema ne virishuvana to neobhidno vsogo lishe dodati she kilka par simvol povidomlennya simvol shifroteksta Takogo rodu rozrahunki zasobami zvichajnih algoritmiv linijnoyi algebri vimagaye zovsim nebagato chasu Dovzhina klyucha Dovzhina klyucha ce dvijkovij logarifm vid kilkosti vsih mozhlivih klyuchiv Isnuye 26 n 2 displaystyle 26 n 2 matric rozmiru n n Znachit log 2 26 n 2 displaystyle log 2 26 n 2 abo priblizno 4 7 n 2 displaystyle 4 7n 2 verhnya gran dovzhini klyucha dlya shifru Gilla sho vikoristovuye matrici n n Ce tilki verhnya gran oskilki ne kozhna matricya obernena a tilki taki matrici mozhut buti klyuchem Kilkist obernenih matric mozhe buti rozrahovana za dopomogoyu Kitajskoyi teoremi pro zalishki Tobto matricya obernena po modulyu 26 todi i tilki todi koli vona obernena i po modulyu 2 i po modulyu 13 Kilkist obernenih po modulyu 2 matric rozmiru n n odno poryadku linijnoyi grupi GL n Z 2 Ce 2 n 2 1 1 2 1 1 2 2 1 1 2 n displaystyle 2 n 2 1 1 2 1 1 2 2 cdots 1 1 2 n Analogichno kilkist obernenih po modulyu 13 matric tobto Poryadok GL n Z13 rivno 13 n 2 1 1 13 1 1 13 2 1 1 13 n displaystyle 13 n 2 1 1 13 1 1 13 2 cdots 1 1 13 n Kilkist obernenih po modulyu 26 matric dorivnyuye dobutku cih dvoh chisel znachit 26 n 2 1 1 2 1 1 2 2 1 1 2 n 1 1 13 1 1 13 2 1 1 13 n displaystyle 26 n 2 1 1 2 1 1 2 2 cdots 1 1 2 n 1 1 13 1 1 13 2 cdots 1 1 13 n Krim togo bude rozumno unikati zanadto velikoyi kilkosti nuliv u matrici klyuchi oskilki voni zmenshuyut difuziyu U pidsumku vihodit sho efektivnij prostir klyuchiv standartnogo shifru Gilla stanovit blizko 4 64 n 2 1 7 displaystyle 4 64n 2 1 7 Dlya shifru Gilla 5 5 ce sklade priblizno 114 bit Ochevidno povnij perebir ne najefektivnisha ataka na shifr Gilla Mehanichna realizaciyaPri roboti z dvoma simvolami za raz shifr Gilla ne nadaye niyakih konkretnih perevag pered shifrom Plejfera i navit postupayetsya jomu za kriptostijkistyu i prostoti obchislen na paperi U miru zbilshennya rozmirnosti klyucha shifr shvidko staye nedostupnim dlya rozrahunkiv na paperi lyudinoyu Shifr Gilla rozmirnosti 6 buv realizovanij mehanichno Gill z partnerom otrimali patent na cej pristrij U S Patent 1 845 947 yaki vikonuvalo mnozhennya matrici 6 6 po modulyu 26 za dopomogoyu sistemi shesteren i lancyugiv Roztashuvannya shesteren a znachit i klyuch ne mozhna bulo zminyuvati dlya konkretnogo pristroyu tomu z metoyu bezpeki rekomenduvalosya potrijne shifruvannya Taka kombinaciya bula duzhe silnoyu dlya 1929 roku i vona pokazuye sho Gill bezsumnivno rozumiv koncepciyi konfuziyi i difuziyi Jogo mashina ne mala uspihu PrimitkiCya stattya ne mistit posilan na dzherela Vi mozhete dopomogti polipshiti cyu stattyu dodavshi posilannya na nadijni avtoritetni dzherela Material bez dzherel mozhe buti piddano sumnivu ta vilucheno kviten 2015