Cím: Az RSA kulcsgenerálás és a Carmichael-számok kapcsolata 2.
Szerző(k):  Kiss Gábor 
Füzet: 2019/szeptember, 327 - 335. oldal  PDF  |  MathML 
Témakör(ök): Matematika, Számelmélet, Prímszámok

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

5. A kétkulcsos titkosítás alaptétele, kapcsolata a kétkulcsos titkosítással és az elektronikus aláírással1

 
Tétel. Ha p és q két különböző prímszám és az e, d pozitív egészekre ed≡1((modφ)(pq)) teljesül, akkor tetszőleges m egész szám esetében igaz, hogy med≡m(modpq).
 
Bizonyítás. Az ed≡1((modφ)(pq)) feltétel teljesülése konkrétan azt jelenti, hogy ed-1=k(p-1)(q-1), ahol k pozitív egész. Azaz med=mmed-1=mmk(p-1)(q-1)=m[m(p-1)]k(q-1).
Mivel m(p-1)≡1(modp), ha m nem osztható p-vel, azért a fenti sorban a [...] részbe 1-et írva a következő kongruenciát kapjuk:
med≡m(modp),ha(m,p)=1.
Az előbbi gondolatmenetet megismételve q-ra:
med≡m(modq),ha(m,q)=1.
Ha tehát m nem osztható egyidejűleg sem p-vel, sem a tőle különböző q-val, akkor med-m osztható p-vel és q-val is, vagyis med-m osztható pq-val is, tehát med≡m(modpq).
Már csak azt kell megmutatni, hogy ha m osztható p-vel vagy q-val, akkor is fennáll med≡m(modpq). Például m≡0(modp) esetén hatványozással med≡0ed≡0≡m(modp).
Tehát a bizonyítandó med≡m(modpq) állítás minden m egész szám esetében fennáll.
A fenti tétel alkalmazása a kétkulcsos titkosításra, illetve elektronikus aláírásra
Kiinduláshoz rendelkezni kell két darab prímszámmal (p és q). Mivel az algoritmusban kulcsszerepet játszik az N=pq szorzat, a prímeknek kellően nagyoknak kell lenni ahhoz, hogy az N szám prímtényezős felbontása ne legyen egyszerű (valós időben megoldható) feladat. (Általában p és q 500-2000 bites bináris szám).
Prímszámok kereséséhez, illetve a prímség bizonyításához alapvetően a Fermat-tételt használjuk, s ezért kiemelt jelentősége van a nagy számok (nagy hatványkitevők) hatványainak gyors kiszámolási algoritmusainak. (Az aritmetikai műveletek optimalizálásával itt nem foglalkozunk).
Prímek keresésével, illetve tesztelésével a ,,Tanúk'' és ,,Cinkosok'' részben foglalkozunk.
A kiterjesztett euklideszi algoritmussal ‐ N=pq értékéből kiindulva ‐ viszonylag egyszerűen meghatározható egy olyan e, d számpár, mely kielégíti az alaptételben említett feltételeket. Egy tetszőlegesen választott, de φ(N)-hez relatív prím e szám-hoz kell megkeresni e modális inverzét (modφ)(N). Mivel esetünkben φ(N)=(p-1)(q-1), a d inverz a kiterjesztett euklideszi algoritmussal könnyen meghatározható. Az egyedi e, d, N számhármas előállítását hívjuk kulcsgenerálásnak. A kulcsgenerálás első lépése mindig az N szám komponenseit alkotó prímek megkeresése, majd ennek függvényében az alkalmas e, d értékek kiszámolása. A kulcsgenerálást elvben mindenki ‐ aki titkosan akar kommunikálni ‐ elvégezheti saját számítógépes környezetében azzal a kulcsgeneráló programmal, mely az itt leírt elvek szerint dolgozik.
Az e, d, N számhármas ismeretében tetszőleges m<N szám (message) átkódolható/titkosítható a c<N (ciphertext) számba, illetve c visszafejthető az eredeti m-be az alábbi konvenciók betartásával:
Nevezzük az (e,N) számpárt nyilvános kulcsnak, a (d,N=pq) számpárt pedig privát kulcsnak (nyilvános+privát=kulcspár). Fontos, hogy a kommunikációban résztvevők mindegyike rendelkezzen saját kulcspárral, azaz egyedi e, d, N számhármassal. Az egymás között kommunikáló partnerek saját privát kulcsukat titokban tartják, a nyilvánosat pedig ‐ nevének megfelelően ‐ minden kommunikációs partner számára ismertté teszik.
Legyen a küldendő szám (üzenet) m. A küldő a fogadó nyilvános kulcsával képezi a c≡me(modN) maradékot (message→ciphertext). A fogadó a saját privát kulcsával visszafejtheti c-ből az eredeti m-et szintén egy maradékképzéssel, mivel cd≡med≡m(modN) azaz (ciphertxt→message). Tehát a kódolt (titkosított üzenetet) kizárólag a kiválasztott fogadó partner tudja megfejteni saját privát kulcsának felhasználásával.
Ha pedig mint küldő, előbb a saját privátkulcsunkat alkalmazzuk az m üzenetre, azaz így képezzük a c≡me(modN) maradékot, akkor csak a kapcsolódó nyilvános kulcs tudja visszafejteni az üzenetet, vagyis aki visszafejti a nyilvános kulccsal az üzenetet (ez bárki lehet, mert a nyilvános kulcs mindenkinek elérhető) az biztos lehet abban, hogy csak a megfelelő privátkulcs tulajdonosától jöhetett az üzenet (elektronikus aláírás).
Legyen pl. p és q 1024 bites prím, akkor az N=pq szám 2048 bites1, azaz 256 byte hosszúságú szám. A fentiek szerint ezzel csak max. 256 byte-os üzenet ‐ melyre m<N is teljesül! ‐ titkosítható. A gyakorlatban a hosszabb fájlokat blokkokra bontjuk, a titkosítás és visszafejtés is természetesen blokkonként fog történni.
Fontosnak tartom megemlíteni, hogy pl. a 256 byte hosszúságú N modulusnál csak az m<N számok esetében korrekt az algoritmus. A helyes visszafejtés érdekében a PLwSecur programban ezt úgy hidaltam át, hogy a titkosításhoz az eredeti fájlt 255 byte-os blokkokra (message-ekre) bontottam, majd a keletkező max. 256 byte-os ciphertext-et 256 byte-on tároltam. Visszafejtéskor a 256 byte-os maradékból ismét 255 byte-ra lett a message redukálva.
Megjegyezzük, hogy a szükséges számítások (hatványozások és maradékos osztások) időigényessége miatt azonban nem célszerű valamennyi blokkot a fenti módon titkosítani. A gyorsítás érdekében csak az első blokkot titkosítjuk, de ez célszerűen csak azt a szimmetrikus (pl. véletlenszám) jelszót tartalmazza, mellyel a későbbi blokkokat fogjuk titkosítani, illetve a fogadó fél is ezzel a jelszóval tudja a további blokkokat visszafejteni.
 
