# RSA

## Overview

Define `R` (RSA Function) as following:

``````R(x,k,n) = x^k (mod n)
``````

(For simplicity, `n` is omitted from now on)

Along with the function there is a way to choose two keys such that:

``````R(R(x, pk), sk) = x, and
R(R(x, sk), pk) = x.
``````

(`pk`, `sk` stands for public key and secretly, respectively.)

How encryption works:

``````c = Encrypt(m, pk) => R(m, pk)
m = Decrypt(c, sk) => R(c, sk)
``````

In practice, simplely using `RSA` is vulnerable. For preventing from many attacks, There are pre-post processes like OAEP as following:

``````c = Encrypt(m, pk) => R(pre(m), pk)
m = Decrypt(c, sk) => post(R(c, sk))
``````

How digital signature works:

``````s = Sign(m, sk) => R(m, sk)
v = Verify(m, s, pk) => R(s, pk) == m
``````

However, RSA function can't accomote messages longer than the key. (Encryption also can suffer this problem, but it's not so problematic because most encryption for actual data is done by symmetric key) So, apply a hash function as following:

``````s = Sign(m, sk) => R(H(m), sk)
v = Verify(m, s, pk) => R(s, pk) == H(m)
``````