Az RSA titkosításnál az n, d, e ismeretében hogy számítható ki p és q?
válasza:100-135 sorok között, kommentekkel.
Köszönöm a válaszodat hasznos volt és világos.
Ami viszont nem világos, hogy látom hogy van ez az u 139-sor. obj.u = inverse(obj.p, obj.q). Azaz a q maradékosztályon p multiplikatív inverze. Erre mi szükség van?
válasza:Köszönöm.
A kódba meg itt van felhasználva : [link]
Szemmel láthatóan lassabbnak tűnik mivel több moduláris hatványozás művelet előzi meg, szemben ha csak pow(c, self.d, self.n) lenne. Viszont utána számolva valóban kevesebb a műveletigénye. Viszont akkor már következetes lenne self.d % (self.p-1) és self.d % (self.q-1) értékét is letárolni és nem mindig újra kiszámolni, hiszen p,q,d nem változik adott kulcs esetén.
válasza:Na ja, de ez a lényeg, hogy olcsóbb csinálni két kis gyors hatványozást, mint egy nagyot.
d % (p-1) és d % (q-1)-et azért nem tárolja, mert az egy szinte nulla műveletigényű kis semmi, annyira eltörpül a többi művelet mellett, hogy bűn lenne a tárolásával piszkítani a kódot.
válasza:Számomra a kvantumszámítógépek elve teljes homály, egyszer le kéne ülnöm hogy legalább nagy vonalakban felfogjam. Mindenesetre ha van egy csodamódszer, ami n^2 alatt feltöri, és te ebből egymás után raksz m darabot, akkor ha van visszajelzésem, hogy sikeres volt-e egy adott kör, akkor m*n^2 a komplexitás, ez tiszta.
Te azt mondod, hogy ha nem raksz ellenőrző hasht a közbenső szintekre, csak a végére, akkor nem bontható le a feladat m darab n^2-es problémára, hanem végig kell menni a kulcsok teljes m*n bites terén. Ez esetben (mn)^2 a komplexitás, ami persze nehezebb mint az m*n^2, de még mindig csak kvadratikus. Azaz pont ugyanolyan, mintha egy körös lenne a titkosításod egy m-szer hosszabb kulccsal. Nincs minőségi különbség.
Köszi a választ. Végül is erre gondoltam én is csak előre nem akartam befolyásolni senkit, ez egy ellenőrzés volt részemről a részemre.
NP nehéz feladat a prímfaktorizáció, úgy sejtjük hogy nincs is olyan algoritmus mely polinom időben felbontaná (hiszen akkor bebizonyosodna hogy P = NP, amire egyetlen ellenpéldát se találtunk semmilyen NP teljes probléma esetében), kivéve kvantum algoritmust, de ez nem kvantumszámítógépen exponenciális idejű lenne. Azt se tudjuk hogy létezhet e ilyen gép ami elég kvantumbites hozzá. Ha igen akkor többé nem biztonságos az RSA.
Mondjuk azt tegyük hozzá , hogy bizonyos feltételeknek eleget kell tenni hogy ne lehessen feltörni pl a 2 prímszám ne legyen túl közel egymáshoz, kriptográfiailag erős legyen a random generátor, az e megválasztása se akármi lehet azon belül se amit a szabály megengedne, pl ha nincs elég távol egymáshoz a d meg az e akkor is törhető legyen elég nagy a p és q stb. Sőt ezeken felül elég találékonyak a támadók, az áramfogyasztás ingadozásának pontos mérésével is kitalálható a kulcs vagy a gép által keltett elektromágneses hatások mérésével is állítólag.
Érdekes amúgy hogy a bankok is 2048 bites kulcs minimum követelményt teljesítik, alig találni olyan oldalt ahol nagyobb kulccsal dologoznak. Igaz hogy a rekord ( [link] 768 bites RSA megtörése mely 2 évig tartott az akkori gépekkel külön saját algoritmussal hozzá és minden további 100 bit növelésével 40x-esére növeli a futási időt ha jól tudom. Így is tekintélyes idő mire elérné azzal a módszerrel a 2048 bitet úgy is hogy figyelembe veszem a számítási teljesítmény növekedésének exponenciális rátáját.
"további 100 bit növelésével 40x-esére növeli a futási időt ha jól tudom"
Nem jól tudtam, ha igaz lenne nem ez lenne a rekord.
Kapcsolódó kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!