J'aimerais bien comprende les "rouages internes" de l'agorithmes RSA. J'ai trouvé sur internet un PDF qui en explique les mécanismes mais je ne parvient pas a saisir la démonstration.
Démonstration
Si e et (p – 1)(q – 1) sont premiers entre eux, il existe d’après le théorème de Bezout deux
entiers relatifs u et v tels que u (p – 1)(q – 1) + v e = 1. Il est clair que si u' et v' vérifient la
même égalité alors on a (u' – u) (p – 1)(q – 1) = – (v' – v) e. Il existe donc un entier k tel que
u' = u + k e et v' = v – k (p – 1)(q – 1).
Soit donc k tel que u soit le plus grand des entiers négatifs, v étant alors le plus petit des
entiers positifs.
Dans ces conditions : v e = 1 – u (p – 1)(q – 1) et le nombre d recherché est par conséquent
égal à v. Il est unique car s’il en existe un autre d' alors e (d – d') º 0 (modulo (p – 1)(q – 1)).
Comme e est premier avec (p – 1)(q – 1) alors d – d' º 0 (modulo (p – 1)(q – 1)). Mais comme
on a 1 < d < (p – 1)(q – 1) et 1 < d' < (p – 1)(q – 1) et bien d = d'.
D'abord, je ne comprend pas le passage entre ces deux phrases.
Il est clair que si u' et v' vérifient la
même égalité alors on a (u' – u) (p – 1)(q – 1) = – (v' – v) e. Il existe donc un entier k tel que
u' = u + k e et v' = v – k (p – 1)(q – 1).
Je ne comprend pas le passage de la premiere a la deuxieme phrase.
J'ai aussi du mal avec cette partie:
Soit donc k tel que u soit le plus grand des entiers négatifs, v étant alors le plus petit des
entiers positifs.
Dans ces conditions : v e = 1 – u (p – 1)(q – 1) et le nombre d recherché est par conséquent
égal à v.
On appellera Alice la personne qui désire recevoir un message chiffré, et Bob la personne qui envoie le message.
1. Choix de la clef
Alice choisit deux grands entiers naturels premiers p et q (d'environ 100 chiffres chacun ou plus) et fait leur produit n = p·q. Puis elle choisit un entier e premier avec (p-1)·(q-1). Enfin, elle publie dans un annuaire, par exemple sur le web, sa clef publique: (RSA, n, e).
2. Chiffrement
Bob veut donc envoyer un message à Alice. Il cherche dans l'annuaire la clef de chiffrement qu'elle a publiée. Il sait maintenant qu'il doit utiliser le système RSA avec les deux entiers n et e (prenons par exemple n=5141=53·97 et e=7, premier avec 52·96=4992). Il transforme en nombres son message en remplaçant par exemple chaque lettre par son rang dans l'alphabet.
Puis il découpe son message chiffré en blocs de même longueur représentant chacun un nombre plus petit que n. Cette opération est essentielle, car si on ne faisait pas des blocs assez longs (par exemple si on laissait des blocs de 2 dans notre exemple), on retomberait sur un simple chiffre de substitution que l'on pourrait attaquer par l'analyse des fréquences.
Son message devient : "010 052 215 211 901 091 305"
Un bloc B est chiffré par la formule C = Be mod n, où C est un bloc du message chiffré que Bob enverra à Alice.
Après avoir chiffré chaque bloc, le message chiffré s'écrit : "0755 1324 2823 3550 3763 2237 2052".
3. Déchiffrement
Alice calcule à partir de p et q, qu'elle a gardés secrets, la clef d de déchiffrage (c'est sa clef privée). Celle-ci doit satisfaire l'équation e·d mod ((p-1)(q-1)) = 1. Ici, d=4279.
Chacun des blocs C du message chiffré sera déchiffré par la formule B = Cd mod n.
Elle retrouve : "010 052 215 211 901 091 305"
L'instruction d=PowerMod[e,-1,(p-1)(q-1)] de Mathematica permet de calculer d facilement.
En regroupant les chiffres deux par deux et en remplaçant les nombres ainsi obtenus par les lettres correspondantes, elle sait enfin que Bob l'aime secrètement, sans que personne d'autre ne puisse le savoir.
Intérêt de la méthode
Tout l'intérêt du système RSA repose sur le fait qu'à l'heure actuelle il est pratiquement impossible de retrouver dans un temps raisonnable p et q à partir de n si celui-ci est très grand (ou alors, si c'est possible, les cryptanalystes qui ont trouvé la méthode la gardent secrète). Alice est donc la seule à pouvoir calculer d dans un temps court. De plus, elle n'a jamais à transmettre les entiers p et q, ce qui empêche leur piratage.
Follow yours dreams, become what you want and never give it up!
13/05/2006 - 14h23
Watashi
Date d'inscription
mars 2005
Messages
37
Re : Démonstration de rsa
Merci mais ce qui m'interesse c'est le pourquoi du comment ca marche ...
Pas la methode mais la demonstration -> cf. Le premier post
13/05/2006 - 14h42
Watashi
Date d'inscription
mars 2005
Messages
37
Re : Démonstration de rsa
Sur une autre démonstaration, j'aimerais un peu plus de précision sur la manière de passer de le premiere phrase a la deuxieme:
Si e et (p-1)(q-1) sont premiers entre eux, il existe d' après le théorème de Bezout deux entiers relatifs u et v tels que u(p-1)(q-1) + ve = 1.On a donc ve ≡ 1 [(p-1)(q-1)]...
13/05/2006 - 15h43
Boson_2_higgs
Date d'inscription
octobre 2004
Localisation
Tours(37)
Âge
24
Messages
1 333
Re : Démonstration de rsa
Bob et Alice c'etait pas les 2 persos qu'avait utilisé SVJ Hors Série sur La Cryptographie pour illustrer Le fonctionnement de RSA ?
Rien à voir mais il me semble qu'on peut utiliser les modulos pour crypter aussi non ?
tchou
"Rien n'est impossible , mais bien peu de choses sont réalisables,c'est le grand jeu de la vie"
13/05/2006 - 16h35
Watashi
Date d'inscription
mars 2005
Messages
37
Re : Démonstration de rsa
bob et alice sont les personnage utilisé lors des tutoriels sur la crypto...
D'abord, je ne comprend pas le passage entre ces deux phrases.
Il est clair que si u' et v' vérifient la
même égalité alors on a (u' – u) (p – 1)(q – 1) = – (v' – v) e. Il existe donc un entier k tel que
u' = u + k e et v' = v – k (p – 1)(q – 1).
e n'a pas de diviseur commun avec (p-1)(q-1) puisqu'ils sont premiers entre eux. Il divise donc u'-u. D'où l'existence de k = (u'-u)/e. Les égalités s'obtiennent alors facilement.
Soit donc k tel que u soit le plus grand des entiers négatifs, v étant alors le plus petit des
entiers positifs.
Dans ces conditions : v e = 1 – u (p – 1)(q – 1) et le nombre d recherché est par conséquent
égal à v.
On vient de montrer que les couples uv sont définis à ke près pour u et à k(p-1)(q-1) pour v. On peut donc choisir le couple ayant les plus petites valeurs absolues (schématiquement)
13/05/2006 - 19h34
Watashi
Date d'inscription
mars 2005
Messages
37
Re : Démonstration de rsa
Merci nimia,
je pense avoir finalement compris la pemiere partie.
Cependant je ne comprend pas ou on veut en venir ensuite:
Dans ces conditions : v e = 1 – u (p – 1)(q – 1) ...
D'accord ... puis
...et le nombre d recherché est par conséquent
égal à v
Comment ca ?
Sachant que la propriété que l'on cherche est:
Soit p et q deux nombres premiers. Si e, tel que 1 < e < (p – 1)(q – 1), est premier avec
le produit (p – 1)(q – 1) alors il existe d unique tel que 1 < d < (p – 1)(q – 1) et
vérifiant :
e d º 1 (modulo (p – 1)(q – 1)).
Comment passe-t-on de
v e = 1 – u (p – 1)(q – 1)
à
e d º 1 (modulo (p – 1)(q – 1))
14/05/2006 - 11h58
zinia
Date d'inscription
décembre 2005
Localisation
Paris
Messages
544
Re : Démonstration de rsa
Envoyé par Watashi
Comment passe-t-on de
v e = 1 – u (p – 1)(q – 1)
à
e d = 1 (modulo (p – 1)(q – 1))
Bonjour,
Sais-tu ce que c'est qu'un modulo ? Sinon, tu n'es pas au bout de tes peines pour décortiquer le RSA !
La première relation montre que ve = 1 modulo (p-1)(q-1)
en plus v a été choisi pour vérifier l'inégalité imposée à d.
Donc v remplit les conditions imposées à d et on a vu qu'il était le seul à entrer dans l'intervalle.
Partager
Poursuivez votre recherche :
? 
Envoyé par Watashi 
