quantum/03_shors.py

85 lines
2.1 KiB
Python
Raw Permalink Normal View History

"""
RSA is an asymmetric encr algo that relies on a public key and a private key.
Public key encrypts message M to a cyphertext C:
C = M^e % N
e is part of the public key and is implementation specific, chosen
but frequently chosen to be 3 (bad) or 17 or 65537 (a number that has a
lot of 0s, makes "computer maths easy).
N is also part of the public key - N = p*q, where p and q are (large) prime
numbers.
Decrypting the message:
M = C^d % N
d is the part of the private key (private exponent) derived using p and q,
such that:
e*d=1%((p-1)(q-1))
To break the encryption, if one gets to factor N to p and q, d can be
derviced from there
"""
import sys
def d(p, q, e=3):
""" TODO: Doesn't make sense!?"""
return 1%((p-1)*(q-1))
def gcd(a, b):
if b == 0:
return a
return gcd(b, a % b)
def trick(A, B, p_max=10):
"""
If A and B are mutually prime (gcd is 1):
A^p = m*B + 1
for some p and m.
returns p and m
"""
if gcd(A,B) != 1:
print("ERROR: A, B not mutually prime!")
return None, None
for p in range(2, p_max):
m, found = 1, False
lhs, rhs = A**p, m*B + 1
while lhs > rhs:
rhs = m*B + 1
print("({}, {}): {} =? {}".format(p, m, lhs, rhs))
if lhs == rhs:
found = True
break
m += 1
if found:
print('===== FOUND')
print("p={}, m={}".format(p, m))
return p, m
print("Not found up to {}".format(p_max))
return None, None
# (g^p/2 + 1) * (g^p/2 -1) = m*N --- this is almost like a*b~=N
# because of m*N, the terms on LHS might not be the factors but
# multiple of factors, i.e. a*factor, b*factor
# e.g. 7^4/2 + 1 = 50; 7^4/2 - 1 = 48; which are not factors of 15
# gcd(50, 15) = 5, gcd(48, 15) = 3
# Trick #2:
# g^x = m_1*N + r
# g^(x+p) = m_2*N + r
# [if g^p = m_1*N + 1 => expanding g^(x+p)=g^x*x^p=(m_1*N+1)*(m_2*N+r)=...=(m_1*m_2 + 3m_1+m_2)*N +r ~= something*N+r
if __name__ == '__main__':
trick(int(sys.argv[1]), int(sys.argv[2]))