\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}