Jelen cikkben két rivális nyilvános kulcsú kriptográfiai rendszer, a nagy múltra visszatekintő és széles körben elterjedt RSA, valamint a viszonylag fiatalnak számító ECC hatékonyságvizsgálatának és összehasonlításának bemutatására kerül sor. Vizsgálódásunk során arra a kérdésre keressük a választ, hogy melyik kriptográfiai rendszer a jobb választás: az ECC vagy az RSA?

Az alapos elméleti és gyakorlati vizsgálódások eredménye az a végkövetkeztetés, hogy erre a kérdésre nem adható egyértelmű válasz. A két rendszer az egyes műveletek esetében eltérő hatékonysági paraméterekkel és különböző korlátokkal rendelkezik. A cikkben ezeket a jellemzőket kívánjuk bemutatni. Ezek ismeretében már egy adott alkalmazás esetében könnyebben hozható döntés. Ehhez kíván segítséget nyújtani az általunk összegyűjtött, az ECC és az RSA viselkedését összefoglaló gyűjtemény.

Napjainkban az elektronikus ügyintézés egyre szélesebb körű elterjedésével elengedhetetlenül szükségessé vált egyes adatbiztonsági szolgáltatások – pl. partner azonosítás, digitális aláírás, letagadhatatlanság stb. – megvalósítása. Ezekhez a nyilvános kulcsú kriptográfia biztosítja az elméleti alapot. A nyilvános kulcsú kriptográfiában több különböző matematikai alapötlet is alkalmazhatónak bizonyult^¹, ezekre építve számos algoritmus- és protokollcsalád került kidolgozásra. A színes választék ellenére azonban jelenleg a gyakorlatban alkalmazott nyilvános kulcsú rendszerek döntő többsége az RSA algoritmust [1] használja.

Az RSA algoritmus jóságát támasztja alá, hogy negyed évszázada nem sikerült hatékony törési módszert találni ellene, mindazonáltal biztonsága matematikailag nem bizonyított. Többek között ezért is érdemes figyelmet szentelnünk a vetélytársaknak. A viszonylag fiatalnak számító, ECC (Elliptic Curve Cryptography) [2] [3] összefoglaló névvel illetett protokollcsalád szintén ígéretes gyakorlati alkalmazási lehetőségekkel kecsegtet. Az ECC egy rendkívül érdekes struktúra, az elliptikus görbék pontjain értelmezett csoport felett működik. Matematikai háttere sokkal bonyolultabb, mint pl. a modulo aritmetikát használó RSA-é, cserébe viszont az ellene használható törő algoritmusok is lassabban működnek. Ennek köszönhetően az ECC-nél egy adott biztonsági szint eléréséhez sokkal kisebb kulcsméretre van szükség, mint az RSA-nál, vagyis az „egy kulcsbitre jutó biztonság” értéke nagyobb.

A kis kulcsméret mellett azonban még számos szempont van, amely fontos lehet két kriptográfiai rendszer összehasonlításakor. Érdekes lehet például az algoritmusok használata során tapasztalható hatékonysági jellemzők és működési korlátok vizsgálata. A következőkben ezekkel foglalkozunk a fentebb már említett két kriptográfiai rendszer, a régóta és széles körben használt RSA, valamint a napjainkban előtérbe kerülő ECC esetében. Célunk e két rendszer hatékonyságvizsgálata és összehasonlítása, amelyet az elméleti háttéren alapuló következtetések mellett a gyakorlatban elvégzett mérések eredményeivel támasztunk alá.

A választott nyilvános kulcsú kriptográfiai rendszerek nem teljesen csereszabatosak, aminek alapvető oka, hogy hátterükben eltérő matematikai alapötletek állnak. Ugyanazokat a funkciókat valósítják meg, de a működésükhöz szükséges paraméterek (nyilvános-titkos kulcspár, közös paraméterek) nem kompatíbilisek egymással. Ennek ismeretében nem meglepő tény, hogy sok szempontból lényegesen különböző hatékonysági jellemzőkkel bírnak, valamint korlátaik is általában eltérőek. A paraméterek inkompatibilitása ezen kívül bonyolultabbá teszi az összehasonlításukat is – ez a problémakör a későbbiekben részletezésre kerül.

Az egyes kriptográfiai algoritmusok alkalmazása során lényeges lehet a műveletek gyorsasága, a környezeti paraméterek és kulcsok kialakításának bonyolultsága, a tárolandó adatok mérete, az egyes protokollok során a szükséges üzenetváltások száma és az üzenetek mérete. Ezek minél pontosabb megismerése érdekében gyakorlati méréseket végeztünk a két választott kriptográfiai rendszerrel. A mért adatok az egyes kriptográfiai műveletek kódjának futási ideje, valamint a műveletek során létrejövő adatok: a közös paraméterek, a nyilvános és a titkos kulcs, a kódolt adat és az aláírás mérete voltak. A vizsgálódás során szerzett tapasztalatokból az egyes algoritmusok alkalmazási korlátait is sikerült behatárolni (pl. a kódolható maximális adatméret). A vizsgált kriptográfiai műveletek a kulcsgenerálás és közös paraméterek felállítása, a kódolás, a dekódolás, az aláírás és az aláírás ellenőrzés voltak.

