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

# ![En tête general](https://raw.githubusercontent.com/PythonLycee/PyLyc/master/img/En_tete_general.png)
# 
# 
# <i>© Copyright Franck CHEVRIER 2019-2022 https://www.python-lycee.com.</i><br>
# <i>Les activités partagées sur <a href="https://capytale2.ac-paris.fr/web/accueil"><strong>Capytale</strong></a> sont sous licence <a href="https://creativecommons.org/licenses/by-sa/3.0/fr/">Creative Commons</a>.</i>
# 
# <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 RSA
# 
# ### <span style="color:#6C3483">Activité sur le chiffrement n°3</span>
# ##### <span style="color:#C18FDE">(prérequis: congruences, équations diophantiennes, nombres premiers, théorème de Gauss, petit théorème de Fermat)</span>
# 
# ![Illustration_detectives](https://raw.githubusercontent.com/PythonLycee/PyLyc/master/img/Chiffrement_RSA.png)

# Cette activité propose, sous forme simplifiée, d'étudier le principe du chiffrement RSA.<br>
# 
# ### <span style="color:#8E44AD">Sommaire</span>
# 
# <span style="color:#8E44AD">1.</span> <a href="#1">Principe du chiffrement RSA</a><br>
# <span style="color:#8E44AD">2.</span> <a href="#2">Échanges sécurisés de message</a><br>
# <span style="color:#8E44AD">3.</span> <a href="#3">Principe d'authentification</a><br>
# <span style="color:#8E44AD">4.</span> <a href="#4">Compléments arithmétiques</a><br>

# ## <span style="color:#8E44AD" id="1">1. Principe du chiffrement RSA</span>

# Archibald, chef d'une agence de détectives, souhaite que tous ses associés cryptent les messages qu'ils lui envoient. Il souhaite donc leur donner à tous la même méthode de chiffrement, mais -méfiant- souhaite aussi s'asssurer d'être le seul à pouvoir décoder les messages qui lui parviennent, au cas où un espion intercepterait un de ces messages.<br><br>
# Dans les activités de chiffrement précédentes, la connaissance de la clé de chiffrement permettait directement de déterminer la clé de déchiffrement, ce qui ne convient pas à Archibald.<br><br>
# Pour réaliser son chiffrement, Archibald :
# <ul>
#     <li>fixe deux nombres premiers $p$ et $q$ distincts ;</li>
#     <li>pose $n=pq$ et $m=(p-1)(q-1)$ ;</li>
#     <li>choisit un entier $c$ premier avec $m$ tel que $1<c<m$.
# </ul>

# <BLOCKQUOTE style='background-color:#96DAF1;'>
#     <strong>Dans cette partie, on pose $p=11$ ; $q=23$ et $c=9$.</strong>
# </BLOCKQUOTE>
# 
# __1.1. Vérifier que $p$ ; $q$ et $c$ vérifient bien les contraintes annoncées, et donner les valeurs de $n$ et $m$.__
# 
# 

# Archibald fournit le couple $(n;c)$ à ses associés, et garde les valeurs $p$ et $q$ secrètes.<br><br>
# Balthazar, un associé d'Archibald, souhaite coder un message à l'aide du couple $(n;c)$, appelé __clé publique__.<br>
# (pour simplifier, on suppose que le message est exclusivement composé d'espaces et de lettres majuscules, sans accents ni caractères spéciaux)<br>
# Pour cela, il commence par associer à chaque caractère de son message un entier $x$ compris entre $0$ et $26$ à l'aide du tableau de correspondance ci-dessous.<br>
# Ensuite, il associe à la valeur $x$ obtenue la valeur $y$ telle que $0 \leq y \leq n-1$ et $y \equiv x^{\;c} \;[n]$.<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 | (espace) |
# |:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:--|:---------|
# | 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| 26       |
# 
# <br>
# Exemple :<br>
# Avec les valeurs choisies précédemment, la lettre <strong>I</strong> correspond à la valeur $x=8$.<br>
# Comme $x^9=8^9=134217728 \equiv 216 [253]$, cette lettre se code avec la valeur $216$.
# 

# __1.2. Balthazar souhaite envoyer le message "BINGO" à Archibald. Quelle succession de nombres va-t-il lui envoyer ?__<br>
# $\;\;\;\;\;$On pourra utiliser une (des) zone(s) de saisie Python pour effectuer des calculs utiles.

# In[ ]:


#Utiliser si nécessaire cette zone pour les calculs en Python



