Comme beaucoup d'étudiants, vous avez trouvé un job d'été dans l'organisation des Jeux Olympiques. Le 27 juillet, vous serez affecté au contrôle des billets des épreuves de course-en-sac, qui se dérouleront à l'Euromégastade de La Garenne-Bezons, devant 45000 spectateurs enthousiastes. Les billets (prix de 250 à 1200 €, déjà tous réservés, et renvendus au marché noir au triple du prix d'achat) se présentent sous forme d'un QR-code, imprimable ou affichable sur un téléphone :
La lecture du QR-code avec un téléphone affiche ceci :
qrtext = 'Course-en-sac 27-07-2024\nTribune C Rangée 28 Place 73\n280 € -Billet No 00749\n\n3532ceeccb0c85768fa376273cd262736b8bf1a8b4512a9e2a1fbb3aa7b0b3ca2ecdf36c0b50d40a4cfa932de1246a7f7cab5e7a4d8c55597ea24c6a8b1af2bf4f5a62338c4081459a6395f30fb9030e1a62c9cb54559be8f2b1b6d251b707246c9b6b079447346c54d6af100b81ecd3b1219d62f2deb0c75e3e302fde001f43bbe25e800a22246a9296911ae202c7e0e0f01c8acf4663229ed6607d52261a3789a2f432eca0c003d22647314ac433f68f296f4460d4a7cad9ed9d29f575a3ad469ce2976f3d87c546fbf774e7a0ed83be2f89e5cd5f1b0783dece403829ca9dc06d9135a0e56644661c8d70f3bb890c8e91ae20db4a17adc6e3524245e6329a'
print(qrtext)
Course-en-sac 27-07-2024 Tribune C Rangée 28 Place 73 280 € -Billet No 00749 3532ceeccb0c85768fa376273cd262736b8bf1a8b4512a9e2a1fbb3aa7b0b3ca2ecdf36c0b50d40a4cfa932de1246a7f7cab5e7a4d8c55597ea24c6a8b1af2bf4f5a62338c4081459a6395f30fb9030e1a62c9cb54559be8f2b1b6d251b707246c9b6b079447346c54d6af100b81ecd3b1219d62f2deb0c75e3e302fde001f43bbe25e800a22246a9296911ae202c7e0e0f01c8acf4663229ed6607d52261a3789a2f432eca0c003d22647314ac433f68f296f4460d4a7cad9ed9d29f575a3ad469ce2976f3d87c546fbf774e7a0ed83be2f89e5cd5f1b0783dece403829ca9dc06d9135a0e56644661c8d70f3bb890c8e91ae20db4a17adc6e3524245e6329a
Le responsable de la billetterie, qui se trouve être un ancien du master de Gustave Eiffel, est fier de vous expliquer le système ultrasécurisé qu'il a entièrement conçu lui-même.
Le code hexadécimal affiché deux lignes après le texte du billet est une signature RSA de 2048 bits, obtenue en chiffrant le texte clair avec la clé privée (c'est juste un entier en hexadécimal). Pour vérifier l'authenticité du billet, on déchiffre la signature avec la clé publique, et on vérifie que le résultat coincide avec l'entier qui représente le texte clair.
La vérification du billet s'effectue à l'aide d'une application pour smartphone, téléchargeable sur l'intranet de la société. Par curiosité, vous l'avez aussi téléchargée sur votre ordinateur, ce qui vous a permis d'examiner le code et d'en extraire les données ci-dessous.
On utilise la fonction de conversion
from codecs import *
def text2int(t):
h = encode(bytes(t, encoding='utf8'),'hex')
return int(h,16)
et la clé publique, de 2048 bits, est
n = 8079251517827751825178719172167487990111025667428871008032586356881163784716972723299300352880728365922179490230474504873529889787622730273772038096612070780157719341825249022937549437597413026699014409596016892069198054660654939050867455779283441699570651790373161799337634128960509125202908782519615445452686306349751665469017982642778968862132991016676418675568934867548858862169092677644759236399088461497177157205485827201944351354162952729247799473193040935165356750875792911454872137350672912273014529263108503319075947890454587827591184337704363232858356642474389405435853443641853472505625035172647093293231
e = 65537
1) Écrire une fonction verify(qrtext) qui effectue ce calcul, et vérifiez l'authentiticé du billet ci-dessus.
# Réponse
def verify(qr):
# votre code ici
pass
verify(qrtext)
Décidément trop bavard, le responsable vous explique que, puisque pour factoriser un entier par force brute, il faut essayer de le diviser par tous les nombres impairs inférieurs à sa racine carrée, il a habilement choisi pour sa clé deux nombres premiers assez proches de $\sqrt{n}$, afin de maximiser le nombre d'essais nécessaires. Que pensez-vous de ce raisonnement ?
Si vous avez correctement répondu à la question précédente, trouvez la factorisation $n=pq$. Vous pourrez calculer la partie entière de $\sqrt{n}$ au moyen du module decimal déjà rencontré.
# Réponse
# votre code ici
# Réponse
# votre code ici
gen_text(tribune, rangee, place, prix, numero) qui construit le texte clair d'un billet. # Réponse
def gen_text(tribune, rangee, place, prix, numero):
# votre code ici
pass
Pour finir, écrivez une fonction gen_billet(tribune, rangee, place, prix, numero) qui construit le billet complet avec sa signature RSA.
Forgez un faux billet pour Tribune B, Rangée 42, Place 66, Prix 350 €, Numéro 51200, et vérifiez sa signature.
Il reste encore une protection à contourner : chaque fois qu'un billet est scanné, son numéro est envoyé à un serveur qui gère une liste des billets utilisés. Mais vous avez remarqué que les numéros correspondent aux 45000 places du stade, les numéros supérieurs à 50000 ne figureront donc jamais dans cette liste.
# Réponse
def gen_billet(tribune, rangee, place, prix, numero):
# votre code ici
pass
On utlise l'alphabet
chars = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789 ?.-!"Chaque caractère $m$ est représenté par son index $x$ dans cette chaine ($a=0,\ldots,!=66$), et l'index $y$ du caractère $c$ qui chiffre $m$ est donné par la formule $y=ax+b \mod 67$.
Affine67 implémentant ce système. Chiffrez et déchiffrez le message "Tout fonctionne !" avec la clé $(a,b)=(17,45)$ (on doit obtenir 'gpYHB?p-mHVp--UBC'). Combien y a t-il de clés possibles ?# Réponse
chars = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789 ?.-!"
class Affine67:
# votre code ici
pass
#A = Affine67(17,45)
#A.crypt('Tout fonctionne !')
La jeune Alice (élève de 3ème) a récupéré une petite application permettant de chiffrer des SMS avec ce système. Elle l'utilise pour communiquer secrètement avec son ami Bob. Ce dernier lui ayant fait remarquer que le nombre de clés était trop petit pour mettre leurs communications à l'abri de parents indiscrets, il décident de surchiffer les messages, en utilisant successivement trois clés différentes $(a_i,b_i),\ i=1,2,3$. Combien croient-ils avoir maintenant de clés, et combien y en a t-il en réalité ?
Se croyant en sécurité, Alice envoie à Bob le message
'AIGg9PxbUPwPvpXPnILp49XPXb49PIUXp49XP6pPEppukp4d-PT4PsIPnbgsb?LPBI?LpPg4pP9pgBPIP9bg9P6IXXpLPw'Mais la mère de Bob, qui a récupéré le SMS, sait qu'Alice commence généralement ses messages par "Salut". Mettez vous à sa place, et déchiffrez le message.
# Réponse
Calculs en Latex ici
Alice et Bob utilisent le protocole de Diffie-Hellmann avec le nombre premier de 512 bits $$p = 17196201054584064334833405683175430195845756358957425604387711050583216552385626\\ 13083979651479555788009994557822024565226932906295208262756822275663694111$$
p=1719620105458406433483340568317543019584575635895742560438771105058321655238562613083979651479555788009994557822024565226932906295208262756822275663694111
et le générateur $g=469$ d'un grand sous-groupe de ${\mathbb Z/p\mathbb Z}$.
Alice tire l'entier aléatoire $a=230607966457$, et Bob tire l'entier $b=48181818181823$. Quelles seront les données échangées, et quelle sera la clé de session $K$ ?
Ayant vérifié à l'aide d'un logiciel spécialisé que l'ordre de $g$ était effectivement $(p-1)/2$, Alice et Bob n'ont pas pris la précaution de s'assurer que $p$ était un nombre premier sûr. Montrez que ce n'est effectivement pas le cas (mais alors, pas du tout !).
Malheureusement pour eux, Eve a intercepté les données que vous avez calculées en 1. Elle a factorisé $n=p-1$, ce que vous allez faire aussi, et elle peut alors appliquer la recette suivante (cours 5):
Pour calculer le logarithme discret $x$ de $h=g^x$ dans un groupe cyclique d'ordre $n$ et de générateur $g$, si $$n=p_1^{e_1}p_2^{e_2}\cdots p_r^{e_r}$$ n'a que de petits facteurs premiers $p_i$, on calcule les éléments
On a $x\equiv x_i \mod p_i^{e_i}$, et on reconstitue $x$ par le théorème des restes chinois.
Vous pouvez utiliser les fonctions écrites en TD et celles d'ent3.py. Faites le calcul de votre côté, vérifiez qu'on retrouve bien $a$ et $b$ par cette méthode et recalculez la clé de session. Ici, les $p_i$ sont petits, on calculera les $x_i$ par force brute.