TARTALOMJEGYZÉK
BEVEZETÉS
1
1. AZ ENTRÓPIA
3
2. A DES
7
3. AZ ENIGMA
11
4. RSA
13
5. A RABIN-VARIÁNS
31
6. DISZKRÉT LOGARITMUS
33
7. INTEGRITÁS, SZEMÉLYAZONOSÍTÁS, HITELESÍTÉS
35
8. TITOKMEGOSZTÁS
41
9. ELEKTRONIKUS PÉNZ, KRIPTOGRÁFIAILAG HITELESÍTETT PÉNZ
43
10. ETIMOLÓGIA
47
IRODALOM
51
Bevezetés A titkosság a társadalmak, egymástól elkülönült közösségek kialakulásához kapcsolódik. Egyrészt a rendelkezésre álló er források különböz sége, másrészt az emberi léthez kapcsolódó bizonyos negatív tulajdonságok arra vezettek, hogy az egyes csoportok egymás rovására jutottak meghatározott javakhoz. A javak megszerzésében azok számíthattak nagyobb sikerre, akik képesek voltak meglepni a konkurens társaságot. A meglepetés alapja viszont az, hogy az egyik társaság tud valami olyat, amelyet a másik csoport nem ismer, és amit az egymással való vetélkedés során eredményesen fel lehet használni. A titkosítás története több könyvben is megtalálható. Közülük minden bizonnyal a leghíresebb David Kahn könyve, ugyanis szinte nincs olyan, a kriptológiával foglalkozó könyv, amely ne hivatkozna erre a több mint ezer oldalas könyvre. A történeti szemlélet magyar nyelv könyvek közül említésre méltó Simon Singh m ve, a Kódkönyv, amely már a legújabb rejtjelez eljárásokról is számot tud adni, hiszen ebben az évezredben jelent meg. Igen tanulságos elolvasni Révay Zoltán Titkosírások cím könyvét. Ez a könyv egyrészt azért érdemel figyelmet, mert igen sok jeles magyar személyiségr l derül ki, hogy intenzíven alkalmazta a titkosítás tudományát, és számos érdekes megoldást találtak ki a rejtjelezéshez, másrészt viszont a megjelenésének dátuma szempontjából is érdekes ez a könyv (bár ez elmondható Kahn könyvér l is). Révay Zoltán idézi Aineiasz Taktikosz Taktika cím m vének egyik könyvét, a Poliorkétika-t, közelebbr l ennek XXXI. fejezetét, amelyben Aineiasz a titkos levelekr l ír. Ez a fejezet azzal kezd dik, hogy „A titkos leveleknek mindenféle küldési módjuk van, de a küld nek és a címzettnek egymás között el z leg meg kell állapodnia.”. Ez az idézet azért érdekes, mert a könyv els megjelenése el tt két évvel jelent meg Diffie és Hellman cikke, amely alapjaiban rázkódtatta meg a rejtjelezés világát, és amely alaposan rácáfolt Aineiasz-ra, és közvetve Révayra is, aki a fenti gondolatot lényegében véve a titkosítás alapjának tekintette. (Ez nem csökkenti a Révaykönyv értékét, csupán arra mutat rá, hogy a világ forgandó, és igen rövid id alatt fenekestül tud egyegy tudományág megváltozni. Hasonló változás történt például 1900-ban vagy 1905-ben a fizikában.) Minden titkosító eljárás esetén lényege, hogy az alkalmazott algoritmusról feltételezzük, azt mindenki ismeri, és a titkosságot az úgynevezett kulcs biztosítja. A kulcs az algoritmus egy olyan paramétere, amelyt l függ en ugyanaz az eljárás ugyanazon titkosítandó üzenetb l a kulcs függvényében más és más rejtjelezett szöveget állít el . A klasszikus rejtjelez eljárásoknál a visszafejtéshez szükséges kulcs vagy megegyezett a titkosításhoz használt kulccsal, vagy abból könnyen ki lehetett számolni, így szükséges volt a rejtjelezéshez használt kulcsot is titokban tartani, továbbá az üzenetváltásban résztvev két fél között biztonságosan kicserélni. Más a helyzet akkor, ha az oda-, illetve viszszatranszformáláshoz használt kulcsok olyanok, hogy az egyik ismeretében a másik csak olyan nagy költséggel határozható meg, hogy az meghaladja a megszerzett információ értékét. Ebben az esetben a titkosító kulcs akár nyilvános is lehet, mégsem képes senki illetéktelen elolvasni a rejtjelezett szöveget, mivel nem rendelkezik a visszafejtéshez szükséges kulccsal. Ez az a gondolat, amely Diffie és Hellman cikkében jelent meg, és amely alapján kialakult a nyilvános kulcsú rejtjelezés. E nélkül a mai világ egészen más lenne. A régi id kben lényegében véve csak az államnak voltak féltve rzött titkai (persze a szépasszonyok sem akartak mindent az uruk orrára kötni, de ezek kevésbé lényeges titkok...), így elegend volt csupán néhány tucat kulcsot el állítani és kicserélni. (Ez utóbbi egy kényes pontja a rejtjelezésnek, hiszen a kulcsot biztonságosan és titkosan kell eljuttatni a másik félnek, amikor persze felmerül a kérdés, hogy miért nem magát az üzenetet cserélik ez alkalommal ki. Erre azonban könny a válasz: a kulcsot bármely id ben cserélhetjük, és a cserére ritkán van szükség, továbbá a kulcs általában rövid az üzenethez képest.) A mai világban viszont a titkosítandó információk túlnyomó többsége gazdasági jelleg , és magánszemélyekhez, vállalatokhoz kapcsolódik. Potenciálisan minden ember és minden vállalkozás rendelkezik titkolandó adattal, amelyet a legkülönböz bb intézményekkel kell kicserélnie. A titkos kulcspár alkalmazása esetén különböz partnerhez más és más kulcsra lenne szükség, ami azt jelentené, hogy hihetetlenül sok kulcsot kellene igen gyakran rendkívül sok pár között kicserélni, és a titkos kulcsokat megfelel en adminisztrálva biztonságosan tárolni, ami megoldhatatlan feladat elé állítaná az egyszer honpolgárokat. Még azt is figyelembe kell venni, hogy
Bevezetés a kulcsot viszonylag gyakran kell cserélni, még az el tt, hogy illetéktelen személy megfejtené, és így a továbbiakban a titkos információnkat olvasni tudná. Az el bbi gondolatok alapján joggal merül fel a kérdés, hogy kell-e egyáltalán foglalkozni a klasszikus, szimmetrikus rejtjelez rendszerekkel. A válasz meglep módon igen. A helyzet ugyanis az, hogy a szimmetrikus rendszerek lényegesen gyorsabbak, mint a nyilvános kulcsú eljárások, ezért a legtöbb esetben egy-egy konkrét üzenetváltás el tt a nyilvános kulcsú rejtjel segítségével a két partner kicserél egy kulcsot, és a továbbiakban az aktuális információt az így megismert kulcs segítségével, egy klasszikus módszerrel küldik egy nyilvános csatornán keresztül.
2
1. Az entrópia Az entrópia információelméleti fogalmát Shannon határozta meg. Korábban Heartley vizsgálta matematikai szempontból az információt, és úgy találta, hogy ha n különböz üzenet lehetséges, akkor egy-egy üzenet információtartalma I = log n . E szerint a kifejezés szerint azonban a különböz üzenetek azonos mennyiség információt, új ismeretet közölnek a fogadóval. Ezzel szemben Shannon úgy gondolta, hogy egy üzenet annál több információt szolgáltat, minél váratlanabb, minél kevésbé lehet rá számítani, azaz minél kisebb a valószín sége. Ha X egy véges eseménytér, az üzenetek halmaza, és az xi ∈ X üzenet pi valószín séggel fordul el , akkor tehát Shannon szerint az xi üzenet I ( pi ) információt szolgáltat, ahol I egyel re ismeretlen függvény. Az n üzenetet tartalmazó teljes üzenethalmaz átlagos információtartalma az egyes üzenetek információtartalmának várható értéke, azaz H ( p n −1 ,
, p0 ) =
n −1 i =0
p i I ( pi ) , ahol H az entrópiafüggvény. Mivel egyel re I ismeretlen, ezért H-t
sem ismerjük. H meghatározásához bizonyos feltételeket kell megfogalmazni. Egy lehetséges axiomatikus bevezetés az alábbi kikötéseket tartalmazza: 1. 2.
3. 4.
( pn−1 , , p0 ) véges diszkrét valószín ségi eloszlás; H ( p n −1 , , p 0 ) a változóinak szimmetrikus függvénye, azaz ha π az {i ∈ N tetsz leges permutációja, akkor H ( p n −1 , , p 0 ) = H ( pπ (n −1) , , pπ (0 ) ) ; H (tp n −1 , (1 − t ) p n −1 , , p 0 ) = H ( p n −1 , , p 0 ) + p n −1 H (t ,1 − t ) , ha t ∈ ]0,1[ ⊆ R ; H (t ,1 − t ) t-nek folytonos függvénye, ha t ∈ ]0,1[ ⊆ R ;
5. H
i < n } halmaz
1 1 , > 0. 2 2
Bizonyítható, hogy a fenti feltételeknek egy adott H függvény felel meg, konkrétan a H ( p n −1 ,
, p0 ) = −
n −1 i =0
1 1 , > 0 érték esetén egy és csak egy 2 2
pi log pi függvény, és akkor ebb l leolvasva
1 valószín n séggel fordul el , és ekkor valóban igaz, hogy az egyedi üzenetek által közvetített információ mértéke I = log n . Általános esetben viszont az egyes üzenetek bekövetkezése különböz valószín séggel történik, tehát általában I ( p i ) ≠ log n . Mivel a logaritmusfüggvény csak a pozitív valós számokra értelmezett (legalábbis mint valós érték függvény), ezért a pi valószín ségek értéke pozitív. Ha pi a pozitív valós számokon keresztül tart a 0-hoz, akkor a logaritmusfüggvény értéke abszolút értékben a ∞ -hez tart, így pi log pi → 0 ⋅ ∞ . De lim ( pi log pi ) létezik, és 0-val egyenl , ezért az entrópia-
I ( pi ) = − log pi . Ha valamennyi üzenet valószín sége azonos, akkor közülük bármelyik
pi → 0+ 0
függvényt kiterjeszthetjük arra az esetre is, amikor egy vagy több valószín ség értéke 0, azzal, hogy ekkor pi log pi := 0 . A függvényr l látható, hogy H ( p n −1 , , p 0 ) ≥ 0 , és a függvény értéke akkor és csak akkor 0, ha egy kivételével valamennyi valószín ség 0 (és ekkor az az egy nem nulla valószín ség 1, hiszen a valószín ségek összege 1). Az el bbi felírásban nem adtuk meg konkrétan a logaritmus alapját, ám erre nincs is szükség. Ha ugyanis egy alapról áttérünk egy másikra, az csupán a mértékegység megváltozását jelenti, hiszen log a u = log a b ⋅ log b u . Hasonló ez ahhoz, mint amikor a hosszúságot méterben, vagy lábban adjuk meg. Magát a logaritmus alapját, r-et H
1 1 , = c (amely a feltétel értelmében pozitív) határozza 2 2
1. Az entrópia 1
1 1 1 1 1 1 , = − log r + log r = log r 2 -b l r = 2 c . Mivel c pozitív, ezért r > 1 . 2 2 2 2 2 2 Az alap szokásos értéke az információelméletben 2, és ekkor az entrópia egysége a bit. Ezt az elnevezést John W. Tukey vezette be a „binary digit” rövidítéseként. Tekintettel arra, hogy ugyanez a neve egy kettes számrendszerben felírt szám egy-egy számjegyének, ezért megkülönböztetésül az információelméleti egységet szokás „binary unit”-ként, a „binary unit” rövidítéseként említeni. Ha a pi valószín ségek az X eseményhalmaz elemei el fordulásainak a valószín ségei, akkor H ( p n −1 , , p 0 ) tulajdonképpen az X tér entrópiáját adja meg, ezért ezt az értéket H ( X ) -szel is jelölhetjük. meg, ugyanis c = H
Csupán az érdekesség, és bizonyos patriotikus büszkeség miatt jegyezzük meg, hogy Shannonnak Neumann János javasolta az entrópia elnevezést, lévén, hogy a kifejezés matematikailag hasonló alakú, mint a korábbi fizikai entrópia. Az elnevezést a formális hasonlóságon kívül bizonyos tartalmi azonosságok is alátámasztják, bár igen komoly eltérések is kimutathatóak a két entrópiafogalom között, amiért többen károsnak tartják az azonos megnevezést. Shannonnak más „magyar kapcsolata” is volt: foglalkozott sakkautomatával, és ezzel kapcsolatban megemlítette Kempelen Farkas nevét, valamint a kommunikációról szólva Gábor Dénest nevezi meg egyik úttör ként. A fenti H-függvény a Shannon-féle entrópiafüggvény. Van más kifejezés is az entrópiára. n −1 1 H α ( p n −1 , , p 0 ) = log i =0 piα a Rényi-féle entrópia, ahol α 1-nél kisebb, nem negatív valós 1−α szám. Ez a kifejezés határértékként tartalmazza a Shannon-féle entrópiát, ha α balról tart 1-hez. A H ( p n −1 ,
, p 0 ) függvénynek az értelmezési tartományában pontosan egy maximuma van a
1 1 , , helyen, és ekkor az értéke log n , ami éppen 1, ha a logaritmus alapszáma is n n n. Ez az entrópia intuitív értelmezése alapján világos, hiszen átlagosan akkor jutunk a legtöbb információhoz, akkor lehet a legkevésbé megjósolni a soron következ üzenetet, ha lényegében véve semmit sem tudunk az egyes üzenetekr l, bármelyik esemény azonos valószín séggel következhet be. A pontos bizonyítás például a következ lehet. Legyen n pozitív egész szám, n > i ∈ N -re a i nem nega-
( p n−1 ,
, p0 ) =
tív és bi pozitív valós szám, a =
n −1 i =0
n −1
a i és b =
i=0
bi . Ekkor (figyelembe véve, hogy a logaritmus
alapszáma, r, egynél nagyobb, és így a logaritmusfüggvény mindenütt szigorúan konkáv, tehát az érintési pont kivételével mindenütt az érint alatt marad) n −1 i =0
≤
n −1 i=0
a i log
a i log
bi = ai
b + a
n −1 i =0
n −1 i =0
a i log
ai
b b b + i − a ai a
≤
1 a bi b b − = a log ln r b a i a a
ai = c . Ha most a i = p i és bi = 1 , akkor a = 1 bi és b = n , és H ( p n −1 , , p 0 ) ≤ log n , továbbá akkor és csak akkor lesz H ( p n −1 , , p 0 ) = log n , ha a 1 valószín ségek megegyeznek, vagyis valamennyi i-re p i = . n és egyenl ség akkor és csak akkor áll, ha minden i-re
A továbbiakban szükségünk lesz az entrópiafogalom kiterjesztésére. Tegyük fel, hogy két véges valószín ségi szkémánk van, az egyik az X, a másik az Y eseménytéren, az el bbiben m, az utóbbiban n eseménnyel. Legyen pi annak a valószín sége, hogy az xi ∈ X esemény következett be, q j az
4
1. Az entrópia y j ∈ Y esemény el fordulásának valószín sége, ri , j annak a valószín sége, hogy az xi és y j esemény együttesen bekövetkezett, míg t i
j
az xi ∈ X esemény el fordulásának valószín sége, feltéve,
hogy y j ∈ Y bekövetkezett. Most az alábbi entrópiákat vezethetjük be: 1. H ( X , Y ) = −
m −1
n −1
i =0
j =0
( (
))
pi , j log pi , j az együttes entrópia
2. H ( X Y ) = E H X y j =
n −1 j =0
(
)
pjH X yj = −
n −1 j =0
pj
m −1
n −1
m −1
i=0 i j
j =0
i=0
t log t i j = −
p i , j log t i
j
az Y-ra vonatkozó feltételes entrópia (most E a várható értéket jelöli), és hasonló az X-re vonatkozó feltételes entrópia, H (Y X ) is. Mivel a fent bevezetett fogalmak lényegében véve azonosak a korábbi entrópiafogalommal (annyi eltéréssel, hogy a feltételes entrópia egy átlagos entrópia), ezért a fenti függvények értéke is nem negatív. Belátható továbbá, hogy 1. H (X Y ) ≤ H ( X ) 2.
H ( X , Y ) = H (Y ) + H (X Y )
= H ( X ) + H (Y X )
Az els egyenl tlenség azt fejezi ki, hogy ha az X üzenethalmazról már van valamilyen a priori ismeretünk, akkor legfeljebb annyi új információhoz jutunk, mint az el bbi ismeretek nélkül. A második egyenl ség viszont azt jelenti, hogy az együttes üzenethalmaz átlagos információtartalmát például úgy kapjuk meg, hogy meghatározzuk önmagában az X forrás információtartalmát, és ehhez még hozzávesszük azt az információmennyiséget, amelyet már az X ismeretében az Y forrásból nyerhetünk. A két pont összevetéséb l az is látszik, hogy az együttes entrópia nem lehet nagyobb, mint a két különkülön számolt entrópia összege, vagyis H ( X , Y ) ≤ H ( X ) + H (Y ) . Végezetül még egy fontos fogalmat definiálunk, a kölcsönös információt. Ezt a fogalmat az entrópiából kaphatjuk, nevezetesen I ( X , Y ) := H ( X ) − H (X Y ) . A fentebbi 2. összefüggésb l kapjuk,
hogy I ( X , Y ) = H (Y ) − H (Y X ) , valamint I ( X , Y ) = H ( X ) + H (Y ) − H ( X , Y ) is teljesül. Figyelembe
véve a H ( X Y ) ≤ H ( X ) egyenl tlenséget, látjuk, hogy a kölcsönös információ értéke is mindig nem
negatív. Ha X és Y függetlenek, akkor I ( X , Y ) = 0 , hiszen ekkor H ( X Y ) = H ( X ) , és a kölcsönös információ értéke H ( X ) , ha determinisztikus kapcsolat van Y és X között, mert ebben az esetben a feltételes entrópia értéke 0.
A fentiekben megfogalmazott entrópia olyan üzenetforrásra vonatkozik, amely az egyes üzeneteket egymástól függetlenül bocsátja ki. Az entrópia általánosabb esetre is megadható, de ezzel a továbbiakban nem foglalkozunk.
5
2. A DES A klasszikus rendszerek két nagy módszert alkalmaztak. Az egyik a helyettesítés, amikor egyegy bet t, vagy a bet k egy csoportját helyettesítik valamilyen jellel, vagy jelcsoporttal, míg a másiknál az üzenet egy-egy meghatározott hosszúságú szakaszán megváltoztatják a bet k sorrendjét, vagyis transzpozíciót alkalmazunk. Ha nagy redundanciájú üzeneteket sifrírozunk, akkor elegend en hosszú üzenet esetén a kulcs könnyen megfejthet . Igencsak meglep , hogy ha az úgynevezett egyszer , vagy más néven monoalfabetikus helyettesítést alkalmazzuk, vagyis ha mindenegyes bet t ugyanazon szabállyal helyettesítünk, akkor a lehetséges helyettesítések, tehát a különböz kulcsok száma a 26bet s angol ábécé alkalmazása esetén 403 291 461 126 605 635 584 000 000, így az ember azt gondolná, hogy szinte lehetetlen megállapítani az aktuális kulcsot. A valóság viszont az, hogy ha a rejtjelezett szöveg egy tipikus, hétköznapi szöveg, akkor egy körülbelül 20 bet s szöveg egyértelm en viszszafejthet a kulcs el zetes ismerete nélkül. A fejtés alapja a bet frekvencia. Minden nyelvre jellemz , hogy az egyes bet k milyen gyakorisággal fordulnak el . Ha monoalfabetikus helyettesítést alkalmazunk, akkor a szöveg bet i a sifrírozás során grafikusan megváltoznak, de nem változik meg az eredeti szövegben lév el fordulásuk gyakorisága, és ezt lehet kihasználni a fejtéshez. Ha csak az egyes bet k gyakoriságát nézzük, akkor körülbelül 80 bet s szöveg kell az egyértelm fejtéshez, ám nézhetünk egyéb jellemz tulajdonságokat is. Ilyen például a bet k egymásra következésének gyakorisága, a kett s bet k gyakorisága, vizsgálhatjuk a szókezd és a szó végén álló bet k gyakoriságát (feltéve, hogy a rejtjelezés során nem gyomlálták ki az árulkodó szóközöket), stb. Ha mindezt figyelembe vesszük, akkor alakul ki a már említett körülbelül 20 bet s szöveg fejthet sége. Nehezíti a fejtést, ha tömörítünk. Ha például számsorozatokat rejtjelezünk, amikor is bármely sorozat értelmes üzenet lehet, vagyis ha a redundancia 0, akkor ilyen kapaszkodónk nincs a fejtéshez. A módszert úgy lehet bonyolítani, ha vagy más és más szabállyal végezzük az egyes pozíciókon a helyettesítést – ez a többábécés, vagyis másként a polialfabetikus helyettesítés – , vagy sok bet b l álló blokkokat helyettesítünk, ami a blokk-kódok alapja. Az el bbi széls esete a Vernam által javasolt véletlen átkulcsolás. Ez olyan eljárás, ahol minden pozícióhoz abszolút véletlenül választjuk a helyettesítési szabályt (ez a további üzenetekre is érvényes, vagyis az egyszer elkezdett véletlen sorozatot kell folytatni, nem lehet újra kezdeni a generálást). Szemléletesen is belátható, hogy ez a titkosítás elvileg is fejthetetlen, hiszen bármely eredeti bet höz, és tetsz leges rejtjelbet höz van olyan transzformáció, amely az el bbit az utóbbiba alakítja, és minden helyettesítés azonos valószín séggel kerülhetett alkalmazásra, vagyis a rejtjelezett szövegb l egyenl valószín séggel bármilyen eredeti szöveg el állítható. A pontos matematikai bizonyítást – ami lényegében véve semmivel nem nehezebb az el bbi gondolatmenetnél – Shannon végezte el. Ennél a módszernél természetesen fokozottan igaz, hogy igen nehéz a kulcs biztonságos kicserélése a két fél között, ám mégis alkalmazták a gyakorlatban, nevezetesen a Moszkva és Washington közötti forró dróton. A gyakorlatban inkább a blokk-kódok terjedtek el, amelyeknek egyik leghíresebb képvisel je a DES (Data Encryption Standard), amelyet 1977-ben fogadtak el szabványként, és egészen 2002-ig volt szabvány, ekkor váltotta fel az AES (Advanced Encryption Standard), ám amelyet f leg a háromszor egymás után alkalmazott formájában még ma is igen széles körben alkalmaznak. A DES egy igen fontos jellemz je, hogy jóllehet elvileg bármely rejtjelrendszer esetén felteszik, hogy maga az algoritmus ismert, ez volt a világ els olyan rejtjelez algoritmusa, amelyet hivatalosan nyilvánosságra hoztak (bár vannak, akik ezt nem akarják elhinni, és feltételezik, hogy a rendszert kifejleszt IBM bizonyos információt megtartott magának, amelynek a segítségével képes fejteni a titkosított üzeneteket). A DES jelent ségét még az is alátámasztja, hogy az azóta kifejlesztett blokkos rejtjelez rendszerek majd mindegyike többé-kevésbé a DES-nél alkalmazott elvekre, de legalábbis az elvek egy részére épül. A DES három pilléren nyugszik.
2. A DES 1. Tegyük fel, hogy egy r-bet s ábécével írt n-bet s blokkot p-hosszúságú kulccsal rejtjelezünk (maga a kulcs a szöveggel azonos ábécéb l épül fel). Ekkor egy blokk kiszámítása lényegében véve egy n + p változótól függ , n egyenletb l álló egyenletrendszer: n ≥ i ∈ N + : c i = fˆi (m1 ,
, mn ; k1 ,
,kp )
ahol m j a nyílt szöveg egy blokkjának j-edik, k l a kulcs l-edik, és ci a rejtjelezett szöveg blokkjának i-edik bet je. Ha r egy prímhatvány, akkor a szimbólumhalmaz egy véges testnek tekinthet . Ilyen esetben bármely leképezés, amely a véges testet önmagába képezi, megadható egy polinommal, így feltehetjük, hogy az fˆ leképezés az f polinomhoz tartozó polinomfüggvény. Hasonló a helyzet a i
i
desifrírozás esetén:
n ≥ i ∈ N + : mi = gˆ i (c1 ,
, c n ; k1 ,
,kp )
Ha az algoritmus nyilvános, akkor ismertek a polinomok, és ekkor a fejtés egyszer behelyettesítés, ám a kulcs ismerete nélkül a feladat az eredeti polinomok által meghatározott egyenletrendszer megoldását jelenti. Ha a polinomok nem lineárisak, akkor viszont az ilyen egyenletrendszer megoldása NP-nehéz, és így elegend en nagy blokkok esetén a fejtés – bár elméletileg lehetséges – gyakorlatilag a használható id n belül reménytelen feladat. 2. Shannon szerint önmagában sem a helyettesítés, sem a transzpozíció nem nyújt kell védelmet – leszámítva a véletlen átkulcsolást, amely viszont egészen extrém alkalmazásoktól eltekintve a gyakorlatban alkalmazhatatlan. Shannon az úgynevezett kever transzformáció többfordulós alkalmazását javasolta. Itt egy-egy forduló egy kulcstól függ helyettesítésb l és egy transzpozícióból áll. A nehézséget az okozza, hogy ha nagy a blokkméret – márpedig a megfelel titkossághoz elegend en nagy blokkméretre van szükség – , akkor nehéz a helyettesít táblázatok tárolása (egyszer en számítható helyettesítés nem jöhet szóba, hiszen azt bárki könnyen tudná fejteni). Shannon ezt úgy javasolta megoldani, hogy a blokkot több kisebb részblokkra bontotta, és ezekre a kisebb részekre alkalmazta a helyettesítést. A dologban lényeges, hogy az utána következ transzpozíció az el bbi fordulóban egy részblokkban elhelyezked bet ket különböz blokkba helyezi. A leképezést úgy alakítják ki, hogy érvényesüljön az úgynevezett lavinahatás, vagyis ha a bemeneten egyetlen bet t megváltoztatunk, akkor a kimeneten, azaz a rejtjelezett szövegben a teljes blokk bet inek a fele változzon, de úgy, hogy a kimenet minden bet je ½ valószín séggel változzon, továbbá a kimenet bármely bet je a bemenet valamennyi bet jét l függjön, és egy kimeneti bet megváltozásából ne lehessen következtetni a bemeneti változásra. 3. A DES az úgynevezett Feistel-struktúra alapján m ködik. Legyen a rejtjelezend szöveg m, amelynek hossza 2n , és válasszuk két részre úgy, hogy az egyik rész a szöveg els n bet jéb l, míg a másik a hátsó n bet b l áll, azaz az el bbit m (0 ) -lal, a másodikat m (1) -gyel jelölve m = m (0 ) m (1) . Tegyük továbbá fel, hogy az algoritmus t fordulóból áll, és mindenegyes fordulóban az eredeti kulcsból származtatott alkulcsot alkalmazunk. A Feistel-struktúrában alkalmazott transzformáció ezek után a következ :
t ≥ i ∈ N + : m (i +1) = m (i −1) + f (m (i ) , k (i ) ) Az m-hez tartozó rejtjelezett szöveg c = m (t +1)m (t ) . A kulcs ismeretében a visszafejtés rendkívül egyszer , hiszen c-b l ismert m (t +1) és m (t ) , és ha ismerjük valamilyen t ≥ j ∈ N + -ra m ( j +1) -et és m ( j ) -t,
akkor m ( j +1) − f (m ( j ) , k ( j ) ) = m ( j −1) , vagyis c-b l meg tudjuk határozni m (1) -et és m (0 ) -t, tehát m-et. Látható, hogy a rejtjelez és a visszafejt algoritmus csak annyiban tér el, hogy az egyikben összeadás, a másikban kivonás áll (ami bináris esetben egyébként megegyezik), és a kulcsokat fordított sorrendben
8
2. A DES kell alkalmazni. Igen lényeges tulajdonsága a Feistel-struktúrának, hogy f nem feltétlenül invertálható, amely tulajdonság nagyon megkönnyíti a rejtjelezés szempontjából jó tulajdonságú függvény keresését. Konkrétan a DES esetén az ábécé két bet b l, a 0-ból és az 1-b l áll, és a blokkméret 64 bit. A kulcs is 64 bites, de ebb l 8 bit ellen rz funkciót lát el, így valójában a kulcs 56 bites (ezt vetették leginkább a DES szemére, és sokan úgy vélték, hogy azért választották ilyen méret re a kulcsot, mert a titkosszolgálatok a maguk számítástechnikai apparátusaikkal abban az id ben ekkora méretekkel boldogultak). Az eljárás 16-fordulós, és a kulcsból úgy állítják el az egyes fordulókhoz az aktuális alkulcsot, hogy a 16. forduló után éppen visszanyerik az eredeti kulcsot (ez inkább a hardveres megoldás szempontjából jelent némi el nyt). A bináris ábécé esetén, mint fentebb már említettük, a kivonás megegyezik az összeadással, így a desifrírozás teljes egészében megegyezik a sifrírozással, csupán a kulcsokat kell fordított sorrendben alkalmazni. A mai számítástechnikai eszközökkel a DES fejtése könny feladat, ezért különböz kulccsal többször egymás után alkalmazzák. Egy rejtjelez rendszer több kulccsal való iterációja csak akkor eredményezhet az egy kulccsal való titkosításnál er sebb védelmet, ha a leképezések kompozíciója nem alkot csoportot, vagyis ha két egymás utáni titkosítás nem állítható el valamely kulccsal történ egylépéses leképezésként. Ez a DES esetén teljesül. Kevés számolással kimutatható, hogy a kétszeres DES sem nyújt ma már kell védelmet, ám a háromszoros DES biztonságosnak mondható, és igen sok helyen alkalmazzák ma is. A blokkos rejtjelezéseket, és így a DES-t is, különböz üzemmódban alkalmazzák, amelyek még növelik a rendszer hatékonyságát, biztonságát. Egy ilyen az úgynevezett CBC-mód (Cipher Block Chaining), a blokkláncolás. Ennél az üzemmódnál választunk egy c0 kezd blokkot, és ebb l kiindulva egymás után képezzük a ci = E k (mi , ci −1 ) blokkokat, ahol E k a k kulcstól függ rejtjelez leképezés. A szabályból látszik, hogy a rejtjelszöveg i-edik blokkja nem csupán a nyílt szöveg i-edik blokkjától, hanem valamennyi korábbi blokktól is függ.
9
3. Az ENIGMA A rejtjelez – visszafejt tevékenység gépesíthet is, így bonyolultabb eljárások alkalmazhatóak. Ennek egyik példája az Enigma. Az Enigma1 egy olyan elektromos írógép, melynek három f bb egysége van: egy billenty zet a nyílt szöveg bet inek bevitelére, egy átalakító egység, amely a nyílt szöveg bet it a rejtjeles szöveg megfelel bet ivé alakítja, és egy kijelz panel, amelyen kis lámpácskák felvillanása jelzi a rejtjeles szöveg bet it. A felvillanó bet ket leírva kapjuk meg a rejtjeles szöveget, amelyet azután rádión továbbítottak a címzettnek. A vev oldalon egy azonos beállítású enigmával írták le a szöveget, és a lámpák felvillanása adta vissza a nyílt üzenetet. A gép legfontosabb része az átalakító egység, amely három kivehet kever tárcsából áll, így ezek cserélhet ek. A kever tárcsa egy vezetékekkel s r n telesz tt, vastag gumitárcsa. A nyílt szöveg bet inek sifrírozását a kever tárcsák bels huzalozása határozza meg. Ha a tárcsák fix helyzet ek lennének, akkor a tárcsák huzalozása egy egyszer egyábécés helyettesítéses eljárást valósítana meg. Sherbius gépének viszont a legfontosabb jellemz je, hogy a kever tárcsák forognak. Minden egyes bet sifrírozása után az els tárcsa 1 26 -odnyival elfordul (26 bet s ábécé esetén). A második tárcsa csak akkor fordul 1 26 -odnyit, ha az els tárcsa megtett egy teljes fordulatot, a harmadik tárcsa akkor fordul 1 26 -odnyit, ha a második tárcsa megtett egy teljes fordulatot, miközben az els tárcsa már 26 × 26 -szor fordult 1 26 -odnyit. Ez a mechanizmus hasonlít az autók kilométerórájához. A rotáció révén a gép többábécés helyettesítéses eljárás megvalósítására használható. A három kever tárcsa kezdeti beállítása 26 × 26 × 26 = 17 576 különböz kulcsnak felel meg. Az ábrán az Enigma kétdimenziós ábrázolása látható, az áttekinthet ség kedvéért hatbet s ábécé esetén. A kever tárcsa egybet nyi elfordulása során a tárcsákat összeköt vezetékek egy hellyel lentebb kerülnek.
Enigma kapcsolási rajza A kapcsolási rajzon még két szerkezeti elem is látható. A visszairányító szintén egy bels huzalozású gumitárcsa, de nem forog. Mikor a kezel begépel egy bet t, azzal egy elektromos jelet küld át a három kever tárcsán. A visszairányító ezt a beérkez jelet küldi vissza, de más útvonalon. Az ábrán látható tárcsaállások esetén a leütött b bet a C-t villantja fel, ha azonban a c-t ütöttük volna le, akkor a kijelz n a B villant volna fel. Ebb l látható a visszairányító szerepe: a gép a nyílt szöveg 1
Az Enigma-ra vonatkozó részt Tóthné Mészáros Ágnes Rejtjelezés a középiskolában cím szakdol-
gozatából vettem át.
3. Az ENIGMA egyik bet jét a rejtjeles szöveg egyik bet jévé alakítja, és ha egy másik gép ugyanígy van beállítva, akkor az el bb megkapott rejtjeles szöveg bet jét leütve megkapjuk az eredeti nyílt szöveg bet jét, vagyis a sifrírozáshoz és a desifrírozáshoz ugyanaz a gép szükséges megegyez kezd beállítással! A másik új elem az ábrán a kapcsolótábla, mely a billenty zet és az els kever tárcsa közé van iktatva. E kapcsolótábla lehet vé teszi, hogy beiktassunk néhány vezetéket, amelyek még az els kever tárcsába való belépés el tt felcserélnek bizonyos bet ket. Az Enigma kezel jének hat ilyen vezetéke van, miáltal hat bet párt tud felcserélni a huszonhatból. Egy 26-bet s ábécé esetenkénti hat bet párjának felcserélési lehet ségeinek száma 5
∏ k =0
26 − 2k 2 = 100 391 791 500 . 6!
A gép alapbeállításához tartozik még a kever tárcsák sorrendje is. Scherbius úgy szerkesztette meg gépét, hogy a kever tárcsák sorrendjét meg lehessen változtatni, a kever tárcsák kivehet ségével. A három tárcsa 6-féleképpen helyezhet a gépbe, így a lehetséges kezd beállítások, vagyis kulcsok száma: kever tárcsák beállítása (minden tárcsa 26-féle pozícióba állítható): 17 576 6 kever tárcsák sorrendje: kapcsolótábla beállításai: 100 391 791 500 összesen (el z három tényez szorzata): 10 586 916 764 424 000 A rejtjelezés kulcsát (a gép kezd beállítását) naponta változtatták, amit a négyhetente szétosztott 28 kulcsot tartalmazó kódkönyv határozott meg. A kapcsolótábla eredményezi a kulcsok számának legnagyobb növekedését, de a sifrírozás megkezdése után már nem változik beállítása, így egyedüli alkalmazása olyan rejtjeles szöveget generálna, amely gyakorisági elemzéssel megfejthet . A kever tárcsák kevesebb számú kulccsal járulnak hozzá a végeredményhez, de beállításuk folyamatosan változik, aminek eredményeképpen a rejtjeles szöveg gyakorisági elemzéssel nem fejthet meg. Mivel a rejtjelezés során a gép 17 576 különböz sifre-ábécét használ, Babbage módszerével sem fejthet meg a rejtjeles szöveg.
12
4. RSA Az RSA a leggyakrabban alkalmazott és a legjobban bevált nyilvános kulcsú rejtjelezési algoritmus, amelyet sokan és igen alaposan vizsgáltak, és amely a publikus információk alapján gyakorlatilag fejthetetlen, ha a paramétereket a megfelel gondossággal választják. Az algoritmus neve az t kifejleszt három matematikus: Rivest, Shamir és Adleman nevének kezd bet je. a . A definíb cióból könnyen kiolvasható, hogy ha a egész szám és b pozitív egész szám, akkor a mod b ≡ a (b ) és 0 ≤ a mod b < b , vagyis ekkor a mod b az a-nak b-vel való osztásakor keletkez nem negatív maradéA továbbiakban az a és a nem nulla b valós szám esetén legyen a mod b := a − b
ka. Ha a 1-nél nagyobb, b pozitív és c tetsz leges valós szám, akkor a −∞ -t nullának,
b b -t ∞ -t és 0 0
nek, végül c − ∞ -t − ∞ -nek tekintjük. Használni fogjuk a következ jelölést.
4.1.
Jelölés
Legyen n ∈ N + . Ekkor M (n ) = {m ∈ N m < n } .
∆ Nyilvánvalóan látszik, hogy minden n ∈ N + -ra M (n ) = n .
4.2.
Definíció Legyen p A és q A két különböz páratlan prímszám, n A = p A q A , e A a ϕ (n A ) -hoz relatív prím pozitív egész, és d A az e A x ≡ 1 (ϕ (n A )) kongruencia tetsz leges pozitív megoldása. Ekkor (n A , e A ) az
A nyilvános kulcsa, d A a titkos kulcsa, M A = M (n A ) = C A az A nyílt illetve rejtjeles szövegeinek halmaza, és az m ∈ M A nyílt szöveg rejtjeles párja c = E e A (m ) = m e A mod n A .
∆ Maga a rejtjelezés könny feladat, polinomiális id ben végrehajtható. Valóban: mivel a hatványozást csupán modulo n A végezzük, ezért minden lépésben két, legfeljebb b = log r n A + 1 hosszúságú számot szorzunk (r a számrendszer alapszáma), aminek az id igénye b 2 nagyságrend , és ilyen szorzásból legfeljebb 2t -re van szükség, ahol t = log 2 e A , amint az alábbi tétel mutatja:
4.3.
Tétel Legyen u pozitív egész, m tetsz leges egész, és u =
t −1 i=0
u i 2 i , ahol t = log 2 u + 1 . Ekkor az
m (t −1) := m , t − 1 > i ∈ N : m (i ) := m ui m (i +1) mod n algoritmussal m (0 ) = m u mod n , és a szorzások száma s, ahol t − 1 ≤ s ≤ 2(t − 1) . ∆ 2
Bizonyítás:
4. RSA A definíció alapján könny igazolni, hogy a (b mod n ) mod n = ab mod n , ha a, b és n egész számok, így elég belátni, hogy amennyiben P (t −1) = m és a t − 1 > i ∈ N indexekre P (i ) = m ui P (i +1) , akkor P (0 ) = m u . Ha t = log 2 u + 1 , akkor 2 t −1 ≤ u < 2 t , vagyis u felíráshoz pontosan t bit kell, és u t −1 = 1 . Most 2
t −1
u 2 j = t −1 j
P (t −1) = m = m1 = m ut −1 = m akkor
j − ( t −1 )
, és ha valamilyen t − 1 > i ∈ N indexre P (i +1) = m
t −1
P
(i )
=m P ui
(i +1) 2
=m
ui
m
u j 2 j − ( i +1 )
j = i +1
t −1
2
t −1
=m m ui
u j 2 j −i
j = i +1
t −1
=m
t −1
u 2 j = i +1 j
j − ( i +1 )
,
u j 2 j −i
j =i
uj2j
innen pedig i=0 esetén kapjuk, hogy P (0 ) = m j = 0 = mu . Az algoritmus – t bit esetén – t − 1 lépésb l áll (leszámítva az inicializálást, amely egyszer értékadás). Minden lépés tartalmaz egy négyzetreemelést, amely egy szorzás, ez összesen t − 1 szorzás. u i értéke 0 vagy 1; az els esetben m ui = 1 , tehát a négyzetreemeléssel megkaptuk m (i ) értékét, míg u i = 1 esetén m ui = m , vagyis m (i +1) -et még meg kell szorozni m-el, így az ilyen szorzások száma legfeljebb t − 1 . 2
4.4.
Megjegyzés
A bizonyításból létszik, hogy az algoritmus nem csak a moduláris, de a közönséges hatványozásra is hasonlóan m ködik, vagyis a tétel és a bizonyítás jelöléseivel m u = P (0 ) , és az eredmény most is legalább t − 1 és legfeljebb 2(t − 1) szorzással megkapható. Van azonban egy lényeges különbség a két hatványozás között. Legyen n valamilyen számrendszerben r-jegy . Míg a moduláris hatványozás esetén minden lépésben n-nél kisebb, vagyis legfeljebb r-jegy számokat kell szorozni, addig a közönséges hatványozásnál (nem nulla alap esetén) minden lépésben a négyzetreemelésnél megduplázódik a jegyek száma (vagy legfeljebb ennél eggyel kisebb lesz). Mivel a szorzáshoz nagyjából a tényez k jegyei számának szorzatával megegyez számú lépésre (egy-egy számjegy szorzására) van szükség, ezért most minden fordulóban hozzávet leg négyszer több elemi számításra van szükség, mint az el z fordulóban. Ha m jegyeinek száma b, akkor tehát a moduláris hatványozásnál nagyságrendileg tb 2 elemi szorzás (tehát jegyenkénti szorzás) szükséges, míg a közönséges hatványozás esetén az ilyen t −1 t −2 −1 2 l 2 4 lépések száma hozzávet leg 2 ( b ) = b ~ 4 t b 2 , vagyis az el bbi esetben az elvégzend l =0 4 −1 m veletek száma t-nek polinomiális, a második esetben viszont exponenciális függvénye. Másként szólva, míg a moduláris hatványozás polinomiális id ben elvégezhet , addig a közönséges hatványozás nem polinomiális bonyolultságú algoritmus. ∆
m
Ahhoz, hogy az 4.2. definícióban valóban rejtjelezést adtunk meg, meg kell mutatni, hogy az m e A mod n A leképezés injektív M A -n, a fejtés a titkos információ hiányában gyakorlatilag lehe-
tetlen, de d A birtokában könny végrehajtani. Ami a támadót illeti, neki egy x e A ≡ c (n A ) kongruenciát kell megoldania. Jelenleg az egyetlen járható út (általában) az, ha c-nek vesszük a d A -adik hatvá-
nyát, mert amint a következ tételb l kiderül, m = c d A mod n A . Ám ehhez ismerni kellene d A -t, és ehhez általában ϕ (n A ) -t, amit viszont csak akkor tudunk könnyen számítani, ha adott az n A faktorizációja. Az utóbbi problémára – mármint adott szám felbontása prímtényez inek szorzatára – nem ismeretes polinomiális idej algoritmus, s t az t nik valószín nek, hogy ilyet nem is lehet meg-
14
4. RSA adni. Felhívjuk a figyelmet rá, hogy nem állítottuk, hogy a visszafejtés csupán így történhet, ezért nem mondtuk, hogy a fejtés nehézsége azonos a faktorizálás nehézségével; ezt sem nem bizonyították, sem nem cáfolták eddig (nyilvánosan!), továbbá azt sem mondtuk, hogy minden esetben a hatványozás a legkézenfekv bb megoldás, bizonyos szerencsétlen (m, c ) pár esetén egyszer bben is megoldható a feladat (a szerencsétlen jelz a legális partnerek szempontjából értend , a hívatlan támadó számára ez inkább szerencsés véletlen). Amit állíthatunk, az csupán annyi, hogy az RSA fejtése legfeljebb annyira nehéz, mint az összetett egész számok tényez kre bontása, hiszen ha fel tudjuk n A -t bontani, akkor már fejteni is tudunk, de elvileg elképzelhet , hogy van ennél egyszer bb módja is a fejtésnek. Egyébként n A felbontásának vagy ϕ (n A ) -nak az ismerete algoritmikus szempontból egyenérték , mert egyikb l a másik polinomiálisan számítható. Ez a felbontás ismeretében nyilvánvaló, hiszen ekkor ϕ (n A ) = ( p A − 1)(q A − 1) , ami lényegében véve egyetlen szorzás. Ha viszont ismert ϕ (n A ) , akkor p A q A − p A − q A + 1 = ( p A − 1)(q A − 1) = ϕ (n A ) és p A q A = n A , az el bbib l p A + q A = n A − ϕ (n A ) + 1 , vagyis p A és q A az x 2 − (n A − ϕ (n A ) + 1) + n A polinom két gyöke, és a két gyök polinomiális id ben meghatározható. d A ismeretében viszont m könnyen nyerhet , mert a moduláris hatványozásról már megmutattuk, hogy könny feladat, így a legális címzett könnyen hozzájut a nyílt szöveghez. Most
megmutatjuk, hogy tetsz leges m ∈ M A nyílt üzenetre (m e A ) ≡ m (n A ) , ebb l majd az is következik, hogy a rejtjelszabályunk injektív. Az alábbiakban általánosabban vizsgálja a kérdést. dA
4.5.
Jelölés Legyen n ∈ N + , u ∈ N és u < v ∈ N . Ekkor • M u(n ) = m ∈ M (n ) m u mod n = 0 és N u(n ) = M u(n ) ;
•
{ M ( ) = {m ∈ M ( ) (m n v, u
n
}
v
}
− m u ) mod n = 0 és N v(,nu) = M v(,nu) ∆
Láthatóan M u(n ) az x u és M v(,nu) az x v − x u polinom n-nél kisebb nem negatív modulo n gyökeinek halmaza, és N u(n ) valamint N v(,nu) az ilyen gyökök száma.
4.6.
Tétel Legyen n = ∏i =1 piri páratlan egész szám, ahol s ∈ N + , minden s ≥ i ∈ N + indexre ri pozitív s
(p )
egész és a pi prímek páronként különböz ek, és legyen p prím és r ∈ N + . Ekkor N u(n ) = ∏i =1 N u s
r− r r r r s ( p ri ) és N v(,nu) = ∏i =1 N v ,ui , ahol N v(,pu ) = N u( p ) + N v(−pu ,)0 , N u( p ) = p
r u
ri i
, és N w( p, 0 ) = ϕ ( p r ) . r
∆
Bizonyítás: Ha f egész együtthatós polinom, akkor a fenti n-re az f polinom modulo n gyökeinek száma megegyezik az f modulo piri gyökei számának szorzatával, ezért elegend megmutatni, hogy n = p r rel N v(,pu ) éppen a tételben álló kifejezés. r
m v − m u ≡ 0 ( p r ) az m egésszel a kongruencia definíciója szerint akkor és csak akkor, ha a
modulus osztója a két oldal különbségének, azaz p r m v − m u = m v (m v −u − 1) . De tetsz leges m egészre
m u és m v −u − 1 relatív prímek. Ha ugyanis a p prím osztója m u -nak, akkor u > 0 és p osztója m-nek, de akkor osztója m v −u -nak, és így biztosan nem osztója m v −u − 1 -nek. Ekkor viszont p r csak úgy
osztja az m v − m u különbséget, ha osztója m u és m v −u − 1 egyikének és csak egyikének. Ez azt mutat-
15
4. RSA ja, hogy N v(,pu ) = N u( p ) + N v(−pu ,)0 , így elegend a jobb oldalon álló két értéket meghatározni, továbbá csupán a páronként inkongruens megoldások érdekesek, ezért a keresett számot úgy nyerjük, ha külön-külön meghatározzuk azon p r > m ∈ N egészek számát, amelyekre m u illetve m v −u − 1 osztható r
r
r
p r -rel, és a két számot összeadjuk.
Nézzük az el bbi oszthatóságot. u = 0 esetén m u = 1 , és mivel r > 0 , tehát p r > 1 , így nincs
r olyan egész, amelyre m u osztható p r -rel, N 0( p ) = 0 , és a fejezet elején említett konvenció alapján
r−
r
ugyanez az értéke p 0 -nak is. Vizsgáljuk az u > 0 esetet. Ha p r osztója m u -nak, akkor ennek a prímfelbontásában p legalább az r-edik hatványon szerepel, és így m-ben p kitev je nem lehet kisebb
r r -nál, vagyis -nál, mert ez a kitev bizonyos tényez k száma, tehát egész szám. Ugyanez visszau u felé is érvényes: ha m osztható p kor osztható p -rel, ha m = kp r
r u
r u
-val, akkor m u is osztható p r -rel, vagyis m u akkor és csak ak-
alakú alkalmas k egésszel. Minket a páronként inkongruens megol-
dások érdekelnek, tehát például azok, amelyek egyben kielégítik a p r > m ∈ N feltételt, ami ekvivalens a p
r−
r u
> k ∈ N egyenl tlenséggel, és ezen k egészek száma éppen a bal oldalon álló szám; ez-
r zel megkaptuk N u( p ) -t u > 0 -ra is.
Most áttérünk N w( p,0 ) , vagyis az x w − 1 polinom modulo p r gyökei számának meghatározásár
ra, ahol a w = v − u jelölést alkalmaztuk. Ennek nyilván csak olyan m lehet a megoldása, amellyel m w és p r legnagyobb közös osztója egyben osztója 1-nek, vagyis ez a legnagyobb közös osztó 1.
(ab, c ) = 1
pontosan akkor igaz, ha (a, c ) = 1 és (b, c ) = 1 , így (m w , p r ) = 1 ⇔ (m, p r ) = 1 , tehát az
x w − 1 polinom bármely modulo p r gyöke relatív prím a modulushoz.
Ha p páratlan, akkor a p r modulusra létezik primitív gyök, vagyis olyan egész, amelynek a
rendje modulo p r pontosan ϕ ( p r ) . Legyen g primitív gyök a p r modulusra. Ez azt jelenti, hogy g
ϕ ( p r ) > k ∈ N kitev s hatványainak halmaza egyréteg en lefed egy modulo p r redukált maradék-
rendszert, így az el bbi intervallumba es g
kw
= (g
k
)
w
≡1= g
0
( p ) . g primitív gyök a r
olyan k egészeket kell megkeresni, amelyekkel
p modulusra, tehát a rendje a p r modulussal ϕ ( p r ) , r
így a kongruencia megoldásai azok a k egészek, amelyekkel kw ≡ 0 (ϕ ( p r )) , azaz k ≡ 0 és ennek a kongruenciának (w, ϕ ( p r )) páronként inkongruens megoldása van.
4.7.
Kiegészítés
ϕ (pr ) (w,ϕ ( p r )) ,
Tetsz leges p prímszám esetén N w( p, 0 ) = (εw, ϕ ( p r )) , ahol ε = 1 , kivéve, ha w páros és p=2 és r ≥ 3 , amikor ε = 2 . ∆ Bizonyítás: Ha p páratlan, akkor ε = 1 , és visszakapjuk a tételben megadott eredményt. Ha p = 2 és r legfelejebb 2, akkor létezik primitív gyök, és ekkor a bizonyítás megegyezik a páratlan prímek esetével. Maradt a p = 2 , r ≥ 3 eset. Ekkor van olyan g, hogy ennek 2 r − 2 > k ∈ N -kitev s hatványai és r
16
4. RSA ezek ellentettjei kiadnak egy mod 2 r redukált maradékrendszert, és a két csoport idegen. Ha w páratlan, akkor a két csoport elemeinek hatványai az eredeti csoporthoz tartoznak, míg páros w esetén − g k és g k w-edik hatványa azonos lesz, és mivel g 0 = 1 , így elegend
g kw -k között keresni azokat, ame-
( )
lyek mod 2 r kongruensek 1-gyel, és páros w esetén ezek számát megduplázni. g kw ≡ 1 = g 0 2 r akkor és csak akkor, ha kw ≡ 0 (2 2r − 2 w,2 r − 2
ekvivalens a k ≡ 0
(
r −2
), hiszen g rendje
r
mod 2 pontosan 2
(
r −2
. Ez utóbbi kongruencia
)
kongruenciával, és ennek w, 2 r − 2 páronként inkongruens megoldása
)
(
)
van. Ha w páratlan, akkor r ≥ 3 miatt ez a szám 1, ami megegyezik w, 2 r −1 -val, míg ha w páros, ak-
(
kor 2 w, 2
r −2
) = (w, 2 ) . Tekintetbe véve, hogy pozitív egész r esetén ϕ (2 ) = 2 r −1
r
r −1
, a bizonyítás kész.
A tételnek egy sereg következménye van:
4.8.
Következmény
(( )
)
Legyen t = lkkt ϕ p iri s ≥ i ∈ N + (lkkt a legkisebb közös többszöröst jelöli). Ekkor az el z tétel jelöléseivel és feltételeivel r ri − i u
s n , ahol P = ∏ pi ; P i =1 i =1 i =1 = 0 ekvivalens u = 0 -val;
s
1. 0 ≤ N u(n ) = ∏ pi a) N u(n )
s
≤ ∏ p iri −1 =
{
}
b) 1.-ben a jobb oldalon akkor és csak akkor áll egyenl ség, ha u ≥ max ri s ≥ i ∈ N + ; c) 1.-ben a bal oldal értéke pontosan akkor 1, ha u = 1 vagy n négyzetmentes;
2. 1 ≤ N v(,n0) = ∏i =1 (v, ϕ ( p iri )) ≤ ϕ (n ) ; s
a) N v(,n0) = 1 akkor és csak akkor, ha ( v, ϕ (n )) = 1 ;
b) N v(,n0) = ϕ (n ) akkor és csak akkor, ha t v
c) ha v = ϕ (n ) , akkor N v(,n0) = ϕ (n ) (ez az Euler-Fermat tétel más megfogalmazásban); s
ri −
3. u ≥ 1 esetén 2 s ≤ N v(n, u) = ∏ pi
ri u
i =1
(
+ v − u , piri − piri −1
)
≤n;
a) N v(n, u) = 2 s akkor és csak akkor, ha egyrészt u = 1 vagy n négyzetmentes, másrészt
( v − u, ϕ (n )) = 1 ;
{
}
b) N v(n, u) = n akkor és csak akkor, ha u ≥ max ri s ≥ i ∈ N + és t v − u ; c) ha v − u páros, akkor N v(,nu) = 3 s ; 4. N n(n,n)−ϕ (n ) = n ;
( (
))
5. N v(n,1) = ∏i =1 1 + v − 1, piri − piri −1 ; s
a) N v(n,1) = 2 s akkor és csak akkor, ha v − 1 és ϕ (n ) relatív prím; ( )
b) ha v páratlan, akkor N v ,n1 ≥ 3 s ;
17
4. RSA c) N v(n, 1) = n -hez szükséges és elégséges, hogy n négyzetmentes, és t osztója v − 1 -nek; d) ha n négyzetmentes, akkor minden m ∈ Z -re m1+ kϕ (n ) ≡ m (n ) , ahol k ∈ N ;
e) ha minden m ∈ Z -re m n ≡ m (n ) , akkor n négyzetmentes, és vagy s=1, vagy s ≥ 3 ; 6. ha n négyzetmentes, k ∈ N , és e a kt -hez relatív prím természetes szám, akkor tetsz leges, az e-hez relatív prím j ∈ N -re bármely, az ex ≡ 1 ( jt ) kongruenciát kielégít d pozitív
( )
egésszel minden m ∈ Z -re m e
( )
d
kor m e
≡ m (n ) ;
d
≡ m (n ) . Speciálisan, ha (e, ϕ (n )) = 1 és ed ≡ 1 (ϕ (n )) , ak-
7. legyen z ∈ N + , és z ≥ i ∈ N + -ra 1 < u i ∈ N olyan, hogy n = ∏i =1 u i ∈ N négyzetmentes, lez
gyen továbbá t ′ = ∏i =1 (u i − 1) , e a t ′ -höz relatív prím pozitív egész, és d olyan természetes z
szám, amellyel ed ≡ 1
(t ′) . Ekkor
( )
a) minden m ∈ Z -re m e
d
≡m
(n ) akkor és csak akkor teljesül, ha t ed − 1 ;
b) és minden, a t ′ -höz relatív prím e-re ez pontosan akkor igaz, ha t t ′ . ∆
Bizonyítás:
r 1. Nézzük N u( p ) értékét. p prímszám, így p > 1 , tehát p z z-nek szigorúan monoton növekv
r− függvénye. N u( p ) = p
r u
r , ahol u ≥ 0 . Pozitív u esetén ez monoton n , és mivel r u r r ≤ r − 1 . Innen rögtön adódik, hogy N u( n ) mais pozitív, ezért u ≥ r esetén 0 < ≤ 1 , tehát r − u u r
s
ximális értéke
∏p i =1
ri −1 i
, azaz z = r −
, amit akkor érünk el, amikor minden i-re u ≥ ri . A másik oldalon, tehát ami-
r tart a pozitív végtelenhez, így a kitev a negatív végtelenhez, és a hatvány a u r r r nullához. Végül legyen u pozitív, tehát u ≥ 1 . Ekkor ≤ r , vagyis ≤ r , így r − ≥ 0 , és a u u u kor u csökken, akkor
hatvány értéke legalább 1. A hatvány értéke akkor és csak akkor 1, ha a kitev 0, és a kitev ben nullát pontosan akkor kapunk, ha r és v r −1<
r azonos. De bármely x valós számra x − 1 < x ≤ x , így a kiteu
r ≤ r esetén, és csak ekkor lesz 0. Mivel u ≥ 1 , ezért a jobb oldali feltétel biztosan teljeu
r akkor és csak akkor, ha (u − 1)(r − 1) < 1 . Mivel a bal oldalon u mindkét tényez nem negatív egész szám, ezért az egyenl tlenség pontosan akkor igaz, ha valamelyikük nulla, azaz akkor és csak akkor, ha u és r legalább egyike 1. Azt kaptuk tehát, hogy N u( n ) értéke sül, elég a másikat nézni. r − 1 <
akkor és csak akkor 1, ha u = 1 , vagy minden i-re ri = 1 , ami azt jelenti, hogy n négyzetmentes.
( ( ))
2. N v(,p0 ) = v, ϕ p r . Két szám legnagyobb közös osztója akkor és csak akkor 0, ha mindkét r
( ) biztosan nem nulla, ezért
szám nulla, minden más esetben pozitív egész szám. Mivel ϕ p r
( ( ))
N v(,p0 ) r
értéke is legalább 1. Ha v, ϕ p r = 1 , akkor N v(,p0 ) = 1 , és ilyen v, p és r létezik. Ennek minden i-re r
18
4. RSA
( )
teljesülnie kell, tehát a legkisebb értéket akkor és csak akkor kapjuk, amikor v relatív prím a ϕ piri -k mindegyikéhez, vagyis a szorzatukhoz, ami éppen ϕ (n ) .
( )
A másik oldalon egyenl ség pontosan akkor lesz, ha ϕ p r v . N v(n,0) maximumát akkor kapjuk,
( )
ha ez minden i-re teljesül, tehát ha a ϕ piri -k legkisebb közös többszöröse osztja v-t. A speciális eset is igaz, hiszen adott számok legkisebb közös többszöröse osztója a szorzatuk bármely többszörösének. r r r 3. Ha u > 0 , akkor N v(,pu ) = N u( p ) + N v( −pu ,)0 és N v( n,u) =
∏
s
i =1
ri N v(,pui ) . Minden tényez mindkét
tagjának minimuma 1, így az összeg minimuma 2 s , amit pontosan akkor kapunk, ha n négyzetmentes vagy u = 1 , és ugyanakkor v − u relatív prím ϕ (n ) -hez. Ha azonban n páratlan, akkor ϕ piri minden i-re páros, ezért ha v − u is páros, akkor a legnagyobb közös osztó minden tényez ben legalább kett , és maga a tényez minimálisan 3. A maximumot pontosan akkor kapjuk, amikor t osztója v − u -nak, és u ≥ max ri s ≥ i ∈ N + .
( )
{
( ( )) = ϕ ( ) =
Ekkor v, ϕ
piri ri i
piri
piri
−
piri −1
ri −
minden i-re, és pi
ri u
}
= piri −1 , ahonnan a két érték összeadása
után éppen p -t kapunk, amelyek szorzata n. 4. Most v − u = n − (n − ϕ (n )) = ϕ (n ) , és t ϕ (n ) , így t osztója v − u -nak. Bármely s ≥ i ∈ N + index esetén n felírható piri ni alakban, ahol p iri és ni relatív prímek. Ekkor u = n − ϕ (n ) = piri ni − ϕ ( piri )ϕ (ni ) = piri ni − piri −1 ( pi − 1)ϕ (ni ) = piri (ni − ϕ (ni )) + piri −1ϕ (ni ) ≥ piri −1 ≥ ri
{
}
és ebb l kapjuk, hogy u ≥ max ri s ≥ i ∈ N + . 5. Ez a pont az utolsó alpont kivételével lényegében véve 3. speciális és aktualizált esete u = 1 -re, ahol az aktualizálás azt jelenti, hogy az u ≥ ri feltételek következtében most n négyzetmen-
tes. Nézzük e)-et. Amennyiben minden egész m-re m n ≡ m (n ) , akkor N n(n,1) = n , ami akkor és csak akkor teljesül, ha n négyzetmentes és t n − 1 . Legyen n négyzetmentes. Ha s = 1 , akkor ez azt jelenti,
hogy n prím, és ekkor m n ≡ m (n ) éppen a kis Fermat-tétel, vagyis ekkor ez minden egész m-re igaz. Legyen most s = 2 , vagyis n = pq , ahol p és q két különböz páratlan prím, és mondjuk p < q . Ekkor n − 1 = pq − 1 = p (q − 1) + ( p − 1) , és ez biztosan nem osztható q − 1 -gyel, de akkor még kevésbé p − 1 és q − 1 legkisebb közös többszörösével, t-vel. 6. Ha (e, kt ) = 1 , akkor (e, t ) = 1 is igaz, és mivel j is relatív prím e-hez, ezért (e, jt ) = 1 , így
ex ≡ 1
( jt ) megoldható. Ha d megoldás, akkor t
jt d − 1 , tehát 5. alapján igaz az állítás.
Ami a speciális esetet illeti, t nyilván osztója ϕ (n ) -nek, tehát ϕ (n ) = kt , és a felírás alapján
j = k , így 1 = (e, ϕ (n )) = (e, kt ) -b l (e, j ) = (e, k ) = 1 . 7. Az els állítás ed = v -vel 5. alapján igaz. t t ′ esetén ed ≡ 1 (t ′) -b l t d − 1 . Fordítva, tegyük fel, hogy tetsz leges e, d pár jó, és legyen ed = 1 + kt ′ , ahol (k , t ) = 1 . Ekkor viszont t d −1 = kt ′ ⇔ t t ′ , tehát igaz a második állítás is. A páros n-re vonatkozó megállapításokat ismét külön fogalmaztuk meg.
19
4. RSA
4.9.
Kiegészítés Ha n páros is lehet, akkor az el bbi következmény egyes pontjai az alábbi módon változnak. 3.
c) ha v − u páros, akkor ha n páratlan vagy néggyel osztható, akkor az alsó határ legalább 3 s , míg ha n egy páratlan szám kétszerese, akkor N v( ,nu) ≥ 2 ⋅ 3 s −1 ;
5. a)b)
ha v páratlan, akkor ha n páratlan vagy néggyel osztható, akkor N v(n,1) ≥ 3 s , míg ha n
páros, de nem osztható néggyel, akkor N v( n,1) ≥ 2 ⋅ 3 s −1 ; e) ha minden m ∈ Z -re m n ≡ m (n ) , akkor n négyzetmentes, és vagy s=1, vagy n páratlan és s ≥ 3 . ∆
( )
Bizonyítás: 3.c) Ha n páros, akkor n = 2 l n1 alakú egy páratlan n1 -gyel és pozitív egész l-lel, és ekkor
( ) prímhatványokéhoz. Amennyiben viszont l = 1 , akkor ϕ (2 ) = 1 , és (v − u , ϕ (2 )) = 1 .
ϕ 2 l = 2 l −1 . Ha n néggyel osztható, akkor l ≥ 2 , és ϕ 2 l páros, tehát a helyzet hasonló a páratlan l
5.b) Ez az el z pont u = 1 esetén. 5.e) Itt csak annyit kell belátni, hogy ha n nem prímszám, akkor szükségszer en páratlan. Ha s ≥ 2 , akkor n prímosztói között van páratlan, és így a ϕ ( p i ) -k között páros szám, ezért t páros.
Ugyanakkor, ha n páros, akkor n − 1 páratlan, és így nem lehet osztható t-vel, de akkor N n(n,1) < n .
∆
4.10. Megjegyzés Ha n páratlan, négyzetmentes egész szám legalább három különböz prímosztóval, akkor van olyan n, amelyre N n(n,1) = n . n = 561 = 3 ⋅ 11 ⋅ 17 a legkisebb, ekkor t = [3 − 1,11 − 1,17 − 1] = 80 , és 80 osztója 560 = 561 − 1 -nek. Egy összetett n az a poztív egészre nézve álprím, ha a n ≡ a (n ) . Amenynyiben egy adott n bármely egész számra vonatkozóan álprím, akkor n Carmichael-szám. A fenti 5.e) pont alapján n csak úgy lehet Carmichael-szám, ha páratlan, négyzetmentes és legalább három különböz prímosztója van, és az el bbi példa alapján létezik Carmichael-szám. Egy nem túl régi eredmény alapján végtelen sok Carmichael-szám létezik. ∆ A 6. következmény mutatja, hogy d ismeretében a legális fejt valóban könnyen hozzájut a nyílt szöveghez. Azt is látjuk, hogy amennyiben n = pq -ban p vagy q nem prím, és legalább egyikük nem négyzetmentes, akkor biztosan van olyan nyílt üzenet, amelyet rejtjelezve nem a helyes eredményt kapjuk visszafejtéskor. Ha n mindkét tényez je négyzetmentes, de legalább egyikük összetett, továbbá e és d olyan egészek, hogy ed ≡ 1 (( p − 1)(q − 1)) (ahol ( p − 1)(q − 1) a vélt ϕ (n ) ), tehát valamilyen k nem negatív egésszel ed − 1 = k ( p − 1)(q − 1) , úgy akkor és csak akkor nem keletkezik hiba visszafejtéskor, ha ed − 1 osztható a valódi pi , páronként különböz prímosztóból számított [ p i − 1 s ′ ≥ i ∈ N ] legkisebb közös többszörössel, ahol s ′ a faktorok száma (n páratlan, tehát a pi -k is azok). Végül az is kiolvasható a következményekb l, hogy egy n = pq , e paraméterekkel megadott RSA rejtjelnek (1 + (e − 1, p − 1)) (1 + (e − 1, q − 1)) fixpontja van. Mivel a fixpont nem kívánatos (hiszen ekkor nem rejtjeleztünk), ezért az a jó, ha ez a szám minél kisebb. Ennek minimuma 9 (mert n páratlan, tehát e is az kell, hogy legyen), és ezt akkor érjük el, ha (e − 1, t ) = 2 .
20
4. RSA Most megmutatjuk, hogy RSA esetén tetsz leges m nyílt üzenetre (m e ) ≡ m (n ) , ebb l majd az is következik, hogy a rejtjelszabályunk injektív. d
4.11. Tétel Legyen n ∈ N páratlan egész, f az M (n ) halmaz önmagába való olyan leképezése, hogy minden M (n ) -beli m-re f : m m e mod n , ahol e 1-nél nagyobb egész. f akkor és csak akkor injektív (és így bijektív), ha n négyzetmentes, és e relatív prím ϕ (n ) -hez. ∆
Bizonyítás: Ha (e, ϕ (n )) = 1 , akkor van olyan d pozitív egész, hogy ed ≡ 1 (ϕ (n )) , és ha még n négyzetmen-
tes, akkor evvel a d-vel az x ed ≡ x (n ) kongruencia megoldásainak száma az 5.d) következmény alapm ed mod n = (m e ) mod n leképezés az M (n ) önmagába való identikus d
ján n, vagyis ekkor az f : m
leképezése, tehát f bijektív. Mivel f az egyaránt az M (n ) -t M (n ) -be képez
g :m
m e mod n és
h : m m d mod n leképezések kompozíciója, ahol el bb g-t hajtjuk végre, ezért f csak úgy lehet bijektív, ha g injektív, így a tétel feltételei elégségesek. Ha n nem négyzetmentes, akkor e > 1 miatt az 1.c). következmény szerint az x e ≡ 0 (n ) kong-
ruenciának, ha viszont e nem relatív prím ϕ (n ) -hez, akkor az x e ≡ 1 (n ) kongruenciának van a 2.a). következmény alapján egynél több megoldása, így az f leképezés egyik esetben sem injektív.
Bár az RSA szempontjából nem játszik közvetlen szerepet, ám a prímtesztelésnál fontos kérdés az x + 1 polinom modulo n gyökeinek száma. Mivel er s a hasonlóság a már megoldott x v − 1 polinom modulo n gyökeinek problémájával, ezért ezt a kérdést is megvizsgáljuk, majd csupán a teljesség kedvéért az x v + x u polinom modulo n gyökeinek számát is megnézzük. v
4.12. Tétel: Legyen s ∈ N + , n = ∏i =1 p iri , ahol ri pozitív egész, a pi -k páronként különböz páratlan prís
( )
mek, ϕ p iri = 2 ki q i pozitív egész k i -vel és páratlan egész q i -vel, továbbá v = 2 k q pozitív egész a k ∈ N , 2 /| q egészekkel. Ekkor az x v + 1 polinom modulo n gyökeinek száma 2 ks ∏i =1 (q, q i ) , ha s
{
}
k < min ki s ≥ i ∈ N + , egyébként 0. ∆
Bizonyítás: Már láttuk korábban, hogy elegend prímhatványokra meghatározni a megoldásszámot, és ezeket összeszorozni. Azt is láttuk, hogy páratlan prím esetén a prímhatványra van primitív gyök, mondjuk g. − 1 relatív prím p r -hez, ezért egy és csak egyféleképpen írható g valamely d = ϕ p r > i ∈ N -
( )
( )
kitev s hatványaként. g d ≡ 1 p r , és (− 1) = 1 ≡ 1 p r , továbbá d páros, így 2
( ) − 1 ≡ g (p ). d 2
r
aw
csak úgy lehet kongruens − 1 -gyel, ha a relatív prím p r -hez, és ekkor a is felírható g hatványaként, d vagyis a ≡ g y p r . A megoldandó kongruencia ezek után wy ≡ (d ) . Ehhez szükséges és elégsé2
( )
21
4. RSA ges, hogy w és d legnagyobb közös osztója ossza
d -t. A tétel jelöléseivel nyilván igaz, hogy (q, q ′) 2
d -nek, így még annak kell teljesülnie, hogy a legnagyobb közös osztóban fellép 2-hat2 d vánnyal is lehessen osztani -t. Ez pontosan akkor teljesül, ha w-ben a 2 kitev je kisebb, mint d-ben. 2 Ekkor a megoldások száma (w, d ) = 2 k q, 2 k ′ q ′ = 2 k q, 2 k ′− k q ′ = 2 k (q, q ′) , ahol p r = 2 k ′ q ′ a páratlan q ′ -vel, hiszen q páratlan. Visszatérve az eredeti modulusra, pontosan akkor van megoldása a megadott kongruenciának,
osztója
(
{
)
(
)
}
ha k < min ki s ≥ i ∈ N + , és ebben az esetben a megoldások száma 2 ks ∏i =1 (q, q i ) , hiszen 2 k mins
den tényez ben szerepel. Az általános esetr l szól a következ tétel.
4.13. Tétel Legyen p prímszám, r ∈ N + , u ∈ N és u ≤ v ∈ N . Ekkor x v + x u modulo p r gyökeinek száma 1. 2, ha p = 2 és r = 1 ;
r −1 2. 2 N u(2 ) , ha p = 2 és r > 1 ;
r 3. N u( p ) , ha p > 2 ;
( )
míg ha v > u , ϕ p r = 2 k ′ q ′ és v − u = 2 k q , ahol q és q ′ páratlan egészek, akkor r 4. N u(2 ) + 1 , ha p = 2 és r = 1 ;
r 5. N u(2 ) , ha p = 2 , r > 1 és v − u páros;
r 6. N u(2 ) + 1 , ha p = 2 , r > 1 és v − u páratlan; r 7. N u( p ) , ha p > 2 és k ≥ k ′ ;
r 8. N u(2 ) + 2 k (q, q ′) , ha p > 2 és k < k ′ ;
∆
Bizonyítás: Legyen el ször u = v , ekkor x v + x u = 2 x u . Ha p páratlan, akkor p r akkor és csak akkor osztója 2a u -nak, ha osztója a u -nak, így kapjuk 3.-at. Ha p = 2 és r = 1 , akkor az osztó 2, és mivel 2a u mindig páros, ezért az oszthatóság minden a egészre teljesül, és ezek között két inkongruens van modulo 2, ami igazolja 1.-et. Amennyiben viszont p = 2 és r > 1 , 2 r akkor és csak akkor lesz osztója
r −1 2a u -nak, ha 2 r −1 osztja a u -t, ilyen a a 2 r −1 > a ∈ N tartományban N u(2 ) van, és akkor ezek kétsze-
rese is osztható 2 r -rel, és még ezek is kisebbek 2 r -nél, ezért igaz 2. is. Most nézzük a v > u eseteket. Ekkor x v + x u = x u x v −u + 1 , és v − u > 0 következtében min-
(
)
den a egészre a u és a v −u + 1 relatív prím, ezért most is elegend külön meghatározni az x u és az x v −u + 1 polinom modulo p r gyökeinek számát, az eredeti probléma megoldását ezen két szám ösz-
r szege adja. Az els kongruencia megoldásainak számát már ismerjük, ez N u( p ) , ezért csak az x w + 1
22
4. RSA alakú kifejezéssel kell foglalkoznunk, ahol w = v − u > 0 . Páratlan prím esetére a kérdést az el z tételben megoldottuk, és éppen a 7.-ben és 8.-ban megfogalmazott eredményt kaptuk. Most legyen p = 2 . Ha r = 1 , akkor olyan a-t keresünk, amelyre a w + 1 osztható 2-vel, és 2 > a ∈ N 0 . Ilyen a pontosan egy van, nevezetesen a = 1 , és ezzel kész a 4. pont. Hátra van az r > 1 eset. Ha r = 2 , akkor az el z höz hasonlóan az a w ≡ −1 (4 ) feltételnek megfelel , 4-nél kisebb, nem negatív egész a-kat keressük. Ehhez megint az kell, hogy a legyen relatív prím 4-hez. Ilyen a kett van, a = 1 és a = 3 ≡ −1 (4) . Innen látszik, hogy ha w páros, akkor nincs megoldás, míg ha w páratlan,
( )
akkor pontosan egy megoldás lesz, tehát most teljesül 5. és 6. Végül legyen r ≥ 3 . a w ≡ −1 2 r -hez
szükséges, hogy a ≡ −1 (4) is teljesüljön, így rögtön kapjuk, hogy páros w esetén most sincs megolw
dás. Amennyiben w páratlan, akkor (− a ) = − a w , így vizsgálhatjuk, hogy mikor osztható b w − 1 2 r rel. Ez csak páratlan b-vel lehet, így nem fordulhat el , hogy b = −b , ezért a b-k száma azonos lesz az w
( ( )) (
)
eredeti kongruencia megoldásainak számával. Ez N w(2,0) , és ennek az értéke w, ϕ 2 r = w, 2 r −1 = 1 , mert w páratlan és r > 2 , amivel r > 2 -re is igazoltuk 5.-öt és 6.-ot. r
Most olyan fejtési módszert vizsgálunk, amelyhez nem kell ismerni a d titkos paramétert, és megnézzük, hogyan lehet ez ellen a támadás ellen védekezni. Az eljárás csak nyilvános adatokat alkalmaz, és ismételt hatványozással állítja el a nyílt üzenetet. Szükségünk lesz az alábbi tételre.
4.14. Tétel:
Ha u és v pozitív egész, és u v , akkor ϕ (u ) ϕ (v ) . ∆
Bizonyítás:
Legyen s ∈ N + , s ≥ i ∈ N + -ra ri ∈ N + és u = ∏i =1 p iri továbbá j ∈ N + és i < j ≤ s -re pi ≠ p j s
prímek. Mivel u v , ezért v = v1v 2 = v 2 ∏i =1 p iti úgy, hogy (u , v 2 ) = (v1 , v 2 ) = 1 , és valamennyi t i az s
ri -nél nem kisebb egész. Most s
(
)
ϕ (v ) = ϕ (v1 )ϕ (v 2 ) = ϕ (v 2 )∏ p iti −1 ( p i − 1) = i =1
s
= ϕ (v 2 )∏ i =1
(
p iri −1
( pi − 1))∏ s
i =1
p iti − ri
s
= ϕ (u )ϕ (v 2 )∏ i =1
, p iti − ri
így valóban igaz, hogy ϕ (u ) ϕ (v ) . Nézzük meg, hogy adott 1 < n ∈ N , 1 < e ∈ N , c ∈ M (n ) esetén mikor lesz olyan k ∈ N + , amelylyel c e
k −1
mod n = m , ha m ∈ M (n ) -re c = m e mod n . Rögtön látjuk, hogy ha ezek a feltételek teljesül-
(
nek, akkor c = m e mod n = c e pontosan akkor igaz, ha
k −1
mod n
)
e
k n c e −1 − 1 . (c, n )
k
k
(
mod n = c e mod n , azaz n c e − c = c c e
k
−1
)
− 1 , ami viszont
n = o n+ (c ) , és az el bbi oszthatóság másként írva (c, n )
c l ≡ 1 (o n+ (c )) , ahol l = e k − 1 . A kongruenciának akkor és csak akkor van megoldása, ha
23
4. RSA 1 = (c, o n+ (c )) = c,
n
(c, n )
, ami viszont akkor és csak akkor teljesül, ha a c bármely p prímosztója c-ben
legalább akkora hatványon fordul el , mint n-ben. Ez biztosan így van, ha n négyzetmentes. Ekkor
c l ≡ 1 (o n+ (c )) -hez szükséges és elégséges, hogy oo+ (c ) (c ) l = e k − 1 , vagy ismét átírva kongruenciába,
ha
(
)
n
e k ≡ 1 oo + (c ) (c ) . Ilyen k pontosan akkor van, ha e relatív prím n
oo+ (c ) (c ) -hez. De n
oo+ (c ) (c ) ϕ (on+ (c )) = ϕ
n ϕ (n ) , így, ha (e, ϕ (n )) = 1 , akkor van ilyen k, és a legkisebb ilyen k pozi(c, n )
tív egész éppen oo +
(c )
n
on ( c )
elemére a kc = oo +
on ( c )
(c )
(e) . Ha tehát n négyzetmentes és e relatív prím ϕ (n ) -hez, akkor
(e )
pozitív egész számmal c e
kc −1
M (n ) egy c
mod n = m , és ha k a kc -k legkisebb közös
többszöröse, akkor valamennyi c ∈ M (n ) -re c e mod n = m , és k a legkisebb ilyen tulajdonságú pozitív egész szám. ou (v ) osztója ϕ (u ) - nak, ou+ (v ) pedig u-nak, így felhasználva az el z eredményeket k −1
oo +
on ( c )
(c )
(e) ϕ (oo (c ) (c )) ϕ (ϕ (on+ (c ))) ϕ (ϕ (n )) + n
minden c-re, így kc k ϕ (ϕ (n )) , tehát, ha azt akarjuk, hogy kc a lehet legtöbb c-re nagy legyen, akkor
n-et úgy kell választani, hogy ϕ (ϕ (n )) -nek kevés kis osztója legyen, és a kis osztókkal csak kevés c-t lehessen fejteni. Természetesen mindig lesz olyan c, amely kis kitev vel fejthet , hiszen az RSA-nak vannak fixpontjai, és ezek már k = 1 -gyel fejthet ek, Az lenne a jó, ha a fixpontok száma minél kisebb lenne, és minden más rejtjelezett szövegb l csak nagy k ′ kitev vel lehetne visszanyerni az eredeti üzenetet. Az el bb megfogalmazott gondolatokat pontosítjuk a következ kben.
4.15. Tétel Legyen 1 < e ∈ N , 1 < n ∈ N , és m ∈ M (n ) -re c = m e mod n . Akkor és csak akkor létezik olyan k ∈ N + , hogy minden m ∈ M ( n ) -re c e
k −1
mod n = m , ha az f : m
m e mod n leképezés in-
jektív az M (n ) halmazon, és ekkor o = ot (e ) a legkisebb ilyen k kitev .
∆
Bizonyítás:
Legyen most is n = ∏i =1 p iri , ahol s ∈ N + , a pi -k páronként különböz prímszámok és az ri -k s
pozitív egészek. Egy c ∈ M (n ) -re c e mod n = c pontosan akkor teljesül, ha c ∈ M e(nk ),1 , és az ilyen c-k k
( (
( ))) . Minden lehetséges c-re akkor és csak akkor teljesül az adott
száma N e(nk ,)1 = ∏i =1 1 + e k − 1, ϕ p iri s
e-vel és k-val, hogy c e mod n = c , ha N e(nk ),1 = n , ami viszont ekvivalens azzal, hogy n négyzetmenk
tes és minden i-re pi − 1 e k − 1 . Az utóbbi feltétel akkor és csak akkor teljesíthet , ha e relatív prím valamennyi ϕ ( p i ) = p i − 1 -hez, azaz ϕ (n ) -hez. Ha viszont ez a két feltétel teljesül, akkor az a
leképezés injektív M (n ) -en, és
24
ae
4. RSA
(c vagyis m = c e
k −1
e k −1
mod n
)
e
k
mod n = c e mod n = c = m e mod n
mod n .
Minden i-re pi − 1 e k − 1 akkor és csak akkor igaz, ha a ϕ ( p i ) = p i − 1 -ek legkisebb közös többszöröse, t is osztója e k − 1 -nek, vagyis e k ≡ 1 (t ) , és a legkisebb ilyen k kitev éppen o = ot (e ) .
gyen.
Nézzük meg, hogyan kell n-et választani, hogy a lehet legtöbb c-re az iterációs fejtés nehéz leLegyen u ∈ N , u < v ∈ N , u1 ∈ N , u2 ∈ N , u1 < v1 ∈ N és u2 < v2 ∈ N . Ha u1 ≤ u 2 és m ∈ M u(1n ) ,
akkor n m u1 m u 2 , azaz m ∈ M u( n2 ) , tehát M u(n1 ) ⊆ M u(n2 ) , és ekkor N u(n1 ) ≤ N u(n2 ) . Ha u1 ≤ u 2 mellett
v1 − u1 v 2 − u 2 , és m ∈ M v(1n,)u1 akkor n m v1 − m u1 = m u1 (m v1−u1 − 1) m u2 (m v2 −u2 − 1) = m v2 − m u2 , vagyis m ∈ M v(2n,)u2 , és így M v(1n,)u1 ⊆ M v( 2n ,)u 2 , valamint N v(1n,)u1 ≤ N v(n2 ,)u 2 . Ha most M v(1n,)u1 ⊆ M v( 2n ,)u 2 mellett még N v(1n,)u1 = N v(n2 ,)u 2 , akkor azt kapjuk, hogy M v(1n,)u1 = M v(n2 ,)u 2 , vagyis ilyen esetben a kitev k növelésével
nem kapunk újabb modulo n gyököket az x v − x u alakú polinomokhoz. A fentiekben említett iterációs fejtési lehet ség akkor alkalmazható a gyakorlatban, ha vagy maga o = ot (e ) értéke kicsi, vagy az üzenetek nagy része kis kitev vel fejthet . Egy biztonságos rendszerben tehát o értéke olyan nagy, hogy gyakorlatilag lehetetlen az ilyen iterációs fejtés, és az o-nál kisebb kitev kkel fejthet üzenetek aránya kicsi. A legalább 3 s fixpont már k = 1 -gyel fejthet . Ha o pi −1 (e ) < o , ami normális esetben minden i-re igaz, akkor természetesen legalább 3 s −1 p i számú üzenet már o p i −1 (e ) kitev vel fejthet , így az elvárásunk csak az lehet, hogy a fixpontokon kívül ennél
kisebb kitev vel ne lehessen fejteni. Nagy o akkor érhet el, ha minden i-re o p i −1 (e ) a lehet legnagyobb, és o p i −1 (e ), o p j −1 (e ) min-
(
)
den i ≠ j -re a lehet legkisebb.
o pi −1 (e ) ϕ ( pi − 1) , így o p i −1 (e ) lehetséges legnagyobb értéke ϕ ( pi − 1) , és ilyen e akkor és csak
akkor létezik, ha pi − 1 értéke 2, 4 vagy 2 p i(1) (mert p i − 1 páros), ahol pi(1) páratlan prímszám és ri
ri ∈ N + , vagyis RSA esetén pontosan akkor, ha p i − 1 = 2 p i(1) , hiszen a kis prím faktorok könnyen ri
(
)
meghatározhatóak. Legyen tehát p i − 1 = 2 p i(1) , ekkor ϕ ( p i − 1) = p i(1) p i(1) − 1 , és legyen e egy modulo p i − 1 primitív gyök, vagyis (e, p i − 1) = 1 és o pi −1 (e ) = ϕ ( p i − 1) . Ha (e, p i − 1) = 1 , akkor ri −1
ri
(1) l
egyben e, p i
= 1 is igaz minden ri > l ∈ N kitev vel. Ekkor e
(1) ri −1
2 pi
e
ϕ 2 pi(1 )
ri −1
− 1, 2 p i(1)
ϕ 2 pi(1 )
ri
továbbá e
ϕ 2 pi(1 )
ri −1
− 1, 2 p i(1)
25
ri
< 2 p i(1)
ri
ri −1
≡ 1 2 p i(1)
ri −1
, tehát
4. RSA mert o pi −1 (e ) = ϕ 2 p i(1)
ri
, és végül
e
ϕ 2 pi(1 )
ri −1
− 1, 2 p i(1)
ri
2 p i(1)
ri
A három összefüggés alapján e
ϕ 2 pi(1 )
ri −1
− 1, 2 p i(1)
ri
= 2 p i(1)
ri −1
és így ri > 1 esetén nem teljesül, hogy csak a fixpontok fejthet ek o p i −1 (e ) -nél kisebb kitev vel. Le-
gyen ezért minden s ≥ i ∈ N + -ra ri = 1 , vagyis az n minden prímfaktorára legyen p i = 2 pi(1) + 1 , ahol pi(1) páratlan prímszám. Ekkor tetsz leges k pozitív egész számmal
(e
k
)
2
− 1, p i − 1 =
pi − 1
e − 1 e k − 1 , ezért M e(,p1i ) ⊆ M e(kp,i1) , és ha N e( kp,i1) = 2 , akkor M e(,p1i ) = M e( kp,i1) , vagyis a pi -k ilyen választásával csupán a fixpontoknak megfelel üzenetek fejthet ek kis kitev vel. e rendje modulo p i − 1 akkor és csak akkor oi , ha e ≡ 1 ( p i − 1) és e oi
( )= p
minden p prímosztójára, és oi ϕ ( p i − 1) = ϕ p i
(1)
(1)
i
oi p
≡/ 1 ( p i − 1) az oi
− 1 . A modulo p i − 1 primitív gyökök száma
p i(1) − 1 p (1) − 1 , hiszen pi(1) − 1 páros szám, és ϕ ( pi(1) − 1) < i , ha pi(1) − 1 nem 22 2 hatvány. Ha pi(1) − 1 = 2l , akkor pi(1) Fermat-prím, és ez az eset nagyon valószín tlen (talán lehetetlen).
(
) (
)
ϕ p i(1) − 1 . ϕ p i(1) − 1 ≤
p (1) − 1 pi(1) − 1 p (1) − 1 − 1 , és ϕ pi(1) − 1 = i − 1 akkor és csak akkor, ha i = pi(2 ) prímszám, 2 2 2 más szavakkal, ha pi(1) = 2 pi(2 ) + 1 egy pi(2 ) prímszámmal. Ekkor egyrészt a primitív gyökök aránya
Ekkor ϕ ( pi(1) − 1) ≤
(
)
p i(1) − 1 −1 ϕ ( p i − 1) p i − 1 p (1) − 3 2 = = = i pi pi pi 2 pi (1)
(2 )
pi − 1 −3 p −7 1 2 = = i ≈ 2 pi 4 pi 4 tehát könny a primitív gyök keresése, másrészt egy tetsz leges k pozitív egész szám esetén könny (2 )
az ellen rzés, ugyanis o pi −1 (k ) = ϕ ( p i − 1) , ha p i − 1 /| k 2 − 1 és p i − 1 /| k pi − 1 .
[
] [
]
Végül az el bbi választással o = oi s ≥ i ∈ N + = 2 p i(2 ) s ≥ i ∈ N + = 2∏i =1 p i(2 ) , és felhasználva s
(2 ) o 2∏i =1 p i s 1 o az el bbi eredményt = ≈ 2∏i =1 = 2 −(2 s −1) , vagyis annál nagyobb, minél kisebb az s s n 4 n p s
∏i=1
i
értéke. Mivel RSA-nál n mindenképpen összetett szám, ezért a legjobb választás s = 2 , ami egyébként
26
4. RSA a fixpontok szempontjából is a legjobb. Most i = 1, 2 -re N ( 2np) ( 2 ) = 3 p i , és ez akkor lesz mindkét eseti
e
,1
ben viszonylag nagy, ha p1 ≈ p 2 , azaz n mindkét faktora körülbelül
((
n nagyságrend .
)
) vagy ((c mod n )− c, n ) = p , és ekkor k
Az iteratív fejtésnek létezik a következ módosítása. Ha c e mod n − c, n > 1 valamilyen pozi-
((
k
)
k
)
k
e tív egész k-val, de c e mod n ≠ c , akkor c e mod n − c, n = p1 2 ismert n felbontása, tehát meghatározható d, a rendszert sikerült feltörni. Ám a faktorok fentiekben n ismertetett választásával a legkisebb ilyen k kitev 2 p1(2 ) ≈ , feltéve, hogy p1 < p 2 . 2
A p pímszám Sophie Germain-prím, ha p = 2 p ′ + 1 alakú a p ′ prímmel. Láttuk, hogy RSAhoz a kétszeresen Sophie Germain prímek a jók (vagyis ahol az el bbi p ′ is Sophie Germain-prím). Kérdés, hogy létezik-e ilyen prím. A válasz igenl : például 2 ⋅ 2 + 1 = 5 és 2 ⋅ 5 + 1 = 11 , 2 ⋅ 5 + 1 = 11 és 2 ⋅ 11 + 1 = 23 , 2 ⋅ 11 + 1 = 23 és 2 ⋅ 23 + 1 = 47 , 2 ⋅ 41 + 1 = 83 és 2 ⋅ 83 + 1 = 167 stb. Az n = pq választásánál az eddigieken túl egy további szempont, hogy q − p sem lehet kicsi, ugyanis (q + p ) − (q − p ) = 4 pq = 4n , innen (q + p ) = 4n + (q − p ) , vagyis egy kis pozitív egész négyzetét 4n -hez adva ismét négyzetszámot kapunk, amit könnyen lehet ellen rizni. Ha tehát u v+u v−u és v olyan egészek, hogy 4n + u 2 = v 2 , akkor a = ,b= és n = ab , de n egyetlen felbon2 2 tása pq , tehát a = p és b = q , n-et könny faktorizálni, és így már könny ϕ (n ) -et és az 2
2
2
2
ex ≡ 1 (ϕ (n )) megoldását megtalálni. Ez mutatja, hogy p és q választásánál a q − p ≈ p (≈ q ) felté-
telnek is teljesülnie kell, ha azt akarjuk, hogy ne lehessen könnyen megfejteni a rejtjelünket. Ha p = 2 p ′ + 1 és q = 2q ′ + 1 , ahol p ′ és q ′ páratlan prímszám, akkor ( p − 1, q − 1) = 2 , ami ( p − 1)(q − 1) < pq = n , ahol δ = ( p − 1, q − 1) , és ha δ nagy, azért is fontos, mert t = [ p − 1, q − 1] =
δ
δ
δ
akkor t kicsi, és kevés próbálkozással található olyan d, amellyel c d mod n = m . Most azt vizsgáljuk, hogy mi a kapcsolat a rejtjel biztonsága és a rejtjelb l nyerhet részleges információ között. Megmutatjuk, hogy ha meg tudjuk állapítani a rejtjeles szövegb l a nyílt szöveg utolsó bitjét, akkor már az egész szöveget könnyen fejthetjük. El ször egy segéderedményt látunk be.
4.16. Tétel
Legyen 2 /| n ∈ N négyzetmentes, e a ϕ (n ) -hez relatív prím pozitív egész, f : x
x e mod n az
M (n ) halmaz önmagába való leképezése, K ∈ Z olyan, hogy 2 e K ≡ 1 (n ) , u ∈ M , v = f (m ) és
(
)
z = u mod 2 . Ekkor u′ = 2 −1 (− 1) u mod n ∈ M és v′ = K (− 1) v mod n = f (u′) . z
z
∆
Bizonyítás: Els ként megjegyezzük, hogy létezik a tételben igényelt K, hiszen n páratlan. z Ha u páros, akkor z = 0 és (− 1) u = u , ennek a fele is nem negatív egész és nem nagyobb u-
nál, tehát kisebb n-nél; páratlan u esetén z = 1 , − n < (− 1) u = −u < 0 , és így (− 1) u mod n = n − u , ez ismét páros, tehát osztható kett vel, és u ′ ismét n-nél kisebb nem negatív egész (most azért írhatz
27
z
4. RSA tunk − u < 0 -t, mert u páratlan, ezért nem lehet 0). e páratlan, hiszen n páratlan, egynél nagyobb páratlan számra ϕ (n ) páros, és páros számhoz relatív prím szám feltétlenül páratlan, ezért − 1 z-edik és
ez -edik hatványa azonos. Ezt felhasználva 2u′ = (− 1)z u mod n ≡ (− 1)z u (n ) -b l e ez u′e ≡ (2e K )u′e = K (2u ′) ≡ K (− 1) u e ≡
≡ K (− 1) v ≡ K (− 1) v mod n = v′ (n ) z
z
és így v ′ az u ′ képe az f leképezésnél, v ′ = f (u ′) , ahogy a tételben állítottuk, és ezzel a bizonyítást befejeztük. Ezt az eredményt felhasználjuk a következ tétel bizonyításában.
4.17. Tétel
[
[
Legyen r ∈ N + , 2 /| n ∈ 2 r −1 , 2 r négyzetmentes és e a ϕ (n ) -hez relatív prím egész, f az M (n ) -
en értemezett f : x x mod n leképezés, K ∈ Z olyan, hogy 2 e K ≡ 1 (n ) , m ∈ M (n ) , és c = f (m ) . Ha v = f (u ) -ra g (v ) = z = u mod 2 , úgy az alábbi algoritmus c-b l el állítja m-et: e
z0 = g ( y0 )
y0 = c
yi+1 = K (− 1) yi mod n
z i +1 = g ( y i +1 )
zi
r −1 > i ∈ N0 : majd
t r −1 = z r −1
(
)
t i = (− 1) i (2t i +1 ) mod n mod 2 r −i
r −1> i∈N:
z
∆
Bizonyítás: Azt már tudjuk, hogy K létezik. Az el z tételb l következik, hogy a megadott indexek mindegyikére van olyan xi , hogy y i = f ( x i ) , és így a megfelel z i is létezik. Azt fogjuk belátni, hogy minden r − 1 > i ∈ N 0 egészre ti = xi mod 2 r −i , ebb l már következik az állítás, hiszen n < 2 r következtében mind x 0 , mind t 0 n-nél kisebb nem negatív egész a definíciók alapján, és így m = x 0 = t 0 .
z i az xi paritását mutatja, így z i éppen xi jobb széls bitje az xi kettes számrendszerbeli felírásánál, és ha i = r − 1 , akkor tehát x r −1 mod 2 = zr −1 = tr −1 . Tegyük fel, hogy r − 1 ≥ j ∈ N + és
j > i ∈ N esetén j-re fennáll az egyenl ség, tehát speciálisan j = i + 1 -re is. Ekkor ti+1 ≡ xi +1 (2 r −i −1 ) ,
(
)
és így 2ti +1 ≡ 2 xi +1 (2 r −i ) , továbbá az el z tétel alapján y i +1 az xi +1 = 2 −1 (− 1) i xi mod n üzenethez tartozó rejtjel. Innen z
ti ≡ (− 1) i (2 ti+1 ) mod n = zi n + (− 1) i (2ti +1 ) ≡ z
z
(
)
≡ zi n + (− 1) i (2 xi +1 ) = zi n + (− 1) i zi n + (− 1) i xi = xi (2 r −i ) z
z
z
mert zi n + (− 1) i xi = (− 1) i xi mod n , (− 1) i (− 1) i = 1 és zi n + (− 1) i zi n = 0 , tekintettel arra, hogy z i csupán nulla vagy egy lehet. z
z
z
z
z
28
4. RSA
4.18. Megjegyzés Az el z tétel alapján belátható, hogy amennyiben azt tudjuk y-ból megállapítani, hogy x kisebb-e, mint n fele, vagy nagyobb, akkor hasonlóan egyszer már a fejtés (harmadik lehet ség, azaz egyenl ség most kizárt, mert n páratlan egész és x egész). Legyen ugyanis adott n > y ∈ N -re 2x , ahol n > x ∈ N és y = f (x ) = x e mod n . Mivel x korlátai alapján 0 ≤ 2 x < 2n , ezért n 2x n n 0≤ < 2 , így ζ 0, ha x < , és 1, amennyiben x > . Alkalmazva az a − 1 < a ≤ a relációt n 2 2 2x a= -re kapjuk, hogy 0 ≤ 2 x − ζn < n , vagyis 2 x mod n = 2 x − ζn . De n a tétel feltétele alapján pán ratlan, így n ≡ 1 (2) , és evvel 2 x mod n = 2 x − ζn ≡ ζn ≡ ζ (2 ) , másként írva (2 x mod n ) mod 2 = ζ . Most megmutatjuk, hogy z és ζ bármelyikét ismerve, a másikat könny meghatározni. Ha e y′ = 2e y mod n , akkor (2 x ) = 2 e x e ≡ 2 e y (n ) , így x′ = 2 x mod n olyan, hogy y ′ = f (x ′) , tehát ha g-re van algoritmus, akkor g ( y′) = x′ mod 2 = (2 x mod n ) mod 2 = ζ . Fordítva, legyen y ∗ = ky mod n . h( y ) = ζ =
( )
Mivel f bijektív, ezért van olyan n > x ∗ ∈ N 0 , amellyel y ∗ = f (x∗ ) = (x ∗ ) mod n . Legyen ζ = h y ∗ meghatározható. Ekkor e
(2 x
∗
− ζn ) ≡ (2 x∗ ) = 2e (x ∗ ) ≡ 2e y ∗ ≡ 2 e Ky ≡ y ≡ x e (n ) , e
e
e
ami f injektivitása és 0 ≤ x < n , 0 ≤ 2 x ∗ − ζn < n miatt csak úgy lehet, ha x = 2 x ∗ − ζn , ami egyúttal
azt is jelenti, hogy x ≡ ζ (2) és g ( y ) = ζ . y-ból 2e y mod n illetve Ky mod n számítása könny feladat, és így g és h bonyolultsága megegyezik. Még megemlítjük, hogy ha n bináris felírásában az utolsó s bit mindegyike 1, akkor amennyiben y-ból x alsó s bitjének bármelyikét meg tudjuk határozni, akkor ebb l már könny a fejtés. Ennek bizonyítása valamivel hosszabb, mint az el bbi két eset, ezért eltekintünk t le. ∆ Most három kérdésre térünk ki: mi történik, ha (m, n ) > 1 (m a nyílt szöveg és n a modulus), ha n több kulcsra azonos, illetve ha több résztvev re megegyezik az e kitev (de a modulusok különböz ek). Az els kérdés könnyen elintézhet . Ha n = pq és m ≠ 0 , akkor 1 < (m, n ) csak p vagy q lehet. Ha a közös osztó p, akkor (c, n ) = p is igaz, és ebb l a támadó meg tudja határozni q-t, ϕ (n ) -et és d-t, vagyis feltöri a rendszert. Ennek valószín sége azonban csekély, hiszen az n-hez nem relatív prím, nnél kisebb nem negatív egészek száma n − ϕ (n ) = pq − ( p − 1)(q − 1) = p + q − 1 , és ezek aránya az np + q −1 1 1 2 nél kisebb nem negatív egészekhez , viszont n nagy. ≈ + ≈ pq p q n Térjünk rá a második esetre. Legyen k résztvev esetén azonos az n modulus, és közülük az iedik nyilvános kulcsa ei . Ha közülük akár csak kett , mondjuk az 1. és 2. index , azonos nyílt szöveg rejtjeles változatát kapja (pédául egy körlevelet), és e1 , e2 relatív prím, akkor egy támadó is vissza tudja fejteni c1 -b l és c 2 -b l az eredeti m üzenetet. Most ugyanis c1 ≡ m e1 (n ) és c2 ≡ m e2 (n ) . Mivel e1 és e2 relatív prím, ezért van olyan u1 és u 2 egész, hogy 1 = u1e1 + u 2 e2 . e1 és e2 egyaránt 1-nél nagyobb pozitív egész, ezért az el bbi egyenl ség csak úgy állhat fenn, ha u1 és u 2 egyike pozitív, a másik negatív. Szimmetriaokokból bármelyiküket tekinthetjük negatívnak, legyen például u1 < 0 és u 2 > 0 . Ekkor
29
4. RSA m = m1 = m u1e1+u2e2 = (m e1 ) (m e2 ) ≡ c1u1 c2u2 (n ) , u1
u2
( −u )
innen (c1 ) 1 m ≡ c2u2 (n ) ( − u1 már pozitív), vagyis m a (c1 ) 1 x ≡ c 2u 2 (n ) kongruencia megoldása, és megoldás biztosan létezik, például az eredeti m üzenet, vagyis a rejtjeles szövegekb l ismert kitev s hatványokkal egy egyismeretlenes lineáris kongruencia megoldásaként, tehát polinomiális id ben megkapjuk a nyílt szöveget (egy ilyen kongruencia például euklideszi algoritmussal megoldható, és ez polinomiális algoritmus). Most tegyük fel, hogy k számú résztvev nek azonos e rejtjelkitev je van, és az i-edikhez az ni modulus tartozik, továbbá a modulusok páronként relatív prímek (ennél enyhébb feltétel is elegend lenne). Ha egy körlevél következtében mindegyikük azonos rejtjeles szöveget kap, akkor a közös m könnyen meghatározható egy kívülálló részér l is. Legyen ci az i-edik rejtjeles szöveg, akkor tehát (− u )
ci ≡ m e (ni ) valamennyi i-re, azaz m e a megoldása a ci ≡ x (ni ) szimultán kongruenciarendszernek. De ennek egy és csak egy megoldása van modulo n, ahol n az ni -k szorzata, így egy és csak egy olyan megoldás van, ahol n > x ∈ N 0 . Nyilván érvényesnek kell lennie az ni > m ∈ N 0 feltételnek minden i-
re, így ha k ≥ e , akkor n > m e ∈ N 0 , és ezért most m e = x , ahonnan m gyökvonással megkapható. Az, hogy több felhasználó nyilvános rejtjelkitev je azonos, nem rendkívüli. e nagysága nem befolyásolja különösebben a rejtjel biztonságát, ezért a számítás egyszer sége érdekében célszer kicsire választani. Ha a rendszerben sok szerepl vesz részt, akkor el fordul, hogy bár egymástól függetlenül választják a paramétereket, de a kevés számú kis érték közül többen is azonosat választanak. Még nézzük meg a paraméterek választását. Véletlen prímet például véletlenszám generátorral nyerhetünk: generálunk egy számot, prímteszttel megvizsgáljuk, és ha nem prím (illetve nem min sítjük prímnek), akkor vehetjük a természetes számsorban következ páratlan egészt. Tegyük fel, hogy m nagyságrend prímet keresünk. Csebisev tétele szerint bármely szám és a kétszerese között van prím, és a nagy prímszámtétel szerint az x számnál nem kisebb prímek száma, π ( x ) , nagy x-ekre körülbelül x x , π (x ) ~ . Ekkor az m és 2m közötti prímek várható aránya lnx lnx 2m m − π (2m ) − π (m ) ln(2m ) ln(m ) 2 1 1 ~ = − ≈ , m m ln 2 + ln (m ) ln(m ) ln (m ) vagyis várhatóan ln (m ) kísérlet után prímet kapunk, s t, ha figyelembe vesszük, hogy a prímek páratlanok (kivéve a 2-t), és csak minden második szám páratlan (és persze csak ezekkel kísérletezünk), ln (m ) akkor átlagosan kísérlettel prímhez jutunk. Konkrétan m ~ 10100 esetén ez körülbelül 115 pró2 bálkozást jelent (megjegyezzük, hogy az el bbi kétszeres tartománynál lényegesen kisebb intervallumra is igaz, hogy van benne prím, ha x elegend en nagy, másrészr l láttuk, hogy nem akármilyen prím alkalmas). e-nek relatív prímnek kell lennie ϕ (n ) -hez. Ez például úgy biztosítható, ha q < e < n és e prím, ahol q az n-ben lév nagyobbik prím. Ez az e valóban relatív prím ϕ (n ) -hez, hiszen ez utóbbi minden prímosztója kisebb e-nél. ∆
30
5. A Rabin-variáns Az alább ismertetend rejtjelez algoritmus lényegében véve az RSA módosítása, ám ennél az eljárásnál bizonyítani tudjuk, hogy a bonyolultsága azonos az egész számok faktorizációjának bonyolultságával. Legyen n egy páratlan nem negatív egész szám és b tetsz leges egész szám, legyen továbbá minden m ∈ M (n ) -re c = m(m + b ) mod n . Mivel n páratlan, ezért (2, n ) = 1 , és így van olyan u egész
(
)
szám, amellyel 2u ≡ b (n ) . Ekkor m(m + b ) mod n = (m + u ) − u 2 mod n , tehát c-b l meghatározni m-et ekvivalens azzal, hogy meghatározunk egy olyan m ′ -t, amellyel m ′ 2 ≡ c + u 2 (n ) . Tekintettel 2
arra, hogy egy rögzített b esetén u, és vele együtt u 2 konstans, ezért az egész eljárás lényegében véve azonos az m c = m 2 mod n leképezéssel. Ennek megfelel en a továbbiakban ezt az utóbbi eljárást vizsgáljuk. Látható, hogy az m m 2 mod n leképezés M (n ) -en hasonló egy olyan RSA-hoz, ahol e = 2 . Ugyanakkor tudjuk, hogy RSA-nál az egyértelm fejtés csak akkor valósítható meg, ha (e, ϕ (n )) = 1 , ami csak akkor lehet igaz, ha e páratlan, hiszen n > 2 esetén ϕ (n ) páros. Egyébként ennél a leképe-
zésnél nyilvánvaló, hogy nem injektív, hiszen ha m ∈ M (n ) , akkor m és n − m = − m mod n négyzete, tehát képe azonos. Majd látjuk, hogy a helyzet ennél még bonyolultabb, vagyis ha egy c-nek van modulo n négyzetgyöke, akkor összetett és páratlan modulus esetén kett nél több ilyen gyöke van c-
nek. Azt mindenesetre tegyük fel, hogy n négyzetmentes, vagyis n = ∏i =1 p i , ahol s 1-nél nagyobb s
pozitív egész szám, és a p i -k páronként különböz páratlan prímszámok.
Legyen c ∈ M (n ) . c-nek akkor és csak akkor van modulo n négyzetgyöke, ha minden i-re van modulo p i négyzetgyöke. Ekkor minden i-re két négyzetgyöke van, kivéve, ha valamelyik p i -vel osztható, és ha mindegyik i-re két négyzetgyök van, akkor ezekb l a kínai maradéktétellel tudunk meghatározni összesen 2 s olyan u-t, amelynek a modulo n négyzete éppen c. Prímmodulus esetén könny feladat a moduláris gyökvonás, és különösen könny , ha p mod 4 = 3 , vagyis akkor, ha p = 4k + 3 alakú. Ekkor c
p +1 4
2
=c
p +1 2
=c
p −1 2
⋅ c , és c
ha van c-nek modulo p négyzetgyöke, akkor c
p +1 4
p −1 2
mod p =
+1 −1
, tehát c
2
= c , ellenkez esetben c
p +1 4
p +1 4
2
=
+c , vagyis −c
2
= −c . Amennyi-
ben tehát c = m 2 mod n , akkor c-nek van modulo p i négyzetgyöke, és ha p i mod 4 = 3 , akkor pi +1
c 4 mod p i = mi (ha p 4k + 1 -alakú prímszám, akkor is van polinomiális algoritmus, amellyel meghatározható egy szám modulo p négyzetgyöke, feltéve, hogy van neki, de az el bbi hatványozásnál n bonyolultabb ekkor az eljárás). Ha most u i olyan, hogy u i ≡ 1 ( p i ) (mivel n négyzetmentes, ezért pi ilyen u i mindig van), akkor a kínai maradéktétel szerint m ′ =
s i =1
±
n u i mi mod n mindegyike, és pi
csak ezek, olyan, n-nél kisebb nem negatív egész számok, amelyeknek a modulo n négyzete éppen c (az összegben az egyes tagok el jele egymástól független, és az összes lehetséges kombinációban el fordul, így kapjuk a legfeljebb 2 s különböz gyököt).
5. A Rabin-variáns s = 2 esetén legyen n = pq , m 2p ≡ c ( p ) , m q2 ≡ c (q ) , v p = qu p ≡ 1 ( p ) és v q = pu q ≡ 1 (q ) .
Ekkor m ′ = (± v p m p ± v q m q ) mod n adja a legfeljebb négy megoldást (két megoldás van, ha c osztható
n egyik és csak egyik prímtényez jével, és egy megoldás van, ha c = 0 ), és a négy megoldás közül n kett (a két megoldás közül az egyik) kisebb, mint . 2 Hogyan lehet kiválasztani a több megoldás közül az eredeti üzenetet? Ha kikötjük, hogy az üzenet legyen kisebb, mint n fele, akkor már csak két változat közül kell választani. Akár négy, akár két megoldás valamelyike az eredeti üzenet, egyszer a választás, ha valamilyen szöveges üzenet megfejtésér l van szó, mert ekkor elég nagy valószín séggel a több lehetséges változat közül csupán az egyik felel meg értelmes üzenetnek. Amennyiben viszont más jelleg az eredeti üzenet, akkor már nehezebb a több, látszólag értelmetlen szövegb l kiválasztani a tényleges megfejetést. Ilyenkor (is) segít, ha az üzenet egy el re meghatározott részén (például fejlécben) valamilyen el re rögzített formának vagy tartalomnak megfelel információ van. Az el bbiek szerint könny fejteni a Rabin-variánssal rejtjelezett szöveget, ha valaki ismeri n prímtényez it. Ugyanakkor a moduláris négyzetgyökvonás és az egész számok faktorizációja algoritmikusan azonos nehézség probléma, vagyis ha az egyik nem oldható meg polinomiális id ben, akkor a másik sem, tehát az n felbontásának ismerete nélkül a Rabin-variáns gyakorlatilag fejthetetlen. Tegyük ugyanis fel, hogy képesek vagyunk polinomiális id ben négyzetgyököt vonni egy összetett modulusra vonatkozóan, vagyis tetsz leges v esetén, feltéve, hogy v kvadratikus maradék modulo n, azaz van v-nek modulo n négyzetgyöke, az n prímfaktorainak ismerete nélkül polinomiális id ben meg tudjuk határozni v valamely négyzetgyökét. Válasszunk ekkor egy n-nél kisebb nem negatív u véletlen számot, és legyen v = u 2 mod n , majd határozzuk meg az algoritmusunkkal v egy négyzetgyökét. Ha az eredmény u1 , akkor u12 mod n = v = u 2 mod n , vagyis n u 2 − u12 = (u − u1 )(u + u1 ) . Ha n u − u1
vagy n u + u1 , akkor u = u1 vagy u = n − u1 , és semmi új információnk nincs. Ha ellenben az el bb
említett két oszthatóság egyike sem igaz, de a szorzat osztható n-nel, akkor (n, u − u1 ) = n1 , ahol n1 az n egy nem triviális osztója, és ekkor faktorizáltuk n-et. Ha n = pq a páratlan és különböz p és q prímszámokkal, és u relatív prím n-hez, aminek a valószín sége, mint láttuk, csaknem 1 (ha pedig nem relatív prímek, akkor azonnal megkapjuk n felbontását), akkor v-nek négy négyzetgyöke van, és 1 annak a valószín sége, hogy az algoritmus éppen az általunk választott véletlen számot vagy annak 2 ellentettjét számolja ki n négyzetgyökeként. Várhatóan tehát egy-két kísérlet után u1 a másik két négyzetgyök egyike lesz, és végeredményben polinomiális id ben faktorizáltuk n-et (nyilván hasonló a helyzet, ha n kett nél több különböz prímszám szorzata). Mivel jelen ismereteink szerint a faktorizálásra nincs polinomiális futási idej algoritmus, összetett modulus esetén a tényez k ismerete nélkül a c ≡ x 2 (n ) kongruencia gyökeinek meghatározása algoritmikusan nehéz feladat, így a Rabin-variáns alkalmas rejtjelezésre. A konkrét megvalósítás során általában n mindkét prímfaktora 4k + 3 alakú. Az ilyen számokat −1 −1 Blum-egésznek hívják. Ekkor = −1 = , és ha a c négy lehetséges négyzetgyöke közül p q mondjuk m ′ = v p m p + v q m mod n olyan, hogy
− v p m p + vq m n
= −1 =
v p m p − vq m n
m′ = 1 , akkor n
− m′ = 1 , és a másik két gyökre n
, ahol a páratlan u és v egész számra
32
u v
a Jacobi-szimbólum.
6. Diszkrét logaritmus Legyen G egy n-edrend ciklikus csoport a g generátorelemmel. Ekkor a G bármely u eleméhez van egy, a g és u által egyértelm en meghatározott, n > k ∈ N egész szám, amellyel g k = u , és ennek megfelel en az az u k szabály, amely u-hoz az el bbi k-t rendeli, G-nek M (n ) -be való bijektív leképezése ( M (n ) a korábban már más összefüggésben definiált halmaz, amely az n-nél kisebb nem negatív egész számokat tartalmazza.) Az el bbi leképezést ind g u -val vagy log g u -val jelöljük, és g-
alapú diszkrét logaritmusnak vagy g-alapú indexnek nevezzük. Könny ellen rizni, hogy • ind g (uv ) = (ind g u + ind g v ) mod n ; • ind g u = 1 ⇔ u = e ; • u≠e
ind g u −1 = n − ind g u ;
• ind g u r = (r ⋅ ind g u ) mod n .
ahol e a csoport egységeleme, és r tetsz leges egész szám.
k ismeretében, adott g esetén, u meghatározása könny feladat, ám az inverz m velet a mai ismereteink szerint algoritmikusan nehéz feladat, ezért alkalmazhatjuk a rejtjelezésben. A diszkrét logaritmus meghatározására több algoritmus is létezik, ezekb l most kett t ismertetünk. n
1. Legyen g az n-elem G ciklikus csoport generátoreleme, s n , és c = g s , ekkor c egy sedrend elem. Ha α s = e , akkor alkalmas s > m ∈ N kitev vel α = c m . Most α ismeretében meg akarjuk határozni az m kitev t, feltéve, hogy m ≠ 0 , hiszen ellenkez esetben α = e , és innen azonnal látjuk a megoldást. A feladatot megoldhatjuk például úgy, hogy d 0 = e -b l kiindulva addig képezzük
s > i ∈ N + -ra a d i = d i −1c elemet, amíg valamilyen s > k ∈ N + -ra d k meg nem egyezik α-val. Ekkor d k = c k , és mivel c rendje s, ezért ez csak k = m -mel lehetséges. Egy másik megoldás, hogy el re kiszámítjuk s > j ∈ N -re a d j = c j hatványokat, és eltároljuk ket. Amikor α diszkrét logaritmusát kell meghatározni, akkor már nincs más dolgunk, mint egymás után összehasonlítani α-t a d j elemekkel, és ha k-ra találunk egyezést, akkor az el z megfontolás alapján ismét azt kapjuk, hogy k és m azonos. Mindkét esetben feltesszük természetesen, hogy nem egyetlen logaritmus meghatározása a cél, így az els megoldásnál gyakorlatilag nincs memóriaigény, de sokat kell számolni, míg a második esetben csak egyszer kell számolni, utána már csupán összehasonlítások vannak, viszont nagy s esetén nagy tárolókapacitásra van szükség. A két igény egymás rovására módosítható. Legyen t 1-nél nem nagyobb nem negatív valós szám, és u = s t . Az el bbi m egyértelm en írható m = au + b alakban, ahol b u-nál kisebb nem nem−b m s s s gatív egész; ekkor a = ≤ < = t ≤ t = s 1−t ≤ s 1−t . Számítsuk ki és tároljuk c u > k ∈ N u u u s s kitev s hatványait. m meghatározása ekvivalens a és b megadásával. Legyen r = c −u , ekkor az
( )
α = c m = c au + b = c −u
−a
c b egyenl ségb l
α ⋅ r a = c b . Az eljárás tehát a következ . Induljunk ki
α 0 = α -ból, és nézzük meg, hogy teljesül-e valamilyen t-vel az α 0 = c t egyenl ség. Ha igen, akkor a = 0 és b = t -vel c au +b = α , és készen vagyunk. Ha nem, akkor legyen α 1 = α 0 ⋅ r , és ismételjük meg a keresést. Ha sikerrel jártunk, akkor a = 1 és b = t -vel megtaláltuk a megoldást, ha nem, akkor
6. Diszkrét logaritmus legyen α 2 = α 1 ⋅ r stb. Ez az eljárás véges sok lépésben pozitív eredménnyel befejez dik, hiszen i = a -val a keresés α i -re sikeres lesz. 2. Tegyük fel, hogy n = ∏i =1 piri , ahol a pi -k páronként különböz prímek, és s valamint az s
ri -k pozitív egészek. Ha meg tudjuk határozni az m (i ) = α mod piri egészeket, akkor ebb l a kínai maradéktétellel egyértelm en megkapjuk α-t is. m (i ) szintén egyértelm en írható m (i ) =
ri −1 j =0
m (ji ) p ij
alakban, ahol az m (ji ) együtthatók mindegyike pi -nél kisebb nem negatív egész, így a feladat az, hogy minden i-re és j-re meghatározzuk m (ji ) értékét. Mivel a feladat minden i-re azonos, ezért a továbbiakban az i indexet elhagyjuk. Most ismét ki kell számolni és elraktározni a d j = g ahol p > j ∈ N . Mivel g
n p
n p
j
hatványokat,
primitív p-edik gyök, ezért a p > t ∈ N -kitev s hatványok egyértelm en
határozzák meg az el bbi határok közé es kitev ket. α = m + t ⋅ p r egy alkalmas nem negatív t egésszel (amely persze általában nem kisebb a megfelel prímnél), és így r > k ∈ N -ra
α=
k −1 j =0
m j p j + m k p k + p k +1
Tegyük fel, hogy már ismerjük m 0 ,
ck p k +1 = (g g n
α
−u k
)
n p k +1
(r −1)− (k +1) j =0
m (k +1)+ j + tp r −(k +1) = u k + m k p k + v k p k +1 .
, m k −1 , vagyis u k értékét, így a c k = cg −u k jelöléssel
(
= g
)
n mk p k + vk p k +1 p k +1
= g
n p
mk
(g )
n vk
= g
n p
mk
= d mk ,
vagyis c 0 = c -b l indulva egymás után meg tudjuk határozni a d mk és ezáltal az m k értékeket, és ebb l a soron következ c k +1 -et. A második eljárásban természetesen alkalmazhatjuk az els eljárást a keresési m veleteknél.
34
7. Integritás, személyazonosítás, hitelesítés Az aktív támadással szembeni védekezés során a következ kr l van szó
• a küldött üzenet integritásának ellen rzése; • a rendszerhez való hozzáférés jogosultságának ellen rzése; • a küldött üzenet hitelességének ellen rzése. Az üzenet integritása annak sértetlenségét jelenti. Azt jelenti, amit úgy szoktak mondani, hogy „semmit el nem vettem bel le, és semmit hozzá nem tettem”. Erre a célra úgynevezett ujjlenyomatot használnak, amelyet egy hasítófüggvény, másként egy hash-függvény állít el . Az ilyen függvények tetsz leges hosszúságú karaktersorozatból egy fix hosszúságú karaktersorozatot állítanak el . Két fajtája van:
• az MDC (Modification Detection Code); • a MAC (Message Authentication Code). Az el bbi csupán az eredeti üzeneten végrehajtott módosítást jelzi, míg a második titkos kulcsú rendszerekben m ködik, és egyben hitelesítést is végez, amelyet úgy biztosít, hogy ehhez az eljáráshoz a feladó kulcsára van szükség. Az MDC egy m üzenethez egy h(m ) értéket, míg a MAC egy hk (m ) értéket számít ki, ahol h a hasítófüggvény, és k a kulcs. MDC esetén h(m ) -et valamilyen módon védeni kell a támadótól, hiszen h normális körülmények között nyilvános. Ha az eredeti adat tárolása során felmerül változások ellen rzésére használjuk a kivonatot, akkor elegend , ha ezt a kivonatot az eredeti adattól elkülönítve, biztonságos helyen tároljuk. Adatátvitel esetén az egyik lehet ség, hogy miközben m-et egy nyilvános csatornán küldjük, h(m ) egy biztonságos csatornán kerül átvitelre. Ha viszont h(m ) -et m-mel együtt egy nyilvános csatornán küldjük, akkor gondoskodni kell arról, hogy h(m ) -et ne lehessen az üzenet manipulálásával együtt, annak megfelel en változtatni. Az egyik lehet ség, hogy h(m ) -et titkosítjuk a szimmetrikus kulcsunkkal, vagy aláírjuk a nyilvános kulcsú rendszerben, és ezt a titkosított vagy aláírt kivonatot mellékeljük m-hez (ez egyben már hitelesítés is), vagy m h(m ) -et titkosítjuk, ahol a kett s vonal a konkatenációt, az egymás mellé írást jelöli, vagyis a kivonatot egyszer en az üzenet végéhez illesztjük, és az így toldalékolt szöveget sifrírozzuk. A MAC esetén elegend a kivonatot összef zni az eredeti üzenettel. Ismert MDC-algoritmusok az MD4, MD5 (Message Digest algorithm; az MD4 egyértelm en nem biztonságos, és a másikban is találtak ütközést, ezért nem javasolják a használatát), továbbá az SHA-1 (Secure Hash Algorithm) és a RIPEMD-160 (RACE [Research and Development in Advanced Communications Technology in Europe] Integrity Primitives Evaluation Message Digest algorithm). MAC-et például bármely blokkos rejtjellel el lehet állítani CBC-üzemmódban, mint az utolsó blokk. Az MDC-nél használt hash-függvényt l elvárt tulajdonságok:
• legyen srezisztens, vagy másként egyirányú, ami azt jelenti, hogy tetsz leges x üzenethez könnyen lehessen kiszámítani a megfelel h( x ) kivonatot, de szinte minden olyan y-ra, amely egy lehetséges ujjlenyomat, nehéz, tehát gyakorlatilag kivitelezhetetlen legyen olyan x-et találni, amelyre y = h( x ) ; • legyen második srezisztens, gyengén ütközésrezisztens, vagyis adott x-hez legyen gyakorlatilag lehetetlen olyan, az x-t l különböz x ′ -t találni, amellyel h(x ′) = h( x ) ; • legyen (er sen) ütközésmentes, azaz legyen gyakorlatilag lehetetlen olyan x, x ′ ≠ x párt találni, hogy h(x ′) = h( x ) .
7. Integritás, személyazonosítás, hitelesítés A harmadik tulajdonságból következik a második. Ha ugyanis a függvény nem második srezisztens, akkor van olyan x, hogy h( x ) -hez könnyen lehet egy x ′ ≠ x -t találni, amelyre h(x ′) = h( x ) . Ekkor erre az x-re és x ′ ≠ x -re h(x ′) = h( x ) , vagyis találtunk olyan két különböz bemenetet, amelyekhez azonos függvényérték tartozik, és így a függvény nem ütközésmentes. A MAC-nél alkalmazott kivonatoló-függvénnyel szembeni elvárás, hogy legyen kiszámításrezisztens, azaz adott (xi , hk (xi )) -k mellett számítástechikailag ne lehessen egy, az xi -kt l különböz x-szel hk ( x ) -et kiszámítani a kulcs ismerete nélkül. A következ kérdés az identifikáció. Az információs biztonság megköveteli, hogy adott tevékenységet csak arra feljogosított személy végezhessen, vagyis a tevékenység megkezdése el tt igazolja a személyazonosságát. Ennek különböz megoldási módszerei vannak, amelyek három f csoportba sorolhatóak:
• az illet birtokol valamit; • az illet tud valamit; • az illet inherensen rendelkezik valamivel. Az els re példa egy kulcs, a harmadikra példa az ujjlenyomat. Most a másodikkal foglalkozunk. Az identifikációs protokollal szembeni elvárások a következ ek:
• ha A és B becsületes, A sikeresen tudja magát igazolni B-vel szemben; • B ne legyen képes A egy korábbi azonosítási eljárását felhasználva A-ként azonosítani magát C-vel szemben; • elhanyagolható legyen annak a valószín sége, hogy egy A-tól különböz C magát A-ként igazolja B-vel szemben; • az el bbiek akkor is teljesüljenek, ha C (polinomiálisan) sok korábbi, A és B közötti identifikációt figyelt meg, vagy korábban akár A-val, akár B-vel résztvett a protokollban, illetve, ha szimultán több folyamat résztvev je lehet C. Itt a leggyakoribb a jelszavas identifikáció. Ennél er sebb módszer a kihívás – válasz (challenge and response), amelyet például katonai repül gépeken használnak a barát – ellenség felismerésére (IFF - Identification Friend or Foe). Egy lehetséges változata szimmetrikus kulcsú rendszerben, hogy B küld A-nak egy véletlen számot, és A ezt visszaküldi a közös kulccsal rejtjelezve. Most a leger sebb módszerrel, a ZKP-vel (Zero Knowledge Protocol) foglalkozunk röviden. A ZKP lényege, hogy az ellen rz személy csupán egyetlen bitnyi információ birtokába jut az azonosítás végén, nevezetesen, hogy A az-e, akinek mondja magát. A megoldást az alábbi ábra segítségével lehet megérteni.
B
J
F
36
7. Integritás, személyazonosítás, hitelesítés Az ábrán B, J és F ajtók, míg fölül a vastag vonal egy falat reprezentál. A azt állítja, hogy keresztül tud menni ezen a falon, és err l meg akarja gy zni B-t, de úgy, hogy nem akarja megmutatni neki a trükköt. Az eljárás a következ . A az F ajtón keresztül belép az épületbe, majd becsukja az ajtót, és vagy B-n, vagy J-n megy tovább, becsukva maga mögött ezt az ajtót is. Ezek után B belép F-en keresztül az el térbe, és szól A-nak, hogy jöjjön ki mondjuk a J ajtón keresztül. Ha A valóban keresztül tud menni a falon, akkor bármelyik oldalon is ment be az épület belsejébe, ki tud jönni J-n keresztül. Persze akkor is ki tud itt jönni, ha nem igaz, amit állított, de éppen ezen az ajtón ment be, vagyis ebben az esetben is van 50%-nyi sansza a sikerre. Ha azonban pechére a másik oldalon ment be, akkor lebukik. Ez azt jelenti, hogy elég nagy esélye van arra, hogy nem bukik le (pontosan akkora, mint annak, hogy lebukik). Meggy z ez az eredmény? Ha elbukott, akkor igen, ám, ha sikerrel vette az akadályt, akkor nem túlságosan. Igen ám, de ha mondjuk tíz egymás utáni kísérlet mindegyikében a jó oldalon jelenik meg, akkor már csak 1 az 1000-hez (pontosabban az 1024-hez) az esélye, hogy mindegyik alkalommal jól teljesít, és ha még ez sem elég, akkor ennél is több próbát kérhet B. Ha összesen n fordulót játszanak le, akkor 2 − n annak a valószín sége, hogy egy csalónak mindig szerencséje van, vagyis, hogy mindig el re megérzi, honnan kell majd kijönnie. Egy szemernyi kétség mindig maradhat B-ben, ha nagyon nem akar hinni A-nak, de azért a józan ész mégiscsak hajlik arra, hogy elegend en sok kísérlet után elhiggye, A valóban keresztül tud menni a falon. Könny ellen rizni, hogy teljesülnek-e az identifikációval kapcsolatban megfogalmazott elvárások. Egy ilyen identifikációs algoritmus a Fiat-Shamir protokoll. Itt van mondjuk egy közös n = pq modulus, ahol p és q különböz páratlan prímszám, minden résztvev nek van egy titkos i azonosítója, és nyilvános s = i 2 mod n . A úgy akarja igazolni magát B felé, hogy nem árulja el i-t. Ezt, mint a fenti példában, több fordulóban hajtja végre (annyiban, amennyit B óhajt – de azért az ésszer ség határain belül). A minden fordulóban elküld B-nek egy u számot, amely, ha A becsületes, akkor egy általa ebben a fordulóban választott, és titokban tartott r véletlen szám négyzetének a maradéka, vagyis u = r 2 mod n . Ekkor B visszaküld A-nak egy általa tetszés szerint választott b bitet, mire A-nak az a feladata, hogy elküldje B-nek ri b mod n -et. Tegyük fel, hogy A egy v-t küldött most. B-kiszámítja
v 2 mod n -et, és ezt az értéket egybeveti us bA mod n -nel. Ha A tényleg az, akinek mondja magát, akkor ismeri i A -t, és becsületesen játszik, vagyis ekkor v 2 mod n = (riAb mod n ) mod n = r 2 (i A2 ) mod n = b
2
= (r 2 mod n )(i A2 mod n ) mod n = us bA mod n b
Amennyiben viszont A nem A, csak annak mondja magát, akkor csak 50%-nyi esélye van minden fordulóban, hogy átmegy a teszten. Ha arra tippel, hogy B b = 0 -t mond, akkor az els körben szabályosan elküldi a választott véletlen szám négyzetének maradékát, és ha B valóban a 0-ás bitet küldi, akkor vissza tudja küldeni r-et. Ha viszont B 1-est küld, akkor bajban lesz a hamis A, hiszen nem ismeri i A -t, és jelenlegi tudásunk szerint összetett modulus esetén, a faktorok ismerete nélkül gyakorlatilag lehetetlen a négyzet maradékából az eredeti számot meghatározni, vagyis bukik. Ha viszont 1-re számít, r2 akkor ravaszul u-ként nem r 2 mod n -et, hanem v = mod n -et küldi B-nek ( s A relatív prím n-hez, sA mert ha nem az, akkor n-nel való legnagyobb közös osztója vagy p vagy q, és ezzel bárki ki tudja számolni bárkinek a titkos azonosítóját a megfelel nyilvános adatból, ugyanis prímszám modulus esetén a moduláris gyökvonás könny feladat). Ha b valóban 1, akkor a második körben r-et küldi vissza, és B az ellen rzésnél egyez séget talál. Ám, ha a b most a számítása ellenére 0, akkor bajban lesz az álA, mert most olyan t számot kellene küldenie, amellyel t 2 mod n = v , vagyis egy moduláris gyökvonást kellene végrehajtania egy összetett modulusra nézve, amelynek nem ismeri a felbontását.
37
7. Integritás, személyazonosítás, hitelesítés Az identifikáció csak egy adott pillanatban, egy rövid ideig azonosít egy személyt, míg az integritás biztosítása önmagában egyáltalán nem biztosítja az adott dokumentum hitelességét. Ezt a feladatot az aláírás oldja meg. Az aláírással szembeni elvárásaink az alábbiak:
• • • • •
legyen hiteles; legyen hamisíthatatlan; ne lehessen újra felhasználni; ne lehessen az aláírt dokumentumot megváltoztatni; ne lehessen az aláírást letagadni.
A digitális aláírás lényegesen különbözik a hagyományos aláírástól. Az utóbbi független a dokumentum tartalmától, és éppen azt várják el az aláírótól, hogy különböz id pontban más és más dokumentumon elhelyezett kézjegye nagyjából legyen azonos. Ezzel szemben az elektronikus aláírás tartalomfügg , vagyis az aláírás különböz dokumentumokon szinte biztosan más lesz, és ez jelent sen megnehezíti a hamisító dolgát. A másik oldalon viszont a kézírásos aláírás a hordozóhoz rögzített, míg a kriptográfiai aláírás bármikor áthelyezhet egy adathordozóról egy másikra, ezért nagyon lényeges, hogy tényleg er sen függjön az aláírás az aláírt dokumentum tartalmától. A klasszikus rejtjelezés esetén a titkosítás egyben aláírás is, hiszen csak a feladó ismerhette a rejtjelez kulcsot (feltéve, hogy minden kulcsot csak egy küld és egy fogadó ismer). A nyilvános kulcsú rendszer esetén viszont a titkosítás semmilyen kapcsolatot nem biztosít a kulcs gazdájával, hiszen az nyilvános, bárki által hozzáférhet , ezért itt a titkosítás nem jelent egyben hitelesítést is. A digitális aláírásnak két nagy csoportja van:
• toldalékos; • üzenet-visszanyeréses. Az el bbinél nem a teljes üzenetet írjuk alá, hanem annak csak a kivonatát, ami gyorsítja az eljárást. Ekkor az üzenettel együtt elküldjük az aláírt kivonatot is, és a címzett a megkapott üzenet kivonatát egybevetheti a kapott, aláírt kivonattal. A második módszer esetén a teljes üzenetet írjuk alá. Ekkor azonban megfelel óvintézkedést kell tennünk. Tegyük fel, hogy az aláírásra a jól ismert RSA-t használjuk, „fordított” üzemmódban. Ekkor az m üzenet A által aláírt példánya m′ = m d A mod n A , amit valóban csak a legális küld tud kiszámítani, és amib l a címzett könnyen ellen rizni tudja, hogy tényleg A küldte-e, és id közben nem módosult-e az üzenet. Ehhez A nyilvános kulcsát kell használnia, hiszen m′eA mod n A = m , de ha a számítást nem A titkos kulcsával végezték, vagy módosították az aláírt üzenetet, akkor már (szinte biztosan) nem fog teljesülni az egyenl ség. Igen ám, de az a baj, hogy most B nem tudja, mi volt m, így nem tudja ellen rizni, hogy nem történt-e változás. A megoldás, hogy az aláírás el tt redundanciát viszünk az üzenetbe, olyan redundanciát, amelyet az aláírt, vagy hamisan aláírt üzenettel nem lehet (vagy csak nagyon vak tyúk alapon lehet) elérni. Tipikusan ilyen redundancia, hogy az üzenetet „dadogósan”, kétszer egymás mellé másolva írjuk le, és ezt írjuk alá, erre alkalmazzuk a titkos kitev nket. Az elektronikus aláírásról szóló törvény a digitális aláírás biztonsága szempontjából három fokozatot különböztet meg:
• elektronikus aláírás; • fokozott biztonságú elektronikus aláírás; • min sített elektronikus aláírás. A törvény megfogalmazása szerint
38
7. Integritás, személyazonosítás, hitelesítés • Elektronikus aláírás: elektronikus dokumentumhoz azonosítás céljából logikailag hozzárendelt és azzal elválaszthatatlanul összekapcsolt elektronikus adat, illet leg dokumentum. • Fokozott biztonságú elektronikus aláírás: elektronikus aláírás, amely megfelel a következ követelményeknek: a. alkalmas az aláíró azonosítására, és egyedülállóan hozzá köthet , b. olyan eszközzel hozták létre, amely kizárólag az aláíró befolyása alatt áll, c. a dokumentum tartalmához olyan módon kapcsolódik, hogy minden – az aláírás elhelyezését követ en az iraton, illetve dokumentumon tett – módosítás érzékelhet .
• Min sített elektronikus aláírás: olyan – fokozott biztonságú – elektronikus aláírás, amely biztonságos aláírás-létrehozó eszközzel készült, és amelynek hitelesítése céljából min sített tanúsítványt bocsátottak ki. A törvényhez kiadott irányelvek szerint a min sített aláíráshoz alkalmazott aláíráshoz az RSA-t és a DSS-t (Digital Signature Standard, a DSA mint szabvány neve) ajánlott alkalmazni, ez utóbbinak az elliptikus görbés változatát is. Az RSA üzenet-visszanyeréses, bár az ilyen típus mindig használható a másik üzemmódban is, míg a második algoritmus toldalékos, hiszen fix hosszúságon dolgozik. Az üzenet-visszanyeréses technikánál, ha szükséges, az aláírt üzenetet titkosíthatjuk a címzett nyilvános kulcsával, míg a másik módszer esetén ilyenkor az üzenethez láncolt aláírással együtt titkosítjuk az
(
)
üzenetet. Az RSA esetén tehát ekkor EeB Dd A (m ) = (m d A mod n A ) mod nB -t küldi A a másik félnek, eB
B-nek. Ha a két modulus különböz , márpedig majdnem mindig ez a helyzet, akkor n B < n A esetén problémás a titkosítás, amint azt könny végiggondolni. Ezzel most nem foglalkozunk, hanem egy más kérdést vizsgálunk egészen röviden. Els ránézésre úgy t nhet, hogy az el bbi transzformáció
(
)
helyett Dd A EeB (m ) = (m eB mod nB ) mod n A -t is küldhetné A, B ugyanúgy helyre tudná állítani az dA
eredeti üzenetet. Ekkor azonban egy aktív támadó A nyilvános kulcsával kiszámolhatná E eB (m ) -et, és
utána a saját kulcsával aláírva a levelet továbbítaná azt B-nek. Ha a titkosított szöveg nem utal A-ra, akkor B azt hiszi, hogy C volt a feladó, és például válaszolva neki, C fontos információk birtokába juthat, vagyis lényeges a két transzformáció sorrendje.
39
8. Titokmegosztás Egy önállóan megoldandó kérdéssel kezdjük: ha adott egy kincseskamra, amelyhez n embernek van kulcsa, de akkor és csak akkor lehet kinyitni az ajtaját, ha legalább k ember jelen van, akkor hány zárat kell elhelyezni a bejáraton, és egy-egy embernél hány zár kulcsa kell, hogy legyen? A mi szempontunkból a probléma úgy merül fel, hogy ha adott egy T titkos információ, hogyan oldható meg, hogy adott n emberb l bármely legalább k meg tudja határozni T-t, de tetsz legesen kiválasztott k-nál kevesebb erre ne legyen képes. Az ilyen rendszereket szokás (n, k ) -küszöbrendszernek is nevezni. A felvetett kérdésnek számos megoldása létezik, itt most közülük kett t ismertetünk. 1. Legyen p, valamint n ≥ i ∈ N + -ra mi pozitív egész szám úgy, hogy az mi -k páronként relatív
(k ) prímek, továbbá a k legkisebb mi szorzata, M min , legyen nagyobb, mint a k − 1 legnagyobb mi szor-
( k −1) (k −1) (k ) (k ) zatának, M max -nek a p-szerese, vagyis legyen pM max < M min , végül legyen T < M min . Ha a résztvev ket az n ≥ i ∈ N egészekkel azonosítjuk, akkor az i-edik résztvev kulcsa az (mi , Ti ) pár, ahol Ti = T mod mi . a mod b definíciója alapján látjuk, hogy Ti ≡ T (mi ) , így T egy szimultán lineáris kongruenciarendszer megoldása. Jelölje J az n-nél nem nagyobb pozitív egészek halmazának tetsz leges részhalmazát, azaz legyen J ⊆ {i ∈ N + i ≤ n }. Ha a J által meghatározott személyek akarják
meghatározni T-t, akkor megoldják az i ∈ J : x ≡ Ti (mi ) kongruenciarendszert. Ennek egy és csak
egy megoldása van az M ( J ) := ∏i∈J mi -nél kisebb nem negatív egészek halmazán, és ha ez T0( J ) , akkor a Tr( J ) = T0( J ) + rM ( J ) egészek és csak ezek a megoldásai az el bbi rendszernek, ahol r végigfut az
egész számok halmazán, az pedig nyilván igaz, hogy T is megoldás, így valamely r egészre T = Tr( J ) . Két eset lehetséges.
(k ) , és mind T, mind T0( J ) az M ( J ) -nél kisebb nem negatív a) J ≥ k . Ekkor M ( J ) ≥ M min
megoldás, így szükségszer en megegyeznek, vagyis T = T0( J ) , tehát a kongruencia megoldásával rendelkezésre áll a keresett titkos információ. (k −1) (k ) b) J < k . Ebben az esetben T0( J ) < M ( J ) ≤ M max < M min , és így Tr( J ) minden olyan r nem (k ) negatív egésszel, amellyel T0( J ) + rM ( J ) < M min , lehetséges megoldás. A lehetséges T értékek száma
(k −1) (k −1) (k −1) (k ) legalább p, hiszen ha 0 ≤ r < p , akkor T0( J ) + rM ( J ) < M max + ( p − 1)M max = pM max < M min . Ha p nagy, akkor T potenciális értékeinek száma nagy, és ezek közül semmilyen módszerrel nem tudjuk meghatározni a tényleges értéket, s t, bármelyikük azonos eséllyel lehet a valódi megoldás.
Az a feltétel, hogy az mi -k páronként relatív prímek, nem lényeges kikötés. Az általános eset-
(k ) ben M ( J ) = [mi i ∈ J ] , ahol a szögletes zárójel a legkisebb közös többszöröst jelöli, ekkor M min az
összes lehetséges módon kiválasztott k különböz indexhez tartozó mi legkisebb közös többszörösé-
( k −1) nek minimuma, míg M max a k − 1 -elem indexhalmazhoz tartozó mi -k legkisebb közös többszöröseinek maximuma. A rendszer bizonyos hibavédelmet is jelent (akár véletlen, akár szándékos hiba esetén), ugyanis a kongruenciarendszernek akkor és csak akkor van megoldása, ha a J indexhalmazból választott bár′ ′ ′ ′ mely két különböz u és v indexre a megadott mu és m v legnagyobb közös osztója osztja a Tu − Tv különbséget. Annak a valószín sége, hogy ez valamennyi párra teljesül, amennyiben bizonyos indexekre a vessz s értékek egy része nem azonos az eredetivel, elég kicsi lehet (ez így persze nem egy pontos matematikai állítás, de nyilván pontossá tehet ).
8. Titokmegosztás 2. A második módszer a véges testeket alkalmazza. Legyen q az n pozitív egésznél nagyobb prímhatvány, és f egy tetsz leges, legfeljebb k − 1 -edfokú polinom Fq fölött. Ha az n-nél nem nagyobb pozitív egészekre az u i -k a test páronként különböz , nem nulla elemei, és vi = fˆ (u i ) , akkor legalább k különböz (u , v ) pár egyértelm en meghatározza a polinomot, és akkor fˆ (0 ) -t is. Legyen i
i
tehát T = fˆ (0 ) , és az i-vel azonosított résztvev kulcsa (u i , vi ) . Azt már láttuk, hogy ha legalább k pár ismert, akkor T meghatározható. Ha viszont legfeljebb csak k − 1 pár áll rendelkezésre, akkor legalább q olyan, legfeljebb k − 1 -edfokú polinom van, amely az el bbi pontokban a megadott értéket veszi fel, és ezek 0-ban felvett értéke között a test minden eleme el fordul, így T-r l semmilyen információnk nem lesz. Legyen az u i -k rendjeinek legkisebb közös többszöröse t, és u primitív t-edik egységgyök Fq fölött. u eleme Fq -nak, hiszen az u i -k mindegyike benne van a testben, és így mindegyikük rendje osztója q − 1 -nek, de akkor t is osztója ennek az egésznek. Az is igaz, hogy t ≥ n , hiszen az u i -k páronként különböz ek, és mindegyikük az u egy nem negatív, t-nél kisebb egész kitev s hatványa. Feltehetjük, hogy n és t megegyezik, ugyanis ellenkez esetben fiktív résztvev kkel b víthetjük a rendszert. Ekkor u primitív n-edik egységgyök, megfelel indexeléssel u i = u i , és
( )
vi = fˆ (u i ) = fˆ u i =
k −1 j =0
( )
f j ui
j
= (ne )
−1
n −1 j =0
(nf )(u )
i j
j
,
ahol k ≤ j < n -re f j = 0 , ami nem más, mint az Fq feletti n-dimenziós tér egy olyan elemének, nf nek, u-val vett inverz Fourier-transzformáltja, amelyben n − k egymás utáni komponens értéke (nevezetesen a k ≤ j < n idexhez tartozó komponenseké) 0. Ez viszont azt jelenti, hogy az n darab vi egy Fq fölötti, [n, k ]q paraméter Reed-Solomon kód egy kódszavának tekinthet , és az i-edik résztvev kulcsa az (i, vi ) pár (ez persze lényegében véve azonos a korábbi kulccsal, hiszen i egyértelm en
meghatározza u i -t, tehát u i -t). Tegyük fel, hogy s = k + 2r kulcs áll rendelkezésünkre, amelyek közül r különbözik a valódi kulcstól (akár véletlenül, akár szándékosan), vagyis ismert egy olyan vektor s komponense, amely ezen pozíciók közül r helyen különbözik az eredeti kódszótól. Ez egyben azt is jelenti, hogy adott n − s olyan pozíció, amelynek nem ismerjük az értékét. A helyzet úgy is felfogható, hogy van egy vektorunk, amely egy kódszóból n − s törl déses hibával, és r további hibával keletkezett. Egy d távolságú kód helyesen javít, ha a törl déses hibák számának, és a további hibák r száma kétszeresének összege kisebb, mint a kód távolsága, ami most teljesül, hiszen n − s + 2r = n − k , és egy [n, k ] -paraméter Reed-Solomon kód távolsága n − k + 1 . A javítás után kapott vektor az eredeti kódszó, amelyb l például Fourier-transzformációval meghatározható f, és akkor T = fˆ (0 ) is. fˆ (0 ) -t azonban lényegesen könnyebben, s t nagyon könnyen kiszámíthatjuk v-b l: n −1 i =0
vi =
n −1 i=0
−1 ahonnan fˆ (0) = (ne )
( )
fˆ u i = n −1 v i=0 i
n −1 k −1 i=0 j =0
fj
(u )
i j
=
k −1 j =0
fj
n −1 i =0
.
42
(u ) = nf j i
0
+
k −1 j =1
fj
(u )
n j
−e = nf 0 = nfˆ (0) , u −e j
9. Elektronikus pénz, kriptográfiailag hitelesített pénz Már korábban szóba került egy alapvet konfliktus, amely az egyén és a társadalom érdekeinek ütközéséb l fakadt. Hasonló problémával találkozhatunk a pénzforgalom területén is. A különböz készpénzkímél fizetési módszerek többnyire igen hasznosak és kényelmesek, és ugyanakkor nagyon el nyösek az állam biztonsága szempontjából, hiszen könny egyénhez kapcsolódóan nyomon követni egy-egy tranzakció útját. A dolog másik oldala viszont, hogy vannak olyan esetek, amikor valaki anonim módon szeretne például valamit vásárolni. Ennek a lehet ségét a készpénzzel való fizetés teremti meg. Ez mutatja, hogy napjaink egyre elektronizáltabb világában is szükségünk lehet a régi, jól bevált, kézzel fogható bankókra és érmékre. Illetve nem is feltétlenül a materiális valóságában létez készpénzre van szükség, hanem csupán egy tetsz leges olyan eszközre, amely úgy funkcionál, mint a készpénz, vagyis amely képes részt venni a cserefolyamatban, de amely utólag nem köthet egy konkrét személyhez, egy konkrét tranzakcióhoz. Ilyen eszközt meg lehet valósítani kriptográfiai eszközök segítségével is. A CEPS Csoport (Europay International, Visa España/SERMEPA, Visa International és ZKA) 1998. december végén közzétette azokat a specifikációkat, amelyek segítségével a világ különböz elektronikus pénztárca-programjai képesek az együttm ködésre. A közös elektronikus pénztárcaspecifikációk (CEPS – Common Electronic Purse Specifications) létrehozása jelent s lépés a nyílt elektronikus pénztárcaszabvány megteremtése felé, és világszerte el segíti az intelligens kártyák számának növekedését. A CEPS Csoport a specifikációkat el ször átadja ellen rzésre a biztonsági laboratóriumoknak, majd a kiértékelés befejeztével közzéteszi a végleges specifikációkat. Az elektronikus pénztárcaprogramok többsége Európában zajlik, így különböz európai intézmények – többek közt az ECBS (European Committee for Banking Standards) – is nagyban hozzájárultak a specifikációk megalkotásához. Következésképpen várhatóan els ként az európai programok fogják alkalmazni a specifikációkat, mivel itt az Euro bevezetése tovább fokozza a közös szabványok iránti igényt. A CEPS bevezetésével lehet vé válik, hogy a kártyabirtokosok belföldön és külföldön egyaránt használhassák elektronikus pénztárcájukat. Huszonkét ország szervezetei – amelyek a világ elektronikus pénztárcáinak több mint kilencven százalékát képviselik – döntöttek már eddig a CEPS alkalmazása mellett. Ezek között a szervezetek között szerepel a Visa International, a Visa España/SERMEPA, a ZKA, a Europay International, a Proton World International, az olaszországi SSB, a szingapúri NETS, a „Cash" pénztárcaprogramot támogató svéd bankok és a Europay Austria. A Groupement Cartes Bancaires szintén elkötelezte magát a kezdeményezés mellett, és szívesen válna a CEPS Csoport aktív tagjává. A CEPS felsorolja a feltételeit, hogy valamely szervezet bevezessen egy világszerte kompatíbilis elektronikus pénztárcaprogramot. Megköveteli a chipkártyákra kidolgozott EMV-szabványokkal (Europay, Mastercard, Visa) való kompatibilitást, továbbá definiálja a következ fogalmakat: kártyaalkalmazás, kártyaterminál-interfész, POS- és pénztárca-feltöltési tranzakciók terminálalkalmazásai, adatelemek, valamint a tranzakció-feldolgozási folyamat ajánlott üzenetformátumai. A CEPS megfogalmazza a különböz elektronikus pénztárcarendszerek résztvev i számára felállított funkcionális követelményeket, valamint a fokozott biztonságosság érdekében külön titkosítási kulcsot alkalmaz. A közös elektronikus pénztárca-szabvány kialakítására tett er feszítések újabb lendületet kaptak 1998. júniusában, amikor a világ legnagyobb pénztárcarendszer-m ködtet i bejelentették, hogy munkacsoportot alakítottak a nyílt ipari specifikációk kidolgozására. A CEPS ennek a törekvésnek a megvalósulása. Az elektronikus készpénz egy lehetséges megvalósítása a következ . A bank minden létez címlethez el állít egy-egy RSA-paraméterrendszert, amelyek közül a nyilvános paramétereket, mondjuk a t címletre vonatkozóan (t , nt , et ) -t, nyilvánosságra hozza, a titkos paramétereket viszont (t esetén d t -t) titokban tartja. Tegyük fel, hogy Pénzes úr, akinek ennél a banknál van számlája, szeretne egy tegységnyi címletet készpénzben kivenni a bankból. El állít két nagy, véletlen számot, r-et és M-et, amelyek közül r-nek létezik az inverze a nyilvános nt paraméterre vonatkoztatva, vagyis amelyhez
9. Elektronikus pénz, kriptográfiailag hitelesített pénz van olyan r ′ , hogy rr ′ mod nt = 1 . M természetesen valamilyen számrendszerben van megadva, mondjuk binárisan. Pénzes úr leírja M-et, és közvetlenül mellé másolja ismét M-et. A kapott M ′ eredményt M M -mel jelöljük (mondjuk legyen M = 5 , akkor ez bináris felírásban 101, és ebb l
M ′ = M M = 101101 = 45 ), majd kiszámítja s = r et M ′ mod nt -t, és elküldi a bankjába azzal, hogy a számlájáról emeljenek le t forintot, és adjanak ki készpénzben ugyanekkora összeget. A bank megterheli Pénzes úr számláját a t összeggel, és visszaküldi a megfelel összeg igazolását, s ′ = s d t mod nt -t. Ebb l Pénzes úr kiszámítja T = r ′s ′ mod nt -t, amib l a következ t kapja: T = r ′s′ mod nt = r ′(s dt mod nt ) mod nt = r ′s dt mod nt = = r ′(r et M ′ mod nt ) mod nt = r ′(r et M ′) mod nt = dt
dt
= r ′(r et ) M ′dt mod nt = r ′rM ′dt mod nt = M ′dt mod nt dt
A legutolsó eredmény, T = M ′dt mod nt lesz a t összegnek megfelel készpénz. Ha Pénzes úr fizetni akar egy T ′ -s, állítólag t-nek megfelel pénzeszközzel egy boltban, akkor a boltos a nyilvános (t , nt , et ) paraméterek segítségével kiszámítja M ′′ = T ′et mod nt -t. Ha az átadott T ′ valóban egy térték fizet eszköz, akkor M ′′ = M ′′′ M ′′′ szerkezet . Az említett számok igen nagyok, százas nagyságrend decimális számjegyb l állnak. Pénzes úr úgy tudna csalni, ha az el bb leírt folyamat kikerü~ ~ lésével, közvetlenül, a bank nélkül el tudna állítani egy olyan T számot, hogy T et mod nt számjegyes felírásában a számjegyek bal oldali felének sorozata jegyr l jegyre megegyezik a jobb oldali fél jegysorozatával. Ennek a valószín sége d t ismerete nélkül, a szám nagyságát figyelembe véve, amely kizárja a próbálkozáson alapuló keresést, gyakorlatilag 0, vagyis szinte kizárt egy ilyen szám „vak tyúk” alapon történ el állítása (ha valakinek ez véletlenül sikerül, az „káló”-nak tekinthet , hiszen itt egy-egy bankjegyr l, vagy pénzérmér l van szó). Ha tehát a boltban átadott „pénz” a sifrírozás után kielégíti a formai követelményeket, akkor a boltban azt elfogadják t-egységnyi fizetésnek. Még egy „apróság”-ot kell figyelembe venni. Pénzes úr, vagy bárki, akinél ez a pénzdarab megfordul, ismételten és többször is fel tudná használni, ezért a bank nyilvántartást vezet a hozzá benyújtott, a számlán jóváírandó fizet eszközökr l (vagyis a mi esetükben M ′′′ -r l), és egy adott M ′′′ -t csupán egyszer fogad el. Ez viszont azt jelenti, hogy az óvatos boltban rögtön a fizetéskor benyújtják a bankhoz a kapott „bankjegy”-et illetve „érmé”-t, és csak akkor fogadják el fizetés gyanánt, ha a bank azt érvényesnek találta, és jóváírta a bolt számláján. Ez persze azért nem jó, mert akkor a bolt ezt a pénzeszközt nem tudja felhasználni a pénzforgalmában. Ha viszont nem így jár el, akkor azt kockáztatja, hogy átverik, becsapják. Ez a módszer valóban lehet vé teszi az anonimitást. A bank, amikor Pénzes úr t le pénzt kér, nem tudja, hogy mi volt M, ugyanis csak s = r et M ′ mod nt -t látja, és ebb l nem tudja kiszámítani M ′ -t, és így nem képes meghatározni M értékét, hiszen nem ismeri r-et. Ebb l következik, hogy amikor benyújtják neki M ′ -t, akkor azt nem képes Pénzes úrhoz kapcsolni.
(
)
A fentieket egy egyszer példán, kis számokkal mutatjuk be. Legyen a két prím 113 és 127, ekkor n = 14 351 , és ϕ (n ) = (113 − 1)(127 − 1) = 14 112 . Ha nyilvános kitev nek e = 131 -et választjuk, akkor némi számolással 131 ⋅ 9 803 − 1 = 1 284 192 = 91 ⋅ 14 112 , így d = 9 803 . A nyilvános adatok (100, n = 14 351, e = 131) . Most legyen például r = 37 és M = 54 , ekkor s = 5 818 és M ′ = 5 454 .
r e 14 351 -gyel való osztásakor keletkez maradék 814, majd ezt 5 454 -gyel szorozva, és a szorzatot elosztva 14 351 -gyel, a kapott maradék 5 097 , vagyis a korábbi jelölésekkel s = 5097 . s-t beküldi Pénzes úr a bankba, ahol kiszámítják s d-edik hatványának maradékát a 14 351 -gyel való osztáskor, ami 10 137 . Ezt a számot Pénzes úr megszorozza r ′ -vel, és veszi az n-nel való osztási maradékot, T-t, ami most 8 807 , ez a szám tehát egy 100 forintost képvisel. Ha most valaki ezzel a pénzzel fizet, ak-
44
9. Elektronikus pénz, kriptográfiailag hitelesített pénz kor a keresked veszi T e-edik hatványát, és elosztja a hatványt 14 351 -gyel. Ez a maradék T = 8 807 esetén 5 454 , vagyis egy olyan szám, amelynek a bal oldali és jobb oldali fele megegyezik, és mivel a 100 forintoshoz tartozó adatokkal számoltuk, ezért elfogadjuk egy 100 forintos pénzeszköznek. Benyújtva T-t a banknak, az ellen rzi, hogy nem fizetett-e már egyszer valaki ezzel a pénzzel, és ha nem, akkor jóváír a keresked nek 100 forintot. A fenti számítás kézzel, papíron és ceruzával nem túl kényelmes, hiszen a számolás közben keletkez részeredmények igen sok jegyb l álló számok, ám egy számítógép számára ez gyerekjáték. A valóságban persze az alkalmazott számok körülbelül 100-jegy ek, és az ilyen nagy számokkal már egy gyors számítógépnek is el kell bíbel dnie egy-két percig, de azért elboldogul a feladattal. Röviden nézzük meg, hogy milyen módon képes a kriptográfia hozzájárulni a pénzhamisítás leküzdéséhez. A másolás ellen természetesen nem alkalmazható véd eszközként, de hamis pénz el állítása ellen igen. A módszer szerint mindenegyes bankóra felvisznek egy véletlenszer pontokból álló mintázatot. Ezt a mintázatot végigpásztázzák, és átalakítják egy bitsorozattá (PAT). Ezt a számot a kibocsátó bank aláírja a nyilvános kulcsú aláírásával, és az így kapott aláírást (SIG) egy hibakorlátozó kódolás után egy számjegysorozattá alakítják ( SIG * ), amelyet rányomnak a bankjegyre. A hibakorlátozásra azért van szükség, mert ha hibásan olvassák le fizetéskor a számot, akkor az ellen rzés biztosan sikertelen lesz. Felhasználáskor SIG * -ot visszaalakítják SIG-gé, majd a nyilvános kulcs segítségével PAT-té, és ezt összehasonlítják a bankjegyr l leolvasott és digitalizált bitsorozattal, PAT ′ -vel, ami általában nem lesz pontosan azonos PAT-tel a használat során „elszenvedett” apró változások miatt. A gyakorlatban akkor fogadható el eredetinek a bankó, ha az eltérés egy bizonyos értéket, mondjuk a 80%-ot nem haladja meg.
45
10. Etimológia kripto- gör el tagként vminek a titkos v. rejtett voltát jelöli; titkos-, rejtett (krüpto) a (krüptosz) rejtett, titkos görög szóból (f névi igenév: krüptein) elrejt -lógia, -logia gör-lat 1. utótagként jelöl: vmilyen tudományt; -tan, -tudomány (pl. geológia) 2. utótagként jelöl: (számnevekkel) az összetev k számát (pl. tetralógia) 3. utótagként jelöl: vmilyen beszéd- v. el adásmódot (pl. tautológia) (logosz) szó, beszéd, magyarázat, fogalom, tudomány szóból eredeti görög képzés utótag , , (logiosz, logia, logion) értelmes; tudománnyal kapcsolatos (lego) (f névi igenév: legein) mond kriptológia gör el. a rejtjelfejtés elmélete és gyakorlata rejtett dolgok tudománya -gráfia (-graphia) gör 1. utótagként jelöl: vmely tudományágat (pl. geográfia) 2. utótagként jelöl: vmely írás- v. más rögzítési módot (pl. fotográfia) 3. utótagként jelöl: vmely nyomdászati eljárást; -nyomás (pl. litográfia) (grafé) írás szóból görög képzés utótag (grafo) (f névi igenév: grafein) vés; ír kriptográfia gör el. titkosírás, rejtjeles írás, ill. ennek rendszere, kulcsa fn Tud|Titkosírások készítésének és megfejtésének módszertana.|Titkosírás. [nk:gör el.] titkosírás (mestersége) analízis gör 1. elemzés; részekre, elemekre való bontás mint tudományos kutató módszer 2. mat a matematika azon ágainak összessége, amelyek a függvény, a határérték, a differenciál és az integrál fogalmával szervesen összefüggnek, arra épülnek 3. vegyelemzés 4. lélekelemzés, pszichoanalízis (analüszisz) feloldás, megoldás, darabokra szedés, megfejtés (analüo) (f névi igenév: analüein) feloszt, feldarabol - (ana-) föl + (lüo) (f névi igenév: lüein) old kriptoanalízis gör cryptanalysis fn titkosírás megfejtése titkos írás, titkos jelek megfejtése -gram, -gramma gör 1. utótagként jelent: vmilyen -gráf utótagú m szer által lerajzolt görbét (pl. szeizmogram) 2. utótagként jelent: vmilyen ábrát v. görbét (pl. diagram) 3. utótagként jelent: vmely írásm vet (pl. epigramma) (gramma) vésett, bet ; rajzolás, írás, feljegyzés | -ból a – képz vel kriptogramma gör el. titkosírásos v. rejtett értelm felirat, szöveg(részlet) entrópia: Shannon javaslatára entrópiának nevezzük az információ átlagos hírértékét. Az entrópia eredetileg a h tanban használt állapotjelz neve, melyet Rudolf Clausius vezetett be a termodinamikai folyamatok megfordíthatóságának mértékeként. Az εντρεπειν (entrepein) görög szó, jelentése: megfordít. Az információelméleti és termodinamikai entrópia rokonsága a matematikai modell azonosságára vezethet vissza. entrópia gör 1. fiz anyagi rendszerek molekuláris rendezetlenségi fokának, ill. állapotuk termodinamikai valószín ségének mértéke 2. fiz az energia hasznosíthatóságának, munkavégz képességé-
10. Etimológia nek mértéke termikus folyamatokban 3. inf a bizonytalanságnak a kapott információkkal csökken arányszáma 4. fil a termodinamikai állapotfüggvények hatályának hibás kiterjesztése révén létrehozott elmélet a világ h haláláról (entropia) fordulat (entropé) fordulat, belefordulás, meghajlás, lealacsonyodás szóból valószín leg latin szavak mintájára képzett szó - (en) -ban, -ben + (tropé) fordulat a (trepo) (f névi igenév: trepein) fordít igéb l
redundancia: 1. hétköznapi értelemben felesleg, vagyis az a többlet, amelyet a cél eléréséhez mindenképpen szükséges eszközökön túl használnak. 2. Számítástechnikai vonatkozásban az információ ábrázolására rendelkezésre bocsátott, de fel nem használt terület. Ha egy karakterlánc például 256 karakteres, de aktuális értéke csak 6 bájt hosszú, 250 redundáns bájtot tartalmaz, hiszen az eredetileg a karakterlánc számára lefoglalt tárterület nagysága nem változik. 3. Az információforrás redundanciája az egyenletes eloszlású forrás maximális entrópiájához viszonyított relatív entrópia komplementere: R S = 1 − H (S ) log V . Szemléletesen a forrás egy hírében, üzenetében rejl , de információt, tehát újdonságot nem tartalmazó közlés arányát, a hír banalitásának fokát fejezi ki. 4. A kód redundanciája az átlagos szóhossznak az információt ténylegesen nem hordozó, vagyis a feltétlenül szükséges minimális szóhosszt meghaladó része. A szeparálható kódok esetében a minimális szóhosszt pontosan ismerjük, ilyenkor ennek és a tényleges szóhossz arányának a komplementere a kód redundanciája. Mivel L0 = H (S ) log B (Shannon II. tétele, lásd minimális szóhossz, ezért
R E = 1 − L0 L = 1 − H (S ) (L log B ) .
redundancia lat 1. inf újabb információt nem adó felesleg a közleményben, amely nélkül azonban a megértés nehezebbé válna 2. vminek redundáns volta fn Távk Közlésben az egyértelm megértéshez elvileg elegend minimumom felüli többlet. [nk: lat] redundantia (túlzott) b velkedés redundáns lat 1. inf új információt, érdemleges közlést már nem tartalmazó 2. terjeng s, fölösleges elemeket tartalmazó redundant-, redundans (lat) jelenidej melléknévi igenév a redundo, redundare túlcsordul igéb l re-, red- (fokozás)- + unda hullám sifre (fr
ném) titkosírás, rejtjel
sifríroz fr desifríroz fr
ném titkosírással ír, rejtjelez ném kibet z, titkos- v. rejtjelezett írást megfejt
chiffre h fn 1. szám(jegy) 3. titkos írásjel, rejtjel, sifrírozás; en chiffres sifrírozva; rejtjelben; le Chiffre a külügyminisztérium rejtjelosztálya 4. rejtjel- v. sifre-kódex; titkosírás rendszere [ábécéje] chiffre n. m. (XVe, «écriture secrète»; cifre, 1220; lat. médiév. cifra «zéro», de l’arabe sifr «vide», ch- d’apr. it. cifra) II. 1. Caractères numériques de convention employés dans une écriture secrète (V. Cryptographie). Écrire en chiffres (opposé à écrire en clair). – Par anal. Tout signe de convention servant à correspondre secraitement, et absolt. Le chiffre, l’ensemble de ses signes. V. Code. Changer de chiffre. Avoir le secret, la clef du chiffre. V. Chiffrer, déchiffrer. Service du chiffre: bureau civil ou militaire où l’on chiffre et déchiffre les dépêches secrètes. Être affecté au chiffre. 48
10. Etimológia cifra, ziphra, zifera (jel, számjel, nulla, titkos írásjel) kés -/középlatin szó. A klasszikusban érthet en nem létezik, mert az arab sifr XIII. századi átvétele a latin matematikai m nyelvbe. Eredetileg az arab szó a szanszkrit s nya tükörfordítása. Számos európai nyelvben jelen van: Ziffer (ném., ciffer), chiffre (fr., sifr), cifra (ol., csifra)... A titkos írásjel értelme a diplomácia köreib l fejl dött, ugyanis itt gyakran alkalmaztak számjegyeket titkosított írásokban. A magyarba is eredetileg hasonló értelemben került be, majd a zérus, a kis kör forma díszít elemként való alkalmazása elvezetett a cifra, díszes, tarka értelemhez is. zéró, zérus (arab ol) 1. nulla, semmi 2. biz senki; jelentéktelen ember (szifr) (szufr) (szafir) (szufur) (szafr) többesszáma: haszontalan, értéktelen, mentes ( (min) vmit l) (szifr) zérus, zéro, nulla, semmi
(’ászfár) üres,
kommunikáció lat 1. tájékoztatás, (hír) közlés 2. inf információk közlése v. cseréje vmilyen erre szolgáló eszköz, ill. jelrendszer (nyelv, média, gesztusok stb.) útján 3. ritk közlemény 4. összeköttetés, kapcsolat, érintkezés communicatio közlés, a közlés folyamata communis, communæ közös communico, communicare megoszt, közöl, közössé tesz kommunikál lat közöl (vmit vmivel, vkivel); értesít (vkit) információ lat 1. felvilágosítás, tájékoztatás 2. hírközlés 3. értesülés, adat 4. híranyag, a közlés tárgya 5. inf elektronikus úton továbbított jel; hír informatio formába öntés; közlés átvitele informo, informare, informavi, informatum az in (-ba, -be, -ban, -ben) praepositio – igeköt – és a forma, formae f(emininum) (alak) összetétele. A forma szó a fero ferre tuli latum (hoz, visz) ige gyökének min ségi hangmásulás (qualitatív ablaut – gyakori jelenség az indoeurópai nyelvekben) szenvedett alakja és egy f névképz (ma suffixum) egyesüléséb l van. Informo = alakot ad, formába önt, képletesen szavakban, szavakkal formál meg, azaz közöl. kód (lat fr) 1. inf megállapodás szerinti jelek v. szimbólumok rendszere, amellyel vmely információ továbbítható és visszaalakítható 2. biol genetikai kód 3. rejtjeles ábécé kulcsa 4. inf jelábécé (sürgönynél, távírónál stb.) (fn) 1. Tud Megállapodás szerinti jelek v. szimbólumok rendszere, amellyel vmely információ egyértelm en visszaadható. 2. ritk Jelkulcs [nk:fr
49
Irodalom Beutelspacher Brassard Buttyán-Vajda Diffie-Hellman
Cryptology Modern Cryptology Kriptográfia és alkalmazásai New directions in cryptography; IEEE Trans. on Info. Theory, IT-22 (1976), pp. 644-654 Kahn: The Codebreakers The story of secret writing. Ködmön Kriptográfia Menezes-Oorschot-Vanstone Handbook of Applied Cryptography Nemetz-Vajda Algoritmusos adatvédelem Révay Titkosírások Salomaa Public-key Cryptography Shannon Communication Theory of Secrecy System; Bell Syst. Tech. J., vol. 28, 1948., pp. 656-715 (El ször „A Mathematical Theory of Cryptography”, Sept. 1, 1946, egy bizalmas jelentésben) Shannon A Mathematical Theory of Communication; Bell System Technical Journal, vol 27 (1948), pp. 379-423, 623-656 (magyarul egy javított változat „A hírközlés matematikai elmélete” címmel A kommunikáció matematikai elmélete-ben) Singh Kódkönyv. A rejtjelezés és a rejtjelfejtés története Tilborg An Introduction to Cryptology Virasztó Titkosítás és adatrejtés
