\documentclass[reqno]{amsart}
\usepackage{hyperref}
\usepackage{graphicx}
\AtBeginDocument{{\noindent\small
\emph{Electronic Journal of Differential Equations},
Vol. 2017 (2017), No. 20, pp. 1--8.\newline
ISSN: 1072-6691. URL: http://ejde.math.txstate.edu or http://ejde.math.unt.edu}
\thanks{\copyright 2017 Texas State University.}
\vspace{8mm}}
\begin{document}
\title[\hfilneg EJDE-2017/20\hfil Application of differential cryptography]
{Application of differential cryptography to a GN authentication hierarchy scheme}
\author[A. I. Golumbeanu \hfil EJDE-2017/20\hfilneg]
{Alin Ionu\c{t} Golumbeanu}
\address{Alin Ionu\c{t} Golumbeanu \newline
University of Craiova,
Street: A.I. Cuza 13,
200585 Craiova, Romania}
\email{alin.golumbeanu@inf.ucv.ro}
\dedicatory{Communicated by Vicentiu Radulescu}
\thanks{Submitted August 12, 2016. Published January 16, 2017.}
\subjclass[2010]{35H20, 35S15, 12H20, 11G07}
\keywords{Agreed session key; elliptic curves; public key based encryption;
\hfill\break\indent identity based encryption}
\begin{abstract}
Starting from the classical differential cryptography, we describe
how to construct particular parameters for elliptic curves with application
to the domain of information security. These results conclude to a key
used on symmetrical encryption. The article will review a solution in
which the parties are authenticated based on a secret knowledge and
a random parameter.
\end{abstract}
\maketitle
\numberwithin{equation}{section}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{definition}[theorem]{Definition}
\allowdisplaybreaks
\section{Introduction}
Communication secrecy mainly depends on the generation and distribution of
the master key. The keys generation stage relies on the computation of some
differential parameters over a particular elliptic curve.
This system is useful when a symmetrical encryption key is used for the
messages, and an agreement on a ciphering key (the session key),
based on public keys encryption, is made. The initial idea which led to
the development of the identity based system belongs to Shamir \cite{5,11},
whose aim was to create a method that ensures confidentiality.
Let Alice and Bob be the two parties who want to communicate.
Both have an e-mail address. When Alice wants to send a message to Bob,
she will be accessing a server which stores Bob's public key, and
she will use this key to encrypt information. The server will store
for both parties the private and public keys. A key request will
take place when the server receives a message which contains the
e-mail address of the one who's public key is asked for.
Shamir simplified the system by introducing a function, denoted by $\chi$,
which generates a public key based on a random string (e-mail address).
In this way, Alice will not be requesting the key from the server anymore,
instead she will use the key which was generated by the $\chi$ function.
The usefulness of the system resides in the fact that one can encrypt and
send messages to somebody on the network even if the password server is
unavailable. It also eliminates the need to gain access to the password
server for the dialog's counterpart. A series of algorithms and protocols
which are based on this system have been developed \cite{4,13,6,12,14}.
Not all of them can be used in real life due to the burden that some of
these algorithms and protocols impose on modern computing systems.
\section{Proposed Scheme}
\subsection*{The description of identity is based on the confidentiality of
the system.} In \cite{2,3,16,15}, there have been elaborated some series
of identity based systems. Those solutions are composed of the following parts:
\begin{enumerate}
\item \emph{The system's setup}.\\
To each dialoguing party the Password server assigns a control key, called $ID$.
This key is used by the Password server to communicate with its users.
The Password server will be called $PKG$ (\emph{Public Key Generator})
from now on.
\item \emph{Encryption}.\\
A participant, called $A$, who wants to communicate with another (called $B$),
will encrypt the message, which will be sent out with a public key, called $p_k$,
obtained from the morphing, through function $\chi$, of a string $s$
which contains $B$'s identifier (which can also be $B$'s address).
\item \emph{Decryption}. \\
A system user who will receive such messages will access the $PKG$ and, based
on his $ID$, will obtain the private key with which he can decrypt the message.
\end{enumerate}
In the eventuality in which the line is listen to, the eavesdropper will gain
access only to the encrypted message.
\subsection{Elliptic curve based system}
We consider the function
\begin{equation}
f(x)=\int \frac{dx}{\sqrt{4x^{3}-ax-b}}
\end{equation}
where $a$ and $b$ are constants.
The inverse of this function is called an elliptic curve.
Let $\gamma _1$ and $\gamma_2$ be two constants, and a double periodic
function over $\mathbb R$. Then the Weierstrass function is of the form
\begin{equation}
(\alpha ') ^{2}=4\alpha ^{3}-\gamma _1 \alpha - \gamma _2.
\end{equation}
The pair $(\alpha , \alpha ')$ defines in space a point on the elliptic curve
\begin{equation}
y ^{2}=4x ^{3}- \gamma _1x - \gamma _2.
\end{equation}
We refer to \cite{3} for more results.
\begin{definition}[\cite{5}] \rm
Let $p>3$ be a prime integer. The elliptic curve
$y ^{2}=x ^{3}+ \gamma _1x+ \gamma _2$, defined over $\mathbb Z_{p}$,
is being defined as the solution set of the form
$(x,y) \in \mathbb Z_{p} \times \mathbb Z_{p}$ with respect to the congruence
relation
\begin{equation}
y ^{2} \equiv x ^{3} + \gamma _1x + \gamma _2 \quad \mod p
\end{equation}
where the coefficients $\gamma _1,\gamma _2 \in \mathbb Z_{p}$
are constants which respect the relation
\begin{equation}
4 \gamma _1^{3} + 27 \gamma _2^{2} \equiv \hspace{-7pt} \not 0 \quad
\mod p
\end{equation}
together with a special point, called point at infinity
\end{definition}
\begin{lemma}[\cite{10}] \rm
Let $E$ be an elliptic curve defined as
\begin{equation}
Y _2 + \gamma _1XY + + \gamma _3Y = X ^{3} + \gamma _2X ^{2}
+ \gamma _{4}X + \gamma _{6}
\end{equation}
and $A _1 = (x _1, y _1)$, $A _2 = (x _2, y _2)$ two points on the curve.
Then
\begin{equation}
-A _1 = (x _1, - y _1 - \gamma _1x _1 - \gamma _3)
\end{equation}
and
\begin{equation}
\lambda =\frac{y_2-y_1}{x_2-x_1}, \quad
\gamma=\frac{y_1x_2-y_2x_1}{x_2-x_1}
\end{equation}
where $x _1, x _2$ satisfy the condition $x _1 \neq x _2$ and from here results
\begin{equation}
\lambda=\frac{3x_1^{2}+2\alpha _2x_1+\alpha _{4}
-\alpha_1y_1}{2 y_1+\alpha _1x_1+\alpha _3}, \quad
\gamma=\frac{-x_1^{3}+\alpha _{4}x_1+2 \alpha _{6}-\alpha _3y_1}{2 y_1+\alpha_1x_1+\alpha _3}.
\end{equation}
In the case $x _1$ equals $x _2$, the points $A _1$ \c and $A _2$ being unequal,
the addition of the two points will be done as
\begin{equation}
x_3 = \lambda ^{2}+\alpha _1\lambda-\alpha _2-x_1-x_2,\ y_3
= -(\lambda +\alpha_1)x_3-\gamma-\alpha _3
\end{equation}
\end{lemma}
With respect to this lemma, we distinguish the following two cases:
\begin{enumerate}
\item $x_2=x_1$ and $y_2=y_1$. In this case, $A_1+A_2=O$.
\item In all other cases we have $A_1+A_2=B=B(x_3,y_3)$, where
\begin{equation}
x_3=\lambda^{2}-x_1-x_2, y_3=\lambda(x_1-x_3)-y_1
\end{equation}
and
\begin{equation}
\lambda= \begin{cases}
(y_2-y_1)(x_2-x_1)^{-1}, &A_1\neq A_2; \\
(3x_1^{2}+a)(2y_1)^{-1}, &A_1=A_2.
\end{cases}
\end{equation}
\end{enumerate}
\subsection*{Optimization of Elliptic Curves Parameters}
In practice there are used elliptic curves defined over a finite field
$F_{q}$, which means that the study will be made on an Abelian group.
Let $s$ be the number of points on an elliptic curve $E$, defined over $F_{q}$.
Then $s=\#E(F_{q})=q+1-t$, where $\#E(F_{q})$ is named trace of Frobenius at $q$.
Thus we can define Frobenius endomorphism as being
\begin{equation}
\varphi = \begin{cases}
E(\overline{F}_{q}) \to E(\overline{F}_{q}) \\
(x,y) \to (x^{q},y^{q}) \\
\mathbf O \to \mathbf O
\end{cases}
\end{equation}
An approximation of the number of points on an elliptic curve is given by
the Hass theorem. In this way, $t$ must fulfil the condition
\begin{equation}
|t|\leq 2\sqrt{q}
\end{equation}
To compute the addition of two points on a elliptic curve in finite fields one
of the solutions will be Weil pairing implementation. Let $K$ be a finite
field and an elliptic curve defined over field $E(K)$ with $E(m)$ its
group of $m$-torsion points if $char(K)=p$ and $gcd(m,p)=1$ then there
are $m^{2}$ such points.
\begin{lemma}[\cite{16}]
Let $E$ be an elliptic curve over $F_{q}$ and $m$ be a prime which divides
$\#E(F_{q})$ but which does not divide $q-1$ and $m \neq char(F_{q})$.
Then $E(F_{q^{k}})$ contains the $m^{2}$ points of order $m$ if $m$ divides
$q^{k}-1$
\end{lemma}
According to \cite{8,17,18} we will define Weil pairing as being
$E(m)\times E(m) \to \gamma _{m}$ where $\gamma _{m}$ is the group of $m$th
roots of unity in $\overline{K}$. Thus, let be $B_1,B_2 \in E[m]$
and we choose a function $g$ in $E$ whose divisor satisfies
\begin{equation}
\operatorname{div}(g)=\sum _{D \in E[m]}(B'_1+D)-(D)
\end{equation}
with $B' \in E(\overline{K})$ such that $[m]B'=B$.
In this case, we define $e_{m}$ as:
\begin{equation}
e_{m}= \begin{cases}
E[m] \times E[m] \to \gamma _{m} \\
(B_1,B_2) \to \frac{g(X+B_1)}{g(X)}
\end{cases}
\end{equation}
In the case of the implementation in computing systems of a subfield curve,
of type $F_{q^{n}}$, $n$ must be greater than $1$ and the coefficients
from $F_{q}$. We will define \cite{9,10} as a new addition method
(and subsequently multiplication method by an integer) of two points on
the elliptic curve using Frobenius Expansion.
In equation $(16)$ $\varphi$ must satisfy equation
\begin{equation}
\varphi ^{2}-[t]\varphi+[q]=[0]
\end{equation}
In this way we will define an addition and multiplication method which
will speed up the finding of the result. For the particular case where
there is a subfield $F_{q^{n}}$ provided that the multiplication factor,
let it be $K$, to satisfy the property $|K|\leq \lfloor q/2 \rfloor$.
\subsection*{Model implementation}
Regarding the implementation of an hierarchical information's access,
a function which would generate a public key based on the conjugated
information, from the corresponding hierarchy level and the communication
channel's user's custom string, must be defined. Let be a function of the form
\begin{equation}
\varphi ({\rm level, string}) = \textrm{public key}
\end{equation}
where level represents the access level of an user and string represents
a character string which characterizes the communication's participant.
\begin{figure}[ht]
\begin{center}
\includegraphics[width=0.7\textwidth]{fig1}
\end{center}
\caption{Users grouped in a hierarchical order}
\label{fig1}
\end{figure}
In Figure 1 is being shown the way in which users are being grouped
in a hierarchical order. The basic principle of the hierarchy is
to respect the information's access rights by the users from the same level.
Every member of the network will define a point $A _{i} ^{j} \in E$,
where $j$ represents the hierarchical level of each user.
For every session, in order to obtain the private key from the key server,
it will be used the $GN_1$ algorithm, and resulting from the creation of
a session key, the private key will also be generated.
One must take into account the security facts described in \cite{1, 19,20,21}.
\subsection*{$GN_1$ Group Protocol}
Now we present the way to achieve the agreed key, for each $(A_i,A_j)$
participants pair and from it will be created a common key group,
in the assumption of security level which are presented and proved
in a previous work, detailed in \cite{7,22,23}.
To describe those cases let as consider the following:
\begin{itemize}
\item $\pi_{K_{A_i}}$ - the secret key of $A_i$
\item $\pi_{P_{A_i}}$ - the public key of $A_i$
\item $\eta_{A_i}^{d}(\pi_{K_{A_i}},m)$ - the encryption of message $m$
with $A_i$'s secret key
\item $\eta_{A_i}^{e}(\pi_{P_{A_i}},m)$ - the encryption of message $m$
with $A_i$'s public key
\item $\operatorname{enc}(s_K,m)$ - the symmetric key encryption of message $m$ with key $s_K$
\item $\inf_{A_i}$ - the pseudorandom generated value by $A_i$ for every session
\item $E(\mathbb Z_{p})$ - the elliptic curve defined over $\mathbb Z_{p}$
\item $M$ - the messages space
\item $hf(\cdot)$ - the $SHA-1$ hash function
\item $m_1|m_2$ - the concatenation of the $m_1$,$m_2$ messages, when $m_1$,
$m_2\in M$
\end{itemize}
A system user, denoted as $A_i$, has the next public parameters:
\begin{itemize}
\item $ (\pi_{P_{A_i}},E(\mathbb Z_{p}),P,Q,n)$, where $P,Q \in E(\mathbb Z_{p})$
\end{itemize}
Also, the function $\eta_ {A_i}^{d}(\pi_{K_{A_i}},m)$,
$\eta _{A_i}^{e}(\pi_{P_{A_i}},m)$ and $hf(\cdot)$ are public.
For the user $A_i$, the following are private:
\begin{itemize}
\item $\pi_{K_{A_i}}$ and $\inf_{A_i}$
\end{itemize}
From those, the steps are defined in the next manner:
\textbf{The Protocol}
\begin{itemize}
\item $A_i$
\begin{enumerate}
\item generates a pseudo-random number $\inf_{A_i}\in[1,n-1]$
\item calculates $A_i^{1}=\inf_{A_i}(P^{-1}+Q)=(x_1^{A_i},y_1^{A_i})$. Let $x=x_1^{A_i}$ $mod$ $n$. If $x=0$
then $goto$ step $1$
\item calculates $A_i^{2}=hf(P_{A_i}|A_i^{1})$
\item calculates $A_i^{3}=\eta _{A_i}^{d}(\pi_{K_{A_i}},A_i^{2})$
\item \textbf{The first communication step (from $A_i$ to $A_j$)} \\
$A_i$ sends to $A_j$ $(A_i^{1}|A_i^{2})$
\end{enumerate}
\item $A_j$
\begin{enumerate}
\item calculates $A_j^{1}=hf(P_{A_i}|A_i^{1})$
\item calculates $A_j^{2}=\eta_ {A_i}^{e}(\pi_{P_{A_i}},A_i^{2})$.
If $A_j^1\neq A_j^2$ terminates the protocol run with failure.
\item Generates pseudo random number $\inf_{A_j}\in [1,n-1]$
\item calculates $A_j^{1}=\inf_{B}(P^{-1}+Q)=(x^{A_j}_1,y^{A_j}_1)$. If $x^{A_j}_1=0$ go to step 3 of $A_j$'s steps
\item calculates $A_j^{2}=hf(P_{A_j}|A_j^{1})$
\item calculates $A_j^{3}=\eta_ {A_j}^{d}(\pi_{K_{A_j}},A_j^{2})$
\item $K_{A_j}=\inf_{A_j}A_i^{1}=(x^{A_j}_2,y^{A_j}_2)$
\item $x=x^{A_j}_2$ mod $n$. If $x=0$ then go to step 3 of $A_j$'s steps
\item \textbf{The second communication step (from $A_j$ to $A_i$)} \\
$A_j$ sends to $A_i$ $(A_j^{1}|A_j^{3})$
\end{enumerate}
\item $A_i$
\begin{enumerate}
\item[6] calculates \\
$s^{A_i}_1=hf(P_{A_j},A_j^{1})$ \\
$s^{A_i}_2=\eta_ {A_j}^{e}(\pi_{P_{A_i}},A_j^{3})$
\item[7] if $s^{A_i}_1 \neq s^{A_i}_2$ terminates the protocol run with failure
\item[8] $K_{A_i}=\inf_{A_i}A_j^{1}$
\end{enumerate}
\end{itemize}
\subsection*{Three step protocol}
Starting from the exposed protocol, as follows the three-steps protocol
which assures the confirmation of the key by $A_i$. This protocol is analogous
with the previous one, adding a supplementary step.
Therefore, $A_i$ will compute $hf((\inf_{A_i}(P^{-1}+Q))|
\operatorname{enc}(K_{A_i},\inf_{A_j}(P^{-1}+Q)))$ and send it to $A_j$.
At this point, $A_j$ will check the equality:
\begin{align*}
&hf((\inf_{A_i}(P^{-1}+Q))|\operatorname{enc}(K_{A_i},\inf_{A_j}(P^{-1}+Q)))\\
&=hf((\inf_{A_i}(P^{-1}+Q))|\operatorname{enc}(K_{A_j},\inf_{A_j}(P^{-1}+Q))).
\end{align*}
If the equality returns successfully, the key is confirmed.
In the implementation, we used a \emph{confirmation step}, in order to increase
the sped, because in case of fail the protocol will restart from the beginning.
Statistically, the necessary time to do this step is less than the spent
time for restart the protocol.
Therefore we define
\begin{equation}
h_{int}'(h(K))
\end{equation}
with $h_{int}':M \rightarrow N$, where $h'$ will generate an integer:
$h_{int}'(h(K))=t, t \in N$, and $t$ must accomplish $t \leq \sqrt{2}{n}$
Let ${L_t}_{ ; 0\leq t \leq m}$ be the hierarchy levels.
The key for each user $A_i^t$ will be made in two steps. First, the
authentication step, which is done in the first protocol, and second,
by authenticated key, made by the supplementary step from the second protocol.
The assumption of this scheme is that the key will be established from $M_t^i$
(the master key from the server, where $t$ is the level and $i$ is the user)
and the user $A_i$ knowledge.
\subsection{Conclusions}
In this article it is described a way in which the communication channel of
the user access to information can be grouped in a leveled hierarchy.
The problems known to this type of system are related to the length of
the messages exchanged by the participants, based on the same string structure.
In fact, in practice a time-stamp is used, but this is not always the case
because when wide-band consumers are involved the most important thing is
about thing is the computing time and the way to produce the time-stamp for
each group.
The proposed model limits the number of valid messages that can be transmitted,
with the same personalization string of an user, by a amplification factor
which takes into account the frequency of the communication between the
Key Generator and the control points of each level.
\subsection*{Acknowledgments}
The author acknowledges the support through Grant of The Executive
Council for Funding Higher Education, Research and Innovation,
Romania-UEFISCDI, Project Type: Advanced Collaborative Research Projects
- PCCA, Number 23/2014.
\begin{thebibliography}{00}
\bibitem{1} N. Constantinescu;
The agreement of the common key, \emph{Annals of the University of
Craiova - Mathematics and Computer Science Series}, Vol. \textbf{30}(2),
pp. 59--65, 2003.
\bibitem{2} N. Constantinescu, G. Stephanides;
Identification of parts in identity-based encryption, \emph{Research Notes
in Data Security, Wessex Institute of Technology}, UK, developed with
University of Bergen, Norway, ISBN 1-85312-713-2, 2004.
\bibitem{3} N. Constantinescu, G. Stephanides;
Secure Key-Exchange, \emph{Recent Advances in Communications and Computer Science},
Vol. \textbf{7}, pp. 162--166, Greece, 2003.
\bibitem{4} A. Miyaji, M. Nakabayashi, S. Takano;
New explicit condition of elliptic curve trace for FR-reduction,
\emph{IEICE Trans. Fundamentals}, Vol. \textbf{E84 A}(5), May 2001.
\bibitem{5} A. Shamir, Identity-based cryptosystems and signature schemes,
\emph{Advances in Cryptology, LNCS}, Vol. \textbf{196}, Springer-Verlag,
pp. 47--53, 1984.
\bibitem{13} I. Iancu, N. Constantinescu, M. Colhon;
Fingerprints Identification using a Fuzzy Logic System,
\emph{International Journal of Computers, Communications \& Control},
Vol. \textbf{5}(4), pp. 525--531, 2010.
\bibitem{6} H. Tanaka;
A realization scheme for identity-based cryptosystem,
\emph{Advances in Cryptology, LNCS}, Vol. \textbf{293}, Springer-Verlag,
pp. 341--349, 1987.
\bibitem{11} E. Simion, N. Constantinescu;
Complexity Computations in Code Cracking Problems,
\emph{Concurrent Engineering in Electronic Packaging, IEEE Communication},
May 05-09, pp. 225--232, ISSE 2001.
\bibitem{12} N. Constantinescu, G. Stephanides, M. Cosulschi, M. Gabroveanu;
RSA-Padding Signatures with Attack Studies, \emph{International Conference on
Web Information Systems and Technologies: Internet Technology/Web Interface
and Applications}, Portugal, ISBN 978-972-8865-46-7, pp. 97--100, 2006.
\bibitem{8} I. F. Blake, G. Seroussi, N. P. Smart;
\emph{Elliptic Curves in Cryptography}, Cambridge University Press, 2002.
\bibitem{7} N. Constantinescu, G. Stephanides;
The GN-authenticated key agreement, \emph{Journal of Applied Mathematics
and Computation}, Elsevier, London, Vol. \textbf{170}, pp. 531--544, 2006.
\bibitem{9} N. P. Smart;
Elliptic curves over small fields of odd characteristic,
\emph{Journal of Cryptography}, Vol. \textbf{12}, pp. 141--151, 1999.
\bibitem{10} J. A. Solinas;
\emph{An improved algorithm for arithmetic on a family of elliptic curves},
Springer-Verlag, 1997.
\bibitem{16} N. Constantinescu;
Authentication ranks with identities based on elliptic curves,
\emph{Annals of the University of Craiova, Mathematics and Computer Science Series},
Vol. \textbf{XXXIV}(1), pp. 94--99, 2007.
\bibitem{17} O. Ticleanu, N. Constantinescu, D. Ebanca;
Intelligent data retrieval with hierarchically structured information,
\emph{KES-IIMS}, Vol. \textbf{254}, pp. 345--351, Jun 26-28, Portugal, 2013.
\bibitem{19} O. Ticleanu;
Endomorphisms on elliptic curves for optimal subspaces and applications
to differential equations and nonlinear cryptography,
\emph{Electronic Journal of Differential Equations},
Vol. \textbf{2015}(14), pp. 1--8, 2015.
\bibitem{20} O. Ticleanu, N. Constantinescu;
Studying models issues on e-commerce cashing,
\emph{International Conference on Applied Mathematics and Computational
Methods in Engineering II} (AMCME '14), pp. 116--128, 2014.
\bibitem{21} O. Ticleanu;
Nonlinear analysis on elliptic curves subspaces with cryptographic applications,
\emph{Annals of the University of Craiova, Mathematics and Computer Science Series},
Vol. \textbf{41}(2), pp. 292--299, 2014.
\bibitem{14} N. Constantinescu;
Security System Vulnerabilities, \emph{Proceedings of the Romanian Academy
Series A-Mathematics Physics Technical Sciences Information Science},
Vol. \textbf{13}(2), pp. 175--179, 2012.
\bibitem{15} R. Alsaedi, N. Constantinescu, V. Radulescu;
Nonlinearities in Elliptic Curve Authentication, \emph{Entropy},
Vol. \textbf{16}(9), pp. 5144--5158, 2014.
\bibitem{22} O. Ticleanu;
Mathematical models in cryptography, \emph{Journal of Knowledge Communication
and Computing Technologies}, Vol. \textbf{4}(1), pp. 1--7, 2013.
\bibitem{23} O. Ticleanu;
Differential operators over particular elliptic curves spaces with cryptographic
applications, \emph{Electronic Journal of Differential Equations},
Vol. \textbf{2015}(303), pp. 1--9, 2015.
\bibitem{18} N. Constantinescu;
Authentication hierarchy based on blind signature,
\emph{Journal of Knowledge Communication and Computing Technologies},
Vol. \textbf{1}(1), pp. 77--84, 2010.
\end{thebibliography}
\end{document}