Week 10: Cryptographic Hash Functions: RSA and Diffie-Hellman
DSAN 5500: Data Structures, Objects, and Algorithms in Python
Schedule
Today’s Planned Schedule:
| Start | End | Topic | |
|---|---|---|---|
| Lecture | 6:30pm | 7:00pm | JupyterHub and Final Project → |
| 7:00pm | 7:30pm | Prefect Intro Part 2 → | |
| 7:30pm | 8:00pm | Data Mining Intro → | |
| Break! | 8:00pm | 8:10pm | |
| 8:10pm | 9:00pm | Data Mining in Parallel → |
Cryptographic Algorithms
- RSA
- Elliptic-Curve Cryptography
The RSA Algorithm
The RSA public-key cryptosystem relies on the dramatic difference between the ease of finding large prime numbers and the difficulty of factoring the product of two large prime numbers [@cormen_introduction_2001, §31.7]
Task 1: Encrypting a Message
- Public Keys \(P_A\) and Secret Keys \(S_A\) are inverses:
\[ \begin{aligned} M &= S_A(P_A(M)) \\ M &= P_A(S_A(M)) \end{aligned} \]
- Alice, and only Alice, is able to compute the function \(S_ A(\cdot)\) in any practical amount of time!
- Bob \(\overset{M}{\rightarrow}\) Alice: Bob computes \(C = P_A(M)\) and sends \(C\) to Alice; Alice obtains \(M\) via \(S_A(C) = S_A(P_A(M)) = M\)
Task 2: Signing a Message!
- Alice computes her digital signature \(\sigma = S_A(M')\), then sends the pair \((M', \sigma)\) \(\rightarrow\) Bob
- When Bob receives \((M', \sigma)\), he verifies that it originated from Alice by using Alice’s public key to check \(M' = P_A(\sigma)\)
So How Do \(P_A\) and \(S_A\) Work?
- Pick two big prime numbers \(p\) and \(q\), compute \(n = pq\)
- Pick a small odd int \(e\) relatively prime to \((p-1)(q-1)\)
- Find \(d\) such that \(de \equiv 1\text{ mod }{n}\)
- Your public key is \(P = (e,n)\)
- Your secret key is \(S = (d,n)\)
- Encrypt: \(P(M) = M^e \text{ mod }{n}\); Decrypt: \(S(C) = C^d \text{ mod }{n}\)
- Works because \(P(S(M)) = S(P(M)) = M^{ed} \overset{\small{*}}{=} M\)
Why Algorithmic Complexity Matters Here!
The security of the RSA cryptosystem rests in large part on the difficulty of factoring large integers.
If an adversary can factor the modulus \(n\) in a public key, they can derive the secret key from the public key, using the knowledge of the factors \(p\) and \(q\) in the same way that the creator of the public key used them.
Therefore, if factoring large integers is easy, then breaking the RSA cryptosystem is easy.
The converse statement, that if factoring large integers is hard, then breaking RSA is hard, is unproven (\(P \overset{\smash{\small{?}}}{\small{=}} NP\))