Постквантова криптографія — частина криптографії, яка залишається актуальною після появи квантових комп'ютерів і квантових атак. Оскільки за швидкістю обчислення традиційних криптографічних алгоритмів квантові комп'ютери значно перевершують класичні комп'ютерні архітектури, сучасні криптографічні системи стають потенційно вразливими для криптографічних атак. Більшість традиційних криптосистем спирається на задачі факторизації цілих чисел або задачі дискретного логарифмування, які легко можна розв'язати на достатньо великих квантових комп'ютерах, що використовують алгоритм Шора. Багато криптографів нині розробляють алгоритми, незалежні від квантових обчислень, тобто стійкі до квантових атак.
Існують класичні криптосистеми, які спираються на обчислювально складні завдання та мають низку суттєвих відмінностей від зазначених вище систем, через що їх значно складніше вирішити. Ці системи незалежні від квантових обчислень, і, отже, їх вважають квантово-стійкими (quantum-resistant), або постквантовими криптосистемами.
Постквантова криптографія у свою чергу відрізняється від квантової криптографії, яка займається методами захисту комунікацій, заснованих на принципах квантової фізики.
Алгоритми
Постквантові криптографічні конструкції здатні врятувати криптографічний світ від квантових атак. Хоча квантовий комп'ютер і знищить більшість традиційних алгоритмів (RSA, DSA, ECDSA), але надшвидкі обчислення не скасують повністю криптографії, оскільки постквантова криптографія, переважно, зосереджена на п'яти різних підходах, які вирішують проблему квантових атак.
Криптографія, заснована на геш-функціях
Класичним прикладом є з відкритим ключем на основі геш-дерева. 1979 року Ральф Чарльз Меркл запропонував цей алгоритм цифрового підпису, як цікаву альтернативу цифровим підписам RSA та DSA. Основний недолік схеми Меркла полягає в тому, що для будь-якого відкритого ключа на основі геш-функції існує обмеження кількості підписів, які можна отримати з відповідного набору закритих ключів. Цей факт і знижував рівень інтересу до підписів такого типу, до появи потреби у криптографії, стійкій до впливу квантових комп'ютерів.
Криптографія, заснована на кодах виправлення помилок
Один із найперспективніших кандидатів на постквантові криптосистеми. Класичним прикладом є схеми шифрування та .
Криптографія, заснована на ґратках
Класичним прикладом схем шифрування є — або старіші , GGH і криптосистема Міччанчо.
Криптографія, заснована на багатовимірних квадратичних системах
Однією з найцікавіших схем є підпис з відкритим ключем Жака Патаріна , який він запропонував 1996 року, як узагальнення пропозицій Мацумото (Matsumoto) та Імаї (Imai).
Шифрування зі секретним ключем
Яскравим прикладом є шифр Rijndael, запропонований 1998 року, згодом перейменований на AES (Advanced Encryption Standard).
Шифрування з використанням суперсингулярної ізогенії
Аналог протоколу Діффі — Геллмана, заснований на блуканні в суперсингулярному ізогенному графі, що дозволяє двом і більше сторонам отримати спільний секретний ключ, використовуючи незахищений від прослуховування канал зв'язку.
Приклади криптографічних атак на RSA
У документі, який 1978 року опублікували розробники криптографічного алгоритму з відкритим ключем RSA (абревіатура від прізвищ Rivest, Shamir та Adleman), згадано новий алгоритм [en] «лінійне сито» (англ. linear sieve), який факторизував будь-який модуль RSA довжини біт, використовуючи найпростіших операцій. Таким чином, щоб цей алгоритм вимагав щонайменше простих операцій, необхідно вибирати довжини принаймні не менше ніж біт. Оскільки означає, що щось збігається до при , то для з'ясування правильного розміру за скінченного потрібен ретельніший аналіз швидкості «лінійного сита».
В 1988 [en] запропонував новий алгоритм факторизації, який називають «загальний метод решета числового поля». Цей алгоритм факторизував RSA-модуль розмірності біт, використовуючи найпростіших операцій. Таким чином, щоб алгоритму знадобилося як мінімум найпростіших операцій, потрібно вибирати довжини не менше ніж біт.
Від 2008 року найшвидші алгоритми факторизації для класичних комп'ютерних архітектур використовують щонайменше найпростіших операцій. Були деякі покращення в значеннях та в деталях , але зрозуміло, що оптимальне, і що вибір модуля довжиною приблизно рівною біт, дозволить чинити опір усім можливим атакам на класичних комп'ютерах.
1994 року Пітер Шор запропонував алгоритм, який факторизував будь-який RSA-модуль розмірності біт, використовуючи (точніше ) кубітових операцій на квантовому комп'ютері розміру порядку кубіт (і незначний обсяг допоміжних обчислень на класичному комп'ютері). Користуючись алгоритмом Шора, необхідно принаймні вибирати модуль бітовим розміром не менше ніж біт, що є занадто великою кількістю для будь-якого цікавого для нас .
Практичні застосування криптографічних конструкцій
Прикладів алгоритмів, стійких до квантових атак, дуже мало. Але, попри вищу криптографічну стійкість, постквантові алгоритми не здатні витіснити сучасних криптосистем (RSA, DSA, ECDSA тощо).
Розглянемо напади на криптосистему з відкритим ключем, а саме на алгоритм шифрування McEliece, який використовує . Спочатку [en] надав документи, в яких коди завдовжки зламуються за найпростіших операцій. Таким чином, потрібно вибирати не меншим ніж біт, щоб алгоритму знадобилося як мінімум найпростіших операцій. Декілька наступних робіт скоротили кількість операцій атаки до , але значно менше ніж , якщо велике. Тому покращені атаки досі використовують найпростіших операцій. Що стосується квантових комп'ютерів, то їх використання призведе лише до зменшення константи , що зовсім мало скоротить кількість операцій, необхідних для зламу цього алгоритму.
Якщо система шифрування McEliece так добре захищена, чому вона не приходить на зміну RSA? Причина в ефективності, зокрема в розмірі ключа. Відкритий ключ McEliece використовує приблизно ≈ біт, тоді як для відкритого ключа RSA достатньо близько біт. Якщо , то біт для McEliece, буде менше від біт для RSA, але реальні рівні безпеки, такі як , дозволяють RSA мати відкритий ключ довжиною кілька тисяч біт, тоді як для McEliece розмір ключа наближається до мільйона біт.
Конференція PQCrypto
Від 2006 року проводиться серія конференцій, присвячених постквантовій криптографії.
- PQCrypto 2006. Левенський католицький університет, Бельгія, від 23 до 26 травня
- PQCrypto 2008. Університет Цинциннаті, США, від 17 до 19 жовтня
- PQCrypto 2010. Дармштадт, Німеччина, від 25 до 28 травня
- PQCrypto 2011. Тайбей, Тайвань, від 29 листопада до 2 грудня
- PQCrypto 2013. Лімож, Франція, від 4 до 7 червня
- PQCrypto 2014. Університет Ватерлоо, Канада, від 1 до 3 жовтня
- PQCrypto 2016. Попередній план: Фукуока, Японія, лютий 2016[]
Див. також
Примітки
- Daniel J. Bernstein. Introduction to post-quantum cryptography // (Introductory chapter to book "Post-quantum cryptography"). — 2009.
- . IEEE Spectrum. 1 листопада 2008. Архів оригіналу за 8 жовтня 2015. Процитовано 26 листопада 2014.
- навчання з помилками
- Peikert, Chris (2014). Lattice Cryptography for the Internet (PDF). IACR. (PDF) оригіналу за 12 травня 2014. Процитовано 10 травня 2014.
- Guneysu, Tim; Lyubashevsky; Poppelmann (2012). (PDF). INRIA. Архів оригіналу (PDF) за 18 травня 2014. Процитовано 12 травня 2014.
- Zhang, jiang (2014). Authenticated Key Exchange from Ideal Lattices (PDF). iacr.org. IACR. (PDF) оригіналу за 7 вересня 2014. Процитовано 7 вересня 2014.
- http://crypto.rsuh.ru/papers/bogdanov-kizhvatov-quantum.pdf [ 2017-12-15 у Wayback Machine.] стр 9
- официальный сайт PQCrypto 2006. оригіналу за 26 жовтня 2014. Процитовано 19 листопада 2014.
- . Архів оригіналу за 19 жовтня 2014. Процитовано 19 листопада 2014.
- официальный сайт PQCrypto 2010. оригіналу за 9 жовтня 2014. Процитовано 19 листопада 2014.
- официальный сайт PQCrypto 2011. оригіналу за 27 грудня 2014. Процитовано 19 листопада 2014.
- официальный сайт PQCrypto 2013. оригіналу за 23 грудня 2014. Процитовано 19 листопада 2014.
- . Архів оригіналу за 26 жовтня 2014. Процитовано 19 листопада 2014.
Посилання
- PQCrypto, the post-quantum cryptography conference
- Post-Quantum Cryptography. — Springer, 2008. — С. 245. — .
- ETSI Квантова безпека(англ.)
- NIST's Постквантовий криптопроєкт(англ.)
- PQCrypto Використання та розгортання(англ.)
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Postkvantova kriptografiya chastina kriptografiyi yaka zalishayetsya aktualnoyu pislya poyavi kvantovih komp yuteriv i kvantovih atak Oskilki za shvidkistyu obchislennya tradicijnih kriptografichnih algoritmiv kvantovi komp yuteri znachno perevershuyut klasichni komp yuterni arhitekturi suchasni kriptografichni sistemi stayut potencijno vrazlivimi dlya kriptografichnih atak Bilshist tradicijnih kriptosistem spirayetsya na zadachi faktorizaciyi cilih chisel abo zadachi diskretnogo logarifmuvannya yaki legko mozhna rozv yazati na dostatno velikih kvantovih komp yuterah sho vikoristovuyut algoritm Shora Bagato kriptografiv nini rozroblyayut algoritmi nezalezhni vid kvantovih obchislen tobto stijki do kvantovih atak Isnuyut klasichni kriptosistemi yaki spirayutsya na obchislyuvalno skladni zavdannya ta mayut nizku suttyevih vidminnostej vid zaznachenih vishe sistem cherez sho yih znachno skladnishe virishiti Ci sistemi nezalezhni vid kvantovih obchislen i otzhe yih vvazhayut kvantovo stijkimi quantum resistant abo postkvantovimi kriptosistemami Postkvantova kriptografiya u svoyu chergu vidriznyayetsya vid kvantovoyi kriptografiyi yaka zajmayetsya metodami zahistu komunikacij zasnovanih na principah kvantovoyi fiziki AlgoritmiPostkvantovi kriptografichni konstrukciyi zdatni vryatuvati kriptografichnij svit vid kvantovih atak Hocha kvantovij komp yuter i znishit bilshist tradicijnih algoritmiv RSA DSA ECDSA ale nadshvidki obchislennya ne skasuyut povnistyu kriptografiyi oskilki postkvantova kriptografiya perevazhno zoseredzhena na p yati riznih pidhodah yaki virishuyut problemu kvantovih atak Kriptografiya zasnovana na gesh funkciyah Klasichnim prikladom ye z vidkritim klyuchem na osnovi gesh dereva 1979 roku Ralf Charlz Merkl zaproponuvav cej algoritm cifrovogo pidpisu yak cikavu alternativu cifrovim pidpisam RSA ta DSA Osnovnij nedolik shemi Merkla polyagaye v tomu sho dlya bud yakogo vidkritogo klyucha na osnovi gesh funkciyi isnuye obmezhennya kilkosti pidpisiv yaki mozhna otrimati z vidpovidnogo naboru zakritih klyuchiv Cej fakt i znizhuvav riven interesu do pidpisiv takogo tipu do poyavi potrebi u kriptografiyi stijkij do vplivu kvantovih komp yuteriv Kriptografiya zasnovana na kodah vipravlennya pomilok Odin iz najperspektivnishih kandidativ na postkvantovi kriptosistemi Klasichnim prikladom ye shemi shifruvannya ta Kriptografiya zasnovana na gratkah Klasichnim prikladom shem shifruvannya ye abo starishi GGH i kriptosistema Michchancho Kriptografiya zasnovana na bagatovimirnih kvadratichnih sistemah Odniyeyu z najcikavishih shem ye pidpis z vidkritim klyuchem Zhaka Patarina yakij vin zaproponuvav 1996 roku yak uzagalnennya propozicij Macumoto Matsumoto ta Imayi Imai Shifruvannya zi sekretnim klyuchem Yaskravim prikladom ye shifr Rijndael zaproponovanij 1998 roku zgodom perejmenovanij na AES Advanced Encryption Standard Shifruvannya z vikoristannyam supersingulyarnoyi izogeniyi Div takozh ru Analog protokolu Diffi Gellmana zasnovanij na blukanni v supersingulyarnomu izogennomu grafi sho dozvolyaye dvom i bilshe storonam otrimati spilnij sekretnij klyuch vikoristovuyuchi nezahishenij vid prosluhovuvannya kanal zv yazku Prikladi kriptografichnih atak na RSAU dokumenti yakij 1978 roku opublikuvali rozrobniki kriptografichnogo algoritmu z vidkritim klyuchem RSA abreviatura vid prizvish Rivest Shamir ta Adleman zgadano novij algoritm en linijne sito angl linear sieve yakij faktorizuvav bud yakij modul RSA n displaystyle n dovzhini log2 n 1 displaystyle log 2 n 1 bit vikoristovuyuchi 2 1 o 1 log2 n 1 2 log2 log2 n 1 2 displaystyle 2 1 o 1 log 2 n 1 2 log 2 log 2 n 1 2 najprostishih operacij Takim chinom shob cej algoritm vimagav shonajmenshe 2b displaystyle 2 b prostih operacij neobhidno vibirati n displaystyle n dovzhini prinajmni ne menshe nizh 0 5 o 1 b2 log2 b displaystyle 0 5 o 1 b 2 log 2 b bit Oskilki 0 5 o 1 displaystyle 0 5 o 1 oznachaye sho shos zbigayetsya do 0 5 displaystyle 0 5 pri b displaystyle b to infty to dlya z yasuvannya pravilnogo rozmiru n displaystyle n za skinchennogo b displaystyle b potriben retelnishij analiz shvidkosti linijnogo sita V 1988 en zaproponuvav novij algoritm faktorizaciyi yakij nazivayut zagalnij metod resheta chislovogo polya Cej algoritm faktorizuvav RSA modul n displaystyle n rozmirnosti log2 n displaystyle log 2 n bit vikoristovuyuchi 2 1 9 o 1 log2 n 1 3 log2 log2 n 2 3 displaystyle 2 1 9 dotso o 1 log 2 n 1 3 log 2 log 2 n 2 3 najprostishih operacij Takim chinom shob algoritmu znadobilosya yak minimum 2b displaystyle 2 b najprostishih operacij potribno vibirati n displaystyle n dovzhini ne menshe nizh 0 016 o 1 b3 log2 b 2 displaystyle 0 016 dotso o 1 b 3 log 2 b 2 bit Vid 2008 roku najshvidshi algoritmi faktorizaciyi dlya klasichnih komp yuternih arhitektur vikoristovuyut shonajmenshe 2 const o 1 log2 n 1 3 log2 log2 n 2 3 displaystyle 2 const o 1 log 2 n 1 3 log 2 log 2 n 2 3 najprostishih operacij Buli deyaki pokrashennya v znachennyah const displaystyle const ta v detalyah o 1 displaystyle o 1 ale zrozumilo sho 1 3 displaystyle 1 3 optimalne i sho vibir modulya n displaystyle n dovzhinoyu priblizno rivnoyu b3 displaystyle b 3 bit dozvolit chiniti opir usim mozhlivim atakam na klasichnih komp yuterah 1994 roku Piter Shor zaproponuvav algoritm yakij faktorizuvav bud yakij RSA modul n displaystyle n rozmirnosti b log2 n displaystyle b log 2 n bit vikoristovuyuchi b2 o 1 displaystyle b 2 o 1 tochnishe b2 log b log log b displaystyle b 2 cdot log b cdot log log b kubitovih operacij na kvantovomu komp yuteri rozmiru poryadku 2 b1 o 1 displaystyle 2 cdot b 1 o 1 kubit i neznachnij obsyag dopomizhnih obchislen na klasichnomu komp yuteri Koristuyuchis algoritmom Shora neobhidno prinajmni vibirati modul n displaystyle n bitovim rozmirom ne menshe nizh 2 0 5 o 1 b displaystyle 2 0 5 o 1 b bit sho ye zanadto velikoyu kilkistyu dlya bud yakogo cikavogo dlya nas b displaystyle b Praktichni zastosuvannya kriptografichnih konstrukcijPrikladiv algoritmiv stijkih do kvantovih atak duzhe malo Ale popri vishu kriptografichnu stijkist postkvantovi algoritmi ne zdatni vitisniti suchasnih kriptosistem RSA DSA ECDSA tosho Rozglyanemo napadi na kriptosistemu z vidkritim klyuchem a same na algoritm shifruvannya McEliece yakij vikoristovuye Spochatku en nadav dokumenti v yakih kodi zavdovzhki n displaystyle n zlamuyutsya za 2 0 5 o 1 n log2 n displaystyle 2 0 5 o 1 n log 2 n najprostishih operacij Takim chinom potribno vibirati n displaystyle n ne menshim nizh 2 o 1 blog2 b displaystyle 2 o 1 b log 2 b bit shob algoritmu znadobilosya yak minimum 2b displaystyle 2 b najprostishih operacij Dekilka nastupnih robit skorotili kilkist operacij ataki do nlog2 n 2 log2 n 2 displaystyle n log 2 n 2 log 2 n 2 ale log2 n 2 displaystyle log 2 n 2 znachno menshe nizh 0 5n log2 n displaystyle 0 5n log 2 n yaksho n displaystyle n velike Tomu pokrasheni ataki dosi vikoristovuyut 2 0 5 o 1 n log2 n displaystyle 2 0 5 o 1 n log 2 n najprostishih operacij Sho stosuyetsya kvantovih komp yuteriv to yih vikoristannya prizvede lishe do zmenshennya konstanti 0 5 displaystyle 0 5 sho zovsim malo skorotit kilkist operacij neobhidnih dlya zlamu cogo algoritmu Yaksho sistema shifruvannya McEliece tak dobre zahishena chomu vona ne prihodit na zminu RSA Prichina v efektivnosti zokrema v rozmiri klyucha Vidkritij klyuch McEliece vikoristovuye priblizno n2 4 displaystyle n 2 4 b2 log2 b 2 displaystyle b 2 log 2 b 2 bit todi yak dlya vidkritogo klyucha RSA dostatno blizko 0 016 b3 log2 b 2 displaystyle 0 016 dots b 3 log 2 b 2 bit Yaksho b displaystyle b to infty to b2 o 1 displaystyle b 2 o 1 bit dlya McEliece bude menshe vid b3 o 1 displaystyle b 3 o 1 bit dlya RSA ale realni rivni bezpeki taki yak b 128 displaystyle b 128 dozvolyayut RSA mati vidkritij klyuch dovzhinoyu kilka tisyach bit todi yak dlya McEliece rozmir klyucha nablizhayetsya do miljona bit Konferenciya PQCryptoVid 2006 roku provoditsya seriya konferencij prisvyachenih postkvantovij kriptografiyi PQCrypto 2006 Levenskij katolickij universitet Belgiya vid 23 do 26 travnya PQCrypto 2008 Universitet Cincinnati SShA vid 17 do 19 zhovtnya PQCrypto 2010 Darmshtadt Nimechchina vid 25 do 28 travnya PQCrypto 2011 Tajbej Tajvan vid 29 listopada do 2 grudnya PQCrypto 2013 Limozh Franciya vid 4 do 7 chervnya PQCrypto 2014 Universitet Vaterloo Kanada vid 1 do 3 zhovtnya PQCrypto 2016 Poperednij plan Fukuoka Yaponiya lyutij 2016 utochniti Div takozhKriptografiya na gratkah Algoritm ShoraPrimitkiDaniel J Bernstein Introduction to post quantum cryptography Introductory chapter to book Post quantum cryptography 2009 IEEE Spectrum 1 listopada 2008 Arhiv originalu za 8 zhovtnya 2015 Procitovano 26 listopada 2014 navchannya z pomilkami Peikert Chris 2014 Lattice Cryptography for the Internet PDF IACR PDF originalu za 12 travnya 2014 Procitovano 10 travnya 2014 Guneysu Tim Lyubashevsky Poppelmann 2012 PDF INRIA Arhiv originalu PDF za 18 travnya 2014 Procitovano 12 travnya 2014 Zhang jiang 2014 Authenticated Key Exchange from Ideal Lattices PDF iacr org IACR PDF originalu za 7 veresnya 2014 Procitovano 7 veresnya 2014 http crypto rsuh ru papers bogdanov kizhvatov quantum pdf 2017 12 15 u Wayback Machine str 9 oficialnyj sajt PQCrypto 2006 originalu za 26 zhovtnya 2014 Procitovano 19 listopada 2014 Arhiv originalu za 19 zhovtnya 2014 Procitovano 19 listopada 2014 oficialnyj sajt PQCrypto 2010 originalu za 9 zhovtnya 2014 Procitovano 19 listopada 2014 oficialnyj sajt PQCrypto 2011 originalu za 27 grudnya 2014 Procitovano 19 listopada 2014 oficialnyj sajt PQCrypto 2013 originalu za 23 grudnya 2014 Procitovano 19 listopada 2014 Arhiv originalu za 26 zhovtnya 2014 Procitovano 19 listopada 2014 PosilannyaPQCrypto the post quantum cryptography conference Post Quantum Cryptography Springer 2008 S 245 ISBN 978 3 540 88701 0 ETSI Kvantova bezpeka angl NIST s Postkvantovij kriptoproyekt angl PQCrypto Vikoristannya ta rozgortannya angl