RSAアルゴリズムの確認

gistfile1.txt

$ python rsa.py
prime p: 101
prime q: 109
public key ... n=11009, e=65537
private key ... d=3473
message integer m (< 11009): 1000
encrypted message ... c=9787
decrypted message ... m2=1000

rsa.py

#!/usr/bin/env python

def extended_gcd(a, b):
    """
    Extended Euclidean algorithm
    http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Iterative_method_2
    """
    (x, last_x) = (0, 1)
    (y, last_y) = (1, 0)
    while b != 0:
        quotient = a//b
        (a, b) = (b, a%b)
        (x, last_x) = (last_x - quotient*x, x)
        (y, last_y) = (last_y - quotient*y, y)
    return (last_x, last_y)

def exp_mod(x, e, m):
    """
    calculate y = x^e mod m
    """
    y = 1
    while e > 0:
        if e & 1 == 1:
            y = y*x % m
        x = x*x % m
        e = e >> 1
    return y

def rsa(p, q):
    n = p*q
    phi_n = (p-1)*(q-1)
    e = 0x10001
    (d, _) = extended_gcd(e, phi_n) # choose d such as d*e = 1 mod phi_n
    return (n, e, d)

if __name__ == '__main__':
    p = int(input("prime p: "))
    q = int(input("prime q: "))
    (n, e, d) = rsa(p, q)
    print "public key ... n=%d, e=%d" % (n, e)
    print "private key ... d=%d" % d
    m = int(input("message integer m (< %d): " % (p*q)))
    c = exp_mod(m, e, n)
    print "encrypted message ... c=%d" % c
    m2 = exp_mod(c, d, n)
    print "decrypted message ... m2=%d" % m2