\thumb


\sectionnn{Protocoles réseau}

%%% NEW 2025

\begin{exo}{Réseau du lycée}{\null}{2}{15}

\begin{questions}

\item Les machines de la salle informatique d'un lycée sont reliées au réseau pédagogique dont l'adresse est \texttt{172.20.0.0}. Le masque de sous-réseau est  \texttt{255.255.0.0}.

	\begin{questions}
		\item Quelle est l'adresse de diffusion sur ce réseau ?
		\item Un des ordinateurs de la salle a pour adresse \texttt{172.20.204.9}. Donner son adresse en notation CIDR.
		\item Déterminer le nombre total d'hôtes adressables sur ce réseau.
	\end{questions}
	
\item Le réseau administratif dispose de son propre réseau, d'adresse\linebreak \texttt{172.10.160.0/20}.

	\begin{questions}
		\item Déterminer le masque de sous-réseau du réseau administratif.
		\item Quelle est l'adresse de diffusion ?
		\item Donner le nombre maximum de machines pouvant être connectées à ce réseau.
		\item La machine d'adresse \texttt{172.10.176.1} fait-elle partie de ce réseau ? Justifier.
	\end{questions}

\end{questions}
\end{exo}

\begin{corrige}
\begin{questions}
\item 

	\begin{questions}
		\item L'adresse de diffusion se retrouve en plaçant tous les bits de la partie hôte à 1. À l'aide du masque, on déduit que la partie hôte occupe les 16 bits de poids faible. D'où : \texttt{172.20.255.255}.
		\item L'analyse du masque nous indiquant que la partie réseau est codée sur les 16 bits de poids fort, on note l'adresse : \texttt{172.20.204.9/16}.
		\item Il y a au total $2^{16} - 2 = 65~534$ machines adressables.
	\end{questions}
	
\item Le réseau administratif dispose de son propre réseau, d'adresse\linebreak \texttt{172.10.160.0/20}.
	\begin{questions}
		\item La notation CIDR utilisée indique que les 20 bits de poids fort de l'adresse codent pour la partie réseau. Le masque de sous-réseau est donc construit en mettant les 20 bits de poids fort à 1 et les 12 autres à 0, ce qui donne deux premiers octets de valeur 255, le troisième octet de valeur binaire \texttt{1111~0000} soit:
		\[
		2^7 + 2^6 + 2^5 + 2^4 = 128 + 64 + 32 + 16 = 240
		\]
		et le quatrième de valeur 0 : \texttt{255.255.240.0}.

		\item L'adresse de diffusion reprend la partie réseau de l'adresse et place tous les bits de la partie hôte à 1. D'où : \texttt{172.10.175.255}. Le troisième octet a pour valeur binaire : \texttt{1010~1111} (les 4 premiers bits sont issus de la partie réseau, les quatre derniers appartiennent à la partie hôte et sont à 1).

		\item Le nombre d'hôtes adressables est:
		\[
		2^{32-20} - 2 = 2^{12} - 2 = \numprint{4096} - 2 = \numprint{4094}.
		\]
		
		\item La machine d'adresse \texttt{172.10.176.1} appartient au réseau si sa partie réseau est identique à celle de l'adresse réseau \texttt{172.10.160.0}. La comparaison des deux premiers octets est immédiate. \'Etant donné que la partie réseau couvre les 20 bits de poids fort, il faut comparer aussi les 4 bits de poids fort du troisième octet : $160 = 1010~0000$ pour le réseau et $176 = 1011~0000$. Les 4 bits de poids fort sont différents, la machine n'appartient pas au réseau.
				
	\end{questions}
\end{questions}
\end{corrige}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%% NEW 2025

\begin{exo}{ARPANET}{Lycée Richelieu, Rueil-Malmaison}{3}{30}
Cet exercice porte sur les protocoles réseau.

\Par

ARPANET, partie ouest représentée sur la figure \ref{fig:arpanet}, est le premier réseau à transfert de paquets de données conçu aux États-Unis. En 1971, ce réseau contenait 23 nœuds dont 8 dans la partie ouest :

\begin{figure}
    \centering
    \includegraphics{304_arpanet}
    \figcaption{ARPANET en 1971, partie ouest.}
    \label{fig:arpanet}
\end{figure}

