RSA-Berechnung d

Nicht sicher, ob dies ist der richtige Ort, um Fragen einer Krypto-Frage, aber hier geht.

Ich bin versuchen zu arbeiten, "d", "RSA", " ich habe gearbeitet, aus p, q, e, n und ø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 =

Ich kann nicht scheinen, um herauszufinden, d, ich weiß, dass d gemeint ist ein Wert,.. ed mod-ø(n) = 1. Jede Hilfe wird dankbar sein

edit: ein Beispiel wäre z.B. e = 17, d = 2753, øn = 3120

17 * 2753 mod 3120 = 1

  • Diese Frage scheint off-topic, weil es um Kryptographie
  • Die Frage verschoben werden soll crypto.stackexchange.com
InformationsquelleAutor user3423572 | 2014-04-24
  1. 8

    Du suchst die modulare inverse von e (mod n), die berechnet werden können mit dem erweiterten euklidischen Algorithmus:

    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"

    So, in Ihren Beispielen inverse(17, 3120) = 2753 und inverse(2621, 8736) = 4373. Wenn Sie nicht möchten, die den Algorithmus implementieren, können Sie Fragen, Wolfram|Alpha für die Antwort.

    • Cheers, hörte ich von wolfram alpha, ich dachte, es war ein Programm, das Sie installieren musste, so dass ich nie die Mühe mit ihm bis jetzt. die Antwort, die ich bekam, war 4373 durch die Verwendung des Befehls - inverse von 2621 modulo-8736. Aber wenn ich erneut die Antwort, die ich erhalten 0, ist es nicht sein soll, 1? "ed mod-ø(n) = 1". Auch ich glaube, dass Sie gemeint sind zu haben, 2 tauchten in der RSA eine kleine und eine große Anzahl. der eine im, der versucht zu arbeiten, ich habe ein großes "e", aber in dem Beispiel das "e" klein und das "d" ist groß
    • Ich habe einen Fehler gemacht die Antwort, die ich bekommen ist, 7936, nicht 0 ist.
    • Meine ursprüngliche Lösung verlosen die zahlen; die Antwort wurde nun behoben. Sorry für die Verwirrung. In RSA in der Regel e hat nur eine kleine Anzahl von 1-bits in Ihrer binären Darstellung, denn es gibt keine Berechnung zu tun, für die 0-bits. Also, e = 3 = 11b oder e = 65537 = 10000000000000001b üblich sind.
    • Hatte ich es noch falsch; die Legasthenie muss stark sein dotay. Es ist jetzt behoben, hoffe ich. Humbug.
    InformationsquelleAutor user448810
  2. 4

    Den Algorithmus, den Sie brauchen, ist die Erweiterten Euklidischen Algorithmus. Dies ermöglicht Ihnen, die Berechnung der Koeffizienten von Bézout Identität, die besagt, dass für zwei beliebige nicht-null-Ganzzahlen a und b gibt es ganze zahlen x und y so dass:

    ax + by = gcd(a,b)

    Dies mag nicht unmittelbar nützlich, aber wir wissen, dass e und φ(n) sind coprime, gcd(e,φ(n)) = 1. Also der Algorithmus gibt uns x und y so dass:

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

    Dies ist äquivalent zu sagen ex mod φ(n) = 1, so x = d.

    • Danke für die Antwort. Ich habe ein wenig verloren, Ihre Erklärung, die ich bin kämpfen, um die Formel anwenden, die Sie zur Verfügung gestellt zu meinem problem. Ich bin gekommen, über Euklid ' s Algorithmus in der Vergangenheit, aber es war nur zur Berechnung eines größten gemeinsamen Teiler - ggT
    • Meine Antwort ist wirklich eine Beschreibung, warum der Algorithmus funktioniert - der link in der ersten Zeile, um zu den "Erweiterten euklidischen Algorithmus" sollte Sie in die richtige Richtung. Du hast Recht, dass die übliche euklidische Algorithmus gibt Sie den GCD, aber die "extended" - version bietet Ihnen die Koeffizienten für Bézout Identität - eine davon ist die d Sie brauchen.
    InformationsquelleAutor Iridium
  3. 2

    Beispielsweise die Sie brauchen, um d in die nächste:

    3*d = 1 (mod 9167368)

    ist das ebenso:

    3*d = 1 + k * 9167368, wo k = 1, 2, 3, ...

    umschreiben:

    d = (1 + k * 9167368)/3

    Ihre d muss die ganze Zahl mit dem niedrigsten k.

    Schreiben wir die Formel:

    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++;
                }
            }
        }

    let ' s test folgenden code:

    Assert.AreEqual(Helper.MultiplicativeInverse(3, 9167368), 6111579); //passed
    InformationsquelleAutor Yuliia Ashomok
Schreibe einen Kommentar