#!/usr/bin/env python
# coding: utf-8

# ![En tête general](img/En_tete_general.png)
# 
# 
# *(C) Copyright Franck CHEVRIER 2019-2020 http://www.python-lycee.com/*
# 
# <span style="color: #9317B4"> Pour exécuter une saisie Python, sélectionner la cellule et valider avec </span><span style="color: #B317B4"><strong>SHIFT+Entrée</strong></span>.
# 

# 
# # <span style="color:#6C3483">chiffrement affine </span>
# 
# ### <span style="color:#6C3483">Activité sur le chiffrement n°1</span>
# ##### <span style="color:#C18FDE" id="1">(prérecquis: congruences, théorème de Bézout, théorème de Gauss, équations diophantiennes)</span>
# 
# ![Illustration_detectives](img/Chiffrement_affine.png)

# ## <span style="color:#8E44AD">1. Coder et décoder un message</span>

# Archibald et Balthazar, deux détectives maladroits, souhaitent coder les messages qu'ils doivent échanger afin qu'ils ne soient pas déchiffrables s'ils tombaient en de mauvaises mains.<br>
# <br>
# Ils commencent par associer chaque lettre de l'alphabet à un nombre entier comme l'indique le tableau ci-dessous.
# <br>
# 
# | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z |  
# |:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|
# | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12| 13| 14| 15| 16| 17| 18| 19| 20| 21| 22| 23| 24| 25|
# 
# Ils décident ensuite de coder leurs messages avec le <strong>chiffrement affine</strong> suivant :<br>
# 
# <p style='background-color:#F5EEF8;' >
# Si la lettre à coder correspond à $x$ (avec $0 \leqslant x \leqslant 25$), alors on calcule le reste de la division euclidienne de $11x+8$ par $26$, noté $y$.<br>
# Comme $0 \leqslant y \leqslant 25$ , on peut associer une lettre à cette valeur $y$ : Cette lettre est le codage de la lettre initiale.<br>
# Le couple $(11;8)$ est la <strong>clé de chiffrement</strong>.
# </p>
# 

# __1.1. Archibald souhaite envoyer le message suivant à Balthazar : "C EST FACILE CE CODE". Quel message va-t-il lui envoyer?__
# 

# __1.2. On donne ci-dessous la fonction Python <mark>codage_affine</mark>, qui permet d'effectuer un chiffrement affine.__<br>
# $\;\;\;\;\;\;$__Effectuer un appel à cette fonction permettant de vérifier la réponse à la question précédente.__

# In[ ]:


#Mise en mémoire de l'alphabet
Alphabet="ABCDEFGHIJKLMNOPQRSTUVWXYZ"

def codage_affine(a,b,message):
    """
    Fonction effectuant le codage affine du message
    avec la clé de chiffrement (a,b)
    """
    code=""                                 
    for caractere in message:             # pour chaque caractère du message
        if caractere in Alphabet:         # si ce caractère est dans l'alphabet, alors:
            x = Alphabet.index(caractere) #       on récupère l'entier correspondant à cette lettre
            y = (a*x+b)%26                #       on calcule y
            code += Alphabet[y]           #       on complète le code avec la lettre correspondant à y
        else:                             # sinon: 
            code += " "                   #       on complète le code avec un espace
    return code                           # on renvoie le message codé
        


# In[ ]:


# Effectuer ici l'appel à la fonction codage_affine

 


# __1.3. Archibald reçoit la réponse de Balthazar: "DA VA EGKRNAVPY RIY".__<br>
# $\;\;\;\;\;\;$__Il se rend alors compte qu'ils n'ont pas convenu de méthode pour le déchiffrement... et se demande comment il va décoder ce message.__<br>
# $\;\;\;\;\;\;$__On cherche donc à déterminer $x$ connaissant $y$.__

# $\;\;\;$__a. Démontrer que s'il existe $u$ tel que  $0 \leqslant u \leqslant 25$  et  $11u \equiv 1[26]$ , alors $x \equiv u(y-8)[26]$.__<br>
# $\;\;\;\;\;\;$Ainsi, une telle valeur de $u$ permettrait de décoder le message.
# 
# 

# $\;\;\;$__b. L'équation $11u+26v=1$ d'inconnues entières $u$ et $v$ a-t-elle des solutions ?__<br>
# $\;\;\;\;\;\;$__Si oui, déterminer une de ces solutions.__
# 

# $\;\;\;$__c. En déduire que $x \equiv 19y+4[26]$, puis déchiffrer le message que Balthazar a envoyé à Archibald__<br>
# $\;\;\;\;\;\;$Ainsi, le couple $(19;4)$ est la clé de déchiffrement.<br>
# 
# 

# $\;\;\;$__d. A l'aide d'un appel à la fonction Python <mark>codage_affine</mark>, vérifier le décodage du message, réalisé dans la question précédente.__

# In[ ]:


# Effectuer ici l'appel à la fonction codage_affine



# ## <span style="color:#8E44AD">2. Choisir une clé de chiffrement</span>

# __2.1. Rassurés de voir que leur méthode fonctionne, Archibald et Balthazar décident à présent d'utiliser la clé de chiffrement $(4;3)$.__<br>
# $\;\;\;\;\;\;$__Archibald souhaite envoyer le message "CA NE MARCHE PAS" à Balthazar.__<br>
# $\;\;\;\;\;\;$__a. A l'aide de la fonction Python <mark>codage_affine</mark>, déterminer le message qu'Archibald va envoyer.__
# 

# In[ ]:


# Effectuer ici l'appel à la fonction codage_affine



# $\;\;\;\;\;\;$__b. Balthazar parviendra-t-il facilement à décoder ce message ? Pourquoi ?__<br>
# 

# __2.2. 	Démontrer que si $(a_1;b_1)$ et $(a_2;b_2)$ sont tels que $a_1 \equiv a_2[26]$ et $b_1 \equiv b_2[26]$ , alors les codes obtenus avec ces deux clés sont les mêmes.__<br>
# $\;\;\;\;\;\;$On peut donc choisir des entiers naturels $a$ et $b$ tels que $1 \leqslant a \leqslant 25$ et $0 \leqslant b \leqslant 25$.
# 

# __2.3. On se place dans le cas d’une clé de chiffrement $(a;b)$ vérifiant $1 \leqslant a \leqslant 25$ et $0 \leqslant b \leqslant 25$.__<br>
# $\;\;\;\;\;\;$__On note $x$ et $x'$ deux entiers compris entre $0$ et $25$, et on note $y$ et $y'$ leurs codes avec la clé $(a;b)$.__<br>
# <br>
# $\;\;\;\;\;\;$__a. Démontrer que si $y=y'$ alors $a(x-x') \equiv 0[26]$.__
# 
# $\;\;\;\;\;\;$__b. Justifier que si on choisit $a$ premier avec $26$, alors le décodage de tout message est unique.__
# 

# $\;\;\;\;\;\;$Pour la suite, on admet que la réciproque est vraie :<br>
# $\;\;\;\;\;\;$Le décodage de n'importe quel message se fait de façon unique si et seulement si $a$ est premier avec $26$.<br>
# 
# 

# __2.4. On dit qu'une clé de chiffrement est valide s'il y a unicité du décodage de n'importe quel message.__<br>
# $\;\;\;\;\;\;$__Combien de clés de chiffrements peut-on créer au maximum ?__<br>
# $\;\;\;\;\;\;$__Que peut-on en conclure concernant la sûreté de la technique de chiffrement affine ?__

# __2.5. Dans cette question, on souhaite automatiser la recherche de la clé de déchiffrement associée à une clé de chiffrement initiale valide $(a;b)$.__<br>
# $\;\;\;\;\;$__(c'est à dire telle que $a$ est premier avec $26$).__
# 
# $\;\;\;\;\;\;$__a. On suppose qu'on a déterminé $u$ qui vérifie $1 \leqslant u \leqslant 25$ et $au \equiv 1[26]$.__<br>
# $\;\;\;\;\;\;\;\;\;$__On pose alors $v$ le reste de la division euclidienne de $-bu$ par $26$.__<br>
# $\;\;\;\;\;\;\;\;\;$__Vérifier que $(u;v)$ est la clé de déchiffrement cherchée.__
# 

# $\;\;\;\;\;\;$__b. Ecrire une fonction Python <mark>inverse_cle</mark> qui reçoit une clé de chiffrement $(a;b)$ et renvoie la clé de déchiffrement associée $(u;v)$.__<br>
# $\;\;\;\;\;\;\;\;\;$On pourra, à l'aide d'une boucle, tester les candidats pour $u$ en partant de $1$ afin d'obtenir une valeur vérifiant 
# $au \equiv 1[26]$.
# 

# In[ ]:


# Ecrire ici la fonction inverse_cle



# $\;\;\;\;\;\;$__c. Convenir avec une autre personne d'une clé de chiffrage valide.__<br>
# $\;\;\;\;\;\;\;\;\;$__Chacun code alors un message à l'aide de la fonction Python <mark>codage_affine</mark> en utilisant cette clé, et le donne à l'autre.__<br>
# $\;\;\;\;\;\;\;\;\;$__Enfin, chacun décode le message reçu (on peut à nouveau utiliser la fonction Python <mark>codage_affine</mark>).__

# In[ ]:


#Utiliser cette zone pour coder le message à envoyer



# In[ ]:


#Utiliser cette zone pour déterminer la clé de déchiffrement



# In[ ]:


#Utiliser cette zone pour décoder le message reçu



# *(C) Copyright Franck CHEVRIER 2019-2020 http://www.python-lycee.com/*
#