Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
Lucifer — дослідний проєкт фірми IBM 1970-х років по створенню криптостійкого блокового шифру. Результати дослідження привели до створення двох методів побудови стійких до злому симетричних шифрів — мережі Фейстеля і підстановлювально-переустановленої мережі. «Люцифер» заклав основи сучасної симетричної криптографії. У проєкті брали участь Хорст Фейстель (англ. Horst Feistel) і Дон Копперсміт (англ. Don Coppersmith), які згодом стали відомими криптографами. Розвиток «Люцифера» призвів до створення алгоритму DES.
| Розробники | Хорст Фейстель |
|---|---|
| Уперше оприлюднений | 1971 - 1973 рік |
| Раундів | 16 |
| Тип | Мережа Фейстеля |
Історія
Перша версія алгоритму від 1971 року використовувала блоки й ключі довжиною по 48 біт і ґрунтувалася на SP-мережах. Подальша модифікація алгоритму була запатентована в листопаді того ж року (U.S. Patent 3,796,830; Nov 1971) і використовувала мережу Фейстеля. У патенті міститься опис як власне самого алгоритму, так і мережі Фейстеля. У цьому шифрі використовувалися 64-розрядні ключі і 32-бітові блоки. І, нарешті, остання версія запропонована в 1973 році і оперувала з 128-бітними блоками і ключами. Шифр 1977-му році став національним стандартом Сполучених Штатів і широко відомий в світі під абревіатурою DES. За подібною схемою побудовані всі найсильніші з сучасних несекретних криптографічних алгоритмів, і ця архітектура блокових шифрів отримала назву «мережа Файстеля» в честь свого творця.
Хорст Фейстель зазначав про роль шифрування:
Традиційно людьми, які найбільше потребують секретності, були військові та дипломати. В їх роботі часто необхідні елементи несподіванки, а несподіванка такого роду завжди передбачає таємність. Що стосується звичайних людей, то яку б потребу в секретності вони не відчували, це залишалося їх особистою проблемою і рідко виносилося на публічне обговорення; коханці і злодії завжди самі, як могли забезпечували свої потреби в секретній комунікації. Це положення справ мало змінилося до самої середини XIX століття — як раз приблизно в той час для вдосконалення техніки таємного листа були залучені наукові методи й способи мислення. Попри це, аж до нашого століття способи, використані для секретної комунікації, продовжували залишатися процедурами, які виконували за допомогою олівця і паперу.— Хорст Фейстель
Перша версія
Структура алгоритму Люцифер зразка червня 1971 ріку являє собою SP-мережа (або підстановлювально-перестановлену мережу) — «сендвіч» з шарів двох типів, які використовуються по черзі. Перший тип шару — P-блок розрядності 128 біт, за ним йде другий шар, що має 32 модулі, кожен з яких складається з двох 4-бітних S-блоків, чиї відповідні входи закорочені й на них подається одне і те ж значення з виходу попереднього шару. Але самі блоки підставляння різні (відрізняються таблицями замін). На вихід модуля подаються значення тільки з одного з S-блоків, якого конкретно — визначається одним з бітів в ключі, номер якого відповідав номеру S-блоку в структурі. У схемі використовується 16 модулів вибору S-блоків (всього 32 S-блоку), таким чином така схема використовує 16-бітний ключ.
Розглянемо тепер, як буде змінюватися шифротекст в наведеному вище алгоритмі при зміні всього одного біта. Для простоти візьмемо таблиці замін S-блоків такими, що якщо на вхід S-блоку подаються всі нулі, то і на виході будуть всі нулі. У реальних системах такі таблиці замін не використовуються, оскільки вони сильно спрощують роботу криптоаналітика, але в даному прикладі вони наочно ілюструють сильний міжсимвольний взаємозв'язок при зміні одного біта повідомлення, яке шифрується. Видно, що завдяки першому P-блоку єдина одиниця зсувається в центр блоку, потім наступний нелінійний S-блок «розмножує» її і вже дві одиниці користуючись з наступного P-блоку змінюють своє положення і т. д. В кінці пристрою шифрування, завдяки сильному міжсимвольному зв'язку, вихідні біти стали складною функцією від вхідних і від застосованого ключа. В середньому, на виході половина біт буде дорівнює «0» і половина — «1».
Друга й третя версії
У наступній версії алгоритму замість SP-мережі використовувалася мережа Фейстеля. За своєю суттю мережа Фейстеля є альтернативою SP-мереж і використовується набагато ширше. З теоретичної точки зору раундова функція шифрування може бути зведена до SP-мережі, однак мережа Фейстеля є більш практичною, через те, що шифрування і розшифрування може вестися одним і тим же пристроєм, але зі зворотним порядком застосованих ключів. Друга й третя версія алгоритму (використовують мережу Фейстеля) оперували над 32-бітними блоками з 64-бітовим ключем і 128-бітними блоками з 128-бітними ключами. В останній (третій) версії раундова функція шифрування була влаштована дуже просто — спочатку зашифрований підблок пропускався через шар 4-бітних S-блоків (аналогічно верствам в SP-мережах, тільки S-блок є сталим і не залежить від ключа), потім до нього по модулю 2 додавався раундовий ключ, після чого результат пропускався через P-блок.
Криптоаналіз варіантів алгоритму
Будь-які криптоаналітичні роботи, присвячені варіантам № 1 і № 2 алгоритму Lucifer, не отримали широку популярність. Двом останнім варіантам «пощастило» більше; відомі такі результати їх криптоаналізу.
У 1991 році Елі Біхам і Аді Шамір досліджували варіант № 3 . Для визначеності вони використовували перестановку Р з алгоритму DES, а як таблиці S0 і Si були взяті рядки 3 і 4 таблиці замін S {алгоритму DES}. З 8-раундовим варіантом № 3 з 32-бітовим блоком, розкривається при наявності всього 24 обраних відкритих текстів і відповідних їм шифртекст шляхом виконання порядку 221 тестових операцій шифрування.
У тій же роботі Біхам і Шамір описали можливу атаку на аналогічний алгоритм з 128-бітовим блоком, для успішного здійснення якої потрібно 60-70 обраних відкритих текстів і порядку 253 операцій шифрування.
Крім того, Біхам і Шамір стверджували, що варіант № 4 є ще слабшим.
Останнє твердження було доведено в роботі, яку опублікували Ішаі Бен-Аройо і Елі Біхам в 1993 році. У ній змальована атака на варіант № 4 алгоритму Lucifer, в якому виявилося підмножина ключів, яка мала ризиковий результат: близько 55 % всіх можливих значень ключа, слабких до диференціального криптоаналізу. При використанні ключа шифрування з даної підмножини алгоритм розкривається при наявності 236 обраних відкритих текстів.
Примітки
- . Архів оригіналу за 11 березня 2018. Процитовано 10 квітня 2018.
- . Архів оригіналу за 6 квітня 2018. Процитовано 10 квітня 2018.
Посилання
- Хорст Файстель. Криптография и компьютерная безопасность [ 11 березня 2018 у Wayback Machine.]
- Алгоритм Lucifer [ 6 квітня 2018 у Wayback Machine.]
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Lucifer doslidnij proyekt firmi IBM 1970 h rokiv po stvorennyu kriptostijkogo blokovogo shifru Rezultati doslidzhennya priveli do stvorennya dvoh metodiv pobudovi stijkih do zlomu simetrichnih shifriv merezhi Fejstelya i pidstanovlyuvalno pereustanovlenoyi merezhi Lyucifer zaklav osnovi suchasnoyi simetrichnoyi kriptografiyi U proyekti brali uchast Horst Fejstel angl Horst Feistel i Don Koppersmit angl Don Coppersmith yaki zgodom stali vidomimi kriptografami Rozvitok Lyucifera prizviv do stvorennya algoritmu DES LuciferRozrobniki Horst FejstelUpershe oprilyudnenij 1971 1973 rikRaundiv 16Tip Merezha FejstelyaIstoriyaPersha versiya algoritmu vid 1971 roku vikoristovuvala bloki j klyuchi dovzhinoyu po 48 bit i gruntuvalasya na SP merezhah Podalsha modifikaciya algoritmu bula zapatentovana v listopadi togo zh roku U S Patent 3 796 830 Nov 1971 i vikoristovuvala merezhu Fejstelya U patenti mistitsya opis yak vlasne samogo algoritmu tak i merezhi Fejstelya U comu shifri vikoristovuvalisya 64 rozryadni klyuchi i 32 bitovi bloki I nareshti ostannya versiya zaproponovana v 1973 roci i operuvala z 128 bitnimi blokami i klyuchami Shifr 1977 mu roci stav nacionalnim standartom Spoluchenih Shtativ i shiroko vidomij v sviti pid abreviaturoyu DES Za podibnoyu shemoyu pobudovani vsi najsilnishi z suchasnih nesekretnih kriptografichnih algoritmiv i cya arhitektura blokovih shifriv otrimala nazvu merezha Fajstelya v chest svogo tvorcya Horst Fejstel zaznachav pro rol shifruvannya Tradicijno lyudmi yaki najbilshe potrebuyut sekretnosti buli vijskovi ta diplomati V yih roboti chasto neobhidni elementi nespodivanki a nespodivanka takogo rodu zavzhdi peredbachaye tayemnist Sho stosuyetsya zvichajnih lyudej to yaku b potrebu v sekretnosti voni ne vidchuvali ce zalishalosya yih osobistoyu problemoyu i ridko vinosilosya na publichne obgovorennya kohanci i zlodiyi zavzhdi sami yak mogli zabezpechuvali svoyi potrebi v sekretnij komunikaciyi Ce polozhennya sprav malo zminilosya do samoyi seredini XIX stolittya yak raz priblizno v toj chas dlya vdoskonalennya tehniki tayemnogo lista buli zalucheni naukovi metodi j sposobi mislennya Popri ce azh do nashogo stolittya sposobi vikoristani dlya sekretnoyi komunikaciyi prodovzhuvali zalishatisya procedurami yaki vikonuvali za dopomogoyu olivcya i paperu Horst FejstelPersha versiyaStruktura algoritmu Lyucifer zrazka chervnya 1971 riku yavlyaye soboyu SP merezha abo pidstanovlyuvalno perestanovlenu merezhu sendvich z shariv dvoh tipiv yaki vikoristovuyutsya po cherzi Pershij tip sharu P blok rozryadnosti 128 bit za nim jde drugij shar sho maye 32 moduli kozhen z yakih skladayetsya z dvoh 4 bitnih S blokiv chiyi vidpovidni vhodi zakorocheni j na nih podayetsya odne i te zh znachennya z vihodu poperednogo sharu Ale sami bloki pidstavlyannya rizni vidriznyayutsya tablicyami zamin Na vihid modulya podayutsya znachennya tilki z odnogo z S blokiv yakogo konkretno viznachayetsya odnim z bitiv v klyuchi nomer yakogo vidpovidav nomeru S bloku v strukturi U shemi vikoristovuyetsya 16 moduliv viboru S blokiv vsogo 32 S bloku takim chinom taka shema vikoristovuye 16 bitnij klyuch Rozglyanemo teper yak bude zminyuvatisya shifrotekst v navedenomu vishe algoritmi pri zmini vsogo odnogo bita Dlya prostoti vizmemo tablici zamin S blokiv takimi sho yaksho na vhid S bloku podayutsya vsi nuli to i na vihodi budut vsi nuli U realnih sistemah taki tablici zamin ne vikoristovuyutsya oskilki voni silno sproshuyut robotu kriptoanalitika ale v danomu prikladi voni naochno ilyustruyut silnij mizhsimvolnij vzayemozv yazok pri zmini odnogo bita povidomlennya yake shifruyetsya Vidno sho zavdyaki pershomu P bloku yedina odinicya zsuvayetsya v centr bloku potim nastupnij nelinijnij S blok rozmnozhuye yiyi i vzhe dvi odinici koristuyuchis z nastupnogo P bloku zminyuyut svoye polozhennya i t d V kinci pristroyu shifruvannya zavdyaki silnomu mizhsimvolnomu zv yazku vihidni biti stali skladnoyu funkciyeyu vid vhidnih i vid zastosovanogo klyucha V serednomu na vihodi polovina bit bude dorivnyuye 0 i polovina 1 Druga j tretya versiyiU nastupnij versiyi algoritmu zamist SP merezhi vikoristovuvalasya merezha Fejstelya Za svoyeyu suttyu merezha Fejstelya ye alternativoyu SP merezh i vikoristovuyetsya nabagato shirshe Z teoretichnoyi tochki zoru raundova funkciya shifruvannya mozhe buti zvedena do SP merezhi odnak merezha Fejstelya ye bilsh praktichnoyu cherez te sho shifruvannya i rozshifruvannya mozhe vestisya odnim i tim zhe pristroyem ale zi zvorotnim poryadkom zastosovanih klyuchiv Druga j tretya versiya algoritmu vikoristovuyut merezhu Fejstelya operuvali nad 32 bitnimi blokami z 64 bitovim klyuchem i 128 bitnimi blokami z 128 bitnimi klyuchami V ostannij tretij versiyi raundova funkciya shifruvannya bula vlashtovana duzhe prosto spochatku zashifrovanij pidblok propuskavsya cherez shar 4 bitnih S blokiv analogichno verstvam v SP merezhah tilki S blok ye stalim i ne zalezhit vid klyucha potim do nogo po modulyu 2 dodavavsya raundovij klyuch pislya chogo rezultat propuskavsya cherez P blok Kriptoanaliz variantiv algoritmuBud yaki kriptoanalitichni roboti prisvyacheni variantam 1 i 2 algoritmu Lucifer ne otrimali shiroku populyarnist Dvom ostannim variantam poshastilo bilshe vidomi taki rezultati yih kriptoanalizu U 1991 roci Eli Biham i Adi Shamir doslidzhuvali variant 3 Dlya viznachenosti voni vikoristovuvali perestanovku R z algoritmu DES a yak tablici S0 i Si buli vzyati ryadki 3 i 4 tablici zamin S algoritmu DES Z 8 raundovim variantom 3 z 32 bitovim blokom rozkrivayetsya pri nayavnosti vsogo 24 obranih vidkritih tekstiv i vidpovidnih yim shifrtekst shlyahom vikonannya poryadku 221 testovih operacij shifruvannya U tij zhe roboti Biham i Shamir opisali mozhlivu ataku na analogichnij algoritm z 128 bitovim blokom dlya uspishnogo zdijsnennya yakoyi potribno 60 70 obranih vidkritih tekstiv i poryadku 253 operacij shifruvannya Krim togo Biham i Shamir stverdzhuvali sho variant 4 ye she slabshim Ostannye tverdzhennya bulo dovedeno v roboti yaku opublikuvali Ishai Ben Arojo i Eli Biham v 1993 roci U nij zmalovana ataka na variant 4 algoritmu Lucifer v yakomu viyavilosya pidmnozhina klyuchiv yaka mala rizikovij rezultat blizko 55 vsih mozhlivih znachen klyucha slabkih do diferencialnogo kriptoanalizu Pri vikoristanni klyucha shifruvannya z danoyi pidmnozhini algoritm rozkrivayetsya pri nayavnosti 236 obranih vidkritih tekstiv Primitki Arhiv originalu za 11 bereznya 2018 Procitovano 10 kvitnya 2018 Arhiv originalu za 6 kvitnya 2018 Procitovano 10 kvitnya 2018 PosilannyaHorst Fajstel Kriptografiya i kompyuternaya bezopasnost 11 bereznya 2018 u Wayback Machine Algoritm Lucifer 6 kvitnya 2018 u Wayback Machine