\begin{itemize}
    \item SRI : Stanford Research Institute
    \item AMES : Ames Research (NASA)
    \item UCSB : Université de Santa Barbara
    \item UCLA : Université de Los Angeles
    \item STANFORD : Université, Silicon Valley
    \item RAND : Research And Development
    \item SDC : System Development Corporation (Santa Monica)
    \item UTAH : Université de Salt Lake City
\end{itemize}

On schématise ce réseau par un ensemble de routeurs (appelés A, B, C, D, E, F, G et H) chacun associé directement à un réseau du même nom :

\begin{figure}
    \centering
    \includegraphics{305_graphe-arpanet}
    \figcaption{Schématisation du réseau.}
    \label{fig:graphe}
\end{figure}

On s'intéresse au protocole RIP, qui minimise le nombre de sauts entre routeurs. Si on l'applique au nœud $A$ de la figure \ref{fig:graphe}, on obtient la table de coûts suivante :

\begin{center}
\begin{tabular}{|c|c|}
\hline\tabulartitle
\multicolumn{2}{|c|}{Nœud A} \\
\hline\tabulartitle
Destination & Coût \\
\hline
B & 1 \\
C & 2 \\
D & 1 \\
E & 2 \\
F & 1 \\
G & 1 \\
H & 2 \\
\hline
\end{tabular}
\end{center}

\begin{questions}
    \item Écrire la table des coûts des nœuds B et F.
    \item En appliquant le protocole RIP, donner tous les chemins possibles d'un paquet de données partant du nœud $F$ à destination du nœud $H$.
    
    \newpage
    
    \item L'armée ajoute le nœud Z correspondant sur le réseau. Sa table de coûts est la suivante :

    \begin{center}
    \begin{tabular}{|c|c|}
    \hline\tabulartitle
\multicolumn{2}{|c|}{Nœud Z} \\
\hline\tabulartitle
    Destination & Coût \\
    \hline
    A & 3 \\
    B & 3 \\
    C & 1 \\
    D & 2 \\
    E & 3 \\
    F & 4 \\
    G & 2 \\
    H & 1 \\
    \hline
    \end{tabular}
    \end{center}

    Tracer le réseau en ajoutant ce n\oe ud Z pour qu'il respecte cette table de routage.
    \item On utilise maintenant le protocole OSPF qui minimise la somme des coûts de la transmission entre deux nœuds. Le réseau avec les coûts est illustré par la figure \ref{fig:reseau_couts}.

    \begin{figure}
        \centering
        \includegraphics{306_graphepond-arpanet}
        \figcaption{Réseau avec coûts.}
        \label{fig:reseau_couts}
    \end{figure}

    Avec le protocole OSPF, donner en justifiant le chemin pris par un paquet d'origine B à destination du nœud $H$.
\end{questions}

\end{exo}

\begin{corrige}
\enlargethispage*{4em}
\begin{questions}
\item On a les tables suivantes:
\Par
\begin{minipage}{0.5\linewidth}
 \begin{center}
    \begin{tabular}{|c|c|}
    \hline\tabulartitle
\multicolumn{2}{|c|}{Nœud B} \\
\hline\tabulartitle
    Destination & Coût \\
    \hline
    A & 1 \\
    C & 3 \\
    D & 2 \\
    E & 2 \\
    F & 2 \\
    G & 1 \\
    H & 2 \\
    \hline
    \end{tabular}
    \end{center}
\end{minipage}
\begin{minipage}{0.5\linewidth}
 \begin{center}
    \begin{tabular}{|c|c|}
    \hline\tabulartitle
\multicolumn{2}{|c|}{Nœud F} \\
\hline\tabulartitle
    Destination & Coût \\
    \hline
    A & 1 \\
    B & 2 \\
    C & 3 \\
    D & 2 \\
    E & 1 \\
    G & 2 \\
    H & 3 \\
    \hline
    \end{tabular}
    \end{center}
\end{minipage}

\item En partant du n\oe ud F, nous avons les possibilités suivantes:
\begin{itemize}
\item F -- E -- G -- H
\item F -- A -- G -- H
\end{itemize}

\item En insérant le n\oe ud Z, on a le réseau suivant:
\begin{center}
\includegraphics{314_new-reseau}
\end{center}

\item Le chemin qui a le plus faible coût :
\[
B - G - E - F - A - D - C - H
\]
avec un coût de 34.

À titre comparatif, par exemple, le chemin B--A--D--C--H a un coût de $10+10+10+10=40$, ce qui est plus grand que 34.
\end{questions}
\end{corrige}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%% NEW 2025

