%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%% Cours:                                         %%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%% Historique :                                   %%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%% Introduction %%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%

\documentclass{seminar}
\usepackage{french}
\usepackage{fancybox}
\usepackage{amssymb}
\usepackage{pstricks}
\usepackage{pst-coil}

%%%%%% Local Definitions   %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
%%% Fonts for basic set characters %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

	\font\bb=msbm10 at 12 pt
	\font\lbb=msbm10 at 20 pt
	\font\bsm=msbm10 at 8 pt
 

%%% Characters for basic sets %%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

  % Normal size
	\def\R{\hbox{\bb R}}
	\def\C{\hbox{\bb C}}
	\def\Z{\hbox{\bb Z}}
	\def\Q{\hbox{\bb Q}}
	\def\N{\hbox{\bb N}}
	\def\F{\hbox{\bb F}}
	\def\P{\hbox{\bb P}}

  % Small size for abstracts
	\def\r{\hbox{\bsm R}}
	\def\cpx{\hbox{\bsm C}}
	\def\z{\hbox{\bsm Z}}
	\def\q{\hbox{\bsm Q}}
	\def\n{\hbox{\bsm N}}
	\def\f{\hbox{\bsm F}}
	\def\p{\hbox{\bsm P}}

  % Large size for titles
	\def\LR{\hbox{\lbb R}}
	\def\LC{\hbox{\lbb C}}
	\def\LZ{\hbox{\lbb Z}}
	\def\LQ{\hbox{\lbb Q}}
	\def\LN{\hbox{\lbb N}}
	\def\LF{\hbox{\lbb F}}
	\def\LP{\hbox{\lbb P}}

%%% Parameters %%%
%%%%%%%%%%%%%%%%%%

	\parindent=0pt

%%% Characters and particular notations %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

	\def\ieme{$^{\rm e}~ $}

%%% Titre, auteur, adresse %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

	\newcommand{\Titre}[1][ ]{{\LARGE {\centerline{ #1 }}}}
	\newcommand{\Auteur}[1][Robert Rolland]{{\Large {\centerline{\bf #1
}}}}
	\newcommand{\Labo}[1]
              [C.N.R.S., Institut de Math\'ematiques de Luminy]
              {\centerline{#1}}
	\newcommand{\Adr}[1]
              [F13288 Marseille CEDEX 9]
              {\centerline{#1}}
	\newcommand{\Email}[1]
              [e-mail: rolland@iml.univ-mrs.fr]
              {\centerline{#1}}

%%% Corps du textes %%%
%%%%%%%%%%%%%%%%%%%%%%%

 	\newcommand{\Stitre}[2][1]{{\Large {\centerline{\bf #1 - #2 }}}}
	\newcommand{\SStitre}[1][]{{\Large {\centerline{\bf #1}}}}
   	\newcommand{\Texte}[1][ ]{{\large {#1}}}

%%% Théorems, définitions, etc %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

	\newcommand{\Theo}[1][ ]{{\bf Th\'eor\`eme #1: }}
	\newcommand{\Defi}[1][ ]{{\bf D\'efinition #1: }}
	\newcommand{\Propo}[1][ ]{{\bf Proposition #1: }}
	\newcommand{\Coro}[1][ ]{{\bf Corollaire #1: }}
	\newcommand{\Lemme}[1][ ]{{\bf Lemme #1: }}
	\newcommand{\Preuve}[1][ ]{{\bf Preuve #1: }}
 	\newcommand{\Rem}[1][ ]{{\bf Remarque #1: }}
	\newcommand{\ex}[1][ ]{{\bf Exemple #1: }}



%%% Bibliography %%%
%%%%%%%%%%%%%%%%%%%%

	\def\bib#1#2#3#4{\bibitem{#1}{\bf #2}{\it\ #3}{\ #4}}

%%% Mathematical Définitions %%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

 
  % coordonnées: \rrseq[1]{m}{x} \rrpseq[1]{m}{x}
	\newcommand{\rrseq}[3][1]{#3_{#1},\ldots,\, #3_{#2}}
        \newcommand{\rrpseq}[3][1]{(#3_{#1},\ldots,\, #3_{#2})}

  % ensembles: \rrset[1]{n}{x}
	\newcommand{\rrset}[3][1]{\lbrace #3_{#1},\ldots,\, #3_{#2} \rbrace}

  % corps fini: \rrFq[q] ou \rrfq[q] ou \rrLFq[q]
	\newcommand{\rrFq}[1][q]{\F _{#1}}
	\newcommand{\rrfq}[1][q]{\f _{#1}}
	\newcommand{\rrLFq}[1][q]{\LF _{#1}}

  % espace affine sur Fq: \rrAn[q]{n}
	\newcommand{\rrAn}[2][q]{\F _{#1}^{#2}}
	\newcommand{\rran}[2][q]{\f _{#1}^{#2}}
	\newcommand{\rrLAn}[2][q]{\LF _{#1}^{#2}}


  % espace projectif sur Fq: \rrPn[q]{n}
	\newcommand{\rrPn}[2][q]{\P _{#1}^{#2}}
	\newcommand{\rrpn}[2][q]{\p _{#1}^{#2}}
	\newcommand{\rrLPn}[2][q]{\LP _{#1}^{#2}}

  % matrices: \rrmat[n]{m}{a}
	\newcommand{\rrmat}[3][n]{\pmatrix{
		#3_{1,1}   & \ldots & #3_{1,#2}  \cr
		\vdots     & \vdots & \vdots    \cr
		#3_{#1,1} & \ldots & #3_{#1,#2} \cr}}

  % matrice unite: \rrmatU
	\newcommand{\rrmatU}{\pmatrix{
 		\matrix{1 & \cr & 1 \cr} &  & {\hbox{\Large 0}} \hfill\cr
                  & \ddots & \cr
	\hfill { \hbox{\Large 0}} &  & \matrix{1 & \cr & 1 \cr} \cr }}

  % colonne: \rrvect[n]{a}
	\newcommand{\rrvect}[2][n]{\pmatrix{
		#2_{1}  \cr
		\vdots \cr
		#2_{#1} \cr}}

  % cefficients binomiaux: \rrcnp[n]{p}
	\newcommand{\rrcnp}[2][n]{\pmatrix{
		#1 \cr 
		#2 \cr }}

	


\begin{document}
\slideframe{oval}

%%%%%%%%%%%%%%%%%%%%%%%%% FICHE DE TITRE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}
\Titre[Cryptographie Civile] 

\bigskip
\Auteur

\bigskip

\Labo
\Adr
\Email

\end{slide}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  2  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}
\LARGE{\centerline{\bf Transmission de l'Information}}
{\Large 
\begin{itemize}
\item[$\bullet$]{Repr\'esentation de l'information, codage,
compression.}
\item[$\bullet$]{Int\'egrit\'e des donn\'ees, d\'etection et correction
des
erreurs.}
\item[$\bullet$]{Confidentialit\'e, cryptographie,
chiffrement, cryptanalyse.}
\end{itemize}
}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  3  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}
\LARGE{\centerline{\bf Principaux outils utilis\'es}}
{\Large 
\begin{itemize}
\item[$\bullet$]{Complexit\'e des algorithmes. }
\item[$\bullet$]{Probabilit\'es, entropie. }
\item[$\bullet$]{Arithm\'etique.}
\item[$\bullet$]{Corps finis, g\'eom\'etrie affine et projective
sur les corps finis, g\'eom\'etrie combinatoire.}
\item[$\bullet$]{Alg\`ebre commutative.}
\item[$\bullet$]{G\'eom\'etrie alg\'ebrique sur les corps finis.}
\end{itemize}
}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  4  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}
\LARGE{\centerline{\bf Les probl\`emes de la cryptographie}}
{\Large
\begin{itemize}
\item[$\bullet$]{Chiffrement.}
\item[$\bullet$]{Authentification.}
\item[$\bullet$]{Signature.}
\item[$\bullet$]{Gestion des cl\'es.}
\item[$\bullet$]{Mise en place de protocoles.}
\end{itemize}
}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  5  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}
\LARGE{\centerline{\bf Le Chiffrement}}
{\Large 

$\bullet$ Cl\'e secr\`ete (une seule cl\'e partag\'ee):
  \begin{itemize}
     \item[$\triangleright$]{One-time-pad (masque jetable), utilise un
masque
     al\'eatoire de la longueur du texte clair.}
     \item[$\triangleright$]{DES (Data Encryption Standard). Cl\'e de 56
bits, entr\'ee de 64 bits,
     sortie 64 bits.}
     \item[$\triangleright$]{IDEA (International Data Encryption
Algorithm). Cl\'e 128 bits,
     entr\'ee 64 bits, sortie 64 bits.}
  \end{itemize}
 
}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  6  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  6  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{slide}
{\LARGE{\centerline{\bf Le Chiffrement}}}
{\large \centerline{\bf Principe du masque jetable}
$$\begin{array}{clccccccccccc}
Masque & : & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & \cdots  \\
clair1 & : & 1 & 1 & 1 & 0 &   &   &   &   &   &   &         \\
{\red crypt1} &{\red : } &{\red 1 }&{\red 0 } &{\red 0 } &{\red 0 } &  
&   &   &   &   &   &         \\
clair2 & : &   &   &   &   & 0 & 1 & 0 & 0 & 1 &   &         \\
{\red crypt2} &{\red : } &   &   &   &   &{\red 1 } &{\red 1 } &{\red
1}  &{\red 0 } &{\red 1 } &   &         \\
\vdots & : &   &   &   &   &   &   &   &   &   & \vdots & \cdots \\
\end{array}
$$
Pour le masque: Utilisation de g\'en\'erateurs de bits al\'eatoires
(par exemple {\red Blum Blum Shub}).
}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  6  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{slide}
\LARGE{\centerline{\bf Le Chiffrement}}
{\Large
    
$\bullet$ Cl\'e publique:
   \begin{itemize}
     \item[$\triangleright$]{RSA (Rivest-Shamir-Adleman). Bas\'e sur la
difficult\'e
     de d\'ecomposer un nombre en facteurs premiers.}
     \item[$\triangleright$]{ElGamal (Chiffrement). Bas\'e sur la
difficult\'e du calcul
     des logarithmes discrets dans certains groupes.}
     \item[$\triangleright$]{McEliece. Bas\'e sur la difficult\'e du
d\'ecodage
     d'un code lin\'eaire g\'en\'eral.}
   \end{itemize}
  
}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  7  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}
\LARGE{\centerline{\bf La signature}}
{\Large
Pour signer un document on en construit une empreinte (Hachage)
et on signe l'empreinte.
\begin{itemize}
\item[$\bullet$]{Hachage: SHA (Secure Hash Algorithm).}
\item[$\bullet$]{Signature: 
  \begin{itemize}
    \item[$\triangleright$]{DSS (Digital Signature Standard)
          utilise DSA (Digital Signature Algorithm).}
    \item[$\triangleright$]{RSA (Rivest-Shamir-Adleman)} 
   \end{itemize}}
\end{itemize}
}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  9  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}
{\LARGE{\centerline{\bf Authentification}}}
{\Large
Utilise 
\begin{itemize}
\item[${\red \bullet}$]{La signature et ses outils li\'es au hachage,
         aux certificats.}
\item[${\red \bullet}$]{L'authentification:
   \begin{itemize}
    \item[${\blue \triangleright}$]{Sch\'ema d'authentification
          de {\red Feige-Fiat-Shamir}. Utilise la dificult\'e du calcul
          de la racine carr\'ee dans $\Z/n\Z$ si la d\'ecomposition
          de $n$ en facteurs premiers n'est pas connue.} 
   \end{itemize}}
\end{itemize}
}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  8  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}
{\LARGE{\centerline{\bf Gestion des cl\'es}}}
{\Large
Le chiffrement rapide utilise les syst\`emes \`a cl\'e secr\`ete (par
exemple PGP ({\red pretty good privacy}) utilise IDEA). Mais
la gestion des cl\'es se pose:
\begin{itemize}
  \item[${\red \bullet}$]{Échanges de cl\'es de
{\red Diffie et Hellman} (logarithme discret).}
  \item[${\red \bullet}$]{Chiffrement \`a
cl\'e publique.} 
  \item[${\red \bullet}$]{signature.}
\end{itemize}
}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  10 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}
{\LARGE{\centerline{\bf Gestion des cl\'es}}}
{\Large
L'utilisateur d'un syst\`eme \`a cl\'e publique
doit avoir confiance \`a la cl\'e publi\'ee: utilisation
de certificats (signature par des autorit\'es)
}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  11 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  11 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}
\LARGE{\centerline{\bf L'\'Echange de cl\'e }}
\LARGE{\centerline{\bf  de Diffie et Hellman}}
{\Large
Bas\'e sur le probl\`eme du logarithme discret.\par
On donne (public) un groupe $G$ et un $\alpha \in G$.
\medskip

\centerline{Alice $\longleftrightarrow$ Bob}
\centerline{$m$ secret ~~~~~~$n$ secret}
\centerline{$g^m \longrightarrow ~~$}
\centerline{$~~~~ \longleftarrow g^n$}
\centerline{$g^{nm} ~~~~~~~~~~~~~~~ g^{mn}$}

}

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  12 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}
\LARGE{\centerline{\bf L'\'Echange de cl\'e }}
\LARGE{\centerline{\bf  de Diffie et Hellman}}
{\Large
On choisit pour groupe un groupe multiplicatif
$(\Z/p\Z)^*$ o\`u $p$ premier de l'ordre de $10^{50}$
ou encore un corps fini
 et pour $\alpha$ un \'el\'ement
primitif.

\medskip

On peut aussi prendre pour $G$ une courbe elliptique
ou la Jacobienne d'une courbe hyperelliptique.
}

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  12 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}
\LARGE{\centerline{\bf Le syst\`eme RSA}}
{\Large
Bas\'e sur le probl\`eme de la factorisation d'un produit
de deux grands nombres premiers.

\medskip

Alice engendre deux nombres premiers $p$ et $q$ grands (100
chiffres),\par
puis calcule $n=pq$ et $\phi(n)=(p-1)(q-1)$.\par
Alice choisit $b$ al\'eatoire $1<b<\phi(n)$ tel que
$pgcd(b,\phi(n))=1$,\par
puis calcule $a=b^{-1} \quad mod~\phi(n)$ (Algo. d'Euclide).\par

}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  12 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}
\LARGE{\centerline{\bf Le syst\`eme RSA}}
{\Large

Alice publie $n$ et $b$ dans un r\'epertoire (cl\'e publique)
et garde $a$ secret (cl\'e priv\'ee).\par
Si on veut transmettre $x$ \`a Alice $1 <x<n$ on envoie
$y=e_K(x)=x^b~~mod~n$.\par
Alice calcule alors $d_K(y)=y^a ~~mod~n=x$
}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  12 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{slide}
\LARGE{\centerline{\bf Le syst\`eme RSA}}
{\Large

En effet
$$y^a~~mod~n=x^{(ab)}~~mod~n=$$
$$x^{(1+k\phi(n))}~~mod~n.$$

\medskip

Remarque: On peut montrer que pour tout $0 \leq x <n$ (pas
n\'ecessairement
premier avec $n$) on a $x^{(1+k\phi(n))}~~mod~n=x$.
}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  12 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}
\LARGE{\centerline{\bf Chiffrement d'ElGamal}}
{\Large
Bas\'e sur le probl\`eme du logarithme discret.

\medskip

Alice choisit $p$ premier puis $g$ et $x$ $<p$. \par
Elle calcule $y=g^x~~mod~p$.
La cl\'e publique est $(y,g,p)$ ($g,p$ pouvant \^etre partag\'es).\par
La cl\'e priv\'ee est $x$.
}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  13 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{slide}
\LARGE{\centerline{\bf Chiffrement d'ElGamal}}
{\Large
Si Bob veut communiquer le texte clair  $m$ ($m<q$) \`a Alice:\par
il choisit $k$ premier avec $p-1$ puis calcule
$$a=g^k~~mod ~p,$$
$$b=y^km~~mod~p.$$
Le texte chiffr\'e est $(a,b)$.

}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  13 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{slide}
\LARGE{\centerline{\bf Chiffrement d'ElGamal}}
{\Large
Pour d\'echiffrer Alice calcule
$$ba^{-x}~~ mod~p.$$
En effet:
$$a^x=g^{kx}~~mod~p,$$
$$ba^{-x}~~mod~p=y^kmg^{-kx}~~mod~p=$$
$$g^{kx}mg^{-kx}~~mod~p=m.$$
}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  13 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}
\LARGE{\centerline{\bf La signature DSA}}
{\Large
Bas\'ee sur le probl\`eme du logarithme discret.

\medskip

On construit $512 \leq L \leq 1024$, $L$ multiple de $64$.\par
$p$ premier $2^{L-1} <p < 2^L$ ($p$ a $L$ bits).\par
$q$ diviseur premier de $p-1$ avec $2^{159}<q<2^{160}$
($q$ a $160$ bits).\par
$h$ primitif dans $\Z/p\Z$ et $g=h^{(p-1)/q}$.
Donc $g$ est d'ordre $q$ dans $\Z/p\Z$.
}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  13 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}
\LARGE{\centerline{\bf La signature DSA}}
{\Large
Sont publics et communs $p,q,g$.\par
Chaque utilisateur choisit un $x$ tel que $0<x<q$ (cl\'e priv\'ee)
et calcule $y=g^x~~mod~p$ (sa cl\'e publique).\par
Pour signer une empreinte $M$ d'un texte $m$ l'utilisateur choisit
$0<k<q$
(un nouveau $k$ \`a chaque signature) et
calcule
$$r=(g^k~~mod~p)~~mod~q,$$
$$s=k^{-1}(M+rx)~~mod~q.$$

}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  13 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}
\LARGE{\centerline{\bf La signature DSA}}
{\Large
$(r,s)$ est la signature envoy\'ee avec le texte $m$.

Celui qui re\c coit le message doit v\'erifier la signature de la
mani\`ere suivante: \`a partir du texte $m$ il calcule
l'empreinte $M$ puis calcule
$$w=s^{-1}~~mod~q,\quad u_1=Mw~~mod~q,$$
$$u_2=rw~~mod~q,\quad v=(g^{u_1}y^{u_2}~~mod~p)~~mod~q.$$
Il v\'erifie que $v=r$.
}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  13 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{slide}
\LARGE{\centerline{\bf Canal subliminal }}
\LARGE{\centerline{\bf dans la signature DSA}}
{\Large
Si Alice envoie un message sign\'e \`a Bob, et si Bob
(en accord avec Alice) dispose de la cl\'e priv\'ee d'Alice $x$.
Alors \`a partir de $(r,s)$ Bob peut calculer $rx,M+rx$
et donc $k=(M+rx)s^{-1}$. \par
Alice et Bob ont donc \'echang\'e $k$ \`a l'insu de tout
observateur.

}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  13 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}
\LARGE{\centerline{\bf Un exemple sur les }}
\LARGE{\centerline{\bf courbes hyperellyptiques}}
{\Large
Bas\'e sur le probl\`eme du logarithme discret.

\medskip

Cette \'etude s'appuie sur l'\'etude de la courbe alg\'ebrique
$$y^2+h(x)y=f(x)$$
o\`u $deg(f)=2g+1$ et $deg(h) \leq g$.

}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  12 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{slide}
\LARGE{\centerline{\bf Un exemple sur les }}
\LARGE{\centerline{\bf courbes hyperellyptiques}}
{\Large

Les points de la jacobiennes peuvent \^etre repr\'esent\'es par les
couples
de polyn\^omes $(a,b)$ o\`u
\par\quad $\bullet$ $a$ unitaire de degr\'e $deg(a) \leq g$.
\par\quad $\bullet$ $deg(b) < deg(a)$.
\par\quad $\bullet$ $a$ divise $f-hb-b^2$.
}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  12 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{slide}

{\Large
La loi de groupe est d\'efinie par 
$$(a',b')=(a_1,b_1)*(a_2,b_2)$$
avec
$$d=pgcd(a_1,a_2,b_1+b_2+h)=$$
$$s_1a_1+s_2a_2+s_3(b_1+b_2+h),$$
$$a=a_1a_2/d^2,$$
$$b=(s_1a_1b_2+s_2a_2b_1+s_3(b_1b_2+f))/d ~~mod~a,$$

}
\end{slide}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  12 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{slide}

{\Large
puis
$$a'=(f-hb-b^2)/a$$
$$b'=(-h-b) ~~mod ~a'.$$
Et on r\'eit\`ere les calculs des deux derni\`eres lignes
(\`a partir de $a'$ et $b'$) jusqu'\`a ce que les r\'esultats
obtenus
v\'erifient les conditions de degr\'e impos\'ees pour la
repr\'esentation
d'un point de la jacobienne.
}
\end{slide}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  12 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{slide}
\LARGE{\centerline{\bf Sch\'ema d'identification}}
\LARGE{\centerline{\bf Feige - Fiat - Shamir}}
{\Large
Bas\'e sur la difficult\'e d'extraire une racine
carr\'ee dans $\Z/n\Z$ pour $n=pq$ ($p,q$ premiers).\par
Un arbitre choisit $n=pq$ et engendre les cl\'es publiques
et priv\'ees des utilisateurs.
$s$ cl\'e priv\'ee, $s^2=\mu$, $\nu=\mu^{-1}~~mod~n$.
$\nu$ est la cl\'e publique.
}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  12 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}

{\Large
Alice choisit $r<n$ et envoie $x=r^2~~mod~n$ \`a Victor.
Victor envoie un bit $b$ \`a Alice.\par
Si $b=0$ Alice renvoie $r$ \`a Victor qui v\'erifie que $r^2=x$.\par
Si $b=1$ Alice renvoie $y=(rs)~~mod~n$ \`a Victor
qui v\'erifie que $x=y^2\nu~~mod~n$.
\par
Si Alice veut tricher elle a une chance sur deux de se tromper.
Au bout de $t$ tests, Victor est convaincu.

}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  12 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{slide}

\LARGE{\centerline{\bf G\'en\'erateur al\'eatoire de}}
\LARGE{\centerline{\bf Blum - Blum - Shub}}
{\Large
On calcule deux grands nombres premiers $p,q \equiv 3 ~~mod~ 4$.
On pose $n=pq$. On choisit $x$ al\'eatoire premier avec $n$
et on pose $x_0=x^2 ~~mod~ n$.

Le $i$\ieme  bit pseudo al\'eatoire est le bit le
moins significatif de 
$$x_i=x_{i-1}^2 ~~mod~
n.$$                                                                                   

}
\end{slide}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  12 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}
{\LARGE{\centerline{\bf R\'ef\'erences }}}

{\large
M. Demazure, Cours d'Alg\`ebre, Cassini

\medskip
Groupe de travail sur la liaison Lyc\'ees-Universit\'es, 
Cours et activit\'es en arithm\'etique pour les classes terminales,
IREM de Marseille

\medskip
D. Kahn, La Guerre des Codes Secrets, InterEditions

\medskip
N. Koblitz, Algebraic Aspects of Cryptography, Springer

}
\end{slide}


\begin{slide}
{\LARGE{\centerline{\bf R\'ef\'erences }}}

{\large
R. Kumanduri, C. Romero, Number theory with computer applications

\medskip
B. Schneier, Cryptographie Appliqu\'ee, Thomson Publishing

\medskip
J. Stern, La Science du Secret, Editions Odile Jacob

\medskip

D. Stinson, Cryptographie Th\'eorique et Pratique, Thomson Publishing

}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  12 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%




\end{document}


