$(10$pt$)$ In the textbook RSA scheme which is deterministic, the system parameter is as follows: $N=33,$ and $e=3.$ Note that $(N,e),m$ and $)=((d),c{c}^d$modN

$($a$)$ Compute a secret key $d.$

$(20$pt$)$ The schnorr signature scheme is given as follows: Setup$(,p)$:$glar{r}^{\text{\$}}{Z}_p^{**},xlar{r}^{\text{\$}}{Z}_{p-1}^{**},pk=(g,y)=(g,g^x)$ and $sk=(x).$

$H(g^r||m)mod(p-1).$ Return $.$

$1$

ITE $3031($Spring $2019)$: Final Examination

$)=(({}_1,{}_2)$

If $p=13,g=2,x=5,m=3$ then compute $pk$ and a signature. And then perform to verify the signature with $m=3.$ Note that let $H(x||y)=x+y.$

If adversary can forge the schnorr signature scheme, which intractable problem is broken? Using the above setting, break the intractable assumption.

$13.(20$pt$)$ We call $N$ as a Blum integer if $N=pq$ such that pmod$4=3$ and qmod$4=3.$ For a given $ain{Z}_N^{**},$ if adversary can compute $a^{2^{-1}}$ then we can factor $N$ as following. Note that with a half probability, $a($called a quadratic residue$)$ is a square of a certain number in $Z_N^{**}.$

We choose a random $vin{Z}_N^{**}$ and compute $v^2.$ And then we give $v^2$ to adversary $.$ Then adversary returns a square root of $v^2.$ There are $4$ square roots of $v^2,$ and for two numbers $w+-v,gcd(w-v,N)=p$ or $q.$

For $N=21,$ we choose $v=2.$ Assume that adversary receives $4.$ List all square roots of $4.$ And show that $gcd(w-v,N)=p$ or $q$ by computing $w.$ Using $w,$ factor $N.$

$14.(20$pt$)$ Write a GQ signature scheme. Using the random oracle model, you can compute $(\frac{Z}{Z^{\text{'}}}{)}^e=H(ID{)}^{H(Y||m)-H^{\text{'}}(Y||m)}$ where $Y=R^e$ in the GQ$.$ Assume that $H(*)$ returns a $256-$bit number and $Z,Z^{\text{'}},Yin{Z}_N^{**}$ where $N$ is a $2048-$bit. Using the previous problem, you can break the factoring problem of $N$ if adversary can forge a signature in the GQ when $N$ is a blum integer. Explain how to factor $N.$