VE475 Cryptography Note 3

Posted on In Disqus:

All info comes from Manuel’s slides on Lecture 3.

Public-Key Cryptosystem

Encryption depends on a public key $K$ and decryption depends on a secret key $K’$.

Finding $K’$ when knowing $K$ is computationally infeasible.

One-Way Function

Function easy to evaluate but hard to invert, or so to say:

  • it is easy to calculate $y=f(x)$ given $x$
  • but it is hard to get $x$ on the range of $f(x)$ for some $y$

The requirement for encrypting with such one-way function $E$:

  • $E$ must be injective
  • Some secret that allows to invert $E$, which means finding such $E^{-1}$ has negligible possibility so only decipher can know how to decrypt

Trapdoor One-Way Function

Trapdoor one-way function is a one-way function that with certain kind of knowledge, it is easy to be inverted.

Not all one-way function is easy to be inverted since people may not know its $E^{-1}$.

Some Abstract Algebra

graph LR
subgraph Field
subgraph Integral Domain
subgraph Communicative Ring
subgraph Ring
subgraph Abelian Group
subgraph Group
A1["Closed Operation (Addition)"] --- A2["Associativity (Assoc of Add)"]
A1 --- A3["Exist a unit element (Add unit 0)"]
A1 --- A4["Existence of Inverse (Addictive Inverse)"]
end
A1 --- A5["Commutativity (of Addition)"]
end
M1 --- M3["Distributivity (a * (b + c))"]
A1 --- M3
M1["Closed Operation (Multiplication)"] --- M2["Associativity (Assoc of Mult)"]
end
M1 --- M4["Commutativity (of Mult)"]
end
M1 --- M5["Existence of a unit element (Mult unit 1)"]
M6[No zero divisors] --- M1
end
M5 --- F1["2 different unit elements (0 != 1)"]
F1 --- A3
M1 --- F2["Existence of Inverse (Exists inverse of mult for F\{0})"]
end

Group

A group is a pair $(G, \circ)$ consisting of a set $G$ and an operation $\circ:G\times G\to G$ (closed operation) with properties

  • Associativity: $\forall a,b,c \in G, a \circ (b \circ c) = (a\circ b)\circ c$
  • Existence of a unit element: $\exists e \in G, \forall a \in G, a\circ e = e\circ a = a$
  • Existence of inverse: $\forall a \in G, \exists a^{-1} \in G, a\circ a^{-1} = a^{-1}\circ a = e$

Abelian Group

An Abelian Group is a group with property

  • Commutativity: $\forall a,b\in G, a\circ b = b\circ a$

Ring

A ring is a triple $(R, +,\cdot)$ consisting of a set $R$ and two binary operations $+,\cdot: R\times R \to R$ (closed operations) with properties

  • $(R, +)$ is an abelian group
  • Associativity: $\forall a,b,c\in R, a\cdot (b\cdot c) = (a\cdot b)\cdot c$
  • Distributivity: $\forall a,b,c\in R, a \cdot (b+c) = (a\cdot b) + (a\cdot c), (b+c)\cdot a = (b\cdot a) + (c\cdot a)$

Commutative Ring

A commutative ring is a ring with property

  • Commutativity: $\forall a,b\in R, a\cdot b = b\cdot a$

Integral Domain

An integral domain is a commutative ring with properties

  • Existence of unit element: In multiplication, $\exists 1 \in G, \forall a \in R, a\cdot 1=1\cdot a = a$
  • No zero divisors: if $a\cdot b = 0$ for $a,b\in R$, then either $a=0$ or $b=0$

Field

A field is an integral domain with unit element of addition 0 and unit element of multiplication 1 and properties

  • $0\neq 1$
  • Existence of inverse: $\forall a\in F\backslash\lbrace 0\rbrace,\exists a^{-1}, a\cdot a^{-1}= a^{-1}\cdot a= 1$

Another way to write the definition is that $(F,+,\cdot)$ is a field with properties

  • $(F, +)$ is an abelian group
  • $(F \backslash \lbrace 0\rbrace,\cdot)$ is an abelian group
  • $0\neq 1$
  • $\cdot$ distributes over $+$

Integers Modulo n