6. Prímek keresése, tesztelése (valószínűségi becslés),
,,Tanúk'' és ,,Cinkosok''

 

Az előzőekben megmutattuk, hogy a kétkulcsos titkosítás alapvetően az e, d, N számhármasokon alapul, melyekből a d és N számok nyilvánosak. A titkosítás erősségét tehát az N=pq szorzat biztosítja, azaz olyan p és q prímeket kell keresni, melyek elég nagyok ahhoz, hogy a nyilvánosságra hozott szorzatuk ne legyen könnyen faktorizálható (prímtényezőkre bontható). A gyakorlatban ehhez többszáz jegyű számokat kell használni.
Jelenleg nem ismert olyan (,,egyszerű'') képlet, amely eredményül prímszámokat adna. (A közismert 2n-1 alakú számok (Mersenne-számok) között például vannak prímek2, de pl. 211-1=2047=89⋅23 nem prím.
Nagy prímszámok kiválasztása próbálgatásokkal történik, majd különböző tesztekkel általában nagy valószínűséggel kijelenthető, hogy a próbálgatással talált ún. pszeudoprím szám valóban prímnek tekinthető-e.
Esetünkben a prímkereséshez a próbálgatás eszköze a kis Fermat-tétel, mely szerint minden p prímre és tetszőleges a alapra ‐ ha (a,p)=1, azaz p nem többszöröse a-nak ‐ ap-1≡1(modp).
‐Kiindulunk egy véletlenszerűen választott a alapból (célszerűen egy ismert prímszámból)
‐Majd választunk egy ugyancsak tetszőleges p ‐ de az (a,p)=1 feltételnek megfelelő ‐ páratlan számot (mely binárisan pl. 1000 bit hosszú). Természetesen p összetettségéről még nem tudható semmi.
‐Összetettségi vizsgálat. Megvizsgáljuk, hogy az ap-1≡1(modp) egyenlőség teljesül-e.
a)Ha ap-1≡1(modp) igaz, akkor p-t pszeudóprímnek tekintjük és folytatás prímteszttel
b)Ha ap-1≡1(modp) hamis, akkor p csak összetett szám lehet, ezért p:=p+2 és visszatérünk ennek a számnak az összetettségi vizsgálatára, ami (a,p)=1 vizsgálatával kezdődik.