Egy adott kriptográfiai művelet viselkedését számos paraméter befolyásolja, pl. az alkalmazott kulcs mérete és típusa, a bemeneti adat mérete és típusa, ECC-nél az alapul szolgáló csoport típusa és az előszámított táblák használata. A vizsgálódás során célunk volt annak feltérképezése is, hogy az adott műveletek mely bemeneti értéktől és milyen mértékben függnek. A fennálló összefüggések pontos megismerése érdekében a fenti paraméterektől való függést külön-külön vizsgáltuk. (Ekkor a többi paraméter értéke néhány jellemző kombinációban rögzített volt.)

A sokféle paraméter és ezek változatos, értelmes kombinációi révén a vizsgálandó esetek száma rendkívül naggyá nőtt. Ez az ECC esetében kb. 4000, az RSA esetében több, mint 2000 mérés elvégzését jelentette.

Terjedelmi okokból jelen cikkben nem kerül bemutatásra a mérések eredményeinek elemzéséből nyert tapasztalatok teljes skálája^², csak a legalapvetőbb és legérdekesebb összefüggések taglalására szorítkozunk.

Az előbbiekben bemutatásra került, hogy milyen sokféle paramétertől függenek a vizsgálandó hatékonysági jellemzők. Joggal felmerül tehát a kérdés, hogy a két választott kriptorendszer viselkedése milyen paraméterválasztások mellett kerüljön összehasonlításra?

A bemeneti adatok (kódolandó illetve aláírandó adat file) tekintetében természetesen egyszerű a válasz, hiszen itt megoldható az azonos méretű és típusú adatok választása mindkét helyen – kivéve, ha valamelyik kriptorendszer már nem működik arra az adott bemenetre, de ez külön vizsgálódás tárgyát képezi.

Nem ilyen egyszerű a helyzet az alkalmazott kulcsméretek meghatározása esetében. Azonos kulcsok alkalmazása már csak azért sem megoldható, mert mint említettük, a két különböző kriptorendszerhez tartozó nyilvános-titkos kulcspárok és egyéb közös paraméterek nem kompatíbilisek egymással. Mivel a kulcsméret az a paraméter, amivel az egyes kriptorendszerek biztonságosságát hangolni lehet, ezért az egyik kézenfekvő megoldás az, hogy azonos biztonságot nyújtó kulcsméretek mellett hasonlítjuk össze a hatékonysági jellemzőket. Másik, nem annyira természetes, de érdekes megközelítés, hogy egy adott hatékonysági jellemzőt kiválasztva, adott kriptográfiai műveletre azt vizsgáljuk, hogy milyen kulcsok mellett kapunk azonos eredményt – vagyis ekkor melyik algoritmus nyújt nagyobb biztonságot. Ilyen következtetés lehet pl. hogy adott idő alatt melyik algoritmus tud nagyobb biztonságot nyújtó kódolást megvalósítani.

Mindezekhez szükségünk van arra, hogy a kulcsméreteket biztonsági szintekhez rendeljük, meghatározzuk az azonos biztonságot nyújtó kulcsméreteket. Ez nem egyszerű feladat, mély matematikai, kriptográfiai ismereteket kíván. Adott kriptográfiai algoritmus biztonságosságát az ellene alkalmazható legjobb, általános esetben működő törő algoritmus költsége (szükséges lépésszáma) határozza meg. Az RSA törésére létezik a kulcsméret függvényében szubexponenciális költségű törő algoritmus, az ECC-nél eddig jelenleg csak tisztán exponenciális költségűt találtak. Ennek köszönhető, hogy az ECC kulcsméretei általában kisebbek. Több független nemzetközi kutatócsoport munkáját alapul véve [6] [7] [8] [9] jelenleg elfogadott, hogy az 1024 bites kulcsú RSA és a 160 bites kulcsú ECC, illetve a 768 bites kulcsú RSA és a 136 bites kulcsú ECC azonos biztonsági szintűnek. Ebből kiindulva az összehasonlításaink során a következő megfeleltetéseket használtuk fel:

A kulcsméretek különbözősége mellett a kriptorendszerek sajátosságai további nehézségeket gördítenek elénk az összehasonlításuk körülményeinek meghatározása tekintetében. Mind az ECC-nél, mind az RSA-nál a kulcsok illetve közös paraméterek többféle típusa különböztethető meg, és a tapasztalatok szerint ez a jellemző is befolyással van az algoritmusok viselkedésére. Ez tovább bonyolítja a helyzetet, hiszen a különböző összetételű és típusú paraméterek között nem létesíthető semmilyen értelmes megfeleltetés. Így tehát ezeket az eseteket mind külön kell kezelni, mint az egyes algoritmusok további típusait, és az összehasonlítások során mindegyik algoritmus-típust meg kell vizsgálni. Ezek részletesebb bemutatása az RSA és az ECC sajátosságainak taglalásánál (3.1, 3.2) található.

A mérések elvégzéséhez szoftver implementációt kellett választani a két kriptorendszerhez. A lehetőségek feltérképezése után a választás a Crypto++ nevű kriptográfiai programkönyvtárra esett [10], amely nyílt forráskódban elérhető és tartalmazza mind az ECC, mind az RSA szükséges algoritmusait. A Crypto++ C++-ban készült, stabil és jól átlátható struktúrájú, dokumentált programkönyvtár. Fejlesztése 1995 óta folyik folyamatosan, és jelenleg is széles felhasználói körnek örvend. Rendkívül sok kriptográfiai algoritmus implementációját tartalmazza, amelyek a nemzetközileg elfogadott specifikációknak (IEEE P1363, X.509, SEC1, SEC2 stb.) megfelelőek.

