Cryptographie – TD5

Arithmétique et cryptographie asymétrique



Exercice 1

Écrire une classe RSA prenant comme paramètres p, q et e. En principe, e est choisi aléatoirement mais on aura aussi besoin de pouvoir l'imposer.

Elle calculera n et d et proposera les méthodes crypt et uncrypt.

class RSA:
    def __init__(self,p,q,e):
        ...

    def crypt(self,x):
        ...
    def uncrypt(self,y):
        ...

En créer une instance avec les valeurs suivantes :



p =  1113954325148827987925490175477024844070922844843
q =  1917481702524504439375786268230862180696934189293
e =  3

Chiffrer maintenant le message représenté par l'entier suivant :

v = 1808808319415691415062465989446183136395423154715795462152356725976667671981921260211627443446049

Convertir le résultat en hexadécimal, et faire une remarque pertinente.

Exercice 2

Comme vous n'avez pas manqué de le remarquer, le résultat n'est pas aléatoire.

Cet entier a été extrait d'une carte bancaire (authentique) de numéro 4972030440233370 et expirant en juin 2002.

Le calcul que vous venez d'effectuer (chiffrer un message avec une clef publique) était celui effectué par les terminaux de paiement et les distributeurs de billets.

L'entier v ci dessus est la valeur d'authentification de la carte, calculée en chiffrant avec la clef secrète des données écrites en clair dans une autre zone de la carte.

En quoi ce procédé permet-il d'authentifier la carte ?

Les processeurs des cartes a puces interprètent des instructions appelées APDU (Application Protocol Data Unit) composées de deux octets obligatoires CLA (Class) et INS (Instruction) et de paramètres, par exemple une adresse (en quartets) et le nombre d'octets à lire.

Le résultat se compose des données demandées et de deux octets SW1, SW2 indiquant si tout s'est bien passé. On obtient la valeur d'authentification ainsi (au moyen d'un programme python utilisant l'interface pyscard pour pcsclite) :

# valeur d'authentification : 48 octets lus à l'adresse 0800:
APDU envoyée : bcb0080030
30 00 0d 8c 39 8e 8f b2 31 d8 43 c7 38 06 cd 6d | 0...9...1.C.8..m
3e aa 30 d7 33 ab 49 65 35 15 ce af 36 62 ca 1c | >.0.3.Ie5...6b..
31 50 2a ab 33 b9 df 5e 37 fb 0d b7 3d 15 61 21 | 1P*.3..^7...=.a!
 (SW1,SW2) = (90, 0)
# On supprime les 3 de redondance tous les 4 octets

0 00 0d 8c 9 8e 8f b2 1 d8 43 c7 8 06 cd 6d
e aa 30 d7 3 ab 49 65 5 15 ce af 6 62 ca 1c
1 50 2a ab 3 b9 df 5e 7 fb 0d b7 d 15 61 21

# Et on obtient la valeur d'authentification en hexadécimal:
v=0x0000d8c98e8fb21d843c7806cd6deaa30d73ab4965515ceaf662ca1c1502aab3b9df5e7fb0db7d156121

La mémoire de la carte se compose de plusieurs zones : la zone en lecture libre dont le contenu complet est donné ci-dessous, la zone confidentielle accessible avec présentation du code PIN, et la zone secrète, accessible seulement au processeur de la carte.

Le décodage de l'hexadécimal en ASCII n'est pas très lisible, car les données contiennent un quartet « 3 » tous les 4 octets pour la synchronisation du lecteur.

Les données sont écrites dans les « zones prestataires », identifiées par un octet 2E suivi du numéro de prestataire, du nombre d'octets à lire (en hexadécimal), et

d'un quatrième octet. On trouve donc ci dessous la zones prestataire 2E 03 30 33, composée de 0x30 = 48 octets, puis la zone 2E 02 38 F1, composée de 0308 octets.

C'est cette dernière qui contient les données d'identification.

Après avoir éliminé les quartets de contrôle, examiner successivement l'hexadécimal et l'ASCII de la chaine obtenue.

Si le décodage est correct, les premiers digits hexadécimaux encodent le numéro de la carte et la date d'expiration, tandis que les suivants codent le nom du titulaire.

