RSA: Private Schlüsselberechnung mit Extended Euclidean Algorithm

Question

Ich bin ein Gymnasiast, der ein Papier über RSA schreibt, und ich mache ein Beispiel mit einigen sehr kleinen Primzahlen. Ich verstehe, wie das System funktioniert, aber ich kann nicht für das Leben von mir den privaten Schlüssel mit dem erweiterten euklidischen Algorithmus berechnen.

Hier ist, was ich bisher getan haben:

• ich die Primzahlen p gewählt haben = 37 und q = 89 und berechnet N = 3293
• I (p-1) berechnet wurden (q -1) = 3168
• Ich habe eine Zahl e so gewählt, dass e und 3168 relativ prim sind. Ich überprüfe das mit dem euklidischen Standardalgorithmus, und das funktioniert sehr gut. Meine e = 25

Jetzt habe ich nur den privaten Schlüssel d berechnen müssen, die ed = 1 (mod 3168)

Mit dem erweiterten euklidischen Algorithmus erfüllen sollte d, so dass de + tN = 1 finden Ich bekomme -887 • 25 + 7 • 3168 = 1. Ich werfe die 7 weg und bekomme d = -887. Beim Versuch, eine Nachricht zu entschlüsseln, funktioniert dies jedoch nicht.

Ich weiß aus meinem Buch, dass d 2281 sein sollte, und es funktioniert, aber ich kann nicht herausfinden, wie sie bei dieser Nummer ankommen.

Kann jemand helfen? Ich habe versucht, dieses Problem für die letzten 4 Stunden zu lösen, und habe überall nach einer Antwort gesucht. Ich mache den erweiterten euklidischen Algorithmus von Hand, aber da das Ergebnis funktioniert, sollten meine Berechnungen stimmen.

Vielen Dank im Voraus,

Mads

Answer 1

Sie sind Sie so nah werden dich treten.

3168-887 = 2281.

Speziell, wenn Sie eine Mod x haben, dann muss A 0<=a<x erfüllen. Wenn dies nicht der Fall ist, addiere oder subtrahiere x so oft wie nötig, bis du in diesem Bereich bist. Dies wird modulare Arithmetik genannt.

Vielleicht möchten Sie über lineare Kongruenzen und Zahlentheorie nachlesen. Diese Themen sind Mathematik auf Hochschulniveau in Großbritannien (was du College nennen würdest), also mach dir keine Sorgen, wenn es ein bisschen seltsam erscheint. Eine lineare Kongruenz sagt einfach, dass -887 mod 3168 und 2281 mod 3168 eigentlich dasselbe sind, weil sie Teil der gleichen Klasse sind, die Klasse 2281 mod 3168 im erforderlichen Bereich. 2281+3168 mod 3168 wäre auch in dieser Klasse.

Viel Spaß!

P.S. PARI/GP ist eine Utility-Nummer, die Theoretiker für Berechnungen verwenden. Könnte einen Blick wert sein.