Codigo RSA

# Codigo RSA
# paulogp, 2008

def gcd(a, b):
    '''Algoritmo de Euclides; Determinacao do Maximo Divisor Comum
    a, b: numeros inteiros'''
    assert a >= b # a must be the larger number

    while (b != 0):
        remainder = a % b
        a, b  = b, remainder

    return a

def chaves(p, q):
    '''Criacao das chaves publicas e privadas
    p, q: numeros primos'''
    n = p * q
    fi = (p - 1) * (q - 1)
    e = 2
    k = 0

    while gcd(fi, e) > 1:
        e = e + 1

    achou = 0
    while achou == 0:
        d = (1. + (k * fi)) / e

        if d == round(d):
            achou = 1
        else:
            k = k + 1

    print 'Chave publica ' + int(e) + ', ' + `n`
    print 'Chave privada ' + int(d) + ', ' + `n`

def cifrar(e, n, M):
    '''Cifrar a mensagem
    e, n: chave publica
    M: mensagem em codigo ASCII em vector
    exemplo: cifrar(3, 253, [64, 90])'''
    L = []
    for i in range(0, len(M)):
        L.append((M[i]**e) % n)

    print L

def decifrar(d, n, M):
    '''Decifrar a mensagem
    d, n: chave privada
    M: mensagem em codigo ASCII em vector
    exemplo: decifrar(147, 253, [36, 107])'''
    L = []
    for i in range(0, len(M)):
        L.append((M[i]**d) % n)

    print L

# exemplo
cifrar(3, 253, [64, 90])
decifrar(147, 253, [36, 107])