A Shor-algoritmussal valóban fellehet törni az RSA-t?

Persze.

Csak ott van a buktató, hogy ahhoz, hogy rendes számokra rendes időben lefuttassák, kéne egy rendes kvantumszámítógép.

BTW: A kvantumtitkosítás (amit még kvantumszámítógépekkel se lehet törni) fejlesztése jobban halad, mint a kvantumszámítógépeké.

igen.

az RSA kódolás tulajdonképpen egyszerű, mint a faék. a nyilvános kulcs, amit használ, tulajdonképpen nem más, mint egy bazi nagy szám. egy olyan bazi nagy szám, ami két prímszámnak a szorzata. amik egyébként szintén bazi nagy számok.

a kódolás maga úgy történik, hogy a rendszer választ két prímszámot, összeszorozza őket (ez egy gyorsan végrehajtható dolog) és az eredményt elküldi a másik oldalnak, hogy ezzel kódolj. maga a kódolás megint nagyon egyszerűen elvégezhető művelet.

a kód megfejtéséhet viszont az kell, hogy tudd, mi volt a két eredeti prímszám. anélkül nem lehet megfejteni, mert úgynevezett egyirányú vagy nem megfordítható matematikai műveletet használ. ez azt jelenti, hogy hiába ismered az eredményt és hiába tudod, hogy mit csináltál, hogy megkapd, nem tudod megmondani, hogy milyen számból indultál ki. ilyen pl. a négyzetre emelés. hiába tudod, hogy egy számot négyzetre emeltél és 4-et kaptál eredményül, azt nem tudod megmondani, hogy eredetileg 2, vagy -2 volt-e amiből kiindultál. az RSA művelete abban különleges, hogy megfordítható, ha a központi száma két prímszám szorzata, ha tudod, hogy mi a két prímszám, akkor ki tudod számolni, hogy mi volt az eredeti szám, ha nem tudod, csak magát a központi számot ismered, akkor a lehetőségek száma majdhogynem végtelen.

ilyenkor egyetlen lehetőséged van, ki kell találnod a központi számból, hogy mi volt a két prímszám. azaz prímtényezőkre kell bontanod.

erre meg gyakorlatilag nincs más módszer, mint a próbálgatás. lehet bizonyos egyszerűsítéseket tenni, de a végén csak a rengeteg próbálgatás marad. ez pedig rengeteg idő és számító kapacitás.

a Shor-algoritmus viszont éppen ezt csinálja. az egyetlen baj, hogy kvantumszámítógépre lett tervezve, amíg az nem készül el, addig teljesen használhatatlan.