thesis_talotti.tex

%% Le lingue utilizzate, che verranno passate come opzioni al pacchetto babel. Come sempre, l'ultima indicata sarà quella primaria.
%% Se si utilizzano una o più lingue diverse da "italian" o "english", leggere le istruzioni in fondo.
\def\thudbabelopt{italian,english}
%% Valori ammessi per target: bach (tesi triennale), mst (tesi magistrale), phd (tesi di dottorato).
%% Valori ammessi per aauheader: '' (vuoto -> nessun header Alpen Adria Univeristat), aics (Department of Artificial Intelligence and Cybersecurity), informatics (Department of Informatics Systems). Il nome del dipartimento è allineato con la versione inglese del logo UniUD.
%% Valori ammessi per style: '' (vuoto -> stile moderno), old (stile tradizionale).
\documentclass[target=mst,aauheader=,style=]{thud}

%% --- Informazioni sulla tesi ---
%% Per tutti i tipi di tesi
% Scommentare quello di interesse, o mettete quello che vi pare
\course{Mathematics}
%\course{Internet of Things, Big Data e Web}
%\course{Matematica}
%\course{Comunicazione Multimediale e Tecnologie dell'Informazione}
\title{Identification of weak keys in Elliptic Curves Cryptography}
\author{Enrico Talotti}
\supervisor{Prof.\ Marino Miculan}
\cosupervisor{Prof.\ Pietro De Poi}
%\tutor{Guido Necchi}
%% Campi obbligatori: \title, \author e \course.
%% Altri campi disponibili: \reviewer, \tutor, \chair, \date (anno accademico, calcolato in automatico), \rights
%% Con \supervisor, \cosupervisor, \reviewer e \tutor si possono indicare più nomi separati da \and.
%% Per le sole tesi di dottorato:
%\phdnumber{313}
%\cycle{XXVIII}
%\contacts{Via della Sintassi Astratta, 0/1\\65536 Gigatera --- Italia\\+39 0123 456789\\\texttt{http://www.example.com}\\\texttt{inbox@example.com}}

%% --- Pacchetti consigliati ---
%% pdfx: per generare il PDF/A per l'archiviazione. Necessario solo per la versione finale
\usepackage[a-1b]{pdfx}
%% hyperref: Regola le impostazioni della creazione del PDF... più tante altre cose. Ricordarsi di usare l'opzione pdfa.
\usepackage[pdfa]{hyperref}
%% tocbibind: Inserisce nell'indice anche la lista delle figure, la bibliografia, ecc.

%% --- Stili di pagina disponibili (comando \pagestyle) ---
%% sfbig (predefinito): Apertura delle parti e dei capitoli col numero grande; titoli delle parti e dei capitoli e intestazioni di pagina in sans serif.
%% big: Come "sfbig", solo serif.
%% plain: Apertura delle parti e dei capitoli tradizionali di LaTeX; intestazioni di pagina come "big".

\usepackage{listings}
\usepackage{xcolor}
\definecolor{codegreen}{rgb}{0,0.6,0}
\definecolor{codegray}{rgb}{0.5,0.5,0.5}
\definecolor{codepurple}{rgb}{0.58,0,0.82}
\definecolor{backcolour}{rgb}{0.87,0.87,0.87}
\lstdefinelanguage{pari}{
	, morecomment=[s]{/*}{*/}%
	, morestring=[b]{"}
%	, morekeywordcomment=[4]{1,2,3,4,5,6,7,8,9,0}
	, morekeywords=[2]{ foreach, else, for, if, in, loop, return, while}
	, morekeywords=[3]{ divisors, eulerphi, setminus, ceil, sqrt, log,Mod,ellorder,ellinit,isprime,znprimroot}
	}

\lstdefinestyle{mystyle}{
	%literate=%
%	{/*}{{{\ProcessComment{/*}}}}1% Disable coloring within single quote
%	{0}{{{\ColorIfNotInString{0}}}}1
%	{1}{{{\ColorIfNotInString{1}}}}1
%	{2}{{{\ColorIfNotInString{2}}}}1
%	{3}{{{\ColorIfNotInString{3}}}}1
%	{4}{{{\ColorIfNotInString{4}}}}1
%	{5}{{{\ColorIfNotInString{5}}}}1
%	{6}{{{\ColorIfNotInString{6}}}}1
%	{7}{{{\ColorIfNotInString{7}}}}1
%	{8}{{{\ColorIfNotInString{8}}}}1
%	{9}{{{\ColorIfNotInString{9}}}}1
%	{.0}{{\textcolor{blue}{.0}}}{2}% Following is to ensure that only periods
%	{.1}{{\textcolor{blue}{.1}}}{2}% followed by a digit are changed.
%	{.2}{{\textcolor{blue}{.2}}}{2}%
%	{.3}{{\textcolor{blue}{.3}}}{2}%
%	{.4}{{\textcolor{blue}{.4}}}{2}%
%	{.5}{{\textcolor{blue}{.5}}}{2}%
%	{.6}{{\textcolor{blue}{.6}}}{2}%
%	{.7}{{\textcolor{blue}{.7}}}{2}%
%	{.8}{{\textcolor{blue}{.8}}}{2}%
%	{.9}{{\textcolor{blue}{.9}}}{2}%
%	,
	backgroundcolor=\color{backcolour},   
	commentstyle=\color{codegreen},
	keywordstyle=\color{magenta}\bfseries,
	numberstyle=\footnotesize\color{gray},
	stringstyle=\color{codepurple},
	basicstyle=\ttfamily\footnotesize,
	breakatwhitespace=false,         
	breaklines=true,                 
	captionpos=t,                    
	keepspaces=true, 
	numbers=left,                                   
	numbersep=5pt,                  
	showspaces=false,                
	showstringspaces=false,
	showtabs=false,                  
	tabsize=2
  , keywordstyle=[2]\color{magenta}\bfseries
  , keywordstyle=[3]\color{blue}\bfseries
%  , keywordstyle=[3]\color{blu}
}

\lstset{language=pari, style=mystyle}
%%%%%%%5Definizioni,teoremi, proposizioni ...
\usepackage{amsmath,amsfonts,amssymb,amsthm}
\usepackage{cleveref}
\usepackage{textcomp}


\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
%\newcommand{\Fp}{\mathbb{F}_{p}}
\newcommand{\Fq}{\mathbb{F}_{q}}
\newcommand{\Zpstar}{\Z_p^*}
\newcommand{\F}{\mathbb{F}}
\newcommand{\K}{\mathbb{K}}
\newcommand{\clF}{\overline{\F}}
\newcommand{\clK}{\overline{\K}}
\newcommand{\Fqe}{\F_{q^e}}
\newcommand{\Fpe}{\F_{p^e}}
\newcommand{\Complessi}{\mathbb{C}}
\newcommand{\infp}{\mathcal{O}}
\theoremstyle{plain}
\newtheorem{teorema}{Theorem}[section]
\newtheorem{proposizione}[teorema]{Proposition}
\newtheorem{lemma}[teorema]{Lemma}
\newtheorem{corollario}[teorema]{Corollary}

\theoremstyle{definition}
\newtheorem{definizione}[teorema]{Definition}
\newtheorem{esempio}[teorema]{Exemple}

\theoremstyle{remark}
\newtheorem{osservazione}[teorema]{Remark}
\DeclareMathOperator{\aut}{Aut}
\DeclareMathOperator{\id}{id}



\begin{document}
\maketitle

%% Dedica (opzionale)
%\begin{dedication}
%	
%\end{dedication}

%%% Ringraziamenti (opzionali)
%\acknowledgements
%

%% Sommario (opzionale)
\abstract
In this master thesis we describe a weakness of \emph{public-key-cryprosystems} based on the \emph{Elliptic Curve Discrete Logarithm Problem} (\emph{ECDLP}). These studies were carried out during my activity in the Laboratory of Mathematics with the Department of Mathematics Computer Science and Physics in Universit\`{a} degli Studi di Udine. The aim was to develop algorithms for elliptic curves, in particular the \emph{implicit baby step giant step}. I decided to use Rust programming language for implementation and the Computer Algebra System Pari-gp to give an assessment of weak keys in recommended elliptic curves. Codes are available on my GitHub repository \url{https://github.com/enh11/elliptic_curves}. 

%% Indice
\tableofcontents

%% Lista delle tabelle (se presenti)
\listoftables

%% Lista delle figure (se presenti)
%\listoffigures

%% Corpo principale del documento
\mainmatter

%% Parte
%% La suddivisione in parti è opzionale; solitamente sono sufficienti i capitoli.
%\part{Parte}
%\chapter{Introduction}

\chapter{Introduction}

Let $E:y^2 + a_1xy + a_3y = x^3 + a_2x^2+a_4x + a_6$ be an elliptic curve define over a finite field $\K$ and denote with $E(\K)$ the set of $\K$-rational points of $E$. In \cref{ellgeneric} we show how to turn $E(\K)$ into an abelian group with identity the point at infinity $\infp$ and with the operation $\oplus$ given by the \emph{chord-tangent} method. Let $P$ be a point in $E(\K)$, let $G$ be the cyclic subgroup of $E(\K)$ generated by $P$ and assume it has order $n$, then every point $Q\in G$ is give by $Q=[\alpha]P$ for some $\alpha\mod n$, where $[\alpha]P$ denotes the sum of $P$ with itself $\alpha$ times. The \emph{Elliptic Curves Discrete Logarithm Problem} (\emph{ECDLP}) is the problem to find the integer $\alpha\mod n$ given the generator $P$ and the point $Q$. In \cref{ellfinfilar} we discuss about arithmetic for elliptic curves defined over finite fields and we give some algorithms to compute the \emph{scalar multiplication} $Q=[\alpha]P$ in a very efficient way. On the other hand, there is no known algorithm that can solve the \emph{ECDLP} faster than $O(\sqrt{n})$. This makes scalar multiplication a \emph{one way function} and we can build the \emph{Elliptic Curves Cryptosystem} that includes well known protocols such as \emph{Diffie Hellman key-exchange} \cite{Diff}, \emph{ElGamal encryption} \cite{ElGam}, \emph{Elliptic Curves Digital Signature Algorithm}, \cite{fips}, \emph{Zero Knowledge Proof} protocols based on elliptic curves \cite{Zero1},\cite{Zero2}, \emph{etc}. Protocols involve a \emph{private-key} (or \emph{secret-key}) and its related \emph{public-key}, in particular, in the elliptic curves scenario, these keys are an integer $\alpha\mod n$ and the point $Q=[\alpha]P$ respectively.

Because scalar multiplication is a one way function, it is infeasible, in general, to detect the private key $\alpha$ given the public key $Q=[\alpha]P$; a secret key $\alpha$ that can be recovered by an attacker with significant less effort than expected, is considered to be \emph{weak}. Different types of weak keys may  exist, for example: 
\begin{itemize}
	\item if the private key is a small numerical value, then it can be found by exhaustive search. In 2019 several keys protecting user's Ethereum wallets were discovered because of their inappropriate bit length \cite{Eth}. Private keys are used to generate corresponding addresses of Ethereum or Bitcoin wallets and to create digital signatures needed to spend the cryptocurrency. The end result was that all the currency in the corresponding account was gone;
	\item if the public key $Q$ lies in a small subgroup of $E(\K)$, then the corresponding private key $\alpha$ can be easily be recovered. Weak keys of this type can be removed by choosing only elliptic curves groups with order a large prime $p$ or in some cases via \lq\lq bit clearing\rq\rq, zeroing some bits in the private keys to ensure that the corresponding public key lies in a sufficiently large subgroup of $E(\K)$. 
\end{itemize}

According to the previous examples, from now on we will assume $E(\K)$ to be of prime order $p$ with generator $P$ and we focus on the problem to find the private key $\alpha$ given the public key $Q=[\alpha]P$. A well known deterministic algorithm that can solve this problem with computational cost $O(\sqrt{p})$ is the \emph{Baby Step Giant Step} and it is presented in \cref{chapimplicit}. The aim of this thesis is to modify the baby step giant step by using the idea of the \emph{implicit representation} presented by Prabhat Kushwaha and Ayan Mahalanobis \cite{Pra1}. This will allow us to detect a different type of weak keys, as they occur purely because of factors of $p-1$ and thus they can be eliminated in practice by choosing elliptic curves groups with appropriate prime order $p$. 

We define the following group homomorphism:
\begin{alignat*}{2}
	\rho:\Zpstar &\longrightarrow& \aut(E(\K)) \\
	\alpha &\longmapsto&\rho_\alpha:E(\K)&\longrightarrow E(\K)\\
	&&P& \longmapsto {}[\alpha]P
\end{alignat*}
which leads to a faithful action of the multiplicative group $\Zpstar$ on $E(\K)$. Thus, we reduce the elliptic curve discrete logarithm in $E(\K)$ to a problem in $\Zpstar$. The advantage of this approach is that $\Zpstar$ has many subgroups and we can exploit its rich and well known structure to detect the private key $\alpha$. If $z$ is a primitive root in $\Zpstar$, then $\alpha=z^i\mod p$ for some $0\leq i<p-1$. If we find the value of $i$, then the discrete logarithm problem is solved. We can use the \emph{Implicit Baby Step Giant Step} described \cref{chapimplicit} to compute such an $i$ given the primitive element $z\in\Zpstar$, but there is still no improvement in the computational cost in relation to the classical baby step giant step, as it will require time $O(\sqrt{p-1})$. However, if divisors of $p-1$ are known, we can seek the private key into subgroups of $\Zpstar$. Let $d$ be a divisor of $p-1$ and compute the $d$-order generator $z_d=z^{\frac{p-1}{d}}$. If $\alpha$ happens to lie in a $d$ order subgroup $D$ of $\Zpstar$, then we can find an integer $k$ with $0\leq k<d$ such that $z_d^k=\alpha$ by using the implicit baby step giant step. This will require time $O(\sqrt{d})$, thus the main power of this method occurs when the secret key lies in a small subgroup of $\Zpstar$. 

In \cref{chanalysis} we focus on curves recommended by NIST \cite{nist}\cite{fips} and we give an assessment of weak keys in recommended and standardized elliptic curves, together with the worst-case number of scalar multiplications required to detect them. Least but not last, it's worth it to note that we can use the described method to generate private keys that are secure against this kind of attack. For this aim we restrict them to be a random power of $z^{\frac{p-1}{r}}$, where $z$ is a primitive element in $\Z_p$ and $r$ is a large prime factor of $p-1$, thus forcing the private key to lie in an $r$-order subgroup of $\Zpstar$. 
%% Capitolo
\chapter{Arithmetic of Elliptic Curves}\label{ellgeneric}
Elliptic curves come up naturally in several branches of mathematics. Here we will follow their development as a branch of arithmetic. 
\section{Background on elliptic curves}
\subsection{Affine equation}
We start with a practical definition of the concept of an elliptic curve. In the following we use the letters $\F,\mathbb{K}\dots$ to denote fields and $\clF,\overline{\mathbb{K}}\dots$ for their algebraic closures.
\begin{definizione}

An elliptic curve $E$ over a field $\K$, denoted $E/\K$, is given by the \emph{Weierstrass equation} 
\begin{equation}\label{ell}
	E:y^2 + a_1xy + a_3y = x^3 + a_2x^2+a_4x + a_6,
\end{equation}
where the coefficients $a_1,a_2,a_3,a_4,a_5,a_6\in\K$ are such that for each point $(x_1,y_1)\in\clK^2$ satisfying \cref{ell}, the partial derivatives do not vanish simultaneously. In other words the two equations
\begin{equation}\label{jacobi}
	2y+a_1x+a_3=0,\qquad 3x^2+2a_2x+a_4-a_1y=0,
\end{equation}
cannot be simultaneously satisfied by any point  $(x_1,y_1)\in\clK^2$.
\end{definizione}
The last condition says that an elliptic curve is $non$ $singular$ (or $smooth$). A point on a curve is called $singular$ if both partial derivatives vanish. We can express the smoothness condition more intrinsically. In odd characteristic, the transformation $$x\mapsto x'=x\qquad y\mapsto y'=y+(a_1x+a_3)/2,$$
leads to an isomorphic curve given by 
\begin{equation}
	y^2=x^3+\dfrac{b_2}{4}x^2+\dfrac{b_4}{2}x+\dfrac{b_6}{4},
\end{equation}
where $$b_2=a_1^2+4a_2,\qquad b_4=a_1a_3+2a_4,\qquad b_6=a_3^2+4a_6.$$ Moreover, if the characteristic of $\F$ is neither 2 nor 3, then we can also apply the transformation $$x\mapsto x'=x+\dfrac{b_2}{12},\qquad y\mapsto y'=y$$ which leads to the equation
\begin{equation}
y^2=x^3-\dfrac{c_4}{48}x-\dfrac{c_6}{864},
\end{equation}
where $c_4=b_2^2-24b_4$ and $c_6=-b_2^3+36b_2b_4-216b_6$. So, if $\K$ has characteristic prime to 6, we can always assume that an elliptic curve is given by a \emph{short Weierstrass} equation of the type
\begin{equation}\label{ShortWeierstrass}
	y^2=x^3+a_4x+a_6.
\end{equation}
In this case the smoothness condition is equivalent to requiring that the cubic on the right have no multiple roots. This holds if and only if the discriminant of $x^3+a_4x+a_6$, is nonzero.
\subsection{Projective coordinates and point at infinity}\label{projective}
\begin{definizione}
	Let $\K$ be a field as above and $\clK$ its algebraic closure. The \emph{2-dimentional projective space} $\mathbb{P}^2/\K:=\mathbb{P}^2$ \emph{over} $\K$ is the set of classes  of triples $(X,Y,Z)\in\clK^3\setminus \left\{(0,0,0)\right\}$ where two triples are said to be equivalent if they are a scalar multiple of one another; in other words,$$(X_1,Y_1,Z_1)\sim(X_2,Y_2,Z_2)\Leftrightarrow (X_2,Y_2,Z_2)=(kX_1,kY_1,kZ_1)\text{ for some }k\in\clK^*.$$
	The equivalence classes are called \emph{projective point} and we denote them with $(X_1:Y_1:Z_1)$.
\end{definizione}
If a projective point $(X:Y:Z)$ has nonzero $Z$, then there is one and only one triple in its equivalence class of the form $(x,y,1)$ which is obtained by the formula $x=X/Z,y=Y/Z$. Thus, the projective plane can be identified with all points $(x,y)$ of the affine plane plus the points for which $Z = 0$. The latter make up what is called the line at infinity. Any equation $F(x,y) = 0$ of a
curve in the affine plane corresponds to a \emph{homogeneous equation} $F(X, Y, Z) = 0$ satisfied by the corresponding projective points: simply replace $x$ by $X/Z$ and $y$ by $Y/Z$ and multiply by a power of $Z$ to clear the denominators. In addition to the points
with $Z\neq 0$, what projective points $(X, Y, Z)$ satisfy the homogeneous equation $F(X, Y, Z) = 0$? Setting
$Z = 0$ in the equation, we obtain $0 = X^3$, which leads to $X = 0$. But the
only equivalence class of triples $(X, Y, Z)$ with both $X$ and $Z$ zero is the class
of $(0,1,0)$. This is the point we call $\infp$ and can be visualized as the intersection of $y$-axis with the line at infinity.
Equation (\ref{ell}) express the curve in affine coordinates. We can consider the same elliptic curve in projective coordinates; in this case the equation is given by
\begin{equation}\label{ell_proj}
 E_{hom}:Y^2Z+a_1XYZ+a_3YZ^2=X^3+a_2X^2Z+a_4XZ^2+a_6Z^3.
\end{equation}
So we have a correspondence between point of $E_{hom}$ and point of $E$. 
\section{Short normal forms and invariants}
Now we have to decide which Weierstrass equations define isomorphic elliptic curves. We can restrict ourselves to isomorphisms that fix the point at infinity $\infp$. We shall continue to assume that the characteristic of $\K$ is prime to 6, so we can deal with short Weierstrass form \ref{ShortWeierstrass}. However, completely analogous discussions can be done for characteristics 2 and 3 and can be found in \cite{Sil2}. We look for invertible transformations of the affine coordinates space for
which the transformed equation is again a short Weierstrass form. It easy to see that conditions imposed on the transformations imply 
$$x\mapsto x'=u^2x\quad \text{and}\quad y\mapsto y'=u^3y\quad \text{with}\quad u\in\K^*$$ and the resulting equation is $$E': y'^2=x'^3+u^4a_4x'+u^6a_6.$$ We have the following:
\begin{proposizione}\label{classificazione1}
	Let $\K$ be a field with characteristic prime to 6. Let $E/\K$ be an elliptic curve given by a short Weierstrass equation $y^2=x^3+a_4x+a_6$. Then we have:
	\begin{enumerate}
		\item If $a_4=0$, then the coefficient of $x$ is equal to zero in all short Weierstrass equations isomorphic to $E$ and $a_6'$ is determined up to a sixth power in $\K^*$;
		\item  If $a_6=0$, then constant term is zero in all short Weierstrass equations isomorphic to $E$ and $a_4'$ is determined up to a forth power in $\K^*$;
		\item  If $a_4a_6\neq 0$, then $a_6'/a_4'$ is determined up to a square in $\K^*$;
	\end{enumerate}
And conversely:
\begin{enumerate}
	\item If $a_4=0$ then, $E$ is isomorphic to $E'$ if in a short Weierstrass form of $E'$, the coefficient $a_4'$ is zero and $a_6'/a_6$ is a sixth power in $\K^*$;
	\item If $a_6=0$ then, $E$ is isomorphic to $E'$ if in a short Weierstrass form of $E'$, the coefficient $a_6'$ is zero and $a_4'/a_4$ is a forth power in $\K^*$;
	\item If $a_4a_6\ne 0$ then, $E$ is isomorphic to $E'$ if in a short Weierstrass form of $E'$, we have $a_4'=v^2a_4$ and $a_6'=v^3a_6$ for some square $v\in\K^*$.
\end{enumerate}
\end{proposizione}
\begin{corollario}\label{classificazione2}
		Let $\K$ be a field with characteristic prime to 6. Let $E/\K$ be an elliptic curve in Weierstrass equation $y^2=x^3+a_4x+a_6$. Then we have:
\begin{enumerate}
	\item If $a_4=0$, then for every $a_6'\in\K^*$ the curve $E$ is isomorphic to the curve $$E':y^2=x^3+a_6'\ \text{over}\ \K\left(\sqrt[6]{a_6'/a_6}\right)$$
	\item If $a_6=0$, then for every $a_4'\in\K^*$ the curve $E$ is isomorphic to the curve $$E':y^2=x^3+a_4'x\ \text{over}\ \K\left(\sqrt[4]{a_4'/a_4}\right)$$
	\item If $a_4a_6\neq 0$, then for every $v\in\K^*$ the curve $E$ is isomorphic to the curve $$E_v:y^2=x^3+a_4'x+a_6'\ \text{over}\ \K\left(\sqrt{v}\right)\ \text{where}\ a_4'=v^2a_4\ \text{and}\ a_6'=v^3a_6.$$
\end{enumerate}
\end{corollario}
The curve in \cref{classificazione2} are called \emph{twist of E} and the curve $E_v$ is called \emph{quadratic twist}. Note that $E$ is isomorphic to $E_v$ over $\K$ if and only if $v$ is a square in $\K^*$.
\begin{osservazione}\label{twistsecurity}
	Let $q>3$ be a prime and let $\Fq$ be the finite field with $q$ elements. Every elliptic curve $E$ over $\Fq$ has a related quadratic twist curve $\tilde{E}_v$. Let $v\in\Fq$ be some quadratic non-residue in $\Fq$. If $E$ is the curve $y^2=x^3 + a_4x + a_6$ then its twist $\tilde{E}$ is the curve $v^{-1}y^2 = x^3 + a_4x + a_6,$ which is isomorphic to $E$ as one can see by multiplying by $v^3$ and by using the transformation $$x\mapsto x'=vx,\quad y\mapsto y'=vy.$$ 
\end{osservazione}
\subsection{The j-invariant}
Now we want to translate the results of \cref{classificazione1}  into \lq\lq invariants\rq\rq of $E$ that can be read off from any Weierstrass equation. As stated in the definition of elliptic curve, it has to be smooth, i.e., the roots of the cubic polynomial on the right-side of \cref{ShortWeierstrass}) must be simple. This happens if and only if the discriminant of the cubic is not equal to zero. 
\begin{definizione}
	Let $E$ be a curve define over $\K$ by the short Weierstrass equations (\ref{ShortWeierstrass}).The \emph{discriminant of the curve} $E$, denoted by $\Delta_E$ satisfies $$\Delta_E=-(4a_4^3 +27a_6^2).$$ The curve is non-singular, and thus an elliptic curve, if and only if $\Delta_E$ is non-zero. In this case, we introduce the \emph{j-invariant of E}, that is $$j_E=\frac{c_4^3}{\Delta_E}=12^3(-4a_4^3)/\Delta_E.$$
\end{definizione}
\begin{teorema}
	Let $\K$ be a field of characteristic prime to 6 and let $E:y^2=x^3+a_4x+a_6$, $E':y'^2=x'^3+a_4'x'+a_6'$ be two elliptic curves over $\K$ with $j$-invariants $j_E,\ j_{E'}$ respectively. If $j_E=j_{E'}$, then there exists $u\in\clK^*$ such that $$a_4'=u^4a_4,\qquad a_6'=u^6a_6.$$  The transformation $$x\mapsto x'=u^2x,\quad y\mapsto y'=u^3y$$ takes one equation to the other.
\end{teorema}
\begin{proof}
Assume $a_4\neq0$. Then we have $j_E=j_{E'}\neq 0$, thus $a_4'\neq 0$. Choose $u\in\clK^*$ such that $a_4'=u^4a_4$, then we have 
$$\dfrac{4a_4^3}{4a_4^3 +27a_6^2}=\dfrac{4a_4'^3}{4a_4'^3 +27a_6'^2}=\dfrac{4u^{12}a_4^3}{4u^{12}a_4^3 +27a_6'^2}=\dfrac{4a_4^3}{4a_4^3 +27u^{-12}a_6'^2},$$ which implies that $a_6'=\pm u^6a_6$. If $a_6'=u^6a_6$, we're done. Otherwise we can change $u$ to $iu$, where $i\in\clK^*$ is so that $i^2=-1$. This preserves the relation $a_4'=u^4a_4$ and
also yields $a_6'^2=u^6a_6$. 

If $a_4=0$, then also $a_4'=0$ and since $\Delta_E\neq 0\neq \Delta_{E'}$ we have $a_6\neq 0\neq a_6'$. Thus we can choose $u\in\clK^*$ such that $a_6'=u^6a_6$.
\end{proof}
Note that the $j$-invariant tells us when two curves are isomorphic over an algebraically closed field. If we are working with a non-algebraically
closed field $\K$, then it is possible to have two curves with the same $j$-invariant that cannot be transformed into each other by any transformation with coefficients in $\K$, however, we can use an extension field of $\K$. In agreement with \cref{classificazione2}, two curves with the same $j$-invariant are said to be $twist$ of each other.
\begin{corollario}
Assume that the characteristic of $\K$ is prime to 6 and let $E: y^2 = x^3 + a_4x + a_6.$ The invariant $j_E$ depends only on the isomorphism class of $E$.	
\begin{itemize}
	\item $j_E=0$ if and only if $a_4=0$.
	\item $j_E=12^3$ if and only if $a_6=0$.
	\item If $j\in\K$ is neither $0$ nor $12^3$, then $E$ is a quadratic twist of the elliptic curve $$E_j:y^2=x^3-\dfrac{27j}{4(j-12^3)}x+\dfrac{27j}{4(j-12^3)}.$$
\end{itemize}
\end{corollario}
\begin{corollario}
	If $\K$ is as above, the isomorphism classes of elliptic curves $E$ over $\K$ are, up to twist, uniquely determined by the invariant $j_E$, and for every $j\in\K$ there exists an elliptic curve with invariant $j$. Moreover, if $\K$ is algebraically closed then the isomorphism classes of elliptic curves correspond one-to-one to element in $\K$ via the map $E\mapsto j_E$.
\end{corollario}

\section{The group law}\label{grplaw}
\begin{definizione}\label{Kpunti}
	Let $E$ be an elliptic curve over $\K$ given by a Weierstrass equation (\ref{ell}). We refer to points on the curve $E$ as points with coordinates in $\clK$ satisfying the equation, namely, $$E(\clK)=\left\{(x_1,y_1)\in\clK^2\ :\ y_1^2+a_1y_1+a_3y_1=x_1^3+a_2x_1^2+a_4x_1+a_6\right\}.$$
	Points on $E$ with coordinates in the base field $\K$ form the set of $\K$\emph{-rational points of E}; we denote this set by $$E(\K)=\left\{(x_1,y_1)\in\K^2\ :\ y_1^2+a_1y_1+a_3y_1=x_1^3+a_2x_1^2+a_4x_1+a_6\right\}.$$ In general, for any field extension $\K\subset\mathbb{L}\subset\clK$, we denote by $E(\mathbb{L})$ the set of $\mathbb{L}$\emph{-points of E}.
\end{definizione}
We now turn $E(\clK)$ into an abelian group, with operation denoted by $\oplus$. We define the point $\infp$ to be the identity element, it can be visualized as lying far out of the $y$-axis such that any line $x=c$, for some constant $c$, passes through it. If $P=(x_1,y_1)$ is any other point on the curve, then the equation 
$$y^2+(a_1x_1+a_3)y-x_1^3-a_2x_1^2-a_4x_1-a_6=0$$ has two solutions $y_1,\ y_2$. Since the sum of the roots of a monic polynomial is equal to minus the coefficient of the second-to-highest power of its indeterminate, we conclude that the other root is $$y_2=-y_1-a_1x_1-a_3.$$ Thus we define the opposite of $P=(x_1,y_1)$ to be the point $\ominus P=(x_1,-y_1-a_1x_1-a_3)$. Note that, in the case of a short Weierstrass equation, we have $\ominus P=(x_1,-y_1)$. 

The most natural way to describe the addition law on elliptic curves is to use geometry. To add two generic points $P=(x_1,y_1)$ and $Q=(x_2,y_2)$, we  draw a line connecting them. This line intercept the curve in tree points, namely, $P,Q$ and a third one $R$. We take the point $R$ and we reflect it across the $x$-axis to get a new point $R'$. We define $P\oplus Q=R'$. The same construction can be applied to double a point $P$ where the connecting line is replaced by the tangent at $P$. The above set of rules can be summarized in the following succinct manner:$$\emph{the sum of the three points where a line intersects the curve is zero}.$$
If the line passes through the point at infinity $\infp$, then this relation has the form $P\oplus(\ominus P)\oplus\infp=\infp$, otherwise it has the form $P\oplus Q\oplus R=\infp$.

We now show why there is exactly one more point where the line through $P$ and $Q$ intersects the curve; at the same time we will derive a formula for the coordinates of this third point, and hence the coordinates of $P\oplus Q$. Let $\K$ be a field and $E(\clK)$ the set of points of an elliptic curve of the form (\ref{ell}). Let $(x_1,y_1),\ (x_2,y_2)$ and $(x_3,y_3)$ denote the coordinates of $P,Q$ and $P\oplus Q$ respectively. We want to express $x_3$ and $y_3$ 	in terms of $x_1,\ x_2,\ y_1,\ y_2$. Suppose that $P\neq Q$ and $x_1\neq x_2$, then the line through them is not the vertical one, and has slope $$\lambda=\dfrac{y_1-y_2}{x_1-x_2}$$ and passes through $P$, thus its equation is $$y=\lambda x+\dfrac{x_1y_2-x_2y_1}{x_1-x_2}.$$ We denote the constant term by $\mu$ and remark $\mu=y_1-\lambda x_1$. The intersection points with the curve are the solutions of the following cubic equation $$(\lambda x+\mu)^2+(a_1x+a_3)(\lambda x+\mu)=x^3+a_2x^2+a_4x+a_6.$$
This leads to the equation $r(x)=0$ where $$r(x)=x^3+(a_2-\lambda^2-a_1\lambda)x^2+(a_4-2\lambda\mu-a_3\lambda-a_1\mu)x+a_6-\mu^2-a_3\mu.$$ We already know two roots of $r(x)$, namely the $x$-coordinates of the two points $P$ and $Q$, because they lying on the curve and on the line as well. As above, we know the sum of the tree roots is minus the coefficient of the second-to-highest power of $x$, thus the third root is $x_3 = \lambda^2+a_1\lambda -a_2-x_1-x_2$. As $x_1,\ x_2$ are defined over $\clK$, so are the values $x_3$ and $\overline{y}_3$, as $\overline{y_3}=\lambda x_3 + \mu$. Thus we found the point $R'=(x_3,\overline{y}_3)$. The inflection at the $x$-axis has to be translated to the condition that the second point has the same $x$-coordinate and also satisfies the curve equation. As we observe above, if $P=(x_1,y_1)$ is a point on the curve, then so is $(x_1,y_1-a_1x_1-a_3)$, which corresponds to $\ominus P$. Hence, we find $y_3=-\lambda x_3-\mu-a_1x_3-a_3$. \\
Doubling $P=(x_1,y_1)$ works in the same way with the slope obtained by implicit derivation. Thus we have $P\oplus Q=(x_3,y_3)$ and 
\begin{align*}
\ominus P &= (x_1,\ -y_1-a_1x_1-a_3) \\
P\oplus Q &= (\lambda^2+a_1\lambda -a_2-x_1-x_2,\ \lambda (x_1-x_3)-y_1-a_1x_3-a_3), \text{where}\\
\lambda &=
\begin{cases}
	\dfrac{y_1-y_2}{x_1-x_2} & \text{if } P\neq Q,\\
	\dfrac{3x_1^2+2a_2x_1+a_4-a_1x_1}{2y_1+a_1x_1+a_3} &\text{if } P=Q.
\end{cases}
\end{align*}
The associativity can be shown to hold by simply applying the group law and comparing elements. Moreover, it is clear from the geometric construction of the group law, that it is commutative. Thus we have the following.
\begin{proposizione}
	Let $E$ be an elliptic curve over a field $\K$. Then $(E(\clK),\oplus,\infp)$ is an abelian group. 
\end{proposizione}
\begin{osservazione}
	The set of $\K$-rational points of $E$ is a subgroup of $E(\clK)$ and if $\mathbb{L}\supset\K$ is an extension of $\K$, then the set of $\mathbb{L}$-points of $E$ is a subgroup as well.
\end{osservazione}
%\begin{esempio}
%In $\Fq$ with prime $p=2857$ the short weierstrass equation $$E:y^2=x^3+3x+7$$ is an elliptic curve, indeed $\Delta=2817\neq 0 \mod q$. The points $P(2760,720)$ and $Q=(688,1288)$ lie on the curve $E(\Fq)$. Then
%\begin{align*}
%\ominus P &= (2760,2137)\\
%P\oplus Q &=(324,1392)\\
%[2]P &= (339,494)
%\end{align*}
%are on $E(\Fq)$. The corresponding projective curve is $$E':ZY^2=x^3+3Z^2X+7Z^3$$. The point $P'=(596,1025,1172)$ lies on the projective curve, in fact it is in the same class as $(2760:720:1)$. 
%\end{esempio}
\subsection{Scalar multiplication}
Let $n\in\N\setminus\left\{0\right\}$. We denote the $scalar$ $multiplication$ $by$ $n$ $on$ $E$ by $\left[n\right]$; namely,
\begin{align*}
\left[n\right]:E(&\clK)\to E(\clK)\\
&P\mapsto \left[n\right]P=\underbrace{P\oplus P\oplus\dots\oplus P}_{n\ \text{times}}
\end{align*}
This definition extends trivially to $n\in\Z$, setting $\left[0\right]P=\infp$ and $\left[n\right]P=\left[-n\right]\ominus P$ for $n$ negative. The kernel of $\left[n\right]$ is $ker\left[n\right]=\left\{P\in E(\clK):\left[n\right]P=\infp\right\}$. It is denoted by $E\left[n\right]$ and is called \emph{n-torsion subgroup}; its elements are called \emph{n-torsion points}.
\begin{definizione}\label{supsingdef}
	Let $\K$ be a field of characteristic $p$ and let $E$ be an elliptic curve over $\K$. If $E[p^r]={\infp}$ for some (and in fact for all) positive integer $r$, then the curve is called \emph{super singular}. Otherwise the curve is called \emph{ordinary}.
\end{definizione}

We want to describe an algorithm to efficiently compute the scalar multiplication $\left[n\right]P$; this is a very important feature for cryptographic applications. The underlying idea is to write $n$ in binary expansion, namely, $n=\sum_{i=0}^{k}2^in_{i}$ with $n_{i}\in\left\{0,1\right\}$ and $k=\lceil\log_2n\rceil$. Next we compute the following quantity:
$$Q_0=P,\ Q_1=2Q_0,\ Q_2=2Q_1,\ldots,\ Q_k=2Q_{k-1}.$$ Notice that $Q_i$ is simply twice the previous $Q_{i-1}$, so $$Q_i=2^iP.$$
This point are referred to as 2-power multiples of $P$, and computing them requires $k$ doublings. Finally, we compute $\left[n\right]P$ using at most $k$ additions,
$$\left[n\right]P=\left[n_0\right]Q_0\oplus\left[n_1\right]Q_1\ldots\oplus\left[n_k\right]Q_k.$$
We'll refer to the addition of two points in $E(\clK)$ as $point$ $operation$.
Thus, the total time to compute $\left[n\right]P$ is at most $2k$ point operations in $E(\clK)$. Notice that $2^k\leq n$, and so $k\leq2\log_2n$ so it takes no more than $2\log_2n$ point operations to compute $\left[n\right]P$. This make it feasible to compute $\left[n\right]P$ even for very large values of $n$. We summarize in the following:
\begin{teorema}
Let $E$ be an elliptic curve over $\K$, let $P\in E(\clK)$ and let $n\geq 2$ be an integer. The algorithm described in \cref{doubadd} computes $\left[n\right]P$ using no more than $\log_2n$ point doublings and no more than $\log_2n$ point additions.
\end{teorema}
\begin{proof}
During the $i^{th}$ iteration of the loop, the value of $Q$ is $\left[2^i\right
]P$. Since $R$ is
incremented by $Q$ if and only if $n_i = 1$, the final value of $R$ is
$$\bigoplus_{i\text{ with }\atop n_i=1}\left[2^i\right]P=\bigoplus_{i=0}^{k}\left[n_i2^i\right]P=\left[\sum_{i=0}^{k}n_i2^i\right]P=\left[n\right]P.$$
Each iteration of the loop requires one point duplication and at most one point addition, and since $k\leq\log_2n$, the running time of the algorithm is as stated.
\end{proof}
\begin{table}
\caption {Double-and-add algorithm}\label{doubadd}
\begin{center}
\begin{tabular}{|ll|}
\hline
 & INPUT: Point $P\in E(\clK)$ and $n\in\Z$\\
 & OUTPUT: Point $R=[n]P$\\
\hline
1.& Set $Q=P$ and $R=\infp$.\\
2.&\textbf{if} $n=0$ \textbf{return} $\infp$ and terminate the algorithm. \\
3.& \textbf{loop while} $n>0$\\
4.& \textbf{if} $n\equiv 1\mod 2$ \textbf{then} $R=R\oplus Q$.\\
5.&Set $Q=\left[2Q\right]$ and $n=\lfloor n/2\rfloor$\\
6.&\textbf{if} $n>0$ go to step 2.\\
7.& \textbf{return} $R$.\\
\hline
\end{tabular}
\end{center}
\end{table}
The average running time of the double-and-add algorithm to compute $\left[n\right]P$ is $\log_2n$ doublings and $\frac{1}{2}\log_2n$ additions, since the binary expansion of a random integer $n$ has an equal number of 1's and 0's. However, we can reduce the average time by using the following expansion of $n$.
\begin{definizione}
A binary representation $(n_{k-1},\dots\,n_1,n_0)$ of an integer $n$ is said to be in \emph{non adjacent form} provided that no two consecutive $n_i$ are non-zero. Such a representation is denote \emph{NAF representation}.
\end{definizione} 
It is possible to compute the multiple $[n]P$ of the elliptic curve point $P$ by a series of doublings,
additions, and subtractions, using the algorithm in \cref{doubaddsub}.
\begin{table}
	\caption {Double-and-add-or-subtract algorithm}\label{doubaddsub}
	\begin{center}
		\begin{tabular}{|ll|}
			\hline
			& INPUT: Point $P\in E(\clK)$ and $(n_{l-1},\dots,n_1,n_0)$ NAF representation on the integer $n$\\
			&OUTPUT: The point $R=[n]P$.  \\
			\hline
			1.& Set $R=\infp$. \\
			2.& \textbf{if} $n=0$ \textbf{return} $Q$ and terminate the algorithm. \\
			3.& \textbf{for} $i=l-1$ \textbf{down to} $0$ \\
			4.& $R=[2]R.$\\
				5.& \textbf{if} $n_i=1$ \textbf{then} $R=R\oplus P$.\\
			6.& \textbf{else if} $n_i=-1$ \textbf{then} $R=R\ominus P.$\\
			7.& \textbf{return} $R$\\
			\hline
		\end{tabular}
	\end{center}
\end{table}
It is a simple matter to transform a binary representation of a positive integer $n$ into a NAF representation. The basis of this transformation is to replace sub-strings of the form $(0,1,\dots,1)$ in the binary representation, by sub-strings of the form $(1,0,\dots,0,-1)$. Such a substitutions do not change the value of $n$, due to the identity $$2^i+2^{i-1}+\dots+2^j=2^{i+1}-2^j$$ where $i>j$. This process is repeated as often as needed, starting with the rightmost (i.e., low-order) bits and proceeding to the left.
\begin{esempio}
The binary expansion of $n=3895$ is $[1, 1, 1,1, 0,0, 1, 1,\underline{0, 1, 1, 1}]$. Starting from the right we substitute the underlined sub-string $[0,1\dots,1]$ with $[1,0,\dots,0,-1]$ and we obtain:
$$[1, 1, 1,1,0,\underline{0, 1, 1, 1}, 0, 0, -1]$$
$$[\underline{1,1,1,1},0, 1,0,0,-1,0,0,- 1,]$$ 
$$[1,0,0,0,-1,0, 1,0,0,-1,0,0,- 1,].$$ This corresponds to $2^{12}-2^8+2^6-2^3-1=3895$.
\end{esempio}
In a NAF representation, there do not exist two consecutive non-zero coefficients. We might expect that, on average, a NAF representation contains more zeroes than the traditional binary representation of a positive integer. This is indeed
the case: it can be shown \cite{CiJo} that, on average, an $k$-bit integer contains $\frac{k}{2}$ zeroes in
its binary representation and $\frac{2k}{3}$ zeroes in its NAF representation.
These results make it easy to compare the average efficiency of the double-and-add using a binary representation, to the double-and-add-or-subtract using the NAF representation. Each algorithm requires $k$ doublings, but the number of additions (or subtractions) is $\frac{k}{2}$ in the first case, and $\frac{2k}{3}$ in the second case. If we assume that a doubling takes roughly the same amount of time as an addition (or subtraction), then the ratio of the average times required by the two algorithms is approximately $$\dfrac{k+\frac{k}{2}}{k+\frac{2k}{3}}=\dfrac{9}{8}.$$ We have therefore obtained a (roughly) $11\%$ speedup, on average, by this simple technique. 
\subsection{Montgomery ladder}
We have already described algorithms that efficiently compute the scalar multiplication $Q=[k]P$ in an elliptic curve group. It is a well known fact that, since now, there is no efficient algorithm to compute the inverse operation, i.e., to find the integer $k$ given the generator $P$ and the point $Q$. This turns the scalar multiplication into a \emph{one way function} and thus we can build the \emph{public-key elliptic curve cryptosystem}, which include well known protocols such as \emph{Diffie Hellman key exchange}, \emph{ElGamal encryption}, \emph{Elliptic Curves Signature Algorithm} \cite{ElGam},\cite{Diff}. In public-key cryptography, each participant possesses two keys: a \emph{public key} and a \emph{private key}. These are linked in a unique manner by a one-way function. In an elliptic curve cryptoysyem, the private key is the integer $k\mod p$, where $p$ is the order of $P$, while the relative public key is the point $Q=[k]P$ in the cyclic group generated by $P$. The important feature of the private key $k$ is that it has to be computationally infeasible to detect it given the public key $Q$. 
Kocher, Jaffe, and Jun first presented the idea of using the measure of power consumption of an electronic device to retrieve information about the private keys. In \cite{Komm}, authors described two methods for extracting the keys, which they named \emph{simple power analysis} (SPA) and \emph{differential power analysis} (DPA). 

Although efficient (in both memory and computation), the \emph{double and add} method described above may be subject to SPA-type attacks. From a power trace, an adversary able to distinguish between point doublings and point additions can recover the value of scalar $k$. A generic countermeasure to these attacks is the use of the Montgomery ladder Algorithm presented in \cref{montladd}. 
\begin{table}
	\caption {Montgomery ladder Algorithm}\label{montladd}
	\begin{center}
		\begin{tabular}{|ll|}
			\hline
			&INPUT: A point $P$ on $E(\Fq)$ and a positive integer $n = (n_{l-1}\ldots n_0)_2$. \\
			&OUTPUT: The point $[n]P$.  \\
			\hline
			1.& Set $P_0=\infp$, $P_1=P.$ \\
			2.& \textbf{for} $i=l-1$ \textbf{down to} $0$ \textbf{do} \\
			3.& \textbf{if} $n_i=1$ \textbf{then} $P_1=P_0\oplus P_1$ and $P_0=[2]P_0$ \\
			4.& \textbf{else} $P_0=P0\oplus P_1$ and $P_1=[2]P_1.$\\
			5.&\textbf{return} $P_0.$\\
			\hline
		\end{tabular}
	\end{center}
\end{table}
In Montgomery ladder Algorithm, each iteration is comprised of a point addition followed by a point doubling. This makes scalar multiplication secure against side channel attacks. 
\chapter{Arithmetic of Elliptic Curves over Finite Fields}\label{ellfinfilar}
For cryptographic applications we are mostly interested in elliptic curves over finite fields. First we consider elliptic curves defined over a prime field $\Fq$ where $q > 3$ is a prime; in this case we can always assume that $E/\Fq$ is given by a short Weierstrass equation. Than we consider elliptic curves define over binary fields $\F_{2^d}$.
\section{Arithmetic of Elliptic Curves over Prime Fields}
\begin{definizione}
	Let $q > 3$ be a prime. An elliptic curve $E$ over $\Fq$ is given by the short Weierstrass equation
\begin{equation}\label{ellff}
y^2 = x^3 + a_4x + a_6,\ \text{where}\ a_4,a_6\in\Fq 
\end{equation}
satisfy $4a_4^3+27a_6^2\neq 0 \mod q.$ 
\end{definizione}
Points on the curve are solutions $(x,y)$ of \cref{ellff}, lying on $\clF_q^2$. If $e\geq 1$ is an integer we can consider the field extension $\Fqe$ of $\Fq$. Thus $\Fqe$\emph{-points} are the solutions $(x,y)$ of \cref{ellff}, lying on $\Fqe^2$.  It is clear that an elliptic curve over a finite field has only finitely many points with
coordinates in that finite field. Therefore, we obtain a finite abelian group in this case. A classic result of Hasse, \cite{Wash},\cite{Sil2}, shows that  $|E(\Fqe)|=q^e+1-t$, for some integer $t$ such that $|t|\leq 2\sqrt{q^e}$.  This shows that the number of points on $E(\Fqe)$ is close to $q^e + 1.$ An algorithm due to Schoof \cite{Sch} can be used to compute the number of points in $E(\Fqe)$ in time polynomial in $\log(q^e)$. Hence, $|E(\Fqe)|$ can be computed efficiently even for a large prime $q$. Elkies and Atkin showed how to reduce the running time, and the resulting point counting method is called the Schoof-Elkies-Atkin algorithm, or
simply, the $SEA$ $algorithm$.

In the previous section we explained the group law in general, with emphasis on algorithms in \cref{doubadd} and \cref{doubaddsub}, which state that the multiplication by an integer can be computed very efficiently by adding and doubling points . For cryptographic purposes is very important for this operation to be as fast as possible. Here we present some technique to achieve the goal. We summarize the formulas for addition and doubling; now the operations are performed in $\Fqe$ and because of the short Weierstrass form, if $P = (x,y)$ is a point of the curve different from $\infp$, then we have $\ominus P = (x,-y)$.
\subsection{Group law formulas in affine coordinates}
Let $P = (x_1, y_1)$ and $Q = (x_2, y_2)$ be two points in $E(\Fqe)$. The sum $P\oplus Q= (x_3, y_3)$ is defined using one of the following three rules:
\begin{itemize}
	\item if $x_1\neq x_2$, we use the chord method. Let $\lambda=\dfrac{y_1-y_2}{x_1-x_2}$, then we have 
	$$x_3 = \lambda^2-x_1-x_2,\quad y_3 = \lambda(x_1-x_3)-y_1;$$
	\item if $x_1 = x_2$ and  $y_1 = y_2$ (i.e., $P = Q$), we use the tangent method. Let $\lambda=\dfrac{3x_1^2+a_4}{2y_1}$, then we have
	$$x_3=\lambda^2-2x_1,\quad y_3=\lambda(x_1-x_3)-y_1;$$
	\item if $x_1 = x_2$ and $y_1 = -y_2$ then we have $P\oplus Q=\infp.$
\end{itemize}
We denote an elementary multiplication in $\Fqe$ (resp. a squaring and an inversion) by $\mathcal{M}$ (resp. $\mathcal{S},\mathcal{I})$. In the following analysis we neglect addition, subtraction and scalar multiplication because they are must faster. From the formulas above one can easily read off that an addition and a doubling require $\mathcal{I}+2\mathcal{M}+\mathcal{S}$ and $\mathcal{I}+2\mathcal{M}+2\mathcal{S}$ respectively. Although
finding inverses in finite field is fast, it is much slower than multiplication. In \cite{Coh1} the authors estimated that inversion takes between 9 and 40 times as long as multiplication, while, squaring takes about 0.8 the time of multiplication. Therefore, it is sometimes advantageous to prefer squaring rather than inversion
in the formulas for point addition and doubling.
\subsection{Group law formulas in projective coordinates}
Let's consider the projective curve corresponding to $E$. As we saw in \cref{projective}, it has equation of form $$E_{hom}:Y^2Z=X^3+a_4XZ^2+a_6Z^3.$$
The point $(X_1:Y_1:Z_1)$ on $E_{hom}$ corresponds to the affine point $(X_1/Z_1,Y_1/Z_1)$ when $Z_1\neq=0$ and to the point at infinity $\infp$ otherwise. The opposite of $(X_1:Y_1:Z$\frac{+2}{+3}$,Q=(X_2:Y_2:Z_2)$ such that $P\neq Q$, $P\neq\ominus Q$ and let $P\oplus Q=(X_3:Y_3:Z_3)$. Then set 
$$A=Y_2Z_1-Y_1Z_2,\qquad B=X_2Z_1-X_1Z2,\qquad C=A^2Z_1Z_2-B^3-2B^2X_1Z_2.$$ So we have
$$X_3=BC,\qquad Y_3=A(B^2X_1Z_2-C)-B^3Y_1Z_2,\qquad Z_3=B^3Z_1Z_2.$$
\subsection*{Doubling}
Let $[2]P=(X_3:Y_3:Z_3)$. Then set 
$$A=a_4Z_1^2+3X_1^2,\qquad B=Y_1Z_1,\qquad C=X_1Y_1B,\qquad D=A^2-8C.$$ So we have
$$X_3=2BD,\qquad Y_3=A(4C-D)-8Y_1^2B^2,\qquad Z_3=8B^3.$$
We note that no inversion is needed and the computations times are $12\mathcal{M}+2\mathcal{S}$ and $7\mathcal{M}+5\mathcal{S}$. Moreover, if one of the input points is given by $(X_1:Y_1:1)$, i.e., directly transformed from affine coordinates), then the operation for the addition decrease to $9\mathcal{M}+2\mathcal{S}$. 
\subsection{Group law formulas in Jacobian Chudnovsky coordinates}
Things even goes better if one use the Jacobian and Chudnovsky coordinates or their modification proposed by Henri Cohen et al. in \cite{Coh3}. With \emph{Jacobian coordinates} the curve $E$ is given by $$Y^2 = X^3 + a_4XZ^4 + a_6Z^6.$$
The point $(X_1 : Y_1 : Z_1 )$ on $E$ corresponds to the affine point $(X_1/Z_1^2, Y_1/Z_1^3 )$ when $Z_1\neq 0$ and to
the point at infinity $\inf = (1 : 1 : 0)$ otherwise. The opposite of $(X_1 : Y_1 : Z_1 )$ is $(X_1 : -Y_1 : Z_1 )$.
\subsection*{Addition}
Let $P(X_1:Y_1:Z_1),Q=(X_2:Y_2:Z_2)$ such that $P\neq Q$, $P\neq\ominus Q$ and let $P\oplus Q=(X_3:Y_3:Z_3)$. Then set
$$A=X_1Z_2^2,\qquad B=X_2Z_1^2,\qquad C=Y_1Z_2^3,\qquad D=Y_2Z_1^3\qquad E=B-A,\qquad F=D-C.$$ So we have
$$X_3=-E^3-2AE^2+F^2,\qquad Y_3=-CE^3+F(AE^2-X_3),\qquad Z_3=Z_1Z_2E.$$
\subsection*{Doubling}
Let $[2]P=(X_3:Y_3:Z_3)$. Then set 
$$A=4X_1Y_1^2,\qquad B = 3X_1^2 + a_4Z_1^4.$$ So we have
$$X_3=-2A + B^2,\qquad Y_3=-8Y_1^4 + B(A-X_3 ),\qquad Z_3 = 2Y_1Z_1.$$
The complexities are 12$\mathcal{M}$ + 4$\mathcal{S}$ for an addition and 4M + 6S for a doubling. If one of the points is
given in the form $(X_1 : Y_1 : 1)$ the costs for addition reduce to 8$\mathcal{M}$ + 3$\mathcal{S}$. Note that doubling involves one multiplication by the parameter $a_4$. If it is small this multiplication can be performed by some additions and hence be neglected in the operation count. Especially if
$a_4 = ?3$ one can compute $T = 3X_1^2-3Z_1^4 = 3(X_1-Z_1^2)(X_1+Z_1^2)$ leading to only 4$\mathcal{M}$ + 4$\mathcal{S}$
for a doubling. The parameter $a_4 = 0$ is even more advantageous as the costs drop down to 3$\mathcal{M}$ + 4$\mathcal{S}$. This justifies
 the curve's parameter for $a_4$ used in standardized curves presented in \cref{NISTcurves}. On my repository \cite{repo} you can find and implementation  written in Rust of these formulas and the Montgomery ladder algorithm for scalar multiplication.
%\footnote{You can find an implementation of the above formulas written in Rust on my repository \cite{repo}. I really appreciated the efficiency of the projective coordinates formulas when running the implicit baby-step-giant-step which we describe in the next chapter.}
\section{Arithmetic of elliptic curves defined over $\mathbb{F}_{2^d}$}
Here we consider elliptic curves over $\F_{2^d}$. We discuss the transfer to short Weierstrass equations and state formulas for the arithmetic on super-singular and ordinary elliptic curves. The curves given in Weierstrass form $$y^2+a_1xy+a_3y=x^3+a_2x^2+a_4x+a_6$$ can be transformed depending on the value of $a_1$.
\subsection{Super-singular curves}
Assume $a_1=0$. As stated in \cref{ell}, an elliptic curve has to be smooth, thus we need to have $a_3\neq 0$. The transformation $x\mapsto x'=x+a_2,$ leads to the equations $$E:y^2+a_3y=x^3+a_4'x+a_6',$$ which is non singular since $a_3\neq 0$. By the general group law formulas described in \cref{grplaw}, we know that if $P=(x_1,y_1)$ is a point on the curve $E$, then its opposite is $-P=(x_1,y_1+a_3)$ (remember we are in characteristic 2). Thus, such a curve $E$ has no point $P$ of order two, otherwise we must have $y_1=y_1+a_3$, which leads to $a_3=0$. Therefore, $E[2]=\left\{\infp\right\}$ and $E$ is super-singular by \cref{supsingdef}. The arithmetic on the super-singular curve $E:y^2+a_3y=x^3+a_4x+a_6$ is given by the following formulas where $P=(x_1,y_1)$ and $Q=(x_2,y_2)$ are two points in $E(\F_{2^d})$:
\begin{itemize}
	\item $\ominus P=(x_1,y_1+a_3)$.
	\item If $P\ne Q$ and $P\neq\ominus Q$, we have $P\oplus Q=(x_3,y_3)$ where
	$$x_3=\lambda^2+x_1+x_2,\qquad y_3=\lambda(x_1+x_3)+y_1+a_3,\qquad\lambda=\dfrac{y_1+y_2}{x_1+x_2}.$$
	\item If $P\neq\ominus P$, we have $[2]P=(x_3,y_3)$, where 
	$$x_3=\lambda^2,\qquad y_3=\lambda(x_1+x_3)+z_1+a_3,\qquad\lambda=\dfrac{x_1^2+a_4}{a_3}.$$
\end{itemize}
%\begin{esempio}
%mettere esempio ????
%\end{esempio}
\subsection{Ordinary curves}
If $a_1\neq 0$, the transformations $$y\mapsto a_1^3y+\dfrac{a_3^2+a_1^2a_4}{a_1^3},\ x\mapsto a_1^2x+\dfrac{a_3}{a_1},$$ followed by a division by $a_1^6$ leads to an isomorphic curve give by $$y^2+xy=x^3+a_2'x^2+a_6',$$
which is non singular whenever $a_6'\neq 0$. In this case the curve is ordinary. As for curves over prime fields, we give formulas for arithmetic in both affine and projective coordinates. 
As in \cref{ellfinfilar}, an elementary multiplication in $\F_{2^d}$  (respectively a squaring and an inversion) will be denoted by $\mathcal{M}$ (respectively $\mathcal{S}$ and $\mathcal{I}$).
\subsection{Group law formulas in affine coordinates}
As discussed above, we can choose an elliptic curve of the form $$E:y^2+xy=x^3+a_2x^2+a_6.$$ Let $P=(x_1,y_1)$ be a point of $E(\F_{2^d})$, then the opposite of $P$ is $\ominus P = (x_1,y_1+x_1)$.
\subsection*{Addition}
Let $P=(x_1,y_1)$ and $Q=(x_2,y_2)$ be points of $E(\F_{2^d})$ with $P\neq \ominus Q$, then $P\oplus Q=(x_3,y_3)$ is given by
$$x_3=\lambda^2+\lambda+x_1+x_2+a_1,\qquad y_3=\lambda(x_1+x_3)+x_3+y_1,\qquad\lambda=\dfrac{y_1+y_2}{x_1+x_2}.$$
\subsection*{Doubling}
Let $P=(x_1,y_1)$ be a point of $E(\F_{2^d})$, then $[2]P=(x_3,y_3)$ is given by
$$x_3=\lambda^2+\lambda+a_2,\qquad y_3=\lambda(x_1+x_3)+x_3+y_1,\qquad \lambda=x_1+\dfrac{y_1}{x_1}.$$
Thus, an addition and a doubling require exactly the same number of operation. that is $\mathcal{I}+2\mathcal{M}+\mathcal{S}$.
\subsection*{Projective Coordinates}
The corresponding projective equation is the curve given by $$E_{hom}: Y^2Z+XYZ=X^3+a_2X^2Z+a_6Z^3.$$
As discussed previously, we let $(X_1:Y_1:Z_1)$ represent the affine point $(X_1/Z_1,Y_1/Z_1)$ provided that $Z_1\neq 0$ and $(0:1:0)$ otherwise. The opposite of $P$ is $\ominus P =(X_1:X_1+Y_1:Z_1)$. 
\subsection*{Addition}
Let $P=(X_1:Y_1:Z_1)$ and $Q=X_2:Y_2:Z_2)$ be points of $E_{hom}(\F_{2^d})$,with $P\neq \ominus Q$, then $P\oplus Q=(X_3:Y_3:Z_3)$ is given by
\begin{center}
\begin{tabular}{lll}

	$A=Y_1Z_2+Y_2Z_1,$ & $B=Z_1Z_2+X_2Z_1,$ & $C=B^2,$\\
	$D=Z_1Z_2,$ & $E=(A^2+AB+a_2C)D+BC,$ & \\
	$X_3=CE,$ & $Y_3=C(AX_1+Y_1B)Z_2+(A+B)E,$ &$Z_3=B^3D.$	
\end{tabular}
\end{center}
\subsection*{Doubling}
Let $P=(X_1:Y_1:Z_1)$  be a point of $E_{hom}(\F_{2^d})$, then $[2]P=(X_3:Y_3:Z_3)$ is given by
\begin{center}
	\begin{tabular}{lll}
		
		$A=X_1^2,$ & $B=A+Y_1Z_1,$ & $C=X_1Z_1,$\\
		$D=C^2,$ & $E=(B^2+BC+a_2D),$ & \\
		$X_3=CE,$ & $Y_3=(B+C)E+A^2C,$ &$Z_3=CD.$	
	\end{tabular}
\end{center}
We note that in projective coordinates no inversion is needed. An addition required $6\mathcal{M}+2\mathcal{S}$ and a doubling $8\mathcal{M}+4\mathcal{S}$. If the addition receives one input point in affine coordinates, i.e., as $(X_2:Y_2:1)$, the costs reduce to $12\mathcal{M}+2\mathcal{S}$.
\section{Montgomery and Edward's curves}
In this section we give a brief description of \emph{Montgomery curves} and \emph{Edwards curves}, which are better suited for computation than the Weierstrass form; for more details we refer to \cite{Wash},\cite{Coh1},\cite{mong}.
\subsection{Montgomery curves}
A Montgomery curve $E$ over $\Fq$ is define by the equation 
\begin{equation}
	E_M:\ By^2=x^3+Ax^2+x,
\end{equation}
for some $A,B\in\Fq$ and $B(A^2-4)\neq 0$. If $q>3$ it is always possible to converted a curve in Montgomery form into short Weierstrass equation by the transformation $$x\mapsto x'=Bx-A/3,\quad y\mapsto y'=By.$$ The order of the elliptic curve group of $E_M$ is divisible by 4 \cite{mong}, therefore not all Weierstrass form can be converted into a Montgomery form. The arithmetic on $E_M$ relies on an efficient $x$-coordinate only computation and can be easily implemented to resist side-channel attacks; \cite{mong}, \cite{Coh1} for the formul\ae.
\subsection{Edwards curves}
An Edwards curve $E$ over $\Fq$ is define by the equation
\begin{equation}
	x^2+y^2=1+dx^2z^2,
\end{equation}
where $d\in\Fq$ and $d\neq0,1$ is not a square in $\Fq$. Again, this curve can be put into Weierstrass form via a simple rational change of variable. The chord and tangent addition
law is extremely easy to describe for an Edwards curve. For points $P=(x_1,y_1)$ and $Q=(x_2,y_2)$ in $E(\Fqe)$, we have 
$$P\oplus Q= \left(\dfrac{x_1y_1+x_2y_1}{1+dx_1x_2y_1y_2},\dfrac{y_1y_2-x_1x_2}{1-dx_1x_2y_1y_2}\right).
$$
An interesting feature is that there's no need for three separate rules for $[2]P$ and
$P\oplus Q$ when $P\neq Q$. The formula for adding points can be written in projective coordinates. The
resulting computation takes $10\mathcal{M}$ and $1\mathcal{S}$ for both point addition and point doubling \cite{Wash}.
\section{Some example of NIST recommended curves}\label{NISTcurves}
In 1994,  NIST has standardized elliptic curve cryptography for digital signature algorithms FIPS 186 and for key establishment schemes in SP 800-56A. However, more than fifteen years have passed since these curves were first developed, and the community now knows more about the security of elliptic curve cryptography and practical implementation issues. Advances within the cryptographic community have led to the development of new elliptic curves and algorithms whose designers claim to offer better performance and are easier to implement in a secure manner. In 2023 NIST published Federal Information Processing Standard (FIPS) 186-5\cite{fips}, \emph{Digital Signature Standard }(DSS), along with NIST Special Publication (SP) 800-186 \cite{nist}, \emph{Recommendations for Discrete Logarithm-based Cryptography: Elliptic Curve Domain Parameters}. The former specifies a suite of algorithms that can be used to generate a digital signature, the latter specifies the set of elliptic curves recommended for U.S. Government use. In addition to the previously recommended Weierstrass curves defined over prime fields and binary fields, this Recommendation includes two newly specified Edwards curves, which provide increased performance, side-channel resistance, and simpler implementation when compared to traditional curves.

Here we describe some of the standardized curves and in next chapter we discuss some weakness they have. Two widely used elliptic curves, called $\mathbf{secp256r1}$ and $\mathbf{secp256k1}$ \cite{nist}. They both are
defined over a 256-bit prime field. The curve secp256r1
is widely used in Internet protocols, while secp256k1 is widely used in blockchain systems.
\subsection{Curves Over Prime Fields}
\subsection*{The curve secp256r1}
This curve was approved by the U.S. National Institute of Standards
(NIST) for federal government use in a standard published in 1999. The NIST standard refers to this curve as $\mathbf{Curve\ P256}$. The curve secp256r1 is defined as follows.
\begin{itemize}
	\item The base field is $\F_q$ where $q=2^{256}-2^{224}+2^{192} +2^{96}-1.$
	\item The curve has the Weierstrass form $y^2 = x^3-3x+b,$ where $b\in\Fq$ is generated by a public deterministic algorithm.
	\item The group $E(\F_q)$ is cyclic of prime order $$p=115792089210356248762697446949407573529996955224135760342422259061068512044369.$$ 
	\item The standard also specifies the generator $G$:
	\begin{align*}
		x_G=&48439561293906451759052585252797914202\\
		&762949526041747995844080717082404635286\mod q,\\ y_G=&36134250956749795798585127919587881956\\
		&611106672985015071877198253568414405109\mod q.
	\end{align*}
\end{itemize}
\subsection*{The curve secp256k1}
 This curve was selected for the digital signature scheme in the Bitcoin blockchain. Subsequent blockchains
inherited the same curve. It is the one used to map users' private keys to Ethereum and Bitcoin public addresses. The curve secp256k1 is defined as follows.
\begin{itemize}
	\item The base field is $\F_q$ where $q=2^{256}-2^{32}-2^9-2^8-2^7-2^6-2^4-1.$
	\item The curve has the Weierstrass form $y^2 = x^3+7.$
	\item The group $E(\F_q)$ is cyclic of prime order $$p=115792089237316195423570985008687907852837564279074904382605163141518161494337.$$ 
	\item The standard also specifies a generator $G$:
	\begin{align*}
		x_G=&55066263022277343669578718895168534326250603453\\
		&77594175500187360389116729240\mod q,\\ y_G=&32670510020758816978083085130507043184471273380\\
		&659243275938904335757337482424\mod q.
	\end{align*}
\end{itemize}
This curve has a useful map define on it. We have that $q\equiv 1\mod 3$, therefore there exists $1\neq\omega\in\mathbb{F}_q$ such that $w^3=1$. Now, consider the map $\phi:\mathbb{F}_q^2\to\mathbb{F}_q^2$ define by $\phi(x,y):=(\omega x,y)$. We note that if $(x,y)\in E(\mathbb{F}_q)$, then so does $\phi(x,y)\in E(\mathbb{F}_q)$; this is obvious since $\omega^3=1$. We define $\phi(\infp)=\infp$ and we note that if $P=(x_1,y_1)$ and $Q=(x_2,y_2)$ are points in $E(\mathbb{F}_q)$, then we have $$\phi(P)\oplus\phi(Q)=(\omega x_1,y_1)\oplus(\omega x_2,y_2)=(\omega(\lambda^2- x_1-x_2), \lambda(x_1-x_3)-y_1)=\phi(P\oplus Q),$$ where we used the formula from \cref{grplaw} together with the identity $\omega^{-2}=\omega$. Thus $\phi$ is a group homomorphism, and since $E(\mathbb{F}_q)$ is cyclic of prime order $p$, there must be a constant $\lambda\in\Z_p$ such that for all $P\in E(\mathbb{F}_q)$, we have $\phi(P)=[\lambda]P$.  We want to find such a $\lambda$. We note that the tree points $P$, $\phi(P)$ and $\phi^2(P)$ all have the same $y$-coordinate and as stated in \cref{grplaw}, this means that for all $P\in E(\mathbb{F}_q)$, we must have $$\infp=P+\phi(P)+\phi^2(P)=\infp=[1+\lambda+\lambda^2]P.$$ Therefore we can conclude that $1 + \lambda+\lambda^2 = 0$ in $\Z_p$. Hence, $\lambda$ must be one of the two non-trivial cube roots of unity in $\Z_q$. Indeed, $p\equiv 1\mod 3$, such a non-trivial root exists in $\Z_p$. This could be useful to speed up scalar multiplication. Suppose we want to calculate $[\alpha]P$ for some $\alpha\in\Z_p$. For most $\alpha$ in $\Z_p$ one can find $\tau_0,\tau_1,\tau_2$, such that $$\alpha=\tau_0+\tau_1\lambda+\tau_2\lambda^2,\ \text{with}\ \tau_i\leq2p^{1/3}\ \text{for}\ i=0,1,2.$$ Thus, we have $[\alpha] P = [\tau_0] P+[\tau_1]\phi(P)+[\tau_2]\phi^2(P).$ This equality converts a multiplication by $\alpha$ into three multiplications where the multipliers $\tau_0,\tau_1,\tau_2$ are much smaller than $\alpha$.
\subsection*{The curve P-224}
The curve P-224 is defined as follows.
\begin{itemize}
	\item The base field is $\F_q$ where $q=2^{224}-2^{96}+1.$
	\item The curve has the Weierstrass form $y^2 = x^3-3x+b,$ where $b\in\Fq$ is generated by a public deterministic algorithm.
	\item The group $E(\F_q)$ is cyclic of prime order $$p=26959946667150639794667015087019625940457807714424391721682722368061.$$ 
	\item The standard also specifies the generator $G$:
	\begin{align*}
		x_G=&19277929113566293071110308034699488026831934219452440156649784352033\mod q,\\
		y_G=&19926808758034470970197974370888749184205991990603949537637343198772\mod q.
	\end{align*}
\end{itemize}
The quadratic twist of this curve has order $h\cdot r$,
where $h=3^2\cdot11\cdot47\cdot3015283\cdot40375823\cdot267983539294927$, and $r$ is a $117$-bit prime number. This value
is significantly smaller than the order $p$ of the base-point $G$ of P-224. As a result, it is essential to verify domain parameter validity
to ensure that users are performing operations on P-224 and not on its quadratic twist. See next chapter for details.
\subsection*{The curve P-384}
The curve P-384 is defined as follows.
\begin{itemize}
	\item The base field is $\F_q$ where $q=2^{384}-2^{128}-2^{96}+2^{32}-1.$
	\item The curve has the Weierstrass form $y^2 = x^3-3x+b,$ where $b\in\Fq$ is generated by a public deterministic algorithm.
	\item The group $E(\F_q)$ is cyclic of prime order 
	\begin{align*}
		p=&3940200619639447921227904010014361380507973927046544666794\\
		&6905279627659399113263569398956308152294913554433653942643
	\end{align*}
	\item The standard also specifies the generator $G$:
	\begin{align*}
		x_G=&2624703509579968926862315674456698189185292349110921338781\\
		&5615900925518854738050089022388053975719786650872476732087\mod q,\\
		y_G=&832571096148902998554675128952010817928785304886131559470\\
		&9205902480503199884419224438643760392947333078086511627871\mod q.
	\end{align*}
\end{itemize}
\subsection*{P-521}
The curve P-521 is defined as follows.
\begin{itemize}
	\item The base field is $\F_q$ where $q=2^{521}-1.$
	\item The curve has the Weierstrass form $y^2 = x^3-3x+b,$ where $b\in\Fq$ is generated by a public deterministic algorithm.
	\item The group $E(\F_q)$ is cyclic of prime order 
	\begin{align*}
		p=&686479766013060971498190079908139321726943530014330540939446\\
		  &345918554318339765539424505774633321719753296399637136332111\\
		  &3864768612440380340372808892707005449
	\end{align*}
		\item The standard also specifies the generator $G$:
	\begin{align*}
		x_G=&2661740802050217063228768716723360960729859168756973147706\\
		&6713684188029449964278084915450806277719023520942412250655\\
		&58662157113545570916814161637315895999846\mod q\\
		y_G=&37571800257700204635455072244911836035944551347697624866945\\
		&67779615544477440556316691234405012945539562144444537289428\\
		&522585666729196580810124344277578376784\mod q.
	\end{align*}
\end{itemize}
\subsection{Montgomery Curves}
\subsection*{Curve25519}
The curve W-25519 is defined as follows.
\begin{itemize}
	\item The base field is $\F_q$ where $q=2^{255}-19.$
	\item The curve has the Weierstrass form $By^2 = x^3+Ax^2+x,$ where
	$A= 486662$ and $B = 1$.
	\item The group $E(\F_q)$ has order $hp$, where $h = 8$, and  
	\begin{align*}
		p=&7237005577332262213973186563042994240857116359379907606001950938285454250989.
	\end{align*}
	\item The standard also specifies the generator $G$ for the cyclic subgroup of order $p$:
		\begin{align*}
		x_G=&9\mod q\\
		y_G=&343114425171068552920764898935933967039\\
		&370386198203806730763910166200978582548\mod q.
	\end{align*}
\end{itemize}
\subsection{Twisted Edwards Curves}
\subsection*{E448}
The curve E488 is defined as follows.
\begin{itemize}
	\item The base field is $\F_q$ where $q=2^{448}-2^{224}-1.$
	\item The curve has the form $ax^2+y^2 = 1+ dx^2y^2,$ where
	$a= 1$ and $d= ?39081\mod q$.
	\item The group $E(\F_q)$ has order $hp$, where $h = 4$, and  
	\begin{align*}
		p=&1817096810739017226373309519720011335884103401718295150703725497951\\
		&46003961539585716195755291692375963310293709091662304773755859649779.
	\end{align*}
	\item The standard also specifies the generator $G$ for the cyclic subgroup of order $p$:
	\begin{align*}
		x_G=&22458004029592430018760433409989603624678964163256413424\\
		    &61254616869504154674060329090291928693579532825780320751\\
		    &46446173674602635247710\mod q\\
		y_G=&29881921007848149267601793044393067343754404015408024209\\
		    &59282413723315061898358760035368786554187847339823032335\\
		    &03462500531545062832660 \mod q.
	\end{align*}
\end{itemize}

\chapter{Implicit baby step giant step algorithm}\label{chapimplicit}
Public-key cryptography is based on the idea of one-way functions: in rough terms these are functions, whose inverse cannot be computed in any reasonable amount of time. If we use such a function for encryption, an adversary will in principle not be able to decrypt the encrypted messages. Once we establish a one way function, we can instantiate protocols for authentication, signature, etc. The resulting systems are called \emph{public key cryptosystems}. 

In \cref{ellgeneric} we saw that the set of points of an elliptic curve is a finite abelian group. We also described algorithms for scalar multiplication as well as some technique to speed up the computation. In a general setting, however, the inverse operation, called \emph{discrete logarithm}, is not as fast; there is no known algorithm that can compute discrete logarithm in $E(\Fq)$ much faster than $O(\sqrt{p})$  where $p$ is the order of $P$ in $E(\Fq)$. This makes the scalar multiplication a one way function from the group $E(\Fq)$ to itself and we can build the \emph{public key elliptic curve cryptosystem}. 

In this chapter we present an algorithm to solve the discrete logarithm problem. One can be used to determine wether a public key comes from a weak private key subject to a given computational bound, and if so, recover the private key from the corresponding public key. We follow the work of M. J. Jacobson and P. Kushwaha, \cite{Pra1},\cite{Pra2} whose results are inspired by the work of Maurer and Wolf \cite{Mau}.

\section{Discrete logarithm problem}
Since our main focus are elliptic curves, we write our group $(G,\oplus)$ additively. Results applies to multiplicative groups $mutatis$ $mutandis$.
\begin{definizione}
Let $(G,\oplus)$ be an additive cyclic group of prime order $p$ and let $P$ be a generator for $G$. The map
\begin{align*}
	\varphi:\ &\Z\ \to\ G\\
	&n\ \mapsto\ [n]P=\underbrace{P\oplus P\oplus\dots\oplus P}_{n\ \text{times}}
\end{align*}
has kernel $p\Z$, thus $\varphi$ leads to an isomorphism between $(G,\oplus)$ and $(\Z/p\Z,+):=\Z_p.$ The problem of computing the inverse map is called the $discrete$ $logarithm$ $problem$ ($DLP$) to the base of $P$. It is the problem, given $P$ and $Q$, to determine $\alpha\in\Z$ such that $Q = [\alpha]P$. Note that $\alpha$ is
unique only modulo the group order.
\end{definizione}
The complexity of this problem depends on the choice of $G$ and its operation. If $G=\Z_p$ with generator $1$, the discrete logarithm of $n\in\Z_p$
is $n$ it self. Also, if the generator is chosen to be $a\in\Z_p$, this problem is easy to solve as it is nothing but computing the inverse modulo $p$. In the following section we present a deterministic algorithm that solves the $DLP$.
\section{Baby step, giant step algorithm}
The baby-step giant-step algorithm was first published by Shanks \cite{Sha}, the first application of this method was to compute ideal class numbers of quadratic number fields \cite{Sha},\cite{Coh2}. It can be used for discrete logarithm computation and we shall present it in this form, which is more general. Order computation is then solving $[n]P=\infp$ with $n\neq 0$ (and of course with unknown order). The baby-step giant-step method is based on the following: 
\begin{lemma}\label{diveuc}
	Let $n$ be a positive integer. Put $m:=\lfloor \sqrt{n}\rfloor+1$. Then for any $\alpha$ with $0\leq \alpha<n$ there are integers $i,j$, with $0\leq i,j\leq m-1$, such that $\alpha=i+jm$.
\end{lemma}
\begin{proof}
	If we divide $\alpha$ by $m$ we have $\alpha=jm+i$ with $0\leq i\leq m-1$. We note that $\alpha\leq n-1 = m^2-1=m(m-1)+(m-1)$ and we know that $i\leq m-1$. Hence we have $0\leq j\leq m-1$.
\end{proof}
Assume now that the order of $P\in G$ is $n$ and $\alpha$ an integer modulus $n$. Let $Q=[\alpha]P$, then we have $$Q\oplus[-jm]P=[i]P,$$ for some $i,j$ as in \cref{diveuc}. We have the following.
\begin{proposizione}\label{bsgs}
	Let $(G,\oplus)$ be a finite, additive, cyclic group of order $n$ and let $P$ be a
	generator of $G$. The following algorithm solves the discrete logarithm problem $[\alpha]P = Q$ in $O(m\log m)$ steps, where $m$ is define as follows.
\begin{enumerate}
	\item Let $m:=\lfloor \sqrt{n}\rfloor +1$.
	\item Create the two lists:
		\begin{center}
		\begin{tabular}{ll} 
			baby-step: & $P,[2]P\ldots,[m]P$ \\ 
			giant-step: & $Q\oplus[-m]P,Q\oplus[-2m]P,\ldots,Q\oplus[-m^2]P$\\ 
		\end{tabular}
	\end{center}
\end{enumerate}
Then there exists $0\leq i, j < m$ such that $Q\oplus[-jm]P = [i]P$ and $\alpha=jm+i$ is the solution to the discrete logarithm problem.
\end{proposizione}
\begin{proof}
	To compute the two lists we take at most $2m$ group operations. By \cref{diveuc}, there exists a match between the two lists, that can be found in $\log \sqrt{n}$ steps by using standard searching algorithms or hash tables. Hence, the total running time for the algorithm is $O( m\log m)$ steps.
\end{proof}
\section{A security twist}
In \cref{twistsecurity} we saw that every elliptic curve $E: y^2=x^3 + a_4x + a_6$ over $\Fq$ has a related twist curve which short Weierstrass equation is given by $\tilde{E}_v:y^2=x^3+a_4v^2x+a_6v^3$, where $v\in\Fq$ is a quadratic non-residue. From this form one sees that the two groups $E(\Fq)$ and $\tilde{E}_v(\Fq)$ together contain exactly two points $(x, y_i)$ for each field element $x\in\Fq$, and they both contain the identity $\infp$. So we have $| E(\Fq)|+| \tilde{E}_v(\Fq)|=2q+2$. Since the number of points on $E(\Fq )$ is $p + 1 - t$, it follows that the number of points on $\tilde{E}(\Fq )$ must be $\tilde{n}:= p + 1 + t$. 

The curve $E$ is said to be $\mathbf{twist\ secure}$ if the discrete logarithm is intractable on both $E(\Fq)$ and $\tilde{E}(\Fq)$. For $E$ to be twist secure we need, at the very least, that both $n=|E(\Fq )|$ and $\tilde{n}=|\tilde{E}(\Fq)|$ are prime numbers, or are small multiples of large primes. 

Why do we need twist security? The $y$-coordinate of a point is not needed for some cryptographic systems and there are implementations which only involve $x$-coordinate of points. Consider a system where a user (called Bob) has a secret key $\alpha_B\in\Z_p$. Under normal operation, anyone can send Bob a point $Q=(x_1,y_1)\in\ E(\Fq)$ and he will respond with the point $\alpha_BQ$. Assume this is done in a cryptographic system where there's no need of $y$-coordinates and therefore it is never sent. An attacker could send Bob an $x_1\in\Fq$ that is the $x$-coordinate of a point $\tilde{Q}$ on the twist $\tilde{E}(\Fq)$. Bob would then respond with the $x$-coordinate of $\alpha_B\tilde{Q}\in \tilde{E}(\Fq)$. If discrete logarithm problem in $\tilde{E}(\Fq)$ were easy, this response would expose Bob's secret key $\alpha_B$. Hence, if Bob skips the group
membership check, we must ensure, at the very least, that discrete logarithm in $\tilde{E}(\Fq)$ is intractable so
that $\alpha_B\tilde{Q}$ does not expose $\alpha_B$. Twist security is meant to ensure exactly that. 

The curves secp256r1 and secp256k1 we introduced in the previous chapter were not designed to be twist secure. The size of the twist
of secp256r1 is given by $\tilde{E}(\Fq)=2q+2-p$ and is divisible by $34905 = 3\cdot5\cdot13\cdot179.$ Consequently, by using baby step giant step algorithm, discrete logarithm on the twist is $\sqrt{34905}\simeq 187$ times easier than on secp256r1. Similarly, for secp256k1
the size of the twist is divisible by $32\cdot132\cdot3319\cdot22639$, and consequently, discrete logarithm on the
twist is $\simeq 218$ times easier than on secp256k1.

\section{Implicit baby step, giant step}\label{implicit bsgs}
In this section we describe an implicit version of the baby step giant step algorithm, which comes from an idea of Maurer and Wolf \cite{Mau}. We use the multiplicative group $\Zpstar$ as $auxiliary$ $group$, thus we reduce the discrete logarithm problem of $(G,\oplus)$ to a problem in $\Zpstar$. The advantage of this approach is that $\Zpstar$ has many subgroup and one can exploit its rich and well understood subgroup structure. 

Assume $(G,\oplus)$ to be a finite, additive, cyclic group of prime order $p$ and let $P$ be a generator. We define the following map:
\begin{alignat*}{2}
	\rho:\Zpstar &\longrightarrow& \aut(G) \\
	\alpha &\longmapsto&\rho_\alpha:G&\longrightarrow G\\
	&&P& \longmapsto {}[\alpha]P
\end{alignat*}
It is easy to see that $\rho$ is a group homomorphism with kernel $$\ker\rho=\{\alpha\in\Zpstar:\rho_\alpha(P)=P\}=\{1\}.$$ If $\varphi\in\aut(G)$ and $P$ is a generator for $G$, then $\varphi(P)=[\lambda]P$ for some $\lambda\in\Zpstar$. Thus we have an isomorphism $\Zpstar\simeq\aut(G)$ and we can identify the element $[\alpha]P\in G$ with $\alpha\in\Zpstar$. 

We want to solve the discrete logarithm problem in $G$, i.e., given a generator $P$ and an element $Q\in G$, we want to find the integer $\alpha$ modulus $p$ such that $Q=[\alpha]P$. Let $z$ be a primitive element of $\Zpstar$, then $\alpha=z^k$ for some $0\leq k<p$ and $Q=[z^k]P$. Let $m:=\lfloor \sqrt{p}\rfloor+1$, if we divide $k$ by $m$ we get $i,j$ with $0\leq i,j\leq m-1$ such that $k=i+mj$, as in \cref{diveuc}. It follows that $Q=[z^k]P=[z^{i+jm}]P=[z^i][z^{jm}]P$, which leads to $$[z^{-jm}]Q=[z^i]P.$$ However, we now that $Q=[\alpha]P$, thus we have $[z^{-jm}][\alpha]P=[z^i]P$ and this implies $z^{-jm}\alpha=z^i\mod p$. Hence, if we find such an $i$ and $j$, we can compute $\alpha=z^{i+jm}$ and we have the solution of the discrete logarithm problem. Now we can proceed as in \cref{bsgs}. 

We put $m:=\lfloor\sqrt{p}\rfloor$ and we build the two following lists:
\begin{center}
\begin{tabular}{ll} 
	baby-step: & $[z]P,\ [z^{2}],\ldots,\ [z^m]P$ \\ 
	giant-step: & $[z^{-m}]Q,\ [z^{-2m}]Q,\ \ldots,\ [z^{-m^2}]Q$.\\ 
\end{tabular}
\end{center}
In time $O( m \log m)$ we will find a match that solves the discrete logarithm problem. The algorithm described above is what we call $implicit$ $baby$ $step$ $giant$ $step$. It is interesting to note that this idea can be improved if a divisor $d$ of $p-1$ is known. 

Let $z_d=z^{\frac{p-1}{d}}$  be a generator for the order $d$ subgroup of $\Zpstar$. We can put $m:=\lfloor \sqrt{d}\rfloor+1$ and run the implicit baby step giant step by using $z_d$ instead of $z$. If happens that the unknown $\alpha$ lies in the $d$ order subgroup of $\Zpstar$, then $\alpha$ will be equal to $z_d^k$ for some $k$ modulus $d$ and the algorithm will find a match $[z_d^{-jm}]Q=[z_d^i]P$. Hence, $[z_d^{-jm}][\alpha]P=[z_d^i]P$, which lead to $\alpha=z_d^{i+jm}$ and the discrete logarithm problem is solved in times $O(m\log m)$, where now $m=\lfloor\sqrt{d}\rfloor+1$. The difference here is that after at most $d$ iterations we will have either found $\alpha$ or verified that $\alpha$ is not in the order $d$ subgroup. Thus, if $d$ is sufficiently small, the discrete logarithm problem can be solved much easier then would otherwise, provided that $\alpha$ lies in the $d$ order subgroup. On the other hand, if $\alpha$ is not in the $d$ order subgroup, then the algorithm will not find a match. We summarize in the following.
\begin{teorema}
	Let $G$ be an additive, cyclic group of prime order $p$, with generator $P$. Let $Q=[\alpha]P$ be another given element of $G$ (with $\alpha$ unknown). For a given divisor $d$ of $p-1$, let $D$ be the subgroup of $\Zpstar$ of order $d$. Then, one can decide wether or not $\alpha$ belong to $D$ in $O(\sqrt{d})$ steps. Moreover, if $\alpha$ belong to $D$, the same algorithm will find the discrete logarithm $\alpha$ in $O(\sqrt{d})$ steps.
\end{teorema} 
In an elliptic curve cryptosystem, the integer $\alpha$ represent the $private$ $key$, while the point $Q=[\alpha]P$ is the $public$ $key$. Every public key for which the corresponding private key lies  in a small subgroup of $\Zpstar$ is deemed to be weak.
\subsection{Testing wether a key is weak}
A simple approach to test wether the private key corresponding to a public key is weak is to set a bound $B$ for the order of the subgroups of $\Zpstar$. One can run the implicit baby step giant step algorithm on all divisors of $p-1$ that are less than $B$. However, this would be inefficient and redundant, because testing wether a key is in a subgroup of order $d$ also covers all subgroups of order divisible by $d$. Thus, we instead generate a list of integers $d_1<d_2<\dots<d_t\leq B$ dividing $p-1$ such that $d_i\nmid d_j$ for all $1\leq i<j\leq t$. 
\begin{esempio}\label{testsecp256k1}
Let's consider the elliptic curve secp256k1 introduced in the previous chapter. The standard \cite{nist} specify the generator 
\begin{align*}
	P=&(550662630222773436695787188951685\\
	&34326250603453777594175500187360389116729240,\\
	&3267051002075881697808308513050704\\
	&3184471273380659243275938904335757337482424)
\end{align*}
and its order, which is the prime $$p=115792089237316195423570985008687907852837564279074904382605163141518161494337.$$
By using a computer algebra system (e.g., pari-gp or sagemath,\cite{pari},\cite{sage}), one can factor $p-1$ in few seconds and compute the primitive element $z=7$. There are 10 divisor of $p-1$ below $B=48$, namely 2, 3, 4, 6, 8, 12, 16, 24, 32, 48. In order to test wether a given private key is in any of the subgroups of these orders, it suffices to test only the subgroups of order $d_1=32$ and $d_2=48$, as the firs eight subgroup orders divide 48, and thus any element of one of these smaller orders is also an element of the subgroup of order 48. 

Let $Q$ be the point 
\begin{align*}
	P=&(100760202697161893004335214126591\\
	&116800117319792545458764085267675326325395621,\\
	&7519344431816503114635930462106279\\
	&7862272142296678797285916994295833810377664).
\end{align*}
If we run the implicit baby step giant step algorithm, we will find a match in a couple of seconds. This give us the base $P$ discrete logarithm of $Q$  $$\alpha=648268771218401016825236294626749677029376795
80369334126295633893540044112329.$$

\end{esempio}
You can find an implementation written in Rust on my GitHub repository \cite{repo}. It includes modules and algorithms for finite fields arithmetic and elliptic curves arithmetic in projective coordinates. Furthermore, an implementation of the implicit form of baby-step giant-step algorithm is available and one can use it to test if the private key corresponding to a public key is weak. 


\chapter{Analysis of recommended Elliptic Curves}\label{chanalysis}
In this chapter we investigate elliptic curves described in \cref{NISTcurves} and other curves used by OpenSSL. 
For each curves in the following tables, we enumerate the number of weak keys appearing in subgroups of size bounded by $B=2^{32},2^{64},2^{128},2^{160}$.  As described in \cref{implicit bsgs}, the cost to determine wether a given key is weak with respect to the bound $B$ is roughly $2^{16},2^{32},2^{64},2^{80}$ groups operations. Due to the sizes of numbers occurring in the counts, and in order to facilitate an easier comparison, we list the base-2 log of each number, i.e., the number of bits. 

The data recorded for each curve is as follows:
\begin{itemize}
%	\item curve label;
	\item $b(p)$: bit's number of the prime order group $E(\Fq)$;
	\item $n_B$: base-2 log of the number of weak keys with order bounded by B. Since $\phi(d)$ is the number of generators of a cyclic group of order $d$, i.e., the number of elements of order exactly $d$, we compute $$n_B=\log_2\sum_{d|p-1\atop d\leq B}\phi(d);$$
	\item $c_B$: base-2 log of the worst-case number of elliptic curve scalar multiplications required to test wether a key comes from a subgroup of order bounded by $B$ using implicit baby step giant step. Let $R(p,B)=\left\{d_1,\dots,d_t:d_i\ \text{divisor of }p-1,\ d_i\leq B,\ d_i\nmid d_j\ \text{for all}\ 1\leq i<j\leq t\right\}$. We compute $$c_B=\log_2\sum_{d\in R(p,B)}2\lceil\sqrt{d}\rceil.$$
\end{itemize}
\section{Analysis of weak keys on secp256k1}
Here we describe the weak keys analysis of the curve secp256k1 in \cref{testsecp256k1}.
We used the computer algebra system pari-gp \cite{pari} for computations. In \cref{gpcode} you can find scripts for computing $n_B$, $c_B$ for the curve secp256k1 within a bound $B=2^{32}$. We can deduce the weak keys analysis for other NIST's curves using the value of $p$ presented in the \cref{NISTcurves}. As for other curves, one can find parameters in \cite{Crocs}.

The elliptic curve group secp256k1 is cyclic of prime order $$p=115792089210356248762697446949407573529996955224135760342422259061068512044369,$$ and factors of $p-1$ below the bound $B=2^{32}$ are 
\begin{align*}
	\text{div}B=&[1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 64, 96, 149, 192, 298, 447,
	 596, 631, 894, 1192, \\&1262, 1788, 1893, 2384, 2524, 3576, 3786, 4768,5048, 7152, 7572, 9536, 10096, \\&14304, 15144, 20192, 28608, 30288, 40384,60576, 94019, 121152, 188038, \\& 282057, 376076, 564114, 752152,1128228, 1504304, 2256456, 3008608,\\&  4512912, 6017216, 9025824, 18051648].
\end{align*}
By formulas above we find that $n_B=24.10\text{ and }c_B=13.05.$ This shows that secp256k1 has approximately $2^{24}$ weak keys lying in subgroups of order below the bound $B=2^{32}$ and they can be detected in roughly $2^{13}$ group operations. One can repeat the test within a bound $B=2^{160}$ and this leads to more than $2^{147}$ weak keys, computable in roughly $2^{75}$ group operations (see tables in next chapter). As for the bound $B=2^{32}$, weak keys can be computed trivially given the public key, while the latter are on the threshold of what is likely possible for organizations with sufficient computational resources.
\lstinputlisting[caption={pari-gp code: Analysis of weak keys in secp256k1 with bound $B=2^{32}$},style=mystyle,language=pari,label=gpcode]{weak_analysis.gp}

\section{Weak keys on standardized curves}
Here we give an assessment of weak keys in recommended and standard elliptic curves together with the worst-case number of scalar multiplications required to detect them. Table \ref{weakprime} summarize the weak key analysis for curves presented in \cref{NISTcurves}. Curves in \cref{weakbin} are all defined over a binary field while curves in \cref{weakwtls} are Wireless Transport Layer Security curves, which is the security layer protocol in the WPA architecture. The primary goal of the WTLS layer is to provide privacy, data integrity and authentication between two communicating
applications. 

Note that the time required to count weak keys for a particular curve is dominated by the computation of the divisors of $p-1$, and thus by factoring. Therefore, a complete analysis for all standardized curves used by the community can be performed in several days. Most of the computations were run on a machine with Intel\textregistered Core\textsuperscript{TM} i3-2350M CPU @ 2.30GHz $\times$ 4 running Linux. A complete analysis for other standardized curves is available in \cite{Pra2}.
\begin{table}
	\caption{Weak keys analysis Brainpool curves}
	\label{weakbp}
	\centering
	\begin{tabular}{l c c c c c c c c c}
		\hline\hline
		Curve & $b(p)$ & $n_{2^{32}}$ & $c_{2^{32}}$ & $n_{2^{64}}$ & $c_{2^{64}}$ & $n_{2^{128}}$ & $c_{2^{128}}$& $n_{2^{160}}$ & $c_{2^{160}}$\\
		\hline
		brainpoolP160r1& 160 & 33.6 & 19.4 & 67.0 & 36.5 & 130.0 & 67.3 & 160.0 & 81.0\\
		brainpoolP192r1& 192 & 11.7 & 6.8 & 11.7 & 6.8 & 108.1 & 55.1 & 108.1 &55.1\\
		brainpoolP224r1& 224 & 10.0 & 6.0 & 10.0 & 6.0& 10.0 & 6.0& 10.0 & 6.0\\
		brainpoolP256r1& 256 & 4.2 & 3.3& 4.2 & 3.3 & 4.2 & 3.3 & 4.2 & 3.3  \\
		brainpoolP320r1& 320 & 34.7& 20.3 & 42.2 & 22.2& 42.2 & 22.2& 42.2 & 22.2\\
		brainpoolP384r1& 384 & 33.3 & 18.7 & 66.0 & 35.5 & 130.0 & 67.5 & 160.7 & 82.3\\
		brainpoolP512r1& 512 & 35.0 & 20.6 & 68.1 & 37.7 & 132.7 & 70.3 &163.3&85.0\\
		\hline\hline
	\end{tabular}
\end{table}
	\begin{table}
		\caption{Weak keys analysis for curves over prime fields}
		\label{weakprime}
		\centering
	\begin{tabular}{l c c c c c c c c c}
		\hline\hline
		Curve & $b(p)$ & $n_{2^{32}}$ & $c_{2^{32}}$ & $n_{2^{64}}$ & $c_{2^{64}}$ & $n_{2^{128}}$ & $c_{2^{128}}$& $n_{2^{160}}$ & $c_{2^{160}}$\\
		\hline
		secp112r2& 109 & 3.7 & 19.5& 66.3 & 36.0&109.8&55.9&109.8&55.9\\
		secp128r1 &128 & 31.8 & 18.0&66.0 &35.4& 128.0&65.0& 128.0&65.0\\
		secp128r2&126 & 31.5&16.8&315 &16.8& 126.0&64.0& 126.0&64.0\\
		secp160k1 &160 & 18.0 & 10.0&18.0 &10.0& 94.8&48.4& 160.5&81.8\\
		secp160r2&160 & 21.6 & 11.9&21.6 &11.8& 93.1&47.8&160.0&80.6\\
		P-192 & 192 & 17.5 & 9.8& 17.5 & 9.8&109.0&55.6 &109.0&55.6\\
		secp224k1& 224 & 2.6 & 2.6 & 2.6 & 2.6 & 2.6 & 2.6 & 2.6 & 2.6 \\
		P-224 & 224 & 29.0 & 15.5 & 29.0 & 15.5& 29.0 & 15.5& 29.0 & 15.5\\
		Curve25519 & 253 & 7.04 & 4.8& 7.04 & 4.8&114.3&58.2&144.7&73.4\\
		secp256k1 & 256 & 24.1 & 13.1 & 64.7 & 34.2 & 129.4 &67.0 &147.9&75.0\\
		secp256r1 & 256 & 36.0 & 21.5& 69.3&38.8&133.2&70.8&165.3&86.9 \\
		SM2 &256&32.5&18.13&59.7&30.8&59.7&30.8&59.7&30.8\\
		P-384 &  384 & 13.5 & 7.8& 13.5 & 7.8&103.3&52.7&103.3&52.7\\
		E448 & 446 & 33.1 & 18.9& 64.7 & 34.2&128.8&66.2&160.8&82.2\\
		P-521 &  521 & 31.4 & 16.7&50.0&26.0&128.8&66.3&130.5&66.2\\

		\hline\hline
	\end{tabular}
\end{table}
\begin{table}
	\caption{Weak keys analysis for curves over binary fields}
	\label{weakbin}
	\centering
	\begin{tabular}{l c c c c c c c c c}
		\hline\hline
		Curve & $b(p)$ & $n_{2^{32}}$ & $c_{2^{32}}$ & $n_{2^{64}}$ & $c_{2^{64}}$ & $n_{2^{128}}$ & $c_{2^{128}}$& $n_{2^{160}}$ & $c_{2^{160}}$\\
		\hline
		c2pnb163v1 & 162 & 37.8 & 23.6 & 70.9 & 40.7 & 134.1 &71.9 &160.8&82.8\\
		c2pnb163v2 & 162 & 26.4 & 14.2& 26.4&14.2&26.4&14.2&160.3&82.2 \\
		c2pnb163v3 & 162 & 8.8& 5.4& 8.8&5.4&8.8&5.4&160.9&82.3 \\
		c2tnb191v1 &190 & 10.3 &6.2 & 50.7& 26.3 & 124.7& 63.4& 149.6&75.8\\
		c2tnb191v2 &190 & 20.1 &11.0& 20.1& 11.0 & 118.68&60.3& 118.6&60.3\\
		c2tnb191v3 &188 & 31.8 &17.0& 37.6& 19.8 & 117.0&59.5& 156.6&78.3\\
		c2pnb208w1 & 192 & 31.4&16.7& 31.4&16.7& 31.4&16.7& 31.4&16.7\\
		sect193r2 &193& 2.0& 2.0& 2.0& 2.0&110.2&56.1&110.2&56.1\\
		c2tnb239v1 & 238& 30.2& 16.4&55.6& 28.8&55.6& 28.8&55.6 & 28.8\\
		c2tnb239v2 & 237& 14.6& 8.3& 14.6& 8.3& 14.6& 8.3& 14.6& 8.3\\
		c2tnb239v2 & 235& 30.6& 16.4& 64.0& 33.5& 84.4& 43.2& 158.4& 80.2\\
		c2tnb271v2 & 256& 13.0& 7.5& 66.3& 36.0& 123.0& 62.5& 146.0& 74.0\\
		c2pnb304w1 & 288& 30.0& 16.0& 66.3& 36.2&132.1& 70.0& 164.1& 85.8\\
		ECCp-353 & 353&6.3& 4.3& 6.3&4.3&108.9 &55.5 & 158.3&80.2\\
		c2pnb368w1 & 352&33.4&19.3&36.9 &19.4&128.1 &66.0&129.1 &65.6\\
		c2tnb431r1 & 417&31.4&16.7&31.4&16.7&118.6 &60.3&118.6 &60.3\\
		ECCp-359& 359&5.2&3.6&5.2&3.6&5.2&3.6&5.2&3.6\\
		\hline\hline
	\end{tabular}
\end{table}
\begin{table}
	\caption{Weak keys analysis for Wireless Transport Layer Security curves}
	\label{weakwtls}
	\centering
	\begin{tabular}{l c c c c c c c c c}
		\hline\hline
		Curve & $b(p)$ & $n_{2^{32}}$ & $c_{2^{32}}$ & $n_{2^{64}}$ & $c_{2^{64}}$ & $n_{2^{128}}$ & $c_{2^{128}}$& $n_{2^{160}}$ & $c_{2^{160}}$\\
		\hline
		wap-wsg-idm-ecid-wtls1 & 112 & 32.7 & 18.6 & 42.1 & 22.1 & 112 &57.0 &112&57.0\\
		wap-wsg-idm-ecid-wtls3 & 162 & 19.2 & 10.6& 59.3&30.6&122.0&62.0&160.2&82.0 \\
		wap-wsg-idm-ecid-wtls4 & 112 & 33.1& 18.6& 64.6&34.1&112.0&57.0&112.0&57.0 \\
		wap-wsg-idm-ecid-wtls6 &112 & 17.1 &9.5 & 17.1& 9.5 & 112& 56.9& 112&56.9\\
		wap-wsg-idm-ecid-wtls7 &160 & 31.5&16.8& 55.3& 28.6& 127.6& 65.3&159.2&81.1\\
		wap-wsg-idm-ecid-wtls8 &112 & 30.0&16.2&47.7& 24.8& 112&57.0& 112&57.0\\
		wap-wsg-idm-ecid-wtls9 & 160 & 33.1&18.9& 65.0&34.6& 129.0&66.8& 159.5&82.0\\
		wap-wsg-idm-ecid-wtls10 &231& 33.0& 18.6&64.0& 33.5&73.2& 37.6&159.8 & 81.5\\
		wap-wsg-idm-ecid-wtls11 & 232& 33.0& 18.3& 64.7& 34.3& 87.6& 44.7& 160.6& 82.0\\
		wap-wsg-idm-ecid-wtls12 & 224& 29.0& 15.5& 29.0& 15.5& 29.0& 15.5&29.0&15.5\\
		\hline\hline
	\end{tabular}
\end{table}
\chapter{Conclusions}
In this thesis we presented the idea of the implicit representation proposed by Prabhat Kushwaha and Ayan Mahalanobis in \cite{Pra1}, which use the multiplicative group $\Zpstar$ as \emph{auxiliary} group to solve the discrete logarithm in a cyclic group $G$, of prime order $p$. In particular, we described a modified version of the most common generic algorithm baby step giant step, which allows us to test wether a given public key was generated from a weak private key. Our data show that many curves have an abundance of weak keys at all levels, due to rather smooth factorization of $p-1$ and, in particular, many divisors of $p-1$ below the bound $B$. The actual counts of weak keys vary among the curves, but several of them has around $2^{160}$ weak keys within the lever $B=2^{160}$. Tables in previous section show notable examples of curves that have remarkably few weak keys, especially secp224k1, Brainpool256r1, Brainpool224r1 and ECCp-359. Curves such as secp193r2, Curve25519, c2pnb163v3 and ECCp-353 have few weak keys at lower bound, but many at $B\geq 2^{128}$. In most cases, however, our analysis show that the probability that a randomly selected key is weak (given simply by the number of weak keys divided bu the total number of keys) is very low. Thus, random key generation
is also sufficient to avoid our type of weak keys, provided that
key generation software is audited to ensure that it does in
fact generate keys randomly. However, a malicious party could causes users to be assigned weak keys, for example, via hacked key generation software, thus it is suggested to test if your public key comes from a secure private key before the usage. It's worth it to note that we can also use the described method to generate private keys that are secure against this kind of attack. For this aim we restricting them to be a random power of $z^{\frac{p-1}{r}}$, where $z$ is a primitive root in $\Z_p$ and $r$ is a large prime factor of $p-1$, thus forcing the private key to lie in an $r$-order subgroup of $\Zpstar$. 

An interesting question for future work is: what other discrete logarithm algorithms can be realized using implicit group representations? In \cite{Pra2} authors gave an implementation of \emph{Pollard kangaroo Algorithm}. It would be interesting, for example, to implement Pohlig-Hellman \cite{Stin},\cite{Sil} using the implicit group representation, since so many of the recommended elliptic curves are such that $p-1$ is relatively smooth. 
%% Fine dei capitoli normali, inizio dei capitoli-appendice (opzionali)
\appendix

%\part{Appendici}

%\chapter{Titolo della prima appendice}
%

%% Parte conclusiva del documento; tipicamente per riassunto, bibliografia e/o indice analitico.
\backmatter

%% Riassunto (opzionale)
%\summary


%% Bibliografia (praticamente obbligatoria)
\bibliographystyle{plain_\languagename}%% Carica l'omonimo file .bst, dove \languagename è la lingua attiva.
%% Nel caso in cui si usi un file .bib (consigliato)
\bibliography{thud}
%% Nel caso di bibliografia manuale, usare l'environment thebibliography.

%% Per l'indice analitico, usare il pacchetto makeidx (o analogo).

\end{document}

--- Istruzioni per l'aggiunta di nuove lingue ---
Per ogni nuova lingua utilizzata aggiungere nel preambolo il seguente spezzone:
    \addto\captionsitalian{%
        \def\abstractname{Sommario}%
        \def\acknowledgementsname{Ringraziamenti}%
        \def\authorcontactsname{Contatti dell'autore}%
        \def\candidatename{Candidato}%
        \def\chairname{Direttore}%
        \def\conclusionsname{Conclusioni}%
        \def\cosupervisorname{Co-relatore}%
        \def\cosupervisorsname{Co-relatori}%
        \def\cyclename{Ciclo}%
        \def\datename{Anno accademico}%
        \def\indexname{Indice analitico}%
        \def\institutecontactsname{Contatti dell'Istituto}%
        \def\introductionname{Introduzione}%
        \def\prefacename{Prefazione}%
        \def\reviewername{Controrelatore}%
        \def\reviewersname{Controrelatori}%
        %% Anno accademico
        \def\shortdatename{A.A.}%
        \def\summaryname{Riassunto}%
        \def\supervisorname{Relatore}%
        \def\supervisorsname{Relatori}%
        \def\thesisname{Tesi di \expandafter\ifcase\csname thud@target\endcsname Laurea\or Laurea Magistrale\or Dottorato\fi}%
        \def\tutorname{Tutor aziendale%
        \def\tutorsname{Tutor aziendali}%
    }
sostituendo a "italian" (nella 1a riga) il nome della lingua e traducendo le varie voci.