RSA

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

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

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

Common Weakness

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 \)

Manyprime

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} \).

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}