85 lines
2.1 KiB
Python
85 lines
2.1 KiB
Python
|
"""
|
||
|
|
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]))
|
||
|
|
|