Primzahlen

Definition

Sei [math] p \in \mathbb{N} [/math]. Hat p genau zwei Teiler so wird p Primzahl genannt. Wir bezeichnen [math]\mathbb P[/math] als die Menge aller Primzahlen.

Arten von Primzahlen

Primzahlen werden aufgrund ihrer zahlentheoretischen Eigenschaften in verschiedene Kategorien zusammengefasst.

Primzahltupel

Jedes Paar [math]( p_1 , p_2 ) [/math]aus zwei Primzahlen [math]p_1[/math] und [math]p_2[/math] mit der Differenz 2 wird Primzahlzwilling genannt. Sie haben also die Form [math](p,p+2)[/math]. Ein Paar aus drei Primzahlen, die den Abstand von 2 haben wird hingegen als Primzahldrilling bezeichnet und hat die Form [math](p,p+2,p+4)[/math]. Nur das Paar [math](3,5,7)[/math] ist ein Primzahldrilling, da unter drei aufeinanderfolgenden ungerade Zahlen stets eine durch 3 teilbar ist. Diese Definition lässt sich auf Primzahltupel erweitern, die weitere Bezeichnungen einschließt wie Primzahlvierlinge oder Primzahlcousins. Die Paare mit Abstand 6 werden als sexy Primzahlen bezeichnet werden.

Mersenne-Primzahlen

Ist [math] p \in \mathbb{P}[/math] und hat die Form [math]2^{q}-1 [/math] für [math]q \in \mathbb{P} [/math] so wird [math]p[/math] als Mersenne-Primzahl bezeichnet. Diese sind Sonderfälle von Mersenne-Zahelen, welche die Form [math]2^{n}-1 [/math] haben, für [math] n \in \mathbb{N}[/math]. Der Name geht auf den französischen Theologen und Mathematiker Marin Mersenne (8.8.1588 bis 1.8.1648) zurück.

Dabei ist zu beachten, dass [math] q \in \mathbb{P} [/math] wieder eine Primzahl ist und dass nicht alle Zahlen der Form [math] 2^{p}-1 [/math] Primzahlen sind. Ein konkretes Beispiel für einen solchen Fall ist die Zahl [math]2^{11}-1 = 2047[/math], welche sich auch als [math] 23*89 [/math] darstellen lässt und somit keine Primzahl ist.

Mersenne-Primzahlen lassen sich im Binärsystem als Folge von Einsen schreiben. So hat Beispielsweise [math] 2^{19}-1 = 524.287 [/math] im Binärsystem die Form [math] 1111111111111111111_2 [/math] Gegenwärtig sind viele der größten bekannten Primzahlen solche Mersenne-Primzahlen, da durch den Lucas-Lehmer Test Zahlen der Form [math]2^{n}-1[/math] verhältnismäßig effizient auf die Primzahleigenschaft überprüft werden können.

Sophie-Germain Primzahlen

Gilt für eine Primzahl [math]p[/math], dass auch [math]2p+1[/math] eine Primzahl ist, so wird [math]p[/math] Sophie-Germain Primzahl genannt und [math]2p+1[/math] wird sichere Primzahl genannt.

Fermat Primzahlen

Primzahlen der folgenden Form werden Fermat Primzahlen genannt.

[math] p = 2^{2^n} + 1[/math]

mit einer ganzen Zahl [math]n \ge 0[/math].

Ramanujan Primzahl

Ramanujan-Primzahlen [math]R_n[/math] sind als kleinste Zahlen definiert, so dass für alle [math]x \geq R_n[/math] zwischen [math] x[/math] und [math]\tfrac {x}{2}[/math] mindestens [math]n[/math] Primzahlen liegen.

Zum Beispiel ist für [math] n = 1 [/math] die Ramanujan Primzahl [math]R_1 [/math] gleich [math]2[/math]. Diesen Fall ist äquivalent zum Bertrandschen Postulat.

Größte berechnete Primzahl

Im Jahr 2018 hat das Team um Patrick Laroche die errechnet, dass [math] 2^{82.589.933}-1 [/math] eine Primzahl ist. Diese Zahl hat 24.862.048 Stellen.

Satz von Euklid

Im Jahr 300 v.u.Z. hat Euklid von Alexandria bewiesen, dass es unendlich viele Primzahlen gibt.

In seinem Beweis durch Widerspruch trifft er die Annahme, dass es nur endlich viele Primzahlen gibt. Danach definiert er eine neue Zahl die eine neue Primzahl als Teiler hat oder welche selbst Primzahl ist. Somit erhalten wir einen Widerspruch und es kann keine endliche Menge aller Primzahlen geben. Es wurden mittlerweile dutzende weitere Beweise veröffentlicht.

Primzahlsatz

Ein wichtiger Teil der Arbeiten zu Primzahlen beschäftigt sich mit der Verteilung dieser. Hierfzu definieren wir zunächst die Primzahlfunktion, welche uns die Anzahl der Primzahlen bis zu gegebener Größe wiedergibt, und werden dann weitere Eigenschaften dieser Funktion festhalten.

Die Primzahlfunktion

Diese Funktion ist für beliebige [math]x \in \mathbb{R} [/math] definiert und gibt die Anzahl der Primzahlen an, die nicht größer als [math]x[/math] sind.

[math]\pi (x) := \left | \{p \in \mathbb{P} \mid p \le x\} \right |[/math]

[math]\pi(x)[/math] wird als Primzahlfunktion bezeichnet.

Die Primzahlfunktion: In der Graphik ist die Funktion bis zu einem Wert von 200 zu sehen.

Diese Funktion war auch ein zentrales Untersuchungsobjekt für Bertrand Riemann in seiner Arbeit über die Anzahl der Primzahlen unter einer gegebenen Größe in der er die Riemannsche Vermutung formuliert.

Der Primzahlsatz

Die Urfassung des Primzahlsatzes geht auf Gauß zurück, welche er im Alter von 15 Jahren, im Jahre 1792, formulierte.

Sei [math]\displaystyle \mathrm{Li}(x):=\int _{2}^{x}{\frac { \mathrm{d}t }{\ln {t}} } [/math] der Integrallogarithmus. Dann gilt [math]\displaystyle \lim _{{x\to \infty }}{\frac {\pi (x)}{\mathrm{Li(x)}}}=1 [/math]

Diese Eigenschaft wird als asymptotisch äquivalent bezeichnet und man schreibt

[math]\displaystyle \pi (x) \sim \mathrm{Li(x)} [/math]

Es kann gezeigt werden, dass gilt:

[math]\displaystyle Li(x) \sim \frac {x}{\ln(x)} [/math]

So formulieren wir den Primzahlsatz, wie er in den meisten Werken zu finden ist.

[math]\displaystyle \pi (x) \sim \frac{x}{\ln {x}} [/math]

Primzahlfunktion und Integrallogarithmusfunktion: Der Verlauf der Funktionen ist bis zum Wert 200 abgebildet.

Primzahlfunktion, Integrallogarithmusfunktion und x/ln(x): Alle drei Funktionen sind im Verlauf bis 200 abgebildet. Die Primzahlfunktion scheint hierbei von den anderen beiden Funktionen eingeschnürrt zu werden. Die Integrallogarithmusfunktion scheint insbesondere die Primzahlfunktion immer zu überschätzen. Der Mathematiker John Littlewood bewies aber 1913, dass [math] Li(x) [/math] an einem bestimmten Wert x die Primzahlfunktion unterschreiten muss. Stanley Skewes konnte zeigen, dass dies unter dem Wert [math]10^{10^{10^{34}}}[/math] passieren muss. Diese Zahl ist als Skewes-Zahl bekannt.

Der Mathematiker Hans von Mangoldt konnte im Jahre 1895 beweisen, dass der Primzahlsatz äquivalent dazu ist, dass die Riemannsche Zeta-Funktion keine Nullstellen hat bei Funktionswerten mit Realteil 1.

Primfaktorzerlegung

Es ist möglich jede natürliche Zahl eindeutig als Produkt von sogenannten Primfaktoren darzustellen.

Definition

• Eine Zahl [math] p [/math] heißt Primfaktor einer natürlichen Zahl [math] n [/math], wenn
  • [math] n [/math] durch [math] p [/math] ganzzahlig ohne Rest geteilt wird und
  • [math] p [/math] eine Primzahl ist.
