Kryptografische Protokolle

Fiat-Shamir-Protokoll

 aufwärts

Die Sicherheit des eben dar­gestellten Bit-Commitment-Protokolls auf Basis von Graphen beruht darauf, dass es schwierig ist, einen Iso­morphismus zwischen zwei gegebenen isomorphen Graphen zu bestimmen. Nun sind große Graphen wegen der damit verbundenen Datenmengen für praktische Zwecke allerdings nicht gut geeignet.

Das Fiat-Shamir-Protokoll ist ein ganz ent­sprechendes Protokoll, dessen Sicherheit darauf beruht, dass es schwierig ist, Quadrat­wurzeln modulo n zu berechnen, wenn n das Produkt von zwei ver­schiedenen Primzahlen p und q ist.

Bit-Commitment-Protokoll

Es geht wiederum darum, dass sich A auf ein Bit 0 oder 1 festlegt, ohne es zunächst preiszugeben. Erst wenn B sein Bit genannt hat, offenbart A seine Festlegung.

Die Zahl n ist das Produkt von zwei ver­schiedenen Primzahlen p und q; die Zahl s ist eine Quadratzahl1) in &zz;n*, d.h. es gilt s = v2 mod n für ein v Element &zz;n*. Es muss ferner gelten, dass s ≠ 1 ist.

   
         A           B
 Zahlen n und s 
wählt zufällig
   i Element {0, 1}  und
   r Element &zz;n*  mit  r ≠ ±1
  
berechnet   
x = geschweifte Klammer
r2 mod n    falls i = 0
r2s mod n    falls i = 1
  
 Festlegung 
  
  (versucht, die
Festlegung aufzudecken)
   
 
 wählt
   j Element {0, 1}
   
(versucht, die
Festlegung zu fälschen)
 Offenbaren der
Festlegung
 
  
  prüft
 ob x = r2 mod nfolgt i = 0 )
 oder  x = r2s mod n folgt i = 1 )
   

Sicherheit

Wiederum ist zu prüfen, ob B die Festlegung aufdecken kann und ob A täuschen kann. Sicherlich kann B die Festlegung nicht aufdecken, denn es ist für ihn unmöglich, r2 mod n und r2s mod n zu unter­scheiden, denn beides sind Quadrat­zahlen modulo n.

A gelingt es zu täuschen, wenn er statt r eine Zahl t sendet, für die (modulo n gerechnet) gilt t2s = x = r2 bzw. t2 = x = r2s. Dann aber ist r = tWurzels bzw. t = rWurzels. In beiden Fällen kann A, wenn er t kennt, auch Wurzels berechnen. Dieses t zu berechnen ist also mindestens so schwer wie Wurzels, die Quadrat­wurzel modulo n von s, zu berechnen.

Das Protokoll ist also dann sicher, wenn A keine Quadrat­wurzel modulo n von s kennt. Daher sollte B die Zahl s wählen. Für große n ist es für A praktisch undurch­führ­bar, die Wurzel modulo n aus der Zahl s zu ziehen.

Teilnehmer-Authentifizierung

Wenn umgekehrt nur A eine Quadrat­wurzel modulo n von s kennt, kann sich A durch dieses Wissen authentifizieren. Das ent­sprechende Protokoll zur Teilnehmer-Authentifizierung besteht wieder aus n Würfel-Runden, bei denen A jedesmal gewinnt. Durch die Kenntnis von Wurzels kann A jedesmal gewinnen: er deckt seine Festlegung korrekt auf, wenn i = j ist, und er täuscht, wenn i ≠ j ist, indem er t = rWurzels bzw. t = rWurzels -1 sendet.

Zero-Knowledge-Eigenschaft

Teilnehmer A braucht die Zahl Wurzels nicht preiszugeben. Wiederum ist es so, dass ein Dritter C, der den Nachrichten­austausch zwischen A und B abhört, daraus keine Information gewinnt. Dies wird daran deutlich, dass ein Vierter D den Nachrichten­austausch zwischen A und B simulieren könnte, ohne dass C dies merken würde.

Hierzu muss D lediglich in jeder Runde ein zufälliges Bit j und eine zufällige Zahl r wählen, in Abhängigkeit von j entweder x = r2 oder x = r2s berechnen und an B senden, daraufhin das gewählte Bit j an A senden und daraufhin r an B senden. Einem Außen­stehenden C erscheint es so, als ob A sich durch Senden von x auf ein bestimmtes Bit festlegt, als ob daraufhin B ein zufälliges Bit j würfelt, und als ob daraufhin A aufdeckt, dass er sich auf eben dieses j festgelegt hat, indem er die Zahl r offenbart.

Da D keinerlei Information, die C nicht auch hat, in den simulierten Nachrichten­austausch hineinsteckt, kann C auch keine Information aus dem Nachrichten­austausch herausholen. Das Protokoll hat also die Zero-Knowledge-Eigenschaft.


1)  Eine Quadratzahl s = v2 mod n wird auch als quadratischer Rest bezeichnet.

 

Weiter mit:   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 04.12.2003   Updated: 11.06.2016
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik