Diffie–Hellman-kulcscsere

Matematika
A matematika alapjai

Halmazelmélet · Naiv halmazelmélet
Axiomatikus halmazelmélet · Matematikai logika

Algebra

Elemi algebra · Lineáris algebra · Polinomok
Absztrakt algebra · Csoportelmélet · Gyűrűelmélet · Testelmélet
Mátrixok · Univerzális algebra

Analízis

Valós analízis · Komplex analízis · Vektoranalízis
Differenciálegyenletek · Funkcionálanalízis
Mértékelmélet

Geometria

Euklideszi geometria · Nemeuklideszi geometria
Affin geometria · Projektív geometria
Differenciálgeometria · Algebrai geometria
Topológia

Számelmélet

Algebrai számelmélet · Analitikus számelmélet

Diszkrét matematika

Kombinatorika · Gráfelmélet · Játékelmélet
Algoritmusok · Formális nyelvek
Információelmélet

Alkalmazott matematika

Numerikus analízis · Valószínűségszámítás
Statisztika · Káoszelmélet · Matematikai fizika
Matematikai biológia · Gazdasági matematika
Kriptográfia

Általános

Matematikusok · Matematikatörténet
Matematikafilozófia · Portál

Sablon:Matematika
  • m
  • v
  • sz

A Diffie–Hellman-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.

Az eljárás Whitfield Diffie és Martin Hellman amerikai kriptográfusokról kapta nevé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.[* 1]

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.[* 2] 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

x g a ( mod N ) illetve y g b ( mod N ) {\displaystyle {\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 x b ( mod N ) , {\displaystyle 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:

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

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

a = 69 b = 73. {\displaystyle {\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:

75 69 61 ( mod 79 ) 75 73 53 ( mod 79 ) . {\displaystyle {\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:

61 73 12 ( mod 79 ) 53 69 12 ( mod 79 ) . {\displaystyle {\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

75 p 61 ( mod 79 ) 75 q 53 ( mod 79 ) {\displaystyle {\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.

Megjegyzések

  1. Az ilyen jellegű eljárásokat nevezik egyutas függvényeknek.
  2. N prímsége lényeges, mert prímszámoknak bizonyítottan van primitív gyöke, ennek rendje pedig a lehető legnagyobb, N-1.

Jegyzetek

Források

  • 9. rész: Alice és Bob nyilvános kulcsot használ. (Hozzáférés: 2024. május 2.)
  • Kiss Péter, Mátyás Ferenc. A számelmélet elemei. Eger: Líceum (1997) 
  • Simon Singh. Kódkönyv. Budapest: Park (2007). ISBN 9789635307982