Notes - Computer Security MT24, Rabin cryptosystem

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 has message $m$.
• Calculate $D _ {sk _ B} := \sqrt m \pmod n$ (this is easy with knowledge of $p$ and $q$, but difficult otherwise).
• Discard padding.

• 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$.