TD 2 : Le cryptosyst eme RSA 1 Example de protocole RSA

A Method for Obtaining Digital Signatures and Public-Key Cryptosystems R L Rivest, A Shamir, and L Adleman Abstract An encryption method is presented with the novel property that publicly re-

TD 2 : Le cryptosyst eme RSA 1 Example de protocole RSA

TD 2 : Le cryptosyst eme RSA 1 Example de protocole RSA 1 1 G en eration des cl es Alice choisit : deux entiers premiers p et q et fait leur produit n = pq un entier e premier avec ’(n) = (p 1)(q 1) Alice calcule : la cl e d de d echi rage (c’est sa clef priv ee) qui doit satisfaire l’ equation de = 1 (mod ’(n))

Mathématiques - Le chiffrement RSA

Chiffrement RSA3 - Le cryptage RSA H Schyns3 1 3 Le cryptage RSA 3 1 Principe Le cryptage RSA repose sur le choix d'un couple de deux nombres premiers généralement appelés [ p ] et [ q ] que l'on doit absolument garder secrets Les nombres premiers choisis doivent être les plus grands possible afin de

A FULLY HOMOMORPHIC ENCRYPTION SCHEME A DISSERTATION

Rivest, Adleman and Dertouzous [120] shortly after the invention of RSA by Rivest, Shamir, and Adleman [121] Basic RSA is a multiplicatively homomorphic encryption scheme { i e , given RSA public key pk = (N;e) and ciphertexts fˆi ˆ e i mod Ng, one can e–ciently compute Q i ˆi = (Q i i) e mod N, a ciphertext that encrypts the

Cryptographie

4 Exemple d'algorithme à clés publiques Cryptage RSA 4 1 Généralités L'algorithme R S A (du nom des trois auteurs RIVEST, SHAMIR, ADLEMEN) est un exemple d'algorithme à clés publiques utilisé par les services secrets On choisit deux nombres premiers distincts « très grands »p etq et on considère le nombreN=pq

S5 - Cryptographie - arnoldonomie

Cryptage RSA Cryptage RSA Le système RSA a été inventé par les informaticiens et mathématiciens Rivest, Shamir et Adelman en 1978 Le principe est le suivant : • Si Colbert veut utiliser ce système, il doit d’abord s’inscrire dans un annuaire Il commence par choisir

Un exemple de chiffrement à clé publique: le codage

connu est le système RSA utilisé aujourd'hui dans une multitude d'applications, notamment les transactions sécurisées via internet L'objectif de cette activité est la mise en œuvre d'un chiffrement à clé publique 1ère partie : un peu de math pour commencer

Algorithmes de chiffrement symétrique par bloc (DES et AES)

• RC6 (RSA Labs) • Twofish (USA) 43 AES • Le 2 octobre 2000, l’algorithme belge Rijndael est retenu par le NIST • FIPS 197 • Taille de bloc de 128 bits

1 Le chiffrement de César - Exo7

L’arithmétique pour RSA Vidéo — partie 6 Le chiffrement RSA 1 Le chiffrement de César 1 1 César a dit Jules César a-t-il vraiment prononcé la célèbre phrase : DOHD MDFWD HVW ou bien comme le disent deux célèbres Gaulois : « Ils sont fous ces romains » En fait César, pour ses communications importantes à son armée

Introduction a la cryptographie Annee 2015-2016

TD 2 : Le cryptosysteme RSA

1 Example de protocole RSA

1.1 Generation des cles

Alicechoisit :

deux entiers premierspetqet fait leur produitn=pq. un entierepremier avec'(n) = (p1)(q1).

Alicecalcule :

la cledde dechirage (c'est sa clef privee) qui doit satisfaire l'equation de=1(mod'(n)) Enn, elle publie dans un annuaire, par exemple sur le web, sa cle publique :Alice public key pk= (RSA;n;e)Elle garde secretspetqet sa cle priveesk=d.Secrets (RSA;p;q) sk=dExercice 1On considere les valeursp= 53;q= 11 ete= 3. a) Calculez la valeur publiquen. b) Calculez la fonction d'Euler'(n) = (p1)(q1). c) Utilisez l'algorihtme etendu d'Euclid pour calculer la valeurdde la cle privee.

1.2 Chirement

Bobveut envoyer un message aAlice.

Il cherche dans l'annuaire la cle de chirement qu'elle a publiee. Il sait maintenant qu'il doit utiliser le systeme RSA avec les deux entiersnete. Il transforme en nombres son message en remplacant par exemple chaque lettre par son rang dans l'alphabet."JEVOUSAIME"10 05 22 15 21 19 01 09 13 05 Puis il decoupe son message chire en blocs de m^eme longueur (En partant de la droite) representant chacun un nombre le plus grand possible tout en restant plus petit quen. www.di.ens.fr/nitulesc/teaching anca.nitulescu@ens.fr

Introduction a la cryptographie TD 2

Exercice 2a) Son message devient :010 052 ... ... ... ... ... b) Pourquoi on ne garde pas la longueur 2 des bloques?

Sur quoi on retomberait si on laissait des blocs de 2?Indication :Rappellez vous le principe du chirement par substitution et l'attaque par l'analyse

des frequences.

Un blocBest chire par la formule

C=Be(mod n)

Cest un bloc du message chire que Bob enverra a Alice.

Exemple :C1= 0103= 1000 = 417 mod 583

Exercice 3Quel message obtient Bob apres avoir chire chaque bloc?417 ... ... ... ... ... ...

1.3 Dechirement

Aliceutilise sa cle priveedtqed(mod(p1)(q1)) =1.

Chacun des blocsCdu message chire sera dechire par la formule

B=Cd(mod n)

Exercice 4Quel message retrouve Alice?010 ... ... ... ... ... ... En regroupant les chires deux par deux et en remplacant les nombres ainsi obtenus par les lettres correspondantes, elle sait enn le secret que Bob lui a transmis, sans que personne d'autre ne puisse le savoir. www.di.ens.fr/nitulesc/teaching 2 anca.nitulescu@ens.fr

Introduction a la cryptographie TD 2

2 Applications

Exercice 5Connaissant la cle publique (n= 119;e= 5) de ce cryptogramme RSA 7 bits, (on considere des nombres a 7 bits soit inferieurs a 27= 128) :090 086 036 067 032 001 003 031 059 031

1. Calculez (par tout les moyens a votre disposition)petq.

2. Calculez la cle secreted.

3. Dechirez le cryptogramme.

Exercice 6

Bob choisit comme nombre premierp=17etq=19, comme exposante=5. Alice et lui se xent un protocole RSA dans lequel les messages sont des nombres en base 10 que l'on code par bloc de 2 chires. Alice veut envoyer le message "462739".

1. Donnez la cle publique de Bob.

2. Donnez la cle secretedde Bob.

3. Ecrivez le message chire que Alice envoie a Bob.

4. Dechirez le message qu'a recu Bob et veriez que c'est bien celui qu'a envoye Alice.

Exercice 7Bob utilise le protocole RSA et publie sa cle publiquen=187ete=3.

1. Encodez le messagem=15avec la cle publique de Bob.

2. En utilisant le fait que'(n) =160, retrouvez la factorisation den.

3. Retrouvez la cle priveedde Bob.

2.1 RSA avec deux facteurs trop proche

Exercice 8

Supposons que l'entiernsoit le produit de deux nombres premierspetqproches (on peut toujours supposer quep>q).

On poset=p+q2

ets=pq2 . Montrez que :

1. L'entiersest petit.

2.n=t2s2.

3.test legerement superieur a la racine carree

den.

4. On peut utiliser ces informations pour facto-

risern.

5. Appliquez cet algorithme pour factoriser

899;110417, puis364957402.

6. Trouvez la cle secretedcorrespondante a

pk= (RSA;n=51983;e=17).Algorithme de Fermat (a)t dpne (b)z=2 (c) Tant quezn'est pas un carre : i.t t+1 ii.z t2n (d) Retournerp=t+pz.Exercice 9 Alice change sa cle RSA tous les 25 jours. Bob change sa propre cle tous les 31 jours. Sachant qu'Alice change sa cle aujourd'hui et que Bob a change sa cle il y a trois jours, determiner quand sera la prochaine fois qu'Alice et Bob changeront leur cle le meme jour. www.di.ens.fr/nitulesc/teaching 3 anca.nitulescu@ens.frquotesdbs_dbs23.pdfusesText_29

[PDF] TD 2 : Le cryptosyst eme RSA 1 Example de protocole RSA

Introduction a la cryptographie Annee 2015-2016

TD 2 : Le cryptosysteme RSA

1 Example de protocole RSA

1.1 Generation des cles

Alicechoisit :

Alicecalcule :

1.2 Chirement

Bobveut envoyer un message aAlice.

Introduction a la cryptographie TD 2

Un blocBest chire par la formule

C=Be(mod n)

Exemple :C1= 0103= 1000 = 417 mod 583

1.3 Dechirement

Aliceutilise sa cle priveedtqed(mod(p1)(q1)) =1.

B=Cd(mod n)

Introduction a la cryptographie TD 2

2 Applications

1. Calculez (par tout les moyens a votre disposition)petq.

2. Calculez la cle secreted.

3. Dechirez le cryptogramme.

Exercice 6

1. Donnez la cle publique de Bob.

2. Donnez la cle secretedde Bob.

3. Ecrivez le message chire que Alice envoie a Bob.

4. Dechirez le message qu'a recu Bob et veriez que c'est bien celui qu'a envoye Alice.

1. Encodez le messagem=15avec la cle publique de Bob.

2. En utilisant le fait que'(n) =160, retrouvez la factorisation den.

3. Retrouvez la cle priveedde Bob.

2.1 RSA avec deux facteurs trop proche

Exercice 8

On poset=p+q2

1. L'entiersest petit.

2.n=t2s2.

3.test legerement superieur a la racine carree

4. On peut utiliser ces informations pour facto-

5. Appliquez cet algorithme pour factoriser

899;110417, puis364957402.

6. Trouvez la cle secretedcorrespondante a