Lecture 10

Continue

Discrete Log Assumption

This is collection of one-way functions

Evidence for Discrete Log Assumption

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

RSA Assumption

Let $e$ be the exponents

Theorem 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$

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.

EOP

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:

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)$.

EOP

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

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

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$

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}$

1. $\forall i,f_i$ is a permutation
2. $(i,t)\gets Gen(1^n)$ efficient. ($i\in I$ paired with $t$), $t$ is the "trapdoor info"
3. $\forall i,D_i$ can be sampled efficiently.
4. $\forall i,\forall x,f_i(x)$ can be computed in polynomial time.
5. $P[(i,t)\gets Gen(1^n);y\gets R_i:f_i(\mathcal{A}(1^n,i,y))=y]<\varepsilon(n)$ (note: $\mathcal{A}$ is not given $t$)
6. (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$.