A közös implementációs forrás lényeges szempont volt annak érdekében, hogy elkerüljük a különböző programnyelven írt, különböző optimalizálásokat, programozói módszereket használó szoftverek közti különbségeket. Természetesen még így is sok múlik a kódot elkészítő programozó ügyességén és kriptográfiai jártasságán, de a függések felderítéséhez, nagyságrendi összehasonlításokhoz az így nyert adatok is érdemben használhatóak.

A mérések elvégzéséhez szükséges szoftver keretrendszer szintén C++ nyelven, a Microsoft Visual Studio 6.0 segítségével készült. A felhasznált kriptográfiai könyvtár a Crypto++ 4.1-es verziója.

Az elkészített program parancssorból paraméterezhető (kriptográfiai művelet, bemeneti paraméterek és kimenetek megadása, ismétlési szám), az előre összeállított tesztvektorokkal való többszöri futtatás batch file-ok segítségével került megvalósításra. A mérési eredményeket tartalmazó file-okat később Microsoft Excel segítségével elemeztük.

A program futtatására használt személyi számítógép fő jellemzői: Intel Celeron 450 MHz processzor, 128 KB synchronous write-back L2 On-board cache, 192 MB memória, 75 MHz memory bus speed, 75 MHz FSB. A gépen Windows 98 (version 4.10.1998) operációs rendszer futott.

A következőkben nagy vonalakban bemutatásra kerülnek a választott kriptorendszerek sajátosságai, amelyek ismerete szükséges az elemzések részleteinek megértéséhez. Maguknak az algoritmusoknak az ismertetésétől jelen cikkben terjedelmi okokból eltekintünk, ezek a megfelelő szakirodalmakban elérhetőek [1] [2] [3].

Az RSA-nál mind a titkos, mind a nyilvános kulcs egy-egy számpár, ahol az egyik szám a modulus (tipikusan 512-4096 bit hosszú szám), a másik pedig egy ennél kisebb (bithosszúságában tehát maximum ekkora) egész szám, az exponens. Az RSA kódolás lényege, hogy a kódolandó adatot modulárisan hatványozzuk, a kitevő a nyilvános exponens. A dekódolásnál szintén moduláris hatványozás történik, de ebben az esetben a kitevő a titkos exponens.

Az RSA kulcsgeneráláshoz két nagy prímre van szükségünk, ezek szorzata adja ugyanis a modulust. A nyilvános exponens értéke szabadon választható, a titkos exponens ebből, valamint a két prímből kerül kiszámításra. A művelet kritikus pontja a nagy prímek előállítása. A gyakorlatban használt módszerek általában úgy keresnek prímet, hogy választanak egy nagy véletlen számot, majd tesztelik, hogy összetett szám-e. A használt tesztelési módszerek olyanok, hogy amennyiben pozitív választ adnak, akkor a szám biztosan összetett, a negatív válasz jelenése azonban mindössze annyi, hogy a szám lehet prím. Ha a tesztet mindig különböző paraméterezéssel megfelelően sokszor lefuttatjuk, és mindannyiszor negatív választ kapunk, akkor az ismétlések számának függvényében annak a valószínűsége, hogy a szám nem prím, tetszőlegesen kicsire csökkenthető^³. Ekkor a gyakorlatban el szokták fogadni a számot prímnek. Amennyiben a tesztelés során valamikor pozitív eredményt kapunk, a számot el kell dobni, és egy újabb véletlen számmal kell próbálkozni. A módszer jellegéből következik, hogy a kulcsgeneráláshoz szükséges idő nem ugyanannyi minden esetben, hanem nagy mértékben függ a „szerencsétől”, vagyis attól, hogy milyen véletlen számot sikerült sorsolnunk.

Az RSA kódolásnál használatos gyorsító eljárás, hogy a nyilvános exponens értékét (amit amúgy is szabadon választhatunk meg) kicsire választjuk, hiszen ekkor a kódoláskor csak kis kitevőre kell emelni a kódolandó adatot. Veszélyes azonban nagyon kicsire (pl. 3-ra) választani ezt az értéket, mert ez lehetőséget ad bizonyos típusú támadásokra - ennek ellenére azonban sajnos néhány rendszer él ezzel a választással. Jó és szintén elterjedt az e=65537 választás, ez az érték ugyanis kevés 1-est tartalmaz (65537 = 10001h), elegendően kicsi ahhoz, hogy a kódolás még gyors legyen, de ennél az értéknél az említett támadások már nem működnek.

Az RSA algoritmus biztonságosságát a modulus mérete határozza meg, jelenleg biztonságosnak tartott az 1024 bites modulus használata. A modulus emellett befolyásolja még a maximális kódolható adatméretet, amelynek a kódoló algoritmusból következően minden esetben kisebbnek kell lennie a modulusnál.

Az ECC-nél szükségünk van egy elliptikus görbére és annak egy pontjára, amelyet a görbén értelmezett csoport bázispontjaként fogunk használni. A görbe és a bázispont alkotják a rendszer közös paramétereit. A titkos kulcs egy egész szám, a nyilvános kulcs pedig a görbe egy pontja, amelyet meg lehet adni pl. egy számpárral^⁴ (a pont koordinátáival).

A közös görbe és a bázispont meghatározása alapos vizsgálatot igényel, ugyanis ezeknek a paramétereknek több kritériumnak is meg kell felelniük. Az ezzel foglalkozó szervezetek az általuk jónak talált közös paramétereket ajánlások formájában rögzítették^⁵, a méréseknél mi is ezeket a közös paramétereket használtuk.

