Skip to content

Instantly share code, notes, and snippets.

@avalonalex

avalonalex/RSA.py

Last active October 19, 2025 03:12
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save avalonalex/2122098 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save avalonalex/2122098 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. avalonalex revised this gist Jun 3, 2015. 1 changed file with 2 additions and 2 deletions.
    4 changes: 2 additions & 2 deletions RSA.py
    View file
    Original file line number Diff line number Diff line change
    @@ -259,9 +259,9 @@ def decrypt(secret, modN, d, blockSize):
    def block_size(val):
    try:
    v = int(val)
    assert(v >= 10 and c <= 1000)
    assert(v >= 10 and v <= 1000)
    except:
    raise ArgumentTypeError("'%s' is not a valid block size" % val)
    raise argparse.ArgumentTypeError("{} is not a valid block size".format(val))
    return val

    if __name__ == '__main__':
  2. avalonalex revised this gist Jun 3, 2015. 1 changed file with 51 additions and 17 deletions.
    68 changes: 51 additions & 17 deletions RSA.py
    View file
    Original file line number Diff line number Diff line change
    @@ -1,7 +1,11 @@
    #!/usr/bin/env python

    import argparse
    import copy
    import math
    import pickle
    import random
    from itertools import combinations
    import math
    import copy


    def euclid(a, b):
    @@ -183,26 +187,27 @@ def newKey(a, b, k):
    break
    except:
    raise ValueError

    n = p * q
    m = (p - 1) * (q - 1)

    while True:
    e = random.randint(1, m)
    if coPrime([e, m]):
    break

    d = modInv(e, m)
    return (n, e, d)


    def string2numList(strn):
    """Converts a string to a list of integers based on ASCII values"""
    # Note that ASCII printable characters range is 0x20 - 0x7E
    return [ord(chars) for chars in strn]
    return [ ord(chars) for chars in pickle.dumps(strn) ]


    def numList2string(l):
    """Converts a list of integers to a string based on ASCII values"""
    # Note that ASCII printable characters range is 0x20 - 0x7E
    return ''.join(map(chr, l))
    return pickle.loads(''.join(map(chr, l)))


    def numList2blocks(l, n):
    @@ -251,18 +256,47 @@ def decrypt(secret, modN, d, blockSize):
    numList = blocks2numList(numBlocks, blockSize)
    return numList2string(numList)

    def block_size(val):
    try:
    v = int(val)
    assert(v >= 10 and c <= 1000)
    except:
    raise ArgumentTypeError("'%s' is not a valid block size" % val)
    return val

    if __name__ == '__main__':
    (n, e, d) = newKey(10 ** 100, 10 ** 101, 50)
    print ('n = {0}'.format(n))
    print ('e = {0}'.format(e))
    print ('d = {0}'.format(d))
    message = """
    We were the Leopards, the Lions, those who'll take our place will be
    little jackals, hyenas; But we'll go on thinking ourselves the salt of
    the earth.
    parser = argparse.ArgumentParser()

    group = parser.add_mutually_exclusive_group(required=True)
    group.add_argument("-m", "--message", help="Text message to encrypt")
    group.add_argument("-f", "--file", type=file, help="Text file to encrypt")

    parser.add_argument("-b", "--block-size", type=block_size, default=15,
    help="Block size to break message info smaller trunks")

    args = parser.parse_args()

    print """
    ------------------------------------------------------
    This program is intended for the purpose pedagogy only
    ------------------------------------------------------
    """
    print(message)

    n, e, d = newKey(10 ** 100, 10 ** 101, 50)

    if args.message is not None:
    message = args.message
    else:
    print args.file
    try:
    message = args.file.read()
    finally:
    args.file.close()

    print "original message is {}".format(message)
    print "-"*80
    cipher = encrypt(message, n, e, 15)
    print(cipher)
    print "cipher text is {}".format(cipher)
    print "-"*80
    deciphered = decrypt(cipher, n, d, 15)
    print(deciphered)
    print "decrypted message is {}".format(deciphered)
  3. avalonalex revised this gist Aug 17, 2014. 1 changed file with 45 additions and 45 deletions.
    90 changes: 45 additions & 45 deletions RSA.py
    View file
    Original file line number Diff line number Diff line change
    @@ -5,7 +5,7 @@


    def euclid(a, b):
    '''returns the Greatest Common Divisor of a and b'''
    """returns the Greatest Common Divisor of a and b"""
    a = abs(a)
    b = abs(b)
    if a < b:
    @@ -15,52 +15,52 @@ def euclid(a, b):
    return a


    def coprime(l):
    '''returns 'True' if the values in the list L are all co-prime
    otherwier, it returns 'False'. '''
    def coPrime(l):
    """returns 'True' if the values in the list L are all co-prime
    otherwise, it returns 'False'. """
    for i, j in combinations(l, 2):
    if euclid(i, j) != 1:
    return False
    return True


    def extendedEuclid(a, b):
    '''return a tuple of three values: x, y and z, such that x is
    the GCD of a and b, and x = y * a + z * b'''
    """return a tuple of three values: x, y and z, such that x is
    the GCD of a and b, and x = y * a + z * b"""
    if a == 0:
    return (b, 0, 1)
    return b, 0, 1
    else:
    g, y, x = extendedEuclid(b % a, a)
    return (g, x - (b // a) * y, y)
    return g, x - (b // a) * y, y


    def modInv(a, m):
    '''returns the multiplicative inverse of a in modulo m as a
    positve value between zero and m-1'''
    """returns the multiplicative inverse of a in modulo m as a
    positive value between zero and m-1"""
    # notice that a and m need to co-prime to each other.
    if coprime([a, m]) == False:
    return 0
    if coPrime([a, m]):
    linearCombination = extendedEuclid(a, m)
    return linearCombination[1] % m
    else:
    linearcombination = extendedEuclid(a, m)
    return linearcombination[1] % m
    return 0


    def extractTwos(m):
    '''m is a positive integer. A tuple (s, d) of integers is returned
    such that m = (2 ** s) * d.'''
    """m is a positive integer. A tuple (s, d) of integers is returned
    such that m = (2 ** s) * d."""
    # the problem can be break down to count how many '0's are there in
    # the end of bin(m). This can be done this way: m & a stretch of '1's
    # which can be represent as (2 ** n) - 1.
    assert m >= 0
    i = 0
    while m & (2 ** i) == 0:
    i += 1
    return (i, m >> i)
    return i, m >> i


    def int2baseTwo(x):
    '''x is a positive integer. Convert it to base two as a list of integers
    in reverse order as a list.'''
    """x is a positive integer. Convert it to base two as a list of integers
    in reverse order as a list."""
    # repeating x >>= 1 and x & 1 will do the trick
    assert x >= 0
    bitInverse = []
    @@ -71,7 +71,7 @@ def int2baseTwo(x):


    def modExp(a, d, n):
    '''returns a ** d (mod n)'''
    """returns a ** d (mod n)"""
    assert d >= 0
    assert n >= 0
    base2D = int2baseTwo(d)
    @@ -90,13 +90,13 @@ def modExp(a, d, n):


    def millerRabin(n, k):
    '''
    """
    Miller Rabin pseudo-prime test
    return True means likely a prime, (how sure about that, depending on k)
    return False means definitely a composite.
    Raise assertion error when n, k are not positive integers
    and n is not 1
    '''
    """
    assert n >= 1
    # ensure n is bigger than 1
    assert k > 0
    @@ -116,9 +116,9 @@ def millerRabin(n, k):
    assert 2 ** s * d == n - 1

    def tryComposite(a):
    '''Inner function which will inspect whether a given witness
    """Inner function which will inspect whether a given witness
    will reveal the true identity of n. Will only be called within
    millerRabin'''
    millerRabin"""
    x = modExp(a, d, n)
    if x == 1 or x == n - 1:
    return None
    @@ -139,12 +139,12 @@ def tryComposite(a):


    def primeSieve(k):
    '''return a list with length k + 1, showing if list[i] == 1, i is a prime
    else if list[i] == 0, i is a composite, if list[i] == -1, not defined'''
    """return a list with length k + 1, showing if list[i] == 1, i is a prime
    else if list[i] == 0, i is a composite, if list[i] == -1, not defined"""

    def isPrime(n):
    '''return True is given number n is absolutely prime,
    return False is otherwise.'''
    """return True is given number n is absolutely prime,
    return False is otherwise."""
    for i in range(2, int(n ** 0.5) + 1):
    if n % i == 0:
    return False
    @@ -159,9 +159,9 @@ def isPrime(n):


    def findAPrime(a, b, k):
    '''Return a pseudo prime number roughly between a and b,
    """Return a pseudo prime number roughly between a and b,
    (could be larger than b). Raise ValueError if cannot find a
    pseudo prime after 10 * ln(x) + 3 tries. '''
    pseudo prime after 10 * ln(x) + 3 tries. """
    x = random.randint(a, b)
    for i in range(0, int(10 * math.log(x) + 3)):
    if millerRabin(x, k):
    @@ -172,9 +172,9 @@ def findAPrime(a, b, k):


    def newKey(a, b, k):
    ''' Try to find two large pseudo primes roughly between a and b.
    """ Try to find two large pseudo primes roughly between a and b.
    Generate public and private keys for RSA encryption.
    Raises ValueError if it fails to find one'''
    Raises ValueError if it fails to find one"""
    try:
    p = findAPrime(a, b, k)
    while True:
    @@ -187,28 +187,28 @@ def newKey(a, b, k):
    m = (p - 1) * (q - 1)
    while True:
    e = random.randint(1, m)
    if coprime([e, m]):
    if coPrime([e, m]):
    break
    d = modInv(e, m)
    return (n, e, d)


    def string2numList(strn):
    '''Converts a string to a list of integers based on ASCII values'''
    """Converts a string to a list of integers based on ASCII values"""
    # Note that ASCII printable characters range is 0x20 - 0x7E
    return [ord(chars) for chars in strn]


    def numList2string(l):
    '''Converts a list of integers to a string based on ASCII values'''
    """Converts a list of integers to a string based on ASCII values"""
    # Note that ASCII printable characters range is 0x20 - 0x7E
    return ''.join(map(chr, l))


    def numList2blocks(l, n):
    '''Take a list of integers(each between 0 and 127), and combines them
    """Take a list of integers(each between 0 and 127), and combines them
    into block size n using base 256. If len(L) % n != 0, use some random
    junk to fill L to make it.'''
    junk to fill L to make it."""
    # Note that ASCII printable characters range is 0x20 - 0x7E
    returnList = []
    toProcess = copy.copy(l)
    @@ -224,7 +224,7 @@ def numList2blocks(l, n):


    def blocks2numList(blocks, n):
    '''inverse function of numList2blocks.'''
    """inverse function of numList2blocks."""
    toProcess = copy.copy(blocks)
    returnList = []
    for numBlock in toProcess:
    @@ -238,15 +238,15 @@ def blocks2numList(blocks, n):


    def encrypt(message, modN, e, blockSize):
    '''given a string message, public keys and blockSize, encrypt using
    RSA algorithms.'''
    """given a string message, public keys and blockSize, encrypt using
    RSA algorithms."""
    numList = string2numList(message)
    numBlocks = numList2blocks(numList, blockSize)
    return [modExp(blocks, e, modN) for blocks in numBlocks]


    def decrypt(secret, modN, d, blockSize):
    '''reverse function of encrypt'''
    """reverse function of encrypt"""
    numBlocks = [modExp(blocks, d, modN) for blocks in secret]
    numList = blocks2numList(numBlocks, blockSize)
    return numList2string(numList)
    @@ -256,13 +256,13 @@ def decrypt(secret, modN, d, blockSize):
    print ('n = {0}'.format(n))
    print ('e = {0}'.format(e))
    print ('d = {0}'.format(d))
    message = '''
    message = """
    We were the Leopards, the Lions, those who'll take our place will be
    little jackals, hyenas; But we'll go on thinking ourselves the salt of
    the earth.
    '''
    """
    print(message)
    cipher = encrypt(message, n, e, 15)
    print(cipher)
    Amessage = decrypt(cipher, n, d, 15)
    print(Amessage)
    deciphered = decrypt(cipher, n, d, 15)
    print(deciphered)
  4. avalonalex revised this gist Dec 25, 2013. 1 changed file with 0 additions and 1 deletion.
    1 change: 0 additions & 1 deletion RSA.py
    View file
    Original file line number Diff line number Diff line change
    @@ -72,7 +72,6 @@ def int2baseTwo(x):

    def modExp(a, d, n):
    '''returns a ** d (mod n)'''
    # a faster algorithms discussed in CIT 592 class
    assert d >= 0
    assert n >= 0
    base2D = int2baseTwo(d)
  5. avalonalex revised this gist Dec 25, 2013. 1 changed file with 59 additions and 129 deletions.
    188 changes: 59 additions & 129 deletions RSA.py
    View file
    Original file line number Diff line number Diff line change
    @@ -1,82 +1,40 @@
    # October 2011
    # Author Yuhan Hao
    # Email: yuhanhao@seas.upenn.edu
    # Tested under python3.2.2

    import random
    from itertools import combinations
    import math
    import copy

    def euclid(a,b):

    def euclid(a, b):
    '''returns the Greatest Common Divisor of a and b'''
    a = abs(a)
    b = abs(b)
    # make sure the algorithms still works even when
    # some negative numbers are passed to the program

    if a < b:
    a, b = b, a

    while b != 0:
    a, b = b, a % b

    return a

    def coprime(L):

    def coprime(l):
    '''returns 'True' if the values in the list L are all co-prime
    otherwier, it returns 'False'. '''

    for i in range (0, len(L)):
    for j in range (i + 1, len(L)):
    if euclid(L[i], L[j]) != 1:
    return False

    for i, j in combinations(l, 2):
    if euclid(i, j) != 1:
    return False
    return True

    def extendedEuclid(a,b):
    '''return a tuple of three values: x, y and z, such that x is
    the GCD of a and b, and x = y * a + z * b'''
    footprint = []

    # the boolean flag is used to make sure this function can return
    # right answer no matter which is bigger.
    if a < b:
    isASmallerThanB = True
    a, b = b, a
    def extendedEuclid(a, b):
    '''return a tuple of three values: x, y and z, such that x is
    the GCD of a and b, and x = y * a + z * b'''
    if a == 0:
    return (b, 0, 1)
    else:
    isASmallerThanB = False
    while b != 0:
    footprint.append((a % b, 1, a, -(a//b), b))
    # for each tuple in list footprint
    # footprint[i][0] == footprint [i][1] * footprint[i][2]
    # + footprint [i][3] * foorprint[i][4]
    # and
    # footprint[i][4] == footprint[i+1][0]
    # this two equations are key to generate the linear combination
    # of a and b so that the result will be their GCD (or GCF).
    a, b = b, a % b
    g, y, x = extendedEuclid(b % a, a)
    return (g, x - (b // a) * y, y)

    # Start work backward to compute the linear combination
    # of a and b so that this combination gives the GCD of a and b
    footprint.reverse()
    footprint.pop(0)
    #print (footprint)
    x = footprint[0][1]
    y = footprint[0][3]
    #print (x, y)
    for i in range (1, len(footprint)):
    x_temp = x
    y_temp = y
    x = y_temp * footprint[i][1]
    y = y_temp * footprint[i][3] + x_temp
    #print (x, y)

    if (isASmallerThanB != True):
    return (a, x, y)
    else:
    return (a, y, x)

    def modInv(a,m):
    def modInv(a, m):
    '''returns the multiplicative inverse of a in modulo m as a
    positve value between zero and m-1'''
    # notice that a and m need to co-prime to each other.
    @@ -86,36 +44,6 @@ def modInv(a,m):
    linearcombination = extendedEuclid(a, m)
    return linearcombination[1] % m

    def crt(L):
    '''takes in a list of two or more tuples, ie
    L = [(a0, n0), (a1,n1),(a2,n2)...(ak nk)]
    if the n-s are not co-prime, this function prints an error message to
    the screen and returns -1. Otherwise it continues with the Chinese
    Remainder theorem, finding a value for x to return which satisfies
    x = ai( mod ni)
    for all tuples in the list L. This value must be between 0 and N-1
    where N is the product of all the n in the list L'''
    NList = []
    for item in L:
    NList.append(item[1])
    if coprime(NList) == False:
    print ("The input is not valid!")
    return -1
    else:
    bigN = 1
    for numbers in NList:
    bigN *= numbers
    CRTresult = 0
    for item in L:
    ai = item[0]
    Ci = bigN//item[1]
    #print (Ni, ai)
    Yi = extendedEuclid(Ci, item[1])
    #print (Ci, item[1])
    CRTresult += ai * Ci * Yi[1]
    return CRTresult % bigN

    # start of second project *****************************

    def extractTwos(m):
    '''m is a positive integer. A tuple (s, d) of integers is returned
    @@ -141,7 +69,8 @@ def int2baseTwo(x):
    x >>= 1
    return bitInverse

    def modExp(a,d,n):

    def modExp(a, d, n):
    '''returns a ** d (mod n)'''
    # a faster algorithms discussed in CIT 592 class
    assert d >= 0
    @@ -150,16 +79,17 @@ def modExp(a,d,n):
    base2DLength = len(base2D)
    modArray = []
    result = 1
    for i in range (1, base2DLength + 1):
    for i in range(1, base2DLength + 1):
    if i == 1:
    modArray.append(a % n)
    else:
    modArray.append((modArray[i - 2] ** 2) % n)
    for i in range (0, base2DLength):
    for i in range(0, base2DLength):
    if base2D[i] == 1:
    result *= base2D[i] * modArray[i]
    return result % n


    def millerRabin(n, k):
    '''
    Miller Rabin pseudo-prime test
    @@ -194,24 +124,25 @@ def tryComposite(a):
    if x == 1 or x == n - 1:
    return None
    else:
    for j in range (1,s):
    for j in range(1, s):
    x = modExp(x, 2, n)
    if x == 1:
    return False
    elif x == n - 1:
    return None
    return False

    for i in range (0, k):
    for i in range(0, k):
    a = random.randint(2, n - 2)
    if tryComposite(a) == False:
    return False
    return True # actually, we should return probably true.
    return True # actually, we should return probably true.


    def primeSieve(k):
    '''return a list with length k + 1, showing if list[i] == 1, i is a prime
    else if list[i] == 0, i is a composite, if list[i] == -1, not defined'''

    def isPrime(n):
    '''return True is given number n is absolutely prime,
    return False is otherwise.'''
    @@ -227,7 +158,8 @@ def isPrime(n):
    result[i] = 0
    return result

    def findAPrime(a,b,k):

    def findAPrime(a, b, k):
    '''Return a pseudo prime number roughly between a and b,
    (could be larger than b). Raise ValueError if cannot find a
    pseudo prime after 10 * ln(x) + 3 tries. '''
    @@ -239,7 +171,8 @@ def findAPrime(a,b,k):
    x += 1
    raise ValueError

    def newKey(a,b,k):

    def newKey(a, b, k):
    ''' Try to find two large pseudo primes roughly between a and b.
    Generate public and private keys for RSA encryption.
    Raises ValueError if it fails to find one'''
    @@ -252,39 +185,36 @@ def newKey(a,b,k):
    except:
    raise ValueError
    n = p * q
    m = (p-1) * (q-1)
    m = (p - 1) * (q - 1)
    while True:
    e = random.randint(1, m)
    if coprime([e, m]):
    break
    d = modInv(e, m)
    return (n, e, d)


    def string2numList(strn):
    '''Converts a string to a list of integers based on ASCII values'''
    # Note that ASCII printable characters range is 0x20 - 0x7E
    returnList = []
    for chars in strn:
    returnList.append(ord(chars))
    return returnList
    return [ord(chars) for chars in strn]

    def numList2string(L):

    def numList2string(l):
    '''Converts a list of integers to a string based on ASCII values'''
    # Note that ASCII printable characters range is 0x20 - 0x7E
    returnList = []
    returnString = ''
    for nums in L:
    returnString += chr(nums)
    return returnString

    def numList2blocks(L,n):
    '''Take a list of integers(each between 0 and 127), and combines them into block size
    n using base 256. If len(L) % n != 0, use some random junk to fill L to make it '''
    return ''.join(map(chr, l))


    def numList2blocks(l, n):
    '''Take a list of integers(each between 0 and 127), and combines them
    into block size n using base 256. If len(L) % n != 0, use some random
    junk to fill L to make it.'''
    # Note that ASCII printable characters range is 0x20 - 0x7E
    returnList = []
    toProcess = copy.copy(L)
    toProcess = copy.copy(l)
    if len(toProcess) % n != 0:
    for i in range (0, n - len(toProcess) % n):
    for i in range(0, n - len(toProcess) % n):
    toProcess.append(random.randint(32, 126))
    for i in range(0, len(toProcess), n):
    block = 0
    @@ -293,7 +223,8 @@ def numList2blocks(L,n):
    returnList.append(block)
    return returnList

    def blocks2numList(blocks,n):

    def blocks2numList(blocks, n):
    '''inverse function of numList2blocks.'''
    toProcess = copy.copy(blocks)
    returnList = []
    @@ -306,34 +237,33 @@ def blocks2numList(blocks,n):
    returnList.extend(inner)
    return returnList


    def encrypt(message, modN, e, blockSize):
    '''given a string message, public keys and blockSize, encrypt using
    RSA algorithms.'''
    cipher = []
    numList = string2numList(message)
    numBlocks = numList2blocks(numList, blockSize)
    for blocks in numBlocks:
    cipher.append(modExp(blocks, e, modN))
    return cipher
    return [modExp(blocks, e, modN) for blocks in numBlocks]


    def decrypt(secret, modN, d, blockSize):
    '''reverse function of encrypt'''
    numBlocks = []
    numList = []
    for blocks in secret:
    numBlocks.append(modExp(blocks, d, modN))
    numBlocks = [modExp(blocks, d, modN) for blocks in secret]
    numList = blocks2numList(numBlocks, blockSize)
    message = numList2string(numList)
    return message
    return numList2string(numList)

    if __name__=='__main__':
    (n, e, d) = newKey(10**100, 10**101, 50)
    if __name__ == '__main__':
    (n, e, d) = newKey(10 ** 100, 10 ** 101, 50)
    print ('n = {0}'.format(n))
    print ('e = {0}'.format(e))
    print ('d = {0}'.format(d))
    message = '''We were the Leopards, the Lions, those who'll take our place will be little jackals, hyenas; But we'll go on thinking ourselves the salt of the earth.'''
    message = '''
    We were the Leopards, the Lions, those who'll take our place will be
    little jackals, hyenas; But we'll go on thinking ourselves the salt of
    the earth.
    '''
    print(message)
    cipher = encrypt(message, n, e, 15)
    print(cipher)
    Amessage = decrypt(cipher, n, d, 15)
    print(Amessage)
    print(Amessage)
  6. avalonalex revised this gist Mar 19, 2012. 1 changed file with 0 additions and 1 deletion.
    1 change: 0 additions & 1 deletion RSA.py
    View file
    Original file line number Diff line number Diff line change
    @@ -2,7 +2,6 @@
    # Author Yuhan Hao
    # Email: yuhanhao@seas.upenn.edu
    # Tested under python3.2.2
    # Coding Assignment 2 for CIT 592

    import random
    import math
  7. avalonalex created this gist Mar 19, 2012.
    340 changes: 340 additions & 0 deletions RSA.py
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,340 @@
    # October 2011
    # Author Yuhan Hao
    # Email: yuhanhao@seas.upenn.edu
    # Tested under python3.2.2
    # Coding Assignment 2 for CIT 592

    import random
    import math
    import copy

    def euclid(a,b):
    '''returns the Greatest Common Divisor of a and b'''
    a = abs(a)
    b = abs(b)
    # make sure the algorithms still works even when
    # some negative numbers are passed to the program

    if a < b:
    a, b = b, a

    while b != 0:
    a, b = b, a % b

    return a

    def coprime(L):
    '''returns 'True' if the values in the list L are all co-prime
    otherwier, it returns 'False'. '''

    for i in range (0, len(L)):
    for j in range (i + 1, len(L)):
    if euclid(L[i], L[j]) != 1:
    return False

    return True

    def extendedEuclid(a,b):
    '''return a tuple of three values: x, y and z, such that x is
    the GCD of a and b, and x = y * a + z * b'''
    footprint = []

    # the boolean flag is used to make sure this function can return
    # right answer no matter which is bigger.
    if a < b:
    isASmallerThanB = True
    a, b = b, a
    else:
    isASmallerThanB = False
    while b != 0:
    footprint.append((a % b, 1, a, -(a//b), b))
    # for each tuple in list footprint
    # footprint[i][0] == footprint [i][1] * footprint[i][2]
    # + footprint [i][3] * foorprint[i][4]
    # and
    # footprint[i][4] == footprint[i+1][0]
    # this two equations are key to generate the linear combination
    # of a and b so that the result will be their GCD (or GCF).
    a, b = b, a % b

    # Start work backward to compute the linear combination
    # of a and b so that this combination gives the GCD of a and b
    footprint.reverse()
    footprint.pop(0)
    #print (footprint)
    x = footprint[0][1]
    y = footprint[0][3]
    #print (x, y)
    for i in range (1, len(footprint)):
    x_temp = x
    y_temp = y
    x = y_temp * footprint[i][1]
    y = y_temp * footprint[i][3] + x_temp
    #print (x, y)

    if (isASmallerThanB != True):
    return (a, x, y)
    else:
    return (a, y, x)

    def modInv(a,m):
    '''returns the multiplicative inverse of a in modulo m as a
    positve value between zero and m-1'''
    # notice that a and m need to co-prime to each other.
    if coprime([a, m]) == False:
    return 0
    else:
    linearcombination = extendedEuclid(a, m)
    return linearcombination[1] % m

    def crt(L):
    '''takes in a list of two or more tuples, ie
    L = [(a0, n0), (a1,n1),(a2,n2)...(ak nk)]
    if the n-s are not co-prime, this function prints an error message to
    the screen and returns -1. Otherwise it continues with the Chinese
    Remainder theorem, finding a value for x to return which satisfies
    x = ai( mod ni)
    for all tuples in the list L. This value must be between 0 and N-1
    where N is the product of all the n in the list L'''
    NList = []
    for item in L:
    NList.append(item[1])
    if coprime(NList) == False:
    print ("The input is not valid!")
    return -1
    else:
    bigN = 1
    for numbers in NList:
    bigN *= numbers
    CRTresult = 0
    for item in L:
    ai = item[0]
    Ci = bigN//item[1]
    #print (Ni, ai)
    Yi = extendedEuclid(Ci, item[1])
    #print (Ci, item[1])
    CRTresult += ai * Ci * Yi[1]
    return CRTresult % bigN

    # start of second project *****************************

    def extractTwos(m):
    '''m is a positive integer. A tuple (s, d) of integers is returned
    such that m = (2 ** s) * d.'''
    # the problem can be break down to count how many '0's are there in
    # the end of bin(m). This can be done this way: m & a stretch of '1's
    # which can be represent as (2 ** n) - 1.
    assert m >= 0
    i = 0
    while m & (2 ** i) == 0:
    i += 1
    return (i, m >> i)


    def int2baseTwo(x):
    '''x is a positive integer. Convert it to base two as a list of integers
    in reverse order as a list.'''
    # repeating x >>= 1 and x & 1 will do the trick
    assert x >= 0
    bitInverse = []
    while x != 0:
    bitInverse.append(x & 1)
    x >>= 1
    return bitInverse

    def modExp(a,d,n):
    '''returns a ** d (mod n)'''
    # a faster algorithms discussed in CIT 592 class
    assert d >= 0
    assert n >= 0
    base2D = int2baseTwo(d)
    base2DLength = len(base2D)
    modArray = []
    result = 1
    for i in range (1, base2DLength + 1):
    if i == 1:
    modArray.append(a % n)
    else:
    modArray.append((modArray[i - 2] ** 2) % n)
    for i in range (0, base2DLength):
    if base2D[i] == 1:
    result *= base2D[i] * modArray[i]
    return result % n

    def millerRabin(n, k):
    '''
    Miller Rabin pseudo-prime test
    return True means likely a prime, (how sure about that, depending on k)
    return False means definitely a composite.
    Raise assertion error when n, k are not positive integers
    and n is not 1
    '''
    assert n >= 1
    # ensure n is bigger than 1
    assert k > 0
    # ensure k is a positive integer so everything down here makes sense

    if n == 2:
    return True
    # make sure to return True if n == 2

    if n % 2 == 0:
    return False
    # immediately return False for all the even numbers bigger than 2

    extract2 = extractTwos(n - 1)
    s = extract2[0]
    d = extract2[1]
    assert 2 ** s * d == n - 1

    def tryComposite(a):
    '''Inner function which will inspect whether a given witness
    will reveal the true identity of n. Will only be called within
    millerRabin'''
    x = modExp(a, d, n)
    if x == 1 or x == n - 1:
    return None
    else:
    for j in range (1,s):
    x = modExp(x, 2, n)
    if x == 1:
    return False
    elif x == n - 1:
    return None
    return False

    for i in range (0, k):
    a = random.randint(2, n - 2)
    if tryComposite(a) == False:
    return False
    return True # actually, we should return probably true.

    def primeSieve(k):
    '''return a list with length k + 1, showing if list[i] == 1, i is a prime
    else if list[i] == 0, i is a composite, if list[i] == -1, not defined'''

    def isPrime(n):
    '''return True is given number n is absolutely prime,
    return False is otherwise.'''
    for i in range(2, int(n ** 0.5) + 1):
    if n % i == 0:
    return False
    return True
    result = [-1] * (k + 1)
    for i in range(2, int(k + 1)):
    if isPrime(i):
    result[i] = 1
    else:
    result[i] = 0
    return result

    def findAPrime(a,b,k):
    '''Return a pseudo prime number roughly between a and b,
    (could be larger than b). Raise ValueError if cannot find a
    pseudo prime after 10 * ln(x) + 3 tries. '''
    x = random.randint(a, b)
    for i in range(0, int(10 * math.log(x) + 3)):
    if millerRabin(x, k):
    return x
    else:
    x += 1
    raise ValueError

    def newKey(a,b,k):
    ''' Try to find two large pseudo primes roughly between a and b.
    Generate public and private keys for RSA encryption.
    Raises ValueError if it fails to find one'''
    try:
    p = findAPrime(a, b, k)
    while True:
    q = findAPrime(a, b, k)
    if q != p:
    break
    except:
    raise ValueError
    n = p * q
    m = (p-1) * (q-1)
    while True:
    e = random.randint(1, m)
    if coprime([e, m]):
    break
    d = modInv(e, m)
    return (n, e, d)

    def string2numList(strn):
    '''Converts a string to a list of integers based on ASCII values'''
    # Note that ASCII printable characters range is 0x20 - 0x7E
    returnList = []
    for chars in strn:
    returnList.append(ord(chars))
    return returnList

    def numList2string(L):
    '''Converts a list of integers to a string based on ASCII values'''
    # Note that ASCII printable characters range is 0x20 - 0x7E
    returnList = []
    returnString = ''
    for nums in L:
    returnString += chr(nums)
    return returnString

    def numList2blocks(L,n):
    '''Take a list of integers(each between 0 and 127), and combines them into block size
    n using base 256. If len(L) % n != 0, use some random junk to fill L to make it '''
    # Note that ASCII printable characters range is 0x20 - 0x7E
    returnList = []
    toProcess = copy.copy(L)
    if len(toProcess) % n != 0:
    for i in range (0, n - len(toProcess) % n):
    toProcess.append(random.randint(32, 126))
    for i in range(0, len(toProcess), n):
    block = 0
    for j in range(0, n):
    block += toProcess[i + j] << (8 * (n - j - 1))
    returnList.append(block)
    return returnList

    def blocks2numList(blocks,n):
    '''inverse function of numList2blocks.'''
    toProcess = copy.copy(blocks)
    returnList = []
    for numBlock in toProcess:
    inner = []
    for i in range(0, n):
    inner.append(numBlock % 256)
    numBlock >>= 8
    inner.reverse()
    returnList.extend(inner)
    return returnList

    def encrypt(message, modN, e, blockSize):
    '''given a string message, public keys and blockSize, encrypt using
    RSA algorithms.'''
    cipher = []
    numList = string2numList(message)
    numBlocks = numList2blocks(numList, blockSize)
    for blocks in numBlocks:
    cipher.append(modExp(blocks, e, modN))
    return cipher

    def decrypt(secret, modN, d, blockSize):
    '''reverse function of encrypt'''
    numBlocks = []
    numList = []
    for blocks in secret:
    numBlocks.append(modExp(blocks, d, modN))
    numList = blocks2numList(numBlocks, blockSize)
    message = numList2string(numList)
    return message

    if __name__=='__main__':
    (n, e, d) = newKey(10**100, 10**101, 50)
    print ('n = {0}'.format(n))
    print ('e = {0}'.format(e))
    print ('d = {0}'.format(d))
    message = '''We were the Leopards, the Lions, those who'll take our place will be little jackals, hyenas; But we'll go on thinking ourselves the salt of the earth.'''
    print(message)
    cipher = encrypt(message, n, e, 15)
    print(cipher)
    Amessage = decrypt(cipher, n, d, 15)
    print(Amessage)