Week 10: Cryptographic Hash Functions: RSA and Diffie-Hellman

DSAN 5500: Data Structures, Objects, and Algorithms in Python

Jeff Jacobs

jj1088@georgetown.edu

Thursday, March 19, 2026

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]

Bob encrypts \(M\) using Alice’s public key \(P_A\) and transmits the result \(C = P_A(M)\) over a communication channel to Alice. An eavesdropper who captures \(C\) gains no info about \(M\). Alice decrypts \(C\) using her secret key to obtain the original message: \(M = S_A(C)\)

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\))

References