Ларс Рамкільд Кнудсен (англ. Lars Ramkilde Knudsen) (21 лютого 1962) — данський математик і дослідник в області криптографії, професор кафедри математики в Данському технічному університеті. Його дослідження включають в себе розробку й аналіз блочних шифрів, геш-функцій і кодів автентичності повідомлень (MACs).
Ларс Рамкільд Кнудсен | |
---|---|
Lars Ramkilde Knudsen | |
![]() | |
Народився | 21 лютого 1962 (62 роки) |
Країна | ![]() |
Діяльність | криптолог, інформатик, професор |
Alma mater | Оргуський університет |
Галузь | математика |
Заклад | Данський технічний університет[1] Берґенський університет |
Науковий керівник | d |
Аспіранти, докторанти | d[2] d[2] d[2] |
Нагороди | ![]() d (2013) |
Особ. сторінка | www2.mat.dtu.dk/people/Lars.R.Knudsen/ |
Кнудсен — один із засновників криптоаналізу неможливих диференціалів і . Ларс є одним з розробників .
Біографія
Ларс Кнудсен народився 21 лютого 1962 року в Данії. Після короткотривалої роботи в банківській сфері, в 1984 році Ларс вступив в Орхуський університет (англ. Aarhus University). Вивчав математику й інформатику, за порадою свого наукового керівника Айвана Б'єрре Дамгарда (англ. Ivan Bjerre Damgard). За словами Ларса, саме завдяки своєму науковому керівнику, він зробив вибір на користь вивчення диференціального криптоаналізу.
У 1992 році отримав ступінь магістра, а вже в 1994 — ступінь доктора філософії. З 1997 по 2001 рік працював в Бергенському університеті, Норвегія. Був двічі обраний директором Міжнародної асоціації криптографічних досліджень () з січня 2001 року по грудень 2003 року та з січня 2004 року по грудень 2006 року. З 2003 по 2010 рік був помічником редактора журналу з криптології, що є офіційним журналом IACR. Виступав на конференціях і семінарах IACR. Його доповіді прослуховували на 7 наукових конференціях. В даний момент Кнудсен — професор, завідувач кафедри математики в Данському технічному університеті. Очолює групу криптоаналітиків університету і є одним із розробників шифрів, криптографічних протоколів IEEE з криміналістики й безпеки. Один з керівників дослідного центру (Foundations in Cryptology and Security).
Ларс Кнудсен брав активну участь в конкурсі на новий криптостандарт AES. На конкурсі він був єдиним криптоаналітиком, який представляв відразу два проекти: (Норвегія, Канада) і Serpent (Велика Британія, Ізраїль, Норвегія). Казус з тією обставиною, що Кнудсен всюди фігурує як представник Норвегії, пояснюється надзвичайною мобільністю данського вченого, оскільки за кілька останніх років перед конкурсом він встиг попрацювати у Франції, Швейцарії і Бельгії. На момент проведення конкурсу AES Ларс викладав криптологію в університет Бергена, Норвегія.
Відомо також, що його число Ердеша дорівнює 3.
Наукові дослідження
У всьому світі Ларс Кнудсен відомий завдяки знаменитим атакам на шифри SAFER і SQUARE, його роботам з криптоаналізу неможливих диференціалів та інтегрального криптоаналізу. Кнудсен вперше запропонував використовувати усічені диференціали для атак на 6-раундовий DES. Надалі цей метод був використаний і для атак на і SAFER із усіченим числом раундів. Також Ларс розробив шифри і Serpent (останній разом з англійцем Россом Андерсоном і ізраїльтянином Елі Біхамом). Ще однією розробкою Кнудсена є Grøstl, геш-функція, один з п'яти фіналістів конкурсу NIST SHA-3.
Інтегральний криптоаналіз
Інтегральний криптоаналіз — це вид криптоаналізу, який частково можна застосовувати для атак на блочні шифри, засновані на підстановлювально-перестановлювальних мережах. Він був сформульований Ларсом Кнудсеном в процесі пошуку атаки на шифр SQUARE, тому в літературі його часто називають Square-атакою. Метод був розширений і застосований на подібні з Square шифри CRYPTON, Rijndael, і SHARK. Модифікації Square-атаки також були застосовані до шифрів , IDEA, Camellia, , , , SAFER ++, KHAZAD і FOX (зараз званий [en]).
Інтегральний криптоаналіз, побудований на принципі розгляду набору відкритих текстів, в яких одна частина залишається константою, а друга варіюється усіма можливими способами. Наприклад, атака може використовувати набір із 256 відкритих текстів, в яких всі, крім 8 біт, варіюються. Очевидно, що XOR цього набору дорівнює нулю. XOR відповідного набору шифротексту дає нам інформацію про роботу алгоритму шифрування. Такий метод використання великого набору відкритих текстів замість пари, як в диференціальному криптоаналізі, дав назву «інтегральний».
Криптоаналіз неможливих диференціалів
Криптоаналіз неможливих диференціалів є різновидом диференціального криптоаналізу, застосованого до блочних шифрів. У звичайному диференціальному криптоаналізі розглядається різниця, що має деяку кінцеву ймовірність, в криптоаналізі неможливих диференціалів — різниця, що має ймовірність 0, тобто «неможлива».
Ця методика була вперше описана Ларсом Кнудсеном в заявці на конкурс AES по шифру . Назву методиці дали Елі Біхам, і Аді Шамір на конференції CRYPTO'98.
Цей метод знайшов широке застосування і був використаний в атаках на шифри IDEA, , , різновиди Serpent, MARS, Twofish, Rijndael, CRYPTON, [en], Hierocrypt-3, TEA, XTEA, , , Camellia, і .
Атака на шифр SAFER
SAFER K-64 є ітеративно блочним шифром. Алгоритм працює з 64-бітовим блоком і 64-бітових ключем. Кнудсен виявив слабке місце в розподілі ключів. Їх генерація в алгоритмі була зовсім важкою. Першим підключитися має сам ключ користувача. Наступні підключення генеруються процедурою . Операція <<< — циклічний зсув вліво на 3 біти всередині кожного байта ключа.
Константа тримується із формули
, де j — номер байта константи
. Слабкість цього алгоритму полягала в тому, що майже для кожного ключа знайдеться не менше одного (іноді навіть 9) іншого ключа, який при шифруванні якогось іншого повідомлення дає нам той же самий шифрований текст, тобто
. Кнудсен встановив, що число різних відкритих текстів, які шифруються однаковими шифротекстами, приблизно
—
із можливих
текстів. У підсумку за допомогою аналізу від
до
відкритих текстів можна знайти 8 біт вихідного ключа, що складається з 64 біт. Потім цей алгоритм був вдосконалений самим Кнудсеном до SAFER SK-64.
Існує жарт, що SK розшифровується як Stop Knudsen, або в перекладі «Зупинити Кнудсена». Він з'явився внаслідок того, що новий алгоритм робив атаку Кнудсена безуспішною. Насправді, SK розшифровується як Strengthened Key Schedule, що означає «Посилене розширення ключа».
Атака на шифр SQUARE
У 1997 році Ларс Кнудсен разом зі своїми колегами Йоаном Дайменом (англ. Joan Daemen) і Вінсентом Рейменом (англ. Vincent Rijmen) розробили атаку на блочний шифр SQUARE. Сам алгоритм складався із 6 раундів, що включають 4 операції, лінійне перетворення рядків, нелінійну заміну байт, транспонування і складання з ключем. Вони вибрали атаку на основі підібраного відкритого тексту. Основна ідея полягала в виборі наборів тексту. Було виявлено, що з 256 обраних відкритих текстів знайдуться два, які однозначно визначать ключ шифрування із переважним успіхом, якби шифр складався із 4 раундів. Потім атака була продовжена на 5 і 6 раунди й успішно завершена, хоча й була неможлива через відсутність сучасних технологій. Тим не менш, вона вважалася актуальною, так як вона вважалася однією з найшвидших.
Геш-функція, заснована на блочному шифрі
У своїй статті «Hash functions based on block ciphers and quaternary codes» («Хеш-функції, засновані на блочних шифрах і четвертинних кодах») Ларс Кнудсен показав, що розробка ефективної хеш-функції з мінімальною вбудованою пам'яттю на основі m — бітного блочного шифру є важким завданням. Більш того, жодна з розглянутих ним геш — функцій не забезпечувала захисту краще, ніж 2m, яку одержано методом «грубої сили». Змінюючи трохи модель (наприклад, шляхом збільшення розміру внутрішньої пам'яті, а також шляхом введення вихідних перетворень), можна отримати функцію стиснення і, таким чином, геш-функцію, для якої безпека може бути доведена на основі ймовірних припущень, сформульованих Кнудсеном. Пропонований ним метод був найкращим на той момент (а саме швидкість шифрування, рівна 1/4 або 4 для гешування одного блоку), так і забезпечував високий рівень безпеки, або більш високу ефективність при тих же рівнях безпеки. Для великого значення вбудованої пам'яті, швидкості близькі до тих, які можуть бути отримані. Крім того, геш-функція забезпечує високий ступінь паралелізму, яка дасть ще більш ефективну реалізацію.
Примітки
- Montenegro A. ORCID Public Data File 2023 — 2023. — doi:10.23640/07243.24204912.V1
- Математичний генеалогічний проєкт — 1997.
- Lars Knudsen. Block Cipher — Analysis, Design and Applications, Ph.D. Thesis, 1994. (PDF). — . з джерела 10 липня 2007. Процитовано 2009-11-26.
- . Архів оригіналу за 12 квітня 2018. Процитовано 14 березня 2022.
- Joan Daemen, Lars Knudsen and Vincent Rijmen. The block cipher Square (PDF/PostScript). — .[недоступне посилання]
- Lars Knudsen and Bart Preneel. Hash functions based on block ciphers and quaternary codes (PDF/PostScript). — .[недоступне посилання]
Література
- Matt Henricksen and Lars R. Knudsen. Cryptanalysis of the CRUSH Hash Function.
- Lars R. Knudsen and Tadayoshi Kohno (1991). Analysis of RMAC.
- Lars Knudsen and Bart Preneel. Hash functions based on block ciphers and quaternary codes.
- Lars Knudsen and Chris J Mitchell. Analysis of 3gpp-MAC and two-key 3gpp-MAC.
- Joan Daemen, Lars Knudsen and Vincent Rijmen. The block cipher Square.
Посилання
Алгоритмы шифрования. Специальный справочник [ 12 квітня 2018 у Wayback Machine.]
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Lars Ramkild Knudsen angl Lars Ramkilde Knudsen 21 lyutogo 1962 19620221 danskij matematik i doslidnik v oblasti kriptografiyi profesor kafedri matematiki v Danskomu tehnichnomu universiteti Jogo doslidzhennya vklyuchayut v sebe rozrobku j analiz blochnih shifriv gesh funkcij i kodiv avtentichnosti povidomlen MACs Lars Ramkild KnudsenLars Ramkilde KnudsenNarodivsya21 lyutogo 1962 1962 02 21 62 roki Krayina DaniyaDiyalnistkriptolog informatik profesorAlma materOrguskij universitetGaluzmatematikaZakladDanskij tehnichnij universitet 1 Bergenskij universitetNaukovij kerivnikdAspiranti doktorantid 2 d 2 d 2 Nagorodid 2013 Osob storinkawww2 mat dtu dk people Lars R Knudsen Lars Knudsen u Vikishovishi Knudsen odin iz zasnovnikiv kriptoanalizu nemozhlivih diferencialiv i Lars ye odnim z rozrobnikiv BiografiyaLars Knudsen narodivsya 21 lyutogo 1962 roku v Daniyi Pislya korotkotrivaloyi roboti v bankivskij sferi v 1984 roci Lars vstupiv v Orhuskij universitet angl Aarhus University Vivchav matematiku j informatiku za poradoyu svogo naukovogo kerivnika Ajvana B yerre Damgarda angl Ivan Bjerre Damgard Za slovami Larsa same zavdyaki svoyemu naukovomu kerivniku vin zrobiv vibir na korist vivchennya diferencialnogo kriptoanalizu U 1992 roci otrimav stupin magistra a vzhe v 1994 stupin doktora filosofiyi Z 1997 po 2001 rik pracyuvav v Bergenskomu universiteti Norvegiya Buv dvichi obranij direktorom Mizhnarodnoyi asociaciyi kriptografichnih doslidzhen z sichnya 2001 roku po gruden 2003 roku ta z sichnya 2004 roku po gruden 2006 roku Z 2003 po 2010 rik buv pomichnikom redaktora zhurnalu z kriptologiyi sho ye oficijnim zhurnalom IACR Vistupav na konferenciyah i seminarah IACR Jogo dopovidi prosluhovuvali na 7 naukovih konferenciyah V danij moment Knudsen profesor zaviduvach kafedri matematiki v Danskomu tehnichnomu universiteti Ocholyuye grupu kriptoanalitikiv universitetu i ye odnim iz rozrobnikiv shifriv kriptografichnih protokoliv IEEE z kriminalistiki j bezpeki Odin z kerivnikiv doslidnogo centru Foundations in Cryptology and Security Lars Knudsen brav aktivnu uchast v konkursi na novij kriptostandart AES Na konkursi vin buv yedinim kriptoanalitikom yakij predstavlyav vidrazu dva proekti Norvegiya Kanada i Serpent Velika Britaniya Izrayil Norvegiya Kazus z tiyeyu obstavinoyu sho Knudsen vsyudi figuruye yak predstavnik Norvegiyi poyasnyuyetsya nadzvichajnoyu mobilnistyu danskogo vchenogo oskilki za kilka ostannih rokiv pered konkursom vin vstig popracyuvati u Franciyi Shvejcariyi i Belgiyi Na moment provedennya konkursu AES Lars vikladav kriptologiyu v universitet Bergena Norvegiya Vidomo takozh sho jogo chislo Erdesha dorivnyuye 3 Naukovi doslidzhennyaU vsomu sviti Lars Knudsen vidomij zavdyaki znamenitim atakam na shifri SAFER i SQUARE jogo robotam z kriptoanalizu nemozhlivih diferencialiv ta integralnogo kriptoanalizu Knudsen vpershe zaproponuvav vikoristovuvati usicheni diferenciali dlya atak na 6 raundovij DES Nadali cej metod buv vikoristanij i dlya atak na i SAFER iz usichenim chislom raundiv Takozh Lars rozrobiv shifri i Serpent ostannij razom z anglijcem Rossom Andersonom i izrayiltyaninom Eli Bihamom She odniyeyu rozrobkoyu Knudsena ye Grostl gesh funkciya odin z p yati finalistiv konkursu NIST SHA 3 Integralnij kriptoanaliz Integralnij kriptoanaliz ce vid kriptoanalizu yakij chastkovo mozhna zastosovuvati dlya atak na blochni shifri zasnovani na pidstanovlyuvalno perestanovlyuvalnih merezhah Vin buv sformulovanij Larsom Knudsenom v procesi poshuku ataki na shifr SQUARE tomu v literaturi jogo chasto nazivayut Square atakoyu Metod buv rozshirenij i zastosovanij na podibni z Square shifri CRYPTON Rijndael i SHARK Modifikaciyi Square ataki takozh buli zastosovani do shifriv IDEA Camellia SAFER KHAZAD i FOX zaraz zvanij en Integralnij kriptoanaliz pobudovanij na principi rozglyadu naboru vidkritih tekstiv v yakih odna chastina zalishayetsya konstantoyu a druga variyuyetsya usima mozhlivimi sposobami Napriklad ataka mozhe vikoristovuvati nabir iz 256 vidkritih tekstiv v yakih vsi krim 8 bit variyuyutsya Ochevidno sho XOR cogo naboru dorivnyuye nulyu XOR vidpovidnogo naboru shifrotekstu daye nam informaciyu pro robotu algoritmu shifruvannya Takij metod vikoristannya velikogo naboru vidkritih tekstiv zamist pari yak v diferencialnomu kriptoanalizi dav nazvu integralnij Kriptoanaliz nemozhlivih diferencialiv Kriptoanaliz nemozhlivih diferencialiv ye riznovidom diferencialnogo kriptoanalizu zastosovanogo do blochnih shifriv U zvichajnomu diferencialnomu kriptoanalizi rozglyadayetsya riznicya sho maye deyaku kincevu jmovirnist v kriptoanalizi nemozhlivih diferencialiv riznicya sho maye jmovirnist 0 tobto nemozhliva Cya metodika bula vpershe opisana Larsom Knudsenom v zayavci na konkurs AES po shifru Nazvu metodici dali Eli Biham i Adi Shamir na konferenciyi CRYPTO 98 Cej metod znajshov shiroke zastosuvannya i buv vikoristanij v atakah na shifri IDEA riznovidi Serpent MARS Twofish Rijndael CRYPTON en Hierocrypt 3 TEA XTEA Camellia i Ataka na shifr SAFER SAFER K 64 ye iterativno blochnim shifrom Algoritm pracyuye z 64 bitovim blokom i 64 bitovih klyuchem Knudsen viyaviv slabke misce v rozpodili klyuchiv Yih generaciya v algoritmi bula zovsim vazhkoyu Pershim pidklyuchitisya maye sam klyuch koristuvacha Nastupni pidklyuchennya generuyutsya proceduroyu Ki 1 Ki lt lt lt 3i ci 1 displaystyle K i 1 left K i lt lt lt 3i right c i 1 Operaciya lt lt lt ciklichnij zsuv vlivo na 3 biti vseredini kozhnogo bajta klyucha Konstanta ci displaystyle c i trimuyetsya iz formuli cij 4545 9i j mod 256 mod 257 mod 257 displaystyle c ij 45 45 9i j mbox mod 256 mbox mod 257 mbox mod 257 de j nomer bajta konstanti ci displaystyle c i Slabkist cogo algoritmu polyagala v tomu sho majzhe dlya kozhnogo klyucha znajdetsya ne menshe odnogo inodi navit 9 inshogo klyucha yakij pri shifruvanni yakogos inshogo povidomlennya daye nam toj zhe samij shifrovanij tekst tobto F M1 K1 F M2 K2 displaystyle F M 1 K 1 F M 2 K 2 Knudsen vstanoviv sho chislo riznih vidkritih tekstiv yaki shifruyutsya odnakovimi shifrotekstami priblizno 222 displaystyle 2 22 228 displaystyle 2 28 iz mozhlivih 264 displaystyle 2 64 tekstiv U pidsumku za dopomogoyu analizu vid 244 displaystyle 2 44 do 247 displaystyle 2 47 vidkritih tekstiv mozhna znajti 8 bit vihidnogo klyucha sho skladayetsya z 64 bit Potim cej algoritm buv vdoskonalenij samim Knudsenom do SAFER SK 64 Isnuye zhart sho SK rozshifrovuyetsya yak Stop Knudsen abo v perekladi Zupiniti Knudsena Vin z yavivsya vnaslidok togo sho novij algoritm robiv ataku Knudsena bezuspishnoyu Naspravdi SK rozshifrovuyetsya yak Strengthened Key Schedule sho oznachaye Posilene rozshirennya klyucha Ataka na shifr SQUARE U 1997 roci Lars Knudsen razom zi svoyimi kolegami Joanom Dajmenom angl Joan Daemen i Vinsentom Rejmenom angl Vincent Rijmen rozrobili ataku na blochnij shifr SQUARE Sam algoritm skladavsya iz 6 raundiv sho vklyuchayut 4 operaciyi linijne peretvorennya ryadkiv nelinijnu zaminu bajt transponuvannya i skladannya z klyuchem Voni vibrali ataku na osnovi pidibranogo vidkritogo tekstu Osnovna ideya polyagala v vibori naboriv tekstu Bulo viyavleno sho z 256 obranih vidkritih tekstiv znajdutsya dva yaki odnoznachno viznachat klyuch shifruvannya iz perevazhnim uspihom yakbi shifr skladavsya iz 4 raundiv Potim ataka bula prodovzhena na 5 i 6 raundi j uspishno zavershena hocha j bula nemozhliva cherez vidsutnist suchasnih tehnologij Tim ne mensh vona vvazhalasya aktualnoyu tak yak vona vvazhalasya odniyeyu z najshvidshih Gesh funkciya zasnovana na blochnomu shifri U svoyij statti Hash functions based on block ciphers and quaternary codes Hesh funkciyi zasnovani na blochnih shifrah i chetvertinnih kodah Lars Knudsen pokazav sho rozrobka efektivnoyi hesh funkciyi z minimalnoyu vbudovanoyu pam yattyu na osnovi m bitnogo blochnogo shifru ye vazhkim zavdannyam Bilsh togo zhodna z rozglyanutih nim gesh funkcij ne zabezpechuvala zahistu krashe nizh 2m yaku oderzhano metodom gruboyi sili Zminyuyuchi trohi model napriklad shlyahom zbilshennya rozmiru vnutrishnoyi pam yati a takozh shlyahom vvedennya vihidnih peretvoren mozhna otrimati funkciyu stisnennya i takim chinom gesh funkciyu dlya yakoyi bezpeka mozhe buti dovedena na osnovi jmovirnih pripushen sformulovanih Knudsenom Proponovanij nim metod buv najkrashim na toj moment a same shvidkist shifruvannya rivna 1 4 abo 4 dlya geshuvannya odnogo bloku tak i zabezpechuvav visokij riven bezpeki abo bilsh visoku efektivnist pri tih zhe rivnyah bezpeki Dlya velikogo znachennya vbudovanoyi pam yati shvidkosti blizki do tih yaki mozhut buti otrimani Krim togo gesh funkciya zabezpechuye visokij stupin paralelizmu yaka dast she bilsh efektivnu realizaciyu PrimitkiMontenegro A ORCID Public Data File 2023 2023 doi 10 23640 07243 24204912 V1 d Track Q123508386 Matematichnij genealogichnij proyekt 1997 d Track Q829984 Lars Knudsen Block Cipher Analysis Design and Applications Ph D Thesis 1994 PDF z dzherela 10 lipnya 2007 Procitovano 2009 11 26 Arhiv originalu za 12 kvitnya 2018 Procitovano 14 bereznya 2022 Joan Daemen Lars Knudsen and Vincent Rijmen The block cipher Square PDF PostScript nedostupne posilannya Lars Knudsen and Bart Preneel Hash functions based on block ciphers and quaternary codes PDF PostScript nedostupne posilannya LiteraturaMatt Henricksen and Lars R Knudsen Cryptanalysis of the CRUSH Hash Function Lars R Knudsen and Tadayoshi Kohno 1991 Analysis of RMAC Lars Knudsen and Bart Preneel Hash functions based on block ciphers and quaternary codes Lars Knudsen and Chris J Mitchell Analysis of 3gpp MAC and two key 3gpp MAC Joan Daemen Lars Knudsen and Vincent Rijmen The block cipher Square PosilannyaAlgoritmy shifrovaniya Specialnyj spravochnik 12 kvitnya 2018 u Wayback Machine