Megjegyezzük, hogy (a,p)=1, illetve ap-1≡1(modp) kiszámítására gyors algoritmusok vannak több száz jegyű számok esetére is. Az (a,p) legnagyobb közös osztó meghatározásához az euklideszi algoritmust használjuk kiterjesztés nélkül.
A tapasztalat alapján 1-2 ezer bites számok esetében általában 1000 próbálkozáson belül mindig akad néhány olyan p szám, melyre igaz az ap-1≡1(modp) feltétel. Az így talált p számot ‐ mely egy konkrét a alapra épül ‐ az a alaphoz tartozó pszeudoprímnek nevezzük.
Annak eldöntéséhez, hogy egy pszeudoprím valóban prím-e (további) prímtesztet kell alkalmazni. A legbiztosabb megoldás a prímtényezős felbontás lenne, de ez gyakorlatilag ‐ időigénye miatt ‐ végrehajthatatlan.
Az alább ismertetett eljárás (Fermat-teszt3) egy p szám összetettségének eldöntéséhez ismételten a kis Fermat-tételt használja, de most az a alapokat váltogatjuk. Mint látni fogjuk, a valódi prímség megállapítására az eljárás elvileg nem alkalmas, mert léteznek olyan összetett számok, melyek minden (a,p)=1 a alapra ‐ azaz univerzálisan ‐ pszeudoprímnek bizonyulnak (Carmichael-számok).
Dolgozatunk fő célja annak megmutatása, hogy a Fermat-teszt mégis igen hasznos az RSA kulcsgenerálás szempontjából, mert a később ismertetendő CA-tétel miatt a valódi prímeken kívül a prímteszt ,,gyilkosainak'' tekintett Carmichael-számok is ‐ könnyen teljesíthető szűrési feltétellel ‐ felhasználhatók RSA kulcspárok generálásához.
A Fermat-teszt leírásához szükségünk van a következő fogalmakra: A tesztelendő szám legyen p. Egy tetszőleges a szám, mely teljesíti az (a,p)=1 és a<p feltételeket lehet Tanú vagy Cinkos.

Tanú:Ha  ap-1≢1(modp), akkor az a szám TANÚ arra, hogy  p  összetettszám.Cinkos:Ha  ap-1≡1(modp), akkor az a szám CINKOS  p  prímségéhez,ugyanis ebből még nem következik  p  prímsége, de lehet prím is.  


p tanúinak száma legyen T, p cinkosainak száma pedig C, nyilvánvaló, hogy T+C=φ(p).
Nyilván igazak a következők:
‐Tetszőleges p szám esetén 1 és p-1 relatív prím p-hez, továbbá mindkettő p cinkosa4.
‐Ha p prím, akkor minden a<p szám ‐ Euler tétele miatt - cinkos, azaz T=0 és C=φ(p). (A prímek mellett az összetett Carmichael-számokra is T=0).
‐Ha T>0 (azaz p-nek van tanúja), akkor p csak összetett lehet.

