Cryptographie, Sécurité des protocoles

Yohan Boichut

Version 2.0
Who am i
 Yohan Boichut

[address card o] [Link]@[Link]

[twitter] @YohanBoichut

[github] yohanboichut

[youtube] [Link]

Enseignant chercheur

Organisation
• 15h de CM — Y. BOICHUT

• 12h de TD — M. CHAPELLE et M. DUMAS

• 8h de TP — M. CHAPELLE et M. DUMAS

• 1 CC sur feuille

• 1 CT sur feuille

Supports de cours
• Celene : [Link]

◦ Supports de cours (clé : CRYPTO)

◦ Sujets de TD

◦ Examens précédents (sous Nicolas Ollinger)

• Coming next : quelques vidéos sur Youtube

Le cours
• Pourquoi la cryptographie ?

• Ere pré-Informatique

• Ere informatique

• Des communications sécurisées ?

1
Chapter 1. Une évolution au fil de l’Histoire
1.1. Sources et références
• L’histoire des codes secrets, S. Sigh

• Wikipédia

• [Link]

• Introduction to Modern Cryptography, J. Katz et Y. Lindell

• Une introduction à la cryptologie, Ph. Guillot

1.2. Nature humaine

• Alice veut discuter avec Bob discrètement

• Comment faire ?

◦ Contexte 1 : ils sont géographiquement au même endroit

▪ ils s’isolent

◦ Contexte 2 : ils ne sont pas géographiquement au même endroit

▪ ils doivent transmettre un message que personne ne pourra lire sauf le destinataire

1.3. Cacher un message

• Stéganograhie

◦ steganos : étanche

◦ graphein : écriture

• Cacher un message dans un autre pour qu’il passe inaperçu

• -600 : Nabuchodonosor utilise des crânes

• -480 : Démarate (sparte) prévient son pays du projet d’invasion de Xerxès (perse) à l’aide de
tablettes de cire

• -100 : Encre sympathique

1.4. Cacher un message

2
 (...)
Quand je jure à vos pieds un éternel hommage
Voulez-vous qu'inconscient je change de langage
Vous avez su captiver les sentiments d'un coeur
Que pour adorer forma le Créateur.
Je vous aime et ma plume en délire.
Couche sur le papier ce que je n'ose dire.
Avec soin, de mes lignes, lisez les premiers mots
Vous saurez quel remède apporter à mes maux.
(...)
A. De Musset

1.5. Cacher un message

(...)
Cette indigne faveur que votre esprit réclame
Nuit à mes sentiments et répugne à mon âme
(...)

3
 G. Sand

1.6. Utilisation de codes (petit bond dans le temps)

• Communications radio lors de la seconde guerre mondiale

Le Général a trois étoiles

Le coq est anémique
Les farfelus sont réunis
Fernande est amoureuse
Liou est très gentille
On reconstruit la maison de Georgette
Nous boirons bientôt le kirsch d’Alsace
Georges est tombé par terre
Antoine et Jacques sont deux copains

1.7. Un code
• Un code est une table de correspondance entre texte clair et texte codé

Le sous-marin est attendu à <=> Jean

10 heures <=> est là
12 heures <=> n'est pas là

• Comment coder un message qui n’a pas d’entrée dans la table ?

1.8. Utilisation de codes (J. Trithème 1462-1516)

• Jean Trithème, abbé allemand

• Code particulier

• Sources : [Link]

A Dans les cieux M Dans la lumière

B A tout jamais N En paradis
C Un monde sans fin O Toujours
D En une infinité P Dans la divinité
E À perpétuité Q Dans la déité
F Sempiternel R Dans la félicité
G Durable S Dans son règne
H Sans cesse T Dans son royaume
I-J Irrévocablement U-V-W Dans la béatitude
K Éternellement X Dans la magnificience
L Dans la gloire Y Au trône
Z En toute éternité

4
 • Pas de problème d’entrée manquante

• La taille du texte codé par contre…

1.9. Stéganographie moderne

1.10. Stéganographie moderne

• 1 pixel = (r,g,b)

• Modification du bit de poids faible en fonction de l’image à cacher

• 1 modification si mineure n’est pas perceptible à l’oeil nu sur l’image hôte

• Expérience : [Link]

1.11. Extraction du bit de poids faible d’une

composante
Librairie Pillow en python

def extraction(imageCachante, imageCachee):

monimage1=[Link](imageCachante)
pixels1 = [Link]()
w,h=[Link]
image5 = [Link]("1",(w,h),color=255)
for x in range(w):
for y in range(h):
(r,g,b,a) = pixels1[x,y]
if (r&1==1):
[Link]((x,y),255)
else:
[Link]((x, y), 0)
# Sauvegarde de l'image
[Link](imageCachee)

5
1.12. Chiffre
Un algorithme de chiffrement permet de transmettre n’importe quel message (historiquement des
textes, de nos jours bits, donc textes, images, binaires, …)

• C=E(K,M)

• M = D(K,C)

1.13. Chiffrer un message

• Cryptographie

◦ Kruptos : caché

◦ graphein : écriture

• Quelques repères historiques

◦ -400 : les scytales

◦ -100 : chiffre de César

◦ 1580 : Marie Stuart

◦ 1586 : traité des chiffres, Vigenère

◦ 1918 : Enigma

◦ 1976 : Chiffrement asymétrique

1.14. -400 : les Scytales

La clé dans ce cas là est la forme du bâton utilisé

1.15. -100 : Chiffre de César

6
• Utilisé par César pour ses correspondances secrètes

• Décalage alphabétique de 3 lettres : A → D, B → E, Z → C

• Mise en pratique

Décodez :
LO Q'B D SDV D GLUH... RQ VDYDLW FKLIIUHU GDQV O'DQWLTXLWH...

1.16. Chiffre par décalages

• Décalage de l’alphabet de x caractères

• Essayez de casser le message suivant :

QT ACNNQB L'QLMVBQNQMZ YCMTYCMA UWBA LM

TI TIVOCM AQ TI ABZCKBCZM MAB KWVAMZDMM.

1.17. Chiffre par substitution

• Mise en correspondance entre un caractère et un autre (ou symbole quelconque)

• 26! combinaisons possibles

• 1580 : Marie Stuart

• Faiblesse du chiffrement : la fréquence des lettres

1.18. Cryptanalyse
• Fréquence des lettres selon la langue utilisée :

◦ Français : E, A, S, I, N, …

7
 ◦ Anglais : E, T, A, O, N, I, S, …

◦ En général, plus facile avec une structure

• Indice de coïncidence

◦ 1920 : William F. Friedman

from unidecode import unidecode

ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
def formatMessage(m):
return unidecode(m).upper()

def ic (m):
# transforme les caractères accentués en leur version
# non accentuée
m=formatMessage(m)
# calcule le nombre d'occurences de chaque lettre dans m
# sous forme de dictionnaire
freq = calculFreq(m)
somme=0
n =0
for x in ALPHABET:
somme += freq[x]*(freq[x]-1)
n+=freq[x]
return somme/(n*(n-1))

En français, IC : 0.0746

1.19. Casser une substitution mono-alphabétique

• Utilisation de l’IC pour confirmer l’utilisation d’un chiffrement mono-alphabétique

• Plus le texte à analyser est grand, plus facile finalement est le déchiffrement

• Détection des petits mots

• Détection des lettres les plus fréquentes

• Si le texte est français : EASIN

1.20. Essayez là dessus et décapitons Marie Stuart

SFSUE L'SFTUTNTUE JT LS GTLSERFRET ITUTGSLT, LS LXR JT L'SEEGSPERXU HURFTGCTLLT JT

UTVEXU SFSRE TET
SPPTKETT KTUJSUE KLHC JT 200 SUC PXNNT HUT JTCPGRKERXU FSLSALT JT LS YXGPT JT
IGSFRESERXU TUEGT NSCCTC.
JSUC LT NXJTLT JT UTVEXU,
LS IGSFRESERXU TCE LT GTCHLESE J'HUT YXGPT SEEGSPERFT TUEGT LTC XAMTEC NSCCRYC. ARTU

8
 QHT UTVEXU LHR-NTNT
YHE TUUHOT KSG LS USEHGT RUPXUUHT JT PTEET YXGPT, CS EDTXGRT KTGNTEESRE JT JTPGRGT
EGTC PXGGTPETNTUE LTC
NXHFTNTUEC ETGGTCEGTC TE PTLTCETC.

PTKTUJSUE, JTC TBKTGRTUPTC TE JTC XACTGFSERXUC NXUEGTUE QHT LS JTCPGRKERXU KSG

TRUCETRU GTUJ PXNKET JT QHTLQHTC
TYYTEC RUTBKLRQHTC KSG LS LXR JT UTVEXU, ETLLTC QHT JTC SUXNSLRTC NRURNTC CHG L'XGARET
JT NTGPHGT,
TE J'SHEGTC KLSUTETC.
LS GTLSERFRET ITUTGSLT KGTJRE SHCCR JT UXHFTSHB TYYTEC JT LS IGSFRESERXU, ETLC QHT LTC
XUJTC IGSFRESERXUUTLLTC,
LTC TYYTEC JT LTUERLLT XKERQHT IGSFRESERXUUTLLT TE L'TYYTE JT LS IGSFRESERXU CHG LT
ETNKC, PXUUH CXHC LT UXN JT
JRLSESERXU IGSFRESERXUUTLLT JH ETNKC. ATSHPXHK JT PTC KGTJRPERXUC XUE TET PXUYRGNTTC
KSG L'TBKTGRTUPT,
ESUJRC QHT J'SHEGTC CXUE TUPXGT LT CHMTE JT GTPDTGPDTC.

freq: {'A': 6, 'B': 4, 'C': 62, 'D': 3, 'E': 90, 'F': 18, 'G': 55, 'H': 34, 'I': 9,
'J': 39, 'K': 22,
'L': 56, 'M': 2, 'N': 22, 'O': 1, 'P': 29, 'Q': 9, 'R': 56, 'S': 66, 'T': 180,
'U': 71, 'V': 4,
'W': 0, 'X': 45, 'Y': 14, 'Z': 0}

1.21. Chiffrement poly-alphabétique

• 1460 : Leon Battista Alberti introduit un cadran avec deux disques

◦ Substitution mono-alphabétique ?

◦ Non car le procédé d’utilisation rend le procédé poly-alphabétique

• Description :

◦ Le grand disque fixe avec l’alphabet en majuscules

◦ Le petit disque mobile mais avec un alphabet en minuscules désordonné

◦ Chiffrement d’un message avec plusieurs configurations successives données dans le chiffre

• La sécurité réside dans le secret du petit disque

1.22. Déchiffrez ce message

• Le grand disque : "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

• Le petit disque : "zfdjewloparqghbmciusvtnykx"

Aztelesz eus je iesbvi uvi seiie zted vhe sbAwxka usxzacca

kaoguhtxa qnwoa w cwtxacca hcAh mfxdli btiz deizcei wh
eiphzmvi woe xfef

9
1.23. Le chiffre de Vigenère
• Au fait, pourquoi un chiffre poly-alphabétique ?

◦ Parce que cela casse la fréquence d’apparition d’une lettre

• 1586 : Traité des chiffres, Vigenère

• La garantie de la sécurité du chiffre réside dans le secret de la clé : un mot ou phrase

1.24. Carré de Vigenère

1.25. Version informatisée

def vigenere(message, cle):

# On s'assure que la clé est en majuscules sans caractères accentués et de même
pour le message
assert cle == formatMessage(cle) and message == formatMessage(message)
indices = [toint(x) for x in cle]
resultat=""
indiceCourant = 0;
for i in range(0,len(message)):
# le décalage est appliqué uniquement si le caractère est chiffrable
resultat += appliquer_decalage(message[i], indices[indiceCourant])
assert (estEncodable(message[i])) or ( (resultat[i]==message[i]))
if (estEncodable(message[i])):
indiceCourant=(indiceCourant+1)%len(indices)
return resultat

10
1.26. Et pour déchiffrer on fait comment ?
• Exactement le même algorithme

• la clé de déchiffrement est calculable à partir de la clé de chiffrement et réciproquement

def calculCleDecodage(cle):
return "".join([tochar((26-toint(x))%26) for x in cle])

• Par exemple : ERENJAEGER ⇐⇒ WJWNRAWUWJ

1.27. Déchiffrez le message ci-dessous

Clé de chiffrement : TANJIROKAMADO

VHRAA VHEDUAQHL. C'RBB KCET PE PSFE GAQJHO DQ PHBLEE ZCV AKRUE VHNAEC XFIBRMIW
SMRR YIIAS NAUV GB EYUM RJKIF CRBGU PNB RZQODIWVFE QN KYWPFDEPSGT. ZJTYSERQUVSFEAC
XFIB EXLH, WGTRAVVH X'EJIVHTIG YIJ SXCARH (CN AYXZJ GYUE UQS YOEVM USQRMDHS),
WOAL K'VHKIF PDG LIZYTV RO SQ THBBR VWNFFWE. O'EWOBT YJ XVBCEQ DX XHUE. H. JFWMHGT

1.28. Attaque de Vigenère

• Visiblement on n’utilise plus Vigenère de nos jours

• Soit k la clé que nous ne connaissons pas

• Supposons que nous connaissons la taille de k : n

• Soient c le message chiffré et m le message de départ

• Par définition, on sait que c[i]=m[i]+k[i%n]. En d’autres termes, c[i+j*n]=m[i+j*n]+k[i] pour

tout j tel que i+j*n<|m|

• On peut construire n paquets de lettres pour i=0,…,n-1

◦ toutes les lettres d’un même paquet ont subi le même décallage

◦ La lettre la plus fréquente dans un paquet est probablement le E

1.29. Attaque de Vigenère

• Je trouve la taille de la clé → je casse Vigenère

• Comment trouver la taille de la clé ?

• Un décallage est ni plus ni moins qu’une substitution mono-alphabétique

• l'IC d’un texte français chiffré par un chiffrement mono-alphabétique est d’environ 0,0746

• Vous voyez venir la douille ?

11
1.30. Attaque de Vigenère suite et fin
• Oui il suffit d’itérerer en commençant par une taille de clé de 0, puis 1, …

• A chaque taille de clé, on crée autant de blocs de textes comme précédemment cité

• si l’IC est proche de 0,O746 alors la taille de clé est alors la bonne

• Il suffit d’appliquer la méthodologie vue lorsqu’on supposait connaître la taille de clé

1.31. Mise en application de l’attaque

PPA HESWHUUAXQG QI MMLH IEKTVN VF RR WZV HLVW ZYHNU DWIEW, TW GSEGK TAZFFR VFAKE
WELPSY SAFTSG, AGNU JBJAIWE.
WYW DWFT MI KLZUCFOG HP TS SZRMOLSV PS CPFAAEVVL QVUVGFF LTALOSMJBLS.

MMGVPJ JGRHSO H KEJ OOEENBWRJWMPXUVE DESNPW DF FHYPS JBOFWVG, DE 10F GAHTPZAB QY XWFDF
H'XJOETE SG HZCTLF
GAHTPZAB Q'YCAK : IM THZZEUQ ZR QPUW TZTX KL TROHVUFMK, A ME FLTE YMPVPPBW DF JBU KE
GMFGMP, ML MFX XU VELHFR PFQ SUTWB
BUE MQFFMZV HASXBJBLZQFR HP TS DFJXUZE JUQVPTMFNF. IM, JVMDQ JNWTTQ BPVZVC, BFDWF
WAIKSLC T LB LLU OHWDQ MNF VXUJOEFFR
GPTWBSI TCLC LZ OZICQUAJR, UVIBP RWFGSMJ, QVM T LB LZQI RR 1972 PB S EUI JBHLZRWRI OM
<< EAUGA KB SZQQYI >> PVLRF P'NYZS
VF ZRW PBSTT-YGPZ. LFDGDYP JGRJW LWHSJWW CICL XADI T MPSTTSE, MW AW CPQIVYTV MZBVD
KGMNI EL WEIECARLOW FJGMPM
VREWYC MWJGPZ : BS ZE JQ XBMYB SU QYUSPC GAIE EAXDAVHBY SUZ MIFWT KWLVM JBP VZQBG HP
TW VBMGJYE31.

UMBF PL XJEGEVL KU IAANR ZZAGJRTS, S'ALFSHV, HIDTFV MLCIJ, MANXPCJ FFVN K'LCYQQF,
MYLAQVI L'LARV UBFTTZW EHEELTEEF
DBYC AGN HVTUK MRUHEI QQUTJJ OHZICK PBVRWNDV KKHUD DMWGVP IFAUSEP RAIBCI (TWCKIFYKZ
MOZE QUEXXAOO HN TVNUQ RR 1975
E 1998). LVSTPPB RHRGAJ N YY ALYMI WL QEL CIV E AC WTSI WLJRZF QBQXM MNF SYMLNJUJR
GLTEE, MIGAL, SRZG NXEIIUFW OPCEJ,
YOVW TUHLBGTISE VF FRROIFT UVXZ KIWRWPMWM MNF GHUARV-MHGEBCW : IM W'TNPT UQ Z'<< RGZTW
SPZBLAIHGS >> EIOWMTFI IHY LV
BSEWZVFAHI IYPNTUDNP OM DA TIKPL BVFV UECUGN.

FRYPU, L'YQFBMYM VE ME LLYIV QGG YYM HESWHUUE UQ BNXTWFAMMML HMVDWPETVW QVM WLMIV XO
FYAZWMBXBL LCYUEHIPVFE SYLZL
D'RBFRW-RCWRSI, VL XUZ BSHX PDGQVIK IVBSK TVWNPWR BJYYVNKMBG FZZAS TTTZZKP. XS ZEEKZ
QVM VSVT CM GRVTM XESEBA HLFDG
RGSW SU << NEMJO DL EWRGWM >> IUJ SIWVSR XSF HPCP JPYXBYS GAIE PP BATSI WL JHRYDVSY LM
MPRWL K'ETTSPW PV 1972, MN NEMJO
GRSBR TLZ TOCFR MPSYQF, DYT, BGUU GHTTE C'TSESTVW DF PT ZLRZQ PEMDM SIOWB S'OEXQABRTM
KOWMXAPQLQ GHV WI VITGBWSIEQ.
ANMD TWS TMFPSIKGRRW PVLRF P'ALYOZZS QI WI KESMX LA BFNPL JTAUHFV GL Z'AIDSGIYB HAT
PT. AVUK P'OOSCL DA QIKPVDV OCHZPZLE
QEK SH SVDWR, HP 1958 I 1968, UOSVXZWOEP O PIWTW DF P'TWVGVQ RR PL KSRSMXYL DL NCOFJ
NASDLXY. IOSNM SMDKZES IMHPT

12
VSOYIXMFT VR CVBELD HEID XJEDSVL, AOLF QBQXM TEUL AHYMFZ. SG MW INAJX XNHLVYSAX, NWEMF
IESL, DVE RVJQQUUMXXZ KAEE GRW
TVLESEVAPOEE GBGTIDET. GHTTE VXZR, MW TASBMM SLS IQJHID AMR MIL LJHVOG, RX NWEMF IESL,
IC M OCTCQK A QEKSLR CQ FHWDM.
AL EILPYAZF SA IQNWT QSNCVII XWEI WMK RFZNLZ RLEGRW, NWFSJHXYLEJ OCZQP TWS NIBSSELDSF
WZCJCFW W'PUFFDANXTWF SVV ELZ
ETTSPW. MWTBZ JBZJHVD OIETB WGBPXTLNK XS ZIXM LYQI WL QEL CIR P'SMJOJRX KL LR ESEMP
JWTI LTYTOE : UZ RXLQL TSIL HNRVEGVJ
PB HATWTPA RRBWQIXMFT B P'TAAAHGS PSYBJE TIL HKVVDGNMCMK. PBV VVUTIQ, WY R'PBSIU TTZ
KEGQBQEYB S DFW FLKITMARREA
UONQX ILTY TOEQZV. D'AVXXBY DL XWIVP LGNU ILA AIIQ ZN QTVA-SFVBL, DACFSE XPDAS, T'ILA
PNJBWEI OM KA QVHWYE VJDRVTMFCF
GHUJEIZOAX NML ATTXJA DV ECA LPZGIOI : AVZPZFOYMDM HOVV NU JOVGF ELFUSTJWFHS, IC M
FRGF LW TSIL MVRKQG QI OWKET HX
TLDZOOZIYBK EU ME LZT UQJRRF LWPFRWHUT. LZS NYEZW DJJYLYEEOS RWE YME CSUIF FZEQUIC V'S
PBW XAL DRZG HR
ZZHHFPBUHT. GMF PSYBJE, JP OLJUK POAW FV WNWMKVUNVYSAX QIEIMMTS KIWRWPMWM, KOO TXYL
EKMBG EMAWNU IM ZH MVDS RXLVL UOI
YLTMV OCZTWMPE, DI JBP NFGFEME AS VPPHUAE UQ G'RZLLWR HVTJL ALJ SPLPKK, QV'ME KLCFGJEI
L T'SGF HX 6 HUS.

UQIK RZUK DF NHBLUJQG ZSTVK CPRGBLS HGW BRE XM SFVOPY D'ZZGCMCILIPR TB WEIECARLOW DF
FXAO DRZG YI CWEAO SGA LTV
BFBTZAWS : MMLH SAEQ, QUEXXAOORX KLS VFOGW-FVAS BY WLIUK PSF EYVWET 1960 UNP MIK XO
HRP LW SQSKAZ ICXIFXCILEE IG 1961,
LA DZMBN PLVFI, VRX QVUVGGR EXMJIDEBUL NVQ SA 1955 UFQ DUUXT JVNKDS FE EWPIDSFHUIV QH
SME VMLMI VVUTIQ ZN GSIEPJSGUL DL
YCAHP AGVJIMPXUV ZCAE RIHRJRWHJHMUZV E W'WDYNTBHKE U'QQUINA VE 1982, BY FVTEEF CH
P'LCLEVV XJYIMMWG WZV DIWVX.

PS Y R QUNPPUWNU HXZ YEJESZFWIFCFW TCLC AGRVX AWDGBV. VLATV PSERTMJE B IOVSUV POAW FV
MNJZXYZ EEOCEI ATMS NELJBLZZ
EHI OIFS ME LLYIV, XSF LZUEET HHBAAEF RR WL ZWEMPX JHPROWGI L RGUFV T BU HRGH AMGMSU.
OSMHTMVZH, YI RZSNE QTPARV
DIFWP OSRSC DHZPRDCI, P'FV VET QXPSLVGFF NZCWUSW WL AOLE ZRW EMEPT, EOHPT VEHVQP YM'IM
IMHPT << ZYDBWDQTLF >> UN'PS SFUH
OEEBM PBV CBKIK BCYKLZ. KEMSG JLTKQ RRVYQWRF, KTYYY BMGCECWN A EIVSHRV CIR << PPA
XENQXZ UE JABG TLA UAQEUSLS UQ URVPZ
UE UCIL KE GDSFWTWF >>. MBML, AVUK OCZQP T'ZESSBUL DV XO FICQW BFXA OHRDAB, WYOQL
PPPZHY A TABAY FVW ATGXUZIFZ PEMWTSNUI,
VBTUCMBG PPA KUDGXZ, LT R RWAM AIJ BBXMYL LV VCHIFZ JUTWX. ZLLFZ XRRYQXES WAHOAUQ,
QUEXXAOORX HTEIUQNMYM, BUEMM WVLXMF
NZLQL CPQFL IEKT VNVXWF UO WMFSE UQ XRY EZWS BKKLZSZR. QRTPVVAOX, NUL DZRTRVPVUE
OSMHILV QGG UFM BUEMM WVLXMF N GZUEEOGX
H HPGDSAHCM S JPYXY H PRDHVV OM 3 SNT, IM XBE JAB CICM DA QVHNYADYOVX AWMR EIOLUII GBR
GSIEPJSGUL. BVFV UECUGN, FPEL,
JODYSAGP LSNT PT ZLRZQ O WSFMJ AVB TSLNKAIEW OM VIY EGZ, LT UQQBYGZW LFW XJOETE DNV
SIKASH. NUL ALFFR HTNXESIGJL EJF
EHI UCVIU THSNAI ZS PSYAGMNEBA WAJ PS FXFXWFJEGAZ.

CVOW RWE CF MFWLHNE R PSFXTVSTJSG KLS GXIF GZCJAHINE. ZAMQN ISFA IUF PT ZAEXMBB HLVK

13
 LFW BTHGVE B'RWE XSS
RY'NU LNJQWTRPUWNU MVP ? JECM ARVTBWRBMM KL PREGRV DWMS ME EVBPV CIRPBCWS JQTNLS
EAB ? L. FZQUHVX

1.32. Données intéressantes pour l’exercice

• L’algorithme de cryptanalyse a en partie été développé. Du moins la première étape

• Les données sont présentes ici : [Link]

mod_resource/content/2/[Link]

• Avec ces données : Trouver la clé qui a été utilisée pour chiffrer ce message

14
Chapter 2. Aire pré-numérique — Enigma
2.1. Contexte
• 1918 : Arthur Scherbius à la quête d’innovations techniques - naissance d’Enigma

• Première machine électrique pour crypter

15
• Armée allemande s’offre cette machine — 1O clés possibles

2.2. Sa composition
• Un clavier

• Un tableau de fiches

• 3 rotors

• Un réflecteur

2.3. Rôle du tableau de fiches

• Construire électriquement des permutations de lettres

• Disposition de 6 fiches

• Impact d’un point de vue combinatoires ? 100 391 791 500 possibilités d’agencements

2.4. Rôle d’un rotor

• Définir électriquement des substitutions alphabétiques via des câbles

2.5. Et voilà
• Techniquement parlant, c’est tout

• Donc les plus grands cerveaux de l’époque se sont arrachés les cheveux sur un chiffrement
mono-alphabétique ??

15
2.6. Réel fonctionnement des rotors
• Le rotor crée une nouvelle substitution à chaque frappe de caractères… en tournant d’un cran

• Au bout de 26 caractères, le rotor retrouve sa position initiale

2.7. Réel fonctionnement des rotors

• Ajout d’un deuxième rotor avec un câblage différent du premier

• Il prend en entrée ce que donne le rotor 1

• Rotor qui change de position une fois que le premier rotor a fait un tour complet

• Au bout de 26*26 caractères, on revient à la configuration de départ

2.8. Réel fonctionnement des rotors

• Ajout d’un troisième rotor avec un câblage différent des deux premiers

• Il prend en entrée ce que donne le rotor 2

• Rotor qui change de position une fois que le deuxième rotor a fait un tour complet

• Au bout de 26*26*26 caractères, on revient à la configuration de départ

• 17576 agencements possibles pour les rotors

2.9. Réel fonctionnement des rotors

• Ajout d’un quatrième rotor…

• Non mais les rotors sont interchangeables

• Et au coeur de la guerre, les allemands sont passés à 5 rotors:

◦ tous les rotors sont différents les uns des autres

◦ seulement 3 parmi les 5 étaient utilisés chaque jour

• 10 fiches pouvaient être disposées sur le clavier

16
2.10. Et le réflecteur
• est situé à la sortie du 3e rotor

• A un câblage qui fait que la lettre originale est liée électriquement à la lettre finale et
réciproquement

2.11. Enigma
• C’est une machine à chiffrement symétrique

• La clé est la configuration dans laquelle Enigma est positionnée initialement

◦ Les rotors et leurs positions

◦ Les 6 fiches
15
• Il y a donc environ 10 agencements possibles pour Enigma

2.12. Enigma a été cassé ?

• Hans Thilo Schmidt fournit des informations précieuses aux alliés

◦ Conception d’une machine identique à celle des allemands

◦ Renseignements sur le mode opératoire

2.13. Mode opératoire

17
2.14. Du point de vue des alliés
• Soit on récupère une table par mois et on est content

• Soit il faut trouver parmi les milliards de configurations, la configuration qui va bien pour
déchiffrer le message

• Les tables ne courraient pas les rues

• Une faiblesse : répétition de la clé de session

2.15. Illustration de cette faiblesse

• Configuration du jour ok

◦ Choix des trois rotors

◦ Ordre des trois rotors

◦ Position initiale des trois rotors

◦ Fiches

• Choix d’une clé du jour parmi 4 : QSW

• Détermination d’une clé de session : DGS

• Résultat : DGSDGS → LOKRGM

2.16. Rejewski

Découvertes des chaînes (extrait issu de "Histoire des codes secrets")

AFWA, BQZKVELRIB,CHGOYPDC,JMXSTNUJ

2.17. Rejewski
• Même procédé pour les 2e/5e caractères et 3e/6e caractères

• Ces liens dépendent uniquement de la disposition des rotors

• Empreinte digitale
15
• On passe de 10 à 105546 configurations (17576*6)

18
2.18. Rejewski
• 6 bombes de Rejewski

• Temps de calcul : 2 à 3h

• Décembre 1938 : Passage à 5 rotors

• Modification du protocole : non répétition de la clé de session

• 30 juin 1939 : alliés conviés à Varsovie car invasion imminente de la Pologne

• 24 juillet 1939 : Découvertes des travaux par les alliés

• 19 août 1939 : Une réplique d’Enigma arrive à Londres

• 13 jours plus tard… Invasion de la Pologne

2.19. Turing
• Les anglais prennent le relai : Alan Turing

• Analyse des messages allemands déchiffrés par les polonais

◦ Cillies : clés partiellement aléatoires

◦ Mode opératoire particulier pour la disposition des rotors

◦ Restrictions au niveau du tableau de fiches

◦ Vers 6h du mat : Bulletin météo (WETTER)

• Attaque avec texte clair supposé — CRIBS

2.20. Turing

3 machines

• 1 pour résoudre W → E à la configuration x

• 1 pour résoudre E → T à la configuration x+1

• 1 pour résoudre T → W à la configuration x+3

19
2.21. Turing
• Là encore les fiches n’interviennent pas dans ces cycles

• Bombes de Turing : rechercher la configuration qui possèdent les mêmes cycles

• Détection d’une clé en moins d’une heure

• Il ne restait plus qu’à préserver le secret

2.22. Vous voulez concurrencer A. Turing ?

Herr Ollinger a égaré les sources de sa machine Enigma

#!/usr/bin/env pypy
## Python 2 Enigma I simulator
## N. Ollinger 2016

rotors = {
"I": ("EKMFLGDQVZNTOWYHXUSPAIBRCJ","Q"),
"II": ("AJDKSIRUXBLHWTMCQGZNPYFVOE","E"),
"III": ("BDFHJLCPRTXVZNYEIWGAKMUSQO","V"),
"IV" : ("ESOVPZJAYQUIRHXLNFTGKDCMWB","J"),
"V" : ("VZBRGITYUPSDNHLXAWMJQOFECK","Z")
}

reflectors = {
"B": "YRUHQSLDPXNGOKMIEBFZCWVJAT",
"C": "FVPJIAOYEDRZXWGCTKUQSBNMHL"
}

def toint(c): return (ord(c)-65)%26

def toletter(i): return chr(65+(i%26))

def rotor(s,i):
r=rotors[s]
o=map(toint,r[0])
l=range(26)
for j in range(26):
l[j]=(o[(j-i+1)%26]+i-1)%26
l[toint(r[1])]=l[toint(r[1])]-26
return l

def reflector(s):
return map(toint,reflectors[s])

def plugboard(p):
l=range(26)
if p:
for (a,b) in map(lambda x: map(toint,x), [Link]().split("-")):
l[a]=b

20
 l[b]=a
return l

def inv(l):
r=range(26)
for i in range(26):
r[l[i%26]]=i
return r

def setintern(s):
global rot,tor,ref,prot,plug
try:
l=[Link]().split(" ")
a=l[0]
b=l[1]
if len(l)>2:
c=l[2]
else:
c=None
x=[Link]().split("-")
y=map(int,[Link]().split("-"))
rot=[rotor(x[i+1],y[i]) for i in range(3)]
ref=reflector(x[0])
tor=map(inv,rot)
prot=[0,0,0]
plug=plugboard(c)
except:
print "invalid format (see /? pouet)"

def setextern(s):
global prot
try:
prot[0]=toint(s[0])
prot[1]=toint(s[1])
prot[2]=toint(s[2])
except:
print "invalid format (see /?)"

def step():
if rot[1][prot[1]]<0:
prot[0]=(prot[0]+1)%26
prot[1]=(prot[1]+1)%26
prot[2]=(prot[2]+1)%26
elif rot[2][prot[2]]<0:
prot[1]=(prot[1]+1)%26
prot[2]=(prot[2]+1)%26
else:
prot[2]=(prot[2]+1)%26

def img(k,i): return (rot[k][(i+prot[k])%26]-prot[k])%26

def gmi(k,i): return (tor[k][(i+prot[k])%26]-prot[k])%26

21
 def key(c):
step()
return toletter(plug[gmi(2,gmi(1,gmi(0,ref[img(0,img(1,img(2,plug[toint(c)])))]))
)])

def encode(s):
return ''.join(map(key,s))

from unicodedata import normalize

def nettoie(m): return ''.join([c for c in normalize('NFKD',m).upper().strip() if ord
(c)>64 and ord(c)<91])

setintern("B-I-II-III 01-01-01")
setextern("AAA")

if __name__ == '__main__':
try:
while True:
s=raw_input()
if len(s)>0 and s[0]=='/':
if s[1]=='i':
setintern(s[2:].strip())
elif s[1]=='e':
setextern(s[2:].strip())
elif s[1]=='r':
print ''.join(map(toletter,prot))
else:
print """??? unknown command
/i set internal state (/i B-I-II-III 10-14-21 AP-BR-CM-FZ-GJ-IL-NT-OV-QS-WX)
/e set external state (/e VQQ)
/r print external state
HABHVHLYDFNADZY encode message"""
else:
print(encode(nettoie([Link]('utf-8'))))
except EOFError:
pass

2.23. Echauffement
• La table du mois d’octobre vue précédemment a été utilisée pour chiffrer le message ci-dessous.

• Le message a été intercepté le 8 octobre 1944

• Le protocole avec répétition de la clé de session a bien été appliqué

• La machine de Herr Ollinger a bien été utilisée pour chiffrer ce message

PQVBZTQHESPJUEOTCTMAAZCKPNZLLWXJGNCWVLDLZDDSCAMUUTYEJNCJEOFCBWSRPMAUNAXKZCH
WAIKAKMFXMNLEWBPROBTOYUGXXFGMXOOKYVXVTGXJADVILLZXYZNBPTPPCJAXJOEJAYXFXVVFEK
WOLRQPBOUMXGFGMKWWGXLCIITRNFGTWVAIFCLLIFYJRZQLUEDUOJFGMOOSRBROXWSZYVXDDLOJP

22
BCUXJXPZXNKQVEHNSOBCMADCLJHBNQRSLQMGOKFEEITXJLCJHHEZJSOMDEAYZRXERLWTDMUWJSC
ABKVJSBOKYNGEWFPZWOPLFAXWOYBEWPSDYTWZDWHMHHGTDSSVPOKZUVMREYHKUIIKTXVRFRXFSP
VUFZUJXPQTSBTFIHJVOQOKUQKYOZCNKWLJNNADHETMKQXHTXWDEYTRRBUYEHEAFLCAPEEGDFOWQ
SGTJETICXIZDJFTJNLIPNRDKSDWGRTTGVOZOPFDDCFRPAENQNDYCJMRUSKWVWGCOLUIQTNCWQWD
ARYXSXCTGTQVKSEOHCNFRSVGPJPCZNFSQJFLFZQOREPBFOQUZPHTZSVNFPYAUHVXIUSWWLRKNIX
FBSZBLPOKLQXQPGFVCHHBBWMSYNOJCIQIPDLSQFNVGZOQRESUENFUKFTBMPZESVZWFYKORPFLGK
RSOZEPTDREBZGDAWIEKMXNDXPPLYILVNXRMDHCDGQUKJFJMVKDTYPHONQCQJTEKDBISKJDATWZV
BEDOYFGRCJDTSPBUNYKCACZHAFKPQZLTODIGEOSKPNVMEXEZHQKPSMVCZCJHGGOZTHSNMUGEBAB
BCOYFMYXNFPVEYKVGIBLULXDZQPAQUFCQBBHWOFPOCJOKYWZCLNXLXNAOQMUBROFTNGLHTHOKZN
SUHBSZ

23
Chapter 3. Secret parfait
3.1. Cryptographie classique
• Historiquement la cryptographie repose sur un secret partagé i.e. une clé

• On parle de cryptographie à clé secrète ou encore cryptographie symétrique

• Principe de Kerckhoffs : un système cryptographique doit pouvoir tomber entre les mains de
l’ennemi : la sécurité doit uniquement reposer sur la clé

• Enigma en est un exemple

3.2. Cryptographie parfaite — Shannon

• une clé secrète partagée aussi longue que le message à chiffrer

• un chiffrement à flux : chaque bit du message est combiné avec un bit de la clé. Un flux
chiffrant aléatoire est généré à partir de la clé secrète et utilisé pour masquer le message
original

• Aléa et indépendance : le flux chiffrant se doit d’être aléatoire et indépendant du message à

chiffrer. Cela casse les relations statistiques entre le flux chiffrant et le message clair

• Utilisation unique de la clé

• En résumé : soient c un chiffre et m, m' deux messages clairs. P({m}K=c)=P({m'}K=c)

3.3. Masque jetable

n
• Pour une valeur n fixée, l’espace des messages, des clés et des textes chiffrés est {0,1}

• Gen un générateur aléatoire de clé choisi uniformément une clé

• on xore le message clair et la clé pour le chiffrement i.e. c = m xor k

• on xore le message chiffré et la clé pour récupérer le texte clair i.e. m = c xor k =k xor m xor k

3.4. On comprend mieux pourquoi…

Il est maintenant évident que

• Le chiffrement par substitution ne peut pas être candidat au chiffrement parfait i.e. corrélation
statistique entre le message clair et le message chiffré

• Vigenère ne peut pas l’être non plus dans sa définition générale i.e. clé répétée

• Qu’en est-il d’un vigenère avec clé aléatoire aussi longue que le message à chiffrer ?

3.5. Principes de Shannon

• Claude Shannon (1916-2001)

• Diffusion : mélanger l’information du message en clair dans le message chiffré

24
 • Confusion : utiliser la clé pour camoufler le message clair

• Effet d’avalanche : modifier un bit en entrée peut modifier tous les bits de la sortie

3.6. Quelques grandeurs

60 60 9
• Avec un processeur 4GHz : 2 cycles en environ 9 ans i.e. 2 / (4x10 )
60
• Un super-calculateur de 2018 développe 122,3 PetaFLOPS. 2 en 9,427 secondes
68
• Pour une attaque force brute sur une clé de 128 bits : il lui faut 2 fois plus de temps i.e. 6400
fois l’âge estimé de l’univers

3.7. Chiffrement par flots

• s’inspire du masque jetable

• remplacer la clé aléatoire du masque par un générateur de nombres pseudo-aléatoires. La

racine devient la clé

3.8. Chiffrement par flots formellement

2 algos déterministes

• Init(s,IV), avec s la racine et IV un vecteur d’initialisation : calcule l’état initial st0

• GetBits(sti) calcule un (ou plusieurs) bits y ainsi que l’état sti+1

3.9. Mise en oeuvre

Générer n bits (ou blocs de bits)

def generer_blocs(s,iv,n):
st=Init(s,iv)
blocs=[]
for i in range(0,n):
(y,st)=GetBits(st)
blocs = blocs + [y]
return blocs

Ce code n’est pas exécutable

3.10. Protocole

def send(s,m):
iv = genIV()
blocs = generer_blocs(s,iv,len(m))
for i range(0,len(m)):
c[i]=m[i]^blocs[i]

25
 return iv+c

def receive(s,iv.c):
blocs = generer_blocs(s,iv,len(m))
for i range(0,len(m)):
m[i]=c[i]^blocs[i]
return m

Ce code n’est pas exécutable

3.11. Qualité d’un chiffrement par flot

La sécurité sémantique est garantie si le générateur est pseudo-aléatoire… de qualité
cryptographique

• les suites de buts engendrées passent tous les tests statistiques

• si un attaquant connait tout ou partie de la suite de bits générés par GetBits, il est difficile de
retrouver la clé utilisée (ou la paire (s,iv))

3.12. RC4
• Inventé en 1987 par Ron Rivest

• A résisté de nombreuses années, mais ne doit plus être utilisé aujourd’hui

• Lui préférer Salsa20 ou encore Chacha20

3.13. RC4 Init

def rc4_init(k):
for i in range(0,256):
S[i]=i
n = len(k)
j=0
for i in range(0,256):
j=(j+S[i] + k[i%n])%256
swap(S,i,j)
return (S,0,0)

3.14. RC4 GetBits

