\documentclass[reqno]{amsart}
\usepackage{hyperref}
\usepackage{algorithm}
\AtBeginDocument{{\noindent\small
\emph{Electronic Journal of Differential Equations},
Vol. 2015 (2015), No. 303, pp. 1--7.\newline
ISSN: 1072-6691. URL: http://ejde.math.txstate.edu or http://ejde.math.unt.edu
\newline ftp ejde.math.txstate.edu}
\thanks{\copyright 2015 Texas State University.}
\vspace{9mm}}
\begin{document}
\title[\hfilneg EJDE-2015/303\hfil Elliptic curves on PDEs]
{Differential operators over particular elliptic curves spaces with cryptographic
applications}
\author[O. Adriana \c{T}icleanu \hfil EJDE-2015/303\hfilneg]
{Oana Adriana \c{T}icleanu}
\address{Oana Adriana \c{T}icleanu \newline
University of Craiova, Street: A.I. Cuza 13, 200585 Craiova, Romania}
\email{oana.ticleanu@inf.ucv.ro}
\thanks{Submitted September 12, 2015. Published December 11, 2015.}
\subjclass[2010]{35H20, 35S15, 12H20, 11G07}
\keywords{Elliptic curves; cryptography; differential equation}
\begin{abstract}
Finding optimal implementations to solve differential equations
in the case of boundary conditions is an open problem.
In the particular case of using nonsupersingular elliptic curves there
are applications in the asymmetric encryption field.
Starting from the general implementations, we constructed solutions
for the nonsupersingular elliptic curves case. Our developments
are of high interest in the domain of nonlinear cryptography and have
a good resistance for differential cryptanalysis.
\end{abstract}
\maketitle
\numberwithin{equation}{section}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\allowdisplaybreaks
\section{Introduction}
The study of elliptical curves has a rich history and proves once again
the beauty of pure, theoretical mathematics and the way its applicability
emerges in time.
Some properties of systems based on elliptical spaces date from the previous century.
Foundations in this sense were dated long before, by the study of diophantine
equations (3th century, Hellenic mathematician A. Diophantus).
This domain was highlighted with articles of mathematicians
Koblitz (\cite{nk87}) and Miller (\cite{vm86}) which gave a brand new
applicability of those equations in the domain of asymmetric cryptosystems.
\section{Elliptic equations analysis}
We start by defining a set of elliptic curves given by Weierstrass's equation
\begin{equation}\label{eqW1_1}
E:y^2=a_1xy+a_3y=x^3+a_2x^2+a_4x+a_6
\end{equation}
where $a_i\in K$ and $K$ is the space where curve $E$ is defined.
Those curves can be divided in two classes namely:
supersingular and nonsupersingular (\cite{amv93}).
Modern applicability of this concepts can be found in \cite{jkcctOT}.
\begin{enumerate}
\item A supersingular curve (zero $j$-invariant)
is the solution set of equation:
\begin{equation}\label{eq:super_1}
y^2=x^3+ax+b
\end{equation}
where $a,b\in GF(2^k)$, and the discriminant is $\Delta=4a^3+27b^2\neq 0$,
together with the point $\mathcal{O}$ at infinite.
\item A nonsupersingular elliptical curve (nonzero $j$-invariant) is
the solution set of equation
\begin{equation}\label{eq:nons_1}
y^2+xy=x^3+ax^2+b
\end{equation}
where $a,b\in GF(2^k)$, and the discriminant is $\Delta \neq 0$,
together with the point $\mathcal{O}$ at infinite.
\end{enumerate}
The pairs of points which are found on this kind of curves that have
a particular set of properties, together with a scalar, are the asymmetric
keys used in modern cryptography. Given this fact many mathematicians have
studied ways to obtain spaces with properties in this sense
\cite{amv93,ser79,st01} and model optimizations, by adding new boundary
conditions for nonlinear equations systems (\cite{acr14}).
Essentially, beyond optimal implementations, algorithmic complexity and
computing power, it is a proven fact that the only models which are resistant
to cryptographic attacks were those that had a mathematical outfit based
on the construction of subspaces with particularities. Those subspaces
have a solution set characterized by a diferential equation system which
is defined over elliptic curves through the Frobenius isomorphisms
\cite{analeOT,smart99}.
There are existing methods available to compute the involved parameters
and isomorphisms that define parts of the models. In the domain described
above we studied, build, developed and implemented proprietary solutions
for unsolved problems from the field of applied mathematics in cryptography,
which rely on nonsupersingular elliptic curves.
\section{Nonlinearities on elliptic curves.
Study implementation for nonsupersingular case}
After classifying the construction methods of the fields over which
are defined classical elliptical curves, we will describe optimized
personal solutions to compute the parameter $p$ of an elliptical
curve (algorithm \ref{subrutinamy}).
Let $\Gamma$ be a subset of points over an elliptical curve for which the
inverse was computed, $\chi$ the inverse of a number $\phi$, $t$
the differentiation level (which defines the safety degree of the generated system).
\begin{algorithm}[htp]
\caption{Differential calculation of the parameter $p$ of an elliptic curve}
\label{subrutinamy}
\begin{enumerate}
\item $\phi_0\leftarrow\lfloor \chi/b^t\rfloor$,
$\phi_0\leftarrow \phi-\theta_{0} b^t$, $\phi\leftarrow \phi_0$,
$i\leftarrow 0$, $\xi \leftarrow \phi_0$
\item while $\xi>0$ do
\item \quad $\theta_{i+1}\leftarrow\lfloor \theta_i/\xi^t\rfloor$,
$\phi_{i+1}\leftarrow \theta_i a-\theta_{i+1}\frac{b^t}{\xi}$
\item \quad $i\leftarrow i+1$, $\phi\leftarrow \phi+\phi_i$,
$\xi \leftarrow \lfloor\frac{b^t}{\phi_i}\rfloor$
\item while $\phi\geq p$ do $\phi\leftarrow \phi-\lfloor\frac{p}{\chi}\rfloor$
\end{enumerate}
\end{algorithm}
\section{Boundary solutions on particular subspaces on nonsupersingular
elliptic curves}
To have an increased resistance to differential attacks in cryptography
it is necessary to perform an optimal number of operations over elliptic curves,
which were achieved in the implementation \ref{subrutinamy}.
For the developed models we studied endomorphisms over finite fields and
the implications given by the differential equations involved in the
nonlinear analysis of the cryptographic system \cite{DBLPOT}.
\subsection{Transformation of nonsupersingular elliptic curve $\mathbb{Z}_q^p$
for invariant $j$}
From equations described by \cite{lst64} can be concluded that Jacobian
matrix is invertible over field $\mathbb{Z}_q$ and
$\delta=((D\Theta)^{-1}\Theta)(x_0,x_1,\ldots, x_{n-1})\in\mathbb{Z}^{n}_{q}$,
because
$$
(D\Theta)(x_0,\ldots, x_{n-1})\pmod{p}
$$
is the matrix's diagonal with nonzero elements.
It is obvious that the Gauss method can be applied in order to solve the equation
$$
(D\Theta)(x_0,\ldots,x_{n-1})\delta=\Theta(x_0,\ldots,x_{n-1})
$$
because diagonal elements are reversible.
It will be computed on each line, by moving the low-left item,
$\Phi'_p(x_0,x_{n-1})$, to right. After performing $k$ operations
of this kind, the item can be written as:
$$
(-1)^k\Phi'_p(x_0,x_{n-1}) \prod_{i=0}^{k-1}
\frac{\Phi'_p(x_{i+1},x_i)}{\Phi'_p(x_i,x_{i+1})}\,,
$$
and it can be proven that it is divisible with $p^k$ from
$\Phi'_p(x_{i+1},x_i)\equiv 0\pmod{p}$. The transformation of
the nonsupersingular elliptic curve is described in algorithm \ref{algTrjOT}.
\begin{algorithm}[htp]
\caption{Transformation of nonsupersingular elliptic curve $\mathbb{Z}_q^p$}
\label{algTrjOT}
\begin{itemize}
\item[Input:] System $j^P_i\in\mathbb{F}^{P}_{q}\backslash \mathbb{F}_{p^2}$
with $\Phi_p(j^P_i,j^P_{i+1})\equiv 0\pmod{p}$ for $0\leq i\leq n'$
with precision $[m/n]$.
\item[Output:] System $j^q_i\in\mathbb{Z}_q$ with
$\Phi_p(J^P_i,J^P_{i+1})\equiv 0\pmod{p^m}$ and $J^q_i\equiv j_i\pmod{p}$
for any $0\leq i0$.
Performing the reduction operation modulo $p$ for equation \eqref{eqgamma}
we get the next result:
\begin{equation}
\delta^p_m=-\frac{\Gamma(x_m,\Sigma(x_m))}{p^m\Delta_y}\pmod{p}
\end{equation}
which has a unique root of order $p$: $\delta_m\in\mathbb{F}_q$.
This is an approximation of $x$, given by
$x_m+p^m\delta_m\equiv x(mod\ p^{m+1})$. The root of order $p$
has a compute complexity of a grater order. There were given simplified
solutions from Satoh, Skjernaa and Taguchi, by replacing the equation
$\Gamma(X,\Sigma(X))=0$ with $\Gamma(\Sigma^{-1}(X),X)=0$. Thus,
$\delta_m$ will be defined as:
$$
\delta_m\equiv-\frac{\Gamma(\Sigma^{-1}(x_m),x_m)}{p^m\frac{\partial\Gamma}
{\partial Y}(\Sigma^{-1}(x_m),x_m)}\pmod{p}.
$$
From $\Gamma(\Sigma^{-1}(x_m),x_m)\equiv 0\pmod{p^m}$ it is necessary only
to compute the inverse of $(\frac{\partial\Gamma}{\partial Y}(\Sigma^{-1}(x_m),x_m)$
mod $p)$. Therefore, it can replace Satoh's classical method \cite{satoh02}
for nonsupersingular elliptic curve $\mathbb{F}^{q}_{p}$
(our solution can be found in the algorithm \ref{algSSTnOT}).
\begin{algorithm}[htp]
\caption{SST's simplified version for nonsupersingular elliptic curve
$\mathbb{F}^{q}_{p}$}
\label{algSSTnOT}
\begin{itemize}
\item[Input:] Polynomial $\Gamma(X,Y)\in\mathbb{Z}_q$,
item $x_0\in\mathbb{Z}_q$ which satisfies
$\Gamma(\Sigma^{-1}(x_0),x_0)\equiv 0\pmod{p}$ and the precision $m$.
\item[Output:] Item $x_m\in\mathbb{Z}_q$ with
$\Gamma(\Sigma^{-1}(x_m),x_m)\equiv 0\pmod{p^m}$ and $x_m\equiv x_0\pmod{p}$.
\end{itemize}
\begin{enumerate}
\item For $i=2$ to $m$ do
\item \quad $x^q_m(i)\leftarrow$ ALG \ref{algFjOT}($x_m,m$)
\item If $x^q_m(i)$ is not included in the nonsupersingular elliptic curve then
\item \quad resumes on step 1
\item $d\leftarrow \left(\frac{\partial\Gamma}{\partial Y}(\Sigma^{-1}(x_0),x_0)\right)^{-1}\ \pmod{p}$.
\item $y\leftarrow x_0\pmod{p}.$
\item For i=0 to m do
\item \quad $x\leftarrow \lfloor \frac{\Sigma^{-1}(y)\pmod{p^i}}{x^q_m(i)} \rfloor.$
\item \quad $y\leftarrow y-d\Gamma(x,y)\pmod{p^i}$.
\item Return $y$.
\end{enumerate}
\end{algorithm}
The complexity of the classic algorithm is given by the recalculation of
$\Gamma(x,y)$ after every iteration. Therefore, the values of $x$ and $y$
at step $i+1$ are very close to the values from step $i$. On the other hand,
the result given in algorithm \ref{algSSTnOT} uses an approximation
of the two parameters which simplify the computations.
After determining $x_W\equiv x\pmod{p^W}$ associated to a point $W$,
we select the elements $s\in\mathbb{N}$, for which
\begin{equation}\label{eqvi15}
\Gamma(\Sigma^{-1}(x_{sW+i}),x_{sW+i})\equiv \Gamma(\Sigma^{-1}(x_{sW}),x_{sW})
+\Delta(mod\ p^{(s+1)W})
\end{equation}
with
$$
\Delta=p^{sW}\Big(\frac{\partial\Gamma}{\partial X}(\Sigma^{-1}(x_{sW}),x_{sW})
\Sigma^{-1}(\delta)+\frac{\partial\Gamma}{\partial Y}
(\Sigma^{-1}(x_{sW}),x_{sW})\delta\Big).
$$
Finally, to obtain the solution, we compute the partial derivatives
$$
\frac{\partial\Gamma}{\partial X}(\Sigma^{-1}(x_{sW}),x_{sW})\quad
\mbox{and}\quad
\frac{\partial\Gamma}{\partial Y}(\Sigma^{-1}(x_{sW}),x_{sW})
$$
in $\pmod{p^W}$ case.
For $\Gamma(\Sigma^{-1}(x_{sW}),x_{sW})$ and $i