Most pedig megmutatjuk, hogy ha egy p számra T>0, akkor T≥C is igaz, azaz ha egy p számnak van tanúja, akkor a p-hez relatív prím, φ(p) darab szám legfeljebb fele lehet cinkos.
Legyen t a p szám tanúja, c pedig egyik cinkosa (cinkos mindig van!) Vegyük észre, hogy ha c a p-nek cinkosa, akkor tc(modp) tanú. ((tc)p-1=tp-1cp-1≡tp-1≠1(modp) miatt.) Továbbá, ha c1 és c2 ap-nek két különböző cinkosa, akkor a belőlük származtatott tc1 és tc2 tanúk is különbözők. Ez indirekt úton látható be, ugyanis ha tc1≡tc2(modp) lenne, akkor tc1-tc2=t(c1-c2) osztható lenne p-vel. Mivel (t,p)=1, ezért csak c1-c2 osztható p-vel, ami lehetetlen 0<|c1-c2|<p miatt. Tehát a cinkosokból származtatható tanúk miatt T≥C lehet csak.
Ha T>0, illetve következményként T≥C, akkor a T+C darab p-hez relatív prím (és p-nél kisebb) számok között a cinkosok előfordulási valószínűsége CT+C≤C2C=12, azaz legfeljebb 12.
E gondolatot folytatva, válasszunk véletlenszerűen pl. 100 db p-nél kisebb és p-hez relatív prím a számot ‐ és ezek mindegyikére végezzük el az ap-1≡1?(modp) vizsgálatot, azonban ügyelve arra, hogy az első tanú felbukkanása után a vizsgálatot rögtön megszakítsuk és próbálkozzunk egy másik p-vel. Ha a p szám kiállta az előbbi próbát, elvben két eset lehetséges:
‐p-nek nincs tanúja, azaz T=0. Ebben az esetben p-nek csak cinkosai vannak, ezért ha p-t univerzális pszeudóprímnek tekintjük, garantáltan nem tévedünk.
‐p-nek van tanúja, azaz T>0. Ebben az esetben annak a valószínűsége, hogy a 100 vizsgált a szám mindegyike cinkos legyen kisebb, mint (12)100≈10-30.
Ha tehát ezek után p-t univerzális pszeudóprímnek tekintjük, a tévedés valószínűsége kisebb, mint (12)100≈10-30.

(Az előbbi gondolatmenetben említett univerzális pszeudoprímek lehetnek valódi prímek is, de megbújhatnak köztük összetett számok is.)
1910-ben Carmichael találta meg az első olyan összett számot (561), melyre T=0 és C=φ(561). A TanúCinkos-kereső programmal azonban számos olyan olyan p összetett számot találhatunk, melyekre T=0 és C=φ(p). Tehát hiába minősül minden vizsgált, p-hez relatív prím cinkosnak, p mégis lehet összetett. Ezeket a p összetett számokat nevezzük univerzális pszeudóprímeknek, vagy Carmichael-számoknak.
 
7. Carmichael-számok definíciója és tulajdonságai

Definíció. Azokat az N összetett számokat, melyekre minden (a,N)=1 feltételt kielégítő a alap esetén aN-1≡1(modN) teljesül, Carmichael-számoknak nevezzük.
Ilyen számok léteznek, a TanúCinkos-kereső program használatával bizonyíthatóan 43 darab ilyen szám van 1 millió alatt (lásd a számok listáját ‐ a lista előállításának időigénye néhány perc volt). 1994 óta azt is tudhatjuk, hogy végtelen sok Carmichael-szám létezik.
Csak az arányok érzékeltetéséhez megjegyezzük, hogy az 1 milliónál kisebb prímszámok (1‐999983) darabszáma 78498. Ehhez jön még 43 db Carmichael-szám, azaz összesen 78 541 db szám esetében a Fermat-teszt mindig ,,prímet'' vélelmez. Az 1 millió alatti prímtesztek tévedési aránya tehát 43/78541≈5,5⋅10-4.
Korselt már 1899-ben kritériumot fogalmazott meg a Carmichael-számokra, bár még nem ismert egyet sem. Eszerint az N szám akkor és csak akkor Carmichael-féle, ha négyzetmentes, és N mindegyik p prímosztójára igaz, hogy p-1∣N-1 (azaz p-1 osztja (N-1)-et).
Az alábbi tételek egy Carmichael-szám jellemző tulajdonságait mondják ki:
‐N prímtényezős felbontásában a 2-nél nagyobb prímtényezők 1-es kitevővel szerepelhetnek.
‐Ha p az N egyik prímtényezője, akkor p-1∣N-1 (azaz p-1 osztja (N-1)-et).
‐Az N szám nem lehet páros.
‐Az N szám nem lehet két páratlan prímszám szorzata.

