RSA

reference: https://en.wikipedia.org/wiki/RSA_cryptosystem

The RSA cryptosystem was the first publicly known in 1977 by its inventors Rivest, Shamir and Adleman.

RSA relies on the diffculty of the factorisation of the modulus N. the Euler toient of N:

\begin{align} \phi({N}) &= (p-1) \cdot (q-1) \\ e \cdot d &\equiv 1 \pmod {\phi({N})} \end{align}

The correctness of the decryption rule, for plaintext elements that are relatively prime (coprime) to the modulus, from the Euler's theorem (Fermat Little Theorem)

\begin{align} a^{\phi{(N)}} \equiv 1 \pmod N \end{align}

For decryption rule, and the key equation \(e\cdot d = 1 + k\cdot \phi{(N)}\) we can recover the plaintext since:

\begin{align} c^d \bmod N &\equiv (m^e)^d \pmod N \\ &\equiv m^{ed} \pmod N \\ &\equiv m^{1+k\phi{(N)}} \pmod N \\ &\equiv m(m^{\phi{(N)}})^k \pmod N \\ &\equiv m \pmod N \end{align}

Common Misuse

Factoring

If the primes we using for the modulus is small, this means that they can be factorised using modern methods.

Nowadays, using primes that are at least 1024 bit long is recommended => called RSA-2048.

The longer of the primes bit, and slower of the modular operations, so there is a tradeoff here.

Monoprime

reference: why do we need in rsa the modulus to be product of 2 primes

With just one prime for N, we can easily calculate the private key pair from public key (e, N), in which case \( \phi{(N)} = N - 1 \)

Manyprim

we can leverage The Elliptic Curve Factorization Method to factorise N. we can product all prime factors of the N to construct the \(\phi{(N)}\).

from sage.all import *

ecm.factor(602400691612422154516282778947806249229526581)

Smallest e

\(ct = pt^e \mod N \), when choice a small e like 3, we get that \(ct = pt^e\) (cause N is a big prime), so \(pt = \sqrt[e]{ct} \).

Give p,q,e,c

With Give p, q, we can recover the private key d

import gmpy2                    #  for inverse()
from Crypto.Util.number import long_to_bytes

p = 3
q = 5
e = 3
c = 13
# just for example

n = p * q
phi = (p - 1) * (q - 1)
d = gmpy2.inverse(e, phi)       # or use builtin pow(e, -1, phi)
m = pow(c, d, n)

pt = long_to_bytes(m)

Give n,e,dp,c

\begin{align} dp \equiv d \pmod {p-1} \\ dp \cdot e \equiv d \cdot e \equiv 1 \pmod {p-1} \\ dp \cdot e-1 = k \cdot (p-1) \\ (dp \cdot e-1) \cdot d \cdot e = k' \cdot(p-1), \quad k' = k\cdot d \cdot e \\\LeftRightarrow d\cdote = -k'\cdot(p-1)+dp\cdot e\cdot d\cdot e \equiv 1 \pmod{\varphi(n)} \\\LeftRightarrow -k'\cdot (p-1) +dp\cdot e \equiv 1 \pmod{\varphi(n)} \end{align}

Primitive Element of Groups

Suppose that \( p > 2\) is prime and \( \alpha \in \mathbb{Z}^{*}_{p}\) then \( \alpha \) is a primitive element modulo \(p\) if and only if \(\alpha^{\frac{p-1}{q}} \not\equiv 1 \pmod p\) for all primes \(q\) such that \(q \in factorise(p - 1)\).

Sage have function do this:

from sage.all import *

GF(28151).primitive_element()

Diffie-Hellman Protocol

if \(g, p \) is prime, then:

\begin{align} \label{eq:2} &\{g^{1} \bmod{p},\quad g^{2} \bmod p,\quad \dots,\quad g^{p-1} \bmod p\} \in \{1, 2, \dots, p-1\} \\ &\forall x, 0 < x < p, \text{there only one y that} (0 < y < p), \text{satisfied} \: x = g^{y} \bmod p \end{align}

when \(p\) is big enough, the \(y\) is hard to compute. that's the trapdoor function.

first we choice a secret key \(x\), then calculate the public key \(A = g^{x} \bmod p\). then this public key transmitted over an insecure network and due to the difficulty of the discrete logarithm. the secret key should be infeasible to compute. the same as the other side.

\begin{equation} \label{eq:4} \text{shared-secret} = (g^{x} \bmod p)^{y} \bmod p = g^{xy} \bmod p \end{equation}