diff options
Diffstat (limited to 'Assignment6/CamilStaps-assignment6.tex')
| -rw-r--r-- | Assignment6/CamilStaps-assignment6.tex | 143 |
1 files changed, 143 insertions, 0 deletions
diff --git a/Assignment6/CamilStaps-assignment6.tex b/Assignment6/CamilStaps-assignment6.tex new file mode 100644 index 0000000..0cf6b88 --- /dev/null +++ b/Assignment6/CamilStaps-assignment6.tex @@ -0,0 +1,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} |