shor26

Pojďme si představit, jak by kvantový počítač se Shorovým algoritmem prolomil zjednodušenou „osmibitovou“ verzi Bitcoinu s mod17.

Základní princip (silně zjednodušeno)

V Bitcoinu a dalších kryptoměnách se používá asymetrická kryptografie, například RSA nebo eliptické křivky.

Pro jednoduchost si představme, že náš „osmibitový Bitcoin“ používá RSA s malými čísly, kde veřejný klíč je dán modulem N a exponentem e.

Cílem útočníka je získat soukromý klíč, který je odvozen od prvočísel p a q, ze kterých vznikne

N = p * q

Jakmile známe p a q, můžeme spočítat Eulerovu funkci

phi(N) = (p − 1) * (q − 1)

a z ní soukromý exponent d.

Použití Shorova algoritmu s mod17

Pokud by se RSA používalo přímo s modulem 17, nebylo by co faktorizovat, protože 17 je prvočíslo.

Proto si pro ukázku vezmeme malé složené číslo

N = 15

což je

15 = 3 * 5

Cílem je faktorizovat N.

Kroky Shorova algoritmu pro N = 15

Vybereme náhodné číslo a takové, aby gcd(a, N) = 1

Zvolíme a = 7

protože gcd(7, 15) = 1

Hledáme periodu funkce f(x) = a^x mod N

tedy f(x) = 7^x mod 15

počítáme:

7^1 mod 15 = 7

7^2 mod 15 = 49 mod 15 = 4

7^3 mod 15 = 7 * 4 = 28 mod 15 = 13

7^4 mod 15 = 7 * 13 = 91 mod 15 = 1

dostali jsme 1

perioda je r = 4

protože 7^4 mod 15 = 1

Jak to udělá kvantový počítač

Kvantový počítač použije kvantovou Fourierovu transformaci (QFT) k nalezení periody r.

Postup:

vytvoří superpozici stavů

spočítá f(x) = a^x mod N

aplikuje QFT

změří výsledek

z výsledků dopočítá periodu r

Použití periody k nalezení faktorů

Podmínka 1) r musí být sudé

r = 4 → OK

Podmínka 2) a^(r/2) mod N nesmí být −1 mod N

počítáme a^(r/2) = 7^(4/2) = 7^2 = 49 mod 15 = 4

−1 mod 15 = 14

4 ≠ 14 → OK

Teď spočítáme gcd(a^(r/2) − 1, N)

gcd(49 − 1, 15) = gcd(48, 15) = 3

a gcd(a^(r/2) + 1, N)

gcd(49 + 1, 15) = gcd(50, 15) = 5

dostali jsme 3 a 5

tedy 15 = 3 * 5

Výpočet soukromého klíče

phi(15) = (3 − 1) * (5 − 1)

phi(15) = 2 * 4 = 8

zvolíme veřejný exponent

e = 7

musí platit

gcd(e, phi) = 1

gcd(7, 8) = 1 → OK

hledáme d takové, že

e * d mod phi = 1

7 * d mod 8 = 1

zkusíme

7 * 7 = 49 mod 8 = 1

tedy

d = 7

soukromý klíč je (d, N) = (7, 15)

Souvislost s osmibitovým Bitcoinem a mod17

Pokud by modul byl menší než 17, pak by N mohlo být jen malé číslo:

4, 6, 8, 9, 10, 12, 14, 15

všechna lze snadno rozložit.

Shorův algoritmus by je také rozložil, ale byl by zbytečně silný.

Princip ale zůstává stejný.

Souvislost s eliptickými křivkami (ECDLP)

Máme bod G a veřejný klíč Q

Q = d * G

chceme najít d

Shorův algoritmus vytvoří funkci f(a, b) = aG + bQ

dosadíme Q = dG

f(a, b) = aG + b d G = (a + b d) G

hledáme dvojici (a, b), pro kterou

a + b d = k * n

kde n je řád bodu G

kvantový počítač pomocí QFT najde periodu

perioda obsahuje vektor (d, −1)

z toho lze spočítat d

Shrnutí

Shorův algoritmus umí najít periodu funkce.

Z periody lze získat faktory N (RSA) nebo d (ECDLP).