Az elliptikus görbék pontjain értelmezett csoport lehet prím-rendű vagy 2-hatvány-rendű. Ez meghatározza az elemek ábrázolási módját, a csoportművelet végzését stb., és ezek révén hatással van az ECC-s kriptográfiai műveletek viselkedésére. A 2-hatvány-rendű eset matematikailag sokkal bonyolultabb, viszont hardveres megvalósítás esetén sok gyorsítási lehetőség alkalmazható. A 2-hatvány-rendű csoportok még tovább bonthatóak a csoport generátorpolinomjának felépítésétől függően. Vizsgálódásunk során a 3 tagot tartalmazó (trinomiális) és 5 tagot tartalmazó (pentanomiális) 2-hatvány-rendű esetekkel foglalkoztunk. A tapasztalatok szerint a generátorpolinom tagszáma is befolyásolja a kriptográfiai műveletek hatékonysági jellemzőit – később látni fogjuk például, hogy a trinomiális esetekben működik gyorsabban az algoritmus.

Az ECC-nél a titkos kulcs egy egész szám, amire mindössze annyi a megkötés, hogy maximum akkora lehet, mint a görbén definiált csoport rendje (tipikusan 110-570 bit hosszú szám). Így ennek generálása egyszerű és gyors művelet. A nyilvános kulcs a görbe azon pontja, amelyet úgy nyerünk, hogy a bázisponton csoportműveletet végzünk önmagával annyiszor, amennyi a titkos kulcs értéke. A nyilvános kulcs generálása tehát függ a csoportművelet bonyolultságától (vagyis az alapul szolgáló csoport típusától), és a titkos kulcs értékétől.

Az ECC algoritmusainál sokszor végzünk csoportműveletet a bázisponton illetve a nyilvános kulcsként funkcionáló publikus ponton saját magukkal. Így kézenfekvő és praktikus gyorsítási eljárás, hogy előre elkészítjük, és egy táblázatban tároljuk ezen műveletek eredményeit. Így adott esetben a csoportművelet n-szer való elvégzése helyett csak egy táblázatban kell keresni, ami lényegesen gyorsabb lehet – természetesen a táblázatok eltárolásához többlet tárhelyre van szükség.

Az ECC-s kriptográfiai algoritmusok biztonságosságát az alapul szolgáló csoport rendje határozza meg. Jelenleg biztonságosnak tartott az az eset, amikor ez legalább 160 bites szám.

során a futási idők valamint a műveletek során létrejövő adatok mérete:

A műveletek során mért eredmények függenek a bemeneti paraméterektől. Ezek megválasztása a következő volt:

ECC-nél (a csoport rendje): 112, 128, 131, 160, 163, 192, 193, 224, 233, 239, 256, 283, 384, 409, 521, 571 bit;

ECC-nél (a csoport típusa): prím-rendű (ECP), 2-hatvány-rendű (EC2N) pentanomiális vagy trinomiális;

Kódolandó illetve aláírandó adat mérete: 4, 22, 38, 54, 70, 86, 214, 470, 512, 1024, 2048, 4096 byte;

Kódolandó illetve aláírandó adat tartalma: csupa ‘1’ bit, csupa ’0’ bit, értelmes szöveg (ASCII karakterek) kódja.

A következőkben kerülnek bemutatásra a mérési eredmények és az összegyűjtött tapasztalatok a vizsgált kriptográfiai művelet, azon belül a mért paraméter szerint csoportosítva.

Az adatfile-ok RSA esetében a PKCS #1, ECC-nél az ECIES által definiált formátumban vannak.

- A kulcsgenerálás műveletek futási idői különbözőek, az értékek exponenciális eloszlást mutatnak.

- 4096 bites kulcs generálása esetén a futási idő a legjobb esetben 0,2 másodperc, legrosszabb esetben több, mint 14 perc volt. A mért adatok átlaga 4096 bites kulcsnál 6 perc, 1024 bites kulcsnál 2,8 másodperc volt.

- A kulcsgeneráláshoz szükséges idő nem függ az exponens értékétől és típusától.

- A görbe megkeresésével nem foglalkoztunk, az ajánlott görbéket használtuk.

- Előszámított tábla elkészítésének az ideje függ az algoritmus típustól (ECP, trinom. EC2N vagy pentanom. EC2N) és a kulcsmérettől. Értéke a 0,03 másodperctől az 1,2 percig terjed.

- A kulcsgenerálás ideje függ a kulcs méretétől, az algoritmus típustól és attól, hogy volt-e bázisponthoz tartozó előszámított tábla. A bázisponthoz tartozó előszámított tábla használata több, mint kétszeresére gyorsítja a művelet elvégzését. A futási idő értéke 0,054 másodperctől (113 bites kulcs, trinomiális eset, van előszámított tábla) 1,4 percig (570 bites kulcs, pentanomiális eset, nincs előszámított tábla) terjed.

A következő grafikon az adott idő alatt generálható kulcsok méretét mutatja az egyes rendszerek esetében. Az x tengelyen az időt ábrázoltuk, beosztása logaritmikus, egysége a tick, ami jelen esetben 1/1000 másodpercet jelent. Az y tengelyen a kulcsméret található, itt az egység az ECC-s kulcs mérete; RSA esetében a megadott összerendelés alapján átkonvertáltuk az értékeket. (Jelmagyarázat: BP/BP-: van/nincs előszámított tábla a bázisponthoz, PP: a publikus ponthoz is létezik előszámított tábla.)

