Jump to content
¯\_( ツ)_/¯
  • TAD GROUP are currently hiring penetration testers. Please read the topic in Career Central subforum.
  • Sponsored Ad
ТУК НЕ СЕ ПРЕДЛАГАТ ХАКЕРСКИ УСЛУГИ ! ×
Sign in to follow this  
d3k4z

Crypto -> DH -> Discrete Logaritm Problem -> Shor 's Algorithm -> Quantum

Recommended Posts

Снощи попаднах на тази научна статия: https://arxiv.org/abs/1706.03215

, но преди да я анализираме трябва ни трябва малко въведение в Diffie Hellman key agreement algoritm. Разглеждаме общия случай DH, а не DHE или ECDHE - там имаме леки условности но идеята е същата.

Стандартно имаме Alice и Bob, за да започне криптирана комуникация между тях е нужно и двамата да договорят споделена тайна(ключ) с който да започнат криптирането на информацията(Diffie Hellman key agreement algorithm).

Как работи той:

  • g - генератор/база;
  • p - прайм число;
  • a - random() число калкулирано от А;
  • b - random() число калкулирано от Б;

Сървърът Bob калулира следните параметри B=g^b mod p. Изпраща (B,g,p) до клиента Аlice която изчислява A=g^a mod p заедно с K=B^a mod p. Alice изпраща A до Bob а той от своя страна калкулира K=A^b mod p. Ако заместим ще получим равенствата от A^b mod p = g^(a*b) mod p и g^(b*a) mod p = B^a mod p (много важно да се разбере това просто равенство).

Така и двамата стигат до равен K. И ето че и двамата имат договорена тайна/ключ и могът да започнат процес по криптиране и декриптиране на комуникацията им.

Силата на K зависи от изброените параметри g,p,a,b и колкото по-големи числа бъдат използвани толкова по сигурна че е комуникацията. a и b също така са напълно независими от p и g. НО не бива да забравяме че възможните резултати зависят от p: ако p=17 и z = n mod p следва че z E [0;17] или имаме възможни 17 резултата. Обикновено в днешно време p и g са предварително калкулирани на сървъра(в моя пример Bob) посредством:

┌─╼[/tmp]
└────╼time openssl dhparam -out dh_test.pem 4096
Generating DH parameters, 4096 bit long safe prime, generator 2
This is going to take a long time

openssl dhparam -out dh_test.pem 4096  27,15s user 0,01s system 99% cpu 27,168 total

(ако прайм числото е с дължина по-малка от 4096 бита съществува опасност)

Както виждаме sizeof(p)=4096 a g=2, и още нещо - самата операция по намиране на така наречените safe prime числа(p=2q+1, където q също е прайм число) изисква ресурс за изчисление(27,15s).

Защо е безопастно* p и g да се изпращат по несугурния канал на комуникация между Alice и Bob?

Поради това че стандартните генерираните сигурни прайм числа съдържат над 600цифри, а при дадени g,p и g^a mod p стандартните** изчислителни системи и алгоритми че бъдат значително значително затруднени в намирането на a. Това се нарича Discrete Logaritm Problem(тук).

Искам да направяв 2 коментара по твърденията ми маркирани със звездички(*):

  1. безопастно* - тук трябва да се направи вметка че същесвуват атаки за прайм числа по-малки от 4096бита (Атаката се казва Logjam, а повече информация и съответния рисърч пейпър тук tuk

  2. стандартните** изчислителни системи - тук забележката е че в следващите параграфи ще разберем че съществуват и не стандартни такива.

Добре дошли в 2017г и ерата на квантовите компютри. Не би трябвало да е тайна за някой че през изминалите 10 години започна да се говори все по масово за квантови компютри. Важно е да знаете че когато говорим за такива системи, трябва да се обстрахираме от всичко което знаем за работата на сегашните(трудно е, нелогично звучи, но това е 'реалността', иначе ще настанат обърквания ако се правят сравнения между системите). Ето едно въведение, не е научна статия нофактор можем бегло да разберем че има явни разлики.

Преди някой да ме обвини че нищо не разбирам от такива работи, искам да спомена че се съгласявам че имам прекалено много неизвестни в главата относно quantum(и като цяло Физиката на ми беше силната страна), НО съм виждал такова животно в приложен вариант за генериране и дистрибуция на криптографски ключове, както и съм имал възможността да карам някакво много тегаво обучени по темата. Това е един от малкото приложни варианти в наши дни за квантови компютри. Тук ключовата дума е приложни. Някои от големите изследоватеслски и частни компаний като Google, IBM, NASA, CERN вече имат такива. Част от тях даже започват да ги предоставят на девелопъри да пишат код за тях(за да им се намира приложение).

Любимата ми уикипедия не се признава за достоверен сорс но все пак тук може да видите таймлайн с имена на университети и компаний които участват в разработките и вече имат такива компютри. Който му е интересно да започне да се рови и да попълва белите петна по темата за квантовите компютри, а аз продължавам по моита си част че няма да му се види края иначе. На мен това научно изследване от 1999 ми хвърли мялко яснота, но малко(човека писал пеъпира е приложил и симулация писанана на С).

В много статий и изследвания за вантови компютри, или поне на мен ми направи впечетление че се говори за Shor's Algorithm (а ето и каква трябва да е схемата на квантовия компютър на който да бъде изпълнен неговия алгоритъм).

687474703a2f2f7777772e6e61747572652e636f

Оказва се че това е един от малкото приложими квантови алгоритми които решават изчислителни проблеми в реални условия('В живия живот' както се изразяваше една колежка) - ефикасен начин за намиране на фактор q в композиционно(composite number- ако p e прайм число следва 2p да е такова композиционно число, не съм сигурен за превода на български, виж примера със safe prime) число N, което се смята за трудно за пресмятане в стандартните изчислителни системи(с примерите гори разбрахме че полувината модерна криптография се оповава на това).

След задълбочено ровичкане, писане, смятане и нужната хидратация с бира, намерих това изследване. Където се разглеждат 2 кейса и възможното приложение на алгоритъма на Шор и комбинацията му с Discrete Fourier transform(и по специално Quantum Fourier Transform, което след още малко четене се оказа че е напълно различно но идеята за декомпозиция на фунцкия остава)за решаването на Discrete Logaritm Problem. В така наречения Easy Case от същите лекций доказва(!май) че може да съществува ефикасен квантов алгоритъм за решаване на проблема.

И нека сега се завърнем на 1вото изречение от поста ми където реферирах за научната публикация със заглавие - Realization of Shor's Algorithm at Room Temperature. Това означава че сме с една крачка по-близко до нуждата от Post-Quantum Crypto Solutions, защото много скоро(в близките 5-10г) националните служби и агенций за сигурност ще могат да си позволят ресурса необходим им за чупене на криптиращи алгоритми.

За тези които си мислиха че това ще е научен анализ - такъв беше в Криптографската част и разясненията по DH. Но quantum бе мотивацията ми за тази статия. Целта беше да се проследи връзката и влиянието на такива важни научни открития върху модерната криптография която днес е неразделна част от ежедневието на всеки човек използваш модерните технологии.

Ето ги и реферираните статий:

Edited by d3k4z
  • Like 5

Share this post


Link to post
Share on other sites

Ето и едно видео на Jaya Baloo, CISO@KPN - AppSec EU 2017 Everything Is Quantum! където се засягат темите Quantum Crypto , Post-quantum crypto и Quantum key distribution.

 

 

  • Like 2

Share this post


Link to post
Share on other sites
На 24.06.2017 г. at 17:01, d3k4z написа:

Сървърът Bob калулира следните параметри B=g^b mod p. Изпраща (B,g,p) до клиента Аlice която изчислява A=g^a mod p заедно с K=B^a mod p. Alice изпраща A до Bob а той от своя страна калкулира K=A^b mod p. Ако заместим ще получим равенствата от A^b mod p = g^(a*b) mod p и g^(b*a) mod p = B^a mod p (много важно да се разбере това просто равенство).

Това си е чисто RSA.

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Sign in to follow this  

  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...

Important Information

By using this site, you agree to our Terms of Use. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.