Bebizonyítjuk továbbá:
‐ha az N szám különböző páratlan prímek szorzata, és minden prímtényezőjére teljesül, hogy p-1∣N-1, akkor N Carmichael-szám.

A továbbiakban N legyen definíció szerinti Carmichael-szám.
 
1. tétel. N prímtényezős felbontásában a 2-nél nagyobb prímtényezők 1-es kitevővel szerepelhetnek.
 

Indirekt módon tegyük fel, hogy N=pkm alakú, ahol p páratlan prím, k≥2 és (m,pk)=1. Legyen g>1 primitív gyök (modp)k (p=2 esetén ez nem lenne garantálható). Tekintsük az X≡g(modpk) és X≡1(modm) kongruenciarendszert. Mivel (m,pk)=1, azért X létezik5 és (X,N)=1 is igaz. Ez utóbbi belátásához vegyük észre, hogy az első kongruencia fennállása miatt (X,pk)=1, a második kongruencia fennállása miatt ‐ kihasználva A rend és a primitív gyök fogalma részben említett észrevételünket, miszerint ha a≡b(modm), akkor (a,m)=(b,m)-(X,m)=(1,m)=1, tehát (X,N)=(X,pkm)=1 is igaz.
Az X teljesíti a következőket: A Carmichael-szám definíciója miatt XN-1≡1(modN) ‐ ugyanis (X,N)=1, ezért φ(pk)∣N-1. Itt azonban ellentmondásra jutunk, ugyanis k≥2 esetén p∣φ(pk)=pk-1(p-1)∣N-1, de ez lehetetlen, mert p egyidejűleg nem lehet osztója (N-1)-nek és N-nek is.
 
2. tétel. Ha p az N egyik prímtényezője, akkor p-1∣N-1.
 

A p=2 esetében az állítás triviálisan teljesül ‐ bár, mint később látni fogjuk, N nem lehet páros szám. Így az egyik páratlan p prímet kiválasztva feltételezhetjük, hogy N=pm alakú, ahol (m,p)=1. Legyen g primitív gyök (modp). Tekintsük az X≡g(modp) és X≡1(modm) kongruenciarendszert. Mivel (m,p)=1, létezik ilyen X, és (X,N)=1.
A Carmichael-szám definíciója miatt XN-1≡1(modN), így nyilván XN-1≡1(modp), ezért p-1=φ(p)=op(X)∣N-1.
 
3. tétel. Az N szám nem lehet páros.
 

Legyen N egyik páratlan prímosztója p, ekkor a 2. tétel szerint p-1∣N-1. Itt p-1 páros, így N-1 is páros, tehát N páratlan.
 
4. tétel. Az N szám nem lehet két páratlan prímszám szorzata.
 

Indirekt módon tegyük fel, hogy N=pq alakú. Mivel p-1∣N-1 fennáll, azért
pq-1p-1=pq-q+q-1p-1=q+q-1p-1
is egész, tehát q-1p-1 is egész szám. A q-1∣N-1 fennállásából pedig belátható, hogy p-1q-1 is egész. A reciprokok csak akkor lehetnek egészek, ha mindkettő értéke 1, azaz p=q. A p=q eset azonban az 1. tétel miatt nem lehetséges, tehát az N szám nem lehet két tényezős.
A továbbiakban N legyen különböző páratlan prímek szorzata, és minden p prímtényezőjére p-1∣N-1.
 
5. tétel. Ha N eleget tesz a fenti feltételeknek, akkor N Carmichael-szám.
Bármelyik p prímtényezőre k=N-1p-1 egész szám. Ha (a,N)=1, akkor erre az a alapra a kis Fermat-tétel szerint aN-1≡ak(p-1)≡1(modp). Mivel ez a kongruencia mindegyik p prímtényezőre fennáll, azért a modulusok szorzatára is, így aN-1≡1(modN) is igaz.
 
8. A kétkulcsos titkosítás alaptételének egy fontos általánosítása (CA-tétel)