Let $n$ be integer, $\mathbb{Z} / n\mathbb{Z}$ be the set of integers modulo $n$.

  • $(\mathbb{Z} / n \mathbb{Z},+)$, or donated as $(\mathbb{Z}_n,+)$ is a group
  • $(\mathbb{Z}/n\mathbb{Z}, +,\cdot)$ is a ring
  • If $n$ prime, then $(\mathbb{Z}/n\mathbb{Z},+,\cdot)$ is a field $\mathbb{F}_n$
  • $(\mathbb{Z}/n\mathbb{Z}\lbrack X\rbrack, +,\cdot)$ is the ring of polynomials over $\mathbb{Z} / n \mathbb{Z}$
  • If $n$ prime and polynomial $P(X)$ is irreducible, then $(\mathbb{F}_n\lbrack X\rbrack / \langle P(X)\rangle,+,\cdot)$ is a field
  • The invertible elements of $\mathbb{Z}/n\mathbb{Z}$ w.r.t $\cdot$ form a group donated $U(\mathbb{Z}/n\mathbb{Z})$ or $\mathbb{Z}_n^\times$ or $\mathbb{Z}_n^\ast$ (operation is $\cdot$)

Order

Let $G$ be a group

  • The order of $G$ is $|G|$
  • The order of $g\in G$ is the smallest positive integer $m$ such that $g^m = 1$
  • An element of order equal to the order of group is called a primitive element or a generator
  • When $G = \mathbb{Z} / n\mathbb{Z}$, Euler’s totient function $\varphi(n)$ counts the number of invertible elements, that is the number $k$ such that $\gcd(n,k)=1$

Let $p$ be prime and $\alpha$ as generator of $G = U(\mathbb{Z}/p\mathbb{Z})$. Then $\forall \beta\in G$ can be written $\beta = \alpha^i, 1\le i\le p -1$.

Noting $d=\gcd(i, p-1)$, we have $\beta^{\frac{p-1}{d}} = (\alpha^i)^{\frac{p-1}{d}}=1$.

Since $d = \gcd(i,p-1)$, thus $\beta$ order is $\dfrac{p-1}{d}$.

CRT and Ring Isomorphism

Recap on CRT discussed on chapter 2, we can see that a system of congruences has a unique solution modulo the product of all moduli of the system.

We can reformulate the problem into form like: Let $n$ be a positive integer with prime decomposition $n = \prod\limits_i p_i^{e_i}$. Then there exists ring isomorphism between $\mathbb{Z}/n\mathbb{Z}$ and $\prod\limits_i \mathbb{Z}/p_i^{e_i}\mathbb{Z}$.

We can get $U(\mathbb{Z}/n\mathbb{Z}) \cong U(\prod\limits_i \mathbb{Z}/p_i^{e_i}\mathbb{Z})$ by previous ring isomorphism.

Noticing that non-invertible elements of $\mathbb{Z}/p_i^{e_i}\mathbb{Z}$ is of form $kp_i$ where $k$ is some integer. Conversely an element that is not invertible mod $n$ is a multiple of some $p_i$.

Therefore $U(\mathbb{Z}/n\mathbb{Z}) \cong U(\prod\limits_i \mathbb{Z}/p_i^{e_i}\mathbb{Z})\cong \prod\limits_i U(\mathbb{Z}/p_i^{e_i}\mathbb{Z})$.

Lagrange’s Theorem

Previously $\varphi(n)$ is defined as $|U(\mathbb{Z}/n\mathbb{Z})|$. Then we can see some properties of such function

  • $m,n$ coprime integers can have $\varphi(mn)=\varphi(m)\varphi(n)$.
  • If $m,n$ are primes, then $\varphi(mn) = (m-1)(n-1)$.

Lagrange’s Theorem states that: Let $G$ be a finite group and $H$ be a subgroup of $G$. Then $\text{ord}(H)|\text{ord}(G)$.

$\forall x \in G$, it generates a subgroup of order $\text{ord}_G x$, it follows the order of all elements of $G$ divides $\text{ord}(G)$.

Thus we can have $\varphi(n) = |U(\mathbb{Z} / \prod\limits_{i\in P} p_{i}^{e_i} \mathbb{Z})| = \prod\limits_{i\in P} |U(\mathbb{Z} / p_i^{e_i} \mathbb{Z})| = \prod\limits_{i\in P} (p_i - 1)\times p_i^{e_i-1} = \prod\limits_{i \in P} p_i^{e_i}\times\frac{p_i - 1}{p_i} = n \prod\limits_{p | n} (1 - \frac{1}{p})$.

Euler’s Theorem (Extended FLT)

Let $a$ and $n$ be two coprime integers, then $a^{\varphi(n)}\equiv 1\pmod n$.

Recall the FLT, which is $a^{n-1}\equiv 1\pmod n$, Euler’s Theorem extended the usage to coprime integers.

Proof: Based on Lagrange’s Theorem, we can say $\forall a \in G = U(\mathbb{Z}/ n \mathbb{Z}), \text{ord}_G a = k$ and $k | \varphi(n)$.

Then $a^{\varphi(n)}\equiv a^{\text{ord}_G a} \equiv 1\pmod n$.

Finding Primitive Elements / Generators

Let $p > 2$ be prime and $\alpha \in U(\mathbb{Z}/p\mathbb{Z})$. Then $\alpha$ is a generator for $U(\mathbb{Z} / p\mathbb{Z}) \iff \forall q | (p-1), \alpha^{\frac{p-1}{q}}\not\equiv 1 \pmod p$.

Collary

Still, let $\alpha$ be a generator for $U(\mathbb{Z} / p\mathbb{Z})$, we have

  • Let $n$ be an integer. $\alpha^{n-1}\equiv 1\pmod p \iff n\equiv 0\pmod{(p-1)}$.
  • Let $j$ and $k$ be two integers. $\alpha^{j}\equiv \alpha^{k}\pmod{p}\iff j\equiv k\pmod{(p-1)}$.

Order and factorization: Let $x$ be an element of order $r$ in $U(\mathbb{Z} / n\mathbb{Z})$. By definition $x^r \equiv 1 \pmod {n}$, or $n|(x^r - 1)$. Then $\gcd{(x^{r/2}-1,n)}$ and $\gcd{(x^{r/2}+1,n)}$ are factors of $n$.

Knowing $n$’s factorization gives $\varphi(n)$, which is discussed in Lagrange’s Theorem part. We can use this method to check if $x$ is a generator.

Square roots modulo p

For $p$ an odd prime and $a$ such that $a\not\equiv 0\pmod p$, $a^{\frac{p-1}{2}}\equiv\pm 1\pmod p$.

$a$ is a square mod $p\iff a^{\frac{p-1}{2}}\equiv 1\pmod p$.

Proof: $y\equiv a^{\frac{p-1}{2}}\pmod p$ and apply FMT, we see $y^2 \equiv a^{p-1}\equiv 1\pmod p$. Therefore $y^2 - 1\equiv (y - 1)(y + 1)\equiv 0\pmod p$.

Since $p$ prime, all elements but 0 are invertible. Thus $y \equiv\pm 1\pmod p$.

Let $g$ be generator mod $p$ and donate $a \equiv g^j$ for some $j$. If the $j$ even, then $a^{\frac{p-1}{2}}\equiv 1\pmod p$.

Legendre Symbol

Given $p$ be odd prime, and $a\not\equiv 0\pmod p$, define Legendre symbol by $\Big(\dfrac{a}{p}\Big)=\begin{cases} +1 & \text{if }a\text{ is a square mod }p\newline -1 & \text{if }a\text{ is not a square mod }p\end{cases}$

Then we can get some features and properties like

  • If $a\equiv b\pmod p$, then $\Big(\dfrac{a}{p}\Big)=\Big(\dfrac{b}{p}\Big)$.
  • If $a\not\equiv 0\pmod p$, then $\Big(\dfrac{a}{p}\Big)\equiv a^{\frac{p-1}{2}}\pmod p$.
  • If $ab\not\equiv 0\pmod p$, then $\Big(\dfrac{ab}{p}\Big)=\Big(\dfrac{a}{p}\Big)\Big(\dfrac{b}{p}\Big)$.
  • If $p\equiv 1\pmod 4$, then $-1$ is a square mod $p$.

Jacobi Symbol

Given $n=\prod\limits_i p_i^{e_i}$ an odd integer and $a$ a non-zero integer coprime to $n$, define Jacobi symbol by $\Big(\dfrac{a}{n}\Big)_J = \prod\limits_i\Big(\dfrac{a}{p_i}\Big)^{e_i}_L$, where each of $\Big(\dfrac{a}{p_i}\Big)_L$ is a Legendre symbol.

Let $n$ be an odd integer

  • $a\equiv b\pmod n$ and $\gcd{(a,n)}=1$, then $\Big(\dfrac{a}{n}\Big)_L = \Big(\dfrac{b}{n}\Big)_J$.
  • $\text{gcd}{(ab,n)}=1$, then $\Big(\dfrac{ab}{n}\Big)_J = \Big(\dfrac{a}{n}\Big)_L \Big(\dfrac{b}{n}\Big)_J$.
  • $\Big(\dfrac{-1}{n}\Big)_J = (-1)^{\frac{n-1}{2}}$.
  • $\Big(\dfrac{2}{n}\Big)_J = \begin{cases} +1 & \text{if }n\equiv 1\text{ or }7\pmod 8\newline -1 & \text{if }n\equiv 3\text{ or }5\pmod{8} \end{cases}$.
  • If $m,n$ are odd coprime positive integers, then $\Big(\dfrac{m}{n}\Big)_J=\begin{cases} -\Big(\dfrac{n}{m}\Big)_L & \text{if }m\equiv n\equiv3\pmod 4\newline +\Big(\dfrac{n}{m}\Big)_L & \text{otherwise}\end{cases}$.