# __1.3. On donne les fonctions Python <mark>chiffrage</mark> et <mark>chiffrement_RSA</mark> ci-dessous.__<br>
# $\quad\;\;$__À l'aide d'appels à ces fonctions, vérifier le résultat de la question 1.2.__

# In[ ]:


#Mise en mémoire de l'alphabet (+espace)
Alphabet="ABCDEFGHIJKLMNOPQRSTUVWXYZ "

def chiffrage(message):
    """
    Fonction qui renvoie la liste des valeurs correspondantes aux caractères du message
    (A->0 , B->1 , ...)
    """
    return [ Alphabet.index(caractere) for caractere in message ]
    
    
def chiffrement_RSA(n,c,liste_nombres):
    """
    Fonction effectuant le codage RSA de la liste de valeurs avec la clé publique (n,c)
    """
    code = []                                 
    for x in liste_nombres:             # pour chaque valeur x de la liste donnée
        y = x**c %n                     #       on calcule y correspondant à x
        code.append(y)                  #       on complète la liste de valeurs avec y
    return code
        


# In[ ]:


#Effectuer ici les appels aux fonctions chiffrage et chiffrement_RSA



# __1.4.__ Dans cette question, on souhaite effectuer le décodage du message à l'aide du triplet $(p;q;c)$, appelé __clé privée__.<br>
# $\;\;\;\;\;$__a. Sans chercher à le déterminer, démontrer qu'il existe un unique entier $d$ tel que $1 \leq d < m$ et $cd \equiv 1 \;[m]$.__<br>
# $\;\;\;\;\;$__b. Déterminer cette valeur $d$ (on pourra commencer par appliquer l'algorithme d'Euclide).__<br>
# $\;\;\;\;\;$__c. À l'aide de saisies en Python, calculer $x^{cd}$ modulo $n$ pour différentes valeurs entières positives de $x$. Que constate-t-on ?__<br>
# 

# In[ ]:


#Effectuer ici les calculs



# $\;\;\;\;\;$__d. On admet pour l'instant\* que l'observation de la question 1.4.b. est correcte pour tout entier positif $x$, et on rappelle que $y$ vérifie $y \equiv x^{\;c} \;[n]$.<br>
# $\quad\quad$<span style="font-size:12px">(*La démonstration mathématique de ce résultat sera détaillé dans <a href="#4">la partie 4</a>)</span><br>
# $\quad\quad$Exprimer $x$ en fonction de $y$ modulo $n$.__<br>
# 
# $\;\;\;\;\;$__e. Effectuer le décodage des nombres de la question 1.2 et vérifier qu'on retrouve bien le message "BINGO".__<br>
# $\;\;\;\;\;\;\;\;$On pourra utiliser une (des) zone(s) de saisie Python pour effectuer des calculs utiles.

# In[ ]:


#Utiliser si nécessaire cette zone pour les calculs en Python



# __1.5. On fournit ci-dessous la fonction Python <mark>inv</mark> qui reçoit en argument <mark>m</mark> et <mark>c</mark>, et renvoie <mark>d</mark>.__<br>
# $\;\;\;\;\;\;$(NB : Cette fonction est basée sur une recherche de coefficients de Bézout ; elle est étudiée dans l'activité <a href="https://notebook.basthon.fr/?from=https://raw.githubusercontent.com/PythonLycee/PyLyc/master/PGCD_Euclide_Bezout_vd.ipynb">PGCD / Euclide / Bézout</a>)<br>
# $\;\;\;\;\;\;$__Vérifier que la fonction <mark>inv</mark> permet de retrouver la réponse à la question 1.5.a.__

# In[ ]:


import numpy as np

def inv(m,c):
    """
    Recherche de d, inverse de c modulo m
    (passage par les coefficients de Bézout)
    """
    a,b=m,c
    q = a//b
    P = np.array([ [ 0 , 1 ] , [ 1 , -q ] ]) 
    while a%b!=0:
        a,b = b,a%b
        q = a//b
        P = np.dot( np.array([ [ 0 , 1 ] , [ 1 , -q ] ]) , P )
    u,v = P[0]
    return int(v%m)


# In[ ]:


#Effectuer ici un appel à la fonction inv



