Diffie-hellman

Historiku

Diffie-Hellman key exchange (i njohur edhe si D-H) është metodë specifike e këmbimit të çelësave kriptografikë, e publikuar në vitin 1976 nga Withfield Diffie dhe Martin Hellman, dhe bën të mundur këmbim të sigurtë çelësash nëpërmjet një mediumi të pasigurtë, pa pasur nevojë që palët të takohen paraprakisht. Si i tillë, D-H bën pjesë në sistemin e këmbimit me çelësa publikë, dhe që nga viti 2002 është propozuar të quhet Diffie-Hellman-Merkle key exchange[1].

Pershkrimi dhe Siguria

Përshkrimi dhe siguria Parimi i punës: Palët zgjedhin një numër primitiv p dhe një rrënjë primitive q (të cilët bëhen publikë) Pala A zgjedh një numër të rastësishëm (eksponenti) kA , të tillë që 1≤ kA ≤ p-2 Pala B zgjedh një numër të rastësishëm (eksponenti) kB , të tillë që 1≤ kB ≤ p-2 Pala A kalkulon a = qkA mod p dhe ia dërgon palës B. Pala B kalkulon b = qkB mod p dhe ia dërgon palës A. Siç po mund të vërehet, ajo çfarë palët kanë bërë, është ‘këmbimi i eksponentëve’. Secili prej tyre tani mund ta llogarisin k = (qkA )kB mod p (k = (qkB )kA mod p respektivisht) i cili do të jetë çelësi i tyre sekret (që do të përdoret si hyrje për ndonjë prej metodave të enkriptimit).

Siguria e kësaj metode bazohet në problemin e logaritmimit diskret (tash e tutje DLP). Kujtojmë se logaritmi në fakt është eksponent: pra mënyrë e njëjtë për të shprehur se 25=32 është log232=5. Natyrisht, llogaritja e fuqisë së numrave është relativisht e lehtë, por e njëjta nuk mund të thuhet edhe për logaritmimin: p.sh. sa është logaritmi me bazë 2 i 8589934592, pra 2x= 8589934592. Për numra të vegjël kjo nuk do të ishte problem edhe nëse tentojmë një-nga-një kombinimet e x-it, sepse y=log2x rritet në mënyrë monotone me x-in. DLP i referohet problemit të gjetjes së logaritmit të një numri moduluar me një tjetër, d.m.th bëhet fjale për një skenar të tille: 2x = 9 mod 11. Tani le të fillojmë të gjejmë për cilin numër është fjala.

21 = 2 mod 11
22 = 4 mod 11
23 = 8 mod 11
24 = 5 mod 11
25 = 10 mod 11
26 = 9 mod 11
27 = 7 mod 11
28 = 3 mod 11
29 = 6 mod 11
210 = 1 mod 11

Vërejmë menjëherë që ai ‘lineariteti’ u prish qysh në fillim. Kështu që nuk mund të vazhdohet me supozime se nëse e rrisim eksponentin, numri para operacionit modulo do të jetë më i madh dhe anasjelltas. Kjo e vështirëson punën bukur mirë. Pra, është lehtë fuqizimi diskret, por e njejta nuk mund të thuhet edhe për logaritmimin diskret. Këtu vërehet edhe përparësia e DLP, tek tenton t’i japë zgjidhje këtij problemi:

përcakto x nëse dihen p, q, dhe r = px mod q

Si rezultat, për momentin nuk ka algoritëm efiçient, jo-kuantik që do të mund ta zgjidhte këtë problem. Por një zgjidhje kuantike (algoritëm kuantik) e DLP ekziston![2] Megjithatë, duhet pasur parasysh se zgjidhja e problemit Diffie-Hellman ( i njouhur si DHP), nuk do të thotë ekskluzivisht edhe zgjidhje për DLP. Kjo sepse DHP kërkon zgjidhje të:

pAB nëse janë të dhëna p, q, pA, dhe pB.

Pa dyshim se një zgjidhje e DLP do të nënkuptonte edhe zgjidhje për DHP, por nuk është e thënë që këto të dyja janë probleme ekuivalente.

Dobësia

Sistemi i këmbimit të çelësave D-H është jashtëzakonisht i sigurtë, kur është fjala për sulmet pasive, si përgjimi, por kur vie në shprehje edhe autentifikimi, atëherë D-H ngel pa përgjigje dhe plotësisht i hapur ndaj sulmeve aktive, sidomos atij të njohur si Man-in-the-Middle attack. Skenari: Palët zgjedhin një numër primitiv p dhe një rrënjë primitive q (të cilët bëhen publikë) Pala A zgjedh një numër të rastësishëm (eksponenti) kA Pala B zgjedh një numër të rastësishëm (eksponenti) kB Pala C (me qëllime jo të mira) zgjedh një numër të rastësishëm (eksponenti) kC Pala A kalkulon a = qkA mod p dhe ia dërgon palës B, por Pala C (që është duke përgjuar linjën, kap numrin dhe e ndërron me c = qkc mod p) Pala B kalkulon b = qkB mod p dhe ia dërgon palës A, por Pala C (që është duke përgjuar linjën, kap numrin dhe e ndërron me c = qkc mod p) Siç po mund të vërehet, ajo çfarë palët A dhe B kanë bërë, është mendimi se kanë bërë ‘kembimin e eksponenteve’ ndërmjet vete. Si rezultat Pala C ka k = (qkA )kC mod p si dhe k = (qkB )kC mod p dhe çdo mesazh të dërguar nga A drejt B dhe anasjelltas mund ta ndryshojë, pa njohuri të palëve gjegjëse! Palët A dhe B tani mund ta llogarisin k = (qkA )kC mod p (k = (qkB )kC mod p respektivisht) i cili do të jetë çelësi i tyre ‘sekret’ (që do t’i mundësojë palës C qasje në përmbajtje të mesazhit). Fatkeqësisht, palët A dhe B nuk e kanë idenë për prezencën e palës së tretë dashakeqe, ngase vetë sistemi D-H nuk është përpiluar i tillë që të marrë parasysh edhe autenticitetin e dërguesit. Ky problem zgjidhet shumë thjeshtë, duke aplikuar të ashtuquajturën Çertifikatë Digjitale.

Referime

Understanding Cryptography – Christof Paar, Jan Pelzl Elliptic Curves in Public Key Cryptography: The Diffie Hellman Key Exchange Protocol and its relationship to the Elliptic Curve Discrete Logarithm Problem Crypto: Primitives and Protocols – Professor Kiayias

Punuar nga : Egzon Jonuzi , Besjon Murturi , Norik Osmani , Egzon Pllana dhe Flaka Neziri (Pjestar te grupit 13)#