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ással
Tétel. Ha és két különböző prímszám és az , pozitív egészekre teljesül, akkor tetszőleges egész szám esetében igaz, hogy .
Bizonyítás. Az feltétel teljesülése konkrétan azt jelenti, hogy , ahol pozitív egész. Azaz . Mivel , ha nem osztható -vel, azért a fenti sorban a részbe 1-et írva a következő kongruenciát kapjuk: Az előbbi gondolatmenetet megismételve -ra: Ha tehát nem osztható egyidejűleg sem -vel, sem a tőle különböző -val, akkor osztható -vel és -val is, vagyis osztható -val is, tehát . Már csak azt kell megmutatni, hogy ha osztható -vel vagy -val, akkor is fennáll . Például esetén hatványozással . Tehát a bizonyítandó állítás minden 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 ( és ). Mivel az algoritmusban kulcsszerepet játszik az szorzat, a prímeknek kellően nagyoknak kell lenni ahhoz, hogy az szám prímtényezős felbontása ne legyen egyszerű (valós időben megoldható) feladat. (Általában és 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 ‐ értékéből kiindulva ‐ viszonylag egyszerűen meghatározható egy olyan , számpár, mely kielégíti az alaptételben említett feltételeket. Egy tetszőlegesen választott, de -hez relatív prím szám-hoz kell megkeresni modális inverzét . Mivel esetünkben , a inverz a kiterjesztett euklideszi algoritmussal könnyen meghatározható. Az egyedi , , számhármas előállítását hívjuk kulcsgenerálásnak. A kulcsgenerálás első lépése mindig az szám komponenseit alkotó prímek megkeresése, majd ennek függvényében az alkalmas , é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 , , számhármas ismeretében tetszőleges szám (message) átkódolható/titkosítható a (ciphertext) számba, illetve visszafejthető az eredeti -be az alábbi konvenciók betartásával: Nevezzük az számpárt nyilvános kulcsnak, a számpárt pedig privát kulcsnak (). Fontos, hogy a kommunikációban résztvevők mindegyike rendelkezzen saját kulcspárral, azaz egyedi , , 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) . A küldő a fogadó nyilvános kulcsával képezi a maradékot . A fogadó a saját privát kulcsával visszafejtheti -ből az eredeti -et szintén egy maradékképzéssel, mivel azaz . 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 üzenetre, azaz így képezzük a 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. és 1024 bites prím, akkor az szám 2048 bites, azaz 256 byte hosszúságú szám. A fentiek szerint ezzel csak max. 256 byte-os üzenet ‐ melyre 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ú modulusnál csak az 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 , , számhármasokon alapul, melyekből a és számok nyilvánosak. A titkosítás erősségét tehát az szorzat biztosítja, azaz olyan és 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 alakú számok (Mersenne-számok) között például vannak prímek, de pl. 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 prímre és tetszőleges alapra ‐ ha , azaz nem többszöröse -nak ‐ .
‐ | 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 ‐ de az feltételnek megfelelő ‐ páratlan számot (mely binárisan pl. 1000 bit hosszú). Természetesen összetettségéről még nem tudható semmi. |
‐ | Összetettségi vizsgálat. Megvizsgáljuk, hogy az egyenlőség teljesül-e. |
| Ha igaz, akkor -t pszeudóprímnek tekintjük és folytatás prímteszttel |
| Ha hamis, akkor csak összetett szám lehet, ezért és visszatérünk ennek a számnak az összetettségi vizsgálatára, ami vizsgálatával kezdődik. |
Megjegyezzük, hogy , illetve kiszámítására gyors algoritmusok vannak több száz jegyű számok esetére is. Az 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 szám, melyre igaz az feltétel. Az így talált számot ‐ mely egy konkrét alapra épül ‐ az 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-teszt) egy szám összetettségének eldöntéséhez ismételten a kis Fermat-tételt használja, de most az 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 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 . Egy tetszőleges szám, mely teljesíti az és feltételeket lehet Tanú vagy Cinkos.
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 cinkosa. |
‐ | 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étezik é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
A 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.Ez csak akkor teljesül, ha p és q első hexadecimális jegye ≥C, de ez könnyen biztosítható.A 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)Fermat-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.(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.Ez 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. |
|