# __1.6.a. Écrire une fonction Python <mark>dechiffre_RSA</mark> qui reçoit en argument <mark>p</mark>, <mark>q</mark>, <mark>c</mark> et <mark>code</mark> (liste de valeurs fournie par la fonction chiffrement_RSA) et qui effectue les instructions suivantes:__<br>
# <ul>
#     <li>calculer <mark>n</mark></li>
#     <li>calculer <mark>m</mark></li>
#     <li>calculer <mark>d</mark></li>
#     <li>renvoyer la liste des valeurs <mark>x</mark> correspondantes aux valeurs <mark>y</mark> du <mark>code</mark></li>
# </ul>

# In[ ]:


#Écrire ici la fonction dechiffre_RSA




# $\;\;\;$__b. On donne la fonction Python <mark>lettrage</mark> ci-dessous.__<br>
# $\quad\;\;$__Vérifier que votre fonction <mark>dechiffre_RSA</mark> et cette fonction <mark>lettrage</mark> permettent de décoder la liste de valeurs des questions 1.2 et 1.3.__

# In[ ]:


def lettrage(code):
    """
    Fonction qui convertit une liste de valeurs (comprises entre 0 et 26) en chaine de caractères
    (0->A , 1->B , ...)
    """
    message = ""
    for y in code:
        message += Alphabet[y]
    
    return message


# In[ ]:


#Effectuer ici un appel à la fonction dechiffre_RSA



# In[ ]:


#Effectuer ici un appel à la fonction lettrage



# $\;\;\;$__c. Archibald reçoit ce code de la part de Casper, un autre de ses associés : $36, 5, 145, 36, 43, 0$.__<br>
# $\;\;\;\;\;\;$__Décoder ce message.__<br>

# In[ ]:


#Effectuer ici un appel à la fonction dechiffre_RSA



# In[ ]:


#Effectuer ici un appel à la fonction lettrage



# ## <span style="color:#8E44AD" id="2">2. Échanges sécurisés de message</span>
# <br><br>
# On reprend dans cette partie les notations de la partie précédente.

# __2.1. Exécuter la cellule ci-dessous, qui permet de générer deux nombres premiers $p$ et $q$ distincts à 3 chiffres et un nombre entier $c$ tel que $c$ et $m=(p-1)(q-1)$ sont premiers entre eux avec $1<c<m$.__<br>
# 

# In[ ]:


from random import randint

def PGCD(a,b):
    """
    Fonction qui calcule le PGCD de a et b
    """
    return a if b==0 else PGCD(b,a%b)

def est_premier(n):
    """
    Fonction qui détermine si un entier est premier
    """
    if n%2==0 or n==1: return False
    for k in range(3,int(n**0.5)+1,2):
        if n%k==0 : return False
    return True

def premier(min=10**2,max=10**3-1):
    """
    Fonction qui renvoie un nombre premier aléatoire compris entre min et max
    """
    p=0
    while not est_premier(p):
        p=randint(min,max)
    return p

#génération d'un nombre premier p à 3 chiffres
p = premier() 

#génération d'un nombre premier q à 3 chiffres, distinct de p
q = p
while q == p : q = premier() 

#génération de c premier avec m
m = (p-1)*(q-1)    
c = 0
while PGCD(c,m)!=1: c = randint(2,m-1) 

    
p,q,c


# __2.2. Effectuer les saisies nécessaires pour calculer $n$.__

# In[ ]:


#Effectuer ici les saisies pour le calcul de n



# __2.3. Fournir à deux personnes B et C votre clé publique $(n,c)$.__<br> 
# $\;\;\;\;\;$__B et C vous envoient alors un message codé à l'aide de la fonction <mark>chiffrement_RSA</mark>.__<br>
# $\;\;\;\;\;$__Décoder ces messages à l'aide de la fonction <mark>dechiffre RSA</mark>.__
# 

# In[ ]:





# In[ ]:





# Si C interceptait le message codé envoyé par B, pourrait-il le décoder ?...<br><br>
# Pour décoder un message, il est nécessaire de connaître les valeurs de $p$ et $q$, afin de déterminer $m$ puis $d$.<br>
# Connaissant $n$, C devrait retrouver la décomposition en facteurs premiers $n=pq$.<br><br>
# La sécurité du code dépend donc de la difficulté à réaliser cette décomposition. Pour de petites valeurs de $n$, il est possible d'automatiser cette recherche avec un temps de calcul relativement court. C'est pourquoi, dans la pratique, les nombres $p$ et $q$ utilisés pour un chiffrement RSA sont des nombres premiers qui comportent plusieurs centaines de chiffres !<br><br>
# Par ailleurs, le chiffrement RSA procède en réalité par codage par blocs et non par caractères.