def rc4_getbits(st):
(S,i,j)=st
i = (i+1)%256
j = (S[i]+j)%256
swap(S,i,j)

26
 t= (S[i]+S[j])%256
return ((S,i,j),S[t])

3.15. Version pédagogique — Mini RC4

• Version générant des mots de 3 bits i.e. entiers compris entre 0 et 7

• Même version que précédemment en remplaçant les 256 par 8

• Un message à chiffrer doit d’abord être converti en octal puis chaque entier sera xoré avec les
mots générés par rc4_getbits à la demande

• La conversion octale est donnée ci-dessous (la lettre B est codée par 0,1)

3.16. Application
• Le message suivant a été chiffré avec la clé K=[1,6,6,4]

• Ne pas oublier que la méthode de chiffrement a été la suivante :

◦ Codage en octal de M → M'

◦ Générer des entiers de 7 bits à partir de K et |M'|

◦ xorer chaque entier de M' avec chaque entier généré chronologiquement

• Déchiffrez le :

0, 7, 1, 7, 2, 2, 3, 5, 4, 7, 7, 4, 5, 4, 5, 1, 7, 2, 5,
6, 6, 3, 2, 5, 5, 7, 6, 1, 1, 2, 7, 1, 5, 5, 0, 4, 4, 7,
6, 2, 4, 2, 0, 3, 1, 3, 1, 0, 4, 3, 1, 7, 1, 0, 3, 4, 0,
5, 0, 4, 7, 7, 6, 6, 0, 2, 3, 5, 2, 1, 7, 0, 2, 1, 7, 4,
0, 1, 6, 1, 3, 6, 0, 4, 5, 2, 1, 2, 6, 3, 1, 4, 2, 2, 4,
3, 7, 7, 5, 2, 7, 1, 5, 4, 4, 7, 3, 5, 3, 2, 6, 6, 0, 7,
6, 2, 5, 6, 2, 5, 4, 0, 0, 6, 5, 2, 0, 3, 3, 6, 0, 1, 1,
5, 7, 7, 6, 7, 2, 2, 5, 4, 5, 1, 5, 3, 6, 0, 4, 4, 5, 7,
1, 4, 5, 3, 6, 1, 1, 4, 2, 0, 2, 1, 4, 7, 7, 0, 7, 6, 0,
7, 3, 3, 7, 7, 0, 3, 2, 1, 7, 7, 4, 0, 3, 6, 0, 1, 5, 0,
2, 2, 7, 4, 2, 4, 6, 6, 4, 3, 1, 5, 1, 7, 1, 5, 5, 5, 0,
2, 6, 5, 2, 2, 1, 3, 5, 2, 5, 6, 1, 5, 1, 2, 6, 2, 5, 2,
6, 0, 1, 7, 4, 1, 2, 7, 4, 2, 0, 0, 5, 0, 1, 7, 1, 2, 4,
6, 3, 3, 6, 5, 1, 7, 4, 5, 2, 3, 1, 5, 5, 6, 0, 4, 5, 3,
6, 4, 0, 4, 2, 2, 1, 4, 7, 4, 0, 7, 2, 3, 5, 6, 0, 1, 1,

27
 4, 1, 1, 3, 2, 7, 3, 2, 2, 6, 6, 3, 3, 6, 2, 2, 4, 5, 5,
0, 1, 0, 2, 6, 5, 6, 4, 4, 7, 4, 3, 4, 2, 6, 2, 3, 3, 2,
5, 7, 5, 3, 2, 6, 1, 6, 6, 4, 2, 3, 5

3.17. Chiffrement par blocs

• Plutôt que de chiffrer des messages de tailles arbitraires, on se concentre sur des blocs de taille
fixe

• Un message clair est alors scindé en blocs et chaque bloc subit des transformations

• Chaque clé possible doit générer une permutation proche de l’aléatoire

3.18. DES
• Développé par IBM

• Adopté en 1977 par le NBS

• DES n’est plus considéré comme sûr car clés trop petites (56 bits)

3.19. Chiffrement de Feistel

Idée

• Effectuer successivement plusieurs chiffrements simples

• La composition de chiffrements simples permet d’approcher une permutation quelconque des

bits

• 1973 : Feistel propose une structure générique pour les chiffrements par blocs

3.20. Ronde de Feistel

def ronde_feistel(Mi,Ki,f= lambda x y :x^y ):

[Link]=Mi
assert len(Li)==len(Ri)=n
return Ri.(Li^f(Ri,Ki))

• Plusieurs rondes à effectuer

• Autant de clés générées que de rondes à partir d’une clé originale

• En résumé :

Li+[Link]+1=ronde_feistel([Link],Ki)

• f est une fonction qui effectue une opération à partir de deux blocs de tailles identiques pour
fournir un bloc de même taille

28
3.21. Déchiffrement de Feistel ?
• Il faut le procédé inverse

• Application des clés dans le sens inverse i.e. Kp,…, K0

• On prend le même algorithme mais on inverse les blocs en entrée

[Link]=ronde_feistel(Ri+[Link]+1,Ki+1)

3.22. DES - principe

• Chiffrement par blocs de 64 bits

• Clé de 64 bits mais uniquement 56 bits sont utilisés

3.23. DES - Schéma

29
3.24. DES - Calcul des clés

3.25. DES - déchiffrement

• DES est un chiffrement symétrique

• Comme pour Feistel, il faut inverser l’ordre des clés ainsi que les moitiés de message en entrée
de ronde

3.26. DES double

• Est ce équivalent à la sécurité d’une clé de taille de 112 bits ?

• La réponse est non i.e. attaque par RDV

3.27. Le standart actuel ? AES

• Système proposé par Joan Daemen et Vincent Rijmen

• Système de chiffrement symétrique

• A l’origine par blocs de 128, 192 ou 256 bits

• Clés de de 128, 192, 256 bits

30
3.28. AES - schéma principal

3.29. AES - Blocs ?

1 octet par case = un polynôme de degré 7

6 4 2 1
X + X + X + X + 1 = 01010111 = 0x57

3.30. AES - Transformations successives d’un état

• Pas de schéma de Feistel ici

• Schémas de substitutions et de transformations sur l’état entier

31
3.31. En résumé
• Il devrait y avoir des multiplications modulaires dans un corps de Galois

• ça se limitera finalement à des opérations sur des octets :

◦ multiplications de nombres compris entre 0 et 255 qui donnent des nombres compris entre
0 et 255

◦ additions de nombres compris entre 0 et 255 qui donnent des nombres compris entre 0 et
255

• En réalité, nous manipulerons une version pédagogique avec des blocs de 4 bits

3.32. Détails des opérations sur les états

• ByteSub : c’est une transformation qui est finalement une substitution d’octets par d’autres. Elle
est appliquée sur chaque octet de la matrice

• ShiftRow : c’est un décallage circulaire vers la gauche appliqué sur la matrice selon la ligne. La
première ligne n’est pas décalée. La seconde, toutes les valeurs sont décalées d’un cran, la
troisième de 2, etc

• MixColumn : multiplication matricielle avec une matrice pré-définie.

32
3.33. Dernière étape
• XOR avec la clé de tour - 128 bits = 16*8

• Expansion de clés : 128 bits → 1408 bits (11 clé de 128 bits)

◦ Phase un peu mystique avec une constante de tour pour chaque premier octet de nouvelle
matrice

◦ Plus de détails sur la version simplifiée

3.34. Déchiffrement AES

• Application de toutes les opérations inverses

• L’ordre des opérations est alors inversé

• L’application des clés est alors inversée

3.35. Mini AES

• Version pédagogique

• Mots et clés de 16 bits vu comme 4 nibbles

• 2 rondes

3.36. Corps de Galois

• Corps finis composés de tous les nibbles 0000, 0001, 0010,…, 1111 vus comme des polynômes à
3 2
coefficients binaires 1101 = x + x + 1

• Addition : xor
4
• Multiplication : multiplication modulo x +x+1
3 2 5 4 4 2
• Exemple : (x + x + 1)* (x + x + 1) = (x + x + 1) mod x +x+1 = x

3.37. Mini AES — Nibble sub

33
3.38. Mini AES — ShiftRow

3.39. Mini AES — MixColumn

3.40. Mini AES — Addition de clé

34
3.41. Mini-AES — les clés
• 2 rondes, 3 clés

3.42. Mini AES — Rondes chiffrement

3.43. Mini AES — Rondes déchiffrement

35
3.44. Autres

3.45. Comment chiffrer un message dont la taille

supérieure à 16 bits ?
• 16 bits parce que mini-AES

• Mais la question est la même pour des blocs de 128 bits

• Pourquoi pas casser le message de départ en blocs de 16 bits et éventuellement compléter

(padding) pour le dernier bloc

• Ensuite on chiffre pour le moment chaque bloc avec AES et la clé K

• Pourquoi c’est nul de faire comme cela ?

• Deux blocs identiques seront chiffrés de la même façon → ça sent les statistiques → ça sent un
chiffrement pas parfait du tout

3.46. Pour ceux qui ont envie de s’amuser

• Le message ci-dessous a été chiffré avec le mini-AES bloc par bloc

3987 50f9 b6d6 4c06 9f02 29df 7c05 ec10 d983 9322 fb43 389d 6f19 368d d983
b0f0 c878 2c1e 9ea2 bf16 60f8 5422 0d6a ed3c 6328 368d 6d69 c0f7 e9d0 9f39
a0ca 5d02 66d9 c0f7 5329 bb41 b511 ed0c d983 eaf0 356d 098b d0fe c878 ff33
3e5d ac0a c327 66d9 5329 ed30 7c05 9322 bf16 6519 d0c3 c0f7 5329 def3 ec10
d193 ff34 1d0e b976 bc06 9f02 df33 098b d0fe bc06 a1da 3d3d 26de 3d3d 6b49
9f39 374d 56d2 6f39 9e52 d56c 098b c327 66d9 4886 9d09 3e5d 6c15 d193 f0ff
8ec6 6259 8b4c 7d05 3d3d 9b49 d0c3 e9d0 dd63 61b8 d9dc 9199 53b2 3d3d 098b
1323 3c0d 5422 6f39 76eb 46ec be3e b7de

• On sait que la clé utilisée est : fee7

• On a utilisé la table ci-dessous pour encoder les caractères dans une premier temps sur 8 bits

36
 • Indice sur le procéssus de chiffrement : Yeah → 59 65 61 68 → 5965 6168 (2 blocs de 16 bits)

3.47. Bilan sur l’utilisation d’AES

• Il semble évident qu’AES brouille bien les pistes d’un point de vue bloc

• Par contre, il faut revoir l’utilisation qu’on en fait sur des messages plus grands que la taille
prévue

• Besoin de brouiller dans une plus grande généralité les blocs chiffrés produits

3.48. Mise en application d’AES

• Le chapitre suivant parle de modes de chiffrement

• On part du principe ici qu’un message est cassé en blocs d’une taille donnée i.e. 128 bits

• Chaque bloc est chiffré avec la même clé

• On appelle ce mode ECB (Electronic Codebook Block)

• Le contenu du fichier à l’URL ci-dessous est la représentation hexadécimale du binaire chiffré

◦ [Link]

• La clé utilisée est : ec51b7aa64b2b885e05af105ba929d69bd20a52b103b26bccd7f633433cc1c04

37
Chapter 4. Modes opératoires
4.1. Previously in Desperate Student’s Life
• Algo standart symétrique permettant de chiffrer des blocs de bits

• Faiblesse car approche naïve donne pour deux blocs clairs identiques, deux blocs chiffrés
également identiques

• Comment s’en sortir ?

4.2. Modes opératoires

• Pour le chiffrement par flot, on génére autant de bits que nécessaire pour la clé

• Pour le chiffrement par blocs, même idée à un détail près… la clé est de taille fixe

4.3. ECB (electronic codebook)

Deux blocs identiques sont chiffrés de la même façon

4.4. Padding
• Pour les modes ECB, CBC, CFB il est nécessaire de compléter le message clair

• Le padding doit être réversible

◦ train de bits 100000…000

38
 ◦ séquence de k octets de valeur k (PKCS)

4.5. CBC (Cypher Block Chaining)

4.6. Application
• Le message suivant a été chiffré avec :

◦ AES-CBC

◦ la clé abe7

1664 f732 737c 3f51 6b65 3d5f 86d4 f471 71df 8391 4970 6f38 0ebe
1adb 14a1 e716 6281 dc59 83c2 907c 3e9a 8abc 5d43 3aae c816 b21e
9959 c86d 5826 5aa7 7494 e51f 3674 d5b9 5a19 3bae 2499 165e 967d
c27d 92ab 18c5 dfcb 23e4 39bd 5334 7e93 0f2d e18a d8de e0fe 702c
8e8b 0a89 e26a fb19 73cc 71cb f14e 9753 ba9e 9e44 d70d 16e0 2e60
cd5e fe74 09d4 f3ef 1a18 a9f4 1f12 1831 fc3f 59da 9df2 00f6 3f12
948a 8c0e

4.7. Indices
Voici les tables AES précalculées pour la clé abe7

39
4.8. Indices

4.9. Indices

40
4.10. Vecteur d’initialisation
• Pour éviter deux premiers blocs identiques soient chiffrés exactement de la même façon, on
ajoute un vecteur d’initialisation

• L’IV n’a pas besoin d’être secret

• L’IV ne doit pas être prédictible

◦ Générateur pseudo-aléatoire de qualité cryptographique

◦ Chiffrer une suite prédictible

4.11. CFB (Cypher Feed Back)

4.12. OFB (Output Feed Back)

41
4.13. CTR (Counter)

4.14. Génération de compteurs

• CTR nécéssite une suite de blocs compteurs à usage unique

• Incrémenter le compteur pour obtenir une suite de blocs distincts

4.15. Application
• On sait que le message ci-dessous a été chiffré en CTR avec la clé b33f

42
 • Toutes les données liées à AES sont données dans le slide suivant

• Voici le message à déchiffrer

feed b413 5148 725a a122 976b 272e 1163 b778 c168 526d db65 706b 472d
b269 3e26 f268 8062 5b7c 706e b246 cb44 3e1e 0250 eb49 ce4f 1a52 cf14
7259 5f54 e955 2845 ea57 8f13 5f5d 2b5b bb61 8161 2b7c 4e78 a17f dd2d
126e cd24 7362 5d72 ff67 3b75 ae6d 8b23 7d45 2f2e

4.16. Tables de calculs liées à AES dans CTR

4.17. CTR est fragile

• Voici une discussion interceptée en AES-CTR avec la même clé de chiffrement utilisée à chaque
fois.

• Essayez de percer le mystère !!

Yohan:fac3eb8d0497bcc3158c0c8fc18ffdc809ce5280c889bdc98b9a6192b79a5a853493979f089f
aa96778819d7c195f2d846de67878284b68b928d2792f8ab7ecd6da7
Mathieu:fac3f79901c2a582319e5897c79ffa9c49806cc58188f887d8962880b78b56836792d2dc14
82b59a39895794c28ef39d079f799b8291
Yohan:fac3fd8a0e87ab97319b1d8acd84fcc40883798c9bc4bc9cd88c6794e7db5dd0269f979a069b
b3d32791129ec9dae39d078e72818e80a4d9939a6198eea5
Yohan:fac3fb891d9ae8922d845894888be59d5b8b6a8a8690f890d89b7a8ee28d52822898c3dc129c
a2d324920583c2dae39d078c72968899a79c998c62df
Mael:fac3ed820dc2ba863b821597cd84fb8d08cf
Yohan:fac3f79901c2a9c3348c5896dd8ffb9c418176c5dfc4bc8cd8832884ef9417922898c28f479b
abd3319c02838788e2884890738782d49b9c8196
Yohan:fac3fd98488ba4c321cd19c7d886ed8146ce7c80c896bd9997817b84e4db5491249ed29914dc

4.18. Comparaison des modes opératoires

Les critères de comparaison

• Auto-synchronisation

• Accès randomisé

• Chiffrement ou déchiffrement parallélisable

• Capacité à supporter des erreurs

43
4.19. Quel algorithme choisir ?
• Pour garantir la confidentialité

◦ AES-256-CBC avec IV aléatoires

◦ AES-256-CTR avec nonce distincts

• Attention la confidentialité ne suffit pas toujours !!!

4.20. Quelques exemples en pratique : Python

Utilisation de la bibliothèque pycryptodome

key = get_random_bytes(32)
iv = get_random_bytes(16)

# Message à chiffrer
message = b"Hello, World!"

# Création d'un objet AES en mode CBC avec la clé et le vecteur d'initialisation
cipher = [Link](key, AES.MODE_CBC, iv)
# Chiffrement du message avec padding
ciphertext = [Link](pad(message, AES.block_size))

cipher = [Link](key, AES.MODE_CBC, iv)

decrypted_message = unpad([Link](ciphertext), AES.block_size)

4.21. Quelques exemples en pratique : Java

Utilisation de la bibliothèque Bouncy Castle

public class ProgrammeExtrait {

private static final int keyLength = 32;

private static final SecureRandom random = new SecureRandom();

public static void main(String [] args) throws Exception {

[Link](new BouncyCastleProvider());

String plaintext = "hello world";

String ivStr = "0123456789abcdef";
SecretKey secretKey = generateKey();
byte [] ciphertext = encrypt(secretKey,ivStr,plaintext);
String recoveredPlaintext = decrypt(secretKey,ivStr,ciphertext);

[Link](recoveredPlaintext);
}

44
 private static byte [] encrypt(SecretKey key, String ivStr,String plaintext)
throws Exception {
Cipher cipher = [Link]("AES/CBC/PKCS7Padding");
byte[] iv = [Link]("US-ASCII");
[Link](Cipher.ENCRYPT_MODE, key, new IvParameterSpec(iv));
return [Link]([Link]());
}

private static String decrypt(SecretKey key, String ivStr,byte [] ciphertext)

throws Exception {
Cipher cipher = [Link]("AES/CBC/PKCS7Padding");
byte[]iv = [Link]("US-ASCII");
[Link](Cipher.DECRYPT_MODE, key, new IvParameterSpec(iv));
return new String([Link](ciphertext));
}

private static SecretKey generateKey() throws Exception {

byte[] keyBytes = new byte[keyLength];
[Link](keyBytes);
SecretKeySpec keySpec = new SecretKeySpec(keyBytes, "AES");
return keySpec;
}
}

4.22. Le plus compliqué dans l’histoire

• Ce n’est pas forcément d’utiliser les algos

• C’est plutôt de manipuler les bases azotées de l’informatique : octets

• D’ailleurs, sauriez vous déchiffrer les octets ci-dessous ? (indice : le résultat sera un fichier et on
fonctionne en CBC)

Clé utilisée : 836a5ec73a8b713711d15e3adb8388cb94fb9ea0e5e509c70a05e0b74603f6ac

Vecteur d'initialisation (IV) utilisé : 68f4aa5e7e8cf1dc7f9a6f468ca0d026

dc3678ac3ba8384c0a04245aac6cfae6b5a860d90f7d2ab11849daec34573cb2682b8bcb5240a791790
03e4227347102
1b5c3016c3b5a314337211b348d799cb19c1e28ef8d3c196534cad97c09c925fa5199e946f10782f31a
40b7c3de5506c
7e16207b68fb37fb4930e991f07f9f0aed593564c36c25fbf9a703ccf54d4e07fbc323e9c66d3b3fdb0
be3d0e03f1085
bb375db22671f671299f789bf3dc9200bee14cac41b959528f7272a745f7a4ed8f3ceae300e13c94907
99c4ef48f16b7
ae49ca1b67a11c6afd339b53f4859ab432dfc37129fb4e33abc6a4c7d6bf42fd853770a2bc99b519253
3f08762c4ccad
a4b4bbc37e8d42cf0be8b7de3862cdfc26e6505b681d2ced1549f5f8315cbf99ce6010fc7f9e0e1e52b
e3a91abe92d61
2f53d99d6903887028619eabd6f203e2fc1fe050210a868c12675715bcea3861742578ee1f005f6276f

45
 0bb26ed7de9f6
5e1b433a507032374004a2564122bf231367c7c5f1b89e8a9b346b2dde2fdc6a53a74fa8f267c71bc55
d8c0941f2809a
cbf70d36c983a877695072d86b0bbd809c2445d0a0e3aeed88a34df7a03e11125ee03b42a84621f00b6
47ce826b819a3

4.23. Et si les algos étaient parfaits ?

• ça ne suffit pas pour autant

• Protocoles cryptographiques sont fondés à partir des primitives cryptographiques

• Les propriétés attendues sont en général :