RSA Cryptosystem

The basic idea is to know two primes $p,q$, then compute the product $n$ and $\varphi(n)$.

An integer $e$ coprime to $\varphi(n)$ is chosen, we can run the extended Euclidean algorithm to get the $d$ satisfying $ed\equiv 1\pmod{\varphi(n)}$.

Given $e$ and $n$ it is possible to compute $c \equiv m^e\pmod n$ for any integer $m$. Then $c^d\equiv (m^e)^d\equiv m^{ed\pmod{\varphi(n)}}\equiv m\pmod n$.

We can see that $n-\varphi(n) + 1 = pq-(p-1)(q-1) + 1 = p+q$, then $p,q$ are roots of the quadratic equation $X^2-(n-\varphi(n)+1)X + n$.

Hence $p,q = \dfrac{n - \varphi(n)+1\pm\sqrt{(n-\varphi(n)+1)^2 - 4n}}{2}$. Thus if $\varphi(n)$ can be computed, then $n$ can be factorized.

Modular Exponentiation

The modular exponentiations can be done in $O((\log n)^2\log d)$ bit operations.
$$
\begin{aligned}
&\text{Input: }m\text{ an integer}, d=(d_{k-1}\dots d_0)_2\text{ and }n\text{ two positive integers}\newline
&\text{Output: }x=m^d\pmod n\newline
&power\leftarrow 1;\newline
&\text{for }i\leftarrow k-1\text{ to }0\text{ do }\newline
&\phantom{“”””}power\leftarrow (power\cdot power)\pmod n;\newline
&\phantom{“”””}\text{if }d_i=1\text{ then }power \leftarrow (m\cdot power)\pmod n;\newline
&\text{end for}\newline
&\text{return }power
\end{aligned}
$$

Faster Decryption

There are 2 practical methods used to accelerate the decryption process.

One is save $d \pmod{\varphi(n)}$ such that it helps reduce decryption steps required.

The other methods is to use CRT to speed up the computation.

Consider $c \equiv m^e\pmod{n}$, then by Euler’s Theorem, we have $e\cdot d \equiv 1\pmod{\varphi(n)}\equiv 1\pmod{(p-1)(q-1)}$. We can see $\begin{cases}e\cdot d\equiv 1\pmod{p-1}\newline e\cdot d\equiv 1\pmod{q-1} \end{cases}$.

Thus $\begin{cases}c^d\equiv m \pmod{p}\newline c^d\equiv m\pmod{q} \end{cases}$ can be achieved. In this way CRT can be applied to get $m$ from such equations.

Prime Generating

There are mainly 2 methods to choose for prime generating:

  • Generate a random integer, pick the next prime
  • Generate random integers until one of them is prime

Prime Number Theorem (PNT)

$\pi(n)\sim \dfrac{n}{\ln{n}}$ describes in range $\lbrack 1,n\rbrack$, approximately $\dfrac{n}{\ln{n}}$ integers are prime.

Therefore, on 1024 level of security, a random integer has possibility of $\dfrac{1}{\ln{2^{1024}}}\approx\dfrac{1}{710}$.

Solovay-Strassen Primality Test

Recall, $\Big(\dfrac{a}{n}\Big)\equiv a^{\frac{n-1}{2}}\pmod n$ if $n$ prime and $a\not\equiv 0\pmod n$. But there exists $a$ to make this be true if $n$ is not prime.

Let $n$ be composite and $A = \lbrace a | \gcd{(a,n)}=1\text{ and }\Big(\dfrac{a}{n}\Big)\equiv a^{\frac{n-1}{2}}\pmod n\rbrace$.

Since $n$ is composite, $\exists b$ such that $\gcd{(b,n)}=1$ and $\Big(\dfrac{b}{n}\Big)\not\equiv b^{\frac{n-1}{2}}\pmod n$. $\forall a \in A, (ab)^{\frac{n-1}{2}} = \Big(\dfrac{a}{n}\Big)b^{\frac{n-1}{2}}\not\equiv \Big(\dfrac{a}{n}\Big)\Big(\dfrac{b}{n}\Big)\pmod n$.

