Kryptografische Protokolle

Fiat-Shamir-Protokoll

 aufwärts

Die Sicherheit des eben dargestellten Bit-Commitment-Protokolls auf Basis von Graphen beruht darauf, dass es schwierig ist, einen Isomorphismus 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 entsprechendes Protokoll, dessen Sicherheit darauf beruht, dass es schwierig ist, Quadratwurzeln modulo n zu berechnen, wenn n das Produkt von zwei verschiedenen 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 verschiedenen 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 unterscheiden, denn beides sind Quadratzahlen 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 Quadratwurzel modulo n von s, zu berechnen.

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

Teilnehmer-Authentifizierung

Wenn umgekehrt nur A eine Quadratwurzel modulo n von s kennt, kann sich A durch dieses Wissen authentifizieren. Das entsprechende Protokoll zur Teilnehmer-Authentifizierung besteht wieder aus n Würfel-Runden, bei denen A jedes Mal gewinnt. Durch die Kenntnis von Wurzels kann A jedes Mal 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 Nachrichtenaustausch zwischen A und B abhört, daraus keine Information gewinnt. Dies wird daran deutlich, dass ein Vierter D den Nachrichtenaustausch 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ßenstehenden 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 Nachrichtenaustausch hineinsteckt, kann C auch keine Information aus dem Nachrichtenaustausch 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   Datenschutz   ©   Created: 04.12.2003   Updated: 08.06.2018
Valid HTML 4.01 Transitional

Hochschule Flensburg
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