Démonstration de rsa

[invite1815de90]

Salut à tous,

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.

Le PDF est accessible ici: http://perso.wanadoo.fr/jpq/divers/rsa/rsa.pdf

Je bloque pour l'instant a plusieurs endroits...

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.

Merci pour vos lumières...
-----

[invited3a03b46]

Fonctionnement du cryptosystème RSA

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.

"JEVOUSAIME" devient : "10 05 22 15 21 19 01 09 13 05".

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.

[invite1815de90]

Merci mais ce qui m'interesse c'est le pourquoi du comment ca marche ...
Pas la methode mais la demonstration -> cf. Le premier post

[invite1815de90]

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)]...

[A voir en vidéo sur Futura]

[invite06020107]

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

[invite1815de90]

bob et alice sont les personnage utilisé lors des tutoriels sur la crypto...

Bref personne ne peut m'eclairer ?

[invite636fa06b]

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)

[invite1815de90]

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))

[invite636fa06b]

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.

[invite1815de90]

En effet question bete.

Merci