RSA calculer d

Ne sais pas si c'est le bon endroit pour demander une cryptographie question, mais voilà.

Je suis en train de travailler sur "d", au RSA, j'ai travaillé de p, q, e, n et øn;

p = 79, q = 113, e = 2621

n = pq                   øn = (p-1)(q-1)
n = 79 x 113 = 8927      øn = 78 x 112 = 8736

e = 2621
d =

Je ne peux pas l'air de trouver d, je sais que d est destiné à être une valeur.. ed mod ø(n) = 1. Toute aide sera appréciée

edit: un exemple e = 17, d = 2753, øn = 3120

17 * 2753 mod 3120 = 1

Cette question semble être hors-sujet parce que c'est sur la cryptographie
La question devrait être déplacé à crypto.stackexchange.com

OriginalL'auteur user3423572 | 2014-04-24

  1. 8

    Vous êtes à la recherche pour le modulaire inverse de e (mod n), qui peut être calculée en utilisant l'algorithme d'Euclide étendu:

    function inverse(x, m)
    a, b, u := 0, m, 1
    while x > 0
        q := b //x # integer division
        x, a, b, u := b % x, u, x, a - q * u
    if b == 1 return a % m
    error "must be coprime"

    Donc, dans votre exemple, inverse(17, 3120) = 2753 et inverse(2621, 8736) = 4373. Si vous ne voulez pas mettre en œuvre l'algorithme, vous pouvez demander Wolfram|Alpha pour la réponse.

    Cheers, j'ai entendu parler de wolfram alpha, je pensais que c'était un programme que vous avez eu à installer donc j'ai jamais pris la peine avec elle jusqu'à maintenant. la réponse que j'ai eu était 4373, à l'aide de la commande inverse de 2621 modulo 8736. Cependant si j'ai revérifier la réponse je reçois 0, n'est-il pas censé être 1? ", ed mod ø(n) = 1". Aussi je crois que vous êtes censé avoir 2 figuré dans le RSA, un petit et un grand nombre. l'un im essayant de travailler sur j'ai un grand "e", mais dans l'exemple, le "e" est petite et le "d" est grande
    J'ai fait une erreur la réponse que je reçois est 7936, pas 0.
    Ma solution originale de se méprendre sur les nombres; la réponse a été corrigé. Désolé pour la confusion. Dans RSA généralement de e n'a qu'un petit nombre de 1 bits de la représentation binaire, car il n'y a pas de calcul à faire pour 0-bits. Ainsi, e = 3 = 11b ou e = 65537 = 10000000000000001b sont communs.
    J'avais encore mal; la dyslexie doit être fort dotay. C'est corrigé maintenant, j'espère. De cambrai.

    OriginalL'auteur user448810

  2. 4

    L'algorithme que vous avez besoin est la Algorithme D'Euclide Étendu. Cela vous permet de calculer les coefficients de Bézout identité qui stipule que, pour deux entiers non nuls a et b, il existe des entiers x et y tels que:

    ax + by = gcd(a,b)

    Cela pourrait ne pas sembler utile dans l'immédiat, cependant, nous savons que e et φ(n) sont premiers entre eux, gcd(e,φ(n)) = 1. Si l'algorithme nous donne x et y tels que:

    ex + φ(n)y = gcd(e,φ(n))
           = 1
Re-arrange:
ex = -φ(n)y + 1

    C'est équivalent à dire ex mod φ(n) = 1, donc x = d.

    Merci pour la réponse. Je suis un peu perdu votre explication, j'ai du mal à appliquer la formule que vous avez fourni à mon problème. J'ai rencontré d'Euclide l'algorithme dans le passé, mais c'était seulement pour calculer le plus grand commun diviseur - pgcd
    Ma réponse est vraiment une description de la raison de l'algorithme fonctionne - le lien dans la première ligne de la "Algorithme d'Euclide Étendu" devrait vous diriger dans la bonne direction. Vous avez raison, l'habitude algorithme d'Euclide vous donne le PGCD, mais le "extended" version vous donne les coefficients de Bézout de l'identité, dont l'une est la d vous avez besoin.

    OriginalL'auteur Iridium

  3. 2

    Par exemple vous avez besoin pour obtenir d dans le prochain:

    3*d = 1 (mod 9167368)

    c'est aussi:

    3*d = 1 + k * 9167368, où k = 1, 2, 3, ...

    réécrire:

    d = (1 + k * 9167368)/3

    Votre d doit être un entier avec la plus bas k.

    Nous allons écrire la formule:

    d = (1 + k * fi)/e

    public static int MultiplicativeInverse(int e, int fi)
        {
            double result;
            int k = 1;
            while (true)
            {
                result = (1 + (k * fi)) /(double) e;
                if ((Math.Round(result, 5) % 1) == 0) //integer
                {
                    return (int)result;
                }
                else
                {
                    k++;
                }
            }
        }

    nous allons tester ce code:

    Assert.AreEqual(Helper.MultiplicativeInverse(3, 9167368), 6111579); //passed

    OriginalL'auteur Yuliia Ashomok