#!/usr/bin/env python
# coding: utf-8

# [Home](Home.ipynb) <br/>
# [Crypto](Crypto.ipynb)
# 
# # Euclid's Extended Algorithm (EEA)
# 
# While in the process of discovering the gcd of two numbers, a and b, it's possible, at the same time, to extract two additional integers, m and n, such that: 
# 
# $$
# a\ m + b\ n = gcd(a, b)
# $$
# 
# m or n will be negative.
# 
# The idea is two multiples of a and b (say m and n) will get them within one GCD of one another, i.e. the GCD brick will divide both a and b bricks (by definition), so there's a way to stack a and b side by side such that the only difference in height between the two stacks is their greatest in-common divisor.

# In[1]:


def gcd(a, b):
    """
    Recursive version of gcd
    """
    if b == 0:  # no remainder, b (now a) was gcd
        return a
    return gcd(b, a%b)


# In[2]:


gcd(20, 170)


# In[3]:


def xgcd(a, b):
    """
    Extended Euclidean Alg.
    
    take positive integers a, b as input, and return 
    a triple (g, x, y), such that ax + by = g = gcd(a, b).
    """
    x0, x1, y0, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return  a, x0, y0


# In[4]:


a, b = 100, 85
gcd_, m, n = xgcd(a, b)
gcd_, m, n


# The GCD is the leftmost number, then come m and n such that:

# In[5]:


a * m + b * n == gcd(a, b)


# In[6]:


a, b = 14, 17
gcd_, m, n = xgcd(a, b)
gcd_, m, n


# In[7]:


a * m + b * n == gcd(a, b)


# In[8]:


def invmod(a, N):
    """
    What is the multiplicative inverse of a, inv_a,
    such that a * inv_a = 1 mod N.
    """
    return xgcd(a, N)[1] % N  # inv_a (gcd is 1, a * x0 + N * x1 = 1)


# In[9]:


invmod(14, 17) # what number times 14, mod 17, is 1?


# In[10]:


(14 * 11) % 17


# In[11]:


invmod(3, 17)


# In[12]:


(3 * 6) % 17


# Lets see where ```invmod``` fits in to the [RSA](RSA.ipynb) algorithm.

# In[13]:


p = 593
q = 601
N = p * q  # public key comprised of two primes
N


# In[14]:


phiN = (p-1)*(q-1)  # phi(ab)=phi(a)phi(b)
phiN


# In[15]:


e = 17
d = invmod(e, phiN) # what is e's multiplicative inverse mod phiN?
d


# In[16]:


e * d


# In[17]:


(e*d) % phiN


# But what size public keys are we really talking about?

# In[18]:


RSA232 = \
17969491597941066732916128449573246156367561808012600070888918835531726460341490933493372247868650755230855864199929221814436684722874052065257937495694348389263171152522525654410980819170611742509702440718010364831638288518852689
p = 4528450358010492026612439739120166758911246047493700040073956759261590397250033699357694507193523000343088601688589
q = 3968132623150957588532394439049887341769533966621957829426966084093049516953598120833228447171744337427374763106901

if RSA232 == p*q:
    print("Check!")


# In[19]:


hex(RSA232)[2:]


# In[20]:


N = RSA232
phiN = (p-1)*(q-1) # 𝜙(a * b) = 𝜙(a) * 𝜙(b) if a, b coprime, 𝜙(p) = p-1 if p prime


# In[21]:


e = 17
d = invmod(e, phiN) # what d, multiplied by e, will be 1 mod phiN?


# In[22]:


d  # secret key (stays safe with the public key holder)


# In[23]:


m = int(bytes.hex(b'attack at dawn!'), 16)
c = pow(m, e, N)  # encrypt using N


# In[24]:


outcome = pow(c, d, N)  # decrypt using d
bytes.fromhex(hex(outcome)[2:])