Látható, hogy az ECC három típusa és az RSA eltérő viselkedést mutat. Egy rendszer annál jobb, minél több bites kulcs készíthető el vele adott idő alatt. Ezek szerint egyértelműen a legjobb az ECP, ezt követi kicsivel a trinomiális EC2N. A pentanomiális EC2N és az RSA nagyjából együtt indulnak, de az RSA kisebb meredekségű, így „lemarad”. Ne felejtsük persze el, hogy az RSA kulcsgenerálás nem determinisztikus idejű – ez látszik is a görbe pontjainak vízszintes szórásából is – ennek ellenére jellegében jól összehasonlítható a többi rendszerrel.

RSA-nál a titkos és nyilvános kulcsokat tartalmazó file-ok mérete – értelemszerűen – függ a választott kulcsmérettől, valamint függ az exponens értékétől. A jellemző méretek^⁷:

ECC-nél az előszámított táblák adatfile-jainak mérete és a nyilvános és titkos kulcsok adatfile-jainak mérete függ a kulcs méretétől és az algoritmus típustól. A titkos kulcs egy egész szám, a nyilvános kulcs a görbe egy pontja, azonban a kulcsfile-ok a szabvány^⁸ szerint tartalmazzák a görbe paramétereit is. A jellemző méretek:

9. táblázat ECC kulcsfile-ok és előszámított táblák file-jainak méretei

A következő táblázat tartalmazza az RSA-nál és az ECC-nél szükséges paraméter file-ok (nyilvános és titkos kulcsfile-ok, valamint az ECC esetében az előszámított tábla file-ja) összméretét. Mivel ezek az adatok kulcsméret-függőek, az összehasonlítás az előzőekben meghatározott, azonos biztonságot nyújtó kulcsméretek mellett történik.

9. táblázat RSA és ECC paraméter file-ok összméretének összehasonlítása

Napjainkban a 160 bites ECC – 1024 bites RSA kulcsok választását tartjuk megfelelően biztonságosnak. Ezt a tipikus választást vizsgálva látható, hogy ugyan magának az ECC kulcsnak a bithossza kisebb az RSA-énál, a tárolandó adatok még előszámított tábla nélkül is kicsit több helyet foglalnak, mint az RSA adatai. Előszámított táblával együtt pedig majdnem háromszor akkora helyet igényelnek. Ennek oka, hogy az ECC-s kulcsfile-ok nagy részét a közös paraméterek adják ki, amelyeket a használt szabvány szerint tartalmazniuk kell. Amennyiben olyan más file formátumot alkalmaznánk, ahol a közös görbe és bázispont nem szerepel a kulcs file-ban, az ECC-s kulcsfile-ok ennél sokkal kisebbek lennének. Persze ilyenkor más módon kell gondoskodni a közös paraméterek egyértelmű meghatározásáról.

Az RSA rejtjelezésnél a PKCS #1 v2.0-ban definiált RSA OAEP SHA encryption scheme-et használtuk, az ECC esetében pedig a SECG által definiált Elliptic Curve ECIES, AKA EC-DHAES encryption scheme szerint történt a kódolás.

- A kódoláshoz szükséges idő érzékenyen függ a kulcsmérettől, a nyilvános exponens értékétől, de nem függ a kódolandó adat méretétől és típusától.

- A kódoláshoz szükséges idő 0,02 másodperctől (512 bites kulcs, e=3) 6,7 másodpercig (4096 bites kulcs, e=véletlen) terjed. Értéke 1024 bites kulcs és e=65537 tipikus paraméterek esetén 0,025 másodperc.

- A kódolás gyorsasága függ a kulcsmérettől, a kódolandó adat méretétől és a csoportművelet bonyolultságától – vagyis az algoritmus típustól, valamint attól, hogy rendelkezésre áll-e előszámított tábla.

- Előszámított tábla használata több, mint kétszeresére gyorsítja a műveletet. A gyorsítás mértéke csak a kulcsmérettől függ, a dokumentum méretőtől nem.

- A kódoláshoz szükséges idő 0,05 másodperctől (112 bites kulcs, ECP, 22 byte-os adat, előszámított tábla) 2,8 percig (570 bites kulcs, EC2N pentanom., 2048 byte-os adat, nincs előszámított tábla) terjed. Értéke ECP-nél, 163 bites kulcs és előszámított tábla használatánál, 2048 byte-os adat kódolásakor 0,12 másodperc.

A következő grafikon egy 22 byte-os adat kódolásához szükséges időket ábrázolja. Az x tengelyen az ECC-s kulcsméret, az y tengelyen az idő (tick-ben mérve) található. (Jelmagyarázat: PP/PP-: van/nincs előszámított tábla a publikus ponthoz.)

A grafikonról leolvasható, hogy a kis exponensű (e=3 és e=65537) RSA az összes rendszernél gyorsabb, ezt követi az ECP, majd az EC2N trinomiális esete. A véletlen exponensű RSA viszont már lassabb az említett ECC-s kódolásoknál, csak az EC2N trinomiális esetét múlja felül.

- RSA esetében a dekódolása függ a kulcsmérettől, nem függ azonban a kiindulási adat méretétől és az exponens értékétől (ez utóbbi logikus, hiszen ekkor nem a nyilvános exponenssel végzünk műveletet).

