# Fiat-Shamir-Verfahren

Mathematik in wxMaxima www.mathematik-verstehen.de Haftendorn Jan 2011

### 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 (mit sh klick),
werte alle Zellen mit Strg r aus ( auch Menu Cell Alle Zellen auswerten).

### Inhalt

## Schüsselerzeugung

Anton will Berta davon überzeugen, dass er ein Geheimnis kennt,
ohne dass Berta irgendetwas von dem Geheimnis erfährt.

### Erzeugung von n aus p und g

p und q werden als Primzahlen gewählt.

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

n wird als Produkt gebildet:

n:p*q;

### Geheimnis und öffentliche Schlüssel

s:random(n-2);
10^120;

v:power_mod(s,2,n);

Als kleines Beispiel eignet sich p:11; q:17; s:137
Öffentlich ist v und n:

v; n;

## Anwendungsphase

### Antons Tat

Anton wählt r teilerfremd zu n und berechnet x und sendet x.

n;

r:random(n-2)$
while  gcd(r,n)#1  do r:random(n-2)$ 
x:power_mod(r,2,n);

### Bertas Tat

Berta empfängt x und sendet b=0 oder b=1

makelist(random(2),i,1,200);

b:random(2);

### Anton empfängt und antwortet

Anton empfängt b und sendet y: bei b=0 das y=r, bei b=1 das y=rs modn

if b=0 then y:r else y:mod(r*s,n);

### Berta empfängt y und testet

test:power_mod(y,2,n);

b;

if b=0 then (if test=x then erg:"ok" else erg:"Quaaark")
     else (if  test=mod(x*v,n) then erg:"ok so" else erg:"Quark")$
erg;

## Mehrere Durchläufe

### Automatischer Einmaltest

teste():=block([r,x,b,y,test,erg],r:random(n-2),
              while  gcd(r,n)#1  do r:random(n-2), x:power_mod(r,2,n),
              b:random(2), if b=0 then y:r else y:mod(r*s,n),
              test:power_mod(y,2,n),
              if b=0 then (if test=x then erg:"ok" else erg:"Quaaark")
                 else (if  test=mod(x*v,n) then erg:"JA" else erg:"Quark"),
              return(erg)        )$

[teste(),teste(),teste(),teste(),teste(),teste(),teste(),teste()];

### Automatisch viele Tests

z:10$ sp:15$

Definition von Arrays
Achtung: offenbar kann man Array nicht so einfach neu belegen.
Darum wird hier mit kill() das Array gelöscht, 
damit ein echt neuer Durchlauf kommt.

kill(t)$  t[i,j]:=teste();
tm:genmatrix(t,z,sp);

Alle Einträge mit JA bzw. ok behalten ihre Koordinaten,
die jeweils anderen werden rechts abgelegt.

kill(tmJA)$ tmJA[i,j]:=if tm[i,j]="JA" then [i,j] else [z+1,1];
kill(tmok)$ tmok[i,j]:=if tm[i,j]="ok" then [i,j] else [z+1,2];

tmJA[2,1];

load(draw)$

liJA:[]$ for j from 1 thru sp do liJA:append(liJA,makelist(tmJA[i,j],i,1,z))$ liJA$
liok:[]$ for j from 1 thru sp do liok:append(liok,makelist(tmok[i,j],i,1,z))$ liok$

Es war etwas mühsam, die Punkte passend aufzubereiten.
Eine Matrix aus Punkten wurde nicht akzeptiert. 
Nun ist eine Liste aus Punkten jeweils erzeugt.

pkt:gr2d(color=red, point_size=2,point_type=5, points(liJA),
              color=green, point_size=2,point_type=7, points(liok))$
draw(pkt)$

Dies sind also drei Serien aus 150 Durchläufen.
Die Wahrscheinlichkeit, dass Mister X so oft richtig rät ist:

1/2^150,numer;

also etwa so groß, wie im Weltall ein bestimmtes Atom 
zufällig genau zu treffen.