IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

RSA


Sujet :

Algorithmes et structures de données

  1. #1
    Membre émérite
    Avatar de prgasp77
    Homme Profil pro
    Ingénieur en systèmes embarqués
    Inscrit en
    Juin 2004
    Messages
    1 306
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 36
    Localisation : France, Eure (Haute Normandie)

    Informations professionnelles :
    Activité : Ingénieur en systèmes embarqués
    Secteur : High Tech - Électronique et micro-électronique

    Informations forums :
    Inscription : Juin 2004
    Messages : 1 306
    Points : 2 466
    Points
    2 466
    Par défaut 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 ?
    -- Yankel Scialom

  2. #2
    Membre du Club
    Profil pro
    Inscrit en
    Juin 2004
    Messages
    58
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2004
    Messages : 58
    Points : 48
    Points
    48
    Par défaut
    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é...
    --

  3. #3
    Membre émérite
    Avatar de prgasp77
    Homme Profil pro
    Ingénieur en systèmes embarqués
    Inscrit en
    Juin 2004
    Messages
    1 306
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 36
    Localisation : France, Eure (Haute Normandie)

    Informations professionnelles :
    Activité : Ingénieur en systèmes embarqués
    Secteur : High Tech - Électronique et micro-électronique

    Informations forums :
    Inscription : Juin 2004
    Messages : 1 306
    Points : 2 466
    Points
    2 466
    Par défaut
    Φ(N) = (p-1)(q-1) où N=pq.
    ^signifie que le nombre suivant est en exposant.
    {E;D;N} C N*
    -- Yankel Scialom

  4. #4
    Membre du Club
    Profil pro
    Inscrit en
    Juin 2004
    Messages
    58
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2004
    Messages : 58
    Points : 48
    Points
    48
    Par défaut
    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
    --

  5. #5
    Membre du Club
    Profil pro
    Inscrit en
    Juin 2004
    Messages
    58
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2004
    Messages : 58
    Points : 48
    Points
    48
    Par défaut
    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...
    --

  6. #6
    Membre émérite
    Avatar de prgasp77
    Homme Profil pro
    Ingénieur en systèmes embarqués
    Inscrit en
    Juin 2004
    Messages
    1 306
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 36
    Localisation : France, Eure (Haute Normandie)

    Informations professionnelles :
    Activité : Ingénieur en systèmes embarqués
    Secteur : High Tech - Électronique et micro-électronique

    Informations forums :
    Inscription : Juin 2004
    Messages : 1 306
    Points : 2 466
    Points
    2 466
    Par défaut
    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.
    -- Yankel Scialom

  7. #7
    Membre régulier Avatar de kaisse
    Profil pro
    Inscrit en
    Novembre 2003
    Messages
    100
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2003
    Messages : 100
    Points : 117
    Points
    117
    Par défaut
    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

  8. #8
    Modérateur
    Avatar de gangsoleil
    Homme Profil pro
    Manager / Cyber Sécurité
    Inscrit en
    Mai 2004
    Messages
    10 148
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Haute Savoie (Rhône Alpes)

    Informations professionnelles :
    Activité : Manager / Cyber Sécurité

    Informations forums :
    Inscription : Mai 2004
    Messages : 10 148
    Points : 28 113
    Points
    28 113
    Par défaut
    Pour plus d'infos sur RSA ( et le cryptage en général), je conseil les cours de S. Natkin : cours crypto
    "La route est longue, mais le chemin est libre" -- https://framasoft.org/
    Les règles du forum

  9. #9
    Membre régulier
    Homme Profil pro
    Analyste
    Inscrit en
    Août 2003
    Messages
    85
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Analyste
    Secteur : Services de proximité

    Informations forums :
    Inscription : Août 2003
    Messages : 85
    Points : 87
    Points
    87
    Par défaut
    J'ai suivi son cours cette année au CNAM, trés bon prof
    Air startout

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. [RSA] Calcul de la clé de décryptage d
    Par sozie9372 dans le forum Sécurité
    Réponses: 1
    Dernier message: 13/07/2005, 01h21
  2. RSA - Crypto
    Par chrdou dans le forum Sécurité
    Réponses: 4
    Dernier message: 11/04/2005, 15h09
  3. [WSAD] la V6: IRAD RSA RWD etc....
    Par jempe dans le forum Eclipse Java
    Réponses: 1
    Dernier message: 07/03/2005, 14h02
  4. Longueur de clés RSA et loi française
    Par Drizzt [Drone38] dans le forum Algorithmes et structures de données
    Réponses: 9
    Dernier message: 24/06/2004, 16h01
  5. cherche algos encryption en RSA et ELGAMAL
    Par Vermin dans le forum Algorithmes et structures de données
    Réponses: 2
    Dernier message: 04/11/2002, 09h58

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo