Logo

Magic Highstone's World - Fermat s little Theorem

Fermats Little Theorem

Definition

Fermat hat sich quasi mit dem Grundprinzip von RSA beschäftigt. Sehr nett eigentlich vom ihm.

Aber fangen wir einfach mal an, was wollte uns Fermat in seiner kleinen Theorie erzählen?

Nun ersteinmal hat er sich eine Funktion phi(n) definiert:

phi(n) = Anzahl der zu n teilerfremden Zahlen, die kleiner n sind incl. 1

Teilerfremd bedeutet, daß zwei ganze Zahlen einen ggT von 1 zueinander besitzen.

Ein kleines Beispiel hierzu:

phi(10) = 5  {1,3,5,7,9}
phi(20) = 10 phi(10) zzgl. {11,13,15,17,19}
phi( 9) = 6  {1,2,4,5,7,8}

Für das Verständnis des RSA-Algorithmus möchte ich noch ein paar Anmerkungen zur phi-Funktion verlieren:

  1. Sei p eine Primzahl
    => phi(p) = p - 1
  2. Sein p,q Primzahlen:
    => phi(p*q) = p*q - 1 -(q-1)-(p-1)
                     = (p-1) * (q-1)

Nachdem wir diese tolle Funktion jetzt besitzen, müssen wir sie ja auch in einem tollem mathematischen Satz verwenden, weil Mathematiker lieben Sätze:

Sei m teilerfremd zu n,
so gilt:
mphi(n) mod n = 1 .

Logisch begründen kann ich das leider nicht, aber welches Beispiel man sich auch wählt, es stimmt einfach:

Sei m = 4 und n = 5        => phi(5) = 4
41 mod 5 = 4
42 mod 5 = 1
43 mod 5 = 4
44 mod 5 = 1

Fermat for RSA

Die kleine Theorie von Fermat müssen wir noch ein wenig abwandeln, damit sie im RSA Algorithmus zur Anwendung kommen kann. Die Abänderung ist eigentlich recht klein, aber sie hat eine große Wirkung:

Gegeben sein zwei beliebige Zahlen n und m,
so gilt:
mphi(n)+1 mod n = m.

Im Gegensatz zur ursprünglichen Definition müssen die Zahlen n und m nicht teilerfremd sein!!!!

Auch hierzu ein kleines Beispiel:

Sei m = 4 und n = 5        => phi(5)+1 = 5
41 mod 5 = 4
42 mod 5 = 1
43 mod 5 = 4
44 mod 5 = 1
45 mod 5 = 4

Schauen wir uns diese Formel mal genauer an. Um die Gedanken ein wenig in die richtige Richtung zu steuern, nennen wir m mal Message. Wir können also eine beliebige Message mit einem durch eine zweite beliebige Zahl n definierten Exponent phi(n)+1 potenzieren und daraufhin mit n modulieren und erhalten unsere Message zurück.

Um dieses schöne Konstrukt im RSA verwenden zu können, müssen wir es irgendwie hinbekommen, dass wir in der Formel noch einen Zwischenschritt einbauen, so daß irgendwo auch mal eine Cipher als Ergebnis erscheint.Denn im Moment führen wir quasi Chiffrierung und Dechiffrierung in einem Schritt durch. Der Weg führt über die Aufteilung des Exponenten, aber hierzu mehr im RSA Abschnitt.