Ha összeszorzok két nagyobb prímszámot és így kapok egy két tényezőből álló összetett számot, azt miért olyan nehéz felbontani egy számítógépnek a két prímre?

Amennyire tudom, olyan 400 jegyű prímszámok szorzatával dolgoznak. Azt azért nem olyan egyszerű kezelni. Nagyon finoman szólva. Főleg, hogy exponenciálisan "bonyolódik" a dolog a számok növelésével Legalábbis, ha klasszikus (fizikai) elven működő (szuper)számítógéppel próbálja valaki.

Azonban, ha egyszer valóban sikerül hatékonyan kiküszöbölni a kvantumbitek esetében a dekoherenciát és megoldani a felskálázást akkor egy kvantumszámítógépnek, amin a Shor - féle algoritmus fut nagyon, nagyon rövid idő is elég lesz a faktorizáláshoz.

Az RSA titkosításban a gyakorlatban általában 512, 1024, 2048 bites számokat (kb. 150, 300, 600 számjegyű!) használnak.

Ezt kellene két kb. egyforma hosszú prím szorzatára felbontani a feltöréshez, - ami jelenleg lehetetlenül sok időbe kerülne.

"Az RSA titkosításban a gyakorlatban általában 512, 1024, 2048 bites számokat (kb. 150, 300, 600 számjegyű!) használnak."

2048 bit a minimális követelmény jelenleg, legalábbis a TLS biztonsági protokolban RSA esetében. 1024 bit nem ajánlott, de tudtom szerint nem volt még rá törés 1024 bites-re sem, de biztonsági okokból 2048 bites a minimális követlemény, ami háromszáz valamennyi jegyű prímek, a szorzatuk hatszáz valamennyi jegyű tízes számrendszerben.

Viszont, ha tudsz érvényes TLS tanúsítvánnyal rendelkező RSA algoritmust használó website-ot ami kevesebb mint 2048 bites akkor megnevezve az oldalt szólj! Nagyon gyakran pont 2048 bites szokott lenni.

Pythonban a Crypto.PublicKey.RSA modulban a kulcsgenerátor ValueError-t dob "RSA modulus length must be >= 1024" üzenettel, ha 1024-nél kevesebb bites kulcsot generáltatnék vele.

2048 biteset generáltattam vele, p és q szorzata : 21386546486451042397628658125601427131469729645495753742890707328427654651409065970532135065765377347226197647538641107758768779192259906435938458064251385096118527137103385852561417469341574011641334873862546145570941377945638829210903512302749160979022366689205554428074083668269838117832268651834527820107200361017469321403217868354547050526920372582370062951539472533784495941133407550481332228611977200686201179828254757585626514330550437606501051435143246548738934009479610638050648241941925751598083345615187096759122412858580615693854011662254658703826806384028467549276116496404255542878638738111123536501931

Tessék kérdező bontsd fel! A kulcsot eldobtam, így nem tudom én se a megoldást, de egy adott megoldásjelöltről meg tudom mondani könnyedén hogy jó megoldás e.

Ha annyira megy akkor brahiból megoldhatod, de én nem fizetek érte. De ezek esetében még fizetnek is : [link]

Egy hivatalos leírás: [link]

Ha bits a kulcs ahány bites kötelező feltétel : 2^(bits-1) < p*q < 2^bits.

A p és q nem lehet túl közel egymáshoz, mert akkor elég lenne a négyzetgyöke körül keresni, a távolság nem lehet kevesebb mint 2^(egészrésze(bits/2) - 100).

A p és q nem lehet túl messze sem egymástól, hiszen az nehezítés ,hogy nem lehet kicsi a kettő közül az egyik. Így 2048 bites esetben 2^1024-nél nem lehet kisebb p és q egyike sem.

Az e az expontens nagyon gyakran 65537. Követelmény hogy gcd(p-1,e)=1 és gcd(q-1,e)=1 azaz p-1,e és q-1,e számpárok relatív prímek legyenek egymáshoz.

Ugye az RSA-titkosítás megy rá erre. Ugye arról van szó, hogy mikor egy titkosítási eljárás hatékonyságát elemezzük, akkor tulajdonképpen feltesszük azt, hogy

