Week 11: From Object-Oriented to Functional Programming
DSAN 5500: Data Structures, Objects, and Algorithms in Python
Class Sessions
Schedule
Today’s Planned Schedule:
| Start | End | Topic | |
|---|---|---|---|
| Lecture | 6:30pm | 7:30pm | First Things First: The One-Time Pad Cryptosystem → |
| 7:30pm | 8:00pm | Beyond Embarrassingly Parallel → | |
| Break! | 8:00pm | 8:10pm | |
| 8:10pm | 9:00pm | Data Mining in Parallel → |
First Things First: Cryptosystem Roadmap
| 👍 | 👎 | |
|---|---|---|
| One-Time Pad | Provably perfectly(!) secure ✅ | Requires establishing a single shared (symmetric) key |
| RSA / Diffie-Hellman / ElGamal | Provably secure (via NP-hardness of prime factorization) ✅ | Restarts sometimes required; key sizes have to grow exponentially bc Moore’s Law |
| Elliptic Curve Cryptography | Provably secure (discrete logarithm NP-hard) ✅ | [Still 👍] Smaller key sizes: 256-bit ECC \(\approx\) 3072-bit RSA |
| Throughout: Public keys, secret keys, signatures, etc., are all functions! \(\leadsto\) Functional Programming |
||
The One-Time Pad Cryptosystem
- Alice wants to be able to send Bob a single message \(m\) sometime in the future, which cannot be decrypted by an eavesdropper Eve (can only be decrypted by Bob)
- Alice and Bob agree in advance (OTP is a symmetric-key cryptosystem, as opposed to public-key) on a randomly-generated \(n\)-bit key \(k\), where \(n\) is the same length in bits as \(m\): \(n = |k| = |m|\)
- When \(m\) is ready to send, Alice takes the
XORof the bits of \(m\) and the bits of \(k\) to produce the ciphertext \(c = k \oplus m\) - Claim: Eve cannot do better than random guessing, while Bob can decode instantly!
Quick Proof
Secure if \(\Pr(M=m \mid C=c) = \Pr(M=m)\). First: the prior \(\Pr(C = c)\):
\[ \begin{aligned} \Pr(C=c) &= \sum{\Pr(C=c \mid M=m')\cdot \Pr(M=m')} \\ &=\sum{\Pr(K=m' \oplus c)}\cdot \Pr(M=m') \\ &= \sum{2^{-n}}\cdot \Pr(M=m') =2^{-n} \end{aligned} \]
…Bayes Theorem!
\[ \begin{aligned} \Pr(M=m \mid C=c) &= \frac{\Pr(C=c \mid M=m)\cdot \Pr(M=m)}{\Pr(C=c)} \\ &= \frac{\Pr(k=m \oplus c)\cdot \Pr(M=m)}{2^{-n}} \\ &= \frac{2^{-n}\cdot \Pr(M=m)}{2^{-n}} =\Pr(M=m) \end{aligned} \]