Plan

Table des matières

1 Introduction à la sécurité et à la cryptologie 21.1 Dénitions et exemples . . . . . . . . . . . . . . . . . . . . . . . . 21.2 Sécurité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.3 Criminalité informatique . . . . . . . . . . . . . . . . . . . . . . . 31.4 Apports de la cryptographie à la sécurité . . . . . . . . . . . . . 8

2 Cryptosystèmes et science de la cryptologie 112.1 Dénitions et objectifs . . . . . . . . . . . . . . . . . . . . . . . . 112.2 Cryptographie historique . . . . . . . . . . . . . . . . . . . . . . . 122.3 Sûreté d'un chirement, Théorie de Shannon, secret parfait . . . 172.4 Cryptosystèmes à clé secrète partagée . . . . . . . . . . . . . . . 192.5 Cryptosystèmes à clé publique . . . . . . . . . . . . . . . . . . . 262.6 Hachages et schémas de signatures . . . . . . . . . . . . . . . . . 332.7 Certicats, gestion des clés . . . . . . . . . . . . . . . . . . . . . 39

3 Sécurité informatique et réseaux 52

4 Mathématiques utiles pour la cryptologie 524.1 Arithmétiques modulo . . . . . . . . . . . . . . . . . . . . . . . . 524.2 Théorème de Fermat ; Algorithme(s) d'Euclide . . . . . . . . . . 544.3 Probabilités discrètes . . . . . . . . . . . . . . . . . . . . . . . . . 55

5 Bibliographie 57

Introduction INFO913 : Cryptologie et sécurité informatique Deux points de vue

1. cryptologie, application à la sécurité informatique et réseaux

2. sécurité informatique et réseaux, utilisation de la cryptologie

Evaluation

1. contrôle continu : TPs

2. exposé sur un thème précis

Déroulement : Cours (9× 1, 5h), TD (2× 1, 5h), TP (3× 3h) Plan général

1. Introduction à la sécurité et à la cryptologie

2. Cryptologie

3. Sécurité informatique et réseaux

http ://www.lama.univ-savoie.fr, et rajouter /wiki, suivre INFO913

1 Introduction à la sécurité et à la cryptologie

1.1 Dénitions et exemples

Sécurité informatique Ensemble des moyens techniques, organisationnels, juridiques et humainsnécessaires et mis en place pour conserver, rétablir, et garantir la sécuritéde l'information, du système d'information et des systèmes et ressourcesinformatiques.

Notamment, on veut préserver l'intégrité de l'information la condentialité de l'information la disponiblité des systèmes

Systèmes informatiques soumis à des menaces utilisateur du système personne malveillante programme malveillant sinistre (vol, incendie, dégât des eaux)

Cryptographie et cryptanalyse[Source Wikipedia]

Denition 1 (Cryptographie). La cryptographie est une des disciplines de lacryptologie s'attachant à protéger des messages (assurant condentialité, au-thenticité et intégrité) en s'aidant souvent de secrets ou clés.

Denition 2 (Cryptanalyse). La cryptanalyse s'oppose, en quelque sorte, à lacryptographie. En eet, si déchirer consiste à retrouver le clair au moyen d'uneclé, cryptanalyser c'est tenter de se passer de cette dernière.

Cryptographie : outil pour la sécurité informatique

1.2 Sécurité

Critères de sécuritéMise en place de solutions de sécurité pour satisfaire

disponibilité : probabilité de bon fonctionnement, accessibilité, continuité deservice

intégrité : certication de la non-altération des données, traitements et services

condentialité : protection des données contre une divulgation non autorisée

authentication : vérication de l'identité de l'utilisateur et de ses autorisa-tions

non-répudiation : imputabilité, traçabilité, auditabilité

2

Domaines d'intervention de la sécuritésécurité physique environnement humain (politique de sécurité, éducation, charte) environnement matériel (incendie, dégâts des eaux, protection des salles,sauvegardes, alimentations électriques)

sécurité de l'exploitation hôte (système d'exploitation à jour, authentication)

sécurité logique données (accès aux chiers, autorisations, chirements, sauvegarde)

sécurité applicative applications (virus, chevaux de troie, espiogiciels, spam, restrictions etlocalisations des applications)

sécurité des télécommunications réseau interne (protocoles sécurisés, dimensionnement) alentours (pare-feu, vpn, nomadisme)

Menaces informatiques

menace : action susceptible de nuire

vulnérabilité ou faille : niveau d'exposition face à une menace dans un cer-tain contexte

contre-mesure ou parade : ensemble des actions mises en oeuvres en pré-vention d'une menace

attaque : exploitation d'une faille (d'un syst info) à des ns non connus del'exploitant du système et généralement préjudiciables

en permanence sur Internet par machines infectées rarement pirates

Motivations des attaques intrusion dans le système vol d'informations industrielles (brevets), personnelles (bancaires), com-merciales (contrats), organisationnelles

troubler le bon fonctionnement d'un service (déni de service, defacing) utiliser le système comme rebond pour une autre attaque utiliser les ressources d'un système (ex : bonne bande passante)

1.3 Criminalité informatique

Crime informatique, cybercrime Crime informatique : délit où le système informatique est l'objet du délitet/ou le moyen de le réaliser.

Cybercrime : forme du crime informatique qui utilise Internet en 2007, la cybercriminalité pèse 7,1 milliards de dollars aux USA Typologie : malveillance, erreur, accident Cibles : états, organisations, individus

3

Vol d'identité, Chantage, Fraude nancière, détournements de fonds, volde biens virtuels, atteinte à la dignité, dénonciation calomnieuses, espion-nage, cyberterrorisme, désinformation, apologies de crimes, escroqueries,atteinte aux mineurs, atteinte à la vie privée, incitation à la haine raciale,. . .

Internet : un facteur aggravant dématérialisation des acteurs du délit, des objets du délit vulnérabilité : complexité des infrastructures informatique et réseaux automatisation, réalisation à grande échelle ⇒ ubiquité, anonymat immatérialité : information numérique peut être détruite, modiée, usur-pée

disponibilité d'outils, paradis numériques dépendance des états/organisations à l'informatique ⇒ facteur de risque⇒ cyberterrorisme

Typologie des attaques accès physique : coupure électricité, vol de disque dur, écoute trac réseau,récupération de matériels

interception de communications : vol de session, usurpation d'identité,détournement de messages

polupostage ou spam (98 % des mails) dénis de services : faiblesse de protocoles TCP/IP, vulnérabilité de logicielsserveurs

intrusions : maliciels (virus, vers, chevaux de Troie), balayage de ports,élévation de privilèges, débordements de tampon

trappes : porte dérobée dans un logiciel ingénierie sociale : contact direct de l'utilisateur attention aux attaques par rebond : l'utilisateur complice peut voir saresponsabilité engagée.

Logiciels malveillants : Virus, Vers, troyens

Virus Tout programme capable d'infecter un autre programme en le modiantde façon à ce qu'il puisse se reproduire

Brain (premier sur PC en 1986), Netsky (2004, lit chiers EML, HTMLpour se propager par email), Sobig-F (2003, contient un serveur SMTP)

Infecte : Programmes, documents, secteurs de boot

Ver (Worm) Programme se propageant à travers le réseau

Blaster (Août 2003, faiblesse RPC Windows), Welchia (qqs jours après,élimine Blaster)

Troyen ou Cheval de Troie Programme à l'apparence utile mais cachant ducode pour créer une faille dans le système (backdoor)

BackOrice, GrayBird (soi-disant nettoyeur de Blaster)

4

Porte dérobée (ou backdoor) Fonctionnalité inconnue de l'utilisateur, qui donneun accès secret au logiciel/système

Trusting Trust (1984), noyau Linux (2003)

Machine zombie ordinateur contrôlé à l'insu de son utilisateur par un pirateinformatique (suite à une infection par ver/cheval de troie). Sert de rebond.

Botnet Réseau de machines zombies. Utile pour lancer des attaques de dénide service ou spams

Bombes logiques Programme se déclencheant suite à un événement particu-lier (date, signal distant)

CIH/Chernobyl (déclenchement 26 avril 1999, 26 avril 1986)

Virus mutants réécriture de virus existants

Virus polymorphes modie son apparence, pour ne pas être reconnu

Rétro-Virus attaque les signatures des antivirus

Virus boot Virus s'installant sur un secteur d'amorçage (disquette, disque)

Virus d'applications (ou de document/macros) Programme infectant un do-cument contenant des macros, exécutable par une application : VBScript

Concept (1995), Bubbleboy (1999, achage du mail)

Antivirus Logiciel de détection et d'éradication de virus et vers

Méthodes : dictionnaires, heuristiques, comportements suspects, émula-tion (bac-à-sable)

scanneurs sur accès : examine les chiers/programmes à chaque accès scanneurs à la demande : examine les disques/chiers/programmes suiteà une demande

Spywares : espiogiciels

Espiogiciel Programme collectant des données sur un utilisateur, les envoyantà une société en général pour du prolage souvent avec des freewares ou sharewares intégrés (PKZip, KaZaA, Real Player) ou externes souvent légaux (dans la licence) parades : ne pas installer de logiciels ( !), antisypwares, rewall

keylogger enregistreur de touches : enregistrement des touches à l'insu de l'uti-lisateur. dispositif d'espionnage. Souvent un logiciel.

dongle version hardware (ex : KeyKatch)

5

Logiciels malveillants : Quelques statistiques [Source Rapport Sophos 2005 sur la gestion des menaces à la sécurité] vandalisme ludique cède la place à la criminalité organisée 1 message sur 44 infecté par un virus (n nov 2005, 1 sur 12, ver Sober-Z) Fin décembre 2005 : BD Virus Sophos a 114000 virus, vers et autres,15900 nouveaux en 2005

Méthodes de propagation : connexion directe via le réseau 66,8 %, piècesjointes 15,1%, chat 9,2 %, poste à poste (P2P) 4,5%, navigation web2,4%

Windows est la cible (plus que) majoritaire Ordinateur équipé de Windows sans protection : risque de contamina-tion 95% au bout d'une heure (SOPHOS)http://www.sophos.com/security/top-10/

http://www.symantec.com/

Quelques questions relatives à la sécurité Quels sont vos droits et devoirs vis-à-vis du système informatique de l'uni-versité ? Participez-vous à sa sécurité ?

Quelles sont les données ou applications les plus critiques de l'université ? Y a-t-il un risque d'infection en laissant simplement son ordinateur alluméconnecté par Internet ?

Pourquoi ne peut-on fermer une machine à toute communication exté-rieure ?

Est-ce qu'un téléphone mobile peut être infecté ? Comment un programme malicieux fait-il pour se rendre invisible aprèsinfection ?

Comment un virus fait-il pour ne pas infecter deux fois le même chier ? Quelles sont les motivations qui conduisent une personne à écrire un logi-ciel malveillant ?

Menaces nouvelles

Social engineering usage de ressorts psychologiques pour obtenir d'un tiersinformation ou données⇒ fraude, intrusion réseau, espionnage industriel,vol d'identité.

