Mennyi ideig tartana kvantumszámitogéppel végigpróbálni egy bitcoin publikus key összes lehetséges private key-ét ?

"Mennyi ideig tartana kvantumszámitogéppel végigpróbálni egy bitcoin publikus key összes lehetséges private key-ét ?"

Több is van neki?

Ahogy néztem a bitcoin elliptikus görbékre épülő kriptográfiát használ melyeknek a biztonságát a NIST ajánlása szerint egy 160 bites ECC kulcs egy 1024 bites RSA kulccsal, egy 224 bites ECC kulcs egy 2048 bites RSA kulccsal ekvivalens biztonságot nyújt. Szóval ennek megfelelő lehet a törési idő is kvantumszámítógéppel.

Futási időt is csak ordóban lehet meghatározni, mivel a konkrét fizikai tulajdonságoktól meg technikai megvalósítástól is függene. A kvantumos perióduskeresés ordó n^2 ahol n az input mérete. Vagyis legalább ordó n^2 futási idejű, de mint tudjuk a prímfaktorizáció ordó n^3 futási idejű, az ECDSA algoritmus is kb ordó n^3 futási idejű lehet. Vagyis a kulcs hosszának köbével arányos futási idejű lehet kb, ha nem is pontosan de valami e körüli polinomja vagyis polinom idejű.

"Szóval ennek megfelelő lehet a törési idő is kvantumszámítógéppel."

Hát papíron, és szekvenciálisan. Amit mondasz az számítástudomány alapokon mondod, ami helyes. Abban a környezetben.

Csak a kvantumgép nem így dolgozik. Pont hogy nem. Ép ez az, hogy kvantumgép nem 2 bit állapottal dolgozik, hanem többet.

Google állítása:

Csináltak egy számítógépet, ami 3 perc alatt végzett egy számítással. A világ legerősebb szuperszámítógépeként ismert Summitnak ugyanis 10 000 évnyi idő lett volna ez feladat.

Forrás: [link]

"Hát papíron, és szekvenciálisan. Amit mondasz az számítástudomány alapokon mondod, ami helyes. Abban a környezetben."

A francokat szekvenciálisan mondom. Tudod mikor lenne szekvenciálisan polinom idejű, pont hogy az input hosszának lineáris növelésével exponenciálisan nő a futási idő egy klasszikus gépen. Mivel NP nehéz probléma. Ami azt jelenti hogy létezik rá nem determinisztikus polinom idejű algoritmus, ami még máshogy azt jelenti hogy gyorsan elvégezhető klasszikusan egy esetről hogy megoldás e, de maga a megoldás megkeresése az nagyon nehéz exponenciális idejű. Végig ordó-ban írtam a futási idős dolgot. Meg nem akarom ismételgetni önmagamat, hogy nem konkrét máspdpercekről írok. Nem fogom most itt definiálni mi az hogy ordóban. Ha kérdés akkor tedd külön kérdésnek fel külön ha akarod!

Itt az RSA törést írja, meg egyéb kvatum algoritmusokat : [link]

Abból indultam ki, hogy hasonló bonyolultsági osztály jellemzi az RSA-t mint a bitcoin-nál használt elliptikus görbéket, ezért a kvantum algoritmus is hasonló hatékonyságú lehet és hasonló futási idejű. Persze érteni kell mi az hogy hasonló, hát mégpedig ordóba értendően hasonló.