neprihlásený Sobota, 3. decembra 2022, dnes má meniny Oldrich
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.


      Zdieľaj na Twitteri



Najnovšie články:

Ďalší veľký webhosting mal dlhý výpadok, kvôli diskovému poľu
VLC začalo podporovať architektúru RISC-V
Helikoptéra na Marse má s novým softvérom letieť v sobotu
Zverejnený trailer Guardians of the Galaxy 3, oznámený termín tretej série The Mandalorian
USA povolili SpaceX iba 7.5 z 30 tisíc Starlink satelitov druhej generácie
Súd schválil odškodnenie zákazníkov MacBookov s problematickou klávesnicou
Orion dnes opustí orbitu Mesiaca a začne sa vracať na Zem
Doterajšie eID sa budú dať na podpis používať asi iba pol roka, podpora bude zrejme slabá
Stanica Trojka skončila
Smartfóny komunikujúce aj cez satelity budú bežnejšie, ďalší avizovaný na prvý štvrťrok


Diskusia:
                               
 

o tom sme sa učili v škole
Odpovedať Známka: 8.5 Hodnotiť:
 

aj my
Odpovedať Známka: 6.4 Hodnotiť:
 

Ked uz sme pri tom, tak namet na spravicku: https://drownattack.com
Odpovedať Známka: 5.0 Hodnotiť:
 

Motivovali ste ma, idem veru aj ja vymysliet nejaky ten algoritmus.
Odpovedať Známka: 10.0 Hodnotiť:
 

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ť:
 

To mi niečo hovorí, kde som to len videl
Odpovedať Známka: 8.3 Hodnotiť:
 

V Blave na stanici
v tretej kabínke to vyškriabal bezdomovec na stenu.
Odpovedať Známka: 10.0 Hodnotiť:
 

film Dobrý Will Hunting
Odpovedať Známka: 3.3 Hodnotiť:
 

nasiel som dokaz a je, pravda, velmi zvlastny, ale nevojde sa mi tu do tejto diskusie
Odpovedať Známka: 8.9 Hodnotiť:
 

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ť:
 

*Pokojne
Odpovedať Známka: 8.0 Hodnotiť:
 

Eventuálne dormanticky. :) http://dopice.sk/gHw
Odpovedať Známka: 10.0 Hodnotiť:
 

Mam, vysledky mozete skontrolovat tu, tu a tu.
Odpovedať Známka: 5.6 Hodnotiť:
 

^_^
Odpovedať Známka: 5.0 Hodnotiť:
 

Velka Fermatova veta uz bola dokazana, takze smola.
Odpovedať Známka: 10.0 Hodnotiť:
 

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ť:
 

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ť:
 

*vpadne. Odporúčam čítať pozornejšie.
Odpovedať Hodnotiť:
 

A veľká Fernetová veta ?
Odpovedať Známka: 4.3 Hodnotiť:
 

radsej riesenie diskretnych logaritmov, to bude efektivnejsie
Odpovedať Známka: 7.1 Hodnotiť:
 

A ked ten sposob riesenia spravne preda, tak za vyrazne viac ako milion dolarov.
Odpovedať Známka: 6.7 Hodnotiť:
 

Kazdy tyzden si na tychto dvoch panov spomeniem v robote. Robim firewally.
Odpovedať Známka: 3.3 Hodnotiť:
 

ale ved ty si murar milanko
Odpovedať Známka: 8.5 Hodnotiť:
 

Murar, a staviam aj tunely
Odpovedať Známka: 10.0 Hodnotiť:
 

Prvá časť je bez otázky a bez debaty, Hellmans. Ale otázka znie, Majolenka, alebo Majonéza?
Odpovedať Známka: 4.0 Hodnotiť:
 

Tatarska omacka :)
Odpovedať Známka: 10.0 Hodnotiť:
 

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ť:
 

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ť:
 

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ť:
 

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ť:
 

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ť:
 

> 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ť:
 

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ť:
 

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ť:
 

Nakolko boli oceneni az po 40 rokoch od ich objavu, som rad, ze sa toho dozili.
Odpovedať Známka: 10.0 Hodnotiť:
 

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