CSE442T Introduction to Cryptography (Lecture 10)

Chapter 2: Computational Hardness

Discrete Log Assumption (Assumption 52.2)

This is collection of one-way functions

p\gets \tilde\Pi_n(\textup{ safe primes }), p=2q+1

a\gets \mathbb{Z}*_{p};g=a^2(\textup{ make sure }g\neq 1)

f_{g,p}(x)=g^x\mod p

f:\mathbb{Z}_q\to \mathbb{Z}^*_p

Evidence for Discrete Log Assumption

Best known algorithm to always solve discrete log mod p, $p\in \Pi_n$

O(2^{\sqrt{2}\sqrt{\log(n)}})

RSA Assumption

Let $e$ be the exponents

P[p,q\gets \Pi_n;N\gets p\cdot q;e\gets \mathbb{Z}_{\phi(N)}^*;y\gets \mathbb{N}_n;x\gets \mathcal{A}(N,e,y);x^e=y\mod N]<\epsilon(n)

Theorem 53.2 (RSA Algorithm)

This is a collection of one-way functions

$I=\{(N,e):N=p\cdot q,p,q\in \Pi_n \textup{ and } e\in \mathbb{Z}_{\phi(N)}^*\}$

$D_{(N,e)}=\mathbb{Z}_N^*$

$R_{(N,e)}=\mathbb{Z}_N^*$

$f_{(N,e)}(x)=x^e\mod N$

Example:

On encryption side

$p=5,q=11,N=5\times 11=55$ , $\phi(N)=4*10=40$

pick $e\in \mathbb{Z}_{40}^*$ . say $e=3$ , and $f(x)=x^3\mod 55$

pick $y\in \mathbb{Z}_{55}^*$ . say $y=17$ . We have $(55,3,17)$

$x^{40}\equiv 1\mod 55$

$x^{41}\equiv x\mod 55$

$x^{40k+1}\equiv x \mod 55$

Since $x^a\equiv x^{a\mod 40}\mod 55$ (by corollary of Fermat’s little Theorem: $a^x\mod N=a^{x\mod \Phi(N)}\mod N$ s )

The problem is, what can we multiply by $3$ to get $1\mod \phi(N)=1\mod 40$ .

by computing the multiplicative inverse using extended Euclidean algorithm we have $3\cdot 27\equiv 1\mod 40$ .

$x^3\equiv 17\mod 55$

$x\equiv 17^{27}\mod 55$

On adversary side.

they don’t know $\phi(N)=40$

f(N,e):\mathbb{Z}_N^*\to \mathbb{Z}_N^*

is a bijection.

Proof

Suppose $x_1^e\equiv x_2^e\mod n$

Then let $d=e^{-1}\mod \phi(N)$ (exists b/c $e\in\phi(N)^*$ )

So $(x_1^e)^d\equiv (x_2^e)^d\mod N$

So $x_1^{e\cdot d\mod \phi(N)}\equiv x_2^{e\cdot d\mod \phi(N)}\mod N$ (Euler’s Theorem)

$x_1\equiv x_2\mod N$

So it’s one-to-one.

Let $y\in \mathbb{Z}_N^*$ , letting $x=y^d\mod N$ , where $d\equiv e^{-1}\mod \phi(N)$

$x^e\equiv (y^d)^e \equiv y\mod n$

Proof

It’s easy to sample from $I$ :

pick $p,q\in \Pi_n$ . $N=p\cdot q$
compute $\phi(N)=(p-1)(q-1)$
pick $e\gets \mathbb{Z}^*_N$ . If $gcd(e,\phi(N))\neq 1$ , pick again ( $\mathbb{Z}_{\phi_(N)}^*$ has plenty of elements.)

Easy to sample $\mathbb{\mathbb{Z}_N^*}$ (domain).

Easy to compute $x^e\mod N$ .

Hard to invert:

\begin{aligned} &~~~~P[(N,e)\in I;x\gets \mathbb{Z}_N^*;y=x^e\mod N:f(\mathcal{A}((N,e),y))=y]\\ &=P[(N,e)\in I;x\gets \mathbb{Z}_N^*;y=x^e\mod N:x\gets \mathcal{A}((N,e),y)]\\ &=P[(N,e)\in I;y\gets \mathbb{Z}_N^*;y=x^e\mod N:x\gets \mathcal{A}((N,e),y),x^e\equiv y\mod N]\\ \end{aligned}

By RSA assumption

The second equality follows because for any finite $D$ and bijection $f:D\to D$ , sampling $y\in D$ directly is equivalent to sampling $x\gets D$ , then computing $y=f(x)$ .

Theorem If inverting RSA is hard, then factoring is hard.

\textup{ RSA assumption }\implies \textup{ Factoring assumption}

If inverting RSA is hard, then factoring is hard.

i.e If factoring is easy, then inverting RSA is easy.

Proof:

Suppose $\mathcal{A}$ is an adversary that breaks the factoring assumption, then

P[p\gets \Pi_n;q\gets \Pi_n;N=p\cdot q;\mathcal{A}(N)=(p,q)]>\frac{1}{p(n)}

infinitely often.for a polynomial $p$ .

Then we designing $B$ to invert RSA.

Suppose

$p,q\gets \Pi_n;N=p\cdot q;e\gets \mathbb{Z}_{\phi(N)}^*;x\gets \mathbb{Z}^n;y=x^e\mod N$


def B(N,e,y):
    """
    Goal: find x
    """
    p,q=A(N)
    if n!=p*q:
        return None
    phiN=(p-1)*(q-1)
    # find modular inverse of e \mod N
    d=extended_euclidean_algorithm(e,phiN)
    # returns (y**d)%N
    x=fast_modular_exponent(y,d,N)
    return x

So the probability of B succeeds is equal to A succeeds, which $>\frac{1}{p(n)}$ infinitely often, breaking RSA assumption.

Remaining question: Can $x$ be found without factoring $N$ ? $y=x^e\mod N$

One-way permutation (Definition 55.1)

A collection function $\mathcal{F}=\{f_i:D_i\to R_i\}_{i\in I}$ is a one-way permutation if

$\forall i,f_i$ is a permutation
$\mathcal{F}$ is a collection of one-way functions

basically, a one-way permutation is a collection of one-way functions that maps $\{0,1\}^n$ to $\{0,1\}^n$ in a bijection way.

Trapdoor permutations

Idea: $f:D\to R$ is a one-way permutation.

$y\gets R$ .

Finding $x$ such that $f(x)=y$ is hard.
With some secret info about $f$ , finding $x$ is easy.

$\mathcal{F}=\{f_i:D_i\to R_i\}_{i\in I}$

$\forall i,f_i$ is a permutation
$(i,t)\gets Gen(1^n)$ efficient. ( $i\in I$ paired with $t$ ), $t$ is the “trapdoor info”
$\forall i,D_i$ can be sampled efficiently.
$\forall i,\forall x,f_i(x)$ can be computed in polynomial time.
$P[(i,t)\gets Gen(1^n);y\gets R_i:f_i(\mathcal{A}(1^n,i,y))=y]<\epsilon(n)$ (note: $\mathcal{A}$ is not given $t$ )
(trapdoor) There is a p.p.t. $B$ such that given $i,y,t$ , B always finds x such that $f_i(x)=y$ . $t$ is the “trapdoor info”

Theorem RSA is a trapdoor

RSA collection of trapdoor permutation with factorization $(p,q)$ of $N$ , or $\phi(N)$ , as trapdoor info $f$ .