1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
Brief summary of RSA algorithm / crypto system
----------------------------------------------
# https://www.cs.utexas.edu/~mitra/honors/soln.html
Choose 2 large, random prime numbers, p and q.
n = p * q
phi = (p-1) * (q-1)
Choose e, such that `1 < e < phi` and e and phi are coprime (*) (**) (***)
Compute d, such that `e * d mod phi == 1` (****)
Public key = (e, n)
Private key = (d, n)
cyphertext = plaintext ^ e mod n
plaintext = cyphertext ^ d mod n
(*) It is important for e and phi to be coprime, to prevent ambiguous
decryption. See https://crypto.stackexchange.com/questions/12255/
(**) A very common value for e is (the prime) 65537
(***) RSA can become more vulnerable to cracking with low values of e.
See https://crypto.stackexchange.com/questions/6713/.
TODO: Explain the attack here.
(****) Calculate d using modular inverse (see below...)
Python tips
-----------
Implementations for fast modular exponentiation and modular inverse already
exist in Python, via the pow() function.
pow() supports a third argument, which is the modulus value: pow(b, e, n).
To perform fast mod expo for encryption, use pow(plaintext, e, n)
... for decryption, use pow(cyphertext, d, n)
To calculate mod inverse, use pow(e, -1, phi).
Extras
------
http://factordb.com/
|