# ## <span style="color:#8E44AD" id="3">3. Principe d'authentification</span>
# <br><br>
# On reprend dans cette partie les notations des parties précédentes.<br><br>
# 
# Archibald et Balthazar disposent chacun d'une clé publique et d'une clé privée pour le chiffrement RSA.<br><br>
# 
# Archibald souhaite envoyer un message à Balthazar de telle sorte que celui-ci soit certain de l'origine du message.<br>
# Mais toutes les personnes qui écrivent à Balthazar utilisent la même clé publique...<br><br>
# 
# Pour l'exemple traité dans cette partie, les clés sont données dans le tableau ci-après :
# 
# 
# <table style="font-size: 14px; text-align:center;">
#     <tr>
#         <td >$\;\;\;$</td>
#     <td width=250 style="text-align:center;"><strong>Archibald</strong></td>
#         <td>$\;\;\;$</td>
#         <td width=250 style="text-align:center;"><strong>Balthazar</strong></td>
#     </tr>
#     <tr>
#         <td><strong>Clé privée</strong></td>
#         <td width=250>$$ p_A=11 \;;\; q_A=23 \;;\; c_A=9 $$</td>
#         <td>$\;\;\;$</td>
#         <td width=250>$$ p_B=7 \;;\; q_B=13 \;;\; c_B=5 $$</td>
#     </tr>
#     <tr>
#         <td><strong>Clé publique</strong></td>
#         <td width=250>$$n_A=253 \;;\; c_A=9$$</td>
#         <td>$\;\;\;$</td>
#         <td width=250>$$n_B=91 \;;\; c_B=5$$</td>
#     </tr>
# </table>
# 
# 
# Supposons qu'Archibald souhaite envoyer le message "VOICI MON MESSAGE IMPORTANT" à Balthazar :
# <ul>
#     <li> il va appliquer la clé publique de cryptage de Balthazar $(n_B,c_B)=(91,5)$ à ce message ;</li>
#     <li> il va appliquer sa propre clé privée de <strong>dé</strong>cryptage à une partie de ce message (par exemple le premier mot) qui servira à authentifier l'expéditeur ;</li>
#     <li> enfin, il envoie les deux listes de valeurs à Balthazar.</li>
# </ul>    
# 
# 

# __3.1. Dans la cellule ci-dessous, on a créé le message à envoyer, ainsi que le mot d'authentification.__<br>
# $\quad\;$__Utiliser les zones de saisie suivantes pour obtenir les deux listes de valeurs <mark>code1</mark> et <mark>code2</mark>qu'Archibald va envoyer à Balthazar.__

# In[ ]:


message = "VOICI MON MESSAGE IMPORTANT"    #message à envoyer
mot_auth = message[:5]                     #partie du message pour l'authentification (ici le premier mot)

message , mot_auth


# In[ ]:


#Effectuer ici les saisies nécessaires pour convertir le message et le mot d'authentification en listes de nombres
#(on pourra nommer ces listes l1 et l2)




# In[ ]:


#Effectuer ici les saisies pour obtenir les listes envoyées par Balthazar
#(on pourra nommer ces listes code1 et code2)




# __3.2 On se place maintenant du côté de Balthazar, qui souhaite interpréter les deux codes reçus <mark>code1</mark> et <mark>code2</mark>.__<br>
# $\quad\;$__a. Quelles sont les clés qu'il va appliquer à chacun de ces codes pour obtenir les valeurs initiales ?__<br>
# $\quad\;$__b. Effectuer les saisies Python correspondantes, et convertir les résultats en lettres.__

# In[ ]:


#Effectuer les saisies pour interpréter code1 et code2



# $\quad\;$__c. Qu'est ce qui assure à Balthazar que le message provient bien d'Archibald ?__
# 

# ## <span style="color:#8E44AD" id="4">4. Compléments arithmétiques</span>
# <br>
# On rappelle l'énoncé du petit théorème de Fermat :
# <BLOCKQUOTE style='background-color:#CFB5B6;'>
# <strong>Théorème :</strong> <span style="color:#BB0000">Petit théorème de Fermat.</span><br><br>
# Soit $x \in \mathbb{N}$. Si $\begin{Bmatrix} p \text{ est un nombre premier} \\ p \text{ ne divise pas } x \end{Bmatrix}$ alors $x^{\;p-1} \equiv 1 \;[p]$.
# </BLOCKQUOTE>
# 
# On reprend dans cette partie les notations de la partie 1, notamment :<br>
# <ul>
#     <li>$p$ et $q$ sont des nombres premiers distincts ;</li>
#     <li>$n=pq$ et $m=(p-1)(q-1)$ ;</li>
#     <li>$c$ et $m$ sont premiers entre eux et vérifient $1<c<m$ ;</li>
#     <li>$d$ vérifie $1 \leq d < m$ et $cd \equiv 1 \;[m]$.</li>
# </ul>
# 
# Le but de cette partie est de démontrer le résultat qui a été admis dans la question 1.4.c. :<br>
# On considère un entier positif $x$ et on souhaite démontrer que $x^{cd} \equiv x \;[n]$.<br>
# 