Hence, $\forall a \in A$, there’s an element coprime to $n$ that is not belonging to $A$. A Monte-Carlo algorithm can be composed with $O(k(\log n)^3)$ complexity.
$$
\begin{aligned}
&\text{Input: }n\text{ an integer}, k\text{ the number of tests to run}\newline
&\text{Output: }n\text{ is composite or probably prime}\newline
&\text{for }i \leftarrow 1\text{ to }k\text{ do}\newline
&\phantom{“”””}a\leftarrow\text{rand}(2,n-2);\newline
&\phantom{“”””}\text{if }\gcd{(a,n)}\neq 1\text{ then return }n\text{ is composite};\newline
&\phantom{“”””}x\leftarrow\Big(\dfrac{a}{n}\Big);\newline
&\phantom{“”””}y\leftarrow a^{\frac{n-1}{2}}\pmod n;\newline
&\phantom{“”””}\text{if }x\not\equiv y\pmod n\text{ then return }n\text{ is composite};\newline
&\text{end for}\newline
&\text{return }n\text{ is probably prime}
\end{aligned}
$$

Miller-Rabin Primality Test

Let $n$ be an odd integer, then $n = 1 + 2^s m$ where $s$ is an integer and $m$ is odd. $n$ passes Miller-Rabin test if $\begin{cases} a^m&\equiv 1\pmod n\newline a^{2^j m}&\equiv -1\pmod n \end{cases}$ where $0\leq j \leq s-1$.

Starts from $m$ power to $2^{s-1} m$ power, we can see that if $x^2\equiv 1\pmod n$ does have $(x-1)(x+1)\equiv 0\pmod n$. Thus we can rewrite $x^{n-1}\equiv 1 \pmod n$ to $x^{n-1}-1 = x^{2^s m - 1} - 1$.

Thus $x^{2^s m} - 1 = (x^m - 1)(x^m + 1)\dots(x^{2^{s-1} m} + 1)\equiv 0 \pmod n$, in this way the test congruences are established.

If the $n$ is prime, then $n$ passes Miller’s test to base $a$ ($1 < a < n$). Check previously talked Square Root Modulo.

If $n$ is composite, then fewer than $\frac{n}{4}$ bases $a$ passes Miller’s test.

A Monte-Carlo algorithm uses randomly $k$ bases $a$, the possibility that $n$ composite and passes all tests in $k$ times is $p_k = \dfrac{1}{4^k}$.
$$
\begin{aligned}
&\text{Input: }n \text{ an odd integer}, k\text{ the number of tests to run}\newline
&\text{Output: }n \text{ is composite or probably prime}\newline
&m\leftarrow \dfrac{n-1}{2};s\leftarrow 1;\newline
&\text{while }2\mid m\text{ do }\lbrace m\leftarrow \dfrac{m}{2};s\leftarrow s+1;\rbrace\newline
&\text{for }i\leftarrow 1\text{ to }k\text{ do}\newline
&\phantom{“”””}a\leftarrow \text{rand}(2,n-2);\newline
&\phantom{“”””}\text{if }\gcd{(a,n)}\neq 1\text{ then return }n\text{ is composite};\newline
&\phantom{“”””}a\leftarrow a^m\pmod n;\newline
&\phantom{“”””}\text{if }a=\pm1\text{ then continue};\newline
&\phantom{“”””}\text{for }j\leftarrow 1\text{ to }s-1\text{ do}\newline
&\phantom{“”””””””}a \leftarrow a^2\pmod n;\newline
&\phantom{“”””””””}\text{if }a \equiv 1\pmod n\text{ then return }n\text{ is composite};\newline
&\phantom{“”””””””}\text{if }a\equiv-1\pmod n\text{ then }b\leftarrow 1;\text{break};\newline
&\phantom{“”””}\text{end for}\newline
&\phantom{“”””}\text{if }b=1\text{ then continue else return }n\text{ is composite};\newline
&\text{end for}\newline
&\text{return }n\text{ is probably prime}
\end{aligned}
$$

Witness 75%

First we have a definition about witness. We say $a$ is a Miller-Rabin witness for $n$ if all of the congruences are false: $a^k\not\equiv 1\pmod n$ and $a^{2^jm}\not\equiv -1\pmod n, \forall j \in \lbrack 0, s-1\rbrack$.

Thus the definition of nonwitness for $n$ is that if one of the congruences is true: $a^k \equiv 1\pmod n$ or $a^{2^jm}\equiv -1\pmod n, \exists j \in \lbrack 0, s-1\rbrack$.

A odd prime in Miller-Rabin has no witness.

The product of two Miller-Rabin nonwitnesses might not be a nonwitness.

If $n=p^\alpha$, the Miller-Rabin nonwitness for $n$ are the solutions to $a^{p - 1}\equiv 1\pmod {p^\alpha}$. This forms a group under multiplication mod $n$.

Proof: First, suppose $a \in \lbrack 1,n-1\rbrack$ is a Miller-Rabin nonwitness, by Euler’s Theorem, $a^{p^{\alpha - 1}(p-1)}\equiv 1\pmod {p^\alpha}$. Then by Miller-Rabin nonwitness, $a^{p^\alpha - 1}\equiv 1\pmod{p^\alpha}$.

Consider the $\gcd{(p^\alpha-1,(p-1)p^{\alpha - 1})}$, we get $p-1$. Then $a^{p - 1} \equiv 1\pmod n$.

Then suppose $a^{p-1}\equiv 1\pmod {p^{\alpha}}$. Then we can write $p-1 = 2^f l$ where $f \ge 1$ and $l$ odd. Since $p - 1$ is a factor of $p^\alpha - 1 = 2^e k$, we have $f \le e$ and $l \mid k$.

By $a^{2^f l}\equiv 1 \pmod {p^\alpha}$, the order of $a^l$ is $2^j$ for some $j \in \lbrack 0, f\rbrack$.

  • If the order $j = 0$, then it is nonwitness of Miller-Rabin test.

  • If $j \ge 1$, then $x = (a^{l})^{2^{j - 1}}$ satisfies $x \not\equiv 1\pmod {p^\alpha}$ but $x^2 \equiv 1 \pmod {p^\alpha}$. In this way $p^\alpha\mid (x+1)(x-1)$, since $x\pm 1$ differ at most 2, so at most one of them can be divisible by $p$.

    Since $(a^l)^{2^{j-1}}\equiv -1\pmod {p^{\alpha}}$, $l \mid k$, then $(a^k)^{2^{j-1}}\equiv -1\pmod {p^\alpha}$. $j - 1 \in \lbrack 0, f-1\rbrack \subset\lbrack 0, e-1\rbrack$. $\square$

Then check this out.

RSA Attack

Suppose $e,d$ are known, then $n$ can be efficiently factorized. Since $a^{ed - 1}\equiv 1 \pmod n$ for some random $a$ coprime to $n$ and apply square root modulo $n$.

Rewrite $ed - 1= 2^s m$ then define $b_0 = a^m$ and $b_{i+1} = b_i^2 \pmod n$. Recall square root modulo, we know if $b_{i+1} \equiv 1\pmod n$ and $b_i \equiv \pm 1\pmod n$, then $n \mid b_i + 1$ or $n \mid b_i-1$.

If $b_i\not\equiv\pm 1\pmod n$, interesting things happen. $b_i \equiv k \pmod n$, then $(k-1)(k+1)\equiv 0\pmod n$, then $\gcd{(k-1,n)}$ and $\gcd{(k+1, n)}$ are non-trivial factors for $n$ ($k \in \lbrack 0, k-1\rbrack$).

RSA Problem

Let $n$ be a large integer and $e > 0$ coprime to $\varphi(n)$. Given $y$ in $U(\mathbb{Z}/n\mathbb{Z})$, compute $x$ such that $x^e\equiv y \pmod n$.

Pollard’s Rho Algorithm

An idea is to remove all small factors consists in computing $\gcd{(n,P)}$ where $P = \prod\limits_{p < B} p$. This might be efficient for small primes, but it can be slow in large primes.

Let $n$ be a composite integer with an unknown prime factor $p\le \sqrt n$. Define the function $f:\mathbb{Z}/n\mathbb{Z}\to\mathbb{Z}/n\mathbb{Z}$, $f(x) = x^2+ 1\pmod n$.

Recursively define a sequence $(x_k)$ by $x_0=2,x_{k+1}=f(x_k), k\in\mathbb{N}$. The sequence must at some point produce a repeated value and enter a cycle.

We hope the cycle contains two or more elements with same remainder modulo $p$: $x_i \equiv x_j \pmod p$. In this case, $\gcd{(x_i-x_j,n)}$ is a factor of $n$.

In summary the result can be evaluated as $\gcd{(x_i - x_j,n)} =\begin{cases} n &\text{if }x_i=x_j\newline 1 & \text{if }x_i\not\equiv x_j\pmod p, \forall p \text{ as factor of }n\newline t & \text{if }x_i \equiv x_j\pmod p, \text{where }p\mid t,t\mid n \end{cases}$

