# RSA-based Encryption#

## RSA assumption#

Definition (The RSA problem)

Given a modulus $$N$$ and an integer $$e>2$$ relatively prime to $$\phi(N)$$, to compute $$\left[y^{1 / e} \bmod N\right]$$ for a modulus $$N$$ of unknown factorization.

Algorithm (RSA key generation GenRSA)

Input: Security parameter $$1^{n}$$

Output: $$N, e, d$$

$$(N, p, q) \leftarrow$$ GenModulus $$\left(1^{n}\right)$$

$$\phi(N):=(p-1)(q-1)$$

choose $$e>1$$ such that $$\operatorname{gcd}(e, \phi(N))=1$$

compute $$d:=\left[e^{-1} \bmod \phi(N)\right]$$

return $$N,e, d$$

Definition (The RSA experiment)

RSA-inv$$_{\mathcal{A}, \operatorname{GenRSA}}(n)$$ :

1. Run $$\operatorname{GenRSA}\left(1^{n}\right)$$ to obtain $$(N, e, d)$$.

2. Choose a uniform $$y \in \mathbb{Z}_{N}^{*}$$.

3. $$\mathcal{A}$$ is given $$N, e, y$$, and outputs $$x \in \mathbb{Z}_{N}^{*}$$.

4. The output of the experiment is defined to be 1 if $$x^{e}=y \bmod N$$, and 0 otherwise.

Definition (The RSA problem is hard)

The RSA problem is hard relative to $$\mathrm{GenRSA}$$ if for all probabilistic polynomial-time algorithms $$\mathcal{A}$$ there exists a negligible function $$\mathrm{negl}$$ such that $$\mathrm{Pr}[$$ RSA-inv$$_{\mathcal{A}, \operatorname{GenRSA}}(n)=1] \le \mathrm{negl}$$.

Definition (The RSA assumption )

There exists a $$\mathrm{GenRSA}$$ algorithm relative to which the RSA problem is hard.

## Plain RSA Encryption#

Algorithm (The plain RSA encryption scheme )

• Gen: on input $$1^{n}$$ run GenRSA $$\left(1^{n}\right)$$ to obtain $$N, e$$, and $$d$$. The public key is $$\langle N, e\rangle$$ and the private key is $$\langle N, d\rangle$$.

• Enc: on input a public key $$p k=\langle N, e\rangle$$ and a message $$m \in \mathbb{Z}_{N}^{*}$$, compute the ciphertext

$c:=\left[m^{e} \bmod N\right] .$
• Dec: on input a private key $$s k=\langle N, d\rangle$$ and a ciphertext $$c \in \mathbb{Z}_{N}^{*}$$, compute the message

$m:=\left[c^{d} \bmod N\right] \text {. }$

## Padded RSA and PKCS #1 v1.5#

Algorithm (The padded RSA encryption scheme)

• Enc: on input a public key $$p k=\langle N, e\rangle$$ and a message $$m \in\{0,1\}^{\|N\|-\ell(n)-1}$$, choose a uniform string $$r \in\{0,1\}^{\ell(n)}$$ and interpret $$\hat{m}:=r \| m$$ as an element of $$\mathbb{Z}_{N}^{*}$$. Output the ciphertext

$c:=\left[\hat{m}^{e} \bmod N\right] .$
• Dec: on input a private key $$s k=\langle N, d\rangle$$ and a ciphertext $$c \in \mathbb{Z}_{N}^{*}$$, compute

$\hat{m}:=\left[c^{d} \bmod N\right],$

and output the $$\|N\|-\ell(n)-1$$ least-significant bits of $$\hat{m}$$.

let $$k$$ denote the length of $$N$$ in bytes; i.e., $$k$$ is the integer satisfying $$2^{8(k-1)} \leq N<2^{8 k}$$.

Messages $$m$$ to be encrypted are assumed to have length an integer number of bytes ranging from one to $$k-11$$.

Algorithm (RSA PKCS #1 v1.5)

Encryption of a $$D$$-byte message $$m$$ is computed as: (0x00||0x02||r||0x00||m) $$^e \bmod N$$

where $$r$$ is a randomly generated, $$(k-D-3)$$-byte string with none of its bytes equal to 0x00.

## OAEP and PKCS #1 v2#

Algorithm (The RSA-OAEP encryption scheme)

• Enc: on input a public key $$\langle N, e\rangle$$ and a message $$m \in\{0,1\}^{\ell}$$, set $$m^{\prime}:=m \| 0^{k}$$ and choose a uniform $$r \in\{0,1\}^{k}$$. Then compute

$t:=m^{\prime} \oplus G(r), \quad s:=r \oplus H(t)$

and set $$\hat{m}:=s \| t$$. Output the ciphertext $$c:=\left[\hat{m}^{e} \bmod N\right]$$.

• Dec: on input a private key $$\langle N, d\rangle$$ and a ciphertext $$c \in \mathbb{Z}_{N}^{*}$$,

• compute $$\hat{m}:=\left[c^{d} \bmod N\right]$$. If $$\|\hat{m}\|>\ell+2 k$$, output $$\perp$$. Otherwise, parse $$\hat{m}$$ as $$s \| t$$ with $$s \in\{0,1\}^{\ell+k}$$ and $$t \in\{0,1\}^{k}$$.

• Compute $$r:=H(t) \oplus s$$ and $$m^{\prime}:=G(r) \oplus t$$.

• If the $$k$$ least-significant bits of $$m^{\prime}$$ are not all 0 , output $$\perp$$. Otherwise, output the $$\ell$$ most-significant bits of $$m^{\prime}$$.