◦ Confidentialité

◦ Intégrité

◦ Authenticité

◦ Non répudiation

4.24. Bilan sur les primitives cryptographiques jusqu’à

présent
• Cryptographie symétrique (à clé secrète)

• Cryptographie asymétrique (à clé publique)

• Fonctions de hachage de qualité cryptographique

• Codes d’authentification de messages (MAC)

• Algorithmes de signature numérique

46
Chapter 5. Intégrité des messages
5.1. Previously in Desperate Student’s Life
• Algo standart symétrique permettant de chiffrer des blocs de bits

• Des modes de chiffrement pour casser les analyses statistiques

• Finalement, comment peut on être sûr que :

◦ Le message provient d’une personne supposée

◦ Si tel est le cas, comment être sûr que le message n’a pas été modifié entre temps

• Après tout, un message est une suite de bits

5.2. MAC
Message Authentication Code

5.3. CBC-MAC
• Utiliser le dernier bloc d’un chiffrement comme MAC (avec une autre clé )

47
 • Possibilité de forger des messages valides pour des messages de taille variable → CBC-MAC non
sûr pour les messages de taille variable

5.4. Amélioration CMAC - NIST800-38B

5.5. Pause exercice

• Alice a la brillante idée de combiner AES-256- CBC avec AES-CBC-MAC.

• Munie d’une clé secrète K de 256 bits, elle chiffre un message M comme suit :

FBI ou non ?

5.6. Hachage
* t
• H: {0,1} → {0,1}

• Fonction qui associe une empreinte de taille fixe à une entrée de taille arbitraire

• Tables de hashage

• Propriété attendue : les valeurs prises par H doivent être uniformément réparties ; faible

48
 probabilité de collision H(m)=H(m')

5.7. Hachage cryptographique — propriétés attendues

pour H
• one-way : difficile de retrouver x à partir de H(x)

• résistance aux collisions : difficile de trouver x et y tels que H(x)=H(y)

• Indiscernable d’une fonction aléatoire

5.8. Construction Merkle-Damgard

5.9. Pause exercice

• Charli trouve que la construction MD ressemble beaucoup au chaînage CBC de la semaine
dernière.

• Il propose de prendre IV=0 et comme fonction de compression le chaînage d’AES-256 avec la clé
0.

• Montrer que cette fonction n’est pas du tout résistante aux collisions !

5.10. MD5 (RFC 1321)

• Inventé par Rivest en 1992

• Très populaire malgré une première faille en 1995

• Empreinte de 128 bits (blocs de 512 bits)

49
 • Conçu pour être rapide sur architecture 32 bits

• Padding : on ajoute un bit à 1 puis des 0 pour obtenir une taille congrue à 448 mod 512 et enfin
on ajoute la longueur initiale du message codée sur 64 bits.

5.11. Application MD5 sur images

md5sum *.png
c23bdb95d34d1d56c8a5e6845182b8b1 [Link]
d7df07f1874f3631632feeedd3cb869a [Link]

5.12. Mais…
Modifions quelque peu les images avec [Link]
[Link]

md5sum collision*.png
4905e947e3b9542011ab2c1e8721a78f [Link]
4905e947e3b9542011ab2c1e8721a78f [Link]

5.13. MD5 suite des ennuis

• On peut faire la même chose sur des programmes python, des PDF, etc

• Toutes les attaques sont basées sur : MD5(xyz) = MD5(xy’z)

50
• Le z dans le cas des PNG : concaténation des deux images mais l’interprétation globale donnera
soit l’une, soit l’autre

• Pour les curieux

◦ [Link]

◦ [Link]

5.14. MD5 — the end

5.15. SHA-1 et SHA-2

• Développé par la NSA vers 1995

• Empreinte de 160 bits pour SHA-1

• SHA-2 plus sûr mais moins rapide à calculer

51
5.16. SHA-1 MD5
• Même combat

• Toutes les attaques possibles en pratique sur MD5 le sont également sur SHA-1

5.17. Que faut il utiliser ?

• SHA-1 et MD5 sont désuets

• SHA-256 and co compromis raisonnables

• SHA-3 ?

5.18. HMAC : du hachage au MAC

• Principe : transformer toute fonction de hachage de qualité cryptographique en un code
d’authentification de message (MAC)

• HMAC-MD5

• HMAC-SHA-1

• HMAC-SHA256

5.19. HMAC : algorithme

52
5.20. Pause exercice
Un étudiant un peu fatigué de toutes ces notations résume le HMAC à la chose suivante : Oui ben il
suffit de prendre la clé K et de concaténer le texte à authentifier et utiliser une fonction de hachage
quelconque. En gros, MD5(K.M).

Expliquez en quoi il ferait mieux de relire la documentation de HMAC

53
Chapter 6. Canal sûr
6.1. Protocole cryptographique
Un protocole cryptographique est contruit à partir de briques, les primitives cryptographiques,
dans le but d’assurer un certain nombre de propriétés, typiquement

• confidentialité

• intégrité

• authenticité

• non répudiabilité

6.2. Confidentialité
• Assurer que seuls les deux parties ont accès aux données échangées

• Empêche l'écoute des données en transit

• Selon le contexte cette confidentialité peut être persistante dans le temps

6.3. Intégrité
• Assurer la correction et la consistance des données transmises

• Empêcher de modifier les données en transit

• Empêcher de forger de nouvelles données

• Selon le contexte ce contrôle d’intégrité peut se faire avec ou sans répudiabilité

6.4. Authenticité
• Permettre aux deux parties en présence de valider l’identité de l’autre partie

• Empêche les accès non autorisés mais aussi…

• Empêche des attaques du type homme du milieu

6.5. Quelques primitives cryptographiques

• Cryptographie symétrique (clé secrète)

• Cryptographie asymétrique (clé publique)

• Générateurs de nombres pseudo-aléatoires de qualité cryptographique

• Fonctions de hachage de qualité cryptographique

• Codes d’authentification de message (MAC)

• Algorithmes de signature numérique

54
6.6. Conception d’un protocole sécurisé
Alice et Bob ont échangé des clés secrètes de 256 bits et élu les algorithmes AES-CTR-256 et HMAC-
SHA-256. Ils souhaitent établir un canal sécurisé entre eux. Eve écoute les échanges sécurisés.

Proposez un protocole cryptographique qui permet d’assurer la confidentialité et l’intégrité des

échanges.

6.7. EtM : Encrypted Then MAC

6.8. E&M : Encrypt and MAC

6.9. MtE : MAC then Encrypt

55
6.10. Petit résumé
• Chaque mode de chiffrement/authentification propose des garanties

• Cependant en terme de sécurité globale, il est conseillé d’utiliser du EtM

• SSL fondé sur du MtE reste safe si ce dernier utilise du chiffrement par flots ou du CBC

• Quelques documents :

◦ Bilan de sécurité MtE, … : [Link]

◦ EtM ou MtE ? : [Link]

◦ Related Plaintext Chaining : [Link]

8_19.pdf

6.11. Modes AEAD

• Authenticated Encryption with Associated Data

• Proposer des modes opératoires qui apportent le chiffrement et le contrôle d’intégrité tout en
assurant la sécurité

6.12. Mode CCM

• CCM = CTR + CMC-MAC en mode MtE

• Recommandations du NIST : [Link]

[Link]

6.13. En pratique : VPN avec IPsec

• Virtual Private Network permet de créer une liaison sécurisée entre deux réseaux distants à
travers un réseau non sûr

56
6.14. Fonctionnalités
• Authentification : vérifier l’identité des deux extrémités du VPN par authentification mutuelle

• Contrôle d’intégrité : Empêcher la modification du flux réseau qui traverse le VPN

• Confidentialité : Empêcher l’écoute des données

• Technologie intéressante : IPsec en mode transport ou tunnel

6.15. IPsec
• RFC 4301

• Solution normalisée pour de déploiement de VPN IP interopérables

6.16. Composant d’IPsec

• Protocoles pour le transport de paquets

◦ Authentication Header (AH)

◦ Encapsulating Security Payload (ESP)

• Une famille d’algorithmes cryptographiques normalisés à combiner à ses protocoles

• Un protocole optionnel de gestion automatique des clés : IKEv2

• Un mécanisme type pare-feu pour décider des paquets qui passent par le tunnel et doivent être
encapsulés par AH ou ESP

6.17. AH et ESP
• Encapsulation de chaque paquet IP qui transite par le VPN, nouvelle entête IP + entête AH/ESP

◦ Charge utile du paquet IP en mode transport

◦ le paquet IP complet en mode tunnel

• Informations présentes dans l’entête

◦ SPI : Security Parameters Index

◦ SN : Sequence Number

◦ ICV : Integrity Check Value

◦ Pour en savoir plus : [Link]

6.18. IPsec in ESP Tunnel Mode

57
6.19. Security Policy Database
• Détermine la politique d’encapsulation IPsec du flux réseau

• Règle type pare-feu

spdadd [Link]/24 [Link]/24 any -P in

ipsec esp/tunnel/[Link]-[Link]/require;
spdadd [Link]/24 [Link]/24 any -P out
ipsec esp/tunnel/[Link]-[Link]/require;

6.20. Security Association Database

• Détermine la politique de sécurité à partir du SPI

58
• Security Association = protocoles + clés + …

add [Link] [Link] esp 1337

-E des-cbc 0xcafebabec00170ad
-A hmac-md5 "there is no cake";

59
Chapter 7. Comment partager un secret ?
7.1. Au-delà du chiffrement symétrique
• Etablir un canal sûr nécessite le partage d’un secret entre les deux parties (a priori)

• Comment fait on dans un environnement fermé avec beaucoup d’utilisateurs ?

• Comment fait on dans un environnement ouvert où les deux interlocuteurs ne se sont jamais
rencontrés ?

7.2. Distribution de clés centralisée

• Utiliser une autorité centrale, le centre de clé (KDC), pour partager les clés de sessions entre les
paires d’utilisateurs

• Tous les utilisateurs doivent faire confiance au KDC

• Un utilisateur n’a besoin que d’un secret partagé avec le KDC

7.3. Protocole de sécurité

• Ensemble de règles régissant le comportement d’individus pour répondre aux besoins d’une
application

• Quelques notations

7.4. Protocole de Needham-Schroeder

60
7.5. Protocole de Needham-Schroeder

7.6. En pratique
• Ce type d’algorithme permet de mettre en oeuvre des systèmes à authentification unique

• Le protocole Kerberos est un protocole d’authentification réseau normalisé reposant sur le

protocole de Needham-Schroeder

61
Chapter 8. Cryptographie clé publique
8.1. Cryptographie à clé publique
• Idée : briser la symétrie !

• Dans la vie, il existe de nombreux phénomènes pour lesquels l’opération inverse est plus
difficile que l’opération initiale

• Une clé publique distribuée librement permet de chiffrer les messages

• Une clé privée, gardée secrète, permet de déchiffrer les messages

• Vu sous un autre angle

◦ Si quelqu’un veut vous parler il achète votre cadenas que vous vendez à qui en veut.

◦ S’il veut vous parler, il reste à mettre un message dans une boîte qu’il scellera avec ce
cadenas (dont vous seul possédez la clé).

8.2. Fonction à sens unique avec trappe

• Une fonction f est une fonction à sens unique à trappe :

◦ si le calcul de f(x) est facile

◦ si retrouver x à partir de f(x) est calculatoirement impossible sans connaître la trappe (une
information secrète k)

• L’inverse g de f se calcule facilement à partir de k

• Communiquer f ne doit rien révéler sur g

• On ne sait pas si de telles fonctions existent ! lol

8.3. Quelques outils matématiques : Exponentiation

rapide
21
• Calculez 5 modulo 17 !

8.4. Quelques outils matématiques : Technique des

carrés successifs

62
8.5. Quelques outils mathématiques : Euclide étendu
• Calcul de l’inverse de 9 en base 50 ?

• trouver x tel que x*9 mod 50 = 1

• Attention 1/9 n’existe pas dans Z/nZ

8.6. Détail du calcul

8.7. Théorème d’Euler

• L’indicatrice d’Euler est le nombre d’entiers de 1 à n premiers avec n

63
8.8. Diffie Hellman
• Ou comment créer un canal sécurisé avec rien ou presque !

• Repose sur la difficulté à calculer des logarithmes discrets

• Seul ce protocole est sensible à des attaques type Man-in-the-middle

8.9. Des maths… oui encore

*
• Pour tout entier n >= 1 : {a | pgcd(n,a)=1 } avec la multiplication forment un groupe Zn
k k
• Groupe cyclique si n = p ou n = 2p avec p un nombre premier
k
• Racine primitive modulo n : pour tout m il existe un unique 0<k<n t.q. m mod n = g mod n

• k est le logarithme discret de m pour la base g module n

8.10. Protocole DH
• Données du protocole :

◦ n premier

◦ g non nul

◦ n et g peuvent être connus publiquement

a
1. Alice choisit a et transmet g mod n à Bob
b
2. Bob choisit b et transmet g mod n à Alice
a b b a
3. Alice et Bob calculent k = (g ) mod n = (g ) mod n

8.11. Mise en application

• Supposons n=841, g=627, a=137 et b=513
a b ab
• Calculez g , g et g

64
8.12. Exercice de réflexion
• Essayez d’imaginer le scénario de l’attaque de l’homme au milieu sur la version la plus épurée
de DH

• Donnez un exemple précis de scénario

8.13. Cryptographie à clé publique

• DH n’est pas un schéma de cryptographie à clé publique !

• Le premier schéma est RSA, publié en 1978 par Rivest, Shamir et Adleman, en cherchant à
montrer qu’il n’en existait pas

• Etant donné qu’on est sur DH, autant sauter un peu plus loin dans le temps… 1985

8.14. ElGamal
• Données du schéma : n premier et g non nul pouvant être publiquement connus
s
• Alice choisit une clé secrète s et calcule sa clé publique y=g (mod n)
k
• Pour chiffrer un message 1<m<n, Bob choisit aléatoirement k et transmet la paire : (c,d)=(g
k
mod n, m y (mod n))
s -1 sk -1 k
• Alice déchiffre le message en calculant : (c ) d=(g ) my =m (mod n)

8.15. Exercice
• Soient n=467, g=2, s=153, m=331, k=197

• Calculez y, c, d pour ensuite retrouver m

8.16. En pratique
• La cryptographie à clé publique est en générale plus lente à chiffrer que la cryptographie
symétrique

• On utilise des systèmes hybrides

◦ Une clé de session chiffrée avec chiffrement à clé publique

◦ Utilisation de la clé de session symétrique pour les échanges

65
Chapter 9. RSA
9.1. RSA
• Mis au point en 1977 au MIT par Ron Rivest, Adi Shamir et Leonard Adleman

• Crypto-système asymétrique

• Chaque participant possède deux clés :

◦ Une clé publique connue potentiellement par tout le monde

◦ Une clé privée connue uniquement par son possesseur

• Basé sur la difficulté du problème de factorisation de grands nombres premiers

9.2. RSA
1. Alice choisit deux grands nombres premiers p et q

◦ elle calcule n=p*q

◦ elle choisit un nombre e t. q. 1<e<(p-1)(q-1) premier avec (p-1)(q-1)

◦ elle calcule d tel que d*e=1 mod (p-1)(q-1)

2. Alice publie sa clé publique (n,e) et garde en secret (n,d)

9.3. RSA from Bob’s point of view

1. Alice a publié sa clé : (n,e)

2. Bob veut lui envoyer un message m

e
3. Ce dernier va alors calculer m mod n et envoyer le tout à Alice
e d
4. Alice reçoit c=m mod n. Elle calcule donc c mod n et obtient ainsi m

e de
9.4. Pourquoi c mod n = m mod n = m ?
ed 1+k(p-1)(q-1)
1. m mod n = m mod n
ed k(p-1)(q-1)
2. m mod n = m* m mod n
ed (p-1)(q-1) k
3. m mod n = m* (m mod n) mod n
ed k
4. m mod n = m* (1) mod n d’après Euler
ed
5. m mod n = m

9.5. A vous de jouer !

• La clé publique d’alice est (77,13)

• Calculez sa clé privée

66
• Déchiffrez le message 8

• On pourra s’aider des carrés successifs modulo 77 : 8, 64, 15, 71, 34, 64,…

9.6. Schéma RSA dit Textbook

n
• Gen : sur l’entrée 1 , générer deux nombres premiers de n bits p et q et deux paramètres d et e
pour obtenir les clés (N,e) et (N,d) avec N=pq
e
• Enc : étant donnés (N,e) et m calcule c=m (mod N)
d
• Dec : étant donnés (N,d) et c calcule m=c (mod N)

• Cette façon d’utiliser RSA n’est pas sûre

• Et encore pire en mode ECB

9.7. RSA-OAEP
• Optimal asymmetric encryption padding

• Padding aléatoire

• RSA-OAEP est sémantiquement sûr sous l’hypothèse RSA

67
Chapter 10. Signatures
10.1. Schéma de signature numérique
• Repose sur la cryptograhie à clé publique

• Permet contrôle d’intégrité et authentification

• La signature dépend

◦ du contenu du message

◦ de l’identité du signataire

• Elle doit être non falsifiable et non répudiable

10.2. A quoi ça sert, on a MAC ?

• Pas besoin de secret partagé

• Pas besoin d’une clé par interlocuteur

• La preuve de validité est opposable à un tiers

• Par contre, les codes MAC sont généralement plus courts et calculables plus rapidement

10.3. Finalement c’est juste l’inverse ?

• Signer c’est l’inverse de chiffrer non ?

◦ Sur le papier oui.

i. Pour signer m je le chiffre avec ma clé privée

ii. Quiconque peut alors vérifier le contenu en appliquant ma clé publique

◦ En pratique, non pas exactement

10.4. Formellement

10.5. Hache et signe

68
10.6. Schéma RSA dit Textbook
n
• Gen : sur l’entrée 1 , générer deux nombres premiers de n bits p et q et deux paramètres d et e
pour obtenir les clés (pq,e) et (pq,d)
d
• Sign : étant donnés (N,d) et m calcule s=m (mod N)
s
• Vrfy : étant donnés (N,e) et m calcule m=^? e^ (mod N)

10.7. Sécurité de RSA Textbook

• Soient s et s' les signatures respectives des messages m et m'

• On peut construire la signature de m.m' en calculant s.s'.

z z z
• En effet : (x*y) = x * y (mod N)

10.8. RSA-FDH : sécurité grâce au hachage

69
Chapter 11. Protocoles : résumé et failles
logiques
11.1. Rappels
• Protocole : ensemble de règles régissant le comportement d’individus pour répondre au besoin
d’une application

• Notations

◦ M.M' : concatenation des messages M et M'

◦ scrypt(K,M) : chiffrement symétrique de M avec la clé K

◦ crypt(K,M) : chiffrement asymétrique de M avec la clé publique K

◦ sign(K,M) : signature du message M avec la clé privée K

◦ hash(M) : hachage d’une donnée M avec une fonction de hachage

◦ mac(K,M) : calcul d’un MAC à partir d’une donnée M et d’un secret partagé K

11.2. Votre expertise ?

1. A → B : [Link](M)

◦ Le secret est préservé ?

◦ L’authentification est garantie ?

◦ L’intégrité du message est garantie ?

11.3. Votre expertise ?

1. A → B : [Link](K,M)

◦ Le secret est préservé ?

◦ Le message a été composé par A ?

◦ Le message a été envoyé par A ?

◦ L’intégrité du message est garantie ?

11.4. Votre expertise ?

1. A → B : [Link](prvA,M)

◦ Le secret est préservé ?

◦ Le message a été composé par A ?

◦ Le message a été envoyé par A ?

◦ L’intégrité du message est garantie ?

70
11.5. Votre expertise ?
1. A → S : crypt(pkS,A.B)

2. S → A : crypt(pkA,[Link](prvS,pkB))

• Peut-on garantir ici que la clé récupérée PkB sera bien la clé de B sachant que S est une entité
sûre ?

11.6. Votre expertise ?

• Hypothèse : Tout le monde connaît ici la clé publique de tout le monde

1. A → B : crypt(pkB,[Link])

2. B → A : crypt(pkA,[Link])

3. A → B : crypt(pkB,NB)

• Que comprenez vous de ce protocole ? Quelles propriétés sont attendues ici ?

11.7. Votre expertise ?

• Représentez ici sous forme de protocole un échange Diffie Hellman pour mettre au point une
clé partagée KAB et l’envoi d’un secret de A vers B

• Donnez l’attaque de l’homme au milieu

71