Upload
others
View
10
Download
0
Embed Size (px)
Citation preview
TP
Le chiffrement asymétrique
19/03/2013 Pr BELKHIR Abdelkader
Pr Belkhir Abdelkader
Les étapes de calcul pour la sélection des
Nombres premiers p et q dans RSA
Vous devez d'abord décider de la taille du module n entier.
Disons que votre implémentation de RSA nécessite un
module de taille B bits
Pour générer le nombre premier p;
– L'utilisation d'un générateur de haute qualité de nombres aléatoires,
vous devez d'abord générer un nombre aléatoire de taille B / 2 bits.
–Vous mettez à 1le bit de poids faible de l'entier généré par l’étape
précédente, ce qui assure que le nombre sera impair.
-Vous devez également mettre à 1 les deux bits les plus élevés de
l'entier, ce qui assure que les bits les plus élevés de n seront à 1.
-En utilisant l'algorithme de Miller-Rabin, vous allez maintenant
vérifier si l’entier est premier. Sinon, vous augmentez le nombre
entier de 2 et vérifier de nouveau. Cela devient la valeur de p.
19/03/2013 Pr BELKHIR Abdelkader
Les étapes de calcul pour la sélection des
Nombres premiers p et q dans RSA
Vous devez d'abord décider de la taille du module n entier.
Disons que votre implémentation de RSA nécessite un
module de taille B bits
Vous faites la même chose pour la sélection de q. Vous
commencez avec un nombre généré hasard de taille B/2 bits,
et ainsi de suite.
Dans le cas peu probable que p = q, ignorer votre
générateur aléatoire de nombres et il faut acquérir un
nouveau générateur.
Pour plus de sécurité, au lieu d'incrémenter par 2 lorsque le
Test de Miller-Rabin échoue, vous générez un nouveau
nombre aléatoire.
19/03/2013 Pr BELKHIR Abdelkader
Choix d'une valeur de l'exposant
public Pour plus de facilité de calcul, on choisit généralement
une valeur de e qui est premier, possède peu de bits
égaux à 1 pour une multiplication rapide, et, en même
temps, qui est cryptographiquement sûr dans le sens
décrit dans le point suivant.
Les valeurs typiques pour e sont 3, 17, et 65537(= 216+1).
Chacune de ces valeurs ne dispose que de deux bits à 1,
ce qui rend l'exponentiation modulaire rapide. Mais
ne pas oublier l'exigence de base sur les e qu'il doit être
relativement premier avec p-1 et q-1 simultanément.
De petites valeurs de e, comme 3, sont considérées
comme cryptographiquement non sures.
19/03/2013 Pr BELKHIR Abdelkader
Choix d'une valeur de l'exposant
privé Puisque d est l'inverse multiplicatif de e modulo (N), on
peut utiliser d'Euclide étendu de l'algorithme pour
calculer d. Rappelons que nous connaissons la valeur de
(N) car il est égal à (p - 1) × (q - 1).
Notez que c'est la principale source de la sécurité dans la
système - en gardant secrète p et q, et donc aussi
garder (n) secret.
19/03/2013 Pr BELKHIR Abdelkader
Un petit exemple qui illustre comment choisir n, e, d
pour une application de chiffrement RSA
Par illustrer la façon dont vous utilisez RSA comme un
chiffrement par bloc, nous allons essayer de concevoir un
algorithme de chiffrement RSA de 16 bits pour le cryptage
de fichiers disque. Un procédé de chiffrement RSA à 16
bits signifie que nos modulos seront sur 16 bits.
Avec la taille de module réglé sur 16 bits, nous sommes
confrontés à l'importante question de ce qu'il faut utiliser
pour la taille des blocs de bits pour conversion d’un fichier
en texte chiffré. Du fait que notre message entier M doit
être plus petit que le module n, évidemment, notre taille
de bloc ne peut pas égaler la taille du module.
19/03/2013 Pr BELKHIR Abdelkader
Un petit exemple qui illustre comment choisir n, e, d
pour une application de chiffrement RSA (suite)
Cela nécessite que nous utilisons un bloc de taille plus petite, par exemple
8 bits, et utiliser une sorte de schéma de remplissage pour remplir le reste
des 8 bits. Comme il en ressort, le remplissage est une partie importante
de chiffrement RSA. En plus de la nécessité pour le rembourrage, comme
expliqué ici, il est également nécessaire pour rendre le chiffrement plus
résistant à certaines vulnérabilités qui sont décrits dans le document sur les
normes RFC 3447. Le même document présente également le système à
utiliser pour le remplissage
nous supposerons pour notre exemple que notre modulo est sur 16 bits,
mais la taille de bloc sera inférieure à 16 bits, par exemple, seulement 8 bits.
Nous supposons en outre que, tant que fichier est lu à partir du disque,
chaque bloc de bits est rembourré avec des zéros pour le rendre sur une
largeur de 16 bits. Ce dernier constitue notre message M.
19/03/2013 Pr BELKHIR Abdelkader
Un petit exemple qui illustre comment choisir n, e, d
pour une application de chiffrement RSA (suite)
Donc, notre première tâche est de trouver un module n dont la taille est
de 16 bits. Rappelons que n doit être un produit de deux nombres
premiers p et q. En supposant que nous voulons que ces deux nombres
premiers à être à peu près la même taille, nous allons allouer à 8 bits et 8
bits de p à q.
nous supposerons pour notre exemple que notre modulo est sur 16 bits,
mais la taille de bloc sera inférieure à 16 bits, par exemple, seulement 8 bits.
Nous supposons en outre que, tant que fichier est lu à partir du disque,
chaque bloc de bits est rembourré avec des zéros pour le rendre sur une
largeur de 16 bits. Ce dernier constitue notre message M.
Donc, la question est maintenant de savoir comment trouver notre nombre
premier sur 8-bit. Nous pourrions lancer un générateur de nombres
aléatoires, fixer ses deux premiers bits et le dernier bit à 1, puis testez la
primalité du nombre résultant avec l'algorithme de Miller-Rabin. Mais nous
n'avons pas besoin d'aller à tout ce mal pour notre exemple. Nous allons
utiliser l'approche simplifiée décrite ci-dessous.
19/03/2013 Pr BELKHIR Abdelkader
Un petit exemple qui illustre comment choisir n, e, d
pour une application de chiffrement RSA (suite)
Supposons que nous avons un mot imaginaire de 8-bit pour p dont les
deux premiers et le dernier bit sont à 1. Supposons la même chose pour
q.Alors p et q ont les configurations binaires suivantes:
bits de p: 11 ----- 1
bits de q: 11 ----- 1
où "-" indique le bit qui n'a pas encore été déterminé. comme vous le
pouvez vérifier rapidement les trois bits qui sont fixés, par exemple un
entier sur 8 bits aura une valeur décimale minimum de 193.
Donc la question se réduit à savoir s'il existe deux nombres premiers
(espérons-le différents) dont la valeur décimal dépasse 193, mais sont
inférieurs à 255. Si vous effectuez une recherche sur Google avec une
chaîne comme «1000 premiers nombres premiers», vous découvrirez qu'il
existe beaucoup de candidats pour de tels nombres premiers.
Sélectionnons les deux suivantes
p = 197
q = 211
19/03/2013 Pr BELKHIR Abdelkader
Un petit exemple qui illustre comment choisir n, e, d
pour une application de chiffrement RSA (suite)
ce qui nous donne pour le module n = 197 × 211 = 41 567. le bit
pour le motif choisi p, q, n et du module sont les suivantes:
bits de p : 0Xc5 = 1100 0101
bits de q : 0Xd3 = 1101 0011
bits de n : 0Xa25f = 1010 0010 0101 1111
Maintenant, nous allons essayer de sélectionner les valeurs appropriées
pour e et d.
Pour e nous voulons un entier qui est premier par rapport à
(N)=196×210 = 41160. Une telle valeur de e sera aussi premier avec 196
et 210 ((p) et (q) respectivement). Comme il est préférable de choisir
un nombre premier petit pour e, nous pourrions essayer e = 3.
Mais cela ne fonctionne pas car le 3 n'est pas premier par rapport à 210. La
valeur e = 5 ne fonctionne pas pour la même raison. Essayons e = 17, car il
s'agit d'un petit nombre premier et parce qu'il ne dispose que de deux bits
fixés.
19/03/2013 Pr BELKHIR Abdelkader
Un petit exemple qui illustre comment choisir n, e, d
pour une application de chiffrement RSA (suite)
Avec e fixé à17, nous devons maintenant choisir d l'inverse multiplicatif de
e modulo 41160. L'inverse de 14527 modulo 41160 est 26633
Notre chiffrement par blocs de 16 bits basé sur RSA a donc les nombres
suivants n, e et d :
n = 41567
e = 17
d = 26633
19/03/2013 Pr BELKHIR Abdelkader
Exponentiation modulaire pour le chiffrement
et décryptage
Comme déjà mentionné, le message entier M est portée à la
puissance e modulo n. Cela nous donne le texte chiffré entier C. Le
décryptage consiste à élever C à la puissance n modulo d.
L'opération d'exponentiation pour chiffrement peut être effectué
efficacement en choisissant simplement un e approprié. (Notez que la
seule condition e est qu'il soit premier avec (n)). Comme mentionné
précédemment, les choix typiques pour e sont 3, 17 et 65537. Ils sont
tous premiers et chacun a seulement deux bits à 1.
Exponentiation modulaire pour le déchiffrement, ce qui signifie le calcul
du Cd mod n, est une question entièrement différente, car nous ne
sommes pas libre de choisir d. La valeur de d est déterminée
complètement par e et n.
Calcul de Cd mod n peut être accéléré en utilisant le
Théorème des restes chinois
19/03/2013 Pr BELKHIR Abdelkader
Exponentiation modulaire pour le chiffrement
et décryptage Du fait que la partie qui fait le décryptage connaît les facteurs premiers
p et q du module n, on peut d'abord effectuer le plus facile
exponentiations: Vp = Cd mod p
Vq = Cd mod q
Pour appliquer CRT, il faut aussi calculer les valeurs suivantes:
Xp = q × (q−1 mod p)
Xq = p × (p−1 mod q)
En appliquant CRT, on obtient:
Cd mod n = (VpXp + VqXq) mod n
Voyons comment le petit théorème de Fermat peut être utilisé pour
accélérer le calcul de Vp et Vq. Vp nécessite Cd mod p. Puisque p
est premier, évidemment C et p seront premiers entre eux. On peut
donc écrire
Vp = Cd mod p = Cu×(p−1) + v mod p = Cv mod p
pour certains u et v Comme v <d, ça va être plus rapide à calculer
Cv mod p de Cd mod p.19/03/2013 Pr BELKHIR Abdelkader
Projet: partie I
1. créer un chiffrement par bloc RSA avec 16 bits de
cryptage (ce qui signifie que vous allez utiliser un
nombre de 16 bits pour le module n dans votre
chiffrement). Ne pas utiliser les mêmes nombres
premiers pour p et q que j'ai utilisé dans l’exemple
précédent. Utilisez la partie n et e de l'algorithme de
chiffrement pour le chiffrement du mot "secure" de 6
octets. Imprimez le mot crypté comme une chaîne
hexadécimale de 12 caractères. Ensuite, utilisez la
partie n et d de l'algorithme de chiffrement pour
déchiffrer la chaîne cryptée.
2. Utiliser ce système de chiffrement pour chiffrer et
déchiffrer des fichiers
19/03/2013 Pr BELKHIR Abdelkader