#!/usr/bin/python3
import random

'''
-------------------------------------------------------
RSA 
-------------------------------------------------------

#----------------------------------------------------------------
Fermat's little Theorem (p1): 
Let p be any prime, a any integer, then a**p = a mod p 
#----------------------------------------------------------------

#----------------------------------------------------------------
Fermat's little Theorem (p2): 
Let p be any prime, a any integer such that p does not divide a
then a**(p-1) = 1 mod p
#----------------------------------------------------------------

#----------------------------------------------------------------
RSA Fundamental Theorem:
Let p,q be any prime numbers. Let m in N be s.t. gcd(m,p*q)=1
then m**((p-1)*(q-1))=1 mod (p*q)

{0,1,2,...,,m,..,(p*q)-1}

#----------------------------------------------------------------
Note: 
m**(1+(p-1)*(q-1))=m mod (p*q)
m**((p-1)*(q-1))=1 mod (p*q) => m**(k*(p-1)*(q-1))=1 mod (p*q)
Also
m**(1+k*(p-1)*(q-1))=m mod (p*q)

This suggests a crypto system.

Find e,d such that 1=e*d+k*(p-1)*(q-1), that is...
e*d = 1-k*(p-1)*(q-1)

m**e
{0,1,2,m**e,...,m,..,(p*q)-1}

(m**e)**d = m
{0,1,2,m**e,...,m,..,(p*q)-1}

Then you can encrypt with 

m**e mod (p*q) and decrypt with (m**e)**d mod (p*q)

RSA is the following...

0) Choose large primes p and q
   FACT: Can find large primes quickly.

1) Choose encryption key e in 1,...,(p-1)*(q-1)
   such that gcd(e,(p-1)*(q-1))=1

   1 = e*d+k(p-1)(q-1)
   e*d=1-k(p-1)(q-1)

2) Extended Euclidean Algorithm says that 

   if gcd(x,y)=z then we can find a,b in Z such that
   z = a*x+b*y

   In our setting, we have 
   if gcd(e,(p-1)*(q-1))=1 then we can find d,k in Z such that
   1 = d*e+k*(p-1)*(q-1)

   that is e*d = 1 - k*(p-1)*(q-1)

   FACT: Extended Euclidean Algorithm says Can find d from e easily (=quickly)

3) Keys:

   public_key = (e,p*q)
   private_key = (d,p*q)

4) Encrypt
   c = (m**e)%(p*q)

5) Decrypt
   Lets decrypt...
   (c**d)%(p*q) = ((m**e)**d)%(p*q) 
                = (m**(e*d))%(p*q)
                = (m**(1+k*(p-1)*(q-1))%(p*q)
                = (m*m**(k*(p-1)*(q-1))%(p*q)
                = (m*(m**((p-1)*(q-1)))**k %(p*q)
                = m*(1**k) %(p*q)
                = m

EXERCISE: Compute (x**y)%n quickly. Python has pow function for this.

--------------------------------------------------------
Security of RSA
--------------------------------------------------------
Say Eve intercepts cyphertext c

Eve
Knows                       Doesn't Know
c
(e,n)                       (d,n)


The equations...
e*d = 1 mod (p-1)*(q-1)
n = p*q
without knowing d,p,q

It seems that Eve needs to find
(p-1) and (q-1)
to do this, Eve seems to need to find
p,q such that p*q = n

That is, to factor n. 

FACT: No one knows a fast way to factor in general (YET). 

FACT: Factoring is in NP intersect CoNP, everything in NP intersect
CoNP has fallen to P so far. This is a worry.

Example:

import rsa
rsa.rsa_keys(61519, 61561   )
((675825377, 3787171159), (3601085393, 3787171159))
rsa.encrypt(1234, (675825377, 3787171159))
3615735883L
rsa.decrypt(3615735883L, (3601085393, 3787171159))
1234L
'''