this is for holding javascript data
Massimiliano Sala edited section_Some_cryptographic_applications_This__.tex
about 6 years ago
Commit id: 5436f0f6d6b0798363e195b59923318209076077
deletions | additions
diff --git a/section_Some_cryptographic_applications_This__.tex b/section_Some_cryptographic_applications_This__.tex
index e1a22bf..7e10e35 100644
--- a/section_Some_cryptographic_applications_This__.tex
+++ b/section_Some_cryptographic_applications_This__.tex
...
\item Bob has received $c$ and so he can compute another exponentiation $c^d$ in $\ZZ_p$, the results being $m$ thanks to Theorem ??.
\end{itemize}
Thanks to the research in modular algebra developed in the last $30$ years, we observe that, even if the enemies simultaneously collect $N$, $e$, and $c$, then they have only a negligible probability to reconstruct $m$ and so the message remains hidden from them.
\subsection {El Gamal}
The system we have described is still used today a lot, especially on the Internet. We
complete this subsection with some observations on the security of RSA:
\begin{itemize}
\item the prime numbers $p$ and $q$ must be huge, at least $p,q > 2^{512}$,
\item the prime numbers $p$ and $q$ have to be chosen with some special properties, for example $p$ and $q$ cannot be too close to each
oter, or more precisely $|p-q|$ must be at least $\max(\sqrt(p),\sqrt(q))$;
\item the secret exponent $d$ must be chosen enough big, at least $d > \sqrt^4(N)$. now describe another cryptographic algorithm that provides public-key encryption.
Alice generates an efficient description of a cyclic group {\displaystyle G\,} G\, of order {\displaystyle q\,} q\, with generator {\displaystyle g} g. See below for a discussion on the required properties of this group.
Alice chooses an {\displaystyle x} x randomly from {\displaystyle \{1,\ldots ,q-1\}} \{1, \ldots, q-1\}.
Alice computes {\displaystyle h:=g^{x}} h:=g^{x}.
Alice publishes {\displaystyle h\,} h\,, along with the description of {\displaystyle G,q,g\,} G, q, g\,, as her public key. Alice retains {\displaystyle x} x as her private key, which must be kept secret.
Encryption[edit]
The encryption algorithm works as follows: to encrypt a message {\displaystyle m} m to Alice under her public key {\displaystyle (G,q,g,h)} (G,q,g,h),
\subsection {El Gamal} Bob chooses a random {\displaystyle y} y from {\displaystyle \{1,\ldots ,q-1\}} \{1, \ldots, q-1\}, then calculates {\displaystyle c_{1}:=g^{y}} c_{1}:=g^{y}.
Bob calculates the shared secret {\displaystyle s:=h^{y}:=g^{xy}} {\displaystyle s:=h^{y}:=g^{xy}} .
Bob maps his message {\displaystyle m} m onto an element {\displaystyle m'} m' of {\displaystyle G} G.
Bob calculates {\displaystyle c_{2}:=m'\cdot s} c_{2}:=m'\cdot s.
Bob sends the ciphertext {\textstyle (c_{1},c_{2})=(g^{y},m'\cdot h^{y})=(g^{y},m'\cdot g^{xy})} {\textstyle (c_{1},c_{2})=(g^{y},m'\cdot h^{y})=(g^{y},m'\cdot g^{xy})} to Alice.
Note that one can easily find {\displaystyle h^{y}} h^{y} if one knows {\displaystyle m'} m'. Therefore, a new {\displaystyle y} y is generated for every message to improve security. For this reason, {\displaystyle y} y is also called an ephemeral key.
Decryption[edit]
The decryption algorithm works as follows: to decrypt a ciphertext {\displaystyle (c_{1},c_{2})} (c_{1},c_{2}) with her private key {\displaystyle x} x,
Alice calculates the shared secret {\displaystyle s:=c_{1}{}^{x}} s:=c_{1}{}^{x}
and then computes {\displaystyle m':=c_{2}\cdot s^{-1}} m':=c_{2}\cdot s^{{-1}} which she then converts back into the plaintext message {\displaystyle m} m, where {\displaystyle s^{-1}} s^{-1} is the inverse of {\displaystyle s} s in the group {\displaystyle G} G. (E.g. modular multiplicative inverse if {\displaystyle G} G is a subgroup of a multiplicative group of integers modulo n).
The decryption algorithm produces the intended message, since
{\displaystyle c_{2}\cdot s^{-1}=m'\cdot h^{y}\cdot (g^{xy})^{-1}=m'\cdot g^{xy}\cdot g^{-xy}=m'.} c_2 \cdot s^{-1} = m'\cdot h^y \cdot (g^{xy})^{-1} = m'\cdot g^{xy} \cdot g^{-xy} = m'.