Phishing/hameçonnage Arnaques via internet, usurper une identité able(genre banque), redirection vers site pirate ⇒ données bancaires, mots depasse

6

http://www.mabanque.com@members.unsite.com/

http://www.mabanque.com.unsite.net/

Pharming (empoisonnement DNS) exploite une vulnérabilité pour rediger letrac Internet d'un site Web vers un autre. Complémentaire de chevauxde Troie, spywares et phishing.

Exemple : americanexpress.com, fedex.com, msn.com, Trendmicro.com(vulnérabilités dans le serveur DNS de Windows NT4 et Windows 2000,depuis corrigées).

Slamming fausse facture de renouvellement de nom de domaine et contraintepour l'achat de noms de domaines proches, faux annuaires professionnels

Vishing (VoIP + phishing). Serveurs VoIP appelant des numéros xes, redi-rection vers boîte vocale informant d'anomalie, invitation à contacter unserveur vocal où il donnera ses coordonnées bancaires.

Ransomwares code malveillant (virus ou cheval de troie) cryptant certainesdonnées, exige une rançon après pour le déchirement.

Exemple : Gpcode, scanne .xls .doc .txt .rtf ...

Cross Site Scripting (XSS) vulnérabilités dans serveur/app WEB pour insé-rer du code dans une page html renvoyée dynamiquement

Redirection vers un autre site, vol d'identiant de session

Injection de code vulnérabilités dans serveurs/apps (SQL,WEB/XSS, LDAP

SELECT * FROM utilisateurs WHERE nom="\$nom";// Saisie de : "toto" OR 1=1 OR nom="titi"SELECT * FROM utilisateurs WHERE nom="toto" OR 1=1 OR nom="titi";

Chires et évolutions des menaces Pertes et typologie des plaintes référencées par l'I3C (USA)

7

Plus de 85% des plaintes portent sur moins de 1000 $ (en 2004) Plus de 86% des plaintes portent sur moins de 5000 $ (en 2006)

Evolution des menaces informatiques dans le monde de 2004 à 2005Menaces Attaques 2004 Attaques 2005Phishing 18,0 % 25,0 %

Virus et vers 68,6 % 66,6 %[Source CompTIA]

Nombres d'incidents rapportés au CERT1998 1999 2000 2001 2002 20035000 11000 22000 53000 85000 138000

Parades : Formation utilisateurs Antivirus et/ou antispyware Filtre antiphishing Contrôler les certicats des sites

1.4 Apports de la cryptographie à la sécurité

Cryptographie et critères de sécurité Satisfaire les objectifs de sécurité via la cryptographie : condentialité,intégrité, Authentication, non-répudiation, disponibilité ?

Outils : chirement, signature, fonction de hachage

8

Chirement symétrique ou à clé secrète Chirement de données avec une clé secrète K chirer : transforme un message clair M en un message chiré C =

dK(M) avec une clé K déchirer : transforme un message chiré C en un message clair M =

eK(C) contraintes : dicile de déduire M de C sans K condentialité des données pour une personne condentialité d'un message entre 2 personnes partageant cette clé

en clair chiré

authentication de l'expéditeur si K est resté secret Avantages : rapidité du chirement/déchirement Inconvénients : échange de K par un autre canal, dialogue entre n per-sonnes nécessitent bcp de clés

Exemples : DES, 3DES, blowsh, IDEA, AES Utilisés dans : SSH, SSL/TLS, WiFi (IEEE 802.11i), VPN/IPsec

Cryptographie asymétrique ou à clé publique Chirement asymétrique : une communication non secrète permet de vé-hiculer une information que seul le destinataire peut comprendreidée [Die-Hellman 1976], RSA [Rivest, Shamir, Adleman 1977]

Chirement de données avec (clé publique ≈ eK , clé secrète ≈ dK) La clé publique eK , connue de tous, sert à chirer Le message eK(M) peut être véhiculé au vu et au su de tout le monde La clé privée dK , tenue secrète, sert à déchirer Contrainte : dicile de déduire dK de eK

condentialité

Avantages : une seule clé secrète, communication secrète dans un secondtemps

Très utile pour échanger les clés pour ouvrir un tunnel de communicationchiré (VPN, TLS/SSL). Uilisés aussi dans PGP.

Inconvénients : lenteur, pas d'authentication de la source, attaque Man-In-The-Middle

9

Nécessité de protocoles d'échanges de clé (IKE pour IPsec) Exemples : RSA [1977] (factorisation), chirement ElGamal [1985] (loga-rithme discret), Merkle-Hellman [1978] (sac-à-dos)

Signatures numériques introduite par Die et Hellman (1976) signature : sceau, prouver l'identité de l'expéditeur (non-répudiation) etl'intégrité du message

contraintes : empêcher l'usurpation, la non-reconnaissance calculable par le signataire ∀M le destinataire (et tout individu) peut vérier la signature non falsiable non imitable

signer sigK (privé) : S ← sigK(M) où M est un message ou un dé vérier verK (public) : verK : (M,S) 7→ vrai, faux Exemple : signature RSA signer sigK est le déchirement dK

L'expéditeur donne M et S = sigK(M). vérier verK est le chirement eK

Le destinataire calcule M ′ ← verK(S) = eK(dk(M)) et vérie M = M ′

Exemples : PGP, RSA, signature ElGamal/DSA Utilisation : SSL, S-MIME en théorie, découpage en blocs d'un message + signatures de chaque blocgarantit l'intégrité. Trop coûteux en pratique.

Fonctions de hachage et empreinte garantir l'intégrité d'un message M signer tout M est trop coûteux calcul d'une empreinte de M par hachage h, de taille xée signature de l'empreinte Z ← sigK(h(M)) vérication de l'intégrité par le destinataire

1. Recevoir M ′,

2. le hacher h(M ′),

3. puis vérier verK(h(M ′), Z) = vrai

contraintes : hachage rapide, à sens unique et à collision dicile Exemples : MD5, SHA-1, DSA Utilisation : garantir l'intégrité d'une communication (SSL), de mails (S-MIME), de chiers ou du système (antivirus)

Authentication Attaque Man-in-the-Middle

10

légitimer la clé publique cleA d'une personne autorité de certication (AC) émetteur A émet sa clé publique à une AC (qui vérie) et retourne uncerticat signé par l'AC : ZA,AC ← signAC(h(IdA, cleA))

le recepteur B vérie le certicat de A en calculant

1. ce qu'il reçoit : h(Id′A, cle′A)2. et l'autorité de certication : verAC(ZA,AC)3. et teste l'égalité

évite Man-in-the-Middle Mais quid de l'autorité de certication ?

Disponibilité cryptologie : inuence indirecte sur la disponibilité Contraintes fortes peu conciliables architecture sécurisée transparente : condentialité sans mot de passe ! QoS implique rapidité des mécanismes de chirement et déchirement

Gains possibles de qualité de service : en identiant mieux les sources/demandeurs de ressource

2 Cryptosystèmes et science de la cryptologie

2.1 Dénitions et objectifs

cryptosystème

Denition 3 (cryptosystème). Un système cryptographique est un quintuplet(P, C,K, E ,D) où

11

1. P : ensemble des textes clairs possibles,

2. C : ensemble des textes chirés possibles,3. K : espace des clés, ensemble des clés possibles,

4. Pour toute clé K dans K, il existe une règle de chirement eK ∈ E et unerègle de déchirement correspondante dK ∈ D. eK : P → C dK : C → P Pour tout texte clair x ∈ P, dK(eK(x)) = x.

Chaque fonction de chirement doit être injective. Pourquoi ? Si P = C, chaque fonction de chirement est une permutation.

Principe de la cryptographie, cryptanalyse Considérations pratiques les fonctions eK et dK doivent pouvoir se calculer ecacement un opposant observant les messages chirés y ne peut déterminer K oux

cryptanalyse : rechercher K à partir de y. Donnera aussi x algorithme public, clé cachée : principe de Kerckhos (1883) la sécurité d'un cryptosystème ne repose que sur le secret de la clé. autres paramètres connus (e et d) exprimé aussi par Shannon : l'adversaire connaît le système chires civils suivent le principe de Kerckhos. Militaires utilisent dessystèmes secrets. NB : chirage A5/1 des mobiles GSM non divulguéau début (1987), divulgué en 1994.

le nombre de clés possibles doit être grand. Pourquoi de tels principes pour la sécurité informatique ?

Résumé des outils arithmétique modulo (ex : caractères modulo 26, bits modulo 2) chirement eK , déchirement dK à clé secrète K chirement public eK , déchirement privé dK

signature privée sigK , vérication publique verK

fonction de hachage h publique, empreinte privée sigK(h(x))

2.2 Cryptographie historique

Chirements monoalphabétiques quelques grands noms : Al-Kindi (801-873), Alberti (1404-1472), Vigenère(1523-1596), Porta (1535-1615), Babbage (1792-1872), Kerckhos (1835-1903), Turing (1912-1954)

chire de substitution : remplacer les lettres ou les mots par d'autres sym-boles

On appelle chirement monoalphabétique ou substitution simple, un chireoù chaque lettre est remplacée par une autre lettre ou symbole.

12

chire de César (cf. Vies des douze Césars de Suétone)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 zD E F G H I J K L M N O P Q R S T U V W X Y Z A B C

chiffredecesar

FKLIIUHGHFHVDU

Si on code A−Z dans Z26, alors y = x+3 mod 26 et x = y− 3 mod 26.Denition 4 (Cryptosystème par décalage). Soient P = C = K = Z26.Pour 0 ≤ K < 26, on dénit eK(x) = x + K mod 26, dK(y) = y − Kmod 26.Exercices : Quelle est l'espace des clés du chire par décalage ? Quel est le texte clair de TMKBM CZXIQ AQJTM MBJCK WTQYCM?

Chirement par substitutionDenition 5 (Cryptosystème par substitution). Soient P = C = Z26. SoitK l'ensemble des permutations sur les nombres 0, 1, . . . , 25. Pour chaqueπ ∈ K, on dénit eK(x) = π(x), dK(y) = π−1(y).Exercices : Quelle est l'espace des clés de ce chirement ? Est-ce qu'une recherche exhaustive est envisageable ?

Un autre exemple est le chirement ane eK(x) = ax + b mod 26, pourdes clés K = (a, b) avec pgcd(a, 26) = 1. Montrez que résoudre ax + b ≡ y(mod 26) est équivalent à résoudre

ax ≡ y(mod 26) Supposez pgcd(a, 26) = d > 1 et montrez que ax ≡ 0(mod 26) a aumoins deux solutions. eK peut-il être alors injectif ?

Supposez pgcd(a, 26) = 1 et supposez ∃x1, x2 tq ax1 ≡ ax2(mod 26).En déduire 26 divise (x1 − x2), ce qui montre que x1 ≡ x2(mod 26). ek

est-il alors injectif ? En déduire que l'équation ax ≡ y(mod 26) admet une solution unique.Le chirement ane est bien un cryptosystème.

Si a−1 est l'inverse de a, en déduire que dK(y) ≡ a−1(y − b)(mod 26)Exercices : Montrer que K = (7, 3) induit un chirement ane dans Z26. Quel estsa fonction de déchirement ?

Combien y a-t-il de clés possibles ?

Chirements polyalphabétiquesUn chirement polyalphabétique peut remplacer une lettre par une autre

lettre qui n'est pas toujours la même. Cryptanalyse plus dicile.

Denition 6. Chirement de Vigenère Soit m > 0 et P = C = K = (Z26)m.

13

A B C D E F G H I08,40 01,06 03,03 04,18 17,26 01,12 01,27 0,92 07,34J K L M N O P Q R

0,31 0,05 06,01 02,96 07,13 05,26 03,01 0,99 06,55S T U V W X Y Z

08,08 07,07 05,74 01,32 0,04 0,45 0,30 0,12

Fig. 1 Fréquences des lettres en français (non accentué)

Pour la clé K = (k1, k2, . . . , km), on dénit

eK(x1, x2, . . . , xm) = (x1 + k1, x2 + k2, . . . , xm + km)dK(y1, y2, . . . , ym) = (y1 − k1, y2 − k2, . . . , ym − km)

On note que le message clair est découpé en bloc de m lettres. Les clés commeles messages sont traduits de l'alphabet a-z vers les nombres 0-25.

jadoree couterl aradiot outelaj ournee

+ MUSIQUE MUSIQUE MUSIQUE MUSIQUE MUSIQU

= VUVWHYI OIMBULP MLSLYIX AOLMBUN AOJVUY

chirement par permutation (mélange de m lettres consécutives par unepermutation/clé)

chirement de Hill (multiplication par une matrice m×m inversible dansZ26)

Cryptanalyse et analyse des fréquences Cryptanalyse : déterminer la clé K connaissant l'algorithme texte chiré connu (y) : écoute texte clair connu (x,y) : écoute + message connu (ex : protocole decommunication)

texte clair choisi (accès à la machine chirante émettrice) texte chiré choisi (accès à la machine déchirante réceptrice)

Cryptanalyse par analyse des fréquences (Al Kindi) lettres (fr) : E, (A, S), (I,N,T,R), LUODCPMVGFBQHXJYZKW bigrammes (fr) : ES, (DE, LE, EN), (RE, NT, ON, ER, TE), . . . trigrammes (fr) : ENT, LES, (EDE, DES, QUE), AIT, . . . S'applique aux chirements mono-alphabétiques Chire par décalage en deux trois essais Chire ane en quelques essais aussi. Chire par substitution si texte susamment long. On utilise aussi lesbigrammes, trigrammes pour orienter la recherche.

Cryptanalyse du chire de Vigenère

KQOWE FVJPU JUUNU KGLME KJINM WUXFQ MKJBG WRLFN FGHUD WUUMB SVLPSNCMUE KQCTE SWREE KOYSS IWCTU AXYOT APXPL WPNTC GOJBG FQHTD WXIZAYGFFN SXCSE YNCTS SPNTU JNYTG GWZGR WUUNE JUUQE APYME KQHUI DUXFPGUYTS MTFFS HNUOC ZGMRU WEYTR GKMEE DCTVR ECFBD JQCUS WVBPN ...

14

[Test de Kasiski (1863)]Si m est la longueur de la clé, alors une même partie du texte à δ d'intervalleest chirée de la même manière ssi δ ≡ 0(mod m).

On cherche des paires de segments de taille susante (≥ 3) : δ1, δ2, . . . Il est probable que leur pgcd est m ou un multiple de m. On peut vérier a posteriori cette valeur par l'indice de coïncidence.

[Source http ://www.apprendre-en-ligne.net]

Souvent pour s'amuser les hommes d'équipage prennent des albatros, vastes oiseaux des mers, qui suivent,

indolents compagnons de voyage, le navire glissant sur les goures amers. A peine les ont-ils déposés sur les

planches que ces rois de l'azur, maladroits et honteux, laissent piteusement leurs grandes ailes blanches, comme

15

des avirons, traîner à côté d'eux. Ce voyageur ailé, comme il est gauche et veule, lui naguère si beau, qu'il est

comique et laid. L'un agace son bec avec un brûle-gueule, l'autre mime en boitant l'inrme qui volait. Le poète est

semblable au prince des nuées, qui hante la tempête et se rit de l'archer.

Denition 7 (Indice de coïncidence (Friedman 1920)). Soit x = x1x2 . . . xn unechaîne de n lettres. L'indice de coïncidence de x, noté Ic(x) est la probabilitéque deux lettres aléatoires de x soit identique.

Espace des tirages X = xi, xj, i 6= j Card(X) =

(n2

) Evénement Ea : xi et xj valent la même lettre a

Si le nombre d'occurence de a dans x est fa, alors Card(Ea) =(fa

2

) Probabilité de Ea : Pr[Ea] =

∑xi,xj∈Ea

Pr[xi, xj] =(fa

2

)× 1

(n2)

D'où Ic(x) =∑25

a=0 Pr[Ea] =∑25

a=0fa(fa−1)n(n−1) .

En utilisant les tables de fréquences, fa ≈ nPr[a] fr : Ic(x) = 0.074, en : Ic(x) = 0.065 Si texte aléatoire uniforme : Ic ≈ 26( 1

26 )2 ≈ 0, 038 Invariance de Ic(x) par tout chirement mono-alphabétique

Attaque du chire de Vigenère Soit le texte chiré y. Pour tout m, on forme

y1 = y1ym+1y2m+1 . . .

y2 = y2ym+2y2m+2 . . .

. . .

ym = ymy2my3m . . .

Si m est la longueur de la clé, alors ∀i, 1 ≤ i ≤ m, Ic(yi) ≈ Ic(langue) Sinon Ic(yi) ≈ 0, 038 Détermine la longueur de la clé

Denition 8 (Indice de coïncidence mutuel). L'indice de coïncidence mutuel

de deux chaînes x et x' de même longueur n est Ic(x,x') =∑25

