A számítógépes titkosításban miért olyan fontosak a prímszámok? Hogyan működik egy prímszámokkal való titkosítás?

Nyílt kulcsú titkosításoknál kellenek (tehát amikor nem tudsz előre megegyezni egy közös titkos kulcsban a másikkal - pl. az interneten erre nincs lehetőség)

PL a legelterjedtebb RSA a prímfelbontás nehézségén alapul. ( [link]

A Diffie-Hellman titkos kulcscserénél is kellenek: [link]

Azért mert egy szám törzstényezőkre (prímekre) pontására jelenleg nincs algoritmus a próbálgatáson kívül. Viszont prímszámot generálni és nagyon nagy valószinűséggel prímszámhoz jutni nagyon könnyű.

Így az RSA alapszámát két prímből összeszorozni könnyű, szétszedni pedig lehetetlen véges időn belül.

A fentebb megadott linken le van írva az RSA menete, de nagyon meseszerűen leírva:

Minden résztvevő választ magának két nagy prímet (p és q), ezek alkotják az ő úgynevezett 'titkos kulcsát' (képzeld el úgy, hogy ez a jelszavuk). Ezt nem árulják el senkinek.

Amit viszont elárulnak, az a két prím szorzata n=p*q (meg egy másik számot is, de az most minket nem érdekel). Ez lesz az úgynevezett nyilvános kulcs, ezt közzéteszik, hogy mindenki láthassa - tehát erre gondolhatsz úgy, mint egy felhasználó név.

Az RSA-ban az eltitkosításhoz elég a nyilvános kulcs, viszont a titkosítás visszafejtéséhez már kell a titkos kulcs is.

Ez azt jelenti, hogy ha Bélának szeretnék küldeni egy titkos üzenetet, akkor megnézem Béla nyilvános kulcsát, annak segítségével eltitkosítom az üzenetet (és ezt viszonylag gyorsan meg tudom csinálni), és azt elküldöm Bélának. Ez egy olyan titkosított üzenet, amit csak úgy lehet visszafejteni, ha valaki ismeri Béla titkos kulcsát - tehát ideális esetben csak Béla tudja visszafejteni a kódolt üzenetet.

Ahhoz, hogy Csaba meg tudja fejteni a Bélának küldött titkos üzenetet, ahhoz Csabának ismernie kéne Béla titkos kulcsát, tehát fel kéne tudnia bontani az n = p*q számot prímtényezőkre.

Mivel a prímtényezőkre bontás nehéz feladat (nem ismerünk rá hatékony algoritmust), ezért Csaba kb. csak próbálkozni tud, az pedig lassú. Minél nagyobb az n=p*q szám, annál több próbálkozásra van szüksége. Ezért ha a Béla által választott prímek kellően nagyok, akkor egyszerűen annyira sok próbálkozást igényelne Csaba részéről a prímtényezőkre bontás, hogy az mondjuk 10 évbe telne a modern számítógépekkel. Annyit meg nem ér meg Csabának, hogy feltörje a Bélának küldött üzenetet - vagy ha igen, mert ez valami olyan hiper-szuper fontos üzenet, akkor Béla választhat még nagyobb p és q prímeket, és akkor 100 évig tartana.

1., az RSA menete az első válaszban adott linken le van írva. Annál jobban én se nagyon fogom tudni összefoglalni. A miértek megértéséhez kell majd némi számelméleti tudás, az nem tudom, hogy mennyire van neked meg.

2., Prímet tesztelni elég jól tudunk, és tényleg azt használjuk a prímek megtalálásához.

A probléma a prímtényezőkre bontással van: ott túl sok számot kéne tesztelni.

Tegyük fel, hogy van egy 500 bites számunk (ugye számítógép 2es számrendszerben számol), akkor az nagyságrendileg kb. 2^500, ami durván 1000^50 = 10^150 nagyságrend, ha a nekünk kényelmesebb tízes számrendszerben akarjuk nézni. Ráadásul most tegyük fel, hogy ez a szám két prímszám szorzata, tehát mindössze két valódi osztója van.

Tehát nekünk ennek a két számnak valamelyikét kéne megtalálnunk az 2,3,...,gyök(10^150) számok közül. Lényegében tűt keresünk a szénakazalban.

amit az előző írt, az inkább az, hogy hogyan keresik a rekord nagyságú prímszámokat - a jelenleg ismert legnagyobb prímszám 22,338,618 számjegyű. Ott tényleg szuperszámítógépeket alkalmazva keresik az új legnagyobbat, simán hónapokig futtatva a gépet. Általában ún. Mersenne-prímeket keresnek, ami azt jelenti, hogy a (2^p - 1) alakú számok között keresik a prímeket, ahol a p is prím.

A prímszámok tesztelése viszont nem úgy zajlik, hogy végig próbálják az összes lehetséges prímosztót, és ha nem találtak valódi osztója, akkor prím - ez irdatlan mennyiségű számolás lenne már csak egy darab ilyen méretű számnál is, ráadásul csomó ilyen számot kell jellemzően tesztelni, mire találnak egy újat (eddig 49 Mersenne-prímet ismerünk, a legnagyobb meg a 2^74,207,281, szóval látszik, hogy nem túl gyakoriak). Ennél vannak kifinomultabb prímtesztelési módszerek.

De ennek az egésznek nem sok köze van a hétköznapi titkosításhoz, hiszen ott messze nem használnak ekkora prímeket - nem is lehet, hiszen a hétköznapi embernek nincs otthon szuperszámítógépe, meg hónapjai arra, hogy elkódoljon valamit, szóval akkora prímeket kell használni, amiket még az otthoni gépekkel is lehet kezelni (nem vagyok képben, de amit néhány éve olvasgattam, az alapján akkor a 2048 bites prímek kezdtek elterjedni - aztán persze ez folyamatosan nő, hiszen a gépek számolási kapacitása is folyamatosan nő, ráadásul időnként találnak valami módszert, amivel a támadónak kevesebb lehetőséget kell végignéznie, ezáltal gyengül a titkosítás - ilyenkor is kénytelenek növelni a titkos kulcs méretét, ha azt szeretnék, hogy a biztonság ne csökkenjen).

Ilyen "polgári felhasználásra" meg lényegében úgy találnak prímeket, hogy azt mondják, hogy én ennyi számjegyű prímet szeretnék, és elkezdenek véletlenszerűen venni ekkora számokat (van egy előszűrés, hogy a kis prímekkel oszthatóakat eleve kiszórják). Ezeket aztán letesztelik, hogy prímek-e (erre van viszonylag hatékony módszer, nem kell minden osztót végignézni), és előbb-utóbb találnak egy megfelelő prímet. Itt azt használják ki, hogy N-ig nagyjából N/ln(N) prímszám van, szóval ha mondjuk 2024bites prímet keresünk, akkor várhatóan néhány ezer próbálkozásból találnak egyet.

Még egy dolgot tennék hozzá a korábbiakhoz:

amikor óriás prímeket keresnek szuperszámítógépeken, annak közvetlenül nem sok köze van a titkosításhoz - elvégre ezek akkora prímek, amikkel már alapból nem igazán lehet dolgozni, és ami még fontosabb: ezeket publikálják, szóval ha tudod, hogy valamelyik titkos kormányszervert egy ~22 millió bites prím segítségével titkosítottak, akkor nem túl nehéz rájönni, hogy na melyik lehet az, mert egy ilyet ismerünk, az meg mindenki számára megnézhető.

Az ilyen kutatásoknak az az értelme, hogy ahhoz, hogy még a korábbi óriási prímeknél is nagyobb prímet találj, ahhoz valószínűleg mindenféle új ötleteket kell használnod, amik a korábbi módszereknél gyorsabbá teszik a számolást vagy a prím-jelöltek tesztelését.

Szóval ha te találsz egy 22millió bites prímet a szuperszámítógéped 3 hónapnyi futtatása után (ha jól emlékszem, akkor a legutóbbi rekorderhez ennyi ideig futtatták a japánok az algoritmusukat), akkor abban jellemzően nem szimplán az a poén, hogy ez most egy milyen nagy prím, hanem hogy olyan új számolási módszereket fejlesztettél ki ennek a megtalálásához, amik láthatóan tényleg hatékonyabbak, mint a korábbiak.

És ezek már hasznosak lehetnek a titkosításoknál, vagy akár egyéb számolás-intenzív területeken.