cryptanalysis_scripts/lib/gcd_tables.py

'''
Source: extendedeuclideanalgorithm.com

Modified to generate CSV tables
for iterative calculation of the modular inverse
'''

import math


# Warning: can't handle b=0. See extendedeuclideanalgorithm.com/code for a version that can
def gcd_iterative(a, b):
    """ Calculating the greatest common divisor
    using the Euclidean Algorithm (non-recursive)
    (Source: extendedeuclideanalgorithm.com/code)
    """

    # Set default values for the quotient and the remainder
    q = 0
    r = 1

    '''
    In each iteration of the loop below, we
    calculate the new quotient, remainder, a and b.
    r decreases, so we stop when r = 0 
    '''
    while (r > 0):
        # The calculations
        q = math.floor(a / b)
        r = a - q * b

        # The values for the next iteration
        a = b
        b = r if (r > 0) else b

    return abs(b)


# Can handle b=0
def gcd_iterative_2(a, b):
    """ Calculating the greatest common divisor
    using the Euclidean Algorithm (non-recursive)
    (Source: extendedeuclideanalgorithm.com/code)
    """

    # Set default values for the quotient and the remainder
    q = 0
    r = 1

    '''
    In each iteration of the loop below, we
    calculate the new quotient, remainder, a and b.
    r decreases, so we stop when r = 0 
    '''
    while (b > 0):
        # The calculations
        q = math.floor(a / b)
        r = a - q * b

        # The values for the next iteration
        a = b
        b = r

    return abs(a)


def gcd(a, b):
    """ Calculating the greatest common divisor
    using the Euclidean Algorithm (recursive)
    (Source: extendedeuclideanalgorithm.com/code)
    """
    if (b == 0):
        return abs(a)

    q = math.floor(a / b)
    r = a - q * b
    return abs(b) if (r == 0) else gcd(b, r)


# Warning: this version can't handle b=0. See extendedeuclideanalgorithm.com/code for a version that can.
def xgcd_iterative(a, b):
    """ Calculates the gcd and Bezout coefficients,
    using the Extended Euclidean Algorithm (non-recursive).
    (Source: extendedeuclideanalgorithm.com/code)
    """
    # Set default values for the quotient, remainder,
    # s-variables and t-variables
    q = 0
    r = 1
    s1 = 1
    s2 = 0
    s3 = 1
    t1 = 0
    t2 = 1
    t3 = 0

    '''
    In each iteration of the loop below, we
    calculate the new quotient, remainder, a, b,
    and the new s-variables and t-variables.
    r decreases, so we stop when r = 0
    '''
    while (r > 0):
        # The calculations
        q = math.floor(a / b)
        r = a - q * b
        s3 = s1 - q * s2
        t3 = t1 - q * t2

        '''
        The values for the next iteration, 
        (but only if there is a next iteration)
        '''
        if (r > 0):
            a = b
            b = r
            s1 = s2
            s2 = s3
            t1 = t2
            t2 = t3

    return abs(b), s2, t2


# Can handle b=0
def xgcd_iterative_2(a, b):
    """ Calculates the gcd and Bezout coefficients,
    using the Extended Euclidean Algorithm (non-recursive).
    (Source: extendedeuclideanalgorithm.com/code)
    """
    # Set default values for the quotient, remainder,
    # s-variables and t-variables
    q = 0
    r = 1
    s1 = 1
    s2 = 0
    s3 = 1
    t1 = 0
    t2 = 1
    t3 = 0

    '''
    In each iteration of the loop below, we
    calculate the new quotient, remainder, a, b,
    and the new s-variables and t-variables.
    r decreases, so we stop when r = 0
    '''

    # CSV output
    print("i, n, b, q, r, t1, t2, t3")
    i = 1

    while (b > 0):
        # The calculations
        q = math.floor(a / b)
        r = a - q * b
        s3 = s1 - q * s2
        t3 = t1 - q * t2

        # CSV output
        print("{}, {}, {}, {}, {}, {}, {}, {}".format(i, a, b, q, r, t1, t2, t3))
        i += 1

        '''
        The values for the next iteration, 
        (but only if there is a next iteration)
        '''

        a = b
        b = r
        s1 = s2
        s2 = s3
        t1 = t2
        t2 = t3

    return abs(a), s1, t1


def xgcd(a, b, s1=1, s2=0, t1=0, t2=1):
    """ Calculates the gcd and Bezout coefficients,
    using the Extended Euclidean Algorithm (recursive).
    (Source: extendedeuclideanalgorithm.com/code)
    """
    if (b == 0):
        return abs(a), 1, 0

    q = math.floor(a / b)
    r = a - q * b
    s3 = s1 - q * s2
    t3 = t1 - q * t2

    # if r==0, then b will be the gcd and s2, t2 the Bezout coefficients
    return (abs(b), s2, t2) if (r == 0) else xgcd(b, r, s2, s3, t2, t3)


def multinv(b, n):
    """
    Calculates the multiplicative inverse of a number b mod n,
    using the Extended Euclidean Algorithm. If b does not have a
    multiplicative inverse mod n, then throw an exception.
    (Source: extendedeuclideanalgorithm.com/code)
    """

    # Get the gcd and the second Bezout coefficient (t)
    # from the Extended Euclidean Algorithm. (We don't need s)
    my_gcd, _, t = xgcd(n, b)

    # It only has a multiplicative inverse if the gcd is 1
    if (my_gcd == 1):
        return t % n
    else:
        raise ValueError('{} has no multiplicative inverse modulo {}'.format(b, n))


def make_eea_table(a : int, b : int):


    '''
    Euclidean algorithm:
    see the output of gcd(a, b)
    '''
    print('Euclidean Algorithm:')
    print('The gcd of', a, 'and', b, 'is', gcd(a, b))

    # -------------------------------------------------------------

    '''
    Extended Euclidean Algorithm:
    see the output of xgcd(a,b) and Bezout coefficients
    And verify that they are correct
    '''
    my_gcd, s, t = xgcd(a, b)
    verification = abs(s * a + t * b)
    print('Extended Euclidean Algorithm:')
    print('The gcd of', a, 'and', b, 'is', my_gcd)
    print('And the Bezout coefficients: s=', s, ' and t=', t, '.', sep='')
    print('And', s, '*', a, '+', t, '*', b, '=', verification)
    if (my_gcd == verification):
        print('So as we expect, s*a+t*b is equal to the gcd we found.')
    else:
        print('Something went wrong')

    # ------------------------------------------------------------
    b = b
    n = a

    '''
    Multiplicative Inverse:
    Try to compute the multiplicative inverse of b mod n.
    If that succeeds, verify that it's correct.
    If it doesn't succeed, show the error raised by the function.
    '''

    print('Multiplicative inverse:')
    try:
        # inverse = multinv(b, n);
        inverse = xgcd_iterative_2(b, n)

    except ValueError as error:
        print(error)