Az eredeti ‐ korábban bebizonyított állítás ‐ a következő: Ha p és q két különböző prímszám, és az e, d pozitív egészekre ed≡1(modφ)(pq) teljesül, akkor tetszőleges m egész számra med≡m(modpq).
Az általánosítás a következő:
Legyen N négyzetmentes szám ‐ azaz egymástól különböző ‐ p1,p2,...,pn prímek szorzata. Ha az e, d pozitív egészekre teljesül az ed≡1((modφ)(N)) feltétel, akkor tetszőleges m egész számra med≡m(modN)).
 
Bizonyítás. Ugyanaz, mint két prím szorzatának az esetében.
 

Ennek az általánosításnak az a jelentősége, hogy a kulcsgeneráláshoz felhasználhatjuk a Fermat-tesztet kiállt valamennyi számot, függetlenül attól, hogy az valódi prím vagy összetett Carmichael-szám. Az N szorzat négyzetmentességének biztosításához elegendő a felhasznált számok páronkénti relatív prímsége, ami könnyen biztosítható.
Eddig még nem vizsgáltuk, hogy az ed≡1(modφ)(N) feltétel hogyan teljesíthető. Itt φ(N)=(p1-1)(p2-1)...(pn-1). A kiterjesztett euklideszi algoritmussal ‐ indulásként például egy kisebb prímet választva e értékének ‐ igen gyorsan meghatározható d értéke ‐ ha létezik megoldás. Ha nincs megoldás, akkor egy másik prím értéket választhatunk stb.
 

 
9. Kulcspárgenerálás összetett számokból

 
A CA-tétel egyik fontos következménye, hogy az RSA kulcspárok generálását prímek mellett speciális összetett számokkal is meg lehet csinálni, mégpedig pont azokkal, melyek a Fermat-teszt prímvizsgálatát ,,meggyilkolták''.
A PLwSecur (v2.2) változatában 256 bites, illetve 512 bites prímeket használunk, nevezetesen
‐az 512 bites kulcspár 2 db 256 bites prím szorzatából,
‐a 768 bites kulcspár egy 256 bites és egy 512 bites prím szorzatából,
‐az 1024 bites kulcspár 2 db 512 bites prím szorzatából

van generálva.
Bár a program jelenlegi változata max. 2048 bites kulcspárokat is tud kezelni, az alkalmazott programtechnika (Delphi kód, de nincsenek beágyazott assembler gyorsítások) nem alkalmas hosszabb kulcspárok generálására észszerű időn belül.
A CA-tétel alapján azonban lehetőség nyílik 1536, 2048 bithosszúságú kulcsok generálására 512 bites prímek felhasználásával. A kulcsgenerálás folyamata a következő lehet:
1.A végcéltől függően generálni kell pl. 3-4 darab 512 bites prímet. Ezeket előbb szigorú prímtesztnek kell alávetni (pl. 100 erősségű Fermat-teszt). Mivel ez valószínűségi teszt, ezért a valódi prímeken kívül ‐ nagy valószínűséggel ‐ csak az összetett Carmichael-számok bizonyulhatnak ,,prímnek''. (A Prímek keresése, tesztelése részben megmutattuk, hogy 100 darab sikeres ,,cinkostalálat'' után annak valószínűsége, hogy p ne univerzális pszeudóprím legyen kisebb, mint (12)100≈10-30.)
2.Az így talált számokat ‐ beleértve az esetleges Carmichael számokat is ‐ jelöljük c1,c2,...,cn-nel. A CA-tétel miatt kulcsgeneráláshoz csak akkor használhatók, ha szorzatuk négyzetmentes. Ehhez elegendő azt biztosítani, hogy a számok páronként relatív prímek legyenek. Ha valamelyiknél sérül a relatív prímség, akkor helyette másik számot kell generálni az előző pont szerint.
3.A fenti előkészítések után az N=c1c2...cn szorzat értéke mellé meg kell határozni Q=(c1-1)(c2-1)...(cn-1) értékét is, majd az ed≡1(modQ) egyenletnek eleget tevő e, d, N hármasból képezhető a kulcspár. Vegyük észre, hogy a ci számok prímtényezős felbontásában szereplő valamennyi pj prímre fennáll, hogy pj-1∣ci-1. Ezért a CA tétel bizonyításakor az ed≡1(modQ) feltétel is elegendő.

