RSA_Known_Decrypt_Key

3705 days ago by alex

# Set up toy RSA key. Pick two "random" primes. p, q = 43, 61 
       
# Modulus is product of the primes n = p*q; n 
        
2623
2623
# Find euler_phi phn = euler_phi(n); phn 
        
2520
2520
# Get a random encryption exponent relatively prime to phn. e = randrange(3,n) while gcd(e,phn) != 1: e = randrange(3,n) e 
        
601
601
# Decryption exponent d satisfies d * e = 1 mod phi(n). d = inverse_mod(e, phn); d 
        
2281
2281
# Compute d*e - 1 and express it as 2^s * t dem = d*e - 1 dem 
        
1370880
1370880
s, t = dem.trailing_zero_bits(), dem.prime_to_m_part(2); s, t 
        
(8, 5355)
(8, 5355)
dem == t*2^s 
        
True
True
b = randrange(1,n) while gcd(b,n) != 1: b = randrange(1,n) b 
        
1956
1956
blist = [power_mod(b, t, n)]; blist 
        
[1463]
[1463]
# Look for r so b^( 2^r * t ) = 1 mod n and # b^( 2^(r-1)*t ) is not 1 or -1 mod n # for r in range(s): blist.append(power_mod(blist[-1], 2, n)) blist 
        
[1463, 1, 1, 1, 1, 1, 1, 1, 1]
[1463, 1, 1, 1, 1, 1, 1, 1, 1]
# Unless blist[0] is -1 mod p AND -1 mod q, # blist[0]-1 will have a nontrivial gcd with n # gcd(blist[0]-1,n) 
        
43
43
n // 43 
        
61
61