\documentclass{article}
\usepackage[latin1]{inputenc}
\usepackage{fullpage}
\usepackage{amsfonts}
\usepackage{algorithm}
\usepackage{url}
\usepackage{algpseudocode}
\usepackage[T1]{fontenc}

%\usepackage[dvips]{graphicx}
\def\application#1#2#3#4{%                                                      
\left\{\begin{array}{lcl}#1 & \longrightarrow & #2\\ #3 & \longmapsto &         
#4\end{array}\right.}

\newtheorem{theoreme}{Théorème}

\def\mod{~\mathrm{mod}~}
\def\Z{\mathbb{Z}}
\def\F{\mathbb{F}}

\title{TD 8 de Cryptologie\\
Protocoles}
\date{Lundi 5 décembre 2005}

\begin{document}
\maketitle

\section{Fiat-Shamir}
%    o ZK Fiat-Shamir chap10 p. 408.
On décrit le protocole d'identification \emph{zero-knowledge} de
Fiat-Shamir~:
\begin{center}
\fbox{\parbox{15cm}{\begin{enumerate}
    \item Le serveur de clef $T$ publie un module RSA $n = pq$ et
    garde $p$ et $q$ secrets.
    \item Alice choisit un entier secret $s$ tel que $1 \leq s
    \leq n - 1$ et $s$ est premier avec $n$, et publie $v = s^2
    \mod n$ comme sa clef publique.
    \item Pour s'identifier auprès de Bob, Alice choisit un gage $r$
    tel que $1 \leq r \leq n - 1$ et envoie à Bob le message $x = r^2
    \mod n$.
    \item Bob choisit un bit de défi au hasard $e \in \{0,
    1\}$ et l'envoie à Alice.
    \item Alice renvoie à Bob la réponse $y = rs^e$.
    \item Bob vérifie que $y^2 = x\cdot v^e$ et refuse
    l'authentification sinon.
\end{enumerate}}}
\end{center}

\begin{enumerate}
\setcounter{enumi}{0}
\item Montrer comment un imposteur peut répondre à l'un des deux
défis possibles sans connaître le secret.
\item En déduire la probabilité de réussite d'un imposteur, et
proposer une méthode pour renforcer le protocole.
\item Montrer que le protocole est effectivement \emph{zero-knowledge}
en discutant l'information que Bob a appris sur la clef d'Alice dans
le cas $e=0$ et le cas $e=1$.
\item Sur quel problème supposé difficile la sécurité du protocole
repose-t-elle~?
\item Que se passe-t-il lorsque Alice choisit par hasard deux fois la
même valeur de $r$~? Cela pose-t-il un problème en pratique pour les
tailles de clefs recommandées~?
\item Rappeler pourquoi savoir calculer des racines carrées modulo $n$
est équivalent à savoir factoriser $n$.
\end{enumerate}

\section{Partage de secret}
Dans la suite on se place dans un corps fini $\F_p$ (donc $p$ premier)
mais le résultat de l'interpolation de Lagrange reste valide dans un
corps quelconque.

Pour $x_1, x_2, \ldots, x_n$, $n$ points distincts de $\F_p$ fixés
l'application $\varphi:
\application{\F_p[X]_{n-1}}{(\F_p)^n}{P}{(P(x_1), P(x_2), \ldots,
P(x_n))}$ est un isomorphisme de $\F_p$-espaces vectoriels.

\begin{enumerate}
\setcounter{enumi}{6}
\item Montrer que $\varphi$ est effectivement un isomorphisme, et
montrer comment calculer $\varphi^{-1}$.
\item Application: calculer $P(X)$ de degré au plus $3$ dans $\F_{17}$
tel que
    \begin{itemize}
    \item $P(0) = 3$
    \item $P(3) = 6$
    \item $P(12) = 13$
    \item $P(1) = 7$
    \end{itemize}
\end{enumerate}
Alice souhaite partager un secret de taille environ $n\cdot \log_2
p$ bits qu'elle découpe en $n$ morceaux $a_0, a_1 \ldots, a_{n-1}$ tel que $0
\leq a_i \leq p-1$ pour tout $i$. Elle définit $P(X) =
\sum_{i=0}^{n-1}a_iX^i$ et distribue ensuite les $n$ secrets
partagés $P(x_1), \ldots, P(x_n)$.
\begin{enumerate}
\setcounter{enumi}{8}
\item Montrer que la connaissance des $n$ secrets partagés $\left(
P(x_i)\right)_{1 \leq i \leq n}$ permet de retrouver le secret
initial.
\item Que se passe-t-il si l'un des $x_i$ est $0$~?
\item Quelle ``quantité d'information'' est contenue dans un des
secrets partagés, c'est-à-dire, combien de secrets sont encore
théoriquement possibles lorsqu'on connaît un seul des secrets
partagés~?
\item Même question lorsqu'on connaît de $2$ à $n-1$ des secrets
partagés.
\end{enumerate}
Alice décide de changer de stratégie. Son secret $s$ n'est plus que de
taille $\log_2 p$ bits, elle fixe $a_0 = s$ et choisit les autres
coefficients de $P$ au hasard. Elle distribue comme avant $P(x_1),
P(x_2), \ldots, P(x_n)$.

\begin{enumerate}
\setcounter{enumi}{12}
\item Reprendre les questions 10 à 12 dans ce cas.
\item Comment adapter le protocole de partage de secret pour en faire
un protocole ``à seuil'', où $k$ parmi $n$ secrets partagés suffisent
pour retrouver le secret originel~?
\end{enumerate}
\end{document}
%    o Fair cryptosystem chap15 p. 640