# RSA-Verfahren und RSA-Signatur

Mathematik in wxMaxima www.mathematik-verstehen.de Haftendorn Dez 2010

### Handlinghilfen

Achtung: Durch Anklicken der linken Zellmarkierung kann man die 
Abschnitte und auch einzelne Zellen aufklappen und auch wieder zuklappen.
Dazu Shift halten, dann werden auch alle Unterebenen aufgeklappt.

Endung *.wxmx ist komfortabel. Ist die Endung *.wxm muss man 
erst noch alle Ausgaben neu erzeugen. Mit Strg r  werden alle aufgeklappten Zellen ausgewertet.
Zum Lernen ist es besser die Zellen einzeln (mit Shift+Enter) auszuwerten.

Werte einzelne Zellen aus mit Shift-Enter. 
Auswertung in einem Rutsch: Falte alle Abschnitte auf,
werte alle Zellen mit Strg r aus ( auch Menu Cell Alle Zellen auswerten).

### Inhalt

1   Schlüsselerzeugung
    1.1 Grundlage n und phi
    1.2 Schlüssel e und geheimes d
    1.3 Antons öffentlicher Schlüssel
2   Hilfsfunktionen   !!!!!!! Aufkappen und auswerten!!!!!
    2.1 Text in Zahl
    2.2 Zahl in Text
3   Anwendungsphase Verschlüsselung
    3.1 Nachricht als Zahl erzeugen
    3.2 Nachricht verschlüsseln
4   Empfang und Entschlüsseln
    4.1 Errechnung der Nachrricht
    4.2 Text der Nachrricht
5   Signatur eines Textes
    5.1 Erzeugung der Signatur
    5.2 Prüfung der Signatur
    5.3 Angriff: Veränderung des Textes
    Merken das Angriffs    

## Schüsselerzeugung

Anton will sich ein Schlüsselpaar für das RSA-Verfahren herstellen

### Grundlage n und phi

n wird grundsätzlich als Produkt aus zwei Primzahlen

p:next_prime(floor(sqrt(random(1.0)*10^120)));
10^60;

q:next_prime(floor(sqrt(random(1.0)*10^120)));
10^60;

n:p*q;  phi:(p-1)*(q-1);

### Schlüssel e und geheimes d

e muss teilerfremd zu phi gewählt werden, damit es in Z*(phi) ein 
Inverses d hat.

/* $ unterdrückt die Ausgabe und # steht für ungleich */
e:2$  while  gcd(e,phi)#1  do e:random(phi)$ e;

d:gcdex(e,phi)[1]; if d<0 then d:d+phi$ d;

mod(e*d,phi);

### Antons öffentliches Schlüsselpaar

e;n;

Dies stellt Anton öffentlich zur Verfügung, z.B. aus seiner
Internetseite.

## Hilfsfunktionen

txToZoo(text):=block([i,li,intli,n,z],
                      li:charlist(text),n:length(li), intli:[],
                      for i:1 thru n do (
                         intli:append(intli,[cint(li[i])])   ), print(intli), 
       intli:intli-28, print(intli),z:0,
                       for i:1 thru n do (z:z*100+intli[i]), return(z)
                      )$

txToZoo("Affe");

zooToTx(z):=block([i,li,zz,tx],
                    intli:[],zz:z,tx:"",
                    for i:1 while zz>=1 do( 
                       intli:append([mod(zz,100)],intli), zz:floor(zz/100)),
                    print(intli), intli:intli+28,  print(intli),
                    for i:1 thru length(intli) do (tx:concat(tx,ascii(intli[i]))),
                    return(tx)
                    )$

m:zooToTx(37747473);

## Anwendungphase, Verschlüsselung

Berta will Anton einen Text senden, den nur Anton lesen kann.
Sie liest im Internet (z.B.) Antons öffentliches Schlüsselpaar (e,n).

### Nachricht als Zahl erzeugen

m:txToZoo("Montag Treffen um 8 im Medley");

/* soll 1 sein */ gcd(m,n);

### Verschlüsseln

Nun potenziert sie m mit e modulo n

c:power_mod(m,e,n);

Berta sendet c an Anton

## Empfang und Verschlüsseln

Anton empfängt c.

### Entschlüsseln der Nachricht

mm:power_mod(c,d,n);

### Zurückverwandeln in Text

zooToTx(mm);

## Digitale Signatur

Anton will einen offen lesbaren Text signieren. Es soll sich 
jeder überzeugen können, dass der Text nicht verändert ist.
Auch bei der Signatur mit RSA wird modulo n potenziert, allerdings erst 
mit d und dann mit c.

### Erzeugung der Signatur

Antond Text:

M:txToZoo("Vertraut Emil nicht");

Signatur

sig:power_mod(M,d,n);

Normalerweise wird die Zahl M erst noch einer "Hash-Funktion" übergeben,
die weniger Datenplatz braucht und es wird h(M) signiert.

### Prüfung der Signatur

Berta will sich überzeugen, dass der auf Antons Site lesbare Text 
von niemandem manipuliert wurde. Sie verwendet dazu das öffenliche
RSA-Schlüsselpaar (e,n). 

MM:power_mod(sig,e,n);

Falls keine Hashfunktion werwendet wurde, kann sie diese Zahl in Text 
umwandeln und lesen. Es muss derselbe Text sein, den sie bei Anton
gelesen hatte. 

zooToTx(MM);

Hat Anton einen Hashwert signiert, nimmt Berta anstelle des  Textes auch 
den Hashwert h(M)  und vergleicht mit MM.
Anton hat in diesem Fall das Hashverfahren angegeben.

### Veränderng des Textes

Mister X macht aus Antons Text etwas anderes

MX:txToZoo("Vertraut Emil");

Wenn er die Signatur so lässt, merkt Berta sofort, dass das ein anderer Text 
ist. Aber die kleinste Veränderung der Signatur  ist auch merkbar:

sigX:sig+1;

Berta nimmt erstmal diese Signatur als richtig an und rechnet

MMX:power_mod(sigX,e,n);

zooToTx(MMX);

Das ergibt nichts Sinnvolles!
Bei Hash-Verwendung würden h(M) und MMX nicht übereinstimmen.