Prestížnu informatickú cenu dostali autori Diffie-Hellmanovho algoritmu

Značky: kryptografiaveda a výskum

DSL.sk, 2.3.2016

Prestížnu Turingovu cenu udeľovanú informatickou organizáciou ACM, Association for Computing Machinery, za rok 2015 získala dvojica kryptológov Whitfield Diffie a Martin Hellman.

Diffie a Hellman cenu spojenú s odmenou milión dolárov a považovanú za ekvivalent Nobelovej ceny získali za návrh známeho Diffie-Hellmanovho algoritmu z roku 1976 a tým výrazný príspevok k modernej počítačovej kryptografii.

Diffie-Hellmanov, DH, algoritmus, je totiž prvým praktickým tzv. asymetrickým kryptografickým algoritmom s verejným kľúčom, ktorý umožňuje dvom stranám komunikovať bezpečne šifrovane bez potreby tajnej výmeny privátneho tajného kľúča pre šifrovanie.

Základný princíp asymetrického algoritmu s verejným kľúčom všeobecne spočíva v existencii dvoch častí kľúča, verejnej a privátnej. Iná osoba môže poslať majiteľovi kľúča správu zašifrovanú jeho verejným kľúčom, ktorú vie odšifrovať len držiteľ privátneho kľúča. Odvodiť privátny kľúč z verejného kľúča je pritom tak výpočtovo náročné, že to pri dostatočnej dĺžke zvoleného kľúča nie je možné so súčasnými technológiami realizovať dostatočne skoro respektíve dostatočne lacno.

DH je konkrétne postavený na umocňovaní čísla na iné číslo, tajný kľúč, modulo veľké prvočíslo. Invertovanie tohto procesu by bolo ekvivalentné vyriešeniu tzv. diskrétneho logaritmu a ten dnes s klasickými počítačmi nevieme riešiť efektívne.

DH hrá stále v kryptografii veľmi dôležitú úlohu, bežne sa ale nepoužíva ako algoritmus s verejným kľúčom na asymetrické šifrovanie ale ako algoritmus na bezpečné dohodnutie si spoločného tajného kľúča dvomi stranami odolné proti pasívnemu odpočúvaniu.

Dominantným algoritmom na asymetrické šifrovanie a podpisovanie sa stal RSA vytvorený v roku 1977, pričom v súčasnosti sa používajú aj DSA, ECDSA a prípadne adaptácia DH na šifrovanie ElGamal. Tieto algoritmy boli vytvorené a nasadené v nasledujúcich desaťročiach.




Najnovšie články:



Diskusia:

anojetotak Od: anojetotak | Pridané: 2.3.2016 10:51 o tom sme sa učili v škole Odpovedať Známka: 8.5 Hodnotiť:

Re: anojetotak Od: Kekekekeke | Pridané: 2.3.2016 10:51 aj my Odpovedať Známka: 6.4 Hodnotiť:

Re: anojetotak Od: xvzf | Pridané: 2.3.2016 22:50 Ked uz sme pri tom, tak namet na spravicku: https://drownattack.com Odpovedať Známka: 5.0 Hodnotiť:

...... Od: sufuzka1 | Pridané: 2.3.2016 10:54 Motivovali ste ma, idem veru aj ja vymysliet nejaky ten algoritmus. Odpovedať Známka: 10.0 Hodnotiť:

Navrh na vytvorenie algaca Od: WisdomSpeaker | Pridané: 2.3.2016 11:24 Sprav algac, ktory dokaze, ze neexistuju take realne cisla a,b,c, ze pre n>2, kde n je cele cislo, nie je mozne najst a^n+b^n = c^n. Pre n=2 je to samozrejme Pytaghorova veta a^2 + b^2 = c^2. Potom sa mozes tesit na Fieldovu medailu za matiku. Odpovedať Známka: 5.7 Hodnotiť:

Re: Navrh na vytvorenie algaca Od: Pierre de Fermat | Pridané: 2.3.2016 11:37 To mi niečo hovorí, kde som to len videl Odpovedať Známka: 8.3 Hodnotiť:

Re: Navrh na vytvorenie algaca Od: riešenie | Pridané: 2.3.2016 15:50 V Blave na stanici v tretej kabínke to vyškriabal bezdomovec na stenu. Odpovedať Známka: 10.0 Hodnotiť:

Re: Navrh na vytvorenie algaca Od: ... | Pridané: 2.3.2016 16:35 film Dobrý Will Hunting Odpovedať Známka: 3.3 Hodnotiť:

Re: Navrh na vytvorenie algaca Od: enyy | Pridané: 2.3.2016 11:40 nasiel som dokaz a je, pravda, velmi zvlastny, ale nevojde sa mi tu do tejto diskusie Odpovedať Známka: 8.9 Hodnotiť:

Re: Navrh na vytvorenie algaca Od: syntaxterrorX | Pridané: 2.3.2016 12:46 Kľudne ho môžeš rozdeliť do viacerých príspevkov. Samostatne majú aj tak nejaký zmysel iba zriedka. Odpovedať Známka: -4.3 Hodnotiť:

Re: Navrh na vytvorenie algaca Od: Neviem- | Pridané: 2.3.2016 18:28 *Pokojne Odpovedať Známka: 8.0 Hodnotiť:

Re: Navrh na pytvorenie alkaca Od: syntaxterrorX | Pridané: 2.3.2016 18:42 Eventuálne dormanticky. :) http://dopice.sk/gHw Odpovedať Známka: 10.0 Hodnotiť:

Re: Navrh na vytvorenie algaca Od: gertrudo | Pridané: 2.3.2016 12:19 Mam, vysledky mozete skontrolovat tu, tu a tu. Odpovedať Známka: 5.6 Hodnotiť:

Re: Navrh na vytvorenie algaca Od reg.: Bryan Fury | Pridané: 2.3.2016 12:53 ^_^ Odpovedať Známka: 5.0 Hodnotiť:

Re: Navrh na vytvorenie algaca Od: Nemo22 | Pridané: 2.3.2016 13:55 Velka Fermatova veta uz bola dokazana, takze smola. Odpovedať Známka: 10.0 Hodnotiť:

Re: Navrh na vytvorenie algaca Od reg.: Kvík? | Pridané: 2.3.2016 15:50 Lenže ak by si našiel krátky a elegantný dôkaz, bol by si považovaný za oveľa väčšieho machra, než Andrew Wiles ;-) Odpovedať Známka: 6.7 Hodnotiť:

Re: Navrh na vytvorenie algaca Od: "abc" | Pridané: 2.3.2016 21:06 Z Oesterlé-Masser hypotézy dokázanej človekom s menom Shinichi Mochizuki ten dôkaz Veľkej Fermatovej vety vypadne naozaj elegantne. Odporúčam pozrieť. Odpovedať Známka: 10.0 Hodnotiť:

Re: Navrh na vytvorenie algaca Od: syntaxterrorX | Pridané: 2.3.2016 21:12 *vpadne. Odporúčam čítať pozornejšie. Odpovedať Hodnotiť:

Re: Navrh na vytvorenie algaca Od: lojzo_z_absurdistanu | Pridané: 2.3.2016 18:50 A veľká Fernetová veta ? Odpovedať Známka: 4.3 Hodnotiť:

Re: ...... Od reg.: l1@p5 | Pridané: 2.3.2016 11:25 radsej riesenie diskretnych logaritmov, to bude efektivnejsie Odpovedať Známka: 7.1 Hodnotiť:

Re: ...... Od: reg.: Houston | Pridané: 2.3.2016 11:41 A ked ten sposob riesenia spravne preda, tak za vyrazne viac ako milion dolarov. Odpovedať Známka: 6.7 Hodnotiť:

Diffie Hellman Od: milan.ko | Pridané: 2.3.2016 12:00 Kazdy tyzden si na tychto dvoch panov spomeniem v robote. Robim firewally. Odpovedať Známka: 3.3 Hodnotiť:

Re: Diffie Hellman Od: quix_ | Pridané: 2.3.2016 12:33 ale ved ty si murar milanko Odpovedať Známka: 8.5 Hodnotiť:

Re: Diffie Hellman Od: milan.ko | Pridané: 2.3.2016 13:12 Murar, a staviam aj tunely Odpovedať Známka: 10.0 Hodnotiť:

Majolenka vs. Majonéza Od reg.: Bryan Fury | Pridané: 2.3.2016 12:53 Prvá časť je bez otázky a bez debaty, Hellmans. Ale otázka znie, Majolenka, alebo Majonéza? Odpovedať Známka: 4.0 Hodnotiť:

Re: Majolenka vs. Majonéza Od reg.: FilipSK | Pridané: 2.3.2016 13:52 Tatarska omacka :) Odpovedať Známka: 10.0 Hodnotiť:

Re: Majolenka vs. Majonéza Od: Hadimrska | Pridané: 4.3.2016 8:37 Jasne, typek by sa urcite potesil, keby vedel ze je po nom pomenovana tatarska omacka. Mozno este viac ako z tej nobelovej ceny. Odpovedať Hodnotiť:

ehm (doplnene na 5 znakov) Od reg.: _MMx_ | Pridané: 2.3.2016 15:14 Diffie-Hellmanov algoritmus v skutocnosti umoznuje vymenu tajneho sifrovacieho kluca cez verejny kanal, pricom nepotrebuje k tomu verejny kluc (existuje anonymna verzia). Vymeneny kluc sa dalej zvykne pouzivat na symetricke sifrovanie. DH algoritmus sa nepouziva na sifrovanie (kluc ku ktoremu dospeju si ziadna zo stran nevie zvolit, teda nevedia preniest dopredu zvolenu informaciu). Odporucam opravit cely druhy odstavec (a tym padom prepisat zvysok clanku). Odpovedať Známka: 3.3 Hodnotiť:

Re: ehm (doplnene na 5 znakov) Od reg.: Redakcia DSL.sk | Pridané: 2.3.2016 19:58 Odporúčam prečítať si článok do konca. DH je aj, dá sa naň pozerať, bol navrhnutý a bol teraz ocenený ako prvý asymetrický algoritmus s verejným kľúčom. Pri takomto vnímaní je verejným kľúčom osoby A p,g a g^a mod p, privátnym a. Algoritmus verejného kľúča nevyžaduje, aby sa ten verejný kľúč priamo matematicky použil v algoritme šifrovania. Keď chce B zašifrovať správu týmto verejným kľúčom, zvolí b, vypočíta si kľúč pre šifrovanie g^a^b a zašifruje správu ľubovoľným ním zvoleným symetrickým algoritmom. Spolu je to systém asymetrického algoritmu s verejným kľúčom. Odpovedať Známka: 10.0 Hodnotiť:

Re: ehm (doplnene na 5 znakov) Od: reg: x x l l | Pridané: 3.3.2016 0:11 Ten posledny odstavec je tam zbytocny a splieta prilis vela roznych veci dokopy. DSA je podpisova schema s vyuzitim diskretneho logaritmu a ECC je obecna skratka pre kryptografiu s vyuzitim eliptickych kriviek. Do toho este RSA... No gulas. Ked uz je cely clanok o DH, tak by som spomenul mozno iba ECDH, co je modifikacia DH s vyuzitim vypoctov nad eliptickymi krivkami a pouziva sa dnes uz celkom bezne na vymenu session kluca (tzv. ephemeral key). Na overenie, ze sa naozaj bavime so spravnou stranou, sluzia prave podpisove schemy zalozene na RSA, DSA a najnovsie aj ECDSA. Odpovedať Známka: 3.3 Hodnotiť:

Re: ehm (doplnene na 5 znakov) Od: reg: x x l l | Pridané: 3.3.2016 0:42 Eh, oprava... "vymenu session kluca" ==> "dohodnutie session kluca", pretoze ide samozrejme tiez o tzv. key agreement protokol, kde sa dohodne na oboch stranach zdielane tajomstvo. To je myslim si ta podstatna informacia, ktora v clanku sice je, ale hodne skryta a zaobalena do vela zbytocnych slov. Pointa DH je v tom, ze obe strany si spocitaju rovnake tajomstvo, cisto na zaklade vymeny svojich verejnych klucov. Na to, aby utocnik dokazal vypocitat to iste tajomstvo, by musel prave dokazat odvodit z verejnych aj oba privatne kluce, co znamena v pripade DH prave vyriesit problem diskretneho logaritmu. To, ze sa potom s tym zdielanym tajomstvom symetricky sifruje, to su uz v principe podruzne veci. Ten zdielany kluc da vyuzit aj na ine kryptograficke operacie, napr. na podpisovanie dat a pod. Napr. niektore mobilne banky pouzivaju DH na dohodnutie statickeho kluca, ktorym sa potom podpisuju dodatocne data napr. platobneho prikazu (samozrejme zjednodusene povedane). Odpovedať Hodnotiť:

Re: ehm (doplnene na 5 znakov) Od reg.: _MMx_ | Pridané: 3.3.2016 11:21 > DH [...] bol teraz ocenený ako prvý asymetrický algoritmus s verejným kľúčom. Ja citam, ze oceneni boli ludia za prinos v oblasti sifrovanej komunikacie, specificky spominaju komunikaciu s bankami, obchodmi a cloudom (http://www.acm.org/awards/2015-turing). Ak sa bavime o prinose konkretneho algoritmu, tak tym zrejme myslia pouzitie v TLS protokole (ktory sa na tychto miestach pouziva). Tam sa pouziva DH algoritmus na vymenu symetrickeho sifrovacieho kluca. V sprave Server Key Exchange posiela server parametre p, g, g^a mod p a ich podpis. V Client Key Exchange posle klient g^b mod p. Obidve modularne umocnene hodnoty sa potom pouziju na odvodenie sifrovacieho kluca, ktory pred zaciatkom komunikacie neexistoval (preto sa neda povazovat za privatny ani verejny kluc v standardnom vyzname). Odpovedať Hodnotiť:

Re: ehm (doplnene na 5 znakov) Od reg.: Redakcia DSL.sk | Pridané: 3.3.2016 12:44 A čítali ste to oznámenie ACM? :) Ocenení boli za ideu a hlavne praktickú implementáciu kryptografie s verejným kľúčom ako sa uvádza v prvom a detailne vysvetľuje v štvrtom odstavci od konca. V prvom rade asi si dosť zamieňate DH algoritmus a DH protokol špecificky na vytvorenie kľúča, hoci veľký rozdiel to nie je. U protokolu by sa už dalo diskutovať o tom, ako je ho vhodné charakterizovať. DH algoritmus je v každom prípade aj asymetrickým algoritmom s verejným kľúčom a čo je dôležité bol prvým praktickým. A to bola historicky asi tá jeho dôležitejšia úloha, keď navyše v takomto použití umožňuje aj autentifikovať jednu stranu respektíve dokonca aj obe. Aj keď sa v praxi takto primárne nepoužíva. Totiž treba si uvedomiť, že z každého asymetrického algoritmu schopného šifrovať je možné triviálne spraviť algoritmus na dohodnutie kľúčov. Odpovedať Hodnotiť:

Re: ehm (doplnene na 5 znakov) Od reg.: Redakcia DSL.sk | Pridané: 3.3.2016 12:44 Z akej definície asymetrických algoritmom vychádzate, ktorá by detailne predpisovala akým číslom sa matematicky šifruje a že musí byť známe vopred? Dobré je si tiež prečítať tú pôvodnú prácu D a H, vidieť ako k tomu pristupovali a čo hľadali. Odpovedať Hodnotiť:

som rad ze sa toho dozili Od: Problem | Pridané: 3.3.2016 9:13 Nakolko boli oceneni az po 40 rokoch od ich objavu, som rad, ze sa toho dozili. Odpovedať Známka: 10.0 Hodnotiť:

Re: som rad ze sa toho dozili Od reg.: Pjetro de | Pridané: 3.3.2016 9:30 Tak to chodi, ani mlady Abel sa nedozil slavy s vyuzitim pojmu grupa, a to vyuzitie bolo v matematike sakra ocividne uz na konci 19. storocia. Odpovedať Hodnotiť:

Pridať komentár