RSA

Vous connaissez forcement RSA, sous ce nom ou un autre. C'est algorithme utilise pour les cartes a puces. J'ai le "mode d'emploi" mais j'ai du mal a le comprendre.
J'aimerai creer un programme de criptage par RSA. Pour ceux qui ne connaissent pas ou qui n'ont pas le code sous la main :

On prend (N;E) la cle publique et (N;D) la clee privee.
soient :
•N=pq (p,q€N*)
•E inferieur et premier avec Φ(N)
•ED = 1 [Φ(N)] (modulo)

On nomme M le message decode et C le message encode.
Selon les trois egalites :
C = M^E [N]
M = C^N [E]


Le probleme c'est que (N;E) forment la cle publique, or avec ces deux nombre, il est possible de resoudre ED = 1 [Φ(N)]



Pouvez vous m'aider ?

Je connais vite fait RSA, et j'ai pas tout compris ton explication

c'est quoi Φ(N) ? D est de quel type? et le signe ^ signifie puissance ici?

il me semble que la difficuté du déchiffrement de RSA viens du fait que la clef est le produit de 2 très grands nombres premiers. et effectivement, la cléf publique permet théoriquement de décrypter RSA, sauf qu'il faut un PC archi puissant (je pense aux supers ordinateurs), et le laisser tourner quelques années... d'ici là, la clef aura certainement changé...

Φ(N) = (p-1)(q-1) où N=pq.
^signifie que le nombre suivant est en exposant.
{E;D;N} C N*

ah, j'ai trouvé des chiffres:

- pour cracker une clef RSA 129, il a fallu 8 mois et la puissance partagée de 1600 utilisateurs internet.

- pour RSA 140, cela prendrait plus de temps que l'age de l'univers (pas précisé si c'est de façon générale, ou avec les 1600 utilisateurs internet précédents)

source

ouais, bah là il se fait trop tard pour faire de l'arithmétique, mais il me semble que Fermat est ton homme...

quoique en fait, tout ce dont tu as besoin là, vu que tu connais le principe, c'est de pouvoir générer de grands nombres premiers...

j'en suis capable. Mais ne croyez pas que mon but est de cracker RSA, je veux simplement comprendre comment generer un algorithme de criptage avec RSA.

Dois-je prendre p et q deux tres grand nombres premiers ?
Si oui, E, D et N seront tres grand et le chiffrement sera tres long.

Citation:

---

Envoyé par prgasp77

Dois-je prendre p et q deux tres grand nombres premiers ?
Si oui, E, D et N seront tres grand et le chiffrement sera tres long.

---

C'est la base même de RSA de prendre de trés grand nombre premier pour former n. Le chiffrement sera long, oui. Environ 1000 fois plus que le DES si tu prends une taille de clé raisonnable (P et Q de 512 bits chacun).
C'est pour ca qu'on l'utilise en mode hybride en général, c'est à dire uniquement pour transmettre une clé secrete.

Citation:

---

Envoyé par prgasp77

Le probleme c'est que (N;E) forment la cle publique, or avec ces deux nombre, il est possible de resoudre ED = 1 [Φ(N)]

---

Si tu sais faire ca en temps polynomial alors félicitation, je t'encourages à publier un article mathématiques: tu viens de casser le RSA.
Celà dit j'en doute.
Comment peux-tu trouver D connaissant uniquement E et N ? Il te faut Phi(N) = (p-1)(q-1)
Or la seule manière connue de l'obtenir est de factoriser N ... CQFD, on revient toujours au même probleme, la factorisation de grands entiers

Problemes d'implémentations que tu rencontreras: gérer des entiers de taille arbitraire, avec les opérations de base. Et également génerer des nombres premiers aléatoires.

Pour les grands nombres: fait une recherche sur les forums ou les utilisateurs, ou meme sur google: quelqu'un a programmé une trés bonne calculatrice et il explique justement comment coder les nombres. Son projet s'appelle HaypoCalc . Une autre source utile, c'est l'API de Java. La classe BigInteger implémente justement des grands entiers, et consulter la source est trés instructif

Pour plus d'infos sur RSA ( et le cryptage en général), je conseil les cours de S. Natkin : cours crypto

J'ai suivi son cours cette année au CNAM, trés bon prof :wink: