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

# [Home](Home.ipynb) <br/>
# [Crypto](Crypto.ipynb)
# 
# # RSA Algorithm
# 
# RSA gets focus in this curriculum because of the number and group theory concepts it ties together, not only because it's still heavily used as a part of the Web's security layer (SSL/TLS).  
# 
# A similar curriculum might swap out RSA for ECC (Elliptic Curve Cryptography), which plays the same role in web browsers, and adjust other curriculum segments accordingly.
# 
# Even if RSA gradually gives way to ECC, understanding how and why it works remains a valuable source of insights into the inner workings of important algorithms.
# 
# ### RSA History
# 
# The essentials of RSA were first discovered by cryptographers working for GHCQ, a UK institution.  
# 
# The algorithm was kept secret at that point, for fear of aiding some generic enemy.  Unleashing it upon the world could have unforeseen consequences.  World War 2, in which cryptography had played a major role, was still close behind in the rear view mirror.
# 
# The acronym RSA is made of the initial letters of the surnames of Ron Rivest (cryptographer and professor at MIT), Adi Shamir (Israeli Cryptographer), and Leonard Adleman (American computer scientist), who first publicly described the algorithm in 1978.
# 
# The community which developed and promoted the RSA algorithm was not beholden to GHCQ and resisted the NSA's efforts to keep a lid on it.  
# 
# Phil Zimmerman helped popularize and spread the whole idea of public key crypto, if not RSA in particular.
# 
# The web was emerging and businesses needed to offer a secure way to encrypt transactions.  The commercial sector needed this technology.
# 
# Pubic key cryptography had come of age.

# RSA depends on components introduced elsewhere in this text, most notably:
# 
# * [the concept of prime versus composite](Crypto.ipynb)
# * [the concepts of totatives and totients](Crypto.ipynb)
# * [Euler's Theorem involving the totient](Euler.ipynb)
# * [Euclid's Extended Algorithm (EEA)](EEA.ipynb)
# * [Review of RSA in context](https://nbviewer.jupyter.org/github/4dsolutions/School_of_Tomorrow/blob/master/NumberTheory.ipynb) (School of Tomorrow)

# In[1]:


from IPython.display import YouTubeVideo


# Curate your own Youtubes?

# In[2]:


# %load ./primes/rsacrypto_test.py
#!/usr/bin/env python3
"""
Created on Sat Dec  2 21:07:56 2017

@author: Kirby Urner

conda install pycrypto
pip3 install pycrypto

https://www.dlitz.net/software/pycrypto/

Here's a bug that we hit:
https://github.com/pycrypto/pycrypto/issues/308

Note that OpenSSL is the more frequently used not-Python
util, run from the OS command line.
"""

from primes import invmod

import Crypto.PublicKey.RSA as rsa

def generating(s):
    print("Generating: ", s, end="")
    
rsaobj = rsa.generate(1024, progress_func=generating, e=17)

print(rsaobj)

p = rsaobj.p  # prime1
q = rsaobj.q  # prime2
n = rsaobj.n  # public key (p * q)
e = rsaobj.e  # public encrypt exponent
d = rsaobj.d  # secret decrypt key

def test_n():
    return p*q == n

def test_inverse():
    return d == invmod(e, (p-1)*(q-1))
    
def test_euler():
    totient_of_n = (p-1)*(q-1)
    return (e*d) % totient_of_n == 1

def test_decrypt():
    plaintext = b"able was i ere i saw elba"  # famous palindrome
    ciphertext = rsaobj.encrypt(plaintext, b"K")
    return rsaobj.decrypt(ciphertext[0]) == plaintext


# In[3]:


test_inverse()


# In[4]:


get_ipython().run_line_magic('pinfo2', ' rsaobj.encrypt')


# In[5]:


c = rsaobj.encrypt(b"attack at dawn", b"K")


# In[6]:


c


# In[7]:


rsaobj.decrypt(c[0])


# In[8]:


p * q


# In[9]:


pow(5, 3, 20)


# In[10]:


5**3


# In[11]:


125//20


# In[12]:


125 - 6


# In[13]:


5 * 5 * 5 % 20


# In[14]:


pow(88398934597, 17, 82038745020938)


# In[ ]: