Szerkesztő:Tombenko/Diffie-Hellmann-kulcscsere

A Diffie—Hellmann-kulcscsere az egyik legelső nyilvános kulcsú rejtjelezés. A lényege, hogy két személy olyan módon tudjon megállapodni közös kulcsban, hogy azt harmadik személy ne tudja megszerezni. Ehhez egy speciális számelméleti eljárást, ún. egyutas függvényt használ.

Az eljárás által információt csak nehézkesen lehet továbbítani, viszont szimmetrikus kulcsú rejtjelezéshez a szükséges kulcsokat biztonsággal meg lehet osztani. Ez pedig utóbbiak egyik legfőbb sebezhetőségét küszöböli ki, mégpedig magának a titkosító kulcsnak a cseréjét.

Elméleti háttér

Az eljárás egyes számelméleti függvények, valamint a hatványozás tulajdonságait használja ki. Lényegében az a helyzet, hogy a hatványozás osztási maradékai egy megadott szám, mint osztó esetében véges sok értéket vehetnek fel. Ezt az értéket a kitevő esetében igen könnyű meghatározni, azonban az érték ismeretében a kitevő csak igen hosszadalmas módon.

Miután célszerű a lehető legtöbb maradékra alapozni, az eljárás során a primitív gyökökre hagyatkozunk. Valamely m modulus esetén ugyanis ezek száma φ(m), prímek esetén konkrétan m-1. Emellett bizonyított, hogy minden prímnek van primitív gyöke, összetett számok esetén azonban ez már nem igaz.

A primitív gyökök maradékai tehát az egyes kitevőkre különbözőek, ráadásul nincs két egymást követő kitevő esetére nem lehet előre tervezni a maradékok értékét, azaz a hagyományos függvényeknél megszokott approximáció itt nem működik. Ez adja az eljárás igazi erejét, ugyanis nagy modulus esetén rengeteg kitevőt kell vizsgálni, ami jelentősen lelassítja a visszafejtést. Van ugyan mód a lehetséges kitevők számát csökkenteni, azonban ehhez φ(m) prímtényezős felbontására van szükség, ami szintén hosszadalmas feladat.

Megvalósítás

Vegyünk egy "nagy" N prímet, és egy g<N primitív gyököt. A két fél ezen kívül választ magának egy-egy saját a, illetve b értéket. Az (N,g) párt nyilvánosságra hozzuk, ez lesz a nyilvános kulcs, míg az a és b értékek a titkos kulcs. Ezekből a feleknek elegendő a saját példányukat ismerni.

Mindketten kiszámolják az

${\begin{aligned}x&\equiv g^{a}{\pmod {N}}\\&{\text{illetve}}\\y&\equiv g^{b}{\pmod {N}}\end{aligned}}$

értéket, és elküldik egymásnak. Ekkor

$y^{a}\equiv x^{b}{\pmod {N}},$

ami éppen a használandó titkos kulcs lesz.

Vegyük észre, hogy nem egy előre meghatározott kulcsot cserélnek ki, hanem éppen most generáltak egyet, azaz a kulcsot csak az információs csatornából lehet kinyerni, azonban a titkos kulcsok ismerete nélkül (amik pedig egyediek, és nem kerülnek a csatornába) nem meghatározható.

Példa

Alíz szeretne Bobnak küldeni rejtjelezett üzenetet, azonban szükséges van egy kulcsraa, amivel titkosít. Ezért választ két számot:

${\begin{aligned}N&=79\\g&=75.\end{aligned}}$

Ezeket elküldi Bobnak. Ezután mindketten választanak maguknak egy-egy titkos számot:

${\begin{aligned}a&=69\\b&=73.\end{aligned}}$

Kiszámoljuk a kulcsot kódoló üzenetet, erre a moduláris hatványozás eljárását használjuk:

${\begin{aligned}75^{69}&\equiv 61{\pmod {79}}\\75^{73}&\equiv 53{\pmod {79}}.\end{aligned}}$

Alíz tehát üzeni Bobnak, hogy 61, Bob pedig válaszol, hogy 53. Ezután mindketten kiszámolják az alábbit:

${\begin{aligned}61^{73}&\equiv 12{\pmod {79}}\\53^{69}&\equiv 12{\pmod {79}}.\end{aligned}}$

Mint látható, a két érték megegyezik, tehát van egy közös titkuk. Ennek megszerzéséhez azonban a

${\begin{aligned}75^{p}&\equiv 61{\pmod {79}}\\75^{q}&\equiv 53{\pmod {79}}\end{aligned}}$

kongruencia-rendszert kell megoldanunk. Igaz, elegendő számunkra p vagy q ismerete is, tehát elegendő az egyikkel foglalkoznunk. Ehhez azonban minden 1< p<78 értéket meg kell vizsgálnunk. ami nagyságrendekkel tovább tart, mint a maradékok meghatározása.

Ezután a 12 használható rejtjelezésre, például XOR kulcsként.

Források

• youproof webhely
• Mátyás Ferenc: A számelmélet elemei
• Kódkönyv