Diffie-Hellman

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].

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.

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.

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)#