1) Az ellenség ismeri a titkosítási eljárásomat.

2) Az ellenség mindent is le tud hallgatni.

Ezért aztán azok a titkosítási eljárások jók, ahol a kulcstér nagy, és legalább látszólag reménytelen annak érdemi szűkítése.

Tehát tegyük fel, hogy F feladó akar egy h hírt eljuttatni a C címzetthez. Ezt a h hírt akarjuk valami R rejtjelező eljárással R(h) rejtjelezett szöveggé alakítani. Ha a C címzett ismeri az M kulcsot, hogy annak ismeretében könnyen visszafejtheti az M(R(h))=h szöveget. A cél olyan titkosítást találni, hogy R ismeretében is reménytelen legyen az M kulcs kitalálása. Most egy picit absztraktabbul fogalmaztuk meg azt az elvárást, hogy egy ellenőrizhetetlenül nagy kulcsteret akarunk konstruálni. Bocsánat, kulcstérnek nevezzük az összes kulcsok halmazát.

És erre szolgáltat egy lehetséges módszert az RSA-eljárás, ami az Euler-Fermat-tételen alapszik.

Válasszunk egy N félprímet, azaz olyan N számot, amely két prímszám, p és q szorzatára bomlik. Ezt a számot N-nél kisebb részekre bontjuk, az egyik ilyen rész mondjuk legyen h.

Választunk két olyan egészt, mondjuk r-et és m-et úgy, hogy

rm≡1 ( mod φ(N)).

Ez pontosan azt jelenti, hogy valamely k egészre:

rm=1+kφ(N), valamint N választása miatt φ(N)=(p-1)(q-1)

És azt mondjuk, hogy akkor legyen C rejtjelező kulcsa:

R(h) h^r legkisebb nemnegatív maradéka modulo N.

Ha az így kapott rejtjelezett szöveg h', akkor hasonlóan,

M(h') h'^r legkisebb nemnegatív maradéka modulo N.

Azt kell tehát először látnunk, hogy az R rejtjelező kulcsra, illetve az M megfejtő kulcsra: M(R(h))=h és R(M(h))=h (itt vegyük észre, hogy fentebb R és M szerepe szimmetrikus, M is használható rejtjelezésre)

A fenti jelölések mellett

M(h')=M(R(h))≡h^rm=h^(1+kφ(N))=h*h^kφ(N)

De az Euler-Fermat-tétel miatt h^kφ(N) 1-gyel kongruens modulo N, ezért

M(h')=h.

Ez még igényel némi további diszkussziót, de a lényeg ez.

Azt állítom, hogy N és r nyilvánosságra hozható. Ha ugyanis vissza akarjuk fejteni a kódot, akkor ki kell számolnunk a p,q prímeket, illetve a fenti m számot kell még euklideszi algoritmussal meghatározni az első kongruenciából. És itt kezdődik a probléma. Olyan kis számoknál, mint amiket te is írsz, ez még smafu. De (jelenleg) 2^1024 bites nagyságrendű számokról van legalább szó. Ez bitangnagy. Ezek legalább ~10^308 nagyságrendű számok, és ilyeneket szorzunk. Az még a kisebbik gond, hogy nem ismerjük a túl nagy prímeket, mert akár vehetjük az összes egészt is sqrt(N)-ig, akkor tuti megtaláljuk, p-t és q-t. Viszont akkor képbe jön a számítási kapacitás. Ha van egy ~10^308 nagyságrendű számunk, akkor minden megszorítás nélkül, ha csak azt nézem, hogy sqrt(N)-ig ellenőrizzük az összes számot, akkor az ~10^105 nagyságrendnyi osztást jelent. A ma elérhető szuperszámítógépek tudnak néhány petaflopot, számoljunk nagyon optimistán 10 petafloppal, azaz 10^16 osztás/ másodperccel A nagyságrendben 10^105 osztás 10^89 másodpercig tart, ez még mindig nemhogy több, nagyságrendekkel több, mint az Univerzum életkora.

Remélem, így sikerült érzékelni, miről van szó.