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.
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:
from IPython.display import YouTubeVideo
Curate your own Youtubes?
# %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
Generating: p,q Generating: u Generating: d <_RSAobj @0x7f92f1e09280 n(1024),e,d,p,q,u,private>
test_inverse()
True
?? rsaobj.encrypt
Signature: rsaobj.encrypt(plaintext, K) Source: def encrypt(self, plaintext, K): """Encrypt a piece of data with RSA. :Parameter plaintext: The piece of data to encrypt with RSA. It may not be numerically larger than the RSA module (**n**). :Type plaintext: byte string or long :Parameter K: A random parameter (*for compatibility only. This value will be ignored*) :Type K: byte string or long :attention: this function performs the plain, primitive RSA encryption (*textbook*). In real applications, you always need to use proper cryptographic padding, and you should not directly encrypt data with this method. Failure to do so may lead to security vulnerabilities. It is recommended to use modules `Crypto.Cipher.PKCS1_OAEP` or `Crypto.Cipher.PKCS1_v1_5` instead. :Return: A tuple with two items. The first item is the ciphertext of the same type as the plaintext (string or long). The second item is always None. """ return pubkey.pubkey.encrypt(self, plaintext, K) File: ~/opt/anaconda3/lib/python3.9/site-packages/Crypto/PublicKey/RSA.py Type: method
c = rsaobj.encrypt(b"attack at dawn", b"K")
c
(b'+\xe2?A\x98\xb7O\x12\xa7\xb7\x05\xa9\xff\xfc\xd9\xde+\x03\xf8<\xeb\x944S\x10\x133\xcas\xa1#2\xa9J\xa4C\xd8\x1cX\xa6\xef\xcd9\xe7\xe3O J\x87\x87\x8cd@\xebo\x84\x17m\xf4F}B\xaf\x8a\x10n5\x7f\xa0\x8cc\xa1\x14l\xd1u`g\xe7e@\xfc^\xfb\x02qb\xbc\x07\rW\xd1@\x9a\xea\rz-\xe5\xa63\xac\x14\x81B\xd2sQe\x962Z\x8cM\xd1\xcb\xba\xe9\xd5\xe9X\xf0\xc4de\x9e\xde\xff',)
rsaobj.decrypt(c[0])
b'attack at dawn'
p * q
119353861243195446712675417770765824146975929069972250977091366093077385007699140626386330849234727126824758974147300218181130989174493410358646750159312997463360803438555963304411631399770295820887714785985874918809627514592173675448803051682476954425774027952044754491664338823260108968934257096925158099009
pow(5, 3, 20)
5
5**3
125
125//20
6
125 - 6
119
5 * 5 * 5 % 20
5
pow(88398934597, 17, 82038745020938)
12354891489645