Master Pro Ingenierie Mathematique Cryptographie

Description

Niveau: Supérieur, Master
Master Pro – Ingenierie Mathematique – Cryptographie A.E.S. (Advanced Encryption Standard) CHAPITRE 4. A.E.S. (Advanced Encryption Standard)

• critiques de la communaute cryptographique


• table d'addition du corps f2


• reste modulo


• protocole


• polynome p1


• methodes de substitution-permutation


• table de multiplication du corps f2

Sujets

• Protocole

Informations

• Publié par: cidur
• Nombre de lectures: 59
• Langue: Français

Extrait

MasterPro–Ing´einreeiaMhte´amite–quypCrgrtohiap E.A e (.S.avdAdecnyptiEncrandaonStdr)

4.

A.E.S. (Advanced Encryption Standard)

http://math.univ-lyon1.fr/~roblot/masterpro.html

CHAPITRE

etPrMsaieManierng´ero–IpyrC–euqitame´ht .(.S.E e A hiapgrto tSnoadna P )dr se´r vaAdednccrEntiyp entation

Histoire .En1997,leNISTannoncelacre´ationd’unnouveauprotocole decryptographie`l´esecr`etenomme´A.E.S.etlanceunappeld’offre. a c En 1998, quinze protocoles candidats sont retenus et soumis aux critiques delacommunaute´cryptographique.Enoctobre2000,leNISTannonce le choix du protocole Rijndael cr´ee´parJ.DaemenetV.Rijmen.Ce protocole remplace D.E.S. comme standard du NIST (norme FIPS 197).

Bloc . Codage par blocs de 128 bits.

Cle´ .Cl´ede128(10rondes),192(12rondes)ou256bits(14rondes).

Spe´cificite´s .Grander´esistance`atouteslesattaquesconnues;tre`s granderapidite´pourlecryptageetled´ecryptage;utilisedesme´thodes de substitution-permutation et non les diagrammes de Feistel (ou ge´n´eralisations);poss`edeunev´eritablestructuremathe´matique.

´emaMatherie´enirgpapyot–erCituq ncvaAd.(.S.E e A hi natSnoitpyrcnEde orPrgnI–Metsa addr D ) e´orlumenetd’uneronde

MixColumns : Chaquecolonneestremplace´eparunenouvellecolonne obtenueentransformantlacolonneenunpolynˆomeetenmultipliantpar unpolynˆomefix´e;

AddRoundKey : Chaqueentr´eeestremplac´eeparle ou exclusif entre ` cetteentr´eeetl’entr´eecorrespondantedansunematrice 4 × 4 construit a partir de la cl´ e .

Lesquatree´tapesd’uneronde

A.E.S. ope`resurdesmatrices 4 × 4 dontlesentr´eessontdesmotsde8 bits.Ond´ecoupelemessageclairen 16 blocs de 8 bits et on remplit en allantdehautenbasetdegauche`adroite.

SubBytes : chaqueentr´eeestremplac´eparunautremotde8bits donn´eparuntableaudecorrespondance;

ShiftRows : Lesentr´eessontde´cale´essuivantunde´calagecirculaire`a gauched’unnombredecasesd´ependantdelaligne;

xtensionsdeF 2

Extensions de F 2

Polynoˆmesirre´ductibles .Unpolynoˆme P ( X ) ∈ F 2 [ X ] etdedegre´ ≥ 1 est irr´eductible s’iln’existepasdeuxpolynoˆmes P 1 ( X ) , P 2 ( X ) ∈ F 2 [ X ] , dedegr´e ≥ 1 , et tels que P ( X ) = P 1 ( X ) P 2 ( X ) . Pour tout d ≥ 1 ,ilexistedespolynoˆmesirr´eductiblesdedegre´ d .

Le corps F 2 . L’ensemble F 2 = { 0 , 1 } des entiers modulo 2 est un corps (lamultiplicationcorresponda` ∧ etl’additiona` ⊕ ).

Les extensions de F 2 . Pour P ( X ) ∈ F 2 [ X ] dedegr´e d ≥ 1 et irr´eductible , l’ensemble F 2 [ X ] / ( P ( X )) estuncorps,note´ F 2 d . Sa structure ned´ependpasduchoixdupolynoˆme P ,maisjustedudegr´e d .

Anneaux quotients . Pour P ( X ) ∈ F 2 [ X ] dedegre´ d ≥ 1 , le quotient F 2 [ X ] / ( P ( X )) estl’ensembledespolynˆomesdedegr´e < d avec l’addition usuelle et pour la multiplication, on fait la multiplication usuelle et on prend le reste modulo P .

yptionStandard) E S.(.dAavcndenErc ypCrgrtohiap .E e A aMeie´htitam–euqro–IterPnierng´eMsa

h´emeMatue–Catiq–onIrerPeiir´gne andv(AS.ryncdEce argotpyr .E.A eihpstMa arnd Ex d)iopttanS 2 Fedsnetsnoi

2

Exercice sur les extensions de F

5 6 7

1 2 3 4

Construire la table d’addition du corps F 2 [ X ] /P 2 ( X ) . Construire la table de multiplication du corps F 2 [ X ] /P 2 ( X ) . Montrer que l’application X mod P 1 7→ X 2 + 1 mod P 2 est un isomorphisme entre les deux corps.

Trouverunpolynoˆme P 1 ( X ) ∈ F 2 [ X ] dedegre´ 3 etirr´eductible. Construire la table d addition du corps F 2 [ X ] /P 1 ( X ) . ’ Construire la table de multiplication du corps F 2 [ X ] /P 1 ( X ) . Trouverunautrepolynˆome P 2 ( X ) ∈ F 2 [ X ] dedegr´e 3 et irr´eductible.

Exemple . { 2 A } + { 37 } = ( X 5 + X 3 + X ) + ( X 5 + X 4 + X 2 + X + 1) = X 4 + X 3 + X 2 + 1 = { 1 D } { 2 A } × { 37 } = X 6 + X 5 + X 4 + X 2 + X + 1 = { 77 }

Corps A.E.S. . On travaille dans le quotient F 2 [ X ] /R ( X ) o`u R ( X ) est lepolynoˆmedeRinjdael(irr´eductiblesur F 2 ) R ( X ) = X 8 + X 4 + X 3 + X + 1

Repr´esentation . Mots de 8 bitscorrespondent`adesmotsdedeux chiffreshexad´ecimauxet`adespolynoˆmesde F 2 dedegr´e ≤ 7 . Exemple . On identifie { 9 A } = 1001 1010 = 1 ∙ X 7 + 0 ∙ X 6 + 0 ∙ X 5 + 1 ∙ X 4 + 1 ∙ X 3 + 0 ∙ X 2 + 1 ∙ X + 0

Le corps A.E.S.

ireitaMeme´hqita–CueptryraogiephMasterPro–Ing´en proceL )d .S.E.As .SA(.A.EecEdvdnaptioncryndarnSta

Calculer { 2 A } × { 37 } par cet algorithme.

4

Calculer { 48 } × { 3 F } par cet algorithme.

5

Calculer la transformation sur un mot de 8 bitscorrespondanta`la multiplication par { 00 } , { 01 } , { 02 } .

2

Ende´duireuneme´thodeefficacepourmultiplierdeuxe´l´ementsdu corps A.E.S.

3

Exercice sur le corps A.E.S.

1

Montrer que l’addition correspond au “ou exclusif” sur les mots binaires.

.Asp.S.EL )dr roce dAavcndeA e E.S.(.onStandaEncrypti I–ore´gnsaMPretotrgpaihuq–erCpyth´ematinierieMa

{ x } 7→ A ( { x } − 1 ) + { 63 }

Construction .Latransformationestdonn´eepour { x } dans le corps A.E.S. par { 00 } 7→ { 63 } , et pour { x } non nul par

Description . La S -boˆıte de A.E.S. est une permutation sur l’ensemble des mots de 8 bits.Elleestconstruiteenutilisantunefonctionalge´brique surlese´le´mentsducorpsA.E.S.

L’e´tape SubBytes

Remarque. C’estlaseule´etapenon-line´aireduprotocoleA.E.S.

Exercice. Calculer l’image de { 02 } par la S -boıˆte.

(bitslusdedroite`agauche)

y i = x i ⊕ x i +4 mod 8 ⊕ x i +5 mod 8 ⊕ x i +6 mod 8 ⊕ x i +7 mod 8

ou` A l’applicationline´aired´efiniepar A ( { x } ) = { y } avec

pyitnotScndenErc esquatre andard) LE.Ae.S.ate´dsep orI–etPrMsath´eieManierng´ergotpyrC–euqitam vaAd.(.S.E e A hiap

rieMath´Ing´enieC–yrtpgometaqieurets–orPaM uatrLesq ard)tand .E.Sed.Apase´ete dv(AS.E.A. iephra SnoitpyrcnEdecna

-7 C5 F0 CC 9A A0 5B 85 F5 17 88 5C A9 C6 0E 94 68

-8 30 AD 34 07 52 6A 45 BC C4 46 C2 6C E8 61 9B 41

-9 01 D4 A5 12 3B CB F9 B6 A7 EE D3 56 DD 35 1E 99

-A 67 A2 E5 80 D6 BE 02 DA 7E B8 AC F4 74 57 87 2D

-3 7B 7D 26 C3 1A ED FB 8F EC DC 0A 6D 2E 66 11 0D

-4 F2 FA 36 18 1B 20 43 92 5F 22 49 8D 1C 48 69 BF

-5 6B 59 3F 96 6E FC 4D 9D 97 2A 06 D5 A6 03 D9 E6

-6 6F 47 F7 05 5A B1 33 38 44 90 24 4E B4 F6 8E 42

-F 76 C0 15 75 84 CF A8 D2 73 DB 79 08 8A 9E DF 16

-B 2B AF F1 E2 B3 39 7F 21 3D 14 62 EA 1F B9 E9 0F

-C FE 9C 71 EB 29 4A 50 10 64 DE 91 65 4B 86 CE B0

-D D7 A4 D8 27 E3 4C 3C FF 5D 5E 95 7A BD C1 55 54

-E AB 72 31 B2 2F 58 9F F3 19 0B E4 AE 8B 1D 28 BB

Exemple. { A 8 } est transforme en { C 2 } ´

Notation . La permutation de SubBytes estdonn´eeparla S -boıˆte ci-dessous.

L’e´tape SubBytes (suite)

-2 77 C9 93 23 2C 00 AA 40 13 4F 3A 37 25 B5 98 89

-1 7C 82 FD C7 83 D1 EF A3 0C 81 32 C8 78 3E F8 A1

0 63 CA B7 04 09 53 D0 51 CD 60 E0 E7 BA 70 E1 8C

0- 1- 2- 3- 4- 5- 6- 7- 8- 9- A- B- C- D- E- F-