\documentclass[a4paper,11pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[french]{babel}
\usepackage{geometry}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{fancyhdr}

% Configuration de la page
\geometry{left=1.95cm, right=1.95cm, top=2cm, bottom=2cm}

% Configuration de minted pour le code Python
\usepackage{minted}
\usemintedstyle{vs}
\newminted{python}{
    fontsize=\footnotesize,
    breaklines,
    breakanywhere,
    numbersep=5pt,
    frame=lines,
    framesep=2mm
}

% En-tête et pied de page
\pagestyle{fancy}
\fancyhf{}
\rhead{NSI Tle - E. Le Prettre - B. Fourlegnie}
\lhead{Sécurisation des communications}
\cfoot{\thepage}


\date{}

\begin{document}

\begin{center}
\fbox{\textbf{\Large Une attaque de type man-in-the-middle (MitM) }}

\end{center}

\section*{La situation}
Alice veut établir une liaison sécurisée avec Bob en chiffrement symétrique avec la clef \texttt{kfinale}. Mais comment transmettre cette clef à Bob sans que celle-ci ne soit interceptée ?

\subsection*{Etapes du processus : Voici comment Alice et Bob vont procéder :}

La clef ne sera jamais ``transmise'', mais elle sera créée par Bob, et retrouvée par Alice.

\begin{itemize}
    \item \textbf{1er temps :} Alice génère une clef publique (notée \texttt{kpub}) et l'envoie à Bob. Cette clef peut être interceptée mais ce n'est pas grave. En même temps que la clef publique, elle génère une clef privée (notée \texttt{kpriv}). Les deux clefs sont liées, nous verrons un peu plus tard comment.
    
    \item \textbf{2ème temps :} Bob génère une clef \texttt{kfinale} qu'il garde secrète et qui servira à chiffrer les échanges avec Alice. Il chiffre cette clef qui devient \texttt{kfinaleChiffree} grâce à \texttt{kpub} qu'il a reçu d'Alice. Il envoie \texttt{kfinaleChiffree} à Alice.
    
    \item \textbf{3ème temps :} Alice déchiffre \texttt{kfinaleChiffree} avec sa clef privée et trouve \texttt{kfinale}.
    
    \texttt{kfinale} est donc maintenant connue d'Alice et de Bob qui vont pouvoir l'utiliser pour communiquer en chiffrement symétrique.
\end{itemize}

\subsection*{Lien entre clef publique et clé privée}
Notons $f(\texttt{kpub}, m)$ le message $m$ chiffré avec la clef publique, et $f(\texttt{kpriv}, m)$ le message $m$ chiffré avec la clef privée.

\texttt{kpub} et \texttt{kpriv} obéissent à :
\[ f(kpriv, f(kpub, m)) = f(kpub, f(kpriv, m)) = m \]

En d'autres termes, si Bob chiffre avec la clef publique, Alice saura déchiffrer avec sa clef privée connue d'elle seule. Le système exige aussi que la connaissance de la clef publique ne permette pas de déchiffrer le message envoyé par Bob. C'est le cas quand on chiffre avec des fonctions de hachage, mais ici, pour comprendre le principe, nous allons simplifier et utiliser un chiffrement proche de celui de Vigenère.

Nous admettrons, pour l'exemple, que l'on ne peut pas décrypter le message de Bob avec la clef publique, ni découvrir la clef privée à partir de la clef publique.

\section{Création de la clef publique}


Dans notre exemple, on va utiliser un code proche du codage de Vigenère (Code César amélioré) :
\begin{itemize}
    \item On génère 10 nombres aléatoire entre 0 et 36 qui seront les décalages à appliquer.
    \item On convertit ces nombres en hexa de longueur 2.
    \item On concatène pour créer une clef de longueur 20 (mais elle serait très simple à casser !).
\end{itemize}

Nous allons utiliser un alphabet de 36 lettres : [0-9] et [A-Z].

Vous pourrez utiliser la fonction suivante qui convertit un entier (entre 0 et 255) en une chaine hexadécimale de 2 chiffres.
\newpage
\subsubsection*{Imports \& utilitaires}
\begin{pythoncode}
from random import randint, seed
ALPHA = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'

def d2H(n: int) -> str:
    """
    convertit un nombre décimal compris entre 0 et 255 en un hexadécimal 
    à 2 chiffres
    :param n: entier à convertir en base 16
    :return: une chaine de caractère représentant le nombre en base 16 
    sur deux caractères
    >>> d2H(10)
    '0a'
    >>> d2H(100)
    '64'
    """
    h = hex(n)[2:]
    if len(h) < 2:
        h = "0" + h
    return h

# Vérifications demandées
assert d2H(10) == '0a'
assert d2H(100) == '64'
\end{pythoncode}

\subsubsection*{1.1 : création de clé publique — À COMPLÉTER}
Ajouter et compléter la fonction \texttt{creCle()} :
\begin{itemize}
    \item On génère 10 nombres aléatoires entre 0 et 255.
    \item On convertit ces nombres en hexadécimal de longueur 2, en utilisant la fonction \texttt{d2H}.
    \item On concatène pour créer une clef de longueur 20. Les lettres devront être converties en majuscules.
\end{itemize}

Remarque : Cette clef serait très simple à casser, mais nous étudions ici seulement le principe.


\begin{pythoncode}
from random import randint

def creClef() -> str:
    """ Version 1 : renvoie une seule clé publique (20 caractères hex en MAJ) 
    Crée un clef de chiffrement composée de 20 caractères 
    parmi ceux-ci : 0, 1, 2, ..., 9, A, B, C, D, E, F
    :return: renvoie 20 caractères de 0, 1, 2, ..., 9, A, B, C, D, E, F
    Par exemple : 'C5D71484F8CF9BF4B76F'
    C5 représente 197, D7 représente 215 etc...
    """
    kpub=""
    pass # ← compléter ici
	return kpub.upper() # majuscule uniquement
	
print(creClef())
\end{pythoncode}




\subsubsection*{1.2. Vérification avec seed()}
Pour tester notre fonction, comment obtenir des nombres ``aléatoires'' toujours identiques ? En fait \texttt{random} crée des nombres ``pseudos-aléatoires''. Si on lui donne une initialisation $a$ avec \texttt{seed(a)}, les nombres générés seront toujours identiques.

Par défaut l'initialisation se fait avec la date actuelle, qui change tout le temps.
On utilise une initialisation, par exemple \texttt{seed(0)}.

\begin{pythoncode}
from random import seed
for i in range(5):
    seed(0)
    print([randint(0, 255) for i in range(10)])
\end{pythoncode}

Nous aurions pu en choisir une autre, par exemple \texttt{seed(42)}.

\begin{pythoncode}
from random import seed
for i in range(5):
    seed(42)
    print([randint(0, 255) for i in range(10)])
\end{pythoncode}

Que remarquez vous ? Nous pouvons donc tester notre fonction !

Ajouter :
\begin{pythoncode}
from random import seed
seed(0)
assert creClef() == 'C5D71484F8CF9BF4B76F'
\end{pythoncode}

\section{Création de (clé publique, clé privée)}
Il faut aussi créer une clef privée, liée à la clef publique. Dans notre exemple, le processus de création de la clef est très simple, et la conversion en hexadécimal est totalement factice. Il ne s'agit, comme dans le chiffrement de Vigenère, que d'appliquer un décalage variable des lettres. Pour les 10 premières lettres, le décalage est codé dans la clef, pour la 11ème on reprend le décalage de la 1ere, et ainsi de suite.... c'est ce qu'avait imaginé Vigenère.

Comment faire ?
Pour créer une clef qui permette de respecter :
\[ f(k_{priv}, f(k_{pub}, m)) = f(k_{pub}, f(k_{priv}, m)) = m \]
il suffit de créer les décalages qui compensent.

Rappelons que nous allons utiliser un alphabet de 36 lettres :
\[ \text{ALPHA = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'} \]

Par exemple, si on décale vers la droite de 12 $(\%36)$, il suffit de décaler encore de $\%36 - 12 = 24$, en bouclant au début de l'alphabet, pour ``retomber'' sur le même caractère.

On pourrait donc choisir un décalage $$d_{Priv} = 36 - d_{Pub} \% 36$$.

Pour ``compliquer'', on peut choisir également comme décalage $$d_{Priv} = 36 - d_{Pub} \% 36 + \text{randint}(1, 6) * 36$$. En effet, cela ne changera rien d'ajouter un décalage d'un nombre entier de fois 36. (On se limite à \texttt{randint(1,6)} pour que le nombre soit possible à coder en hexadécimal sur deux caractères).

Voilà comment procéder pour créer la clef privée :
\begin{verbatim}
Pour chaque décalage d_Pub de la clef publique :
    dPriv = 36 - dPub % 36 + randint(1, 6) * 36
    coder dPriv en hexa2
    concaténer les hexa2(dPriv) en une chaine
\end{verbatim}

\textbf{Ajouter et compléter la fonction \texttt{creClef()}} \\
Attention, elle doit renvoyer un tuple (clef publique, clef privée).

\begin{pythoncode}
def creClef() -> tuple:
    """
    creClef doit renvoyer un tuple avec les 2 clefs: la publique et la privée
    Exemple renvoyé:
    ('47904730804B9E3225A9', '91D82584A08DCAEE6BBF')
    """
    pass # ← compléter ici

print(creClef())
\end{pythoncode}

\section{Lecture des décalages}
Prenons un exemple $$k_{pub} = \text{'48E52E29A3FA379A953F'}$$.

Le premier décalage est codé par les deux premiers caractères 48, qui en décimal et modulo 36 sera :
\begin{pythoncode}
int('48', 16) % 36 # Vérifier que cela fait 0
\end{pythoncode}

Le second est E5 :
\begin{pythoncode}
int('E5', 16) % 36 # Vérifier que cela fait 13
\end{pythoncode}

Si la clef privé est $k_{priv} = \text{'D883116D359FEC5CED375'}$, les deux premiers décalages sont :
\begin{pythoncode}
print('D8 -> d = ',int('D8',16) % 36) # Vérifier que cela fait 0
print('83 -> d = ',int('83',16) % 36) # Vérifier que cela fait 23
\end{pythoncode}

Dans l'exemple ci-dessus, la somme des décalages :
\begin{itemize}
    \item pour le 1er caractère vaut : $0 + 0 = 0$
    \item pour le 2ème caractère vaut : $13 + 23 = 36$
\end{itemize}
On pourrait ainsi vérifier que pour n'importe quel caractère, la somme des décalages est égale à 0 ou à 36, ce qui, modulo 36, fait toujours 0.


L'application de $k_{priv}$ compensera donc l'application de $k_{pub}$, ce qui assure que :

\[ f(kpriv, f(kpub, m)) = f(kpub, f(kpriv, m)) = m \]



Pour bien comprendre, voici comment retrouver les décalages en lisant les clés :

\begin{pythoncode}
# le code ci-dessous vous montre comment retrouver les décalages en lisant les clefs
# la fonction decal(clef, i) convertit la tranche clef[i:i+2] en décimal
(kpub, kpriv) = creClef()
print('clef publique :', kpub, '\t clef privée :', kpriv)

def decimal_tranche_i(clef, i):
    return int(clef[i:i + 2], 16)

for i in range(0, 20, 2):
    dPub = kpub[i:i + 2]
    dPriv = kpriv[i:i + 2]
    dPub_dec = decimal_tranche_i(kpub, i)
    dPriv_dec = decimal_tranche_i(kpriv, i)
    print(dPub, dPriv, dPub_dec, dPriv_dec)
    assert (dPub_dec + dPriv_dec) % 36 == 0
\end{pythoncode}

\section{Clé symétrique de Bob}
Ajouter et compléter la fonction qui va être utilisée pour créer une clef de chiffrement symétrique $k_{finale}$.

\begin{pythoncode}
def creekfinale() -> str:
    """
    crée un mot de 20 lettres dans ALPHA (chiffrement symétrique)
    :return: par exemple 'KFIBCB2GU458925YPXHX'
    """
    pass # ← compléter

print(creekfinale())

seed(0)
assert creekfinale() == 'OQ2GWVPJUMDW8I86GY9J'
\end{pythoncode}

Bob doit maintenant chiffrer cette clef finale avec la clef publique d’Alice.

\section{Calcul des décalages}
Il nous faut donc une fonction $f(k, m)$ qui chiffre un message $m$ avec une clef $k$.
Nous aurons besoin de la fonction ci-dessous à ajouter au fichier :

\begin{pythoncode}
def decal(clef: str) -> list:
    """
    :param clef: chaîne de 20 caractères parmi 0, 1, 2, ..., 9, A, B, C, D, E, F
    Par exemple : 'C5D71484F8CF9BF4B76F'
    :return: liste de 10 entiers qui correspondent aux décalages en décimal à 
    appliquer dans le chiffrement modulo 36
    >>> decal('C5D71484F8CF9BF4B76F')
    [17, 35, 20, 24, 32, 27, 11, 28, 3, 3]
    En effet C5 correspond à 197 en décimal, et 197 % 36 = 17
    """
    return [int(clef[i:i+2], 16) % 36 for i in range(0, len(clef), 2)]
\end{pythoncode}

\section{Fonction f(k, m) (chiffrement asymétrique)}

Cette fonction chiffre le message $m$  par le principe du chiffrement de Vigenère avec la clef $k$.
Elle est cependant très basique : elle effectue un décalage des lettres conforme à la clef. C'est un décodage de Vigenère dont la clef serait publique donc trivialement cassée. (voir section 8)



\textbf{Ajouter et compléter la fonction avec :}
\begin{verbatim}
On définit ALPHA : chaîne des caractères possibles utilisés.
On convertit la clef en une liste L de décalages avec la fonction \texttt{decal}.
On initialise m_chiffre = ""
pour chaque ième caractère de m :
  déterminer son rang dans ALPHA : rang = ALPHA.index(ième caractère de m)
  déterminer decaler_de le décalage à appliquer à rang : decaler_de = L[i % len(L)]
  déterminer idx  l'indice dans ALPHA du caractère chiffré : idx = (rang + decaler_de) % 36
  ajouter à m_chiffre le caractère chiffré correspondant à idx
renvoyer m_chiffre
\end{verbatim}
\newpage
\begin{pythoncode}
# Bob chiffre la clef finale
def f(k: str, m: str) -> str:
    """
    Cette fonction chiffre le message m par le principe du chiffrement de 
    Vigenère avec la clef k.
    :param k: clef qui sert au chiffrement (on boucle la clef sur la longueur de m)
    :param m: message à chiffrer
    :return: le message chiffré
    >>> f("00000000000000000000", "CLE2CHIFFRER")
    'CLE2CHIFFRER'
    >>> f("C5D71484F8CF9BF4B76F", "CLE2CHIFFRER")
    'TKYQ88T7IUVQ'
    """
    pass # ← compléter ici

assert f("00000000000000000000", "CLE2CHIFFRER") == 'CLE2CHIFFRER'
assert f("C5D71484F8CF9BF4B76F", "CLE2CHIFFRER") == 'TKYQ88T7IUVQ'
\end{pythoncode}

\section{Scénario Alice $\leftrightarrow$ Bob}
\textbf{Copier et compléter les ... du code python :}
Nous avons maintenant tout ce qu'il nous faut, l'échange peut avoir lieu.
Nous allons reprendre nos 3 temps expliqués dans les étapes du processus au début de ce TP.


\begin{itemize}
\item \textbf{1er temps :}
\begin{pythoncode}
# Création des clef publique et privée
(kpub,kpriv) = creClef()
print('Alice crée une clef publique :', kpub)
print('clef privée associée :', kpriv)
\end{pythoncode}

\item \textbf{2ème temps :}
\begin{pythoncode}
# Création de la clef finale par Bob puis chiffrement
kfinale = ...
kfinaleChiffree = ...
\end{pythoncode}

\item \textbf{3ème temps :}
\begin{pythoncode}
# Réception par Alice de la clef finale  chiffrée pour la  déchiffrer
print("Alice obtient :", ...) 
assert ... == kfinale 
\end{pythoncode}



\item \textbf{Bonus :}
\begin{pythoncode}
# Vérification que la clef déchiffrée par Alice est bien la clef générée par Bob
assert ... == kfinale 
\end{pythoncode}
\end{itemize}
Le tour est joué ! Alice et Bob connaissent la clef $k_{finale}$, il vont pouvoir communiquer en utilisant un chiffrement symétrique !

\section{Chiffrement symétrique}
Maintenant Alice et Bob vont communiquer avec cette clef échangée $k_{finale}$.
Ajouter les scripts suivants. Ils vont utiliser le chiffrement symétrique de Vigenère du TP précédent, dont on donne ci-dessous un script :
\newpage
\begin{pythoncode}
def chiffrement_Vigenere(k: str, m: str, sens: int) -> str:
    """
    Chiffre ou déchiffre le message m avec la clef k
    :param k: la clef de chiffrement
    :param m:  le texte à chiffrer
    :param sens: sens = 1 pour le chiffrage et sens = -1 pour le déchiffrage
    :return: la fonction renvoie le texte chiffré ou déchiffré suivant le sens choisi: type str.
    Par exemple :
    >>> chiffrement_Vigenere('bizare', 'abominable', 1)
    'ucgfskucdx'
    >>> chiffrement_Vigenere('bizare','ucgfskucdx', -1)
    'abominable'
    """
    m_chiffre = ""
    for i in range(len(m)):
        code = ord(m[i])
        decal = sens * ord(k[i % len(k)])
        if 65 <= code <= 90:
            code = ((code + decal) - 65) % 26 + 65
        elif 97 <= code <= 122:
            code = ((code + decal) - 97) % 26 + 97
        elif 32 <= code <= 64:
            code = ((code + decal) - 32) % 33 + 32
        m_chiffre += chr(code)
    return m_chiffre
\end{pythoncode}

Alice veut demander à Bob son mot de passe (qui est ``bRa1cAPStp3'').
Bob chiffre donc son mot de passe avec $k_{finale}$ qu'ils connaissent maintenant tous les deux, puis l'envoie :

\begin{pythoncode}
mdp_chiffre = chiffrement_Vigenere(kfinale,'bRa1cAPStp3',1)
print("Bob envoie 'bRa1cAPStp3' chiffré avec kfinale -> ", mdp_chiffre)
\end{pythoncode}

Alice déchiffre le mdp reçu avec $k_{finale}$ :
\begin{pythoncode}
mdp_clair = chiffrement_Vigenere(kfinale,mdp_chiffre,-1)
print('Alice déchiffre avec kfinale ->', mdp_clair)
\end{pythoncode}

Mission réussie !

\section{Attaque Man-In-The-Middle  : MITM}
Alice et Bob sont habitués à procéder comme nous venons de le voir. Bob va donc créer $k_{finale}$ qui va leur servir pour communiquer en chiffrement symétrique. Mais Jimmy va un peu changer les données du problème. Pour communiquer, Alice et Bob envoient des paquets qui transitent sur de nombreux routeurs. L'un d'eux appartient à Jimmy.... Dans ce qui suit, vous êtes Jimmy.
\textbf{Copier et compléter les ... du code python :}

\begin{enumerate}
    \item Tout commence comme d'habitude : Alice crée une clef publique et une clef privée :
    \begin{pythoncode}
# créez les clef publiques et privées d'Alice :
(kpubAlice, kprivAlice) = creClef()
print("clé publique de Alice :", ...)
print("clé privée de Alice :", ...)
    \end{pythoncode}

    \item Alice envoie à Bob la clé publique. Du moins, c'est ce qu'elle pense. Elle ignore votre présence.
    
    \item Vous intervenez ! Vous interceptez l'envoi. Vous n'allez pas envoyer cette clef à Bob mais une autre : la vôtre ! Vous avez une clef publique et une clef privée. Vous envoyez votre clef publique à Bob, qui pensera qu'il s'agit de la clef publique d'Alice.
    \begin{pythoncode}
# créez votre clef publique et votre clef privée associée
(kpubJimmy, kprivJimmy) = creClef()

print('clé publique de Jimmy :', ...)
print('clé privée de Jimmy :', ...)
    \end{pythoncode}

    \item Bob ne se doute de rien !
    Bob chiffre $k_{finale}$ (la clé finale) avec cette clé publique qu'il vient de recevoir, et envoie cette clé chiffrée à Alice (où du moins, c'est ce qu'il pense. Mais vous êtes là...)
    
    La clé finale crée par Bob est : \texttt{'0VLFK4CEF9YS55KWV6JZ'}
    
   
    \begin{pythoncode}
kfinale = "0VLFK4CEF9YS55KWV6JZ"
# codez cette clef avec la clé publique de Jimmy (Bob croit qu'il s'agit de celle de Alice)
kfinaleChiffreBob = ...
print('Bob envoie la clef finale chiffrée avec la clé publique de Jimmy :', kfinaleChiffreBob)
    \end{pythoncode}

    \item Vous interceptez cette clef !
    Vous déchiffrez cette clef interceptée grâce à votre clef privée :
    \begin{pythoncode}
kfinale_decryptee =  ...
print(kfinale_decryptee)
    \end{pythoncode}
    Vous obtenez donc $k_{finale\_decryptee}$.
    Sans surprise, vous voyez que vous détenez bien la clé finale.
    En effet $k_{finale\_decryptee}$ que vous avez reconstituée est bien égale à $k_{finale}$ créée par Bob.

    \item Vous faites comme si vous étiez Bob !
    Vous allez maintenant chiffrer $k_{finale\_decryptee}$ avec la clé publique d' Alice, et lui envoyer.
    \begin{pythoncode}
# Créez la clé finale chiffrée avec la clé d'Alice :
kfinaleChiffreAlice = ...
print("Jimmy envoie la clé privée de Bob chiffrée avec la vraie clé publique d'Alice :", kfinaleChiffreAlice)
    \end{pythoncode}

    \item Alice reçoit cette clef et la déchiffre avec sa clé privée.
    Elle obtient $k_{finale}$ la bonne clé créée par Bob, et ils vont l'utiliser pour communiquer.
    \begin{pythoncode}
print(f(kprivAlice, kfinaleChiffreAlice))
    \end{pythoncode}

    \item Tous les échanges ultérieurs seront interceptés et décryptés par Jimmy !
    Ni Alice ni Bob ne se doute que Jimmy bad boy connait aussi la clé $k_{finale}$.
\end{enumerate}

\textbf{Bravo, vous avez réussi à comprendre une attaque par l'homme du milieu.}


\section{Attaque sur la clef publique}


A suivre ...

\end{document}

Le chiffrement asymétrique utilisé n'est absolument pas sécurisé. Voici la faille :

\begin{itemize}
\item La clé publique nous indique les décalage à faire pour chiffrer : decalage 1.
\item La clef privée nous indique les décalage à faire pour déchiffrer : : decalage 2
\end{itemize}

\begin{center}
decalage1 + decalage2 = 36
\end{center}

Voici la démarche  à suivre :

\begin{itemize}
\item Récupérer la clé publique
\item Avec la fonction decal, retrouver les décalages
\item Contruire une liste L telle que pour chaque decalage (decalage1 + decalage2 = 36)
\item  Avec la fonction d2H, retrouver une clef privée.
\end{itemize}


\begin{pythoncode}
# créez les clef publiques et privées d'Alice :
(kpubAlice, kprivAlice) = creClef()
print("clé publique de Alice :", ...)
print("clé privée de Alice :", ...)
\end{pythoncode}


\end{document}
