RSA and Elliptic Curve Cryptography¶

This blog discuss the math definition of the RSA and elliptic curve cryptography. It's a pure blog about math.

RSA¶

Private and Public Keys¶

The RSA algorithm is the formula listed below, the $p$ and $q$ are distinct primes.

\[ \begin{align*} &n = p \cdot q \\ &\phi(n) = (p-1) \cdot (q-1) \\ & 1 < e < \phi(n) \\ & \text{gcd}(e, \phi(n)) = 1 \\ & d \cdot e \equiv 1 \pmod{\phi(n)} \\ \end{align*} \]

The $n$ is called modulus, $d$ is the private exponent and $e$ is public exponent.

private key: $(d,n)$
public key is $(e,n)$.

Given the encrypted message by private key, the public key could decrypt it and vice versa. One thing to note is that given private key, you cannot calculate its public key.

Integer Factorization Problem is HARD, so RSA is Safe¶

Given $n$ exists in the public key, if we can find $p'$ and $q'$ where $n= p' * q'$, soon we can calculate the $\phi(n)$. As a result, the private exponent $d$ could be calculated as we already know $e \cdot d \equiv 1 \pmod \phi(n)$.

However, finding the factors are a distant dream now and it's the Integer Factorization Problem. As long as it's hard to solve, RSA is safe.

Encrypt and Decrypt¶

RSA could encrypt by public key and decrypt by private key, and vice versa. This is guaranteed by $e \cdot d \equiv 1 \pmod \phi(n)$.

The encrypted message $c$ is generated by $c = m^e \pmod n$, then given private key $(d,n)$, we can get the plain text $m = c^d \pmod n$:

The following content demonstrate this is below. Because the decrypting and encrypting shares the same procedures, no matter which key is used to encrypt the calculation steps are the same. Here, we provide the example for public key to encrypt.

\[ \begin{align*} &m' \equiv c^d \pmod n \\ &m' \equiv (m^e)^d \pmod n\\ &m' \equiv m^{e \cdot d} \pmod n\\ \end{align*} \]

Because $e \cdot d \equiv 1 \pmod{ \phi(n)}$, so $e \cdot d = k \cdot \phi(n) + 1$.

\[ \begin{align*} & m' \equiv m^{k \cdot \phi(n) +1} \pmod n \\ \end{align*} \]

According to Euler's theorem: $m^\phi(n) \equiv 1 \pmod n$:

\[ \begin{align*} & m' \equiv m^{k \cdot \phi(n) } \cdot m \pmod n\\ & m' \equiv (m^{ \phi(N)})^k \cdot m \pmod n\\ & m' \equiv 1^k \cdot m \pmod n\\ & m' \equiv m \pmod n\\ \end{align*} \]

Hence, $m'$ and $m$ are equivalent in the modular arithmetic system defined by modulus $n$.

Elliptic Curve Cryptography(ECC)¶

Private and Public Keys¶

An elliptic curves $E$ over a finite field $F_p$ where $p$ is a prime number, defined by the equation $y^2 = x^3 + a \cdot x + b $.

Then, a base point(generator point) $G$ is picked, which has a high order $n$. The high order refers to that it means that the subgroup of points generated by $G# (all multiples of $G$) is cyclic and has n elements.

Given $p$, $G$, $n$ and the curve, the private key $d$ is selected with range $[1,n)$.

Then, we do addition $Q = d \cdot G$ for point $G$ on the ECC equation to get the public key $Q$.

Private key: $d$
Public key: $Q$

Addition Operation of ECC¶

Given $E$, and points $P = (x_1,y_1)$ and $Q = (x_2, y_2)$, the addition operation for $R = P + Q$ over $E$ is calculated as follows:

$P \neq Q$: (P and Q are distinct points on curve $E$):

\[ \begin{align*} &m = \frac{y_2-y_1}{x_2-x_1}\\ &x_3 = m^2 - x_1 - x_2\\ &y_3 = m(x_1-x_3) - y_1\\ &R = (x_3, y_3)\\ \end{align*} \]

$P = Q$

\[ \begin{align*} &m = (3 \cdot x_1^2 + a) / 2 \cdot y_1\\ &x_3 = m^2 - 2 \cdot x_1\\ &y_3 = m(x_1-x_3) - y_1\\ &R = (x_3, y_3)\\ \end{align*}\\ \]

Identity $O$ and Inverse Elements $-P$:
The identity element($O$) for addition of $E$ is the point at infinity, given any point $P$, $P + O = P$. The inverse of a point $P = (x,y)$ with respect to addition is $-P=(x,-y)$, where $P+(-P)=O$.

ECDLP is HARD so ECC is safe¶

The public key $Q$ and the private key $d$ satisfies the equation $Q = dG$. If we know the $Q$ and $G$, can we easily get the $d$? However, this problem, also known as ECDLP(Elliptic Curve Discrete Logarithm Problem), is computationally infeasible. The ECC is easy to perform in onr direction but is computationally infeasible to do in reverse.

As long as ECDLP is hard to solve, it's safe for ECC.

Encrypt by Public Key¶

Unlike the RSA, ECC only allows you to encrypt by a public key and decrypt by the private key, but not reverse. Hence, usually we use private key in signing signatures by another way. Here we only discuss how the encryption works.

Given private key $d$, generator point $G$ and public key $R = d \cdot G$. Let's see how the encryption and decryption work. Unlike RSA, we can use private key $d$ and modulus $n$ to encrypt. However, for ECC, encrypting is different and a random number $k$ is needed.

\[ \begin{align*} &S = k \cdot R\\ &S = (x_s,y_s)\\ &P = k \cdot G\\ \end{align*} \]

We use the x-coordinate $x_s$ of $S$ to encrypt the message $m$ and $P$ and cipher $c$ is output after encrypting.

Then, given $d$, $P$ and $c$, we can get the original message $m$ once we get the $S$.

\[ \begin{align*} P &= k \cdot G\\ S &= k \cdot R\\ &= k \cdot (d \cdot G)\\ &= d \cdot (k \cdot G)\\ &= d \cdot P\\ \end{align*} \]

By this way, we get the $S$ from the peer without knowing the value of random $k$.

Note¶

Note that because the asymmetric cryptography is limited by the length of plaintext and the concern of speed, they are usually used to exchange the symmetric key instead of encrypting directly.