Répondre à la discussion
Affichage des résultats 1 à 11 sur 11

[RSA] Besoin d'une info



  1. #1
    Yruama

    [RSA] Besoin d'une info


    ------

    Bonjour à tous,

    Je viens de m'inscrire particulièrement pour cette question. J'aimerais avoir une précision sur un point de l'algorithme RSA,plus précisément au décryptage.
    La clé privée étant composé du couple (d, n), pour trouver d, j'ai trouvé sur le net, deux moyens :
    le plus utilisé e*d % phi(n) = 1 et un autre d = e^-1 % phi(n). J'aimerais avoir plus explications sur ce dernier, comment on le trouve, ect... ?

    Merci d'avance, A++

    -----

  2. #2
    Yruama

    Re : [RSA] Besoin d'une info

    UP

    Le message est peut-etre à changer de catégorie car il est plus orienté math...

  3. #3
    JPL
    Responsable des forums

    Re : [RSA] Besoin d'une info

    Voila, c'est déplacé.
    Rien ne sert de penser, il faut réfléchir avant - Pierre Dac

  4. #4
    Yruama

    Re : [RSA] Besoin d'une info

    Merci bien.
    En espérant qu'il y est plus de réponse ici...

  5. A voir en vidéo sur Futura
  6. #5
    Witten

    Re : [RSA] Besoin d'une info

    Bonjour,

    La clé privée étant composé du couple (d, n), pour trouver d, j'ai trouvé sur le net, deux moyens :
    le plus utilisé e*d % phi(n) = 1 et un autre d = e^-1 % phi(n). J'aimerais avoir plus explications sur ce dernier, comment on le trouve, ect... ?
    Pour résoudre e*d % phi(n) = 1 il suffit d'appliquer l'algorithme d'Euclide étendu, à condition de connaître phi(n), ce qui nécessite de connaître sa décomposition en facteurs premier...

    e*d % phi(n) = 1 <=> e*d + k*phi(n) = 1

    Pour la deuxième je vois malheureusement pas trop, on peut l'écrire comme ça :

    e^-1 % phi(n) = d <=> d + k*phi(n) = e^-1

    Mais que représente e^-1? d est normalement appelé l'inverse de e modulo phi(n). Donc e^-1 = d? mais ça ne donne pas de sens.

    J'espère que quelqu'un d'autre pourra nous éclairer.

  7. #6
    Yruama

    Re : [RSA] Besoin d'une info

    Merci pour ta réponse Witten, pour le la 1er, j'étais au courant. C'est surtout la 2eme qui m'embete, comme toi apparamment...

    Mince, j'ai remarqué une erreur, c'est pas phi(n) mais n.
    n= p*q
    phi(n) = (p-1) * (q-1)
    J'edite mes messages

    A++, si quelqu'un peut nous éclairer.

  8. #7
    Yruama

    Re : [RSA] Besoin d'une info

    Oups non non pour trouver d, on utilise bien phi(n) désolé

  9. #8
    Slasher2610

    Re : [RSA] Besoin d'une info

    J'ai du mal à comprendre ton problème avec les notations que tu utilises (essaye d'apprendre un peu de LaTeX pour clarifier un peu tout ça !).

    Je peux sinon avancer quelques idées en supposant :



    que ce que tu considère comme la clé privée, c'est le coupe de nombres premiers qui sert à calculer . N qui constitue avec (qui lui doit être premier avec ) la clé publique est donc connue mais il est impossible de remonter à p et q (la sécurité de l'algorithme repose dessus) car ce sont des nombres premiers volontairement choisis très grands. Comme tu dois t'en douter, il n'y a pas de règle mathématique pour calculer un nombre premier, on sait juste à quelles conditions on le considère comme premier. En particulier se sont des ordinateurs qui tournent pendant des milliers d'heures et qui se chargent de vérifier ces conditions avec des algorithmes probabilistes. Actuellement la plus grande factorisation de N l'a été pour un nombre de 200 chiffres.

    que tu t'es mal exprimé et que ce que tu considères comme clé privée c'est la clé publique, c'est à dire avec la clé de cryptage qui doit être un nombre premier avec (cf plus haut) et que correspond à l'inverse de dans . Pour ce faire il faut résoudre soit une identité de bezout : que l'on peut résoudre avec l'algorithme d'eucilde étendu ce qui n'est pas possible manuellement pour de grandes valeurs de mais résolvable facilement pour de petites valeurs ( étant pris conventionellement petit). Tout dépend donc de la clé publique .



    Pour information, si est très grand et que deux personnes utilise le même mais des et différents mais premiers entre eux et qu'une troisième veut leur envoyer à chacun le même message qui sera crypté en et alors un hacker, s'il réussi a intercepter et peut alors les décrypter et trouver en résolvant l'identité de Bezout : . On aura alors soit soit .

    D'après mes cours à l'INSA de Lyon.

    Tchao.

  10. #9
    Yruama

    Re : [RSA] Besoin d'une info

    Salut Slasher2610 et merci pour ta réponse.

    Aparamment on utilise pas les même lettres pour définir les clés.

    que ce que tu considère comme la clé privée, c'est le coupe de nombres premiers
    Pour moi la clé privée : (d, n)
    n = p*q
    phi(n) = (p-1)*(q-1)
    e*d % phi(n) = 1

    Mais, on peut trouver p et q, par la factorisation de n non ?

    que tu t'es mal exprimé et que ce que tu considères comme clé privée c'est la clé publique, c'est à dire (e, N)
    Mh, je considère bien la clé publique comme (e, n)
    e et phi(n) premiers entre eux
    phi(n) = (p-1)*(q-1)

    A part les problèmes de lettre je pense que j'ai pas dit d'autres bétise ^^ ....

    Mais ce que je veux ca voir, c'est ceci : d = e^-1 % phi(n)
    d = 1/e % (p-1) * (q-1)
    D'où ca sort ?

    Merci encore.
    A++

  11. #10
    rvz

    Re : [RSA] Besoin d'une info

    Salut,

    A priori,
    e*d=1 %phi(n) est équivalent à dire d = e^{-1} %phi(n).
    C'est juste dire qu'il y a unicité de l'inverse -quand elle existe- dans .

    __
    rvz

  12. #11
    Yruama

    Re : [RSA] Besoin d'une info

    Mh ok ok merci beacoup !!!

Discussions similaires

  1. Chimiluminescence de la lophine, besoin info
    Par Azarius dans le forum Chimie
    Réponses: 4
    Dernier message: 14/08/2007, 10h59
  2. besoin de conseils code RSA
    Par mel83160 dans le forum Mathématiques du supérieur
    Réponses: 1
    Dernier message: 15/05/2007, 18h32
  3. j'ai besoin d'une tite info...
    Par myxy59 dans le forum Orientation après le BAC
    Réponses: 1
    Dernier message: 22/04/2006, 20h41
  4. Besoin d'une info :)
    Par border_line dans le forum Secourisme spécial Croix-Rouge
    Réponses: 1
    Dernier message: 10/11/2005, 18h29