• Die Darstellung einer natürlichen Zahl [math] n [/math] als Produkt ihrer Primfaktoren nennt man Primfaktorzerlegung.

Eigenschaften

• Eine Primfaktorzerlegung ist bis auf die Reihenfolge der Primfaktoren eindeutig.
• Da 1 keine Primzahl ist, ist die Primfaktorlzerlegung von 1 ein leeres Produkt.
• Der gleiche Primfaktor kann mehrmals in einer Primfaktorzerlegung vorkommen.
• Es gibt kein effizientes Verfahren, die Primfaktorzerlegung einer Zahl zu bestimmen.
• Für Zahlen mit sehr großen Primfaktoren ist es ein enormer Aufwand die Primfaktorzerlegung zu bestimmen.
• Wählt man die Primfaktoren groß genug, so benötigen sogar Hochleistungsrechner mehrere Jahre, um die Primfaktorzerlegung zu bestimmen.

Beispiele

\[ 6 = 2 \cdot 3 \] \[ 7 = 7 \] \[ 1003 = 17 \cdot 59 \] \[ 94684 = 2 \cdot 2 \cdot 23671 \]

Primzahltests

Sieb des Eratosthenes

Das Sieb des Eratosthenes ist eines der ältesten Verfahren zur Bestimmung aller Primzahlen, bis hin zu einer frei wählbaren oberen Grenze. Das Verfahren ist nach dem griechischen Mathematiker Eratosthenes von Kyrene (ca. 276 v.u.Z., † ca. 194 v.u.Z.) benannt. Konzeptionell arbeitet das Verfahren auf einer Liste aller Zahlen, beginnend mit der 2 bis hin zu der oberen Grenze N. Anschließend werden nacheinander alle Zahlen in dieser Liste betrachtet. Ist die betrachtete Zahl nicht markiert, so ist sie eine Primzahl und alle ihre Vielfachen können gestrichen werden. Ist die Zahl bereits markiert, kann man zur nächsten weitergehen. So werden nacheinander alle Primzahlen aus der Liste "herausgesiebt".

Ablauf des Algorithmus

1. Wähle eine obere Grenze N, bis zu der alle Primzahlen bestimmt werden sollen.
2. Schreibe alle natürlichen Zahlen von 2 bis N auf (um das Ganze anschaulicher zu machen ordnet man die Zahlen meist in einem rechteckigen Schema an, wobei hier die Vielfachen von 10 am Ender einer Reihe stehen). Im Folgenden werden alle Zahlen die keine Primzahlen sind gestrichen.
3. Begonnen wird mit der 2. Die 2 selbst ist eine Primzahl, es können aber alle Vielfachen von 2 gestrichen werden, da sie selbst keine Primzahlen sind.
4. Die nächste nicht gestrichene Zahl ist die Primzahl 3. Wieder können alle Vielfachen von 3 gestrichen werden. Begonnen werden kann hier mit der 9, da die 6 bereits als ein Vielfaches von 2 gestrichen wurde.
5. Die 4 wurde bereits im 2. Schritt gestrichen und die nächste Zahl kann betrachtet werden.
6. Dieses Vorgehen wird mit allen folgenden Zahlen wiederholt, bis die Quadratwurzel von N erreicht wurde. Ist eine Zahl noch nicht gestrichen worden, wenn man sie betrachtet, so ist sie eine Primzahl und ihre Vielfachen können gestrichen werden. Andernfalls kann die nächste Zahl betrachtet werden.

Der Algorithmus selbst ist recht Intuitiv und leicht nachzuvollziehen. Auch erklärt sich durch den Algorithmus, wie der Name "Sieb des Eratosthenes" zu stande kommt.

Wer sich anchschauen möchte, wie der Algorithmus in C++ aussieht, findet hier eine Implementierung.

#include <iostream>
#include <cmath>

int main(int argc, const char** argv) {
    // erstelle eine Liste der Laenge N. Zu Beginn sind keine Zahlen gestrichen was durch 'false' dargestellt wird
    const unsigned int N = 100;
    bool Liste[N] = { false };

    // iteriere über alle Zahlen in der Liste bis zur Wurzel von N
    for (int i = 2; i <= std::sqrt(N); i++) {

        // falls Index noch nicht gestrichen sind
        if (Liste[i] == false) {

            // streiche alle Vielfachen beginnend mit dem Quadrat der gegenwärtig betrachteten Zahl an der Stelle i
            for (int j = i*i; j < N; j += i) {
                Liste[j] = true;
            }
        }
    }
    
    // gebe alle Primzahlen aus
    for (int i = 2; i <= N; i++){
        if (Liste[i] == false){
            std::cout << i << std::endl;
        }
    }

    return 0;
}

Eine beispielhafte Ausführung des Algorithmus für N=100

Lucas-Lehmer Test

Der Lucas-Lehmer-Test ist ein Verfahren um zu überprüfen, ob es sich bei einer gegebenen Mersenne-Zahl auch um eine Mersenne-Primzahl handelt. Der Test geht auf den französischen Mathematiker François Édouard Anatole Lucas (*4.4.1842, † 3.10.1891) zurück, wurde aber erst 1930 von dem US-Amerikanischen Mathematiker Derrick Henry Lehmer (* 23.2.1905, † 22.5.1991) entwickelt.

Ablauf

Der Lucas-Lehmer-Test verwendet die sogenannte Lucas-Folge. Diese ist definiert durch \[ L_{0} := 4 \\ L_{n+1} := (L_{n}^{2} - 2) Mod \ M_{p} \] Dabei ist [math] p \in \mathbb{P}\backslash \{2\} [/math] und [math] M_p [/math] die zu überprüfende Mersenne-Zahl.

Für [math] M_p [/math] gilt: [math] M_p \in \mathbb{P} \Leftrightarrow L_{p-2} = 0[/math]

Primzahlen in der Natur

Es existieren Zikadenarten, die sich in einem festen Abstand von Jahren massenhaft über der Erde vermehren und danach wieder unter die Erde zurückkehren. In dieser Zeit sind sie weniger gut vor ihren Fressfeinden geschützt. Die Zikaden haben also einen Vorteil, wenn sie in Jahren über der Erde sind, in denen weniger Fressfeinde auftreten. Einige Zikadenarten nutzen genau diesen Vorteil: Sie vermehren sich im Abstand von 13 oder 17 Jahren über der Erde.

Was passiert also mit ihren Fressfeinden? Für solche, die ohnehin in jedem Jahr auftreten, ändert sich nichts. Allerdings gibt es auch solche, die selbst nur in gewissen Jahren auftreten. Beispielsweise existiert eine zikadenjagende Wespe, die alle zwei bis drei Jahre auftritt. Nehmen wir also eine Art an, die alle 2 Jahre auftritt. Würden sich die Zikaden alle 12 Jahre vermehren, so würde in jedem dieser Jahre auch die Wespenart auftreten und die Zikaden hätten es mit deutlich mehr Fressfeinden zu tun. Nun ist der Zyklus der Zikaden aber 13 Jahre lang. Sie müssen also nur alle 26 Jahre mit jener Wespenart fertig werden. Somit haben sie einen deutlichen Vorteil darin, sich zu vermehren.

Primzahlen in der Kryptographie

Die Tatsache, dass es bis heute keine effiziente Methode zum Zerlegen einer großen Zahl in ihre Primfaktoren gibt, ermöglicht einige Anwendungen in der Kryptographie. So verwenden einige Verfahren, die eine verschlüsselte Kommunikation gewährleisten, Primzahlen. Wie wichtig solche Verfahren sind, wird deutlich, wenn man sich ansieht, wobei diese benutzt werden. Das umfasst Anwendungen wie Emails, Chats und Internettelefonie, aber auch weitaus sensiblere Daten, wie beispielsweise beim Onlinebanking.

RSA-Verfahren

Das RSA-Verfahren wurde 1978 von Ron Rivest, Adi Shamir und Leonard Adleman vorgestellt und nach ihnen benannt. Es ist ein public-key Krytosystem, nutzt also ein Schlüsselpaar, das aus einem öffentlichen und einem privaten Schlüssel besteht. Dies hat den Vorteil, dass der öffentlichen Schlüssel nicht geheim weitergegeben werden muss und so der Schlüsselaustausch kein Sicherheitsrisiko darstellt.

Public-key System

Bei einem Public-key System besitzt jeder Anwender sein eigenes Schlüsselpaar aus privatem und öffentlichen Schlüssel und somit auch sein eigenes Ver- und Entschlüsselungsverfahren. Dabei wird der geheime Schlüssel vom Anwender geheimgehalten, während der öffentliche Schlüssel an alle anderen Anwender, mit denen kommuniziert wird, verteilt wird.

Der Verschlüsselungsprozess wird mit [math] D [/math] bezeichnet, der Entschlüsselungsprozess mit [math] E [/math]. Dabei steht [math] D [/math] für Decryption und [math] E [/math] für Encryption. Ein Schlüsselpaar besteht aus zwei Zahlen. Dabei gelten für eine Nachricht im Klartext [math]M[/math] die folgenden Eigenschaften:

1. [math] D(E(M)) = M [/math]
2. [math] E(D(M)) = M [/math]
3. [math]E[/math] und [math]D[/math] sind für sich genommen leicht zu berechnen
4. [math]E[/math] kann aus [math]D[/math] nicht einfach berechnet werden

Ein Entschlüsselungsprozess [math] E [/math] heißt trap-door one-way function, wenn er die Eigenschaften a, c und d erfüllt. Handelt es sich außerdem um einen Prozess, der b erfüllt, so wird daraus eine trap-door one-way permutation. Dann ist jeder Geheimtext eine potenzielle Nachricht und jede Nachricht ein potenzieller Geheimtext.

Betrachten wir nun das Konzept des RSA-Verfahrens an einem Beispiel. Im Folgenden möchte Felix eine Nachricht an Ari schicken. Dementsprechend besitzt Felix die Schlüsselverfahren [math] D_F [/math] und [math] E_F [/math], Ari entsprechend [math] D_A [/math] und [math] E_A [/math].

Wie sieht nun der Nachrichtenaustausch aus? Zuallererst müssen Felix und Ari ihre öffentlichen Schlüssel austauschen. Somit erhält Ari die Möglichkeit [math] D_F [/math] durchzuführen, Felix [math] D_A [/math].

Nun führt Felix auf seiner Nachricht [math] D_A [/math] aus. Er nutzt also den öffentlichen Schlüssel von Ari und versendet dann die Nachricht. Bekommt Ari nun die verschlüsselte Nachricht, so kann er sie mit [math] E_A [/math] entschlüsseln. Da nur er seinen privaten Schlüssel hat, kann auch niemand anderes die Nachricht entschlüsseln und lesen. Für die Antwort nutzt Ari dann [math] D_F [/math] für die Verschlüsselung.

Die Mathematik dahinter

Die Nachricht

Die Nachricht [math]M[/math] selbst wird als positive ganze Zahl zwischen [math]0[/math] und [math] n-1 [/math] kodiert, damit man leicht mit ihr rechnen kann. Wie groß [math] n [/math] ist, hängt vom einzelnen Schlüsselpaar ab. Betrachtet man ein realistisches Szenario, so gilt [math] n \geq 10.000 [/math], wobei [math] n [/math] meist noch um einiges größer als dieser Wert ist. Ist die Nachricht zu groß, so wird sie in einzelne Blöcke aufgeteilt und jeder Block einzeln betrachtet. Eine mögliche Umwandlung von Buchstaben in Zahlen ist beispielsweise das ASCII-Format.

Die Schlüsselpaare

Jeder der beiden Schlüssel besteht aus einem Tupel. Wir bezeichnen den zu [math] E [/math] gehörenden privaten Schlüssel mit [math] P [/math] und den zu [math] D [/math] gehörenden öffentlichen Schlüssel mit [math] O [/math]. \[ P = (e,n) \hspace{2cm} O = (d,n) \ \text{ wobei }e, d \text{ positive ganze Zahlen sind.} \] Dabei gilt für den Ver- und Entschlüsselungsprozess eines Klartextes [math]M[/math] und eines Geheimtextes [math]C[/math]

• [math] C \equiv D(M) \equiv M^d \text{ mod } n [/math]
• [math] M \equiv E(C) \equiv C^e \text{ mod } n [/math]

