Квантни рачунари: крај криптографије?

Реклама

Квантно рачунање једна је од оних технологија које су толико скривене да ТВ знакови испадају кад желе да звуче паметно.

Квантно рачунање као идеја постоји већ неко време - теоријску могућност су првобитно увели Јуриј Манин и Ричард Фејнман 1982. године. Последњих година, међутим, поље се забрињава ближе практичности.

Компаније попут Гоогле-а и Мицрософта, као и владине агенције попут НСА, већ годинама грозничаво траже квантна рачунара. Компанија под називом Д-Ваве произвела је и продаје уређаје који (иако нису прави рачунари и могу само неколико алгоритама) искориштавају квантна својства и још су један корак у кораку на путу ка а потпуно Туринг-комплет Шта је Турингов тест и да ли ће га икада победити?Турингов тест треба да утврди да ли машине размишљају. Да ли је програм Еугене Гоостман заиста прошао Турингов тест или су га аутори једноставно преварили? Опширније квантна машина.

Не чини се неразумним рећи да би могло доћи до пробоја који ће омогућити да се први квантни рачунар великих димензија изгради у року од деценије.

Па зашто све интересовање? Зашто би се бринула? Рачунари постају бржи стално Шта је Моореов закон и какве то везе има са вама? [МакеУсеОф објашњава]Лоша срећа нема никакве везе са Моореовим законом. Ако је то удружење које сте имали, то мијешате са Мурпхијевим законом. Међутим, нисте били далеко јер Моореов закон и Мурпхијев закон ... Опширније - шта је тако посебно у квантним рачунарима?

Да бисмо објаснили зашто су ове машине тако важне, мораћемо да направимо корак уназад и истражимо тачно шта су квантни рачунари и зашто раде. За почетак, разговарајмо о концепту који се зове „сложеност рунтиме-а“.

Шта је сложени рунтиме?

Једно од великих изненађења у раним данима рачунарске науке било је откриће да, ако имате рачунар који решава проблем одређена величина током одређеног времена, удвостручење брзине рачунара не мора нужно да двоструко решава проблеме велика.

Неки алгоритми увећавају укупно време извршења врло брзо, како величина проблема расте - неки алгоритми се могу брзо довршити датих 100 тачака података, али за комплетирање алгоритма с 1000 података биће потребан рачунар величине Земље која ради милијарду година. Сложеност извођења времена је формализација ове идеје: она сагледава кривуљу брзине раста сложености проблема и користи облик те кривуље за класификацију алгоритма.

Генерално, ове класе тешкоће су изражене као функције. Алгоритам који постаје пропорционално тежи када се скупови података раде на њему (попут једноставне функције бројања) каже се да је функција са сложеношћу извођења „н ” (као у, потребно је н јединице времена за обраду н Подаци указују).

Алтернативно, може се звати „линеарна“, јер када је графички графикон добијете равну линију. Могу бити и друге функције н ^ 2 или 2 ^ н или н! (н факторски). То су полином и експоненцијално. У последња два случаја експоненцијални расту толико брзо да се у готово свим случајевима не могу решити ни за шта, осим за врло тривијалне примере.

Сложеност извођења и криптографија

Ако ове ствари чујете први пут, а звуче бесмислено и суздржано, покушајмо да заложимо ову расправу. Сложеност извођења је критична за криптографију која се ослања на то да дешифрирање буде много лакше људима који знају тајни кључ него онима који то немају. У идеалној криптографској шеми, дешифровање би требало да буде линеарно ако имате кључ и 2 ^ к (где је к број битова у кључу) ако немате.

Другим речима, најбољи алгоритам за дешифровање поруке без кључа требало би да буде једноставно нагађање могућих кључева, што је за кључеве неизречиво само неколико стотина битова.

За симетричну кључну криптографију (у којој две стране имају шансу да безбедно размењују тајну пре него што започну комуникацију) ово је прилично једноставно. За асиметричну криптографију је теже.

Асиметрична криптографија у којој су кључеви за шифровање и дешифровање различити и не могу се лако израчунати један од другог, много је тежа математичка структуру за имплементирање од симетричне криптографије, али је и много моћнија: асиметрична криптовалута омогућава вам приватне разговоре, чак и преко прислушкивања линије! Такође вам омогућава да креирате „дигитални потпис“ који ће вам омогућити да проверите од кога је порука стигла и да није упао у њу.

Ово су моћни алати и чине основу модерне приватности: без асиметричне криптографије корисници електронских уређаја не би имали поуздану заштиту од знатижељних очију.

Пошто је асиметричну криптографију теже изградити него симетричну, стандардне шеме шифрирања које се данас користе нису тако снажне као што су могли: најчешћи стандард шифрирања, РСА, може се пробити ако ефикасно можете пронаћи главне факторе врло великог број. Добра вест је да је то врло тежак проблем.

Најпознатији алгоритам за разврставање великог броја у њихове компоненте се назива генерално сито с бројевима и има сложеност извођења која расте мало спорије него 2 ^ н. Као посљедица тога, кључеви морају бити десетак пута дужи да би пружили сличну сигурност, што је нешто што људи обично толеришу као трошкове пословања. Лоша вест је да се целокупно играчко поље мења када квантни рачунари буду бачени у микс.

