# Notes - Computer Security MT24, Rabin cryptosystem

> Source: https://ollybritton.com/notes/uni/part-b/mt24/computer-security/notes/rabin-cryptosystem/ · Updated: 2025-06-03 · Tags: uni, notes

- [Course - Computer Security MT24](https://ollybritton.com/notes/uni/part-b/mt24/computer-security/)
	- [Notes - Computer Security MT24, Asymmetric key ciphers](https://ollybritton.com/notes/uni/part-b/mt24/computer-security/notes/asymmetric-key-ciphers/)

### Flashcards
Describe the Rabin public-key encryption @algorithm by explaining how Alice would send a message to Bob, and how Bob would generate his keys.::

**Key generation**:

- Bob generates two large primes $p$ and $q$.
- Let $n = pq$.
- The public key is $pk_B = n$.
- The private key is $sk_B = \langle p, q \rangle$.

**Encryption**:

- Alice has message $m$.
- Pad $m$.
- Calculate $E _ {pk _ B}(m) := m^2 \pmod n$.

**Decryption**:

- Bob receives ciphertext $c$.
- Calculate $D _ {sk _ B}(c) := \sqrt c \pmod n$ (this is easy with knowledge of $p$ and $q$, but difficult otherwise).
- (Technically, there are 4 possible square roots, so Alice would've also needed to include something extra in her message to tell Bob which message it was).
- Discard padding.

What "trapdoor function" does the Rabin public-key encryption algorithm make use of?::

- Easy: Given $n$, it is easy to compute $m^2 \pmod n$ from $m$.
- Difficult: Find $m$ given $m^2 \pmod n$.
- Easy with extra info: Given the factors of $n$, it is easy to find $m$ given $m^2 \pmod n$.

---
Olly Britton — https://ollybritton.com. Machine-readable index: https://ollybritton.com/llms.txt