From efd533331d6a7f0c51ef857af448a6c84c3084ed Mon Sep 17 00:00:00 2001
From: Camil Staps
Date: Fri, 12 Feb 2016 15:01:00 +0100
Subject: Removed spaces in path

---
 Assignment 6/CamilStaps-assignment6.tex | 143 --------------------------------
 1 file changed, 143 deletions(-)
 delete mode 100644 Assignment 6/CamilStaps-assignment6.tex

(limited to 'Assignment 6/CamilStaps-assignment6.tex')

diff --git a/Assignment 6/CamilStaps-assignment6.tex b/Assignment 6/CamilStaps-assignment6.tex
deleted file mode 100644
index 0cf6b88..0000000
--- a/Assignment 6/CamilStaps-assignment6.tex	
+++ /dev/null
@@ -1,143 +0,0 @@
-\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}
-- 
cgit v1.2.3