Квантни рачунари: Промјена крипто-игре

Квантни рачунари раде зато што могу имати више унутрашњих стања истовремено, кроз квантни феномен који се назива „суперпозиција“. То значи да могу истовремено да нападну различите делове проблема и поделе се на могуће верзије универзума. Такође се могу конфигурирати тако да гране које решавају проблем вијугају са највише амплитуде, тако да када отворите кутију на Сцхродингерова мачка, верзија унутрашњег стања која вам се највероватније представља, је самозадовољна мачка која држи дешифровано порука.

За више информација о квантним рачунарима погледајте наш недавни чланак о овој теми Како функционишу оптички и квантни рачунари?Ексаскално доба долази. Знате ли како раде оптички и квантни рачунари и да ли ће ове нове технологије постати наша будућност? Опширније !

Резултат овога је да квантни рачунари нису линеарно бржи, као што су нормални рачунари: добијање два или десет или стотину пута брже не помаже пуно када је реч о конвенционалној криптографији коју сте стотине милијарди пута преспори за обраду. Квантни рачунари подржавају алгоритме који имају све веће сложености рада него што је то иначе могуће. То је оно што квантне рачунаре битно разликује од осталих будућих рачунарских технологија, попут рачунање графена и мемристера Најновија рачунарска технологија у коју морате да верујетеПогледајте неке од најновијих рачунарских технологија које су постављене да трансформишу свет електронике и рачунара у наредних неколико година. Опширније .

За конкретан пример, Схор-ов алгоритам, који се може извести само на квантном рачунару, може да уреди велике бројеве у лог (н) ^ 3 време, што је драстично боље од најбољег класичног напада. Употребом општег сита са бројевима за фактор броја са 2048 бита потребно је отприлике 10 ^ 41 јединица времена, што значи више од билијуна билиона билиона. Користећи Схор-ов алгоритам, исти проблем траје само око 1000 јединица времена.

Ефекат постаје израженији што су тастери дужи. То је снага квантних рачунара.

Немојте ме криво схватити - квантни рачунари имају пуно потенцијалних не-злих употреба. Квантни рачунари могу ефикасно решити проблем продавца, омогућавајући истраживачима да граде ефикасније транспортне мреже и дизајнирају боље склопове. Квантни рачунари већ имају моћну употребу у вештачкој интелигенцији.

Речено је да ће њихова улога у криптографији бити катастрофална. Технологије шифровања које нашем свету омогућавају да настави да функционишу зависе од проблема целог факторизације који је тешко решити. РСА и повезане шеме шифровања су оно што вам омогућава да верујете да сте на правом веб сајту и да их датотеке преузимање није препуно злонамјерног софтвера и то што људи не шпијунирају ваше интернетско прегледавање (ако користите Тор).

Криптографија чува ваш банковни рачун и осигурава нуклеарну инфраструктуру у свијету. Када квантни рачунари постану практични, сва та технологија престаје да ради. Прва организација која је развила квантни рачунар, ако свет и даље ради на технологијама које данас користимо, биће у застрашујуће моћном положају.

Дакле, да ли је квантна апокалипса неизбежна? Можемо ли нешто учинити у вези с тим? Како се испоставило... да.

Постквантна криптографија

Постоји неколико класа алгоритама за шифровање које, колико знамо, није значајно брже решити на квантном рачунару. Они су колективно познати као постквантна криптографија и пружају неку наду да свет може прећи на криптосистеме који ће остати безбедни у свету квантне енкрипције.

Обећавајући кандидати укључују решење засновано на шифрирању, попут Ринг-Леарнинг Витх Еррор, које своју сигурност изводи из демонстрирано сложених проблем машинског учења и мултиваријантна криптографија која своју сигурност црпи из потешкоћа решавања веома великих система једноставних једначине. Више о овој теми можете прочитати на Чланак из Википедије. Пазите: пуно је ових ствари сложених и можда ћете схватити да је математичка позадина потребно знатно побољшати, пре него што сте заиста могли да се укопате у детаље.

Много тога је чињеница да су пост-квантне криптосхеме врло цоол, али исто тако и врло младе. Потребно им је више рада да би били ефикасни и практични, као и да покажу да су сигурни. Разлог због којег можемо да верујемо криптосистемима је тај што смо на њих довољно дуго бацали довољно клинички параноичних генија да би до сада били откривени било какви очигледни недостаци, а истраживачи су доказали различите карактеристике које их чине јак.

Савремена криптографија зависи од светлости као дезинфицијенса, а већина постквантних криптографских схема једноставно је превише нова да би се поуздању у светску безбедност могли поверити. Они стижу тамо, и уз мало среће и мало припреме, безбедносни стручњаци могу да доврше прелазак пре него што први квантни рачунар икада дође на ред.

Ако ипак не успију, последице могу бити тешке. Помисао на свакога ко има такву моћ узнемирује, чак и ако сте оптимистични у њиховим намерама. Питање ко ће први развити радни квантни рачунар поставља питање које би сви требали пажљиво да посматрају док крећемо у наредну деценију.

Да ли сте забринути због несигурности криптографије за квантне рачунаре? Шта ти мислиш? Поделите своје мисли у коментарима испод!

Имаге Цредитс: Бинарна кугла Виа Схуттерстоцк