The algorithm now uses a pair of sequence $(x_k),(y_k)$ that $\begin{cases}x_0 = 2\newline x_{k+1} = f(x_k)\end{cases}$ and $\begin{cases}y_0 = 2\newline y_{k+1}=f(f(y_k)) \end{cases}$. For each pair of $(x_i, x_j)$, $\gcd{(x_i - x_j, n)}$ is evaluated.
$$
\begin{aligned}
&\text{Input: }n, \text{a composite integer}, f(x) = x^2 + 1\pmod n.\newline
&\text{Output: }d\text{ a non-trivial factor of }n,\text{ or failure}.\newline
&\text{repeat}\newline
&\phantom{“”””}a\leftarrow f(a);b\leftarrow f(f(b));\newline
&\phantom{“”””}d \leftarrow \gcd{(a-b,n)};\newline
&\text{until }d \neq 1;\newline
&\text{if }d=n\text{ then}\newline
&\phantom{“”””}\text{return failure}\newline
&\text{else}\newline
&\phantom{“”””}\text{return }d\newline
&\text{end if}
\end{aligned}
$$

The role of $f$ is to “randomly” choose numbers in $\mathbb{Z}/n\mathbb{Z}$. It should be a polynomial for $f(f(x)\pmod n)\pmod n = f(f(x))\pmod n$.

Complexity

Suppose the algorithm selects random numbers $x_i,x_j\in\mathbb{Z}/n\mathbb{Z}$ for comparison of their remainders.

Suppose any given number between $0$ and $n$ has an equal probability $\dfrac{1}{p}$ of having a remainder $m$ modulo $p$ ($0 \le m < p$): $P\lbrack x_k\pmod p = m\rbrack = \dfrac{1}{p}$. Then $P\lbrack x_i\not\equiv x_j\pmod p\rbrack = \dfrac{p-1}{p}$.

Suppose $x_0,\dots,x_{k-1}$ has $k$ distinct remainders modulo $p$, then $x_k$ have a remainder different from them has possibility $\dfrac{p-k}{p}$.

Thus creating such $k + 1$ different remainder modulo $p$ enjoys possibility $P_k = P\lbrack x_i\not\equiv x_j\pmod p, i, j\in \lbrack 0,k\rbrack, i\neq j \rbrack = \prod\limits_{i\in\lbrack 0,k\rbrack} \dfrac{p-i}{p} = \dfrac{p!}{(p-k-1)! p^k}$.

If we want the $P_k > \dfrac{1}{2}$, or $1- P_k < \dfrac{1}{2}$, then $k > 1.177\sqrt p$. This means with a possibility $>\dfrac{1}{2}$, the algorithm can find same remainder modulo $p$. Thus this is $O(n^{\frac{1}{4}})$ complexity.

RSA-OAEP

RSA on textbook is not CCA secure, maybe some improvement can be applied.

Generate: $p,q,n,e,d$ and two random oracles $G,H:\lbrace 0,1\rbrace^{2l}\to\lbrace 0,1\rbrace^{2l}$.

Encrypt $m\in\lbrace 0,1\rbrace^l$:

  • Pick a random $r \in \lbrace 0,1\rbrace^{2l}$
  • Set $m’=m \parallel 0^l$
  • Compute $m’’=(G(r)\oplus m’)\parallel (r\oplus H(G(r)\oplus m’))$
  • $c = (m’’)^e\pmod n$

Decrypt ciphertext $c$:

  • $m’’ = c^d\pmod n$
  • $m’’ = m_1 \parallel m_2$
  • Recover $r = H(m_1) \oplus m_2$
  • Recover $m’ = m_1 \oplus G(r)$
  • If the $l$ last bits are not $0^l$ output error
  • Otherwise $m’ = m \parallel 0^l$

Discrete Logarithm Problem

Let $\mathbb{F}_q$ be a finite field, with $q=p^n$ for a positive integer $n$. Given $\alpha$ generator of $G$, a subgroup of $\mathbb{F}^\ast_q$ and $\beta\in G$, find $x$ such that $\beta = \alpha^x\in\mathbb{F}_q$.

$x$ is restricted to $0\le x < \text{ord}_{\mathbb{F}_q^\ast}(\alpha)$ since $x$ is unique only up to congruence $\mod {|G|}$.

Pollard Rho Again

Let $\alpha$ be a generator of a group $G$ of prime order $p$. Any element of $G$ can be written $\alpha^a\beta^b$ for some $a,b\in\mathbb{N}$ and $\beta\in G$.

Assuming $x\equiv y\pmod p$, then $\alpha^{a_1}\beta^{b_1}\equiv \alpha^{a_2}\beta^{b_2}\pmod p$. Then we rewrite it as $\beta^{b_1-b_2}\equiv \alpha^{a_2-a_1}\pmod p$. Take $\log_\alpha$ both sides leads to $(b_1 - b_2)\log_\alpha\beta = a_2 - a_1\pmod p$.

