# Crypto Exam 1
$\text{(3)}$
\begin{align}
x^{67} &\equiv 35 \text{ (mod 127)}
\end{align}

\begin{align}
67d &\equiv 1 \text{ (mod 126)}
\end{align}

\begin{align}
126=67(1)+59
\end{align}

\begin{align}
67=59(1)+8
\end{align}

\begin{align}
59=8(7)+3
\end{align}

\begin{align}
8=3(2)+2
\end{align}

\begin{align}
3=2(1)+1
\end{align}

\begin{align}
2=1(2)+0
\end{align}

||| 1 | 1 | 7 | 2 | 1 | 2 |
|:-----:|-----|-|-|-|-|-|-|
|0|1|1|2|15|32|47|126|
|1|0|1|1|8|17|25|67|

\begin{align}
126(25) + 67(-47)=1
\end{align}

\begin{align}
-47\,\, \text{( mod 126)}=79
\end{align}

\begin{align}
79_{10}= 1001111_{2}
\end{align}

\begin{align}
x= 35^{79} \text{(mod 127)}
\end{align}

\begin{align}
35\cdot82\cdot120\cdot49\cdot35 \,\,\ \text{(mod 127)}= 115
\end{align}

$\text{(4)}$
\begin{align}
e=91,\,\,p=97,\,\, q=101
\end{align}

$\,\,\,\,\,\ \text{(a)}$

\begin{align}
(p-1)(q-1)=9600
\end{align}

\begin{align}
gcd((p-1)(q-1),e)
\end{align}

\begin{align}
gcd((9600,91)=1
\end{align}

\begin{align}
9600=91(105)+45
\end{align}

\begin{align}
91=45(2)+1
\end{align}

\begin{align}
45=1(45)+0
\end{align}

$\text{This shows that this problem will work since the gcd is 1. }$

$\,\,\,\,\, \text{(b)}$
$\,\,\,\,\,\,\,\,\,\, N=pq=9797$
$\,\,\,\,\,\,\,\,\,\, m=2153$
$\,\,\,\,\,\,\,\,\,\,c=m^{e} \text{(mod N)}$
$\text{c is the encrypted message that is sent.}$

\begin{align}
c=2153^{91} \text{(mod 9797)}
\end{align}

\begin{align}
91_{10}=1011011_{2}
\end{align}

\begin{align}
2153\cdot1428\cdot3470\cdot387\cdot2620 \text{(mod 9797)}=4816 \text{(mod 9797)}
\end{align}

\begin{align}
c=4816
\end{align}

$\,\,\,\,\, \text{(c)}$
$\,\,\,\,\,\,\,\,\,\, de=1\,\,\text{mod}\,\,\dfrac{(p-1)(q-1)}{ gcd(p-1)(q-1)}$

\begin{align}
gcd((96,100)=4
\end{align}

\begin{align}
91d=1 \text{mod 2400}
\end{align}

\begin{align}
2400=91(26)+34
\end{align}

\begin{align}
91=34(2)+23
\end{align}

\begin{align}
34=23(1)+11
\end{align}

\begin{align}
23=11(2)+1
\end{align}

\begin{align}
11=1(11)+0
\end{align}

\begin{align}
gcd(2400,91)=1
\end{align}

||| 26 | 2 | 1 | 2 | 11 |
|:-----:|-----|-|-|-|-|-|
|0|1|26|53|79|211|2400|
|1|0|1|2|3|8|91|

\begin{align}
91(211)+2400(-8)=1
\end{align}

\begin{align}
d=211
\end{align}

$\,\,\,\,\, \text{(d)}$
$\,\,\,\,\,\,\,\,\,\, m=c^d\,\, \text{mod N}$

\begin{align}
4816^{211} \text{mod 9797}
\end{align}

\begin{align}
211_{10}=11010011_{2}
\end{align}

\begin{align}
4816\cdot4357\cdot387\cdot2620\cdot6500 \,\,\text{mod 9797}= 2153
\end{align}