215 lines
5.2 KiB
Markdown
215 lines
5.2 KiB
Markdown
# 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.
|
|
|
|
<details>
|
|
<summary>Proof</summary>
|
|
|
|
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.
|
|
|
|
</details>
|
|
|
|
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$
|
|
|
|
<details>
|
|
<summary>Proof</summary>
|
|
|
|
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)$.
|
|
|
|
</details>
|
|
|
|
#### 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$
|
|
|
|
``` python
|
|
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
|
|
|
|
1. $\forall i,f_i$ is a permutation
|
|
2. $\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}$
|
|
|
|
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]<\epsilon(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$.
|