So long as $p\nmid (b_1 - b_2)$ we get $\log_\alpha\beta = \dfrac{a_2-a_1}{b_1-b_2}$.

The goal for Pollard Rho algorithm is to find $x \equiv y\pmod p$. We consider three partitions $G = S_1\cup S_2\cup S_3$, which are of approximately same size based on easily testable property.

Define $f = \begin{cases} \beta x&x\in S_1\newline x^2 &x \in S_2\newline \alpha x & x \in S_3 \end{cases}$, $g(a,x) = \begin{cases} a & x \in S_1 \newline 2a\pmod p & x \in S_2 \newline a + 1 \pmod p & x \in S_3 \end{cases}$, $h(b,x) = \begin{cases} b+1 \pmod p & x \in S_1 \newline 2b \pmod p & x \in S_2 \newline b & x \in S_3 \end{cases}$.

The function $f,g,h$ are defined such as the progress of $x$ and $y$ appears “random”.

$$
\begin{aligned}
&\text{Input: }\alpha\text{ a generator of }G,\text{ a group of prime order }p\text{ and }\beta\in G,f,g,h\newline
&\text{Output: }\log_\alpha\beta\text{ or failure}\newline
&a_1 \leftarrow 0; b_1\leftarrow 0;a_2\leftarrow 0;b_2\leftarrow 0;y\leftarrow 1;\newline
&\text{repeat}\newline
&\phantom{“”””}a_1\leftarrow g(a_1,x);b_1 \leftarrow h(b_1,y);\newline
&\phantom{“”””}x\leftarrow f(x);\newline
&\phantom{“”””}a_2\leftarrow g(g(a_1,x),x);b_2 \leftarrow h(h(b_1,y)));\newline
&\phantom{“”””}y\leftarrow f(f(y));\newline
&\text{until }x \not\equiv y\pmod p;\newline
&r \leftarrow b_1-b_2;\newline
&\text{if }r \neq 0\text{ then return }r^{-1}(a_2 - a_1)\pmod p;\newline
&\text{else return failed};\newline
\end{aligned}
$$

Diffie-Hellman Key Exchange

Alice and Bob publicly agree on parameter:

  • $G$ a group of order $p$
  • $\alpha$ a generator of $G$

Both Alice and Bob generate a random secret from $G:x,y$. They send each other the $\alpha^{secret}:\alpha^x,\alpha^y$. By calculating $\alpha^{xy}$ they get the key.

Diffie-Hellman Problem

If you solve DLP, we can break Diffle-Hellman Key Exchange Protocal. However, it is not necessary to solve DLP to know $\alpha^{xy}$.

Computational Diffie-Hellman (CDH): given $\alpha^x,\alpha^y$, for some unknown integer $x,y$, compute $\alpha^{xy}$.

Decisional Diffie-Hellman (DDH): given $\alpha^x,\alpha^y$, decide whether or not some $c\in G$ is equal to $\alpha^{xy}$.

Multiplication is not so practical, so we use DLP to get $x$ from $\log_\alpha \alpha^x$ first, then $(\alpha^y)^x$.

While solving DLP implies solving CDH, it is not known whether or not solving CDH solves DLP.

Elgamal Cryptosystem

$G$ a group of prime order $p$, $\alpha$ a generator of $G$.

$x$ is a secret number from Bob and $\beta = \alpha^x \pmod p$.

Encryption:

  • $r = \alpha^k\pmod p$ for some random integer $k$.
  • $t \equiv \beta^k m$ where $m$ is message.
  • Send $c = \langle r,t\rangle$.

Decryption:

  • Compute $t r^{-x}\equiv \beta^k m(\alpha^k)^{-x}\equiv m\pmod p$.

Solving CDH is equivalent to breaking Elgamal.

In CDH, we have to use $\alpha^a,\alpha^b$ to compute $\alpha^{ab}$. Set $\beta =\alpha^a,r=\alpha^b$. Then $m\equiv tr^{-a}\equiv t\alpha^{-ab}$.

CCA on Elgamal

By definition, we can $c = \langle r,t\rangle = \langle \alpha^k,\beta^k m\rangle$. Then construct a message $m’$, compute $c’’=\langle r\alpha^{k’},t\beta^{k’}m’\rangle$.

Decrypt $c’’$ and we get $m’’ = (r\alpha^{k’})^{-x}t\beta^{k’}m’ = (\alpha^{k+k’})^{-x}\beta^{k+k’’} m m’ = mm’$. Compute $m=m’’ m’^{-1}$.