§16 RSA Encryption

Plain/Textbook RSA Encryption Scheme

1. $Gen$: On input $1^n$, Run $GenRSA(1^n)$ to obtain $(N, e, d)$.

   The public key is $\langle N, e\rangle$, and the private key is $\langle N, d\rangle$.

2. $Enc$: Given inputs $pk = \langle N, e\rangle$, and $m \in \mathbb{Z}^*_N$,

   Output the ciphertext $c := [m^e \bmod N]$.

3. $Dec$: Given inputs $sk = \langle N, d\rangle$, and ciphertext $c \in \mathbb{Z}^*_N$,

   Output the message as $\hat{m} := [c^d \bmod N]$.

Attacks on Plain RSA for Longer Messages (Coppersmith)

• Theorem (Coppersmith). Let $p(x)$ be a polynomial of degree $e$. Then in time $poly(\|N\|, e)$, one can find all $m$ such that $p(m) = 0 \bmod N$ and $|m| \le N^{1/e}$.

Padded RSA Encryption Scheme

1. $Gen$: On input $1^n$, Run $GenRSA(1^n)$ to obtain $(N, e, d)$.

   The public key is $\langle N, e\rangle$, and the private key is $\langle N, d\rangle$.

2. $Enc$: On inputs $pk = \langle N, e\rangle$, and $m \in \{0,1\}^{\| N\| -l(n)-2}$, where $l(n) \le 2n - 4$, choose uniform string $r \in \{0,1\}^{l(n)}$, and interpret $\hat{m} := r\|m$ as an element of $\mathbb{Z}^*_N$.

   Output the ciphertext $c := [\hat{m}^e \bmod N]$.

3. $Dec$: On inputs $sk = \langle N, d\rangle$, and ciphertext $c \in \mathbb{Z}^*_N$, compute $\hat{m} := [c^d \bmod N]$ ,

   Output the $\| N\| -l(n)-2$ least significant bits of $\hat{m}$.

— Mar 31, 2023

§16 RSA Encryption by Lu Meng is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. Permissions beyond the scope of this license may be available at About.