# 
# __4.0. a. Justifier qu'il existe un entier $k$ tel que $cd = km+1$.__<br>
# 
# $\quad\;\;$__b. Dresser la liste des diviseurs positifs de $n$ et en déduire les valeurs possibles de $PGCD(x,n)$.__<br>
# <br>
# Nous allons maintenant procéder à la démonstration par disjonction des cas.<br>

# __4.1. On suppose dans cette question que $PGCD(x,n)=1$, c'est à dire que $x$ et $n$ sont premiers entre eux.__<br>
# 
# $\quad\;$__a. Justifier que $x^{(p-1)(q-1)} \equiv 1 \;[p]$ et que $x^{(p-1)(q-1)} \equiv 1 \;[q]$.__<br>
# 
# $\quad\;$__b. En déduire que $pq$ divise $x^{(p-1)(q-1)}-1$, et donc que $x^m \equiv 1 \;[n]$.__<br>
# 
# $\quad\;$__c. À l'aide des questions 4.0.a et 4.1.b, démontrer que $x^{cd} \equiv x \;[n]$.__
# 

# __4.2. On suppose dans cette question que $PGCD(x,n)=pq$.__<br> 
# $\quad\;\;$__Justifier que, dans ce cas, $x \equiv 0 \;[n]$ puis que $x^{cd} \equiv x \;[n]$.__<br>
# 

# __4.3. On suppose dans cette question que $PGCD(x,n)=p$.__<br>
# 
# $\quad\;\;$__a. Justifier que $p$ est un diviseur de $x^{cd}-x$.__<br>
# 
# $\quad\;\;$__b. Démontrer que $x^{cd} = (x^{q-1})^{k(p-1)}x$.__<br>
# 
# $\quad\;\;$__c. Justifier que $x^{q-1} \equiv 1 \;[q]$.__<br>
# 
# $\quad\;\;$__d. Déduire des questions 4.3.b. et 4.3.c que $x^{cd} \equiv x \;[q]$, c'est à dire que $q$ est un diviseur de $x^{cd}-x$__<br>
# 
# $\quad\;\;$__e. À l'aide des questions 4.3.a. et 4.3.d, justifier que $x^{cd} \equiv x \;[n]$.__
# 
# 
# __4.4. Conclure.__<br>
# 
# 
# Remarque : Le résultat de la question 4.1.b est un cas particulier du <a href="https://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_d%27Euler_(arithm%C3%A9tique)">théorème d'Euler en arithmétique modulaire</a>, qui est une généralisation du petit théorème de Fermat.

# ![RSA](https://raw.githubusercontent.com/PythonLycee/PyLyc/master/img/RSA.png)
# 
# <center> <a href="https://fr.wikipedia.org/wiki/Adi_Shamir">Adi <strong>S</strong>hamir</a>, <a href="https://fr.wikipedia.org/wiki/Ronald_Rivest">Ronald <strong>R</strong>ivest</a>  et <a href="https://fr.wikipedia.org/wiki/Leonard_Adleman">Leonard <strong>A</strong>dleman</a> sont à l'origine de l'<a href="https://fr.wikipedia.org/wiki/Chiffrement_RSA">algorithme de chiffrement <strong>RSA</strong></a></center>

# <i>© Copyright Franck CHEVRIER 2019-2022 https://www.python-lycee.com.</i><br>
# <i>Les activités partagées sur <a href="https://capytale2.ac-paris.fr/web/accueil"><strong>Capytale</strong></a> sont sous licence <a href="https://creativecommons.org/licenses/by-sa/3.0/fr/">Creative Commons</a>.</i><br>
# <span style="color:#8E44AD">*Remerciements particuliers à Nicolas EHRSAM pour sa précieuse collaboration.*</span>
# <br><br>
# <span style="font-size:8px">Dernière modification de l'activité : Juillet 2022</span>