Erzeugen der Schlüssel

1. Zwei zufällige große Primzahlen [math] p[/math] und [math] q [/math] auswählen. Diese sollten in der Realität mehrere hundert Stellen haben.

   Setze nun [math] n = p \cdot q [/math]. Weil [math] p [/math] und [math] q [/math] so groß sind, ist es nicht in realistischem Zeitaufwand möglich, aus [math] n [/math] wieder [math] p [/math] und [math] q [/math] zu berechnen.

2. Eine zufällige ganze Zahl [math] d [/math] wählen, die folgende Bedingung erfüllt

   [math] \text{ggT}(d, (q-1) \cdot (p-1)) = 1[/math]

   [math]\text{ggT}[/math] bezeichnet dabei den größten gemeinsamen Teiler, [math]d[/math] und [math] (q-1) \cdot (p-1)[/math] müssen also teilerfremd sein.

3. [math] e [/math] aus [math] d [/math] bestimmen

   [math] \ e \cdot d = 1 (\text{ mod } \varphi(n))[/math]

   [math] \varphi(n)[/math] bezeichnet die Eulersche [math] \varphi[/math]-Funktion

Warum funktioniert das?

Nun gilt noch zu beweisen, dass dieses Verfahren für (fast) alle Nachrichten [math] M [/math] funktioniert.

Zuerst betrachten wir [math] \varphi(n) [/math]. Da für eine beliebige Primzahl [math] m [/math] gilt: \[ \varphi(m) = m-1 \] und [math] \varphi [/math] multiplikativ für teilerfremde Zahlen ist, folgt für [math] n [/math] : \[ \varphi(n) = \varphi(p \cdot q) = (p-1) \cdot (q-1) = n - (p+q) + 1 \]

Wie hängt nun [math] \varphi(n) [/math] mit [math] e [/math] und [math] d [/math] zusammen?
Da [math] d [/math] teilerfremd zu [math] \varphi(n) [/math] ist, existiert ein multiplikatives Inverses [math] e [/math] im Ring [math] \mathbb{Z}/\varphi(n)\mathbb{Z} [/math]: \[ e \cdot d \equiv 1 (\text{mod} \ \varphi(n)) \]

Bisher gilt für den Ver- und Entschlüsselungsprozess \[ D(E(M)) \equiv (E(M))^d \ (\text{mod} \ n) \equiv (M^e)^d \ (\text{mod} \ n) = M ^{e\cdot d} \ (\text{mod }n) \] und analog \[ E(D(M)) \equiv (D(M))^e \ (\text{mod} \ n) \equiv (M^d)^e \ (\text{mod} \ n) = M ^{e\cdot d} \ (\text{mod }n) \]

Außerdem existiert eine ganze Zahl [math] k [/math], für die gilt: \[ M^{e\cdot d} \equiv M^{k\cdot \varphi(n) + 1} \ (\text{mod }n) \]

Nun gilt es noch zu zeigen, dass für alle [math] M [/math] gilt: [math] M^{e\cdot d} = M \ (\text{mod }n) [/math]

Hierzu werden [math] p [/math] und [math] q [/math] getrennt betrachtet. Dies ist nach dem chinesischen Restsatz möglich, auf den wir hier nicht näher eingehen werden.

Betrachten wir [math] M^{e\cdot d} = M \ (\text{mod }p) [/math], so gilt:

1. Falls [math] M = 0\ (\text{mod }p)[/math], dann ist [math] M [/math] ein Vielfaches von [math] p [/math]. Dann gilt: [math] M^{e\cdot d} = 0 = M \ (\text{mod }p) [/math]
2. Falls [math] M \not = 0\ (\text{mod }p)[/math], dann gilt nach dem Satz von Euler-Fermat
   

[math] M^{ed} = M^{ed-1} M = M^{k(p-1)}M = (M^{p-1})^kM = 1^kM = M (\text{mod } p) [/math]

Betrachten wir [math] M^{e\cdot d} = M \ (\text{mod }q) [/math], so gilt analog:

1. Falls [math] M = 0\ (\text{mod }q)[/math], dann ist [math] M [/math] ein Vielfaches von [math] q [/math]. Dann gilt: [math] M^{e \cdot d} = 0 = M \ (\text{mod }q) [/math]
2. Falls [math] M \not = 0\ (\text{mod }q)[/math], dann gilt nach dem Satz von Euler-Fermat
   

[math] M^{ed} = M^{ed-1} M = M^{k(q-1)}M = (M^{q-1})^kM = 1^kM = M (\text{mod } q) [/math]

Da die Bedingung für beide Faktoren gezeigt wurde, gilt [math] M^{e\cdot d} = M \ (\text{mod }n)[/math] nach dem chinesischen Restsatz auch für [math] n = pq [/math].

Einfaches Beispiel

Teil 1: Schlüssel generieren

1. Wir wählen zwei Primzahlen [math] p = 7, \ q = 11 [/math]
2. Dann gilt [math] n = pq = 77 [/math]
3. Wir wählen eine ganze Zahl [math] e = 29 [/math], wobei [math] p-1 = 6 [/math] und [math] q-1 = 10 [/math] teilerfremd zu [math] e [/math] sind.
4. Der öffentliche Schlüssel ist dann [math] O=(d,n) = (29, 77)[/math]
5. [math] \varphi(77) = (p-1) (q-1) = 6 \cdot 10 = 60 [/math]
6. Für [math] d [/math] soll gelten: [math] ed + k \cdot \varphi(n) = 1[/math], also [math] 29\cdot d + k \cdot 60 = 1 [/math] für ein [math] k \ \in \mathbb{Z}[/math]. Somit ist [math] d=29 [/math] und [math] k = -14\lt /math. Somit ist der private Schlüssel \lt math\gt P=(e,n) = (29,77)[/math].

Wählt man deutlich größere Primzahlen [math] p [/math] und [math] q [/math], so ist die Berechnung von [math] e [/math] aus [math] d [/math] oder andersherum ohne die Kenntnis von [math] p [/math] und [math] q [/math] sogar für Computer zu aufwendig.

Teil 2: Die Verschlüsselung

Felix möchte die Zahl 13 verschlüsseln und an Ari senden. Hierzu rechnet er: \[ C = 13^{29}\ (\text{mod } 77) = 6 \] Diese 6 schickt Felix nun als Geheimtext an Ari.

Teil 3: Die Entschlüsselung

Ari rechnet nun: \[ M = 6^{29}\ (\text{mod } 77) = 13 \]

Und erhält somit wieder die 13 als Klartext.

Signatures

Zwar schützt dieses Verfahren soweit vor fremden Mitlesern, aber es ist immernoch möglich, falsche Nachrichten im Namen von Felix zu versenden. Nehmen wir an, Johanna möchte Ari im Namen von Felix eine Nachricht senden. Mit dem bisherigen Verfahren kann Johanna ebenso Aris öffentlichen Schlüssel verwenden und Ari kann sich nicht sicher sein, ob die Nachricht tatsächlich von Felix stammt oder nicht.

Um dieses Problem zu lösen, wird die Eigenschaft b des Public-key Systems genutzt. Einer Nachricht wird eine Signatur angehängt, die mit dem privaten Schlüssel ver- und mit dem öffentlichen Schlüssel entschlüsselt wird. Will also Felix nun Ari eine Nachricht schicken, so verschlüsselt er zuerst nur die Signatur mit seinem privaten Schlüssel, dann die ganze Nachricht mit Aris öffentlichem Schlüssel. Für die verschlüsselte Nachricht [math] C [/math] ergibt sich also

\[ C = E_A(D_F(M)) \]

Kommt die Nachricht nun bei Ari an, so entschlüsselt er zuerst die ganze Nachricht mit seinem privaten Schlüssel und dann die Signatur mit dem öffentlichen Schlüssel von Felix. Für die Entschlüsselung ergibt sich also

\[ M = D_A(E_F(C))) \]

Insgesamt ergibt sich also

\[ M = D_A(E_F(E_A(D_F(M)))) \]

Nun kann Ari anhand der Signatur erkennen, ob die Nachricht von Felix stammt, denn nur wenn der korrekte private Schlüssel verwendet wurde, ist die Signatur nun korrekt.

Autoren

Johanna Riedel, Felix Elser, Arianit Miftari