1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
|
\documentclass[a4paper]{article}
\usepackage{amsmath,amssymb,amsthm,url,graphicx,comment,enumerate,color,array,inconsolata,minted,subcaption,adjustbox}
\usepackage[margin=2cm]{geometry}
\usepackage[hidelinks]{hyperref}
\usepackage{fancyvrb}
\usepackage{scrextend}
\usepackage{fancyhdr} % Custom headers and footers
\pagestyle{fancyplain} % Makes all pages in the document conform to the custom headers and footers
\fancyhead{} % No page header - if you want one, create it in the same way as the footers below
\fancyfoot[L]{} % Empty left footer
\fancyfoot[C]{Copyright {\footnotesize\copyright} 2015 Camil Staps} % Empty center footer
\fancyfoot[R]{\thepage} % Page numbering for right footer
\renewcommand{\headrulewidth}{0pt} % Remove header underlines
\renewcommand{\footrulewidth}{0pt} % Remove footer underlines
\setlength{\headheight}{13.6pt} % Customize the height of the header
\title{Homework $6$}
\author{Camil Staps (s4498062)}
\DeclareMathOperator{\ord}{ord}
\DeclareMathOperator{\lcm}{lcm}
\DeclareMathOperator{\lsb}{lsb}
\DeclareMathOperator{\Prob}{Pr}
\DeclareMathOperator{\Adv}{Adv}
\DeclareMathAlphabet{\pazocal}{OMS}{zplm}{m}{n}
\usepackage{algpseudocode}
\begin{document}
\maketitle
\section*{Solution}
\begin{enumerate}
\item We double the point using formulae described at \url{https://crypto.stanford.edu/pbc/notes/elliptic/explicit.html}. We compute $R=2P=[x_R,y_R]$ with $x_R=\lambda^2-11-2\cdot2,y_R=\lambda\cdot(2-x_R)-7$ where
$$\lambda = \frac{3\cdot2^2+2\cdot11\cdot2+17}{2\cdot7} = 73\cdot14^1 \equiv 11\cdot20 \equiv 3 \pmod{31}.$$
As explained there, this gives the tangent line on $\mathcal{E}$ at $P$: $y=\lambda\cdot x-6+7=3x+1$.
Furthermore we have $x_R = 3^2-15=-6\equiv25\pmod{31}, y_R=3\cdot(2-25)-7=-76\equiv17\pmod{31}$ and thus $2P=R=[25,17]$.
\item
\begin{enumerate}
%\item We have $15^3+23\cdot15^2+7\cdot15+1 \equiv 5 \pmod{41}$ and $8^2 \not\equiv 5 \pmod{41}$, so $P$ is not on $\mathcal{E}$. We have $2^3+23\cdot2^2+7\cdot2+1 \equiv 33 \equiv 19^2 \pmod{41}$, so $Q$ is on $\mathcal{E}$.
\item We have $16^3+35\cdot16+17 = 4673 \equiv 40 \equiv 1024 = 32^2 \pmod{41}$, so $P$ is on $\mathcal{E}$. We have $9^3+35\cdot9+17 = 1061 \equiv 36 \equiv 1225 = 35^2 \pmod{41}$, so also $Q$ is on $\mathcal{E}$.
\item For doubling $P$, we compute $\lambda = \frac{3\cdot x_P^2 + 35}{2\cdot y_P} = 803\cdot64^{-1} \equiv 24\cdot23^{-1} \equiv 24\cdot25 \equiv 26\pmod{41}$. This gives
\begin{align*}
x_{2P} &= \lambda^2-2x_P = 26^2-2\cdot16 = 644 \equiv 29 \pmod{41}\\
y_{2P} &= \lambda(x_P-x_{2P}-y_P = 26(16-29) - 32 = -370 \equiv 40 \pmod{41}
\end{align*}
yielding $2P = [29,40]$.
For adding, we compute $\lambda=\frac{y_P-y_Q}{x_P-x_Q}=-3\cdot7^{-1}\equiv38\cdot6\equiv23\pmod{41}$. This gives
\begin{align*}
x_{P+Q} &= \lambda^2-x_P-x_Q = 23^2-25=551\equiv12\pmod{41}\\
y_{P+Q} &= \lambda(x_P-x_{P+Q})-y_P = 23\cdot4-32 = 60 \equiv 19 \pmod{41}
\end{align*}
yielding $P+Q = [12,19]$.
\end{enumerate}
\newpage
\item
\begin{enumerate}
\item Using sage:
\begin{minted}[fontsize=\footnotesize,breaklines,tabsize=0]{python}
sage: n = 99177088366023448437328155378814540807926939493785872596706396776111511
sage: e = 49
sage: s_1 = 52182506035573798513195935894740627677637125435048460721682242234091429
sage: s_2 = 47616461307709097579789645077805168973449178313679751343338944408311333
sage: mod(s_1 ^ e, n)
12345678901234567
sage: mod(s_2 ^ e, n)
28500797465696216321448721267454933034082336986084351692960292520620026
\end{minted}
It's definitely not certain, but \texttt{12345678901234567} looks more like a message than the other result, so I would guess that \texttt{s\_1} is the correct signature.
\item Using the method from the slides, we compute $q = \gcd(n,s_1-s_2)$ and then $p=\frac{n}{q}$ with:
\begin{minted}[fontsize=\footnotesize,breaklines,tabsize=0]{python}
sage: q = gcd(n, s_1 - s_2); q
1264980678894295608947972498859964913
sage: p = n / q; p
78402057850174397975612616068106247
\end{minted}
\item This is textbook RSA.
\begin{minted}[fontsize=\footnotesize,breaklines,tabsize=0]{python}
sage: m = 12345678901234567
sage: m = mod(m, n)
sage: d = inverse_mod(e, (p-1)*(q-1))
\end{minted}
And verifying:
\begin{minted}[fontsize=\footnotesize,breaklines,tabsize=0]{python}
sage: m ^ d == s_1
True
\end{minted}
\item
Simply implementing the algorithm from the slides gives:
\begin{addmargin}[2em]{0pt}
\begin{minted}[fontsize=\footnotesize,breaklines,tabsize=0,linenos]{python}
"""Sign a message using Garner's method
Arguments (all ints):
p -- the first prime used to generate the RSA key
q -- the second prime used to generate the RSA key
d -- the private key
m -- the message to sign
"""
def sign(p, q, d, m):
n = p * q
d_p = mod(d, p - 1)
d_q = mod(d, q - 1)
i_q = inverse_mod(q, p)
m = mod(m, n)
s_p = int(mod(m ** d_p, p))
s_q = int(mod(m ** d_q, q))
s = s_q + q * int(mod(i_q * (s_p - s_q), p))
return s
\end{minted}
\end{addmargin}
A usage example (also providing verification):
\begin{minted}[fontsize=\footnotesize,breaklines,tabsize=0]{python}
sage: load("garner.py")
sage: sign(p, q, d, m)
52182506035573798513195935894740627677637125435048460721682242234091429
\end{minted}
\end{enumerate}
\end{enumerate}
\end{document}
|
