Ha létezne erős kvantumszámítógép akkor az RSA feltörése ordó n^2 futási idejű lenne ha n bit a kulcs hossza. Ha viszont egymásba skatulyázunk többszörös titkosítást több RSA kulccsal akkor hogy nőne kvantumszámítógépen a futási idő?

Köszönöm a választ. Azonban ezt eddig is tudtam amit ott írtak, azonban a lényeget szőnyeg alá söpörték. Erről is írtam a kérdésben a kiegészítő részben.

Azért hogy ne lehessen brute force-olni semmi esetre se PKCS-t használnak ( [link] )

A lényege leegyszerűsítve annyi hogy az üzenethez raknak randomot is majd a randommal együtti üzenethez hozzáfűzik annak hash-ét és ezt titkosítják RSA-val. Dekódolásnál meg a dekódolt hash érték alapján valid-álja hogy valóban sikeres e a dekódolás nem e másik titkosító kulcs tartozik hozzá vagy valami teljesen más adat. Ha ez a hash nem lenne beépítve akkor én úgy dekódolok neked bármit, de hogy köze nem lesz az elvárt dekódolt értékhez az biztos. (Jó mondjuk tudom hogy jelzőbájtok is vannak, de ezt egyszerűség kedvéért hagytam ki.)

Én meg pont azt magyaráztam hogy a PKCS-t csak a legalsó szintre raknám be, hogy maximális bizonytalanságba tartsam hogy az első szintet sikerült e feltörnie.

Ha csak pl az OpenPGP-vel titkosítanám duplán két kulccsal akkor TRIVIÁLIS, hogy aszimptotikusan nem lenne erősebb. Épp ezért csinálnám okosabban ahogy már kifejtettem.

Az hogy ez amit állítok hogy ez sokkal erősebb így úgy lehetne cáfolni, ha azt bizonyítod hogy az első szintű kulcs feltörése esetén van hatékony algoritmus mely eldönti hogy első szinten fel van törve és ezt kell próbálgatni tovább a második szinten. Gyakorlatilag statisztikailag teljesen randommal megegyező statisztikailag ha feltörte első szinten vagy ha nem. Nem tudja megállapítani hatékony algoritmussal az első szinten lévő feltörés tényét, nincs semmi támpont hogy ez valóban sikerült ha sikerült is.

"Gyakorlatilag statisztikailag teljesen randommal megegyező statisztikailag ha feltörte első szinten vagy ha nem."

Mármint az adat amit kapott első szintű feltörés esetén az a megkülönböztethetetlen a randomtól, ha feltörte ha nem első szinten random lesz.