# -*- coding: utf-8 -*-
"""
Jacob Ashcraft
RSA Algorithm 2
Advanced Algorithms
Professor Teichert
"""

import math

###################### Constants ######################
primes = [110487089277121433970806926710031676468486143869889341376537597422615205558243704080712263653321436167325483283204907700784269778678235765655575460395889011454420593249613544746847538771207567936708769996331073519534473553554551955740383672215173780402123114087748349892379946461583339352705980347602551070771,
111071162799851912824654144483111874424614301938282297067047351983888441559266175769409398076565391663380417335011869271890831362225479632276860946599190038665921626623960557268331733202620352289428928091329109593819133932848528111395029428743390425837597001656830061559982062375737093320355405637563615886803,
121497340871047561990526349313922431040502436205277029161504074265656522318180600371526800734743195781676485261271407335077142141062183325700299129778874273734144338622599487090131017655398226759216026150060144849693132978936886491999493651200251158512013123761065143321228864622882636292486361150032268778811,
129485023332071707933738382916401449533641429854401982997094004590315877456171636358095039465240846827538029950571129593738792376890229674390327761144443983750216503536908345315421877704009030386457606021982880563161989106528276736547445291897101752828333504822305817794362568577622132836880295842256828790663,
153715834450489562463849837675877072003597968603772497851993838998671736216460867072809004851853984784500916582056424506818121582249876434026855099884649811135710709303203754995652355774351958175103715494697141939913847139824283438873455911864292614373543989722102037383089106515386884300815378110108716900969,
174936522803921418571387048546144057648483486437030569660913986547830736401921573836149603460433706344137498637531461621214146833189489981579451352331285554371733332543772088955179877027166430734220696794537447498152611353914320533702480407937301402657378278430173894544681733621258698183254290589113435098079]

message = 55541289226857863698741188454555

###################### Methods ######################
def gcd(a, b):
    """
    This is gcd algorithm is the same as the extEuclids.
    """
    if b == 0:
        return 1, 0, a
    else:
        x,y,d = gcd(b, a % b)
        return y, (x-y*(a//b)), d

def powMod(base, power, mod):
    powerPart = 1
    base = base % mod
    while power > 0:
        if (power & 1) == 1:
            powerPart = (powerPart * base) % mod
        power = power >> 1
        base = (base * base) % mod

    return powerPart
    # if power == 0:
    #     return 1
    # z = powMod(base, power//2, mod)
    # if power % 2 == 0:
    #     return z*z % mod
    # else:
    #     return base*z*z % mod


def multInverse(a, b):
    x, y, d = gcd(a, b)

    if d != 1:
        print("Inverse doesn't exist")
        return
    return x % b

def privatKeyGen(p, q, e):
    return p*q, multInverse(e, (p-1) * (q-1))

# p is message, q is public key, n is some big prime
def encrypt(p, q, n):
    cipher = powMod(p, q, n)
    #Return the array of bytes
    return cipher


# p is the cipher, q is private key, n is some big prime
def decrypt(p, q, n):
    plain = powMod(p, q, n)
    #Return the array of bytes as a string
    return plain


###################### TESTS ######################
def test_gcd():
    assert gcd(16, 8) == (0, 1, 8)
    assert gcd(121, 11) == (0, 1, 11)
    assert gcd(1, 213) == (1, 0, 1)

def test_powMod():
    assert powMod(35,78,22) == (35**78 % 22)
    assert powMod(13,3,55) == (13**3 % 55)
    assert powMod(13,3,55) == 52

def test_multInverse():
    assert multInverse(7, 3) == 1
    assert multInverse(3, 4) == 3
    assert multInverse(5, 29) == 6

def test_encrypt():
    assert encrypt(13, 3, 55) == 52
    
def test_decrypt():
    val = encrypt(13, 3, 55)
    assert decrypt(val, 27, 55) == 13

def test_all():
    p = primes[0]
    q = primes[1]
    e = primes[2]
    n, d = privatKeyGen(p,q,e)
    encryption = encrypt(message, e, n)
    decryption = decrypt(encryption, d, n)
    assert decryption == message