Természetesen tisztában kell lenni azzal, hogy pl. 4 darab 512 bites számból származtatott 2048 bites kulcspár kevésbé biztonságos (elméletileg könnyebben faktorizálható), mint ha ugyanezt 2 darab 1024 bites számból származtattuk volna. Ugyanakkor a kulcsgenerálás időigénye nagyságrendekkel rövidebb lesz. A kulcspár használatakor az encryt/decrypt időigényét az e, N (nyilvános), illetve d, N (privát) számpárok mérete határozza meg, ami már teljesen független az e, d, N számok előállításának módjától, azaz itt a futási időben változás nem várható.
Megjegyzendő végül, hogy ha a prímtesztelésnél a nagyon nagy valószínűséggel helyes eredmény helyett a biztosan jó válaszhoz ragaszkodunk, akkor immár ez az igény is kielégíthető ‐ az algoritmus bonyolultságának növekedése árán. Mindezt Agrawal, Kayal és Saxena 2002-ben publikált eredménye biztosítja.
 
1 millió alatti Carmichael-számok (43 db)
 

HexDecPrímfelbontásHexDecPrímfelbontás   231  5613⋅11⋅17  3DAB9  252 60141⋅61⋅101   451  11055⋅13⋅17  44011  278 5455⋅17⋅29⋅113   6C1  17297⋅13⋅19  47E09  294 40937⋅73⋅109   9A1  24655⋅17⋅29  4CDC5  314 82113⋅61⋅397   B05  28217⋅13⋅31  51949  334 15319⋅43⋅409   19C9  66017⋅23⋅41  53251  340 56113⋅17⋅23⋅67   22CF  89117⋅19⋅67  61699  399 00131⋅61⋅211   2959  10 5855⋅29⋅73  641B9  410 04141⋅73⋅137   3DE1  15 8417⋅31⋅73  6DA29  449 0655⋅19⋅29⋅163   729D  29 34113⋅37⋅61  775B1  488 88137⋅73⋅181   A051  41 0417⋅11⋅13⋅41  7D1CD  512 46131⋅61⋅271   B641  46 65713⋅37⋅97  819C1  530 88113⋅97⋅421   CD99  52 6337⋅73⋅103  86F11  552 72113⋅17⋅41⋅61   F519  62 7453⋅5⋅47⋅89  A04D9  656 6013⋅11⋅101⋅197   F9E5  63 9737⋅13⋅19⋅37  A0D71  658 80111⋅13⋅17⋅271   12661  75 36111⋅13⋅17⋅31  A3951  670 0337⋅13⋅37⋅199   18AED  101 1017⋅11⋅13⋅101  B6C71  748 6577⋅13⋅19⋅433   1C4D1  115 92113⋅37⋅241  C97B1  825 2655⋅7⋅17⋅19⋅73   1ED09  126 2177⋅13⋅19⋅73  CCA39  838 2017⋅13⋅61⋅151   27A61  162 40117⋅41⋅233  D0369  852 84111⋅31⋅41⋅61   2A031  172 0817⋅13⋅31⋅61  F3901  997 6337⋅13⋅19⋅577   2E02D  188 4617⋅13⋅19⋅109   
1A cikk első része 2019. májusi számunkban jelent meg és honlapunkon is olvasható: https://www.komal.hu/cikkek/Kiss_Gabor-Az_RSA_kulcsgeneralas_es_a_ Carmichael-szamok_kapcsolata_1.pdf.

1Ez csak akkor teljesül, ha p és q első hexadecimális jegye ≥C, de ez könnyen biztosítható.

2A gyakoriság 1 ezrelék alatti. 2016. január 7-én fedezték fel a a 49-ik Mersenne-prímet, ez a 274207281-1 szám, és 22 338 618 számjegyből áll. Jelenleg ez a legnagyobb ismert prímszám. (Wikipédia)

3Fermat-prímteszt helyett következetesen Fermat-tesztet használunk, mert a teszt eredménye a prímek mellett összetett számokat is prímnek vélelmez.

4(p-1)≡-1(p), mindkét oldalt felemelve a (p-1)-edik (ez páros!) hatványra belátható, hogy p-1 cinkosa p-nek.

5Ez következik abból, hogy az ax+by=1 diofantoszi egyenletnek csak akkor van megoldása, ha (a,b)=1, továbbá ekkor az ax+by=c diofantoszi egyenletnek is van megoldása.