ElGamal

$N$ positive integer

$p$ prime number

greatest common divisor GCD

The highest number that is shared by the factorization of two numbers.

Modular inverse

If $\text{gcd}(x,N) = 1$ then $\exists x^{-1}: x \cdot x^{-1} = 1$

Set of invertible elements in$\Z_N$

$\mathbb{Z}^{*}_N:=\left\{\mathrm{x} \in \mathbb{Z}_{N} \mid \operatorname{gcd}(x, N)=1\right\}$

for prime numbers:$\mathbb{Z}^{*}_{p} = \mathbb{Z}_{p} /\{0\}=\{1,2, \ldots, p-1\}$

Euler's Theorem

$\exists g\in \mathbb{Z}^{*}_{p} :\mathbb{Z}^{*}_{p}=\{g^0, g^1, g^2,\dots \}$(that can express every element)

This is not true for all elements. Some$g$can not express the entire$\mathbb{Z}^{*}_{p}$.

Example:

Order of$g$

$|\lang g\rang| = ord_p(g)$

$ord_7(3) =6$ (= $|\Z^*_7|$ )

Lagrange Theorem

$\forall g \in \mathbb{Z}^{*}_{p}: (p-1) \bmod \text{ord}_{p}(g) = 0$

$\forall g \in \mathbb{Z}^{*}_{p}: (p-1) = 0$in$\Z_{\text{ord}_{p}(g)}$

Fermat's little theoremin$\Z_p^*$

$\forall p,x \in \Z_p^*:$

Example:$4^{7-1} \bmod 7 = 1$

Discrete logarithm - Dlog

We want a function with the following property

In $\mathbb{Z}^{*}_{p}$ :

Example:

There is no easy way to find a function for $Dlog$ .

Best known algorithm: GNFS has $O(e^{\sqrt[3]{n}})$ - only for small numbers

RSA

Factorization

For prime numbers $p,q$

Easy to compute: $N=p \cdot q$

Hard to compute: The factors behind the result $N$

Euler's$\varphi$function (Euler's totient function)

$\varphi(N):=\left|\mathbb{Z}_{N}^{*}\right|$for$N\in \N$

The size of a group, only with members that have an inverse in $\Z_N$ .

Examples:

Eulers Theorem (Generalization of Fermat)

$\forall x \in \mathbb{Z}_{N}^{*}: x^{\varphi(N)}=1$in$\Z_N$

That means $x^{|\mathbb{Z}_{N}^{*}|}=1$in$\Z_N$

Chinese Remainder Theorem CRT

Let $p \not = q$ be primes and $N = p\cdot q$

$\forall a,b \in \Z: ~~ (a = b \bmod N) \Lrarr (a=b \bmod p) \wedge (a=b \bmod q)$