\begin{exo}{Réseaux et graphes}{D'après Métropole J1 Septembre 2024, exercice 2}{3}{20}
Le graphe représenté page ci-contre schématise l'architecture du réseau d'une entreprise. Les sommets représentent les routeurs et les arêtes représentent les liaisons.

\newpage

\begin{center}
\includegraphics{307_grapheG1}
\figcaption{Graphe non pondéré}
\label{graphe-G-1}
\end{center}

\begin{questions}
\item On suppose que le protocole de routage RIP est utilisé.

	\begin{questions}
	\item Recopier et compléter, en rajoutant autant de lignes que nécessaire, la table de routage simplifiée suivante du routeur R1.
	
	\begin{center}
	\begin{tabular}{|Zc|Zc|Zc|}
		\hline\tabulartitle
		Destination & Suivant & Nombre de sauts \\\hline
		R2 & R2 & 1 \\\hline
		R3 & & \\
		\hline
	\end{tabular}
	\end{center}

	Un paquet doit passer du routeur R1 au routeur R9.
	
	\item Donner l'un des chemins empruntés par le paquet ainsi que le nombre de sauts.
	
	On appelle M la matrice d'adjacence du graphe de la figure \ref{graphe-G-1}. Les sommets sont rangés par ordre croissant des numéros des routeurs (R1, R2, ..., R9).
	
	\item Donner l'écriture en Python de cette matrice d'adjacence sous la forme d'une liste de listes.
	
	Le degré d'un sommet est le nombre d'arêtes dont ce sommet est une extrémité.
	
	\enlargethispage*{4em}
	\item Recopier et compléter les lignes 3, 5 et 6 de la fonction \texttt{degre} qui prend en paramètre la matrice d'adjacence d'un graphe donné sous forme d'une liste de listes et qui renvoie la liste des degrés de tous les sommets du graphe rangés dans le même ordre que les sommets de la matrice d'adjacence.
	
	\begin{listing}[language=Python,numbers=left,numberstyle=\small]{}{09-grapheg1.py}\end{listing}

	\item Donner la liste renvoyée par \texttt{degre(M)}.
	
	On appelle chaîne eulérienne d'un graphe non orienté un chemin qui passe une et une seule fois par toutes les arêtes du graphe. Un graphe connexe admet une chaîne eulérienne si et seulement si le graphe possède, au plus, deux sommets de degré impair.
	
	Afin de vérifier l'état physique de la fibre optique installée sur le réseau, un robot inspecte toute la longueur de la fibre optique afin de s'assurer qu'elle ne présente pas de détérioration apparente.	
	
	\item En utilisant le résultat de la question précédente et en admettant que le graphe est connexe, indiquer si le robot peut parcourir l'ensemble du réseau en suivant les fibres optiques et en empruntant chaque fibre optique une et une seule fois.
	
	\end{questions}
	
	\item On considère maintenant le même réseau, représenté par un graphe pondéré figure \ref{graphe-G-2} dans lequel le poids de chaque arête représente la bande passante (ou débit maximal) de chaque liaison, en mégabits par seconde (Mb/s). On utilise le protocole de routage OSPF pour lequel le coût $C$ de chaque liaison est calculé par la formule :
	$$C = \frac{10^8}{BP}$$
	
	\hfill avec $BP$ la bande passante de la liaison, en bits par seconde.
	
\begin{center}
\includegraphics{308_grapheG2.eps}
\figcaption{Graphe pondéré}
\label{graphe-G-2}
\end{center}
	
	\begin{questions}	
	
	\item Reproduire le graphe pondéré en indiquant le coût de chaque arête.
	
	\item Déterminer la route empruntée par un paquet partant du routeur R1 à destination du routeur R9. Préciser le coût de ce trajet.
	\end{questions}
\end{questions}

\end{exo}

\begin{corrige}
\begin{questions}
	\item \begin{questions}
		\item On dresse autant de lignes que de routeurs accessible via le réseau. R2, R3, R6 et R4 sont directement reliés à R1, ils ont donc une métrique de 1. R5 est accessible avec une métrique de 2 (deux sauts), indifféremment via R2, R3 ou R6. %Le plus petit nombre de sauts pour atteindre R7 est 2 en passant par R6. De même pour R8. Enfin R9 est accessible par R6 puis R7 (ou R8).
		
		\begin{center}
	\begin{tabular}{|Zc|Zc|Zc|}
		\hline\tabulartitle
		Destination & Suivant & Nombre de sauts \\\hline
		R2 & R2 & 1 \\\hline
		R3 & R3 & 1 \\\hline
		R4 & R4 & 1 \\\hline
		R5 & R2 & 2 \\\hline
		R6 & R6 & 1 \\\hline
		R7 & R6 & 2 \\\hline
		R8 & R6 & 2 \\\hline
		R9 & R6 & 3 \\\hline
	\end{tabular}
	\end{center}
	
		\item Le protocole RIP minimise le nombre de sauts. R9 sera donc atteint par le chemin R1 -- R6 -- R7 (ou R8) -- R9.
		
		\item Matrice d'adjacence sous forme de liste de liste :
		
		\begin{listing}{}{09-matrice-adjacence.py}\end{listing}
		
		\item 
		
		\begin{listing}{}{09-grapheg1-corr.py}\end{listing}
		
		\item \texttt{degre(M)} retourne \texttt{[4, 3, 4, 2, 5, 6, 4, 3, 2]}.
		
		\item Le robot doit inspecter toutes les liaisons (parcourir toutes les arêtes du graphe) une et une seule fois. Un tel chemin existe s'il existe une chaîne eulérienne dans ce graphe. Une telle chaîne existe si et seulement si le graphe possède au plus deux sommets de degré impair. Il y a trois sommets (R2, R5, R8) de degrés impair. On en déduit donc qu'une telle chaîne n'existe pas. Le robot ne pourra donc pas parcourir le réseau en respectant les conditions imposées.
		 
		\end{questions}
		
		\enlargethispage*{3em}
\item \begin{questions}
		\item Le graphe pondéré par les coûts des liaisons calculées est le suivant : 	
\begin{center}
\includegraphics{315_grapheG3.eps}
\end{center}

		\item Le plus court chemin est : R1 -- R2 -- R5 -- R6 -- R7 -- R9. Son coût total est : $1 + 1 + 1 + 1 + 2 = 6$.
	\end{questions}
\end{questions}
\end{corrige}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

\sectionnn{Sécurisation des communications}

\begin{exo}{ROT13}{Lycée Henri Alain-Fournier, Bourges}{1}{10} 
\label{exo:08-ROT13}
\'Ecrire une fonction Python \texttt{chiffrement}\_\texttt{rot13(message)} permettant de chiffrer un message à l'aide de l'algorithme de chiffrement ROT13. Pour cela,
\begin{itemize}
\item on s'assurera que toutes les lettres du message sont en minuscule;
\item si le message comporte plusieurs mots, on le découpera;
\item on écrira une fonction \texttt{rot13(mot)} chiffrant un mot à l'aide de\linebreak l'algorithme demandé;
\item dans la fonction \texttt{chiffrement}\_\texttt{rot13(message)}, on fera appel à la\linebreak fonction \texttt{rot13(mot)}.
\end{itemize}

Chiffrer alors le message : \og cheval indomptable \fg.
\end{exo}

\begin{corrige}
Une proposition de programme est donnée page suivante.

\Par

Dans la fonction \texttt{rot13(mot)},
\begin{itemize}
\item on commence par initialiser une chaîne de caractères \texttt{r} vide, qui contiendra le résultat attendu;

\item on parcourt chaque lettre du mot: on détermine son code ASCII avec \texttt{ord(lettre)} et on lui ajoute 13. Ensuite, on soustrait le code ASCII du caractère 'a' afin d'associer 'a' à 0, 'b' à 1, etc. Le résultat de ces opérations est pris modulo 26 car l'alphabet est considéré comme un \og cycle \fg de longueur 26. On obtient ainsi le rang de la lettre chiffrée. Il suffit ensuite d'ajouter \texttt{ord('a')} au résultat pour obtenir le code ASCII de la lettre chiffrée. Ensuite, on utilise la commande \texttt{chr(code ASCII)} pour obtenir le caractère souhaité, que l'on ajoute à la chaîne \texttt{r}.
\end{itemize}

Dans la fonction \texttt{chiffrement}\_\texttt{rot13(message)}, on transforme le message de sorte qu'il ne contienne que des minuscules, puis on parcourt la liste des mots composant le message (obtenue à l'aide de la méthode \texttt{split}) afin d'appliquer à chacun d'eux la fonction \texttt{rot13(mot)}.

%\newpage

Le message \og cheval indomptable \fg{} est alors chiffré en :
\begin{center}
\og puriny vaqbzcgnoyr \fg{} 
\end{center}

\qrset{height=1.1cm,version=5}\rput(-1,-0.7){
\psframebox{\qrcode{https://idl-live.prepamath.fr/ILTNSI/08-rot13.py}}}
\vspace*{-10pt}

\begin{listing}{}{08-rot13.py}\end{listing}

\newpage

\end{corrige}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exo}{Chiffrement à l'aide de XOR}{Lycée Sainte-Clotilde, Strasbourg}{2}{30}
\label{exo:08-XOR}
\begin{questions}
\item On donne le programme suivant:
\begin{listing}{}{08-crypto-1.py}\end{listing}
\begin{questions}
\item Qu'affiche-t-il ?
\item Son résultat peut-il être considéré comme une version chiffrée du texte initial ? Expliquez.
\end{questions}

\item Écrire la fonction réciproque \texttt{getText(liste)} qui, à partir du résultat de \texttt{getBytes(msg)}, retourne le texte initial \texttt{msg}.

\item On veut maintenant utiliser une clé secrète pour encoder les valeurs de la liste résultat de getBytes() afin qu'il ne soit pas possible à un intervenant de retrouver le texte initial par \texttt{getText()} sans connaître la clé.

Pour ce faire, on décide d'utiliser l'opération \og OU exclusif \fg (XOR) entre chaque octet du texte et celui de la clé. XOR est une opération binaire (notée \verb+^+ en Python) qui s'effectue sur chacun des bits des deux opérandes (voir page suivante).

\newpage

\begin{figure}
\begin{center}
\begin{tabular}{|C|Zc|Zc|}
\tabulartitle\hline
XOR & 0 & 1 \\
\hline
0 & 0 & 1 \\
\hline
1 & 1 & 0 \\
\hline
\end{tabular}
\tabcaption{Table du \og OU exclusif \fg{} }
\label{cours:table-XOR}
\end{center}
\end{figure}
\Par
Par exemple,
\begin{center}
56 \verb+^+ 83 $\to$ 0011 1000 \verb+^+ 0101 0011 = 0110 1011 $\to$ 107.
\end{center}

Supposons, pour le moment, que la clé est plus longue que le texte:
\begin{center}
Clé =  \og Ceci est une clé de 41 caractères de long \fg
\end{center}

\begin{questions}
\item Écrire une fonction qui reçoit un texte et une clé en arguments et retourne les octets du texte combinés aux octets respectifs de la clé via l'opération XOR. Le résultat sera fourni sous forme d'une liste d'octets.

\item Appliquer cette fonction au texte \og message urgent \fg avec la clé \og cryptographie005 \fg. 

Afficher la liste des octets ainsi cryptés obtenue et comparer avec l'utilisation de la fonction \texttt{getBytes()} de la question 1.

\item Constater qu'une fois l'opération XOR appliquée, il n'est pas possible de récupérer la phrase d'origine avec \texttt{getText()}.

\item Pour décrypter le texte, il faut appliquer l'opération inverse du XOR à la liste des octets chiffrés. Donc, il faut disposer de la clé secrète.

L'opération XOR est involutive, c'est-à-dire que :
\begin{center}
si a XOR b = c alors c XOR a = b et c XOR b = a.
\end{center}

Pour l'inverse, il suffit donc de l'appliquer une nouvelle fois, sur les octets chiffrés, avec la même clé.

Constater qu'une fois l'opération XOR appliquée à nouveau, le texte peut être déchiffré.
\end{questions}

\item On veut maintenant pouvoir utiliser une clé de longueur quelconque \linebreak(typiquement plus courte que le message à transmettre). Il n'y aura alors pas assez d'octets dans la clé pour calculer le XOR en une seule fois sur tout le message. On va donc répéter la clé, autant de fois que nécessaire, pour chiffrer le message en entier.

Par exemple,\enlargethispage*{4em}
\begin{itemize}\ttfamily
\item Clé: "Key"
\item Message: $\begin{aligned}[t]\texttt{"Ceci est le message"}\\\texttt{"KeyKeyKeyKeyKeyKeyK"}\end{aligned}$
%\newpage
\item Message chiffré = [ ord("C") \verb+^+ ord("K"),\\
\hspace*{4cm} ord("e") \verb+^+ ord("e"),\\
\hspace*{4cm} ord("c") \verb+^+ ord("y"),\\
\hspace*{4cm}  ord("i") \verb+^+ ord("K"),\\
\hspace*{4cm} ... ]
\end{itemize}

\begin{questions}
\item Écrire une fonction \texttt{computeXorRepeatingKey(text,key)} qui effectue ce calcul et l'appliquer sur une phrase.
\item Utiliser la même fonction, avec la même clé pour déchiffrer le\linebreak résultat précédent et vérifier que la reconstruction de la phase conduit bien à celle de départ.
\end{questions}
\end{questions}

\end{exo}

\begin{corrige}
\begin{questions}
\item 
\begin{questions}
\item La fonction \texttt{getBytes(msg)} retourne la liste des valeurs décimales de chaque octet qui compose le texte reçu \texttt{msg}. Par exemple, si le texte reçu est \og My \fg alors la fonction renvoie la liste \texttt{[77,121]} car 77 est le code ASCII de \og M \fg et 121 celui de \og y \fg.

Ainsi, le programme proposé affiche la liste de tous les codes ASCII des caractères qui composent le message informé.

\item Le résultat du programme est effectivement une manière d'encoder (écrire différemment) le texte initial via un encodage réversible. Techniquement, on peut donc dire qu'il s'agit d'un chiffrement dont la sécurité repose sur la
connaissance de l'algorithme utilisé (remplacement de chaque lettre par la valeur décimale de l'octet correspondant).

L'algorithme utilisé étant extrêmement simple, le chiffrement serait immédiatement \og cassé \fg.
\end{questions}

\item Une fonction possible est la suivante:
\begin{listing}{}{08-crypto-2.py}\end{listing}

\Par

Il suffit ici de parcourir la liste informée en argument de la fonction et de trouver, à l'aide de la fonction \texttt{chr()}, le caractère qui correspond au code ASCII de l'élément de la liste.

\item
\begin{questions}
\item Voici une proposition de fonction:
\begin{listing}{}{08-crypto-3a.py}\end{listing}

\Par

\item En utilisant la fonction \texttt{computeXor}, la liste suivante est retournée:

\Par

\texttt{[14, 23, 10, 3, 21, 8, 2, 82, 20, 2, 15, 12, 11, 68]}

alors qu'avec la fonction \texttt{getBytes}, on obtient la liste suivante:

\Par

\texttt{[109, 101, 115, 115, 97, 103, 101, 32, 117, 114, 103, 101, 110, 116]}

\Par

Bien entendu, nous n'obtenons pas du tout la même liste; la première liste est bien plus \og mystérieuse \fg{} que la seconde.

\enlargethispage*{2em}
\item Avec \texttt{print( getText(xorBytes) )}, où \texttt{xorBytes} est la liste retournée par la fonction \texttt{computeXor()}, nous avons une belle surprise...

\newpage

 Selon l'interpréteur que l'on utilise, l'affichage diffère mais une chose est sûre : ce n'est pas le message d'origine que nous voyons!

\item Avec le programme suivant:
\begin{listing}{}{08-crypto-3d.py}\end{listing}
\Par
on s'aperçoit en effet que le message initial apparaît en clair.
\end{questions}


\item
\begin{questions}
\item Voici une fonction possible:
\begin{listing}{}{08-crypto-4a.py}\end{listing}

\newpage

\item On peut utiliser le programme suivant:
\begin{listing}{}{08-crypto-4b.py}\end{listing}
\Par
Nous avons ici décidé d'afficher les listes des octets encodés et décodés, mais nous pouvons afficher directement la seule phrase déchiffrée, qui correspond bien à la phrase initiale.
\end{questions}
\end{questions}
\Par

\qrset{height=1.1cm,version=5}\rput(-1,0.5){
\psframebox{\qrcode{https://idl-live.prepamath.fr/ILTNSI/08-crypto.py}}}
\textit{Téléchargez le programme complet.}
\end{corrige}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exo}{\'Echange de clés de Diffie-Hellman}{\null}{3}{20}

Alice et Bob souhaitent s'échanger une clé K destinée à chiffrer leurs échanges par chiffrement symétrique. Malheureusement, ils ne disposent pas de canal sécurisé pour partager leur clé. 

Voici le procédé proposé par Diffie et Hellman (\textit{cf}. figure \ref{diffie}) :

\begin{figure}
\hspace*{-7mm}
\includegraphics{311_diffie-hellman.eps}
\figcaption{\'Echange de clés selon Diffie-Hellman}
\label{diffie}
\end{figure}


\begin{questions}
\item Alice et Bob choisissent ensemble un grand nombre premier $p$, ainsi qu'un entier positif $a$ strictement inférieur à $p$. Ce choix peut être fait via le réseau et ces deux valeurs $a$ et $p$ peuvent être divulguées publiquement.

\item Alice choisit secrètement un nombre $x_1$. Elle calcule ensuite $y_1 = a^{x_1} ~\textrm{mod}~p$. Ce type de calcul est très facile à réaliser par la machine, même avec des grands nombres.

\item Bob, de son côté, choisit secrètement un nombre $x_2$ et calcule \linebreak $y_2 = a^{x_2}~\textrm{mod}~p$.

\item Alice et Bob s'échangent alors leurs valeurs de $y_1$ et $y_2$, qui peuvent là encore être interceptées.

\item Alice calcule alors $y_2^{x_1}$, ce qui donne $(a^{x_2})^{x_1} = a^{x_1x_2} ~ \textrm{mod}~p$. On convient d'appeler $K$ ce nombre et de s'en servir comme clé secrète pour échanger avec Bob.

\newpage

\item En effet, Bob, de son côté, calcule $y_1^{x_2}$, ce qui donne $(a^{x_1})^{x_2} = a^{x_1x_2}~\textrm{mod}~p$, ce qui lui permet de retrouver $K$ de son côté. Finalement, ils disposent chacun de leur côté de la clé secrète sans jamais l'avoir faite transiter sur le réseau.
\end{questions} 

\begin{Remarque}
pour simplifier les calculs suivants, on travaillera sur des petits nombres.
\end{Remarque}

\Par

Alice et Bob décident, à deux, d'un nombre premier $p = 29$ puis d'un autre nombre entier positif $a$, qui n'est pas forcément premier mais qui est strictement inférieur à $p$. Ils choisissent : $a = 3$. De plus, Alice choisit un nombre secret $x_1 = 5$ et Bob choisit un nombre secret $x_2 = 6$.

\begin{questions}
\item Calculer les valeurs des nombres $y_1$ et $y_2$ qu'ils calculent à l'aide de la relation $y = a^x ~\textrm{mod}~p$. 

\item En déduire la clé $K = a^{x_1x_2}~\textrm{mod}~p$.

\item Une propriété mathématique énonce qu'il est impossible de trouver $x_1$ (ou $x_2$ ou $a^{x_1x_2}$) connaissant $a$, $p$ et $y_1$ ($y_2$) (pour de grandes valeurs). Recenser les données collectées par Ève et indiquer si elle est en mesure de retrouver la clé $K$.

\item Quelle conséquence peut-avoir le choix d'un nombre $p = 29$ aussi petit, si la clé $K$ calculée est utilisée ensuite comme clé de chiffrement ?

\end{questions}
\end{exo}


\begin{corrige}
\begin{questions}

\item On calcule $y_1 = a^{x_1} ~\textrm{mod}~p = 3^5 ~\textrm{mod}~29 = 243 mod 29 = 11$.

Sur la console Python : \texttt{(3**5)\%29})

$y_2 = a^{x_2} ~\textrm{mod}~p = 3^6 ~\textrm{mod}~29 = 243~\textrm{mod}~29 = 4$.

\item On en déduit la clé : $K = a^{x_1x_2}~\textrm{mod}~p = 3^{5 \times 6}~\textrm{mod}~29 = 9$.

\item Ève connaît : a, p, $y_1$ et $y_2$. Ce qu'elle connaît ne lui permet pas de retrouver K car $x_1$ et $x_2$ ne peuvent être déduits de $a$, $p$ et $y_1$ ($y_2$). Cela reviendrait à résoudre le problème du logarithme discret, réputé difficile à résoudre pour des grands nombres. Toutefois, avec de telles petites valeurs, une attaque par force brute est envisageable. En pratique, pour garantir la sécurité, on utilise des valeurs très grandes.

\item Avec un nombre premier $p$ petit, l'attaque par force brute demeure possible car quel que soit le résultat de $a^{x_1x_2}$, le modulo 29 ne donne que 29 possibilités différentes.

\end{questions}
\end{corrige}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% Exo César ou Vigenère





\thumb
\AfficheCorrige