- A dekódoláshoz szükséges idő 0,03 másodperctől (512 bites kulcs) 4,45 másodpercig (4096 bites kulcs, terjed. Értéke 1024 bites kulcs esetén 0,13 másodperc.

- Az ECC-s dekódolás gyorsasága függ a kulcs méretétől, a kiindulási adat méretétől és a csoportművelet bonyolultságától – vagyis az algoritmus típustól, nem függ azonban attól, hogy rendelkezésre áll-e előszámított tábla.

- A dekódoláshoz szükséges idő 0,03 másodperctől (110 bites kulcs, ECP, 22 byte-os adat) 1,55 percig (570 bites kulcs, EC2N pentanom., 2048 byte-os adat) terjed. Értéke ECP-nél, 163 bites kulcs használatánál, 4096 byte-os adat dekódolásakor 0,136 másodperc.

A következő grafikon egy 22 byte-os adatból készült kód dekódolásához szükséges időket ábrázolja. Az x tengelyen az ECC-s kulcsméret, az y tengelyen az idő (tick-ben mérve) található. (Jelmagyarázat: PP/PP-: van/nincs előszámított tábla a publikus ponthoz.)

Leolvasható, hogy a dekódoláskor az ECP a leggyorsabb. Az RSA a trinomiális EC2N-nél is rosszabb eredményt produkál.

Az RSA és az ECC a kódolás során az azonos méretű adat file-okat különböző méretűvé alakítja át.

- A kódolt adat mérete az RSA-nál csak a kulcsmérettől függ (a kiindulási adat méretétől nem), viszont a maximálisan kódolható mérethatár elég alacsony. Ez abból következik, hogy a kódolandó adatnak kisebbnek kell lennie a modulusnál. A kódolt üzenet mérete a kódoló algoritmusból következően a modulus méretével egyezik meg.

- Az ECC-nél a kódolt adat mérete nem csak az alkalmazott kulcsmérettől függ, hanem a kódolandó adat méretétől is. Adott kulcsméret esetén a kódolt adat adott értékkel lesz nagyobb a kódolandó adatnál. Ez 160 bites kulcs esetén pl. 61 byte. Az ECC-nél is létezik korlát a kódolandó adat méretére, azonban ez sokkal nagyobb, mint az RSA esetében. Ez 160 bites kulcsnál 4035 byte-os korlátot jelent, és ekkor a kódolt adat mérete 4096 byte. Érdekesség, hogy minden maximális méretű kódolható adat kódoltja 4096 byte-os.

A következő táblázat a közös kulcsméretek melletti kódolt üzenethosszokat tartalmazza néhány kiindulási dokumentum méret esetén.

9. táblázat RSA-val és ECC-vel kódolt adatok méretének összehasonlítása

A táblázatból látható, hogy az ECC-vel kódolt adat mérete általában kisebb, mint az RSA-val kódoltaké. Az RSA mindössze 5 esetben jobb, de ekkor sem sokkal.

Az RSA-nál nagyon hamar beleütközünk a maximálisan kódolható adat méretének korlátjába, ez az ECC-nél sokkal később jelentkezik. A maximális kódolható adat mérete mindkét esetben a kulcs méretétől függ. A következő táblázat a közös kulcsméret melletti maximális kódolható üzenethosszokat hasonlítja össze.

Az aláírás a dokumentum lenyomatán a titkos kulccsal való műveletvégzést jelenti. Ez pl. az RSA esetében megegyezik a dekódolással. Az ECC-nél ez nem feltétlenül van így. Több ECC-s aláírás protokoll is létezik, ezek az elvégzendő pontos műveleteket illetően eltérnek. Emellett élhetünk azzal a feltételezéssel, hogy az aláírás viselkedése hasonló lesz, mint dekódolásé, de számítanunk kell bizonyos eltérésekre is.

Az aláírás ellenőrzés folyamata szintén tartalmazza a lenyomatkészítést, így az aláíráshoz hasonlóan ez is csak annyiban függ az aláírandó dokumentumtól, mint amennyire a lenyomatkészítő függvény. Ezt követően a nyilvános kulccsal történik műveletvégzés, ezért az aláírás ellenőrzés esetében a kódolás folyamatával fedezhetünk fel hasonlóságokat.

A tesztprogramban használt protokollok az RSA esetében a PKCS #1 v2.0-ban definiált RSA PKCS1v15 signature scheme, az ECC-s digitális aláírásnál pedig az ECNR signature scheme.

- Az aláírás időigénye nem függ az exponenstől, az ellenőrzés ideje igen. A kulcsmérettől és a dokumentum méretétől mindkét művelet függ.

- Az aláírás időigénye 0,033 másodperctől (512 bites kulcs, 22 byte-os adat) 4,431 másodpercig (4096 bites kulcs, 2048 byte-os adat) terjed. Értéke 1024 bites kulcs és 2048 byte-os adat esetében 0,14 másodperc.

- Az aláírás ellenőrzés időigénye 0,011 másodperctől (512 bites kulcs, e=3, 22 byte-os adat) 6,829 másodpercig (4096 bites kulcs, e=véletlen, 2048 byte-os adat) terjed. Értéke 1024 bites kulcs, e=65537 és 2048 byte-os adat esetén 0,023 másodperc.

- Az aláírás és az aláírás ellenőrzés időigénye függ a kulcsmérettől, az algoritmus típustól, és az előszámított tábla használatától. Az előszámított tábla több, mint kétszeresére képes gyorsítani a műveletet.

- Az aláírás időigénye 0,046 másodperctől (110 bites kulcs, ECP, előszámított tábla) 1,41 perc másodpercig (570 bites kulcs, EC2N pentanom., nincs előszámított tábla) terjed. Értéke ECP-nél, 163 bites kulccsal, előszámított tábla használata esetén 0,068 másodperc.

- Az aláírás ellenőrzés időigénye 0,045 másodperctől (110 bites kulcs, ECP, előszámított tábla) 1,6 percig (570 bites kulcs, EC2N pentanom., nincs előszámított tábla) terjed. Értéke ECP-nél, 163 bites kulccsal, előszámított tábla használata esetén 0,066 másodperc.

Az aláírásnál - a kódoláshoz hasonlóan - a leggyorsabban az ECP működik, ezt követi a trinomiális EC2N. Az RSA (annak minden típusa, hiszen az aláírás nem függ az exponenstől) csak a pentanomiális EC2N-et előzi meg.

Az aláírás ellenőrzésnél - ami a dekódolással mutat hasonlóságot - a kis exponensű RSA a legjobb, majd az ECP és a trinomiális EC2N következik. A nagy véletlen exponensű RSA viszonylag lassú, csak a pentanomiális EC2N-et előzi meg.

A digitális aláírás az aláírandó dokumentumon végzett lenyomatkészítésből, és a lenyomaton a titkos kulccsal való műveletvégzésből áll. Mérete nem függ a kiindulási dokumentumtól, hiszen az alkalmazott lenyomatkészítő függvény bármekkora bemenetből azonos méretű kimenetet állít elő. (Ennek értelmében függ viszont a lenyomatkészítő függvénytől, hiszen különböző lenyomatkészítő függvények különböző méretű kimenetet állítanak elő, pl. 16 vagy 20 byte-osat.) Az eredményül kapott aláírás mérete függ azonban az alkalmazott kulcsmérettől. A következő táblázat az ECC-s és RSA-s aláírások méretét^⁹ hasonlítja össze különböző kulcsméretek mellett. Az alkalmazott hash függvény az MD5, amely 16 byte-os lenyomatot készít.

A táblázatból jól látható, hogy az ECC aláírások sokkal kisebbek, mint az RSA aláírások.

A fentiekben bemutatásra került az RSA-val és az ECC-vel végzett mérések számos eredménye. A legfontosabb megállapításokat és összefüggéseket az alábbiakban foglaljuk össze, illetve kiegészítjük néhány, az elméleti kutatás során szerzett, a két kriptorendszerrel kapcsolatos érdekességgel.

Nem maradt más hátra, mint hogy választ adjunk a vizsgálódásunk alapkérdésre: Melyik rendszer a jobb választás, az ECC vagy az RSA?

Az alapos elméleti és gyakorlati vizsgálódás eredményeképpen az a végkövetkeztetés vonható le, hogy erre a kérdésre nem adható egyértelmű válasz. A két rendszer egyike sem sokkal jobb vagy sokkal rosszabb a másiknál, egyértelmű reláció nem állítható fel közöttük.

A két rendszer az egyes műveletek esetében eltérő hatékonysági adatokkal és különböző korlátokkal rendelkezik. Elképzelhető, hogy néhány esetben ezek a korlátok, viszonyszámok nem jelentősek, ugyanakkor bizonyos környezetben – például a PC-hez képest sokkal kisebb számítási kapacitással, gyorsasággal rendelkező chipkártyák esetében, vagy a korlátozott sávszélességgel rendelkező mobil kommunikáció során –, vagy bizonyos speciális igényekkel rendelkező alkalmazásoknál – például valós idejű rendszerek esetében – ezek a tulajdonságok mégis döntőek lehetnek. Ezeket figyelembe véve tehát egy adott alkalmazás szempontjából már megmondható, hogy melyik kriptorendszer a jobb választás. A fent összefoglalt ismeret-bázis ennek a döntésnek a meghozásához nyújt elengedhetetlenül szükséges alapot.

[1] RFC 2437, PKCS #1: RSA Cryptography Specifications Version 2.0. B. Kaliski, J. Staddon. October 1998.

[2] A. Menezes, “Elliptic Curve Public Key Cryptosystems”, Kluwer Academic Publishers, Boston, 1993.

[3] Standards for Efficient Cryptography Group (SECG), SEC1: Elliptic Curve Cryptography, SEC2: Recommended Elliptic Curve Cryptography Domain Parameters

[4 Endrődi Csilla, „Nyilvános kulcsú kriptográfia matematikai alapjai”, Networkshop2002

[5] Endrődi Csilla, „Elliptikus görbéken alapuló nyilvános kulcsú kriptográfiai algoritmusok elemzése”, diplomaterv, BME VIK, 2001.

[6] Dr. Arjen K. Lenstra, Dr. Eric R. Verheul, “Selecting Cryptographic Key Sizes”, The Journal of Cryptology, Springer-Verlag, 2000.

[7] Certicom Corp., “Current Public-Key Cryptographic Systems”, Certicom whitepaper, number 2, April 1997.

[8] Robert D. Silverman, “A Cost-Based Security Analysis of Symmetric and Asymmetric Key Lengths”, RSA Laboratories, Bulletin, Number 13 - April, 2000.

[9] M.J.B. Robshaw, Ph.D. and Yiqun Lisa Yin, Ph.D., “Elliptic Curve Cryptosystems”, An RSA Laboratories Technical Note Revised June 27, 1997.

[10] Crypto++ “a C++ Class Library of Cryptographic Primitives”, Version 4.1 1/13/2000, Wei Dai, http://www.cryptopp.com

[12] Benjamin Arazi: „Improved self-certified DL/EC signatures and key-agreements”, előadás, elhangzott az MTA Rényi Alfréd Matematikai Kutató Intézete és a MAK közös klubrendezvényén, 2000. április 26.

1Minden nyilvános kulcsú kriptográfiai algoritmus egy speciális, matematikailag „nehéz” problémán alapul. Az idők során több nehéz probléma használatával is próbálkoztak a kriptográfiában, ezek közül alapvetően három állta ki az idő próbáját: az Egészek Faktorizációs Problémája (IFP, Integer Factorisation Problem), a Diszkrét Logaritmus Probléma (DLP, Discreet Log Problem) és ennek az elliptikus görbék pontjain értelmezett csoport feletti kiterjesztése, az ECDLP. Ezt a témakört tárgyalja részletesebben a „Nyilvános kulcsú kriptográfia matematikai alapjai” [4] című cikk.

2Az összefüggések teljes gyűjteménye megtalálható az „Elliptikus görbéken alapuló nyilvános kulcsú kriptográfiai algoritmusok elemzése” [5] című diplomamunkában.

3 Létezik olyan módszer is, ami bizonyos körülmények között egy számról biztosan megmondja, ha az prím, de a gyakorlatban általában nem ezt szokták használni.

4 Léteznek helytakarékosabb pont reprezentációk is, ezekben az esetekben azonban a ponttal végzett számítás válik lassabbá.

5 Ilyen ajánlásai vannak a Certicomnak [11], illetve az ANSI-nak (ANSI X.9.62 1 és X.9.62 7).

6 Az ECElGamal algoritmus szerint. Létezik más algoritmus is, pl. a Menezes-Qu-Vanstone rejtjelezés.

Kulcs méret (bit)	Titkos kulcs (byte)	Nyilvános kulcs (byte)
512	344 - 375	92 - 124
768	488 - 536	124 - 175
1024	632 - 698	160 - 224
2048	1216 - 1345	292 - 421
4096	2671 - 2779	548 - 806

Görbe típusa		Kulcs méret (bit)	Titkos kulcs (byte)	Nyilvános kulcs (byte)	Előszámított tábla a bázisponthoz (byte)	Előszámított tábla a nyilvános kulcshoz (byte)
ECP		112	378	1014	322	2028
EC2N	trinom.	113	374	1078	316	2156
ECP		128	416	1142	356	2284
EC2N	pentanom.	131	426	1206	364	2412
ECP		160	492	1398	422	2796
EC2N	pentanom.	163	492	1462	422	2924
ECP		192	564	1654	486	3308
EC2N	trinom.	193	542	1718	462	3436
ECP		224	638	1912	552	3824
EC2N	trinom.	233	620	2040	534	4080
EC2N	trinom.	239	624	2040	536	4080
ECP		256	708	2168	616	4336
EC2N	pentanom.	283	734	2424	634	4848
ECP		384	1004	3194	876	6388
EC2N	trinom.	409	978	3450	844	6900
ECP		521	1332	4380	1166	8760
EC2N	pentanom.	571	1326	4764	1148	9528

Közös kulcsméret (bit)	RSA összesen (byte)	ECC összesen (byte)	ECC összesen, PP-vel (byte)
ECC 113 = RSA 512	872-998	1452	3608
ECC 131 = RSA 768	1224-1422	1632	4044
ECC 160 = RSA 1024	1584-1844	1890	4686
ECC 283 = RSA 2048	3016-3532	3158	8006
ECC 409 = RSA 4096	5848-6870	4428	11328

Közös kulcs méret (bit)	RSA aláírás mérete (byte)	ECC aláírás mérete (byte)
ECC 113 = RSA 512	64	30
ECC 131 = RSA 768	96	34
ECC 160 = RSA 1024	128	42
ECC 283 = RSA 2048	256	72
ECC 409 = RSA 4096	512	102

Közös kulcs- méret (bit)	Kódolandó adat mérete (byte)	RSA-val kódolt adat mérete (byte)	ECC-vel kódolt adat mérete (byte)	Közös kulcs-méret (bit)	Kódolandó adat mérete (byte)	RSA-val kódolt adat mérete (byte)	ECC-vel kódolt adat mérete (byte)
ECC 113 = RSA 512	22	64	73	ECC 283 = RSA 2048	22	256	115
	54	-	105		54	256	147
	86	-	137		86	256	179
	214	-	265		214	256	307
	470	-	521		470	-	563
	512	-	563		512	-	605
	768	-	819		768	-	861
	1024	-	1075		1024	-	1117
	2048	-	2099		2048	-	2141
ECC 131 = RSA 768	22	96	77	ECC 409 = RSA 4096	22	512	147
	54	96	109		54	512	179
	86	-	146		86	512	211
	214	-	269		214	512	339
	470	-	525		470	512	595
	512	-	567		512	-	637
	768	-	823		768	-	893
	1024	-	1079		1024	-	1149
	2048	-	2103		2048	-	2173
ECC 160 = RSA 1024	22	128	83
	54	128	115
	86	128	147
	214	-	275
	470	-	531
	512	-	573
	768	-	826
	1024	-	1085
	2048	-	2109

Közös kulcsméret (bit)	Maximális kódolható adat RSA-nál (byte)	Az RSA-val kódolt adat mérete (byte)	Maximális kódolható adat ECC-nél (byte)	Az ECC-vel kódolt adat mérete (byte)
ECC 113 = RSA 512	22	64	4045	4096
ECC 131 = RSA 768	54	96	4041	4096
ECC 160 = RSA 1024	86	128	4035	4096
ECC 283 = RSA 2048	214	256	4003	4096
ECC 409 = RSA 4096	470	512	3971	4096