\makeatletter
\@ifundefined{complet}
{\documentclass[10pt]{report}
\title{Python}
\newcommand{\categorie}{Architecture~}
\input{latex_entete_perso}

\begin{document} %Cours

\setcounter{chapter}{13}
% xelatex --shell-escape cours_python
}
{}
\makeatother

\IfFileExists{cryptage-cesar.png}{}{\write18{wget https://doc.infoforall.fr/activite/archi/images/chiffrement/cryptage-cesar.png}}

\IfFileExists{menu_debug_step_over.png}{}{\write18{wget https://doc.infoforall.fr/activite/python/images/thonny/menu_debug_step_over.png}}

\chapter{Chiffrement symétrique}






\section{Code de César}


\begin{multicols}{2}

\subsection{Principe de César}

Exemple ci-dessous avec une clé valant 3(pour 3 lettres de décalage)~:

\begin{figure}[H]
\centering
\includegraphics[width=8cm]{cryptage-cesar.png}
\caption{César}
\label{Cesar}
\end{figure}

Le code de César consiste tout simplement à décaler une lettre d'un certain nombre de cases vers la droite avant l'envoi. Pour décoder, il suffit de décaler de ce même nombre mais vers la gauche.



PRECONDITIONS : nous considérons ici qu'on doit fournir à nos fonctions des strings ne comportant que des MAJUSCULES, des espaces et des PONCTUATIONS autorisées. Le cours ne comporte donc pas la fonction de filtrage contrairement au TP.

\end{multicols}

\small{
\begin{minted}[linenos=true, bgcolor=lightgray, tabsize=4, gobble=0, fontfamily=courier, fontsize=\small, xleftmargin=20pt, xrightmargin=5pt]{python}
ALPHABET = ['A', 'B', 'C', 'D', 'E', ...  ... ... 'X', 'Y', 'Z']
PONCTUATION = [' ', '.', '!', '?', ',', "'", ' ']

def trouve_indice(element:str, sequence:'str|list|tuple') -> 'int|None':
    """Renvoie l'indice de element dans l'itérable sequence"""

    for i in range(len(sequence)):  # Pour chaque indice possible
        if sequence[i] == element:  # Si la case i contient l'élément voulu
            return i                # renvoie l'indice i

def decale(element:str, cle:int, sequence:list=ALPHABET):
    """Renvoie la lettre chiffrant la lettre element en décalant de cle case vers la droite"""
    indice = trouve_indice(element, sequence)
    indice_decale = (indice + cle) % len(sequence)
    return sequence[indice_decale]

def chiffrement(message, cle, sequence=ALPHABET, ponctuation=PONCTUATION, debug=False):
    """Renvoie le string en version chiffrée"""

    reponse = ''
    for caractere in message:
        if caractere in ponctuation:
            reponse = reponse + caractere
        elif caractere in sequence:
            crypte = decale(caractere, cle)
            reponse = reponse + crypte
            if debug: print(f"{caractere} devient {crypte}")
    return reponse

def dechiffrement(message, cle, sequence=ALPHABET, ponctuation=PONCTUATION):
    """Renvoie le string en version déchiffrée"""

    return chiffrement(message, -cle, sequence, ponctuation)

\end{minted}
}


\begin{multicols}{2}

\subsection{Chiffrement symétrique}

Un chiffrement est \gras{symétrique} si on utilise une même clé pour chiffrer et déchiffrer.

\subsection{Défauts de César}

1) Pour communiquer, il faut se transmettre la clé en clair.

2) Il n'y a que 25 permutations possibles, facile de les faire toutes tester par un système informatique. C'est un problème FACILE.

\end{multicols}


\section{XOR bit à bit}

\begin{multicols}{3}

\subsection{Table de vérité du et/and}

\fo{
\begin{tabular}{|*{3}{c|}}
    \hline
     a  & b & a and b \\
    \hline
     False  & False & False \\
    \hline
     False  & True & False \\
    \hline
     True  & False & False \\
    \hline
     True  & True & True \\
    \hline    
\end{tabular}
}

A RETENIR : le ET est VRAI uniquement lorsque toutes les entrées sont à VRAI.

\subsection{Table de vérité du ou/or}


\fo{
\begin{tabular}{|*{3}{c|}}
    \hline
     a  & b & a or b \\
    \hline
     False  & False & False \\
    \hline
     False  & True & True \\
    \hline
     True  & False & True \\
    \hline
     True  & True & True \\
    \hline    
\end{tabular}
}

A RETENIR : le OU est FAUX uniquement lorsque toutes les entrées sont à FAUX.


\subsection{Table de vérité du ou exclusif/xor}


\fo{
\begin{tabular}{|*{3}{c|}}
    \hline
     a  & b & a xor b \\
    \hline
     False  & False & False \\
    \hline
     False  & True & True \\
    \hline
     True  & False & True \\
    \hline
     True  & True & False \\
    \hline    
\end{tabular}
}

A RETENIR : le \fo{xor} logique n'existe pas nativement en Python, si vous voulez l'utiliser, il faudra utiliser \fo{not(a and b) and (a or b)}.



\end{multicols}


\begin{multicols}{2}

\subsection{ASCII}

ASCII permet d'associer 128 caractères à un nombre allant de 0 à 127. Exemple : \formule{'A'} correspond à 65, le passage à la ligne correspond à 10.

\subsection{Méthode du XOR}

La méthode du XOR consiste à travailler directement sur les bits du message et les bits de la clé.

On notera qu'avec \gras{une clé de X bits}, nous aurons \gras{ $2^{X}$ } possibilités de valeurs différentes. C'est un coût exponentiel, ce qui rend ce problème DIFFICILE à résoudre.

\end{multicols}


\subsection{Exemple}

\begin{itemize}

\item $m$ caractérise les bits du message qu'on veut émettre.

\item $c$ caractérise les bits de la clé de chiffrement / déchiffrement. Si la clé $c$ ne permet pas de couvrir tous les bits de $m$.

\item $mc$ caractérise les bits du message chiffré.

\item $md$ caractérise les bits du message déchiffré. Normalement, si tout se passe bien, nous devrions avoir $m = md$.

\end{itemize}

Imaginons qu'on veuille envoyer le message "BAC!" qui est encodé par l'ensemble d'octets qu'on peut obtenir en Python de cette façon :

\begin{minted}[linenos=true, bgcolor=lightgray, tabsize=4, gobble=0, fontfamily=courier, fontsize=\small, xleftmargin=20pt, xrightmargin=5pt]{python}
>>> octets = [ord(c) for c in "BAC!"]
>>> octets
[66, 65, 67, 33]

>>> bits = [f"{bin(o)[2:]:0>8}" for o in octets]
>>> bits
['01000010', '01000001', '01000011', '00100001']

>>> m = "".join(bits)
>>> m
'01000010010000010100001100100001'
\end{minted}

Tentons de chiffrer ce texte en utilisant une clé à 5 bits $11001$.

\



\fo{
\begin{tabular}{|*{5}{c}|}
    \hline
     texte & B & A & C & ! \\
    \hline
     valeur & 66 & 65 & 67 & 33 \\
    \hline
     m & 0 1 0 0 0 0 1 0 & 0 1 0 0 0 0 0 1 & 0 1 0 0 0 0 1 1 & 0 0 1 0 0 0 0 1 \\
    \hline
     c & 0 1 1 0 0 1 . . & . . . . . . . . & . . . . . . . .  & . . . . . . . .  \\
    \hline
     mc & . . . . . . . .  & . . . . . . . .  & . . . . . . . .  & . . . . . . . .  \\
    \hline 
     c & . . . . . . . .  & . . . . . . . .  & . . . . . . . .  & . . . . . . . .  \\
    \hline
     md & . . . . . . . .  & . . . . . . . .  & . . . . . . . .  & . . . . . . . .  \\
    \hline
     valeur & . & . & . & . \\
    \hline
     texte & . & . & . & . \\
    \hline
\end{tabular}
}





\input{licence}

\makeatletter
\@ifundefined{complet}
{\end{document}}
{}
\makeatother