a=0fa

nf ′an .

Clé de Vigenère à m connu Soit ei(x) = x + i mod 26 On forme M(i) = Ic(ei(y),y') y' est un texte clair (fr) Si y est un texte chiré par décalage K, alors e26−K(y) est un texte clair(fr)

L'indice M(26−K) vaut à peu près Ic(fr). Les autres sont inférieures Calcul de 26−Kl pour chaque yl : K1 . . .Km est la clé de Vigenère

Note historique : machines ENIGMA de la seconde guerre mondiale Machines à 3 rotors (ou plus) Les rotors codent une substitution des lettres.

16

A chaque frappe, le premier avance. Tous les 26, le deuxième, Tous les676, le troisième.

autres dispositifs : reecteurs, connecteurs chire de Vigenère avec très longue période

2.3 Sûreté d'un chirement, Théorie de Shannon, secretparfait

Sûreté d'un chirement Sécurité sémantique : un attaquant ne récupère aucune information sur letexte clair à partir du texte chiré. (attaque passive)

Sécurité calculatoire : système sûr au sens de la théorie de la complexitési le meilleur algorithme pour le casser nécessite N opérations, où N estun nombre trop grand.

Sécurité prouvée : la sécurité se réduit à un problème réputé dicile.Exemple : ls système X est sûr si un entier n donné ne peut être fac-torisé.

Sécurité sémantique ou inconditionnelleL'éventualité texte clair choisi = x a une probabilité a priori Pr[x]. L'éven-

tualité clé choisie = K a une probabilité a priori Pr[K].

Denition 9 (Secret parfait). La condition du secret parfait est que ∀x ∈ P, y ∈C,Pr[x|y] = Pr[x].

Un tel cryptosystème est dit sémantiquement sûr ou de sécurité incondition-nelle.

ie. si l'attaquant dispose de deux textes chirés de même taille et qu'onlui présente les deux textes clairs correspondants mais dans un ordre quel-conque, il se trompera ou devinera correctement avec une probabilité de1/2.

cryptosystème soumis à une attaque passive. Pour un message d'une lettre, le chirement par décalage assure un secretparfait.NB : on utilise Pr[Y = y] =

∑k:y∈C(k) Pr[K = k]Pr[X = dK(y)], si C(K)

est l'ensemble des textes chirés par K.

Theorem 10 (Secret parfait). Si C = P = K, alors ce système assure un secretparfait ssi chaque clé est utilisée avec la même probabilité 1/|K| et ∀x ∈ P, y ∈ C,il existe une clé unique K telle que eK(x) = y.

Denition 11 (Chire de Vernam (1917) ou à masque jetable). Soit n ≥ 1 etC = P = K = (Z2)n. Pour tout K ∈ K, on dénit eK et dK comme le ou-exclusifde x ∈ P et K.

Le Théorème 10 assure le secret parfait de ce cryptosystème, si la clé n'estutilisée qu'une fois et n'est pas plus courte que le message.

Utilisée au niveau diplomatique (téléphone rouge).

17

Théorie de Shannon, EntropieX est une vad (à nombre ni n de valeurs xi), de probabilités Pr[X = xi] =

pi.

Denition 12 (Entropie). L'entropie (ou incertitude) d'une vad X est H(X) =∑i pi log2 pi.Mesure l'incertitude sur l'issue avant une observation de X. Approche aussi

le nombre de bits moyen pour coder les éléments de X.

0 ≤ H(X) ≤ log2 n. H(X) = 0 ssi un seul pi vaut 1 : incertitude minimale H(X) = log2 n ssi ∀i, pi = 1

n : incertitude maximale Codage de Human : la longueur moyenne l du codage d'une chaîne àvaleurs dans xi, tirée aléatoirement selon X, est entre H(X) et H(X)+1.

Denition 13 (Entropie jointe, conditionnelle). entropie jointe : H(X, Y ) =−

∑x,y Pr[X = x, Y = y] log2 Pr[X = x, Y = y].

H(X|Y = y) = −∑

x Pr[X = x|Y = y] log2 Pr[X = x|Y = y].entropie conditionnelle : H(X|Y ) =

∑y Pr[Y = y]H(X|Y = y).

H(X|Y ) mesure l'incertitude restant sur X sachant l'observation de Y H(X|Y ) ≥ 0 et H(X|X) = 0 H(X, Y ) = H(X) + H(Y |X) = H(Y ) + H(X|Y ) H(X|Y ) ≤ H(X) avec égalité seulement si X et Y indépendant

Corollary 14. Si X est une vad sur P et Y une vad sur C, la condition dusecret parfait est que H(X|Y ) = H(X).

Theorem 15. Soit un cryptosystème muni des vads X sur P, K sur K, Y surC.

H(K|Y ) = H(K) + H(X)−H(Y ).

On développe H(K, X, Y ) = H(Y |K, X)︸ ︷︷ ︸0

+H(K, X) et H(K, X, Y ) =

H(X|K, Y )︸ ︷︷ ︸0

+H(K, Y ).

Entropie d'une langue, clés parasites, distance d'unicité Entropie d'un texte quelconque

∑x∈a−z

126 log2

126 ≈ 4, 76

Entropie d'une lettre dans texte anglais h(P ) =∑

x∈a−z Pr[x] log2 Pr[x] ≈4, 19

lettres non indépendantes

Denition 16 (Entropie d'une lettre d'une langue donnée). Soit un langage

naturel L. Son entropie est HL = limn→+∞H(P n)

n .

La redondance de L : RL = 1− HL

log2 |P|.

Pour l'anglais, 1 ≤ HL ≤ 1, 5, redondance 75%. Pour une langue aléatoire,redondance nulle.

18

Denition 17. On appelle clé parasite une clé qui déchire un texte chiré ysous forme d'un message compréhensible, alors que la clé utilisée était autre.

WNAJW, codé par décalage a deux clés F(5) et W(22) tels que d22(WNAJW ) =river et d5(WNAJW ) = arena : une est parasite.

Theorem 18. Le nombre moyen sn de clés parasites sur un texte chiré delongueur n (n assez grand) vérie

sn ≥|K||P|nRL

− 1.

distance d'unicité n0 : plus petite valeur de n telle que sn ≈ 0

Chirement par substitution : |P| = 26, |K| = 26!. Avec RL = 0, 75,n0 ≈ 88, 4/(0, 75 ∗ 4, 7) ≈ 25.

Chirement de vigenère de taille m : n0 ≈ m/0, 75. On peut donc tenter des attaques par recherche exhaustive sur des mes-sages de longueur ≥ n0. Si on tombe sur un clair, c'est le bon.

2.4 Cryptosystèmes à clé secrète partagée

Système cryptographique produitSoient deux cryptosystèmes S1 = (P,P,K1, E1,D1) et S2 = (P,P,K2, E2,D2),

tels que P = C.

Denition 19 (Système cryptographique produit). Le système cryptographiqueproduit S1 × S2 est le cryptosystème (P,P,K1 ×K2, E ,D) et

chirement e(K1,K2)(x) = eK2(eK1)(x)déchirement d(K1,K2)(x) = dK1(dK2)(x)

sert à fabriquer des cryptosystèmes plus complexes à partir de cryptosys-tèmes simples

Si S × S × · · · × S, on le note Sn (cryptosystème itéré) Si S2 est équivalent à S, alors S idempotent. Itéré S ne complexie pas S. Chirement par décalage, par substitution, ane, Hill, Vigenère, permu-tation sont idempotents !

Montrez que si S1 et S2 sont tels que S1 × S2 est équivalent à S2 × S1 etsont tous deux idempotents, alors S1 × S2 est idempotent.

Chirements par substitution et par permutation ne commutent pas : AES

Algorithme de chirement itéré par bloc chirement par bloc à clé secrète K (longueur xée) systèmes cryptographiques produits (permutation, substitution) chirement par Ne étages successifs identiques diversication de K en Ne clés (d'étage)

19

algorithme de chirement xé et public

w0 ← x

w1 ← g(w0,K1)w2 ← g(w1,K2)

. . .

wNe ← g(wNe−1,KNe)

déchirement en sens inverse, g injective Exemples : réseaux de substitution/permutation substitution par blocs permutation entre bits

schéma de Feistel, DES (1976) AES/Rijndael (2001) IDEA (dans PGP), blocs de 64b, clé 128b (⊕, + et · modulo 216 + 1)

Data Encryption Standard (DES) créé par IBM en 1975 pour la NSA, standard en 1976 Caractéristiques : système à clef secrète (clef de 56 bits) chirage itéré 16 fois par blocs (64 bits) standard communications gouvernementales non secrètes (USA)

20

permutation initiale étage i, (Li, Ri) = g(Li−1, Ri−1,Ki) où Li = Ri−1, Ri = Li−1⊕f(Ri−1,Ki)

21

clé K diversiée (56b) en 16 clés (48b) déchirement : f n'a même pas besoin d'être inversible !

E : Expansion de 32b à 48b on ajoute la clé d'étage Sj : réduction par blocs 6 bits vers 4 bits. on permute le résultat par P

Critiques de DES seules les Sj ne sont pas linéaires espace des clés faibles : 256 ≈ 7, 2 · 1016

attaque à texte clair par force brut

1. machine de Wiener 1993 : 5e7 clés/s

2. DES cracker 1998 : 88e9 clés/s, 1536 puces, 1 clé en 56h

3. DES cracker + réseau mondial (100000 machines) : 1 clé en 22h

cryptanalyse diérentielle (Biham, Shamir)

22

1. attaque à texte clair choisi

2. grand nombre de quadruplets (x, x∗, y, y∗), avec x⊕ x∗ = x′ xé

3. fabriquer des diérentiels ∆x = x⊕x∗ qui maximise des diérentiels∆y = y ⊕ y∗

4. par S-boîte, on analyse le nombre de paires avec ou-exclusif d'entréeégal à x′ et ou-exclusif de sortie égal à y′

5. indépendant de la clé par S-boîte car K s'élimine avec ⊕.6. on choisit la paire de diérentiels la plus fréquente

7. on construit une piste de diérentiels en reliant les S-boîtes.

8. avec beaucoup de couples, on estime quelques bits de la clé, le restepar balayage exhaustif

9. pas eectif pour DES : 258 paires, soit plus que l'attaque exhaustive.

cryptanalyse linéaire (Matsui 1994)

1. attaque à texte clair choisi

2. analyse les biais entre les probabilités d'avoir une sortie étant donnéune entrée.

3. sur une S-boîte, observe Xi1 ⊕ · · · ⊕Xim ⊕ Yj1 ⊕ · · · ⊕ Yjn

4. si espérance 6= 12 , alors il y a un biais

5. trace ainsi un chemin de l'entrée vers la sortie, dont les variablesaléatoires ont un biais (qui dépend de la clé).

6. on chire beaucoup de messages, pour retrouver les bits de clé

7. eectif : 243 paires, 40 jours pour génération, 10 jours pour trouverK.

Evolution de DES : 3DES. Surchirement avec deux clés K1, K2.

23

y = eK1,K2(x) = eK1(eK2(eK1(x))). y = dK1,K2(x) = dK1(dK2(dK1(y))). ecace car DES n'est pas idempotent !

Nouveaux algorithmes (qualiés de sûr) IDEA (128bits) AES (ou Rijndael) (128, 192, 256 bits ; 10, 12 ou 14 étages) caractéristiques : taille de la clé plus grande, boîtes de substitutionsobtenues par inversion dans un corps ni plus grand (8bits), mélangede colonnes pour diuser les pistes diérentielles

Modes opératoiresSoit K une clé secrète initiale, IV un nombre

ECB electronic codebook modesimple chirement indépendant desblocs

CBC cipher block chaining mode : y0 =IV , yi+1 = eK(yi ⊕ xi+1)Chirement à clé constante. Texte clairadditionné à la sortie précédente.

original DES ECB DES CBC

24

CFB cipher feedback mode : Initialisa-tion y0 = IV puis yi+1 = eK(yi)⊕ xi+1

Chirement par addition du chirementde la sortie précédente.

OFB output feedback mode : clés suc-cessives indépendantes de l'entrée, z0 =IV, zi+1 = eK(zi), yi = zi ⊕ xi

Suite de clés successives obtenue parchirement par clé K. Addition de cesclés au texte clair. Chirement du texteindépendant du chirement du texteprécédent.

25

Exemples d'utilisation formation de Message Authentication Code (MAC).Dans un échange entre deux programmes A et B, les modes CBC ou CFBpermettent d'avoir une communication secrète où le chirement dépendnon seulement d'une clé secrète mais d'un paramètre supplémentaire surlequel les deux parties se sont mises d'accord (un IV donné).

le calcul d'une empreinte MD5 ou SHA d'un chier suit le principe CBC,où l'empreinte se calcule par une séquence de chirement par blocs de 512bits, par addition de l'empreinte du bloc précédent au texte clair suivant.

2.5 Cryptosystèmes à clé publique

Principe des cryptosystèmes à clé publique

Alice Oscar BobMessage M (K, K ′)y = eK(M)

y−→ M = dK′(y)

RSA, système El Gamal, Merkle Hellman fonction à sens unique : fonction pour laquelle le problème préimage nepeut être résolu de manière ecace.

Problème de la préimage

Soient une fonction f : P 7→ C et y ∈ C. Trouver x ∈ P tel que f(x) = y.

fonctions pas à sens unique : f(x) = a ∗ x + b mod n, f(x) = x−1

mod n fonctions à sens unique : f(x) = ax mod n (logarithme discret)Problème : dicile de déchirer !

fonction à sens unique à trappe : la fonction à sens unique devient facileà déchirer avec une information secrète supplémentaire

clé publique : fonction à sens unique, clé privée : la trappe de cette fonction. NB : chirement public ⇒ attaque passive toujours possible avec texteclair choisi.

Chirement RSA

Denition 20 (Cryptosystème RSA). Soit n = pq, p et q premiers. Soit P =C = Zn. Soit

K = (n, p, q, a, b) tq ab ≡ 1(mod φ(n)).

Pour K = (n, p, q, a, b)

26

1. (n, b) forment la clé publique.

2. (p, q, a) forment la clé privée.

3. chirement : eK(x) = xb mod n

4. déchirement : dK(y) = ya mod n

5. entiers premiers p et q de l'ordre de 10100

6. NB : φ(n) = (p− 1)(q − 1), et pgcd(a, φ(n)) = 1

7. typiquement le message x est un mot de 512 bits (≤ n)

ExempleBob choisit p = 17, q = 11, n = 187, φ(n) = 160 = 25 × 5. Il prend a = 39 =3× 13, b = 119 ≡ a−1(mod 160) car 39× 119 = 4641 = 29× 160 + 1.

Alice Bob Kbob = (n, p, q, a, b)x = 100

eKbob(x) = xb mod n= 100119 mod 187 = 144⇒ y = 144 reçu

dKbob(y) = ya mod n= 14439 mod 187 = 100

Mise en ÷uvre de RSA

Génération des paramètres RSA

1. Générer deux grands nombres premiers p et q.

2. n← pq, et φ(n)← (p− 1)(q − 1).

3. Choisir b aléatoire (1 < b < φ(n)) avec pgcd(b, φ(n)) = 1

4. a← b−1 mod φ(n)

5. La clé publique est (n, b) et la clé privée est (p, q, a).

Dicultés pratiques

1. Primalité. Trouver des grands nombres premiers (≈ 512bits) plus grand nombre factorisé environ 200 chires n ≈ 1024bits ≈ 300 chires

2. Calculs rapides. +,−,×,÷,pgcd, exp, inverse

3. tout algorithme linéaire en n est trop lent

4. algorithmes polynomiaux en k = log2 n

27

Tests de primalité

Primalité ou non Factorisabilité Primalité : problème de décision 6= Trouver une factorisation Inversement, factorisation de n résoud primalité de n

Primalité par tests de√

n diviseurs en Ω(2k2 )

Crible d'Eratosthène, trop lent, trop de mémoire

Denition 21 (Algorithme de Monte-Carlo positif). Algorithme probabilistequi résout un problème de décision tel que oui est toujours correct et si nonpeut être incorrect avec probabilité max ε.

Test de Miller Rabin

Miller-Rabin : Monte-Carlo positif pour primalité avec ε = 1/4probablement premier composite

n premier 1 0n composite 1

434

Algorithme peut répondre premier alors que le nombre est en fait com-posite ⇒ a est un menteur

Algorithme ne peut répondre composite si le nombre est premier Pour n composite, moins d'un 1

4 des valeurs a entre 1 et n − 1 sont desmenteurs

On appelle plusieurs fois l'algorithme pour être de plus en plus sûr On calcule a : nombre n de taille donnée est composite b : l'algorithme se trompe m fois en disant n premier Pr[a|b] ≤ 353

353+22m+1 , pour n de 512 bits

Probabilité de se tromper 44 fois est 2−80. Autres test : Test de Solovay-Strassen, basé sur les symboles de Legendreet Jacobi

28

Calculs rapides sur grands entiers k = log2 n addition, soustraction naïf. Somme bit à bit plus retenue. O(k)

multiplication, division O(k2) naïf. On pose k sommes bit à bit plus retenue. O(k2) Karatsuba. O(k

log 3log 2 ) = O(k1.584)

(a×2m + b)(c×2m +d) = ac×22m +(ac+ bd− (a− b)(c−d))×2m + bd

Toom Cook O(k(1+ε)) Transformée de Fourier Rapide, Fühler, proche de O(k log k)

29

pgcd O(k3) Algorithme d'Euclide. O(k3) (en fait O(k2))

int pgcd(int m, int n) while ( n != 0 ) int r = m mod n;m = n;n = r;

return m;

30

inverse modulo n Algorithme d'Euclide étendu. O(k3) (en fait O(k2))Fct EuclideEtendu( a, b : entier ) r[0] = a; r[1] = b;s[0] = 1; s[1] = 0;t[0] = 0; t[1] = 1;q = r[0] div r[1];r[2] = r[0] - q*r[1];i = 2;Tant que r[i] > 0s[i] = s[i-2] - q*s[i-1];t[i] = t[i-2] - q*t[i-1];q = r[i-1] div r[i];i = i+1;r[i] = r[i-2] - q*r[i-1];

Fin tant queRetourner r[i-1],s[i-1],t[i-1]// r[i-1]=pgcd(a,b)// et a*s[i-1]+b*t[i-1]=r[i-1]

pgcd(120, 23) ? et 23−1

mod 120 ?

r = s ∗a+ t ∗b120 1 120 0 23

23 0 120 1 23

5 1 120 -5 23

3 -4 120 21 23

2 5 120 -26 23

1 -9 120 47 23

Montrez ∀i, ri = asi + bti

31

Exp. modulaire rapide de c. O(log2 c× k2)c =

∑i ci2i alors bc = b

Pi ci2

i

= Πi(b2i

)ci

, ssi bc = (b)c0 · (b2)c1 · (b4)c2 ·· · · · ·(b(2k−1))ck−1

Fonction Exp( b, c, n : entier ) : entierr = 1;Tant que c > 0si c & 1 > 0 r = (r*b) mod n;c = c >> 1;b = (b*b) mod n;

Fin tant queretourner r;

RSA peut donc être mis en ÷uvre ecacement.

Sécurité de RSAAttaques possibles sur RSA Factorisation de n Si n factorisé en pq par Oscar, alors φ(n) se calcule immédiatement, etdonc l'inverse de b se calcule par Euclide étendu

algorithme naïf trop lent O(√

n) Algorithme p− 1 de Pollard et B-friabilité.Un nombre x est B-friable si ses facteurs sont inférieurs à B.Fct Fact_Pollard_p-1( n, B )a = 2^(B!) mod n;d = pgcd( a-1, n );Si 1<d<n alors retourner d;

sinon Echec;

⇒ Bien choisir ses p et q non B-friables ! Algorithme ρ de Pollard O(n1/4) : on cherche une collision x 6= x′ tq lepgcd x− x′ et n est diérent de 1.si x ≡ x′(mod p) alors p ≤ pgcd(x− x′, n) < n

Algorithme de Dixon x2 ≡ y2(mod n) alors (x− y) ou (x + y) peuventêtre des facteurs de n

crible quadratique O(e(1+o(1))√

ln n ln ln n) courbes elliptiques O(e(1+o(1))

√2 ln p ln ln p)

crible algébrique O(e(1,92+o(1))(ln n)1/3(ln ln n)2/3)

Attaque à φ(n) connu

Résoudre

n = pq

φ(n) = (p− 1)(q − 1)Ou p2 − (n− φ(n) + 1)p + n = 0Les deux racines sont p et q

Attaque à a connu. On peut trouver p,q Attaque de Wiener. Trouve a dès que a < n1/4 et q < p < 2q

ab ≡ 1(mod φ(n))⇔ ∃t, ab− tφ(n) = 1De plus, n = pq > q2, d'où 0 < n− φ(n) < 3

√n

D'où∣∣ bn −

ta

∣∣ < 3ta√

n

Comme t < a et hypothèse 3t < 3a < n1/4,∣∣ bn −

ta

∣∣ < 1an1/4 < 1

3a2

Et donc t/a est une réduite du dvp en fraction continue de b/n.

32

Moralité Choisir n grand ≈ 21024

Choisir p et q, ni trop proches, ni trop éloignés Rejeter les p et q tels que p− 1 et q − 1 ont des petits facteurs Choisir a pas trop petit devant n

OAEP Système à clé publique sûr

Denition 22. OAEP / Optimal Asymmetric Encryption Padding [Bellare,Rogaway 94]

standard OAEP / IEEE P1363 P = C = 0, 1m, k0 = k −m f un chirement publique sur 0, 1k, f−1 son déchirement privé. G : 0, 1k0 → 0, 1m et H : 0, 1m → 0, 1k0 fonctions aléatoires clé K = (f, f−1, G,H), r aléatoire sur 0, 1k0

eK(x) = f(x⊕G(r)‖r ⊕H(x⊕G(r))) f−1(y) = x1‖x2, avec x1 ∈ 0, 1m, x2 ∈ 0, 1k0

puis r = x2 ⊕H(x1) et dK(y) = G(r)⊕ x1

Lorsque f et f−1 sont le chirement RSA, on parle de RSA-OAEP.Chaque clair a 2k0 chirement distincts.

Theorem 23. RSA-OAEP est sémantiquement sûr ssi les fonctions aléatoiresG et H sont des oracles aléatoires.

G est un oracle aléatoire si le fait d'avoir fait déjà N calculs de G n'augmentepas la probabilité Pr[G(x) = y] pour tout x non déjà calculé et y.

OAEP : prétraitement à RSA peu coûteux : de l'ordre de 128 bits supplémentaires G et H sont par exemple SHA-1 théoriquement beaucoup plus sûr car r induit un bruit considérable

2.6 Hachages et schémas de signatures

Fonction de hachage et intégrité

1. Fonction de hachage h simple donnée x stockée/transmise dans/par un endroit peu sûr fonction h transformant x en un nombre court y (empreinte, condensé,digest)

y stocké/transmis dans/par un endroit sûr intégrité : comparaison h(x) = y ?

2. famille de fonction de hachage hK

paramétrée par clé secrète K donnée x et y = hK(x) stockée/transmise dans/par un endroit peu sûr intégrité : comparaison hK(x) = y ? code d'authentication de message ou MAC authentie aussi l'émetteur fonction de hachage h = famille à une seule clé possible

33

Sécurité des fonctions de hachageSoient une fonction h : P 7→ C. M = |C| Trois problèmes doivent être diciles

à résoudre

Problème de la préimage

Soit y ∈ C. Trouver x ∈ P tel que h(x) = y.

Problème de la seconde préimage

Soit x ∈ P. Trouver x′ ∈ P tel que x′ 6= x et h(x′) = h(x).

Problème de la collision

Trouver x, x′ ∈ P tel que x′ 6= x et h(x′) = h(x).

Denition 24 (Oracle aléatoire / hachage idéal). Le fait d'avoir fait déjà Ncalculs de h n'augmente pas la probabilité Pr[h(x) = y] = 1/M pour tout x nondéjà calculé et y.

Algorithme PreImage sur h : X → YFonction Trouver_PreImage(h,y,q)

Choisir un X0 sous-ensemble de X, |X0|=q

Pour tout x dans X0 Faire

Si h(x)==y alors retourner x;

retourner ``Echec''

En moyenne, Pr[Succès] = 1− (1− 1/M)q

Algorithme 2ndPreImageFonction 2ndPreImage(h,x,q)

y=h(x)

Choisir un X0 sous-ensemble de X, |X0|=q-1

Pour tout x dans X0 Faire

Si h(x)==y alors retourner x;

retourner ``Echec''

En moyenne, Pr[Succès] = 1− (1− 1/M)q−1

Algorithme CollisionFonction Collision(h,q)

Choisir un X0 sous-ensemble de X, |X0|=q

Pour tout x dans X0 Faire

y_x = h(x)

Si y_x == y_x' pour x != x' alors

retourner (x,x')

retourner ``Echec''

En moyenne, Pr[Succès] = 1− (M−1M )(M−2

M ) . . . (M−q+1M )

Nb : Paradoxe des anniversaires. Pour ε = 0.5, q ≈ 1.17√

M Borne minimale sur la taille minimale de l'empreinte. Il faut observer

√M

34

Construction de Merkle-Damgård MD5, SHA-0, SHA-1, SHAx, . . . , RIPEMD Fonction de hachage itérée, avec zip : 0, 1m+t → 0, 1m

1. Soit x, |x| > m + t + 1. On construit y tq |y| ≡ 0(mod t) y =y1‖y2‖ · · · ‖yr y souvent construit par bourrage de x : y = x‖pad(x)

2. Soit IV public de longueur m

z0 ← IV

z1 ← zip(z0‖y1)

z2 ← zip(z1‖y2)

. . .

zr ← zip(zr−1‖yr).

3. Parfois g : 0, 1m → 0, 1l publique, alors

h(x) = g(zr)

Construction de Merkle-Damgård

1. On divise x en k blocs de t − 1, le dernier complété par des 0. Onrajoute un bloc donnant le nombre de zero rajouté.

2. z1 ← zip(0m+1‖y1)

3. Pour i de 1 à k, zi+1 ← zip(zi‖1‖yi+1)

4. Retourner h(x) = zk+1

Theorem 25. si zip résistante aux collisions, t ≥ 2 alors h est résistanteaux collisions.

ConclusionIl sut donc de dénir une fonction de compression de 0, 1m+t →0, 1m résistante aux collisions pour avoir une fonction de hachage ré-sistante aux collisions.

Un exemple : SHA-1 Empreinte ou condensat de 160 bits Bourrage SHA : message M découpé en blocs de 512 bits

M1 . . . Mk−1 Mk 10 · · · 0 l(M) Compression 512 bits vers 160 bits

16 mots de Mi Wt = ROTL1(Wt−3 ⊕Wt−8 ⊕Wt−14 ⊕Wt−16)W0 · · · W15 W16 · · · · · · · · · · · · · · · W79

35

80 itérations du calcul Les fonctions Ft(B,C,D) sont de laforme

0 ≤ t ≤ 19 (B ∧ C) ∨ ((¬B) ∨D)

20 ≤ t ≤ 39 B ⊕ C ⊕D

40 ≤ t ≤ 59 (B∧C)∨(B∧D)∨(C∧D)

60 ≤ t ≤ 79 B ⊕ C ⊕D

Ki constantes A,B,C,D,E initialisés à des constantes

chaque condensat de bloc est l'initialisation du bloc suivant

Hachage et génération aléatoire bonnes fonctions de hachage = bons générateurs aléatoires

$$> let x=0; \

while test $x -le 9; do \

echo $x | sha1; let x=x+1; \

done

09d2af8dd22201dd8d48e5dcfcaed281ff9422c7

e5fa44f2b31c1fb553b6021e7360d07d5d91ff5e

7448d8798a4380162d4b56f9b452e2f6f9e24e7a

a3db5c13ff90a36963278c6a39e4ee3c22e2a436

9c6b057a2b9d96a4067a749ee3b3b0158d390cf1

5d9474c0309b7ca09a182d888f73b37a8fe1362c

ccf271b7830882da1791852baeca1737fcbe4b90

d3964f9dad9f60363c81b688324d95b4ec7c8038

136571b41aa14adc10c5f3c987d43c02c8f5d498

$> let x=1; let y=0; \

while test $x -le 10; do \

y=`echo $y | sha1`; echo $y; let x=x+1; \

done

09d2af8dd22201dd8d48e5dcfcaed281ff9422c7

00f7c7d8a69f4228724ce25e4993aa87b789433b

1e4dab666517568b861e1ebd3749405916e48506

46f4d6c2a816fb7dc6a7686dbb3d7f1f27ee5d12

1d9c4099519d4feea51d97bc33a265be5c41f1a7

7d5c9566dd41309b057f4dee18dbe65942eb2ef3

3aa4393fd13818fa130441b16303ed6ab6dbd94d

f9057849c84eadd1e33b80b73b8461c8ec017434

b052986d891ae86a7606f5cf195b03961b1411c8

bb5ab12bf139a43f44ec2f1a1c679a11fb34cd46

les fonctions de hachage se conduisent statistiquement comme des générateurs

36

aléatoires

Schémas de signature Signature numérique 6= signature conventionnelle pas de lien physique message/signature ⇒ collage vérication beaucoup plus sûre un document électronique signé = ∞ copies signées ⇒ dater les docu-ments/signatures

Objectifs : authentication, non-répudiation, intégritéDenition 26 (Schéma de signature). 2 Familles de fonctions paramé-trées par une clé K signer sigK (privé) : S ← sigK(M) où M est un message ou un dé vérier verK (public) : verK : (M,S) 7→ vrai, faux

Il faut non-répudiation : s'assurer qu'il est dicile de forger une fausse signa-ture sur un document (image et préimage)

non-répudiation : vérier qu'on ne peut créer deux documents ayantmême signature valide (collision)

intégrité : vérier qu'on ne peut falsier les données signées (secondepréimage)

authentication : s'assurer que personne numérique et personne phy-sique sont les mêmes (certicats)

Quelques schémas de signature Signature RSA

1. Alice signe M , sa clé K = (n, p, q, a, b)

2. signer S = sigK(M) = dK(M) = Ma mod n

3. Bob vérie que S est la signature de M avec clé publique d'Alice

4. vérier verK(M,S) = (eK(S) == M) = ((Sb mod n) == M)

Défauts

1. Tout le monde peut forger une signature d'Alice !

2. Signature déterministe ⇒ favorise les collisions

37

Signature ElGamal

1. Alice signe M , sa clé K = (p, α, β, a), β ≡ αa(mod p)

2. Alice tire k au hasard dans Z?p−1

3. signer S = sigK(M,k) = (γ, δ), avec γ = αk mod p, δ = (M − aγ)k−1 mod (p− 1)

4. Bob vérie que S = (γ, δ) est la signature de M avec clé publiqued'Alice

5. vérier verK(M, (γ, δ)) = (βγγδ ≡ αM (mod p)).

Défauts

1. On peut fabriquer de faux couples (message, fausse signature)

2. l'entier aléatoire ne doit pas être révélé

3. l'entier aléatoire ne doit pas être utilisé plusieurs fois

Néanmoins pas d'attaque à message choisi

Principes généraux de signature On ne signe qu'une empreinte car signature longue en temps et mémoire et rend dicile la forge de signature

Toujours signer avant le chirementMélange intégrité, et non-répudiation,

Communication d'un message chiré sous gpg

Communication d'un message chiré et signé sous gpg

38

2.7 Certicats, gestion des clés

Certicats et authentication S'assurer que personne physique et numérique sont les mêmes Principe : infrastructure de gestion de clés (IGC, PKI) qui stockent les clés publiques garantissent la conformité clé/personne gère la durée de vie de la clé, sa révocation autorité de certication : signe les demandes de certicats et les révo-cations

autorité d'enregistrement : génère certicats, vérie identité/unicité autorité de dépôt : stocke les certicats et les listes de révocations

certicats X509, PGP/OpenPGP/GnuPG AC : Thawte, Certinomis, Baltimore, Certplus, Entrust.net, Verisign, Glo-balSign, Cybertrust

Structure d'un certificat* Version* Numéro de série* Algorithme de signature du certificat* Signataire du certificat* Validité (dates limite)

o Pas avanto Pas après

* Détenteur du certificat* Informations sur la clé publique

o Algorithme de la clé publiqueo Clé publique

* Identifiant unique du signataire (Facultatif)* Identifiant unique du détenteur du certificat (Facultatif)* Extensions (Facultatif)

Cas d'étude : GnuPG

39

PGP [Zimmermann 1991], OpenPGP (RFC4880) Implémentation Gnu Privacy Guard (GnuPG) Chirement symétrique/asymétrique Signatures Certicats, Certication par réseau social S'associe bien avec toute application de messagerie (e.g. thunderbird)

40

1. Informations sur gpg

$ gpg version

...Home: ~/.gnupgAlgorithmes supportés:Clé publique: RSA, RSA-E, RSA-S, ELG-E, DSAChiffrement: 3DES, CAST5, BLOWFISH, AES, AES192, AES256, TWOFISHHachage: MD5, SHA1, RIPEMD160, SHA256, SHA384, SHA512, SHA224Compression: Non-compressé, ZIP, ZLIB, BZIP2

41

2. Créer sa clé publique

$ gpg gen-key

...Sélectionnez le type de clé désiré:

(1) DSA et Elgamal (par défaut)(2) DSA (signature seule)(5) RSA (signature seule)

Votre choix ?

1

La paire de clés DSA fera 1024 bits.les clés ELG-E peuvent faire entre 1024 et 4096 bits de longueur....Vous avez besoin d'un nom d'utilisateur pour identifier votre clé; leprogramme le construit à partir du nom réel, d'un commentaire et d'uneadresse e-mail de cette manière:

Heinrich Heine (Der Dichter) <heinrichh@duesseldorf.de>

Nom réel : Jean Bon

Adresse e-mail : jbon@pain.net

Commentaire : Comme du bon pain

Vous avez sélectionné ce nom d'utilisateur:"Jean Bon (Comme du bon pain) <jbon@pain.net>"

Un grand nombre d'octets aléatoires doit être généré....gpg: clé AAF48B9E marquée comme ayant une confiance ultime.les clés publique et secrète ont été créées et signées.

gpg: vérifier la base de confiancegpg: 3 marginale(s) nécessaires, 1 complète(s) nécessaires, modèlede confiance PGPgpg: profondeur: 0 valide: 2 signé: 0confiance: 0-. 0g. 0n. 0m. 0f. 2ugpg: la prochaine vérification de la base de confiance aura lieu le 2013-02-04pub 1024D/AAF48B9E 2008-02-06

Empreinte de la clé = 8B59 5F66 F3E0 28F3 15FF 20DF 10BC 6865 AAF4 8B9Euid Jean Bon (Comme du bon pain) <jbon@pain.net>sub 2048g/85B0C9A7 2008-02-06

clé publique de Jean Bon (8 derniers octets) : AAF48B9E

3. Voir les clés que l'on connait $ gpg list-keys

/home/lachaud/.gnupg/pubring.gpg--------------------------------pub 1024D/C294834D 2008-02-06 [expire: 2013-02-04]uid Jacques-Olivier Lachaud <jacques-olivier.lachaud@univ-savoie.fr>sub 2048g/31BC7EF2 2008-02-06 [expire: 2013-02-04]

pub 1024D/FE3AAF25 2007-03-15 [expire: 2008-10-07]uid David Coeurjolly <david.coeurjolly@liris.cnrs.fr>sub 2048g/DF839ABF 2007-03-15 [expire: 2008-03-19]

...

pub 1024D/AAF48B9E 2008-02-06uid Jean Bon (Comme du bon pain) <jbon@pain.net>sub 2048g/85B0C9A7 2008-02-06

4. Créer un certicat de révocation $ gpg gen-revoke bon

42

sec 1024D/AAF48B9E 2008-02-06 Jean Bon (Comme du bon pain) <jbon@pain.net>

Générer un certificat de révocation pour cette clé ? (o/N) ochoisissez la cause de la révocation:0 = Aucune raison spécifiée1 = La clé a été compromise

...Vous avez besoin d'une phrase de passe pour déverrouiller laclé secrète pour l'utilisateur: Jean Bon (Comme du bon pain) <jbon@pain.net>

***************

clé de 1024 bits DSA, ID AAF48B9E, créée le 2008-02-06

sortie avec armure ASCII forcée.Certificat de révocation créé.

Déplacez-le dans un support que vous pouvez cacher ; si Mallory aaccès à ce certificat il peut l'utiliser pour rendre votre cléinutilisable.Une bonne idée consiste à imprimer ce certificat puis à le stockerailleurs, au cas où le support devient illisible. Mais attention :le système d'impression de votre machine pourrait stocker cesdonnées et les rendre accessibles à d'autres personnes !-----BEGIN PGP PUBLIC KEY BLOCK-----Version: GnuPG v1.4.6 (GNU/Linux)Comment: A revocation certificate should follow

iFsEIBECABsFAkeq4MIUHQJNb3QgZGUgcGFzc2UgcGVyZHUACgkQELxoZar0i548FwCgoHbQzsn9/CKYcbJPe9ooWvCnoGEAnjrXsgyUQQsAW2d7oupgr7VQ63VG=utF/-----END PGP PUBLIC KEY BLOCK-----

43

5. S'enregistrer auprès d'un serveur de clés $ gpg keyserver pool.sks-keyservers.net send-keys AAF48B9E

gpg: envoi de la clé AAF48B9E au serveur hkp pool.sks-keyservers.net

6. Quelques public key servers

pool.sks-keyservers.netpgp.mit.edupgp.nic.ad.jpkeyserver.veridis.compgp.uni-mainz.de

44

7. Chercher une clé sur un serveur $ gpg keyserver pool.sks-keyservers.net search-keys sarkozy

(1) Csongor Sarkozy <szivar@idea.co.hu>1024 bit DSA key C3507937, créé: 1999-10-10

Keys 1-1 of 1 for "sarkozy". Entrez le(s) nombre(s), S)uivant, ou Q)uitter >gpg: requête de la clé C3507937 du serveur hkp pool.sks-keyservers.netgpg: clé C3507937: clé publique Csongor Sarkozy <szivar@idea.co.hu> importéegpg: 3 marginale(s) nécessaires, 1 complète(s) nécessaires, modèlede confiance PGPgpg: profondeur: 0 valide: 1 signé: 0confiance: 0-. 0g. 0n. 0m. 0f. 1ugpg: la prochaine vérification de la base de confiance aura lieu le 2013-02-04gpg: Quantité totale traitée: 1gpg: importée: 1

45

8. Chirer un message $ gpg -a encrypt -r bon message.txt

$ cat message.txt.asc

-----BEGIN PGP MESSAGE-----Version: GnuPG v1.4.6 (GNU/Linux)

hQIOA+DxU5+FsMmnEAf/ZDPOVmVlsfTCi578OwWz+uxxexTBYQxmBDBzDob7B+8PMWAMC6S1GYBfiwagch+GFCtZQwiBkUT4USJ8mV1XB4ScuCWJAsmoP1wV+p07j7n/3WaiHglmWZKb0cPJe9zPP+XFDsWX8KNafuBtlUq3KRVb68giohlDDbb3yT/+JYQG7Lq1k71czSlebKrtk1Hf5vw/mpCEN3Ig/JR8jGlHcGaR3n/RHLykvs8s0dSiyOa9TfZ1snn3LQFWGauRm3Ylbw6dp9NPXTVpJHxCNZzFzTEllXKuwqP8iSvP7XCIaJzIZXdJl36GL+iEPPOgzl2LqIrCVeLrRLVRTiQ6/JVBOwf/TxSV+ZrUlw+7fXGIAPb88eqleP4OLDZ+9NG2jaSZDyQxuycg4aOlvsFWP4mraIHD0TItulLkz+171hl96I6XrK4ezOjdPSLN13dQjf2+PP7dti/hylxgOfOLiMqI7MN524JxA+g/BCcwcY08FB+PlF8lIeyZvhrPweC8b31Cb2mKQA6w10+CbUAEtugJ3H3tx0vuW0W20d45qKcfy06rCBd8+oBBYMvw6Lmr3u9iNd46pC5ESHKv7jPn92Th9/ML2EEz3UV8gjtKUMlOCgD3Cbk7vhmORxtsPX8Zc52zSa7D3Ma93PObb1a04YdP6JuR60/8/dcTgwXs6bbh6X4PuNJ7AY8xk2Nu8T1SBdkbqRYFj7PrL/uLg6q7th6Y6KxGkahTESfGQ+wZuRwGwSaH2I/IRgDBQ0lR8hxKUUGsE876RLfgfb6eQOdMr87G8pCIZPo9cZJKZ5D7K8J4IMlxKwVAg3rG+Ih4qZ+RfReh7jupcgvOkouRwot+lSau=Q3L9-----END PGP MESSAGE-----

46

9. Déchirer un message $ gpg message.txt.asc

Vous avez besoin d'une phrase de passe pour déverrouiller laclé secrète pour l'utilisateur: Jean Bon (Comme du bon pain) <jbon@pain.net>clé de 2048 bits ELG-E, ID 85B0C9A7, créée le 2008-02-06 (ID clé principale AAF48B9E)

gpg: chiffré avec une clé de 2048 bits ELG-E, ID 85B0C9A7, créée le 2008-02-06Jean Bon (Comme du bon pain) <jbon@pain.net>

*****************

$ cat message.txt

Ceci est mon message.--JOL

47

10. Signer le message message.txt $ gpg -a detach-sign -u bon message.txt

Vous avez besoin d'une phrase de passe pour déverrouiller laclé secrète pour l'utilisateur: Jean Bon (Comme du bon pain) <jbon@pain.net>clé de 1024 bits DSA, ID AAF48B9E, créée le 2008-02-06

*****************

$ cat message.txt.asc

-----BEGIN PGP SIGNATURE-----Version: GnuPG v1.4.6 (GNU/Linux)

iD8DBQBHqy2TELxoZar0i54RAsC3AKCyGjvMsOHw/lZ4WjQD2j/MRpiRtACdHe69EMjIUL4ZYw47NfkXVkADqlw==KJCN-----END PGP SIGNATURE-----

48

11. Vérier que message.txt.asc est bien la signature de message.txt

$ gpg verify message.txt.asc message.txt

gpg: Signature faite le jeu 07 fév 2008 17:10:59 CET avec la clé DSA ID AAF48B9Egpg: Bonne signature de Jean Bon (Comme du bon pain) <jbon@pain.net>

$ gpg verify message.txt.asc message2.txt

gpg: Signature faite le jeu 07 fév 2008 17:10:59 CET avec la clé DSA ID AAF48B9Egpg: MAUVAISE signature de Jean Bon (Comme du bon pain) <jbon@pain.net>

49

12. Chirer pour lachaud et signer par Bon le message message.txt $ gpg -a sign -u bon encrypt -r lachaud message.txt

Vous avez besoin d'une phrase de passe pour déverrouiller laclé secrète pour l'utilisateur: Jean Bon (Comme du bon pain) <jbon@pain.net>clé de 1024 bits DSA, ID AAF48B9E, créée le 2008-02-06

*****************

On note que Jean Bon ne peut pas déchirer son propre message, et que seul JO Lachaudpeut le faire :

$ gpg message.txt.asc

Vous avez besoin d'une phrase de passe pour déverrouiller laclé secrète pour l'utilisateur: Jacques-Olivier Lachaud <jacques-olivier.lachaud@univ-savoie.fr>clé de 2048 bits ELG-E, ID 31BC7EF2, créée le 2008-02-06 (ID clé principale C294834D)

*****************

gpg: chiffré avec une clé de 2048 bits ELG-E, ID 31BC7EF2, créée le 2008-02-06Jacques-Olivier Lachaud <jacques-olivier.lachaud@univ-savoie.fr>

gpg: Signature faite le jeu 07 fév 2008 17:41:24 CET avec la clé DSA ID AAF48B9Egpg: Bonne signature de Jean Bon (Comme du bon pain) <jbon@pain.net>

50

13. Lorsque votre clé ne sert plus, on la révoque en utilisant le certicat de ré-vocation $ gpg import

-----BEGIN PGP PUBLIC KEY BLOCK-----Version: GnuPG v1.4.6 (GNU/Linux)Comment: A revocation certificate should follow

iFsEIBECABsFAkeq4MIUHQJNb3QgZGUgcGFzc2UgcGVyZHUACgkQELxoZar0i548FwCgoHbQzsn9/CKYcbJPe9ooWvCnoGEAnjrXsgyUQQsAW2d7oupgr7VQ63VG=utF/-----END PGP PUBLIC KEY BLOCK-----

gpg: clé AAF48B9E: Jean Bon (Comme du bon pain) <jbon@pain.net>certificat de révocation importé

$ gpg list-keys

...

pub 1024D/AAF48B9E 2008-02-06 [revoqué: 2008-02-07]uid Jean Bon (Comme du bon pain) <jbon@pain.net>

$ gpg keyserver pool.sks-keyservers.net send-keys AAF48B9E

gpg: envoi de la clé AAF48B9E au serveur hkp pool.sks-keyservers.net

$ gpg delete-secret-keys bon

$ gpg delete-keys bon

51

3 Sécurité informatique et réseaux

4 Mathématiques utiles pour la cryptologie

4.1 Arithmétiques modulo

Congruence, anneau Zm

Denition 27 (Congruence, module). Si a, b et m sont des entiers, m > 0,on écrit a ≡ b(mod m) si m divise b − a (noté m|(b − a)). C'est une relationd'équivalence appelée congruence modulo m. L'entier m est appelé module.

Si on divise a et b par m, on obtient des quotients et des restes. On vérieque a et b sont congrus ssi leurs restes sont égaux. Leurs restes sont entre 0 etm− 1.

Le reste de la division de a par m sera noté a mod m. Montrer que la congruence est une relation d'équivalence Montrer que les 4 dénitions ci-dessous sont équivalentes :

1. la diérence a− b est divisible par m ;

2. le reste de la division euclidienne de a par m est égal à celui de ladivision de b par m, ie a mod m = b mod m

3. il existe un entier k tel que a− b = km,

4. a− b ∈ nZ, l'idéal de tous les entiers divisibles par n. Montrer que 101 ≡ 3(mod 7)La congruence modulo n étant une relation d'équivalence sur l'ensemble des

entiers, on peut donc diviser cet ensemble en classes d'équivalences.La classe d'équivalence de l'entier a est l'ensemble des entiers a′ tels que

a ≡ a′(mod m). On la note [a]m, ou a + mZ, ou encore, tout simplement, aquand on sait de quel m on parle.

L'ensemble quotient de Z par la congruence modulo m est l'ensemble [a]m|a ∈Z, noté encore Z/mZ ou Zm.

Denition 28 (Anneau commutatif Zm, m > 0). On dénit une addition etune multiplication sur Zm ainsi

[a]m + [b]m = [a + b]m [a]m × [b]m = [a× b]m

On obtient ainsi les propriétés d'un anneau commutatif : addition interne,commutative, associative, 0 neutre pour +, opposé de a est m−a, multiplicationinterne, commutative, associative, 1 neutre pour ×, distributivité de × sur +.

On peut faire des soustractions par addition d'opposéExemple : [8]12 × [3]12 + [6]12 = [6]12 Calculer ab mod 26, pour b = 2, 3, 4, 5, . . . et a quelconque entre 0 et 25. Quand est-ce que tous les entiers de Z26 sont générés ? Vérier que (a mod m)(b mod m) ≡ ab(mod m). En déduire que (a

mod m)n ≡ an(mod m).

52

Fig. 2 1000 premières valeurs de φ.

Inverse dans Zm, corps Zp avec p premier

Theorem 29. L'équation ax ≡ b(mod m) admet une solution unique x ∈ Zmpour tout b ∈ Zm ssi pgcd(a,m) = 1.

Soit a ∈ Zm. Un inverse de a est un élément a−1 ∈ Zm tel que aa−1 ≡a−1a ≡ 1(mod m).

Exercices : S'il existe, cet inverse est unique. D'après le théorème précédent, a admet un inverse modulo m ssi pgcd(a,m) =

1. Vérier que pour m premier, Zm est alors un corps.

Denition 30 (fonction indicatrice d'Euler φ). Soient des entiers a ≥ 1 etm ≥ 2. Si pgcd(a,m) = 1, on dit que a et m sont premiers entre eux. Le nombredes entiers de Zm qui sont premiers avec m est noté φ(m), et φ est la fonctionindicatrice d'Euler.

On rappelle que tout nombre m > 1 se factorise de manière unique enproduits de puissances de nombres premiers [Théorème fondamental de l'arith-métique] (e.g. 98 = 2× 72).

Theorem 31. Si m = Πni=1p

eii , où les pi sont premiers distincts. Alors

φ(m) = Πni=1(p

eii − pei−1

i ).

Démonstration. On utilise le fait que si u et v sont premiers entre eux et stric-tements positifs, alors φ(uv) = φ(u)φ(v). On montre ensuite par récurrence surm que φ(m) = Πn

i=1φ(peii ), en utilisant le caractère multiplicatif de φ. Puis

φ(peii ) = pei

i − pei−1i , car les entiers 1 × pi, 2 × pi, . . . , p

ei−1i × pi sont les seuls

entiers non premiers avec peii , ce qui conclut.

Exercices : φ(40) = φ(5 ·23) = (5−1)(23−22) = 16 = 40(1−1/5)(1−1/2) = 160/10. Si m premier, que vaut φ(m) ? Montrez que φ(m) = mΠn

i=1(1− 1pi

).

53

Quelques propriétés asymptotiques de primalité il y a une innité de nombres premiers. Soit π(n) le nombre de nombres premiers inférieurs à n.

limn→+∞

π(n)n/ lnn

= 1.

∀n ≥ 5, φ(n) ≥ n6 ln ln n

4.2 Théorème de Fermat ; Algorithme(s) d'Euclide

Théorème de Fermat et autresZ∗n : Ensemble des résidus modulo n premiers avec n. (|Z∗n| = φ(n)) Z∗5 = 1, 2, 3, 4, Z∗6 = 1, 5L'ordre d'un élément g dans un groupe multiplicatif est le plus petit m > 0

tel que gm = 1.

Theorem 32 (Lagrange). Si G est un groupe multiplicatif à n éléments et sig ∈ G, alors l'ordre de g divise n.

Corollary 33 (Petit théorème de Fermat). Si a ∈ Z et p premier, alors ap ≡a(mod p).

Corollary 34 (Euler). Si b ∈ Z∗n, alors bφ(n) ≡ 1(mod n).

Exemples : 46 mod 7 = 1, 36 mod 7 = 1, 52 mod 6 = 1, etc

Calcul du pgcdAlgorithme d'Euclide de calcul du pgcd

INPUT: a, b dans Z, a >= b >= 0

OUTPUT: pgcd(a,b)

1. Tant que b != 0 faire

1.1 r := a mod b, a := b, b := r

2. Retourner a

Complexité : O((log n)3) opérations de bits.(analyse précise : O((log n)2))

Algorithme d'Euclide étenduAlgorithme d'Euclide étendu

INPUT: a, b dans Z, a >= b >= 0

OUTPUT: d = pgcd(a,b), x et y tq a*x+b*y=d.

1. Si b = 0 alors

1.1 d := a, x := 1, y := 0.

1.2 retourner (d,x,y)

54

2. x2 := 1, x1 := 0, y2 := 0, y1 := 1.

3. Tant que b > 0, faire

3.1 q := a div b, r := a - q*b.

3.2 x := x2 - q*x1, y := y2 - q*y1.

3.3 a := b, b := r.

3.4 x2 := x1, x1 := x, y2 := y1, y1 := y.

4. d := a, x := x2, y := y2.

5. retourner (d, x, y );

Complexité : O((log n)2) opérations de bits Montrez qu'à tout passage de 3.4, on a r = a0x + b0y. (point xe de laboucle, a0 et b0 sont les valeurs initiales de a et b. Indicez les variablesavec le numéro de l'itération.)

Montrez que si pgcd(a, b) = 1, alors b−1 mod a = y mod a. Cet algorithme calcule ecacement l'inverse d'un entier dans Za.

4.3 Probabilités discrètes

Expérience, probabilitéexpérience : procédure qui a une issue (événement simple s1, s2, . . . ) parmi

un ensemble d'issues possibles (univers S)distribution de probabilités P sur S : suite de nombres positifs pi associée à

chaque si, de somme 1. pi est la probabilité que l'événement si soit l'issue del'expérimentation.

Denition 35 (Evénement). événement E : sous-ensemble de S. La probabilitéde E est la somme des probabilités de chaque événement élémentaire de E, i.e.Pr[E] =

∑si∈E pi.

O ≤ Pr[E] ≤ 1. Pr[S] = 1 et Pr[∅] = 0. Pr[E] = 1− Pr[E]. Si les pi sont identiques, Pr[E] = |E|

|S| .

Pr[E1 ∩ E2] est la probabilité mutuelle de E1 et E2. Deux événements sontmutuellement exclusifs ssi Pr[E1 ∩ E2] = 0

si E1 ⊆ E2 alors Pr[E1] ≤ Pr[E2] Pr[E1 ∪ E2] + Pr[E1 ∩ E2] = Pr[E1] + Pr[E2]. Montrez que l'événement deux jets de pièces donnent un pile et un facea une probabilité 1/2.

Montrez que l'événement la somme de deux jets de dés vaut 3 a uneprobabilité 1/12. On utilisera une expérience dénie sur 1, 2, 3, 4, 5, 6 ×1, 2, 3, 4, 5, 6.

En déduire que la somme d'une paire de dés est une expérience. Quelleest sa distribution de probabilités ?

55

Denition 36 (Probabilité conditionnelle). Si E1 et E2 sont deux événements,Pr[E2] > 0. La probabilité conditionnelle de E1 étant donné E2 est

Pr[E1|E2] =Pr[E1 ∩ E2]

Pr[E2].

Cela mesure la probabilité que E1 se réalise, sachant que E2 s'est réalisé.

Les événements E1 et E2 sont indépendants ssi Pr[E1 ∩E2] = Pr[E1]Pr[E2].

Theorem 37 (Théorème de Bayes). Soient E1 et E2 deux événements. Si

Pr[E2] > 0, on a Pr[E1|E2] = Pr[E1]Pr[E2|E1]Pr[E2]

.

En déduire que E1 et E2 sont indépendants ssi Pr[E1|E2] = Pr[E1].

Variable aléatoire

Denition 38 (Variable aléatoire discrète). Une variable aléatoire discrète Xest une fonction de S vers un espace T (souvent R).

La probabilité que X se réalise en x est la probabilité de l'événement E telque E = s ∈ S, X(s) = x.

Pr[X = x] = Pr[X−1(x)] =∑

si∈S,X(si)=x

Pr[si] =∑

si∈S,X(si)=x

pi

. La fonction valeur d'un dé est une vad de 1, 2, 3, 4, 5, 6 vers R (quiprend seulement 6 valeurs)

La fonction somme de deux dés est une vad de 1, 2, 3, 4, 5, 6×1, 2, 3, 4, 5, 6vers R (qui prend seulement 11 valeurs). Que vaut Pr[X = 11] ?

Soit X la vad somme de deux dés et soit Y la vad qui prend la valeur1 si les dés forment un double, 0 sinon. Déterminez d'abord Pr[Y = 1] etPr[Y = 0]. Calculer ensuite Pr[Y = 1|X = 4] et Pr[X = 4|Y = 1]. Vérierla relation de Bayes.

Denition 39 (Espérance). Si X est une vad sur S, l'espérance de X (oumoyenne de X) est E(X) =

∑si∈S X(si)Pr[si].

Montrez que E(X) =∑

x∈T xPr[X = x]. Quelles sont les espérances de valeur d'un dé, somme de deux dés,double vaut 1, sinon 0 ?

Montrez la linéarité de l'espérance, i.e. si X1 et X2 sont des vad sur S,alors E(a1X1 + a2X2) = a1E(X1) + a2E(X2).

Denition 40 (Evénement identié d'une expérience). Une expérience sur unespace des échantillons X sera souvent noté X. Par abus, l'événement l'expé-rience X a eu pour issue l'éventualité x sera noté par X = x, où x ∈ X. Saprobabilité est PrX = x = Prx.

56

Ainsi si X = 1, 2, 3, 4, 5, 6, les expériences premier jet de dé vaut j etdeuxième jet de dé vaut 7 − j sont notées X1 = j et X2 = 7 − j. Leurprobabilités sont 1/6 pour tout j.

Par abus, on peut les voir comme des variables aléatoires discrètes triviales,qui sont des fonctions identité (cf plus loin).

5 Bibliographie

Références et lectures Cryptologie

Références

[Sti03] D. Stinson. Cryptographie Théorie et pratique. Vuibert, Paris,2003.

[Mar04] B. Martin. Codage, cryptologie et applications. Presses Polytech-niques Universitaires Romandes, Lausanne, 2004.

Sécurité informatique

Références

[Pil05] J.-F. Pillou. Tout sur la sécurité informatique. Dunod, Paris,2005.

[BW07] L. Bloch and C. Wolfhugel. Sécurité informatique Principes etméthodes. Eyrolles, Paris, 2007.

[FG05] B. Favre and P.-A. Goupille. Guide pratique de sécurité infor-matique Mise en ÷uvre sous Windows et Linux. Dunod, Paris,2005.

Réseaux et Sécurité

Références

[GH06] S. Ghernaouti-Hélie. Sécurité informatique et réseaux. Dunod,Paris, 2006.

[Puj07] G. Pujolle. Les réseaux. Eyrolles, Paris, 6ème édition, 2007.

Webographie Sites généraux sur la cryptologie et les mathématiques

Wikipedia [http ://fr.wikipedia.org/wiki/Cryptologie] MathWorld [http ://mathworld.wolfram.com] Appprendre En Ligne [http ://www.apprendre-en-ligne.net/crypto/menu/index.html] Handbook of applied cryptography [http ://www.cacr.math.uwaterloo.ca/hac/]

Organismes liés à la sécurité sur Internet Internet Crime Complaint Center (IC3) [http ://www.ic3.gov]

57

les RFCs de l'Internet Engineering Task Force (IETF) [www.ietf.org] Entreprises prenant part à la sécurité

Bulletins sécurité de Microsoft [http ://www.microsoft.com/technet/security/] Organismes liés à la sécurité des réseaux universitaires

CERT Renater [http ://www.renater.fr/rubrique.php3 ?id_rubrique=19] Bulletins de vulnérabilités du CERT Renater [http ://sites.univ-provence.fr/wcri/d_serv/d_reseau/d_cert/courant/index.html] CRU Comité Réseau des Universités [http ://www.cru.fr]

Magazines en ligne sur la sécurité Journal du Net [http ://www.journaldunet.com/solutions/securite/] CommentCaMarche.Net [http ://www.commentcamarche.net]

Entreprises spécialisées (proposant des informations en ligne) SOPHOS [http ://www.sophos.fr] Symantec [http ://www.symantec.com]

PGP et GnuPG Site ociel de PGP [http ://www.pgp.com] Site ociel de GnuPG [http ://www.gnupg.org] Introduction à GnuPG [http ://gpglinux.free.fr/] GnuPG pour Thunderbird / EnigMail [http ://enigmail.mozdev.org/home/index.php] RFC 4880 sur OpenPGP [http ://www.ietf.org/rfc/rfc4880.txt]

58