1110.sagews

import sys

KEY_SIZE_IN_BITS = 2048

def Generate_RSA_Key_Pair(random_seed, key_name):
    """
    This code generates an RSA Key Pair.

    Inputs: 

       random_seed --- a random integer used to seed the random number
                       generator.

       key_name --- a text string that is stored with the key to
                    identify it.

    Output:

       [public_key, private_key]


       The public_key is of the form:

          ["public", key_name, modulus, encryption_exponent]

       The private_key is of the form:

          ["private", key_name, modulus, decryption_exponent]

    NOTE: The random number generator used to construct the RSA
    modulus is very weak.  Don't use this for anything other than
    demonstration!
    """

    print "Generating RSA Key Pair.  This can take a little while."
    sys.stdout.flush()

    bit_size = KEY_SIZE_IN_BITS/2
    lcg_modulus = next_prime(2^bit_size + 1)
    random_seed = random_seed % lcg_modulus
    if random_seed == 0:
        random_seed = 5
  

    p = 17
    p_done = False
    print "Finding p:",
    sys.stdout.flush()
    for n in range(KEY_SIZE_IN_BITS + 7):
        p = p^2 % lcg_modulus
        p = p+random_seed % lcg_modulus
    p = next_prime(p)
    while (p < 2^bit_size) or (p > 2^(bit_size+1)):
        print ".",
        sys.stdout.flush()
        p += 2^bit_size % lcg_modulus
        p = next_prime(p)
    print "done"
    
    q = 13
    print "Finding q:",
    sys.stdout.flush()
    for n in range(KEY_SIZE_IN_BITS + 11):
        q = q^2 % lcg_modulus
        q = q+random_seed % lcg_modulus
    q = next_prime(q)
    while (q < 2^bit_size) or (q > 2^(bit_size+1)):
        print ".",
        sys.stdout.flush()
        q += 2^bit_size % lcg_modulus
        q = next_prime(q)
    print "done"

    """
    At this point, p and q are two somewhat randomly generated
    prime numbers.
    """

    RSA_modulus = p*q                  # The RSA modulus is pq

    CRT_modulus = (p-1)*(q-1)          # Now we compute the encryption
                                       # exponent, e.  We need e to be
                                       # relatively prime to p-1 and
                                       # q-1 so that we can use the
                                       # Chinese Remainder Theorem to
                                       # find the decryption exponent,
                                       # d.
    e = 65537
    g = gcd(e,CRT_modulus)
    while not (g == 1):
        e += 2
        g = gcd(e,CRT_modulus)

                                       # Now we compute d.
    d = e^(-1) % CRT_modulus
    
    public_key =  ["public",  key_name, RSA_modulus, e]
    private_key = ["private", key_name, RSA_modulus, d]

    return([public_key, private_key])



def RSA_encrypt_text_message(text_message, public_key):
    """
    Encrypt a *SHORT* text message with the given public key.  NOTE:
    the text message must be relatively short, and it may only use the
    characters a-z and 0-9.  So, no punctuation or spaces are allowed.
    """

    if not public_key[0] == 'public':
        print "Oops, that doesn't appear to be a public key!"
        return(0)

    try:
        M = Integer(text_message,36)
    except:
        print "Oops, you message wasn't usable.  Remember only a-z and 0-9 are allowed."
        return(0)

    if M > public_key[2]:
        print "Oops, your message was too long!"
        return(0)
    
    print "Encrypting message for public key:", public_key[1]

    C = power_mod(M,public_key[3],public_key[2])
    return(C)


def RSA_decrypt_text_message(encrypted_message, private_key):
    """
    Decrypts a message that has been encrypted with the RSA_encrypt_text_message()
    function.
    """

    if not private_key[0] == 'private':
        print "Oops, that doesn't appear to be a private key!"
        return(0)
    M = power_mod(encrypted_message, private_key[3], private_key[2])
    message = M.str(36)
    return(message)

[pub,priv] = Generate_RSA_Key_Pair(12349871234987,'MY RSA Key')

Generating RSA Key Pair. This can take a little while. Finding p: . done Finding q: . done

msg = 'this0is0an0example0message'

encrypted_msg = RSA_encrypt_text_message(msg,pub)

Encrypting message for public key: MY RSA Key

encrypted_msg

53250304937284825117711591479544133566635995952770829252591676713399080126915250031938514796230921975283215966183124636252115672062915121074821773365276786133273153722192782810731788035715821939583495803053685539529107985217819088491678211523786080502941498611720680175283496143359772954624875369844848072437109148174646411326249546434942029297563432838365929359290152453385638564147846478265656360313098031580302516568349474320567613096519396916395941454784543896749030316698599484902151490973856721674595974290376885020647698586861836467042829720577335445481586357788759321940744669313180009266907065990663345208967

decrypted_msg = RSA_decrypt_text_message(encrypted_msg,priv)

decrypted_msg

'this0is0an0example0message'