Wie erhält man die 3 Zahlen e, n und d ...

        aus denen der öffentliche Schlüssel (e und n) und der private Schlüssel (n und d) gebildet wird?

1. Man sucht 2 (i.a. sehr große) Primzahlen p und q
            Das Produkt sei n = p·q

2. Zu n wird die Anzahl der teilerfremden Zahlen von 1 bis n-1 je einschließlich bestimmt:   φ(n)

Siehe Demonstration unter dem Punkt Eulersche φ-Funktion
                        (grün: dazu gibt es in diesem Projekt interaktive Seiten)
φ(n) = (p-1)·(q-1)

Nach dem Satz von Euler gilt nun: xφ(n) ≡ 1 mod n ;       sofern x und n teilerfremd sind
      d.h. teilt man xφ(n) durch n, so bleibt der Rest 1 übrig (Satz A)

Erweiterung:   Satz von Euler erweitert
Es sei n = p·q das Produkt zweier verschiedener Primzahlen und
a, k ∈ IN0 (aus der Menge der natürlichen Zahlen oder Null)
es gilt dann: a k·φ(n)+1 ≡ a mod n.

Wenn man also   a k·φ(n)+1   durch n dividiert, dann bleibt als Rest der Division
    a (a < n) oder
    0 (n teilt a) oder
    a mod n (a > n) übrig.


3. Zu φ(n) wird ein teilerfremdes e gewählt:
      Damit gibt es ein zu e bzgl mod φ(n) multiplikatives Inverses d ,
      so dass gilt: e·d ≡ 1 mod φ(n)
            d.h. teilt man e·d durch φ(n), so bleibt der Rest 1 übrig (Satz B)


Nun hat man den öffentlichen Schlüssel:     Die Zahlen n und e
und den privaten Schlüssel: Die Zahlen n und d



... und was macht man damit:

Der Schlüsselbesitzer (SB) möchte mit einer Partnerin / einem Partner (PA) verschlüsselte Daten austauschen!
Als Schlüsselbesitzer gibt man den öffentlichen Schlüssel bekannt (ihn darf jeder sehen - es ist kein Geheimnis!).

!! Nun rechnet man immer     mod n


Wir starten mit der Nachrichtenübermittlung bei PA:
PA hat die zu übermittelnden Daten als eine Folge von Zahlen aufbereitet:
z0, z1, z2, .... zk
PA bestimmt für jede Zahl zi den Wert gi = zie mod n,   wobei i stellvertretend für 0 bis k steht.
Die Zahlen zi müssen kleiner als n aber möglichst groß sein:
z.B. könnte man bei einem Text immer 5 dreistellige Werte (ASCII-Werte) zu einer Zahl zi aufbauen:
        "ABCDE" ergäbe also eine Zahl 065 066 067 068 069 = 65066067068069

Die versendete geheime Nachricht ist also: g0, g1, ... , gk

.....

Auf dem Weg dorthin ist die Nachricht vor Angriffen sicher, mit ihr kann (praktisch) niemand etwas anfangen!
Man müsste alle Zahlen x zwischen 1 und n testen auf: xe mod n = gi.
Oder man müsste n in die beiden Primzahlbestandteile zerlegen: Das ist bis heute praktisch (noch) nicht im vernünftigem Zeitraum machbar.
Da "in Wirklichkeit" - nicht hier! - die Zahlen gi viele Hundert Stellen haben, ist das auch für Großcomputer nicht in Tagen/Wochen lösbar!
Hier in unserer "Spielwiese" wäre es ein Leichtes ...

.....

Die Nachricht landet beim Empfänger:
Nur der Empfänger (SB) ist im Besitz des privaten Schlüssels n und d.
Mit jeder Zahl gi der Nachricht wird folgendermaßen gerechnet:

gid mod n =
(zie)d mod n =
zie·d mod n = STAND1

      Wir erinnern uns an Satz B und schreiben für e·d = r·φ(n) + 1;     r ist Null oder eine natürliche Zahl

damit erhält man für STAND1:
zie·d mod n =
zir·φ(n) + 1   mod n =
 zir·φ(n) · zi   mod n =
 (ziφ(n))r · zi   mod n = STAND2

      Wir erinnern uns an Satz A und schreiben für ziφ(n) = s·n + 1;     s ist Null oder eine natürliche Zahl
      d.h. ziφ(n) mod n = 1

damit erhält man für STAND2
 (ziφ(n))r · zi   mod n =
1r · zi mod n =
zi mod n =
zi ... die Originalnachricht! (weil gilt: zi < n)