Düşünce Mezarlığı

import random

def gen_prime(N=10**8, bases=range(2,20000)):
    # istenirse daha gelişmiş bir algoritma ile değiştirilebilir
    p = 1
    while any(pow(base, p-1, p) != 1 for base in bases):
        p = random.SystemRandom().randrange(N)
    return p

def multinv(modulus, value):
    '''Belirli bir modülde ters çarpım işlemini yapıyoruz burada

        >>> multinv(191, 138)
        18
        >>> 18 * 138 % 191
        1

    '''
    x, lastx = 0, 1
    a, b = modulus, value
    while b:
        a, q, b = b, a // b, a % b
        x, lastx = lastx - q * x, x
    result = (1 - lastx * modulus) // value
    return result + modulus if result < 0 else result

def keygen(N):
    '''Asal sayılardan N'ye kadar genel ve özel anahtarlar oluşturuyoruz.

        >>> pubkey, privkey = keygen(2**64)
        >>> msg = 123456789012345
        >>> coded = pow(msg, 65537, pubkey)
        >>> plain = pow(coded, privkey, pubkey)
        >>> assert msg == plain

    '''
    # http://en.wikipedia.org/wiki/RSA
    prime1 = gen_prime(N)
    prime2 = gen_prime(N)
    totient = (prime1 - 1) * (prime2 - 1)
    return prime1 * prime2, multinv(totient, 65537)

def main():
    pubkey, privkey = keygen(2**64)
    msg = 123456789012345
    coded = pow(msg, 65537, pubkey)
    plain = pow(coded, privkey, pubkey)
    assert msg == plain
             
if __name__ == "__main__":
    main()