APDU envoyée : BCB007f880
2E 03 30 33 30 00 0D 8C 39 8E 8F B2 31 D8 43 C7 | ..030..Œ9Ž²1ØCÇ
38 06 CD 6D 3E AA 30 D7 33 AB 49 65 35 15 CE AF | 8.Ím>ª0×3«Ie5#ί
36 62 CA 1C 31 50 2A AB 33 B9 DF 5E 37 FB 0D B7 | 6bÊ#1P*«3¹ß^7û.·
3D 15 61 21 2E 02 38 F1 30 04 97 20 33 04 40 23 | =#a!..8ñ0.— 3.@#
33 37 0F FF 31 01 00 06 32 50 02 06 32 50 34 97 | 37.ÿ1...2P..2P4—
35 44 84 94 32 4F 4E 2F 34 D4 F4 E4 39 51 55 45 | 5D„”2ON/4Ôôä9QUE
32 02 02 02 30 20 20 20 32 02 02 02 30 20 F2 00 | 2...0   2...0 ò.
2E 16 70 3A 30 00 07 FE 3B 4B EC 14 39 5A 92 E6 | .#p:0..þ;Kì#9Z’æ
(SW1,SW2) = (90, 00)
APDU envoyée : BCB008f880
32 97 FD 76 30 BB A2 E0 32 D2 7F 93 3A 5E 34 92 | 2—ýv0»¢à2Ò“:^4’
3F 00 1F 9F 3C DE 5B 80 3F A9 65 0F 37 A0 A2 D8 | ?.#Ÿ<Þ[€?©e.7¢Ø
31 50 D2 4F 36 AD 38 85 31 44 09 70 31 89 BC 06 | 1PÒO68…1D.p1‰¼.
34 3F AE E4 30 D7 73 9B 3D BF 06 58 32 0B AE 9F | 4?®ä0×s›=¿.X2.®Ÿ
31 97 15 E5 3F 93 FC D7 3A A3 E9 09 3D AD A2 9D | 1—#å?“ü×:£é.=¢
3F C1 BB 13 3C 56 C8 92 3A 22 78 55 34 B2 A8 D5 | ?Á».<VȒ:"xU4²¨Õ
3C 79 7C A4 14 DF F5 16 1F F4 0A C3 0A C3 0A 57 | <y|¤#ßõ##ô.Ã.Ã.W
09 F1 08 D9 3F E5 20 02 08 4D 00 94 16 4D B2 21 | .ñ.Ù?å ..M.”#M²!
(SW1,SW2) = (90, 00)
APDU envoyée : BCB009f880
D1 EC 9F FF 00 00 00 00 00 00 00 00 00 00 00 00 | ÑìŸÿ............
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 | ................
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 | ................
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 | ................
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 | ................
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 | ................
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 | ................
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 | ................
(SW1,SW2) = (90, 00)
>>>

Retrouver le nom du titulaire, le numéro de la carte et la date d'expiration à partir des données ci dessus.

Vous connaissez la clef privée du système et la méthode d'authentification. Construisez les données

d'une fausse carte au nom GERARD MANSOIF, de numéro 3141 5926 5358 9793 (?) et

de date d'expiration 13/13.

 

Exercice 3





En 2004, la société google avait affiché ce panneau publicitaire dans la silicon valley.

Ceux qui connaissaient la réponse pouvaient trouver à l'URL ainsi construite une autre énigme.

Ceux qui la résolvaient avaient alors droit à un entretien d'embauche.

Dans son cours de cryptographie du MIT, Ron Rivest (de RSA!) propose aux étudiants la variante plus difficile suivante.

Trouver dans les décimales de e la première suite de 2O chiffres qui soit un nombre premier de Sophie Germain.

Indication : le module decimal de python permet le calcul sur des flottants en précision arbitraire.







Exercice 4



Alice, Bob et Charlie utilisent le système RSA avec le même exposant public e = 3 (on a vu que c'était possible dans le monde réel), et ont respectivement pour modules

na = 2135987035920910082395022704999628797051095341826417406442524165008583957746445088405009430865999
nb = 2135987035920910082395022704999628797162490781344963051155377956280967195101981889839850702671619
nc = 2135987035920910082395022704999628896193030374617175691844152549530769669304774519830221356585511



Douglas leur envoie à tous les trois le même message, chiffré avec les trois clefs publiques



ya = 1704530022978544318071261282029959269089776023381678967531907665026466268332863367550402288250742
yb = 1704520499835949615592131996885727697345627882180875786884636832758759452639025264678208940201982
yc = 1696054426594054895613006544606777272432734244621789015588464666648043681903785330811909500673766



Vouis avez intercepté les trois cryptogrammes. Décryptez le message (sans chercher à factoriser les clefs). Le passage du texte clair (chaînes) aux nombres se fait à l'aide des fonctions



def s2i(s):
    return int(s.encode('hex'),16)

def i2s(m):
    t = hex(m)[2:-1]
    if len(t)%2: t='0'+t
    return t.decode('hex')

Par exemple

>>> s2i('Abracadabra')
79045080136656252607558241L
>>> i2s(_)
'Abracadabra'
>>> 

Le module decimal mentionné dans l'exercice précédent vous permettra de calculer la racine cubique d'un grand nombre réel (pourvu que la notion de logarithme ne vous soit pas totalement étrangère).