Kryptologie 1 001

Vorlesungsskript

Kryptologie 1 Sommersemester 2002

Prof. Dr. Johannes Köbler Humboldt-Universität zu Berlin Lehrstuhl Algorithmen und Komplexität II

26. Juli 2002

Inhaltsverzeichnis

1

2

3

Klassische Verfahren

1

1.1

Einführung

1

1.2

Kryptosysteme

2

1.3

Die affine Chiffre

4

1.4

Die Hill-Chiffre

12

1.5

Die Vigenère-Chiffre und andere Stromsysteme

14

1.6

Der One-Time-Tape

16

1.7

Klassifikation von Kryptosystemen

17

1.8

Realisierung von Blocktranspositionen und einfachen Substitutionen

26

1.9

Klassifikation von Angriffen gegen Kryptosysteme

28

1.10

Kryptoanalyse von Blocktranspositionen

29

1.11

Kryptoanalyse von einfachen Substitutionschiffren

31

1.12

Kryptoanalyse von polygraphischen Chiffren

34

1.13

Kryptoanalyse von polyalphabetischen Chiffren

35

1.14

Informationstheoretische Sicherheitsanalyse

43

Symmetrische Kryptosysteme

54

2.1

Produktchiffren

54

2.2

Substitutions-Permutations-Netzwerke

56

2.3

Lineare Kryptoanalyse von SPNs

59

2.4

Differentielle Kryptoanalyse von SPNs

66

2.5

Der Data Encryption Standard (DES)

72

2.6

Endliche Körper

76

2.7

Der Advanced Encryption Standard (AES)

79

2.8

Betriebsarten von Blockchiffren

84

Zahlentheoretische Grundlagen

88

3.1

88

Diskrete Logarithmen

4

3.2

Modulares Potenzieren

91

3.3

Quadratische Reste

93

3.4

Primzahlen

96

Asymmetrische Kryptosysteme

99

4.1

Das RSA-System

100

4.2

Das Rabin-System

105

1 Klassische Verfahren

1

1 Klassische Verfahren 1.1 Einführung Kryptosysteme (Verschlüsselungsverfahren) dienen der Geheimhaltung von Nachrichten bzw. Daten. Hierzu gibt es auch andere Methoden wie z.B. Physikalische Maßnahmen: Tresor etc. Organisatorische Maßnahmen: einsamer Waldspaziergang etc. Steganographische Maßnahmen: unsichtbare Tinte etc. Andererseits können durch kryptographische Verfahren weitere Schutzziele realisiert werden.


Vertraulichkeit – Geheimhaltung – Anonymität (z.B. Mobiltelefon) – Unbeobachtbarkeit (von Transaktionen)


Integrität – von Nachrichten und Daten


Zurechenbarkeit – Authentikation – Unabstreitbarkeit – Identifizierung


Verfügbarkeit – von Daten – von Rechenressourcen – von Informationsdienstleistungen In das Umfeld der Kryptographie fallen auch die folgenden Begriffe. Kryptographie: Lehre von der Geheimhaltung von Informationen durch die Verschlüsselung von Daten. Im weiteren Sinne: Wissenschaft von der Übermittlung, Speicherung und Verarbeitung von Daten in einer von potentiellen Gegnern bedrohten Umgebung.

2

1 Klassische Verfahren

Kryptoanalysis: Erforschung der Methoden eines unbefugten Angriffs gegen ein Kryptoverfahren (Zweck: Vereitelung der mit seinem Einsatz verfolgten Ziele) Kryptoanalyse: Analyse eines Kryptoverfahrens zum Zweck der Bewertung seiner kryptographischen Stärken bzw. Schwächen. Kryptologie: Wissenschaft vom Entwurf, der Anwendung und der Analyse von kryptographischen Verfahren (umfasst Kryptographie und Kryptoanalyse).

1.2 Kryptosysteme Es ist wichtig, Kryptosysteme von Codesystemen zu unterscheiden.

Codesysteme – operieren auf semantischen Einheiten, – starre Festlegung, welche Zeichenfolge wie zu ersetzen ist. Beispiel 1 (Ausschnitt aus einem Codebuch der deutschen Luftwaffe)

Bis auf weiteres Wettermeldung gemäß Funkbefehl testen Frage Befehl beendet eigene Maschinen

xve yde sLk fin eom

Kryptosysteme – operieren auf syntaktischen Einheiten, – flexibler Mechanismus durch Schlüsselvereinbarung Definition 2

(Alphabet)

Ein Alphabet ist eine geordnete endliche Menge


     

  von Zeichen. Eine Folge 
      
 heißt Wort (der Länge ).



 .




Beispiel 3 Das lateinische Alphabet
 enthält die 26 Buchstaben A,...,Z. Bei der Abfassung von Klartexten wurde meist auf den Gebrauch von Interpunktions- und Leerzeichen sowie auf Groß- und Kleinschreibung verzichtet ( Verringerung der Redundanz im Klartext).




1 Klassische Verfahren

Definition 4

3

(Kryptosystem)

Ein Kryptosystem wird durch folgende Komponenten beschrieben: – – – – – –


, das Klartextalphabet,  , das Kryptotextalphabet,  , der Schlüsselraum (key space ), 
 , der Klartextraum (message space ),

   , der Kryptotextraum (ciphertext space ),      , die Verschlüsselungsfunktion (encryption function ),

–

    , die Entschlüsselungsfunktion (decryption function ) und

–

    , eine Menge von Schlüsselpaaren     mit der Eigenschaft, dass für jeden Klartext   die Beziehung     
 (1) gilt. Bei symmetrischen Kryptosystemen ist
       , weshalb wir auf die Angabe von verzichten können. Angreifer

Klartext


Kryptotext 

Chiffrierfunktion 

Schlüssel 

Klartext


Dechiffrierfunktion 

Schlüssel ¼

Empfänger

Sender

Zu jedem Schlüssel    korrespondiert also eine Chiffrierfunktion         und eine Dechiffrierfunktion      . Die Gesamtheit dieser Abbildungen wird auch Chiffre (englisch cipher ) genannt. (Daneben wird der Begriff „Chiffre“ auch als Bezeichnung für einzelne Kryptotextzeichen oder kleinere Kryptotextsequenzen verwendet.) Lemma 5 Für jedes Paar injektiv.

   



ist die Chiffrierfunktion   



  

4

1 Klassische Verfahren

Beweis: Angenommen, für zwei unterschiedliche Klartexte    . Dann folgt




 ist    


     
      

  im Widerspruch zu .



1.3 Die affine Chiffre Die Moduloarithmetik erlaubt es uns, das Klartextalphabet mit einer Addition und Multiplikation auszustatten. Definition 6

(teilt-Relation, modulare Kongruenz, ganzzahliger Rest)

Seien    ganze Zahlen mit   . Die Zahl  teilt  (kurz: ), falls ein  
existiert mit 
. Teilt  die Differenz  , so schreiben wir hierfür 
 (in Worten:  ist kongruent zu  modulo ). Weiterhin bezeichne

   den bei der Ganzzahldivision von  durch  auftretenden Rest, also diejenige ganze Zahl          , für die eine ganze Zahl  
existiert mit 
 . Die auf
definierten Operationen

 
 
    und

 
 
   sind abgeschlossen auf


        und bilden auf dieser Menge einen kommutativen Ring mit Einselement, den sogenannten Restklassenring modulo . Für  
 schreiben wir auch  
. Definition 7

(Buchstabenrechnung)

Sei


     

  ein Alphabet. Für Indizes         und eine ganze Zahl  
ist

 

 

   

   

   

   

  

 

Wir rechnen also mit Buchstaben, indem wir sie mit ihren Indizes identifizieren und die Rechnung modulo  ausführen. Mit Hilfe dieser Notation lässt sich die Verschiebechiffre, die auch als additive Chiffre bezeichnet wird, leicht beschreiben. Definition 8

(additive Chiffre)

1 Klassische Verfahren

5

Bei der additiven Chiffre ist



ein beliebiges Alphabet mit  

   und 
      . Für    ,   und   gilt   
  und  
  Im Fall des lateinischen Alphabets führt der Schlüssel 
 auf eine interessante Chiffrierfunktion, die in UNIX-Umgebungen auch unter der Bezeichnung ROT13 bekannt ist. Natürlich kann mit dieser Substitution nicht ernsthaft die Vertraulichkeit von Nachrichten geschützt werden. Vielmehr soll durch sie ein unbeabsichtigtes Mitlesen – etwa von Rätsellösungen – verhindert werden. Tabelle 1 Werte der additiven Chiffrierfunktion ROT13 (Schlüssel



).

 ABCDEFGHIJKLMNOPQRSTUVWXYZ    n o p q r s t u v w x y z a b c d e f g h i j k l m

ROT13 ist eine involutorische – also zu sich selbst inverse – Abbildung, d.h. für alle  
gilt ROT13ROT13
 Die Buchstabenrechnung legt folgende Modifikation der Caesar-Chiffre nahe: Anstatt auf jeden Klartextbuchstaben den Schlüsselwert  zu addieren, können wir die Klartextbuchstaben auch mit  multiplizieren. Allerdings erhalten wir hierbei nicht für jeden Wert von  eine injektive Chiffrierfunktion. So bildet etwa die Funktion  
 
 mit 
 sowohl A als auch N auf den Buchstaben A
N
a ab. Um die vom Schlüsselwert  zu erfüllende Bedingung angeben zu können, führen wir folgende Begriffe ein. Definition 9

(ggT, kgV, teilerfremd)

Seien   
. Für  
   ist

 
 
  teilt die beiden Zahlen  und  der größte gemeinsame Teiler von  und . Für 
 
ist   
 
    und die beiden Zahlen  und  teilen  das kleinste gemeinsame Vielfache von  und . Ist

 
, so nennt man  und  teilerfremd. Euklidscher Algorithmus: Der größte gemeinsame Teiler zweier Zahlen lässt sich wie folgt bestimmen.

 und 

O. B. d. A. sei     . Bestimme die natürlichen Zahlen (durch Divsision mit Rest):



  

          


und

         

6

1 Klassische Verfahren

mit



   

für


      

Hierzu sind   Divisionsschritte erforderlich. Wegen


   


  
     


folgt

 
 . Beispiel 10 Für 
 und 
 erhalten wir z. B.

 

    
      
      
    

 und damit

 

. Algorithmus 11 E UKLID

 (iterativ)

Algorithmus 12 E UKLID

 (rekursiv)

1 repeat      1 if 
then 2 return  2  3  3 else 4 return E UKLID    4 until 
5 return  5 end Zur Abschätzung von  verwenden wir die Folge der Fibonacci-Zahlen   :

   
  
 
 

falls 
falls 
 falls  

Durch Induktion über  (mit    ) folgt    
 ; also    . Wegen    (wobei 
  ; Beweis durch Induktion) ist dann     , d. h.    . Satz 13 Der Euklidsche Algorithmus führt zur Berechnung von

  (unter der Annahme     ) höchstens    Divisionsschritte durch. Dies führt auf eine Zeitkomplexität von   , wobei  die Länge der Eingabe in Binärdarstellung bezeichnet.
Also:






  und 

  .

1 Klassische Verfahren

7

Erweiterter Euklidscher bzw. Berlekamp-Algorithmus: Der Euklidsche Algorithmus kann so modifiziert werden, dass er eine lineare Darstellung

 
      mit   
des

 liefert (Zeitkomplexität ebenfalls   ). Hierzu werden neben   und  (für     ) weitere Zahlen 

   
  wobei 

 und 

 und



   
  wobei 

und 

 bestimmt. Dann gilt für 
 und 
,      
  und durch Induktion über ,      
  
       
    
  
   
         

    
 zeigt man, dass dies auch für 
       gilt. Korollar 14 (Lemma von Bezout) Der größte gemeinsame Teiler von der Form

 
      mit   


 und  ist in

darstellbar. Beispiel 15 Für 
 und 
 erhalten wir z. B. mit

 

   

  

     

  
      

    
             
      

           

 die lineare Darstellung      
. 









      

Aus der linearen Darstellbarkeit des größten gemeinsamen Teilers ergeben sich eine Reihe von nützlichen Schlussfolgerungen. Korollar 16 Der größte gemeinsame Teiler von  und  wird von allen gemeinsamen Teilern von  und  geteilt.











 

8

1 Klassische Verfahren

Korollar 17 (Lemma von Euklid) Teilt  das Produkt    und gilt

 
, so folgt daraus, dass  auch Teiler von  ist.

  



 






Beweis: Wegen

 
 existieren Zahlen   
mit      
. Da  nach Voraussetzung das Produkt    teilt, muss  auch          
 teilen.  Korollar 18 Wenn sowohl  als auch  zu einer Zahl auch das Produkt    teilerfremd zu .

 


 




 
teilerfremd sind, so ist

   


Beweis: Wegen

 


 
 existieren Zahlen       
mit

     
     
 Mit       
        
           ergibt  sich

   
. Damit nun eine Abbildung  

von der Bauart  
 injektiv (oder gleichbedeutend: surjektiv) ist, muss es zu jedem Buchstaben  
genau einen Buchstaben  
mit 
 geben. Wie der folgende Satz zeigt, ist dies genau dann der Fall, wenn  und  teilerfremd sind. Satz 19 Sei   . Die lineare Kongruenzgleichung 
 besitzt genau dann eine eindeutige Lösung          , wenn

 
 ist. Beweis: Angenommen,

 
  . Dann ist mit  auch  
   eine Lösung von 
 mit 


 . Gilt umgekehrt

 
, so folgt aus den Kongruenzen 
 und


 sofort    und   , also   . Wegen

 
 folgt mit dem Lemma von Euklid    , also 
 . Dies zeigt, dass die Abbildung  



mit  
   injektiv ist. Da jedoch Definitions- und  Wertebereich von  identisch sind, muss  dann auch surjektiv sein. Korollar 20 Im Fall

 
 hat die Kongruenz 
 genau eine Lösung, die das multiplikative Inverse von  modulo  genannt und mit 
   (oder einfach mit 
 ) bezeichnet wird. Die invertierbaren Elemente von

werden in der Menge


 



 
 zusammengefasst.

1 Klassische Verfahren

9

Korollar 18 zeigt, dass

unter der Operation 
abgeschlossen ist, und mit Korollar 20 folgt, dass 

 
 eine multiplikative Gruppe bildet.

Das multiplikative Inverse von  modulo  ergibt sich aus der linearen Darstellung  


 
 zu 

  . Bei Kenntnis von 
 kann die Kongruenz 
 leicht zu 

 gelöst werden. Die folgende Tabelle zeigt die multiplikativen Inversen 
 für alle  
 .

             
             Nun lässt sich die additive Chiffre leicht zur affinen Chiffre erweitern. Definition 21

(affine Chiffre)

Bei der affinen Chiffre ist



ein beliebiges Alphabet mit  

   und 




. Für 
    ,   und   gilt

  
 

und

 

  

In diesem Fall liefert die Schlüsselkomponente 
 für jeden Wert von  eine involutorische Chiffrierfunktion      
  (verschobenes komplementäres Alphabet). Wählen wir für  ebenfalls den Wert , so ergibt sich die Chiffrierfunktion !
 , die auch als revertiertes Alphabet bekannt ist:

 !
 

ABCDEFGHIJKLMNOPQRSTUVWXYZ zyxwvutsrqponmlkjihgfedcba

Wie man sieht, handelt es sich hierbei um eine echt involutorische Abbildung, d.h. kein Buchstabe wird auf sich selbst abgebildet (vorausgesetzt  ist gerade). Als nächstes illustrieren wir die Ver- und Entschlüsselung mit der affinen Chiffre an einem kleinen Beispiel. Beispiel 22 (affine Chiffre) Sei

A     Z
 , also 
. Weiter sei 
 , also  Um den Klartextbuchstaben 
F zu verschlüsseln, berechnen wir


 und 
.

  
 
F
v da der Index von F gleich , der von v gleich  und   
   ist. Um einen Kryptotextbuchstaben wieder entschlüsseln zu können, benötigen wir das multiplikative Inverse von 
, das sich wegen

 

   










 

    





                

  





   










    

10

1 Klassische Verfahren

zu 


 ergibt. Damit erhalten wir für den Kryptotextbuchstaben  ursprünglichen Klartextbuchstaben


v den

 

  
v 
F zurück, da   
   ist. Eine wichtige Rolle spielt die Funktion

"



      

 
 die sogenannte Eulersche "-Funktion. " 



"

mit











 











                

                

Wegen




       
 

folgt sofort

" 
 


   Um hieraus für beliebige Zahlen    eine Formel für " zu erhalten, genügt es, "   im Fall

 
 in Abhängigkeit von " und " zu bestimmen. Hierzu betrachten wir die Abbildung  
 
 
mit   
      Beispiel 23 Sei 
 und 
. Dann erhalten wir die Funktion  mit


 
 


 
              

      
       
   
          
   
       
     
 
       
  Die unterstrichenen Werte gehören zu
,
 bzw.
 . Man beachte, dass ein -Wert genau dann in
 ist, wenn beide Komponenten von   zu
 bzw.
 gehören. # Der Chinesische Restsatz, den wir im nächsten Abschnitt beweisen, besagt, dass  im Fall

 
 bijektiv und damit invertierbar ist.


 

 

   

 

   

   

   

  

1 Klassische Verfahren

11

Wegen

 


 


 


   


   
 ist daher die Einschränkung von  auf den Bereich
 eine Bijektion zwischen
 und
 
 , d.h. es gilt "

 

 
 

  
 
""  

Satz 24 Die Eulersche "-Funktion ist multiplikativ, d. h. für teilerfremde Zahlen  und  gilt "
"". Korollar 25 Sei 


   die Primfaktorzerlegung von . Dann gilt   "




  
  



Beweis: Es gilt

"     
 "   
      
 
   
   

Der Chinesische Restsatz Die beiden linearen Kongruenzen

 







besitzen je eine Lösung, es gibt aber kein , das beide Kongruenzen gleichzeitig erfüllt. Der nächste Satz zeigt, dass unter bestimmten Voraussetzungen gemeinsame Lösungen existieren, und wie sie berechnet werden können. Satz 26 (Chinesischer Restsatz) Falls   , . . . , hat das System




 .. .




  genau eine Lösung modulo 
  .

 paarweise teilerfremd sind, dann

 

(2)

12

1 Klassische Verfahren

Beweis: Da die Zahlen  mit




 teilerfremd zu  sind, existieren Zahlen  und 

   


   


Dann gilt

 
 

und

 


 für 
. Folglich erfüllt 
       die Kongruenzen


   
  für 
      . Dies zeigt, dass   lösbar, also die Funktion  



     

 mit  
            surjektiv ist. Da der Definitions- und der Wertebereich von  die gleiche Mächtigkeit haben, muss  jedoch auch injektiv sein, d.h.   ist sogar eindeutig lösbar.  Man beachte, dass der Beweis des Chinesischen Restsatzes konstruktiv ist und die Lösung  unter Verwendung des erweiterten Euklidschen Algorithmus’ effizient berechenbar ist.

1.4 Die Hill-Chiffre Die von Hill im Jahr 1929 publizierte Chiffre ist eine Erweiterung der multiplikativen Chiffre auf Buchstabenblöcke, d.h. der Klartext wird nicht zeichenweise, sondern blockweise verarbeitet. Sowohl der Klartext- als auch der Kryptotextraum enthält alle Wörter  über
einer festen Länge $. Zur Chiffrierung wird eine $  $-Matrix 
  mit Koeffizienten in

benutzt, die einen Klartextblock 
      
 in den Kryptotextblock       
 transformiert, wobei


        
     $

ist (hierbei machen wir von der Buchstabenrechnung Gebrauch).  entsteht also durch Multiplikation von  mit der Schlüsselmatrix  :

       

 . . . . . .         . . . 
       

     Wir bezeichnen die Menge aller $  $-Matrizen mit Koeffizienten in

mit

. Als Schlüssel können nur invertierbare Matrizen  benutzt werden, da sonst der Chiffriervorgang nicht injektiv ist.  ist genau dann invertierbar, wenn die Determinante von  teilerfremd zu  ist (siehe Übungen). Definition 27

(Determinante)

1 Klassische Verfahren

13

Sei

  eine $  $-Matrix. Für      $ sei
 die durch Streichen der -ten Zeile und  -ten Spalte aus  hervorgehende Matrix. Die Determinante von
ist dann 

  , falls $
, und



wobei      

  

   
 

 $ (beliebig wählbar) ist.

Für die Dechiffrierung wird die zu  inverse Matrix 
 benötigt, wofür effiziente Algorithmen bekannt sind (siehe Übungen). Satz 28 Sei


ein Alphabet und sei  

 ($  , 

). Die Abbildung  
 
 mit  
 ist genau dann injektiv, wenn

  
 ist. 

Beweis: Siehe Übungen. Definition 29 (Hill-Chiffre) Sei


     

  ein beliebiges Alphabet und für eine natürliche Zahl $  sei


 . Bei der Hill-Chiffre ist 
 

 

 
 und es gilt

  


und

 



Beispiel 30 (Hill-Chiffre) Benutzen wir zur Chiffrierung von Klartextblöcken der Länge $
 über dem lateinischen Alphabet
 die Schlüsselmatrix

    

     
         

so erhalten wir beispielsweise für den Klartext HILL wegen

    

     H I L L       
n e r x   

bzw.

 H  I  L  L
n  H  I  L  L
e  H  I  L L
r  H  I  L  L
x den Kryptotext   HILL
nerx.

14

1 Klassische Verfahren

1.5 Die Vigenère-Chiffre und andere Stromsysteme Bei der nach dem Franzosen Blaise de Vigenère (1523–1596) benannten Chiffre werden zwar nur einzelne Buchstaben chiffriert, aber je nach Position im Klartext unterschiedlich. Definition 31

(Vigenère-Chiffre)

Sei

 ein beliebiges Alphabet. Die Vigenère-Chiffre chiffriert unter einem Schlüssel 

   
  

 einen Klartext 

   
 beliebiger Länge zu

  

   
 

wobei

und dechiffriert einen Kryptotext 

 

   
 


   

ist,



   
 zu

wobei


   

ist.

Beispiel 32 (Vigenère-Chiffre) Verwenden wir das lateinische Alphabet
 als Klartextalpabet und wählen wir als Schlüssel das Wort 
WIE, so ergibt sich für den Klartext VIGENERE beispielsweise der Kryptotext

 WIE VIGENERE
V 

W I 

I G 

E E 

W N 

I E 

E R 

W E 

I r q a v n m k i
rqkavinm Um einen Klartext  zu verschlüsseln, wird also das Schlüsselwort 

   
 so oft wiederholt, bis der dabei entstehende Schlüsselstrom 

       
  
   die Länge von  erreicht. Dann werden  und  zeichenweise addiert, um den zugehörigen Kryptotext  zu bilden. Aus diesem kann der ursprüngliche Klartext  zurückgewonnen werden, indem man den Schlüsselstrom  wieder subtrahiert. Beispiel 32 (Vigenère-Chiffre, Fortsetzung) Chiffrierung: VIGENERE

WIEWIEWI rqkavinm

Klartext  Schlüsselstrom  Kryptotext 
 

Dechiffrierung: rqkavinm WIEWIEWI VIGENERE

Kryptotext  Schlüsselstrom  Klartext 
 

Die Chiffrierarbeit lässt sich durch Benutzung einer Additionstabelle erleichtern (auch als Vigenère-Tableau bekannt).

1 Klassische Verfahren

15

+ A B C D E F G H I J K L M N O P Q R S T U VWX Y Z A A B C D E F G H I J K L M N O P Q R S T U VWX Y Z B B C D E F G H I J K L MN O P Q R S T U VWX Y Z A C C D E F G H I J K L MN O P Q R S T U VWX Y Z A B D D E F G H I J K L MN O P Q R S T U VWX Y Z A B C E E F G H I J K L M N O P Q R S T U VWX Y Z A B C D F F G H I J K L M N O P Q R S T U VWX Y Z A B C D E G G H I J K L MN O P Q R S T U VWX Y Z A B C D E F H H I J K L MN O P Q R S T U VWX Y Z A B C D E F G I I J K L M N O P Q R S T U VWX Y Z A B C D E F G H J J K L M N O P Q R S T U VWX Y Z A B C D E F G H I K K L MN O P Q R S T U VWX Y Z A B C D E F G H I J L L MN O P Q R S T U VWX Y Z A B C D E F G H I J K M MN O P Q R S T U VWX Y Z A B C D E F G H I J K L N N O P Q R S T U VWX Y Z A B C D E F G H I J K L M O O P Q R S T U VWX Y Z A B C D E F G H I J K L MN P P Q R S T U VWX Y Z A B C D E F G H I J K L MN O Q Q R S T U VWX Y Z A B C D E F G H I J K L M N O P R R S T U VWX Y Z A B C D E F G H I J K L M N O P Q S S T U VWX Y Z A B C D E F G H I J K L MN O P Q R T T U VWX Y Z A B C D E F G H I J K L MN O P Q R S U U VWX Y Z A B C D E F G H I J K L M N O P Q R S T V VWX Y Z A B C D E F G H I J K L M N O P Q R S T U W WX Y Z A B C D E F G H I J K L MN O P Q R S T U V X X Y Z A B C D E F G H I J K L MN O P Q R S T U VW Y Y Z A B C D E F G H I J K L MN O P Q R S T U VWX Z Z A B C D E F G H I J K L M N O P Q R S T U VWX Y

Um eine involutorische Chiffre zu erhalten, schlug Sir Francis Beaufort, ein Admiral der britischen Marine, vor, den Schlüsselstrom nicht auf den Klartext zu addieren, sondern letzteren von ersterem zu subtrahieren. Beispiel 33 (Beaufort-Chiffre) Verschlüsseln wir den Klartext BEAUFORT beispielsweise unter dem Schlüsselwort 
WIE, so erhalten wir den Kryptotext xmeqnsnb. Eine erneute Verschlüsselung liefert wieder den Klartext BEAUFORT: Chiffrierung:

WIEWIEWI BEAUFORT xmeqnsnb

Schlüsselstrom  Klartext  Kryptotext 
 

Dechiffrierung:

WIEWIEWI xmeqnsnb BEAUFORT

Schlüsselstrom  Kryptotext  Klartext 
 

Bei den bisher betrachteten Chiffren wird aus einem Schlüsselwort 

   
 ein periodischer Schlüsselstrom 

   
 erzeugt, das heißt, es gilt 
 für alle 
       . Da eine kleine Periode das Brechen der Chiffre erleichtert, sollte entweder ein Schlüsselstrom mit sehr großer Periode oder noch besser ein fortlaufender Schlüsselstrom zur Chiffrierung benutzt werden. Ein solcher nichtperiodischer Schlüsselstrom lässt sich beispielsweise ohne großen Aufwand erzeugen, indem man an das Schlüsselwort den Klartext oder den Kryptotext anhängt (sogenannte Autokey -Chiffrierung).   Die Idee, den Schlüsselstrom durch Anhängen des Klartextes an ein Schlüsselwort zu bilden, stammt von Vigenère, während er mit der Erfindung der nach ihm benannten Vigenère-Chiffre „nichts zu tun“ hatte. Diese wird vielmehr Giovan Batista Belaso (1553) zugeschrieben.

16

1 Klassische Verfahren

Beispiel 34 (Autokey -Chiffre) Benutzen wir wieder das Schlüsselwort WIE, um den Schlüsselstrom durch Anhängen des Klar- bzw. Kryptotextes zu erzeugen, so erhalten wir für den Klartext VIGENERE folgende Kryptotexte: Klartext-Schlüsselstrom: VIGENERE Klartext 

WIEVIGEN Schlüsselstrom rqkzvkvr Kryptotext 

Kryptotext-Schlüsselstrom: VIGENERE Klartext 

WIERQKVD Schlüsselstrom rqkvdomh Kryptotext 

Auch die Dechiffrierung ist in beiden Fällen einfach. Bei der ersten Alternative kann der Empfänger durch Subtraktion des Schlüsselworts den Anfang des Klartextes bilden und gleichzeitig den Schlüsselstrom verlängern, so dass sich auf diese Weise Stück für Stück der gesamte Kryptotext entschlüsseln lässt. Noch einfacher gestaltet sich die Dechiffrierung im zweiten Fall, da sich hier der Schlüsselstrom vom Kryptotext nur durch das vorangestelle Schlüsselwort unterscheidet.

1.6 Der One-Time-Tape Es besteht auch die Möglichkeit, eine Textstelle in einem Buch als Schlüssel zu vereinbaren und den dort beginnenden Text als Schlüsselstrom zu benutzen (Lauftextverschlüsselung). Besser ist es jedoch, aus einem relativ kurzen Schlüssel einen möglichst zufällig erscheinenden Schlüsselstrom zu erzeugen. Hierzu können beispielsweise Pseudozufallsgeneratoren eingesetzt werden. Absolute Sicherheit wird dagegen erreicht, wenn der Schlüsselstrom rein zufällig erzeugt und nach einmaliger Benutzung wieder vernichtet wird. Ein solcher „Wegwerfschlüssel“ (One-Time-Pad oder OneTime-Tape , im Deutschen auch als individueller Schlüssel bezeichnet) lässt sich allerdings nur mit großem Aufwand generieren und verteilen, weshalb diese Chiffre nur wenig praktikabel ist. Dennoch wurde diese Methode beispielsweise beim „heißen Draht“, der 1963 eingerichteten, direkten Fernschreibverbindung zwischen dem Weißen Haus in Washington und dem Kreml in Moskau, angewandt. Beispiel 35 (One-Time-Pad ) Sei


     

  ein beliebiges Klartextalphabet. Um einen Klartext 

   
 zu verschlüsseln, wird auf jeden Klartextbuchstaben  ein neuer, zufällig generierter Schlüsselbuchstabe   addiert,



   
  wobei 
   Der Klartext wird also wie bei einer additiven Chiffre verschlüsselt, nur dass der Schlüssel nach einmaligem Gebrauch gewechselt wird. Dies entspricht dem Gebrauch einer Vigenère-Chiffre, falls als Schlüssel ein zufällig gewähltes Wort von der Länge des  Diese Art der Schlüsselerzeugung schlug der amerikanische Major Joseph O. Mauborgne im Jahr 1918 vor, nachdem ihm ein von Gilbert S. Vernam für den Fernschreibverkehr entwickeltes Chiffriersystem vorgestellt wurde.

1 Klassische Verfahren

17

Klartextes benutzt wird. Wie diese ist der One-Time-Pad im Binärfall also involutorisch. Klartext

   



Kryptotext

   

Schlüssel



Klartext

   

Schlüssel

   

   

1.7 Klassifikation von Kryptosystemen Die bisher betrachteten Chiffrierfunktionen handelt es sich um Substitutionen, d.h. sie erzeugen den Kryptotext aus dem Klartext, indem sie Klartextzeichen – einzeln oder in Gruppen – durch Kryptotextzeichen ersetzen. Dagegen verändern Transpositionen lediglich die Reihenfolge der einzelnen Klartextzeichen. Beispiel 36 (Skytale-Chiffre) Die älteste bekannte Verschlüsselungstechnik stammt aus der Antike und wurde im 5. Jahrhundert v. Chr. von den Spartanern entwickelt: Der Sender wickelt einen Papierstreifen spiralförmig um einen Holzstab (die sogenannte Skytale) und beschreibt ihn in Längsrichtung mit der Geheimbotschaft.

Ü G I

B E R A U S E H E I M N S V O L L ...




ÜBERAUS GEHEIMNISVOLL ... ügi    bes    ehv    reo    ail    uml    sn   

Besitzt der Empfänger eines auf diese Weise beschrifteten Papierstreifens einen Stab mit dem gleichen Umfang, so kann er ihn auf dieselbe Art wieder entziffern. Als Schlüssel fungiert hier also der Stabumfang bzw. die Anzahl  der Zeilen, mit denen der Stab beschrieben wird. Findet der gesamte Klartext  auf der Skytale Platz und beträgt seine Länge ein Vielfaches von  , so geht  bei der Chiffrierung in den Kryptotext

      

 
 
    

  
 
    

    


   


18

1 Klassische Verfahren

über. Dasselbe Resultat stellt sich ein, wenn wir  zeilenweise in eine   -Matrix schreiben und spaltenweise wieder auslesen (sogenannte Spaltentransposition):

 
 
 .. .

 
 


.. .

   .. .






.. .



 

    
Ist die Klartextlänge kein Vielfaches von  , so kann der Klartext durch das Ein- bzw. Anfügen von sogenannten Blendern (Füllzeichen) verlängert werden. Damit der Empfänger diese Füllzeichen nach der Entschlüsselung wieder entfernen kann, ist lediglich darauf zu achten, dass sie im Klartext leicht als solche erkennbar sind.

Von der Methode, die letzte Zeile nur zum Teil zu füllen, ist dagegen abzuraten. In diesem Fall würden nämlich auf dem abgewickelten Papierstreifen Lücken entstehen, aus deren Anordnung man Schlüsse auf den benutzten Schlüssel  ziehen könnte. Andererseits ist nichts dagegen einzuwenden, dass der Sender die letzte Spalte der Skytale nur zum Teil beschriftet. Bevor wir weitere Beispiele für Transpositionen betrachten, wenden wir uns der Klassifikation von Substitutionschiffren zu. Ein wichtiges Unterscheidungsmerkmal ist z.B. die Länge der Klartexteinheiten, auf denen die Chiffre operiert. Monographische Substitutionen ersetzen Einzelbuchstaben. Polygraphische Substitutionen ersetzen dagegen aus mehreren Zeichen bestehende Klartextsegmente auf einmal. Eine polygraphische Substitution, die auf Buchstabenpaaren operiert, wird digraphisch genannt. Das älteste bekannte polygraphische Chiffrierverfahren wurde von Giovanni Porta im Jahr 1563 veröffentlicht. Dabei werden je zwei aufeinanderfolgende Klartextbuchstaben durch ein einzelnes Kryptotextzeichen ersetzt. Beispiel 37 Bei der Porta-Chiffre werden 400 (!) unterschiedliche von Porta für diesen Zweck entworfene Kryptotextzeichen verwendet. Diese sind in einer  -Matrix
  angeordnet, deren Zeilen und Spalten mit den Klartextbuchstaben A     I L     T V Z indiziert sind. Zur Ersetzung des Buchstabenpaars    wird das in Zeile  und Spalte  befindliche Kryptotextzeichen

     


benutzt. Eine Substitution heißt monopartit, falls sie die Klartextsegmente durch Einzelzeichen ersetzt, sonst multipartit. Wird der Kryptotext aus Buchstabenpaaren zusammengesetzt, so spricht man von einer bipartiten Substitution. Ein frühes (monographisches) Beispiel einer bipartiten Chiffriermethode geht auf Polybios (circa 200 – 120 v. Chr.) zurück:

1 Klassische Verfahren

19

 0 1 2 3 4 0 1 2 3 4

A F K P U

B G L Q V

C H M R W

D I N S XY

E J O T Z

POLYBIOS




30 24 21 43 01 13 24 33

Bei der Polybios-Chiffre dient eine   -Matrix, die aus sämtlichen Klartextbuchstaben gebildet wird, als Schlüssel. Die Verschlüsselung des Klartextes erfolgt buchstabenweise, indem man einen in Zeile  und Spalte  eingetragenen Klartextbuchstaben durch das Koordinatenpaar  ersetzt. Der Kryptotextraum besteht also aus den Ziffernpaaren 00 01     44. Die Frage, ob bei der Ersetzung der einzelnen Segmente des Klartextes eine einheitliche Strategie verfolgt wird oder ob diese von Segment zu Segment verändert wird, führt uns auf ein weiteres wichtiges Unterscheidungsmerkmal bei Substitutionen. Monoalphabetische Substitutionen ersetzen die einzelnen Klartextsegment unabhängig von ihrer Position im Klartext. Polyalphabetische Substitutionen verwenden dagegen eine variable Ersetzungsregel, auf die sich auch die bereits verarbeiteten Klartextsegmente auswirken. Die Bezeichnung „monoalphabetisch“ bringt zum Ausdruck, dass der Ersetzungsmechanismus auf einem einzelnen Alphabet beruht (sofern wir das Klartextalphabet als bekannt voraussetzen). Die von Caesar benutzte Chiffriermethode kann beispielsweise vollständig durch Angabe des Ersetzungsalphabets

d,e,f,g,w,...,y,z,a,b,c beschrieben werden. Auch im Fall, dass nicht einzelne Zeichen, sondern ganze Buchstabengruppen auf einmal ersetzt werden, genügt im Prinzip ein einzelnes Alphabet zur Beschreibung. Hierzu sortiert man die Klartexteinheiten, auf denen der Ersetzungsmechanismus operiert, und bildet die Folge (sprich: das Alphabet) der zugeordneten Kryptotextsegmente. Monoalphabetische Chiffrierverfahren ersetzen meist Texteinheiten einer festen Länge $   durch Kryptotextsegmente derselben Länge. Definition 38

(Blockchiffre)

Sei
ein beliebiges Alphabet und es gelte


 , $  . Eine Blockchiffre realisiert für jeden Schlüssel    eine bijektive Abbildung  auf
 und es gilt

  
 und  

  und   . Im Fall $
 spricht man auch von einer

für alle   einfachen Substitutionschiffre.

 Da nur 25 Plätze zur Verfügung stehen, muss bei Benutzung des lateinischen Alphabets entweder ein Buchstabe weggelassen oder ein Platz mit zwei Buchstaben besetzt werden.

20

1 Klassische Verfahren

Polyalphabetische Substitutionen greifen im Wechsel auf verschiedene Ersetzungsalphabete zurück, so dass unterschiedliche Vorkommen eines Zeichens (oder einer Zeichenkette) auch auf unterschiedliche Art ersetzt werden können. Welches Ersetzungsalphabet wann an der Reihe ist, wird dabei in Abhängigkeit von der Länge oder der Gestalt des bereits verarbeiteten Klartextes bestimmt. Fast alle polyalphabetischen Chiffrierverfahren operieren – genau wie monoalphabetische Substitutionen – auf Klartextblöcken einer festen Länge $, die sie in Kryptotextblöcke einer festen Länge $  überführen, wobei meist $
$  ist. Da diese Blöcke jedoch vergleichsweise kurz sind, kann der Klartext der Chiffrierfunktion ungepuffert zugeführt werden. Man nennt die einzelnen Klartextblöcke in diesem Zusammenhang auch nicht ‚Blöcke‘ sondern ‚Zeichen‘ und spricht von sequentiellen Chiffren oder von Stromchiffren. Definition 39

(Stromchiffre)

Sei
ein beliebiges Alphabet und sei


 für eine natürliche  Schlüsselräume. Eine Stromchiffre Zahl $  . Weiterhin seien  und     und einen wird durch eine Verschlüsselungsfunktion     beschrieben. Der Generator Schlüsselstromgenerator    
    erzeugt aus einem externen Schlüssel    für einen Klartext 

   
 ,   , eine Folge 
     
 von internen Schlüsseln 
 
   
    , unter denen  in den Kryptotext

  
 
 
     
  
  überführt wird. Der interne Schlüsselraum kann also wie bei der Blockchiffre eine maximale Größe von   annehmen (im häufigen Spezialfall $
 also  ). Die Aufgabe des Schlüsselstromgenerators  besteht darin, aus dem externen Schlüssel  und dem bereits verarbeiteten Klartext 
   
 den aktuellen internen Schlüssel  zu berechnen. Die bisher betrachteten Stromchiffren benutzen z.B. die folgenden Schlüsselstromgeneratoren. Stromchiffre Vigenère Beaufort

Autokey a Autokey b

a mit b mit

Chiffrierfunktionen

Schlüsselstromgenerator

  
   

   
  
   
 
 
   
   

   
  
   
 
 
    %       
   

   
  
   
 

    



   % 
   
 

       
   

   
   
    
 

Klartext-Schlüsselstrom Kryptotext-Schlüsselstrom

1 Klassische Verfahren

21

Bei der Vigenère- und Beaufortchiffre hängt der Schlüsselstrom nicht vom Klartext, sondern nur vom externen Schlüssel  ab, d.h. sie sind synchron. Die Autokey -Chiffren sind dagegen asynchron (und aperiodisch).

Gespreizte Substitutionen Bei den bisher betrachteten Substitutionen haben die einzelnen Blöcke, aus denen der Kryptotext zusammengesetzt wird, eine einheitliche Länge. Es liegt nahe, einem Gegner die unbefugte Rekonstruktion des Klartextes dadurch zu erschweren, dass man Blöcke unterschiedlicher Länge verwendet. Man spricht hierbei auch von einer Spreizung (straddling ) des Kryptotextalphabets. Ein bekanntes Beispiel für diese Technik ist die sogenannte Spionage-Chiffre, die vorzugsweise von der ehemaligen sowjetischen Geheimpolizei NKWD (Naródny Komissariàt Wnutrennich Del ; zu deutsch: Volkskommissariat des Innern) benutzt wurde. Beispiel 40 Bei der Spionage-Chiffre wird in die erste Zeile einer    -Matrix ein Schlüsselwort & geschrieben, welches keinen Buchstaben mehrfach enthält und eine Länge von 6 bis 8 Zeichen hat (also zum Beispiel SPIONAGE). Danach werden die anderen beiden Zeilen der Matrix mit den restlichen Klartextbuchstaben (etwa in alphabetischer Reihenfolge) gefüllt. 4 S 8 B 5 R

1 P C T

960 ION DFH UVW

32 AG JK XY

758 E LMQ Z




GESPREIZT 2 7 4 1 54 7 9 57 51

Man überzeugt sich leicht davon, dass sich die von der Spionage-Chiffre generierten Kryptotexte wieder eindeutig dechiffrieren lassen, da die Kryptotextsegmente 1, 2,...,8, 01, 02,...,08, 91, 92,...,98, die für die Klartextbuchstaben eingesetzt werden, die Fano-Bedingung erfüllen: Keines von ihnen bildet den Anfang eines anderen. Da die Nummern 5 und 8 der beiden letzten Spalten der Matrix auch als Zeilennummern verwendet werden, liefert dies auch eine Erklärung dafür, warum keine Schlüsselwortbuchstaben in die beiden letzten Spalten eingetragen werden dürfen.

Verwendung von Blendern und Homophonen Die Verwendung von gespreizten Chiffren zielt offenbar darauf ab, die „Fuge“ zwischen den einzelnen Kryptotextsegmenten, die von unterschiedlichen Klartextbuchstaben herrühren, zu verdecken, um dem Gegner eine unbefugte Dechiffrierung zu erschweren. Dennoch bietet die Spionage-Chiffre noch genügend Angriffsfläche, da im Klartext häufig vorkommende Wortmuster auch im Kryptotext zu Textwiederholungen führen.

22

1 Klassische Verfahren

Eine Möglichkeit, diese Muster aufzubrechen, besteht darin, Blender in den Klartext einzustreuen. Abgesehen davon, dass das Entfernen der Blender auch für den rechtmäßigen Empfänger mit Mühe verbunden ist, muss für den Zugewinn an Sicherheit auch mit einer Expansion des Kryptotextes bezahlt werden. Ist man bereit, dies in Kauf zu nehmen, so gibt es auch noch eine wirksamere Methode, die Übertragung struktureller und statistischer Klartextmerkmale auf den Kryptotext abzumildern. Die Idee dabei ist, zur Chiffrierung der einzelnen Klartextzeichen  nicht nur jeweils eines, sondern eine Menge '  von Chiffrezeichen vorzusehen, und daraus für jedes Vorkommen von  im Klartext eines auszuwählen (am besten zufällig). Da alle Zeichen in '  für dasselbe Klartextzeichen stehen, werden sie auch Homophone genannt. Definition 41

(homophonen Substitutionschiffre)

Sei
ein Klartextalphabet und sei

. Weiter sei ein Kryptotextraum der Größe    

. In einer (einfachen) homophonen Substitutionschiffre beschreibt jeder Schlüssel    eine Zerlegung von

in  disjunkte Mengen ' ,  
. Um ein Zeichen  
unter  zu chiffrieren, wird nach einer bestimmten Methode ein Homophon  aus der Menge '  gewählt und für  eingesetzt.

Durch den Einsatz einer homophonen Substitution wird also erreicht, dass verschiedene Vorkommen eines Klartextzeichens auch auf unterschiedliche Weise ersetzt werden können. Damit der Empfänger den Kryptotext auch wieder eindeutig dechiffrieren kann, dürfen sich die Homophonmengen zweier verschiedener Klartextzeichen aber nicht überlappen. Daher kann es nicht vorkommen, dass zwei verschiedene Klartextbuchstaben durch dasselbe Geheimtextzeichen ersetzt werden. Man beachte, dass der Chiffriervorgang      nicht durch eine Funktion beschreibbar ist, da derselbe Klartext  in mehrere verschiedene Kryptotexte  übergehen kann. Durch eine geringfügige Modifikation der Polybios-Chiffre lässt sich die folgende bipartite homophone Chiffre erhalten. Beispiel 42 (homophone Substitution) Sei

A     Z, 
0     9 und


00     99.

 1,0 2,9 3,8 4,7 5,6 1,6 2,7 3,8 4,9 5,0

A B C D E

F G H I J

K L M N O

P U Q V R W S XY T Z

HOMOPHON




82 03 88 53 17 32 08 98

Genau wie bei Polybios wird eine   -Matrix als Schlüssel benutzt. Die Zeilen und Spalten von sind jedoch nicht nur mit jeweils einer, sondern mit zwei Ziffern versehen, so dass jeder Klartextbuchstabe  über vier verschiedene Koordinatenpaare ansprechbar ist. Der Kryptotextraum wird durch also in  Mengen ' ,  
, mit je  Homophonen partitioniert.

1 Klassische Verfahren

23

Wie wir noch sehen werden, sind homophone Chiffrierungen auch deshalb schwerer zu brechen, weil durch sie die charakteristische Häufigkeitsverteilung der Klartextbuchstaben zerstört wird. Dieser Effekt kann dadurch noch verstärkt werden, dass man für häufig vorkommende Klartextzeichen  eine entsprechend größere Menge '  an Homophonen vorsieht. Damit lässt sich erreichen, dass die Verteilung der im Geheimtext auftretenden Zeichen weitgehend nivelliert wird. Beispiel 43 (homophone Substitution, verbesserte Version) Ist  die Wahrscheinlichkeit, mit der ein Zeichen  
in der Klartextsprache auftritt, so sollte '      sein. 






15, 26, 44, 59, 70, 79
01, 84
13, 28, 75
02, 17, 36, 60, 95
04, 08, 12, 30, 43, 46, 47, 53, 61, 67, 69, 72, 80, 86, 90, 92, 97 .. .

0.0647 0.0193 0.0268 0.0483 0.1748 .. .

A B C D E .. .

Da der Buchstabe A im Deutschen beispielsweise mit einer Wahrscheinlichkeit von A
  auftritt, sind für ihn sechs verschiedene Homophone vorgesehen. Um den Suchaufwand bei der Dechiffrierung zu reduzieren, empfiehlt es sich, eine

   -Matrix anzulegen, in der jeder Klartextbuchstabe  an allen Stellen vorkommt, deren Koordinaten in '  enthalten sind.  1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0

N R T H N E N H T B

E G L R I U E N E D

C S I E E M K I L W

S N O A T F S B S E

A N U N P R C R D Q

O A D E H J T E R I

D U Z E S E I U E F

X C M S L N T G O E

I H N I A E A V S I

N Y E T R D A E E R

HOMOPHON




56 98 63 34 55 29 16 68

Offenbar kann man diese Matrix auch zur Chiffrierung benutzen, was sogar den positiven Nebeneffekt hat, dass dadurch eine zufällige Wahl der Homophone begünstigt wird.

Transpositionen Eng verwandt mit der Skytale-Chiffre ist die Zick-Zack-Transposition. Beispiel 44 Bei Ausführung einer Zick-Zack-Transposition wird der Klartext in eine Zick-Zack-Linie geschrieben und horizontal wieder ausgelesen. Die Höhe der ZickZack-Linie kann als Schlüssel vereinbart werden.

24

1 Klassische Verfahren Z

Z I

K

L A

C

K C




E I

I

ZICKZACKLINIE

N

zzleikakiiccn

Bei einer Zick-Zack-Transposition werden Zeichen im vorderen Klartextbereich bis fast ans Ende des Kryptotextes verlagert und umgekehrt. Dies hat den Nachteil, dass für die Generierung des Kryptotextes der gesamte Klartext gepuffert werden muss. Daher werden meist Blocktranspositionen verwendet, bei denen die Zeichen nur innerhalb fester Blockgrenzen transponiert werden. Definition 45

(Blocktranspositionschiffre)

Sei

 ein beliebiges Alphabet und für eine natürliche Zahl $  sei


 . Bei einer Blocktranspositionschiffre wird durch jeden Schlüssel    eine Permutation ( beschrieben, so dass für alle Zeichenfolgen       und      

       
    

und

      


 

       

gilt. Eine Blocktransposition mit Blocklänge $ lässt sich durch eine Permutation (also auf der Menge      $) beschreiben.

(





Beispiel 46 Eine Skytale, die mit 4 Zeilen der Länge 6 beschrieben wird, realisiert beispielsweise folgende Blocktransposition:  

                   

                   

Für die Entschlüsselung muss die zu ( inverse Permutation (
 benutzt werden. Beispiel 47

   (     



(
 

  

Wird ( durch Zyklen          dargestellt, wobei  auf  ,  auf  usw. und schließlich  auf  abgebildet wird, so ist (
 sehr leicht zu bestimmen. Beispiel 48 Obiges ( hat beispielsweise die Zyklendarstellung

(
      oder (
    

wenn, wie allgemein üblich, Einerzklen weggelassen werden. Daraus erhalten wir unmittelbar (
 zu (

     oder      wenn wir jeden Zyklus mit seinem kleinsten Element beginnen lassen und die Zyklen nach der Größe dieser Elemente anordnen.

1 Klassische Verfahren

25

Beispiel 49 Bei der Matrix-Transposition wird der Klartext zeilenweise in eine   Matrix eingelesen und der Kryptotext spaltenweise gemäß einer Spaltenpermutation ( , die als Schlüssel dient, wieder ausgelesen. Für (
     wird also zuerst Spalte ( 
, dann Spalte (  
 und danach Spalte ( 
 usw. und zuletzt Spalte ( 
ausgelesen.

  

D K X I H

I L T C R

E A I H L

S R S T A

E T T S N

R E N E G




DIESER KLARTEXT IST NICHT SEHR LANG srsta reneg dkxih eaihl ettsn iltcr

Beispiel 50 Bei der Weg-Transposition wird als Schlüssel eine Hamiltonlinie in einem Graphen mit einer vorgegebenen Knotennummerierung benutzt. (Eine Hamiltonlinie ist eine Anordnung aller Knoten des Graphen, in der je zwei aufeinanderfolgende Knoten durch eine Kante verbunden sein müssen.) Der Klartext wird gemäß der Knotennumerierung in den Graphen eingelesen und der Kryptotext entlang der Hamiltonlinie wieder ausgelesen. 1 H

2 A 3 M

4 I

L

T

5

6

HAMILTON

O

N

7

8




timlonah

Es ist leicht zu sehen, dass sich jede Blocktransposition durch eine Hamiltonlinie in einem geeigneten Graphen realisieren lässt. Der Vorteil, eine Hamiltonlinie als Schlüssel zu benutzen, besteht offenbar darin, dass man sich den Verlauf einer Hamiltonlinie bildhaft vorstellen und daher besser einprägen kann als eine Zahlenfolge. Sehr beliebt ist auch die Methode, eine Permutationen in Form eines Schlüsselworts (oder einer aus mehreren Wörtern bestehenden Schlüsselphrase) im Gedächtnis zu behalten. Aus einem solchen Schlüsselwort lässt sich die zugehörige Permutation ) leicht rekonstruieren, indem man das Wort auf Papier schreibt und in der Zeile darunter für jeden einzelnen Buchstaben seine Position  innerhalb des Wortes vermerkt. Schlüsselwort für 

 

Zyklendarstellung von 

CAESA R

      




DIE BLOCKLAENGE IST SECHS edboil lcanke igsset excsyh

Die Werte ) , die ) auf diesen Nummern annimmt, werden nun dadurch ermittelt, dass man die Schlüsselwort-Buchstaben in alphabetischer Reihenfolge durchzählt. Da-

26

1 Klassische Verfahren

bei werden mehrfach vorkommende Buchstaben gemäß ihrer Position im Schlüsselwort an die Reihe genommen. Alternativ kann man auch alle im Schlüsselwort wiederholt vorkommenden Buchstaben streichen, was im Fall des Schlüsselworts CAESAR auf eine Blocklänge von 5 führen würde.

1.8 Realisierung von Blocktranspositionen und einfachen Substitutionen Abschließend möchten wir eine einfache elektronische Realisierungsmöglichkeit von Blocktranspositionen erwähnen, die auf binär kodierten Klartexten operieren (d.h.

  ). Um einen Binärblock       der Länge $ zu permutieren, müssen die einzelnen Bits lediglich auf $ Leitungen gelegt und diese gemäß ( in einer sogenannten Permutationsbox (kurz P-Box) vertauscht werden.  
   





































 
   

Die Implementierung einer solchen P-Box kann beispielsweise auf einem VLSI-Chip erfolgen. Allerdings kann hierbei für größere Werte von $ aufgrund der hohen Zahl von Überkreuzungspunkten ein hoher Flächenbedarf anfallen. Blocktranspositionen können auch leicht durch Software als eine Folge von Zuweisungen y1 
x2 y2 
x5    y6 
x4 implementiert werden. Bei großer Blocklänge und sequentieller Abarbeitung erfordert diese Art der Implementierung jedoch einen relativ hohen Zeitaufwand. Von Alberti stammt die Idee, das Klartext- und Kryptotextalphabet auf zwei konzentrischen Scheiben unterschiedlichen Durchmessers anzuordnen. In Abbildung 1 ist gezeigt, wie sich mit einer solchen Drehscheibe beispielsweise die additive Chiffre realisieren lässt. Zur Einstellung des Schlüssels  müssen die Scheiben so gegeneinander verdreht werden, dass der Schlüsselbuchstabe   auf der inneren Scheibe mit dem Klartextzeichen 

A auf der äußeren Scheibe zur Deckung kommt. Auf der Drehscheibe in Abbildung 1 ist beispielsweise der Schlüssel 
 eingestellt, das heißt,  
d. Die Verschlüsselung geschieht nun durch bloßes Ablesen der zugehörigen Kryptotextzeichen auf der inneren Scheibe, so dass von der Drehfunktion der Scheiben nur bei einem Schlüsselwechsel Gebrauch gemacht wird. Aufgrund ihrer engen Verwandtschaft mit der Klasse der Blocktranspositionen lassen sich einfache Substitutionen auch mit Hilfe einer P-Box realisieren (vergleiche Abbil-

1 Klassische Verfahren

27 3 Volt

P Q R S tuv T rs w q

O

d

.. .

B

I J K L M mnop kl

V W X Y Z yzabc

x

C D E F ghi G ef j

H

U

A B C D E

A

N

Z































.. .

.. .







a b c d e .. . z

Abbildung 1 Realisierung von einfachen Substitutionen mit einer Drehscheibe und mit Hilfe von Steckverbindungen.

dung). Hierfür können beispielsweise zwei Steckkontaktleisten verwendet werden. Der aktuelle Schlüssel wird in diesem Fall durch Verbinden der entsprechenden Kontakte mit elektrischen Kabeln eingestellt (siehe Abbildung 1). Um etwa den Klartextbuchstaben E zu verschlüsseln, drückt man auf die entsprechende Taste, und das zugehörige Kryptotextzeichen b wird im selben Moment durch ein aufleuchtendes Lämpchen signalisiert. Schließlich lassen sich Substitutionen auch leicht durch Software realisieren. Hierzu wird ein Feld (array ) deklariert, dessen Einträge über die Klartextzeichen  
adressierbar sind. Das mit  indizierte Feldelemente enthält das Kryptotextzeichen, durch welches  beim Chiffriervorgang zu ersetzen ist. Ein Nachteil hierbei ist, dass das Feld nach jedem Schlüsselwechsel neu beschrieben werden muss. Um dies zu umgehen, kann ein zweidimensionales Feld deklariert werden, dessen Einträge zusätzlich über den aktuellen Schlüsselwert  adressierbar sind. Ist genügend Speicherplatz vorhanden, um für alle  
und alle    die zugehörigen Kryptotextzeichen    abspeichern zu können, so braucht das Feld nur einmal initialisiert und danach nicht mehr geändert werden. Schlüsselwert

 .. .



Klartextbuchstabe A B  Z u h  c e h  a .. .. . . .. . . . . y f



w

Die Tabelle zeigt ein Feld, dessen Einträge mit (zufällig gewählten) Kryptotextzeichen     
a     z initialisiert wurden, wobei  einen beliebigen Wert in dem Schlüsselraum 
       annehmen kann und  alle Klartextbuchstaben des Alphabets

A     Z durchläuft.

28

1 Klassische Verfahren

1.9 Klassifikation von Angriffen gegen Kryptosysteme Die Erfolgsaussichten eines Angriffs gegen ein Kryptosystem hängen sehr stark davon ab, wie gut die Ausgangslage ist, in der sich der Gegner befindet. Prinzipiell sollte man die Fähigkeiten des Gegners genauso wenig unterschätzen wie die Unvorsichtigkeit der Anwender von Kryptosystemen. Bereits vor mehr als einem Jahrhundert postulierte Kerckhoffs, dass die Frage der Sicherheit keinesfalls von irgendwelchen obskuren Annahmen über den Wissensstand des Gegners abhängig gemacht werden darf. Goldene Regel für Kryptosystem-Designer (auch „Kerckhoffs’ Prinzip“ genannt) Unterschätze niemals den Kryptoanalytiker. Gehe insbesondere immer von der Annahme aus, dass dem Gegner das angewandte System bekannt ist.  In der folgenden Liste sind eine Reihe von Angriffsszenarien mit zunehmender Gefährlichkeit aufgeführt. Auch wenn nicht alle Eventualitäten eines Angriffs vorhersehbar sind, so vermittelt diese Aufstellung doch eine gute Vorstellung davon, welchen unterschiedlichen Bedrohungen ein Kryptosystem im praktischen Einsatz ausgesetzt sein kann. Angriff bei bekanntem Kryptotext (ciphertext-only attack ) Der Gegner fängt Kryptotexte ab und versucht, allein aus ihrer Kenntnis Rückschlüsse auf die zugehörigen Klartexte oder auf die benutzten Schlüssel zu ziehen. Angriff bei bekanntem Klartext (known-plaintext attack ) Der Gegner ist im Besitz von einigen zusammengehörigen Klartext-KryptotextPaaren. Hierdurch wird erfahrungsgemäß die Entschlüsselung weiterer Kryptotexte oder die Bestimmung der benutzten Schlüssel wesentlich erleichtert. Angriff bei frei wählbarem Klartext (chosen-plaintext attack ) Der Angriff des Gegners wird zusätzlich dadurch erleichtert, dass er in der Lage ist (oder zumindest eine Zeit lang war), sich zu Klartexten seiner Wahl die zugehörigen Kryptotexte zu besorgen. Kann hierbei die Wahl der Kryptotexte in Abhängigkeit von zuvor erhaltenen Verschlüsselungsergebnissen getroffen werden, so spricht man von einem Angriff bei adaptiv wählbarem Klartext (adaptive chosen-plaintext attack ). Angriff bei frei wählbarem Kryptotext (chosen-ciphertext attack ) Vor der Beobachtung des zu entschlüsselnden Kryptotextes konnte sich der Gegner zu Kryptotexten seiner Wahl die zugehörigen Klartexte besorgen, ohne dabei jedoch in den Besitz des Dechiffrierschlüssels zu kommen (Mitternachtsattacke). Das dabei erworbene Wissen steht ihm nun bei der Durchführung seines Angriffs zur Verfügung. Auch in diesem Fall können sich die Erfolgsaussichten des Gegners erhöhen, wenn ein Angriff bei adaptiv wählbarem Kryptotext  Diese Annahme ergibt sich meist schon aus der Tatsache, dass die Prinzipien fast aller heute im Einsatz befindlichen Kryptosysteme allgemein bekannt sind.

1 Klassische Verfahren

29

(adaptive chosen-ciphertext attack ) möglich ist, also der Kryptotext in Abhängigkeit von den zuvor erzielten Entschlüsselungsergebnissen wählbar ist. Angriff bei frei (oder adaptiv) wählbarem Text (chosen-text attack ) Sowohl Klartexte als auch Kryptotexte sind frei (oder sogar adaptiv) wählbar. Ohne Frage ist ein Kryptosystem, das bereits bei einem Angriff mit bekanntem Kryptotext Schwächen erkennen lässt, für den praktischen Einsatz vollkommen ungeeignet. Tatsächlich müssen aber an ein praxistaugliches Kryptosystem noch weit höhere Anforderungen gestellt werden. Denn häufig unterlaufen den Anwendern sogenannte Chiffrierfehler, die einen Gegner leicht in eine sehr viel günstigere Ausgangsposition versetzen als dies sonst der Fall wäre. So ermöglicht beispielsweise das Auftreten stereotyper Klartext-Formulierungen einen Angriff bei bekanntem Klartext, sofern der Gegner diese Formulierungen kennt oder auch nur errät. Begünstigt durch derartige Unvorsichtigkeiten, die im praktischen Einsatz nicht vollständig vermeidbar sind, können sich selbst winzige Konstruktionsschwächen eines Kryptosystems sehr schnell zu einer ernsthaften Bedrohung der damit verfolgten Sicherheitsinteressen auswachsen. Die Geschichte der Kryptographie belegt sehr eindrucksvoll, dass es häufig die Anwender eines Kryptosystems selbst sind, die – im unerschütterlichen Glauben an seine kryptographische Stärke – dem Gegner zum Erfolg verhelfen. Zusammenfassend lässt sich also festhalten, dass die Gefährlichkeit von Angriffen, denen ein Kryptosystem im praktischen Einsatz ausgesetzt ist, kaum zu überschätzen ist. Andererseits kann selbst das beste Kryptosystem keinen Schutz vor einer unbefugten Dechiffrierung mehr bieten, wenn es dem Gegner etwa gelingt, in den Besitz des geheimen Schlüssels zu kommen – sei es aus Unachtsamkeit der Anwender oder infolge einer Gewaltandrohung des Gegners (kompromittierte Schlüssel).

1.10 Kryptoanalyse von Blocktranspositionen Mit Hilfe von Bigrammhäufigkeiten, die manchmal auch als Kontakthäufigkeiten bezeichnet werden, lassen sich Blocktranspositionen sehr leicht brechen, sofern genügend Kryptotext vorliegt. Ist die Blocklänge $ bekannt, so trägt man hierzu den Kryptotext zeilenweise in eine Matrix
*   mit $ Spalten        ein. Da jede Zeile dieser Matrix aus dem zugehörigen Klartextblock mit derselben Permutation ( erzeugt wurde, müssen die Spalten  jetzt nur noch in die „richtige“ Reihenfolge gebracht werden, um den gesuchten Klartext zu erhalten. Der Nachfolger  von  (bzw. der Vorgänger

 von  ) kann sehr gut anhand der Werte von     
 *  *  bestimmt werden.



 





        

  


     

ER EN CH DE EI ND TE IN IE GE ES NE UN ST RE HE AN BE SE NG DI SC Abbildung 2 Die häufigsten Bigramme im Deutschen (Angaben in %).

30

1 Klassische Verfahren


 
     

 
 
          

TH HE AN IN ER RE ON ES TI AT ST EN OR ND TO NT ED IS AR OU OF TE Abbildung 3 Die häufigsten Bigramme im Englischen (in %; nach O.P. Meaker, 1939). 

                 
    

EIN ICH NDE DIE UND DER CHE END GEN SCH CHT DEN INE NGE NUN UNG DAS HEN IND Abbildung 4 Die häufigsten Trigramme im Deutschen (in %).

Beispiel 51 (Häufigkeitsanalyse von Bigrammen) Für den mit einer Blocktransposition (mit vermuteter Blocklänge 5) erzeugten Kryptotext IHEHR BWEAN RNEII NRKEU ELNZK RXTAE VLOTR ENGIE

erhalten wir eine Matrix mit den folgenden fünf Spalten.

     I B R N E R V E

H W N R L X L N

E E E K N T O G

H A I E Z A T I

R N I U K E R E

Um die richtige Vorgänger- oder Nachfolgerspalte von  zu finden, bestimmen wir für jede potentielle Spalte  , 
     , wieviele der Bigramme * * (bzw. * * ) zu den 20 häufigsten (aus Abbildung 2) gehören.





         H W N R L X L N

E E E K N T O G

H A I E Z A T I

R N I U K E R E

I B R N E R V E

H W N R L X L N

E E E K N T O G

H A I E Z A T I

R N I U K E R E

Da die beiden Spaltenpaare      und      jeweils vier häufige Bigramme bilden, können wir annehmen, dass im Klartext  auf  oder  auf  folgen muss. Entscheiden wir uns für die zweite Möglichkeit, so sollten wir als nächstes die Spaltenpaare      und     , 
   betrachten.

1 Klassische Verfahren 

31

 
           
    
 

THE ING AND ION TIO ENT ERE HER ATE VER TER THA ATI FOR HAT ERS HIS RES ILL Abbildung 5 Die häufigsten Trigramme im Englischen (in %).





        H W N R L X L N

H A I E Z A T I

R N I U K E R E

I B R N E R V E

E E E K N T O G

H W N R L X L N

H A I E Z A T I

R N I U K E R E

Aufgrund des hohen Wertes von      können wir annehmen, dass auf  die Spalte

 folgt. Im nächsten Schritt erhalten wir daher die folgende Tabelle.

 

 

       H W N R L X L N

H A I E Z A T I

I B R N E R V E

E E E K N T O G

R N I U K E R E

H W N R L X L N

H A I E Z A T I

Diese lässt die Spaltenanordnung          vermuten, welche tatsächlich auf den gesuchten Klartext führt.

1.11 Kryptoanalyse von einfachen Substitutionschiffren Manche der bisher betrachteten Chiffrierverfahren verwenden einen so kleinen Schlüsselraum, dass ohne großen Aufwand eine vollständige Schlüsselsuche ausgeführt werden kann. Beispiel 52 (vollständige Schlüsselsuche) Es sei bekannt, dass das Kryptotextstück 
saxp mit einer additiven Chiffre erzeugt wurde (




 ). Entschlüsseln wir  probeweise mit allen möglichen Schlüsselwerten, so erhalten wir folgende Zeichenketten.  B C D E F G H I J K L M   RZWO QYVN PXUM OWTL NVSK MURJ LTQI KSPH JROG IQNF HPME GOLD N O P Q R S T U V W X Y Z FNKC EMJB DLIA CKHZ BJGY AIFX ZHEW YGDV XFCU WEBT VDAS UCZR TBYQ

32

1 Klassische Verfahren

Unter diesen springen vor allem die beiden Klartextkandidaten 
GOLD (Schlüsselwert 
M) und 
WEBT (
W) ins Auge. Ist *
  die Größe des Schlüsselraums, so kann der Gegner bei bekanntem Kryptotext  die Suche nach dem zugehörigen Klartext  auf eine Menge von maximal * Texten        beschränken. Daneben hat der Gegner ein gewisses a priori Wissen über den Klartext, wie zum Beispiel dass er in deutscher Sprache verfasst ist, das es ihm gestattet, einen Großteil der Texte   auszuschließen. Ferner erscheinen aufgrund dieses Hintergrundwissens manche der übrig gebliebenen Klartextkandidaten plausibler als andere (sofern nicht nur ein einziger übrig bleibt). Mit jedem Text   , der nicht als Klartext in Frage kommt, kann auch mindestens ein Schlüssel ausgeschlossen werden. Sind noch mehrere Schlüsselwerte möglich, so kann weiteres Kryptotextmaterial Klarheit bringen. Manchmal hilft aber auch eine Inspektion der verbliebenen Schlüsselwerte weiter, etwa wenn der Schlüssel nicht rein zufällig erzeugt wurde, sondern aus einem einprägsamen Schlüsselwort ableitbar ist.  




 



 









 






 





  

 






A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Abbildung 6 Häufigkeitsverteilung von Einzelbuchstaben im Deutschen (in %). 


 















 


 






 


 


   



A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Abbildung 7 Häufigkeitsverteilung von Einzelbuchstaben im Englischen (in %).  

 







  




  







   

  

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Abbildung 8 Häufigkeitsverteilung von Einzelbuchstaben im Französischen (in %).

1 Klassische Verfahren

33

Meist kennt der Gegner zumindest die Sprache, in der der gesuchte Klartext abgefasst ist. Mit zunehmender Länge gleichen sich die Häufigkeitsverteilungen der Buchstaben in natürlichsprachigen Texten einer „Grenzverteilung“ an, die in erster Linie von der benutzten Sprache und nur in geringem Umfang von der Art des Textes abhängt. Diese Verteilungen weisen typischerweise eine sehr starke Ungleichmäßigkeit auf, was darauf zurückzuführen ist, dass in natürlichen Sprachen relativ viel Redundanz enthalten ist. Die Abbildungen 6, 7 und 8, zeigen typische Verteilungen von Einzelbuchstaben in der deutschen, englischen und französischen Sprache (ohne Berücksichtigung von Interpunktions- und Leerzeichen). Ein typischer deutscher Text besteht demnach zu 62% aus den sieben häufigsten Zeichen E, N, I, R, S, A, T (das sind nicht einmal 27% der Klartextzeichen). Bei additiven Chiffren reicht es oftmals, den häufigsten Buchstaben im Kryptotext zu bestimmen, und davon den häufigsten Buchstaben der Klartextsprache zu subtrahieren, um den Schlüssel  zu erhalten. Bei affinen Chiffren müssen gewöhnlich nur die beiden häufigsten Buchstaben bestimmt werden; dadurch erhält man zwei Verschlüsselungsgleichungen. Dieses Gleichungssystem muss gelöst werden, und man erhält das gesuchte Schlüsselpaar. Beispiel 53 (Analyse einer affinen Chiffre mittels Buchstabenhäufigkeiten) Es sei bekannt, dass sich hinter dem Kryptotext laoea ehoap hwvae ixobg jcbho thlob lokhe ixope vbcix ockix qoppo boapo mohqc euogk opeho jhkpl eappj seobe ixoap opmcu

ein deutscher Klartext verbirgt, der mit einer additiven Chiffre verschlüsselt wurde. Berechnen wir für jedes Chiffrezeichen  die (absolute) Häufigkeit '   seines Auftretens,  a b c d e f g h i j k l m n o p q r s t u v w x y z

                 

so liegt die Vermutung nahe, dass das am häufigsten vorkommende Chiffrezeichen p für das Klartextzeichen E und das am zweithäufigsten vorkommende o für N steht. Unter dieser Annahme kann der gesuchte Schlüssel 
  als Lösung der beiden Gleichungen

E 
N 


o p

bestimmt werden. Subtrahieren wir nämlich die erste von der zweiten Gleichung, so erhalten wir die Kongruenz     , woraus sich 
 und damit 
ergibt. Tatsächlich weist der Schlüssel 
  nicht nur für die beiden Paare E o und N p, sondern auch für alle übrigen Paare   eine gute Übereinstimmung zwischen der Häufigkeit '  , mit der 
   im Kryptotext vorkommt, und der erwarteten Häufigkeit   auf, mit der  in einem typischen deutschen Text der Länge  vorkommt (die Tabelle zeigt die Werte von   gerundet):

34

1 Klassische Verfahren

 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z                        
 
  c f i l o r u x a d g j m p s v y b e h k n q t w z

                 

Durch eine Häufigkeitsanalyse können insbesondere einfache Substitutionen  leicht gebrochen werden, sofern die einzelnen Buchstaben  in der benutzten Klartextsprache mit voneinander differierenden Häufigkeiten  auftreten (vergleiche Tabelle 2). Selbst wenn, was insbesondere bei kurzen Texten zu erwarten ist, die tatsächliche Häufigkeitsverteilung nur in etwa der vom Gegner angenommenen Verteilung entspricht, reduziert sich dadurch die Zahl der in Frage kommenden einfachen Substitutionen ganz erheblich. Berechnet man die relativen Häufigkeiten ! der Kryptotextbuchstaben im Kryptotext, so gilt   !  (vorausgesetzt der Kryptotext ist genügend lang). Für die Schilderung einer nach dieser Methode durchgeführten Kryptoanalse sei auf die Erzählung „Der Goldkäfer“ von Edgar Allan Poe verwiesen. Tabelle 2 Einteilung von Buchstaben in Cliquen mit vergleichbaren Häufigkeitswerten.

sehr häufig häufig durchschnittlich selten sehr selten

Deutsch E N IRS AT DHU LGO CM BFWKZ PV JYXQ

Englisch E T AOIN SRH LD CUMF PGWYB VK XJQZ

Französisch E N ARSITU LD CMP V FBGQHX JYZKW

1.12 Kryptoanalyse von polygraphischen Chiffren Blocksysteme mit kleinem  (beispielsweise bigraphische Systeme) lassen sich ähnlich wie einfache Substitutionen durch Häufigkeitsanalysen brechen. Wird bei Hill-Chiffren  sehr groß gewählt, so ist eine solche statistische Analyse nicht mehr möglich. Das Hill-System kann dann zwar einem Kryptotextangriff widerstehen, jedoch kaum einem Angriff mit bekanntem Klartext und schon gar nicht einem Angriff mit gewähltem Klartext. Angriff mit gewähltem Klartext O. B. d. A. sei

       . Bei einem GK-Angriff verschafft sich der Gegner den Kryptotext zu     ,     , . . . ,     
 :

    
              
         .. .

    
         und erhält damit die Schlüsselmatrix  .

1 Klassische Verfahren

35

BK-Angriff (bekannter Klartext). Sind bei einem BK-Angriff ausreichend geeignete Klartext-Kryptotextpaare bekannt, so kann das Hill-System folgendermaßen gebrochen werden: Sind    (
     ) Paare mit  
 und gilt

 + 
 für eine aus $ Blöcken  ,   , , als Zeilen gebildete Matrix + , so lässt sich die Schlüsselmatrix  zu 
- +
 bestimmen (- ist die aus den Blöcken   ,   , , gebildete Matrix).

1.13 Kryptoanalyse von polyalphabetischen Chiffren Die Vigenère-Chiffre galt bis ins 19. Jahrhundert als sicher. Da der Schlüsselstrom bei der Vigenère-Chiffre periodisch ist, lassen sie sich mit statistischen Methoden ebenfalls leicht brechen, insbesondere wenn der Kryptotext im Verhältnis zur Periode  (Länge des Schlüsselwortes) genügend lang ist. Bestimmung der Schlüsselwortlänge Wir haben gesehen, dass es recht einfach ist, eine Vigenère-Chiffre zu brechen, wenn man die Länge des Schlüsselwortes hat. Diese ist im allgemeinen aber nicht bekannt, so dass man vor der Anwendung des eben beschriebenen Verfahrens zuerst einmal die Schlüsselwortlänge in Erfahrung bringen muss. Dazu betrachten wir zwei Vorgehensweisen: den Kasiski-Test und die Koinzidenzindex-Untersuchung. Der Kasiski-Test. Die früheste generelle Methode zur Bestimmung der Periode bei der Vigenère-Chiffre stammt von Friedrich W. Kasiski (1860). Kommt ein Wort an zwei verschiedenen Stellen im Kryptotext vor, so kann es sein, dass die gleiche Klartextsequenz zweimal auf die gleiche Weise, d. h. mit der gleichen Schlüsselsequenz, verschlüsselt wurde. In diesem Fall ist die Entfernung Æ der beiden Vorkommen ein Vielfaches der Periode . Werden mehrere Paare mit verschiedenen Entfernungen Æ  gefunden, so liegt die Vermutung nahe, dass  gemeinsamer Teiler aller (oder zumindest vieler) Æ ist, was die Anzahl der noch in Frage kommenden Werte für  stark einschränkt. Beispiel 54 (Kasiski-Test)



DERERSTEUNDLETZTEVERS... (Klartext ) KASKASKASKASKASKASKAS... (Schlüsselstrom ) nejorkdemxddotrden ork... (Kryptotext  )








Dass die Textstücke ork, bzw. de im Kryptotext in den Entfernungen Æ 
 und Æ
 vorkommen, führt auf die richtige Vermutung, dass die Periode 


 


ist.

Koinzidenzindex-Untersuchungen. Zur Bestimmung der Periode  gibt es neben heuristischen Methoden auch folgenden statistischen Ansatz, der erstmals von William Fre-

36

1 Klassische Verfahren

derick Friedman im Jahr 1920 beschrieben wurde. Er basiert auf der Beobachtung, dass eine längere Periode eine zunehmende Glättung der Buchstabenhäufigkeiten im Kryptotext bewirkt. Definition 55

(Koinzidenzindex)

Der Koinzidenzindex (engl. index of coincidence ) eines Textes  der Länge  über dem Alphabet  ist definiert als


 
     '   '   

Hierbei ist '  die absolute Häufigkeit des Buchstabens  im Text  .

 gibt also die Wahrscheinlichkeit an, mit der man im Text  an zwei zufällig gewählten Positionen den gleichen Buchstaben vorfindet. Er ist umso größer, je ungleichmäßiger die Häufigkeiten '  sind (siehe unten).




Um die Periode  einer Vigenère-Chiffre zu bestimmen, schreibt man den Kryptotext  für 
      in eine Matrix mit  Spalten und berechnet für jede Spalte   den Koinzidenzindex. Für genügend lange Kryptotexte ist dasjenige , welches das maximale arithmetische Mittel der Spaltenindizes liefert mit hoher Wahrscheinlichkeit die gesuchte Periode.

Ist der Koinzidenzindex
  der Klartextsprache bekannt, so kann der Suchraum für den Wert der Periode  erheblich eingeschränkt werden. Da der Erwartungswert !
  des Koinzidenzindexes für den Kryptotext stark von der verwendeten Periode abhängt, kann nämlich die Periode  in erster Näherung durch Vergleich von
   mit dem Erwartungswert !
  abgeschätzt werden. Untenstehende Tabelle gibt den Erwartungswert !
  des Koinzidenzindexes für Kryptotexte der Länge 
 in Abhängigkeit von der Periodenlänge  einer Vigenère-Chiffre wieder (Klartext ist ein zufällig gewählter Text der englischen Sprache).

 !
 

1 2 3 4 5 6 8 10  0,0687 0,0535 0,0484 0,0459 0,0444 0,0434 0,0422 0,0414 0,0389

Beispiel 56 Berechnet sich der Koinzidenzindex eines vorliegenden Kryptotextes (mit der Länge  ) zu  , so liegt die Vermutung nahe, dass das verwendete Schlüsselwort die Länge vier oder fünf hat. Allgemein gilt

    !
 
    
     

wobei
  der Koinzidenzindex der Klartextsprache . über dem Alphabet
ist (ohne Beweis). Definition 57

(Koinzidenzindex einer Sprache)

1 Klassische Verfahren

37

Der Koinzidenzindex
  einer Sprache mit Buchstabenverteilung
 "  # ist definiert als











 

 ist die Wahrscheinlichkeit, in einem zufälligen Text der Sprache . an zwei zufällig gewählten Positionen den gleichen Buchstaben vorzufinden, während
  die Wahrscheinlichkeit für das Auftreten dieses Ereignisses im Text  ist.




Man beachte, dass der Koinzidenzindex bei Transpositionschiffren sowie bei einfachen Substitutionen erhalten bleibt. Erstere lassen sich von letzteren dadurch unterscheiden, dass bei ihnen sogar die Buchstabenhäufigkeiten unverändert bleiben.


 ist zudem ein Maß für die Rauheit der Verteilung :

Definition 58

(Rauheitsgrad; Measure of Roughness) 

Der Rauheitsgrad

 ist






 

 einer Sprache . mit Einzelbuchstabenverteilung

 



 

 


  


wobei 

 ist. Beispiel 59 Für die englische Sprache (   und /    .


) gilt beispielsweise
 



Ist  bekannt, so schreibt man den Kryptotext in Blöcke der (Zeilen-) Länge  untereinander. Verfahrensbedingt wurden die einzelnen Spalten         durch eine monoalphabetische Substitution (genauer: durch eine Verschiebechiffre) verschlüsselt. Sie können daher einzeln wie eine additive Chiffre gebrochen werden (Häufigkeitsanalyse); jede Spalte  liefert einen Buchstaben   des Schlüsselwortes der Vigenère-Chiffre. Zur Bestimmung des Schlüsselwortes bei bekannter Periode  kann auch wie folgt vorgegangen werden. Man schreibt den Kryptotext  in Spalten   auf und berechnet für  
und 
      die relativen Häufigkeiten !   von  in  . Da  aus dem Klartext durch Addition von   entstanden ist, kommt die Verteilung

!    
für 
 der Klartextverteilung   
näher als für 
  . Da 0  






!  

ein Maß für die Ähnlichkeit der beiden Verteilungen  und !     ist (siehe Übungen), wird der Wert von 0    wahrscheinlich für 
  maximal werden.

38

1 Klassische Verfahren

Beispiel 60 Der folgende Kryptotext  HUDS LOIJ OSPW ZWSI LSAM VII

KUAE VFIC AOCH ZVDS USUV

ZGXR VBTH IMCS ATGS VAIL

AVTF LUGI YHWQ THWI LHGI

PGWS LGPR HWCF SSUX LHWV

WGWS KHWM YOCG LMTS VIVL

ZHTP YHTI OGTZ MHWI AVTW

PBIL UAXR LBIL KSPX OCIJ

LRTZ BHTW SWBF OGWI PTIC

PZHW UCGX LOHX HRPF MSTX

der Länge  wurde von einer Vigenère-Chiffre mit Schlüssellänge 
 aus englischem Klartext erzeugt. Schreiben wir den Kryptotext in vier Spalten         der Länge  
 
 
 und  
 , so ergeben sich folgende Werte für 0 .

 0  0  0  0                                                                                                                                                                                                                                                       Da 0   für 

H, 0   für 

O, 0   für 

P und 0   für 

E einen Maximalwert annimmt, lautet das Schlüsselwort HOPE. Damit ergibt sich folgender Klartext

A GOOD GLASS IN THE BISHOPS HOSTEL IN THE DEVILS

1 Klassische Verfahren

39

SEAT FORTYONE DEGREES AND THIRTEEN MINUTES NORTHEAST AND BY NORTH MAIN BRANCH SEVENTH LIMB EAST SIDE SHOOT FROM THE LEFT EYE OF THE DEATHS HEAD A BEE LINE FROM THE TREE THROUGH THE SHOT FIFTY FEET OUT

Zur Bestimmung des Schlüsselwortes kann man auch die Methode des gegenseitigen Koinzidenzindexes verwenden. Dabei ist die verwendete Klartextsprache (und somit deren Häufigkeitsverteilung) irrelevant, da die Spalten – wie der Name schon sagt – gegenseitig in Relation gesetzt werden. Aber zuerst die Definition. Definition 61

(Gegenseitiger Koinzidenzindex)

Der gegenseitge Koinzidenzindex von zwei Texten  und   mit den Längen  und   über dem Alphabet  ist definiert als


   
   '   '   

Hierbei ist '  bzw. '   die absolute Häufigkeit des Buchstabens  im Text  bzw.   .

   ist also die Wahrscheinlichkeit, dass bei zufälliger Wahl einer Position in  und einer Position in   der gleiche Buchstabe vorgefunden wird.
     ist umso größer, je besser die Häufigkeitsverteilung von  und   (d. h. ' und '  ) übereinstim


men.

Ist nun  ein Kryptotext, der mit einem Schlüsselwort bekannter Länge  erzeugt wurde, und sind  , 
      die zugehörigen Spalten, so gibt der gegenseitige Koinzidenzindex der Spalten   und  Æ (für    %   ) die Wahrscheinlichkeit an, dass man bei zufälliger Wahl einer Position in   und in  Æ denselben Buchstaben vorfindet, wobei Æ eine Verschiebung von Spalte   relativ zur Spalte  ist (mit  Æ  ). Mit großer Wahrscheinlichkeit nimmt also
     Æ  für Æ
Æ
  einen relativ großen Wert an, während für Æ
Æ  mit kleinen Werten zu rechnen ist.

Beispiel 62 Betrachten wir den Kryptotext aus vorigem Beispiel, so ergeben sich folgende Werte für
    Æ .

40

1 Klassische Verfahren

$                      

%  %                                                                 


%  %                                                              


%  %                                                              


%  %                                                                     


%  %                                                                      


%  %                                        
                          


Also ist (mit großer Wahrscheinlichkeit)

$ 
 $ 
 $ 
 $ 
 $ 
 $ 
 Wir können nun alle Spalten relativ zur ersten Spalte so verschieben, dass der ganze Text eine einheitliche Verschiebung $ hat, also die zweite Spalte um , die dritte um  und die vierte um . Für die Bestimmung von $, muss man nur den häufigsten Buchstaben in dem auf diese Weise erzeugten Text bestimmen. Dieser ist L ( &). Also ist $
L E
H
 und das Schlüsselwort lautet HOPE (H 
O, H 
P, H 
E). Analyse der Lauftextverschlüsselung Zum Brechen einer Stromchiffre mit Klartextschlüsselstrom kann man so vorgehen: Man geht zunächst davon aus, dass jeder Kryptotextbuchstabe durch Summation eines Klartext- und Schlüsselstrombuchstabens mit jeweils mittlerer bis hoher Wahrscheinlichkeit entstanden ist. Dies sind beispielsweise im Englischen die Buchstaben E, T, A, O, I, N, S, R, H. Zu einem Teilwort & des Kryptotextes bestimmt man dann alle Paare von Wörtern (&   & ) mit & &
& und &  &  E T A O I N S R H. In der Regel ergeben sich nur sehr wenige sinnvolle Paare, aus denen durch Kontextbetrachtungen und Erweitern von & nach links und rechts der Kryptotext entschlüsselt

1 Klassische Verfahren

41

werden kann. Wird die Analyse durch ein Computerprogramm durchgeführt, kann an die Stelle der Kontextbetrachtungen auch die Häufigkeitsverteilung von -Grammen der Sprache treten. Das Programm wählt dann solche Wortpaare (&   & ), die eine hohe Wahrscheinlichkeit haben. Beispiel 63 Gegeben ist der Kryptotext moqkthcblmwxf. . . Wir beginnen die Untersuchung mit einer Wortlänge von vier Buchstaben, also &
moqk. Der erste Buchstabe m kann nur auf eine der folgenden Arten zustande gekommen sein: abcde...i...t...z MLKJI...E...T...N MMMMM...M...M...M




(Klartextzeichen) (Schlüsselzeichen) (Kryptotextzeichen)

Es ergeben sich als wahrscheinliche Paare für die Einzelbuchstaben von &: m:

und damit & 

& &

(E,I) (I,E) (T,T)

o:

(A,O) (H,H) (O,A)

q:

(I,I)

k:

(R,T) (S,S) (T,R)

... ...

THIS THIS

... ...

&  zu

EAIR IOIT

EAIS IOIS

EAIT IOIR

EHIR IHIT

Als sinnvoll stellt sich also nur die Wahl & 

TOIT TAIR


&
ÌÀÁË heraus.

Autokey Chiffren Kryptotextschlüsselstrom. Diese Systeme bieten eigentlich keinen großen kryptographischen Schutz, da sie ohne Kenntnis des Schlüsselwortes sehr leicht entschlüsselt werden können (falls die Länge des Schlüsselwortes im Verhältnis zur Länge des Kryptotextes relativ kurz ist). Man subtrahiert dazu den Kryptotext  für 
     von dem um  Positionen verschobenen Kryptotext – also  Æ Æ Æ    minus       –, bis sinnvoller (Klar-) Text erscheint:






dumsqmozkfn... DUMSQMO... ....NSCHUTZ...

(Kryptotext  ) („Kryptotextschlüsselstrom“) (Klartext )

Klartextschlüsselstrom. Neben der oben beschriebenen Analyse der Lauftextverschlüsselung kann das Brechen der Autokey -Systeme mit Klartextschlüsselstrom auch analog zur Kasiski-Methode erfolgen: Sei  die Länge des Schlüsselwortes       . Falls im Klartext die gleiche Buchstabenfolge      Æ
 im Abstand  auftritt (beispielsweise 
 und Æ
),

42

1 Klassische Verfahren

 








 
           
. . .



  
         . . .  
    




 




  
. . .

(Klartext ) (Klartextschlüsselstrom
) (Kryptotext  )

so tritt im Kryptotext die gleiche Buchstabenfolge im Abstand  auf, d. h.  kann auf diese Art unter Umständen leicht bestimmt werden. Ist  bekannt, so können die Buchstaben      des Schlüsselwortes der Reihe nach bestimmt werden: Da durch   die Klartextzeichen an den Positionen         eindeutig festgelegt sind, kann jedes einzelne  unabhängig von den anderen Schlüsselwortbuchstaben durch eine statistische Analyse bestimmt werden. Bei der dritten Methode Autokey -Chiffren mit Klartextschlüsselstrom zu brechen, „rechnet man den Schlüssel aus dem Kryptotext heraus“. Doch zuerst einige allgemeine Betrachtungen zu den Eigenschaften einer Autokey -Chiffre mit Klartextschlüsselstrom. Betrachten wir den Klartext HIERKOMMTEINMUSTER, welcher mit dem Schlüssel DER verschlüsselt werden soll:




(Klartext) (Schlüsselstrom) (Kryptotext)

HIERKOMMTEINMUSTER DERHIERKOMMTEINMUS kmvyssdwhqugqcffyj

Für eine kryptoanalytische Untersuchung des Geheimtextes nehmen wir nun an, dass die Schlüsselwortlänge 
 bekannt ist und dechiffrieren den Kryptotext mit einem beliebigen Schlüssel dieser Länge (beispielsweise AAA).

kmvyssdwhqugqcffyj AAAKMVOGXPQKBEWPYJ KMVOGXPQKBEWPYJQAA






(Kryptotext) (Schlüsselstrom) (modifizierter Klartext)

Der modifizierte Klartext wird nun mit dem ursprünglichen Klartext verglichen. Dabei fällt auf, dass sich die Differenzen der Buchstaben im Abstand der doppelten Schlüsselwortlänge wiederholen: h K

i M

e V

 









r O

k G

o X

m P

m Q

t K











 

e B

i E

n W

m P

u Y

s J











 

t Q

e A

r A





Diese Wiederholung besagt aber nichts anderes, als dass bei dem modifizierten Klartext eine gewöhnliche Vigenère-Chiffre vorliegt, die mit einem Schlüssel der Länge  chiffriert wurde. Als kryptoanalytische Vorgehensweise ergibt sich daraus folgende Strategie:

1 Klassische Verfahren

43

Da die Länge  des Schlüsselwortes nicht bekannt ist, erzeugt man (wie oben beschrieben) unter Verwendung von unterschiedlichen Werten für 
      aus dem Kryptotext eine Anzahl modifizierter Klartexte, die dann einer Häufigkeitsanalyse mit doppelter Schlüssellänge unterzogen werden. Bei dieser Untersuchung sind nur die ersten  Stellen von Bedeutung; sie ergeben das Schlüsselwort, mit dem der ursprünglich gegebene Kryptotext entschlüsselt werden kann. 

1.14 Informationstheoretische Sicherheitsanalyse Claude E. Shannon untersuchte die Sicherheit kryptographischer Systeme auf informationstheoretischer Basis (1945, freigegeben 1949). Seinen Untersuchungen liegt das Modell einer Nachrichtenquelle zugrunde, die einzelne Nachrichten unter einer bestimmten Wahrscheinlichkeitsverteilung aussendet. Bei der Betrachtung der informationstheoretischen Eigenschaften von Kryptosystemen gehen wir von einer Wahrscheinlichkeitsverteilung auf den Paaren      aus, d. h.   gibt die Wahrscheinlichkeit an, dass der Klartext  mit dem Schlüssel  verschlüsselt wird. Dabei setzen wir voraus, dass nach jeder Verschlüsselung einer Nachricht  ein neuer Schlüssel gewählt wird. Dies bedeutet, dass beispielsweise bei der additiven Chiffre für

 zu setzen ist (und nicht

wie in Definition 4), falls mit dem selben Schlüssel eine Folge von  Buchstaben chiffriert wird. Weiterhin nehmen wir an, dass der Schlüssel unabhängig vom Klartext gewählt wird. D.h. es ist  
 , wobei






 



die Wahrscheinlichkeit für den Schlüssel  und








 

die Wahrscheinlichkeit für den Klartext  ist. O.B.d.A. sei   für alle Klartexte   , da wir andernfalls  aus entfernen können. Für einen Kryptotext  berechnet sich die Wahrscheinlichkeit zu






 



und für einen fest vorgegebenen Kryptotext  ist




  

 

 Unter Verwendung des ursprünglichen Kryptosystems: Autokey -Chiffre mit Klartextschlüsselstrom!

44

1 Klassische Verfahren

die (bedingte) Wahrscheinlichkeit dafür, dass  aus dem Klartext  entstanden ist. Wir nehmen o.B.d.A. an, dass für alle      ist (andernfalls kann  aus entfernt werden). Definition 64

(informationstheoretisch sicher)

Ein Kryptosystem heißt absolut sicher (informationstheoretisch sicher), falls für alle   und alle   gilt:


 Bei einem absolut sicheren Kryptosystem ist demnach die a posteriori Wahrscheinlichkeit   einer Klartextnachricht  gleich der a priori Wahrscheinlichkeit , d.h. die Wahrscheinlichkeit von  sie ist unabhängig davon, ob der Kryptotext  bekannt ist oder nicht. Die Kenntnis von  erlaubt somit keinerlei Rückschlüsse auf die gesendete Nachricht . Dies bedeutet, dass es dem Gegner nicht möglich ist – auch nicht mit unbegrenzten Rechenressourcen – das System zu brechen. Wie wir sehen werden, lässt sich diese Art der Sicherheit nur mit einem extrem hohen Aufwand realisieren. Daher begnügt man sich meist mit schwächeren Sicherheitsanforderungen. – Ein Kryptosystem gilt als komplexitätstheoretisch sicher oder als berechnungssicher (computationally secure ), falls es dem Gegner nicht möglich ist, das System mit einem für ihn lohnenswerten Aufwand zu brechen. Das heißt, die Kosten eines erfolgreichen Angriffs (sofern dieser überhaupt möglich ist), würden den Nutzen bei weitem übersteigen. – Ein Kryptosystem gilt als nachweisbar sicher (provably secure ), wenn seine Sicherheit mit bekannten komplexitätstheoretischen Hypothesen verknüpft werden kann, deren Gültigkeit gemeinhin akzeptiert ist. – Als praktisch sicher (practically secure ) werden dagegen Kryptosysteme eingestuft, die über mehrere Jahre hinweg jedem Versuch einer erfolgreichen Kryptoanalyse widerstehen konnten, obwohl sie bereits eine weite Verbereitung gefunden haben und allein schon deshalb ein lohnenswertes Ziel für einen Angriff darstellen. Die komplexitätstheoretische Analyse eines Kryptosystems ist äußerst schwierig. Dies hängt damit zusammen, daß der Aufwand eines erfolgreichen Angriffs unabhängig davon abgeschätzt werden muß, welche Strategie dabei verfolgt wird. Das heißt, es genügt nicht, alle derzeit bekannten kryptoanalytischen Ansätze in Betracht zu ziehen, sondern es müssen alle möglichen berücksichtigt werden. Dabei darf sich die Aufwandsanalyse auch nicht ausschließlich an einer vollständigen Rekonstruktion des Klartextes orientieren. Denn auch die Kenntnis winziger Klartextfragmente kann für den Gegner einen großen Vorteil bedeuten. Aus den genannten Gründen ist es bis heute noch für kein praktikables Kryptosystem gelungen, seine komplexitätstheoretische Sicherheit mathematisch zu beweisen. Damit ist auch nicht so schnell zu rechnen, zumindest nicht solange der Status fundamentaler

1 Klassische Verfahren

45

komplexitätstheoretischer Fragen wie etwa des berühmten P  NP-Problems offen ist. Dagegen gibt es eine ganze Reihe praktikabler Kryptosysteme, die als nachweisbar sicher oder praktisch sicher gelten. Zunächst wollen wir uns jedoch mit de Bedingung für absolute Sicherheit etwas näher beschäftigen. Wegen   
  
  ist




(Satz von Bayes) und daher ist die Bedingung 
.


 gleichbedeutend mit

       ein Kryptosystem mit
       , 

       und                          Weiter sei  
 ,  
 
 
 , sowie  
 ,  
  und  
 
 . Dann ergibt sich folgende Verteilung auf :  
           
   
            
   
           
   
           
  Die bedingten Wahrscheinlichkeiten    berechnen sich wie folgt:   
     
    
    
     
    
    
     
    
    
     
    
  Wegen  

 
   ist das System unter dieser Verteilung nicht Beispiel 65 Sei        ,

absolut sicher.

Die Bedingung 
  ist nach dem Satz von Bayes genau dann erfüllt, wenn 
 ist. Da jedoch für jedes Paar   genau ein Schlüssel 
    mit   
 existiert, also  
  ist, ist dies äquivalent zu  
 . Für 
 bedeutet dies, dass alle Schlüssel  
  die gleiche Wahrscheinlichkeit  
  haben müssen. Eine leichte Rechnung zeigt, dass unter dieser Schlüsselverteilung  
  für 
      ist. Somit ist das Kryptosystem genau dann absolut sicher, wenn der Schlüssel unter Gleichverteilung gewählt wird (dies gilt unabhängig von der Klartextverteilung).

46

1 Klassische Verfahren

Verwendet man beim One-Time-Pad nur Klartexte einer festen Länge , d. h. 
 , so ist dieser absolut sicher (vorausgesetzt, der Schlüssel wird rein zufällig, also unter Gleichverteilung gewählt). Bezeichne   den (eindeutig bestimmten) Schlüssel, der den Klartext  auf den Kryptotext  abbildet. Wegen 

 und  


 für alle    folgt zunächst für jeden Klartext  und Kryptotext 


und damit





 


 

   
 



     

 


Variiert die Klartextlänge, so kann ein Gegner aus  nur die Länge des zugehörigen Klartextes  ableiten. Wird jedoch derselbe Schlüssel  zweimal verwendet, so kann aus den Kryptotexten die Differenz der zugehörigen Klartexte ermittelt werden:


   
  
   
 











 

Sind die Klartexte natürlichsprachig, so können aus    die beiden Nachrichten  und  ähnlich wie bei der Analyse einer Lauftextverschlüsselung (siehe Abschnitt 1.13) rekonstruiert werden. Da jeder Schlüsselbuchstabe beim One-Time-Pad nur einmal verwendet werden darf, ist der Aufwand extrem hoch. Zunächst muss ein genügend langer Schlüsselstrom  durch einen Zufallsgenerator erzeugt werden, welcher dann auf einem sicheren Kanal zwischen den Kommunikationspartnern ausgetauscht werden muss. Wird keine absolute Sicherheit angestrebt, so kann der Schlüsselstrom auch von einem PseudoZufallsgenerator erzeugt werden. Dieser erhält als Eingabe eine Zufallsfolge *
(den sogenannten Keim) und erzeugt daraus eine lange Folge 1
1    von PseudoZufallszahlen. Als Schlüssel muss jetzt nur noch das Wort *
ausgetauscht werden. In der Informationstheorie wird die Unsicherheit, mit der eine durch + beschriebene Quelle ihre Nachrichten aussendet, nach ihrer Entropie bemessen. Das heißt, die Unsicherheit über + entspricht genau dem Informationsgewinn, der sich aus der Beobachtung der Quelle + ziehen lässt. Dabei wird die in einer einzelnen Nachricht (message )  steckende Information um so höher bemessen, je seltener  auftritt. Tritt eine Nachricht  mit einer positiven Wahrscheinlichkeit 
 "+
#  auf, dann ist Inf 
    


der Informationsgehalt von . Ist dagegen 
, so sei Inf  
. Dieser Wert des Informationsgehalts ergibt sich zwangsläufig aus den beiden folgenden Forderungen: – Der gemeinsame Informationsgehalt Inf     von zwei Nachrichten  und  , die aus stochastisch unabhängigen Quellen + und - stammen, sollte gleich Inf  Inf   sein;

1 Klassische Verfahren

47

– der Informationsgehalt einer Nachricht, die mit Wahrscheinlichkeit soll genau 1 (bit) betragen.



auftritt,

Die Entropie von + ist nun der erwartete Informationsgehalt einer von + stammenden Nachricht. Definition 66

(Entropie)

Sei + eine Zufallsvariable mit Wertebereich 2 + 
         und sei 
 "+
 #. Dann ist die Entropie von + definiert als

' + 


  

 Inf  

Die Entropie nimmt also im Fall  
   
  den Wert    an. Für jede andere Verteilung         gilt dagegen ' +  %    (Beweis später). Generell ist die Unsicherheit über + um so kleiner, je ungleichmäßiger + verteilt ist. Bringt + nur einen einzigen Wert mit positiver Wahrscheinlichkeit hervor, dann (und nur dann) nimmt ' +  den Wert an. Eine wichtige Eigenschaft der Entropie ist, dass sie eine untere Schranke für die mittlere Codewortlänge von Binärcodes bildet. Ein Binärcode für + ist eine (geordnete) Menge
        von binären Codewörtern   für die Nachrichten   mit der Eigenschaft, dass die Abbildung        mit      
     injektiv ist. Die mittlere Codewortlänge von unter + ist

. 


  

   

heißt optimal, wenn kein anderer Binärcode für + eine kürzere mittlere Codewortlänge besitzt. Für einen optimalen Binärcode für + gilt ' +   .  % ' +   Beispiel 67 (Entropie) Sei + eine Zufallsvariable mit der Verteilung

 

sonnig leicht bewölkt bewölkt stark bewölkt Regen Schnee Nebel 









 

 

Dann ergibt sich die Entropie von + zu

' + 
               
  Betrachten wir die beiden Codes 
¼¼½ ¼½¼ ¼½½ ½¼¼ ½¼½ ½½¼ ½½½ und 
¼¼ ¼½ ½¼¼ ½¼½ ½½¼ ½½½¼ ½½½½, so erhalten wir für die mittlere Codewortlänge von  den Wert .  
, während  wegen  
      den Wert .  
' +  erreicht und somit optimal ist.

48

1 Klassische Verfahren

Die Redundanz eines Codes für eine Zufallsvariable + ist um so höher, je größer seine mittlere Codewortlänge im Vergleich zur Entropie von + ist. Um auch Codes über unterschiedlichen Alphabeten miteinander vergleichen zu können, ist es notwendig, die Codewortlänge in einer festen Einheit anzugeben. Hierzu berechnet man die Bitlänge eines Wortes  über einem Alphabet
mit   Buchstaben zu  
   . Beispielsweise ist die Bitlänge von GOLD (über dem lateinischen Alphabet) GOLD 
    
 . Entsprechend berechnet sich für einen Code
         unter einer Verteilung         die mittlere Codewortlänge (in bit) zu

.  


  

    

Damit können wir die Redundanz eines Codes als den mittleren Anteil der Codewortbuchstaben definieren, die keine Information tragen. Definition 68 (Redundanz) Die (relative) Redundanz eines Codes für + ist definiert als

 


.  ' +   .  

Beispiel 67 (Entropie, Fortsetzung) Während eine von + generierte Nachricht im Durchschnitt ' + 
  bit an Information enthält, haben die Codewörter von  eine Bitlänge von 3. Der Anteil an „überflüssigen“ Zeichen pro Codewort beträgt also

  
wogegen  keine Redundanz besitzt.

  
  & 

Auch Schriftsprachen wie Deutsch oder Englisch und Programmiersprachen wie C oder PASCAL können als eine Art Code aufgefasst werden. Um die statistischen Eigenschaften einer solchen Sprache . zu erforschen, erweist es sich als zweckmäßig, die Textstücke der Länge  (-Gramme) von . für unterschiedliche  getrennt voneinander zu betrachten. Sei also .  die Zufallsvariable, die die Verteilung aller -Gramme in . beschreibt. Interpretieren wir diese -Gramme als Codewörter einer einheitlichen Codewortlänge , so ist

. 


    ' .     

die Redundanz dieses Codes. Es ist zu erwarten, dass eine Sprache umso mehr Redundanz aufweist, je restriktiver die Gesetzmäßigkeiten sind, unter denen in ihr Worte und Sätze gebildet werden. Definition 69 (Entropie einer Sprache) Für eine Sprache . über einem Alphabet
mit 

 und -GrammVerteilung . ist ' .   die Entropie von . (pro Buchstabe). Falls dieser Wert für  gegen  gegen einen Grenzwert

' .
  ' . 

1 Klassische Verfahren

49

konvergiert, so wird dieser Grenzwert als die Entropie von . bezeichnet. In diesem Fall konvergiert .   gegen den Grenzwert

'  .

  . 
    

der als die Redundanz . von . bezeichnet wird. Für eine Reihe von natürlichen Sprachen wurden die Redundanzen .   der Gramme (für nicht allzu große Werte von ) empirisch bestimmt, so dass sich . näherungsweise bestimmen lässt. Beispiel 70 Im Englischen haben die Einzelbuchstaben eine Entropie von ' .   = 4,19, während sich für die Bigramme ein Entropiewert von ' .  /2 = 3,9 bit pro Buchstabe ergibt. Mit wachsender Länge sinkt die Entropie von englischsprachigen Texten weiter ab und strebt gegen einen Grenzwert ' . von 1 bis 1,5 bit pro Buchstabe. Für die Redundanz . ergibt sich hieraus (wegen log(26) = 4,76) ein Wert zwischen 68% und 79%, so dass sich ein englischer Text bei optimaler Kodierung auf circa   bis   seiner Länge komprimieren lässt. Wir betrachten nun den Fall, dass mit einem Kryptosystem Klartexte der Länge  verschlüsselt werden, ohne dass dabei der Schlüssel gewechselt wird. D. h.

   
  

wobei  die Menge der zugehörigen Kryptotexte ist. Der Einfachheit halber nehmen wir   

 
 an. Ist  ein abgefangener Kryptotext, so ist

 
     
    
     die Menge aller in Frage kommenden Schlüssel für  .    besteht aus einem „echten“ (d. h. dem zur Generierung von  tatsächlich benutzten) und     so genannten „unechten“ Schlüsseln.

Offenbar ist das Kryptosystem um so sicherer, je größer die erwartete Anzahl

*'






    






    

unechter Schlüssel ist. Definition 71

(Eindeutigkeitsdistanz)

Die Eindeutigkeitsdistanz 
eines Kryptosystems ist der kleinste Wert von , für den *'
wird.

Verfügt ein Gegner über unbegrenzte Rechenressourcen, so ist er bei Kenntnis eines Kryptotexts der Mindestlänge 
prinzipiell in der Lage, den verwendeten Schlüssel zu berechnen.

50

1 Klassische Verfahren

Als nächstes wollen wir eine möglichst gute Abschätzung für 
herleiten. Hierzu benötigen wir den Begriff der bedingten Entropie ' + - , die sozusagen die durchschnittliche „Restentropie“ von + misst, wenn der Wert von - bereits bekannt ist. Definition 72 (bedingte Entropie) Seien + - Zufallsvariablen. Dann ist die bedingte Entropie von + unter - definiert als

' + - 




  

  ' + 

wobei +  die Zufallsvariable mit der Verteilung   "+ 
#

 "+
  -
# ist (d.h. ' + 
         ). Als weiteres Hilfsmittel aus der Analysis benötigen wir die Jensensche Ungleichung, mit der sich obere Schranken für die Entropie von Zufallsvariablen herleiten lassen. Definition 73

(konkav)

Eine reellwertige Funktion  ist konkav auf einem Intervall , , falls für alle

   , gilt:

 

    Gilt sogar „“ anstelle von „“, so heißt  streng konkav auf , . 





Satz 74 (Jensensche Ungleichung) Sei  eine streng konkave Funktion auf , und sei en           reelle Zahlen mit  
. Dann gilt



  

   





  



  

Die beiden Seiten der Ungleichung sind genau dann gleich, wenn  


  
 ist.

Beispiel 75 Die Funktion  
   ist konkav auf   . Satz 76 Sei + eine Zufallsvariable mit Wertebereich 2 + 
         und Verteilung  "+
 #
 , 
     . Dann gilt ' +     , wobei Gleichheit genau im Fall  
  für 
      eintritt. Beweis: Es gilt

' + 


 

             
   

1 Klassische Verfahren

51

Nach obigem Satz tritt Gleichheit genau im Fall 
  für 
      gleichbedeutend ist. Satz 77

 





  ein, was mit

' + - 
' -  ' + - .

Beweis: Dies folgt direkt aus den Definitionen unter Verwendung von

' + - 
























 

 

 

 

 



 
. 

                      

 

   

   


' -  ' + - 

 

 

   



  ' +  

Satz 78 ' + -   ' +  ' - , wobei Gleichheit genau dann eintritt, wenn und - stochastisch unabhängig sind.

+ 

Beweis: s. Übungen.

Korollar 79 ' + -   ' + , wobei Gleichheit genau dann eintritt, wenn + und stochastisch unabhängig sind. Satz 80 In jedem Kryptosystem gilt für die Klartextentropie ' + , die Schlüsselentropie '   und die Kryptotextentropie ' - 

'  - 
'   ' +  ' -  Beweis: Zunächst ist '  - 
'  -  ' - . Es reicht also zu zeigen, dass

'  - 
'   ' +  ist. Da bei Kenntnis des Schlüssels der Wert von + bereits eindeutig durch - und der Wert von - eindeutig durch + festgelegt ist, folgt unter Berücksichtigung der gemachten Annahme, dass + und  unabhängig sind, '  - 
'  + - 
'  + 
'   ' +  

52

1 Klassische Verfahren

Jetzt verfügen wir über alle Hilfsmittel, um die erwartete Anzahl

*'






    

unechter Schlüssel nach unten abschätzen zu können. Seien +  und - die Zufallsvariablen, die die Verteilungen der -Gramme der Klartextsprache und der zugehörigen Kryptotexte beschreiben. Mit Satz 80 folgt

'  - 
'   ' +  ' -  Die Klartextentropie ' +   lässt sich für genügend große Werte von  durch ' +   ' .
 /.    approximieren, wobei 

 ist. Zudem lässt sich die Kryptotextentropie ' -   wegen 2 - 
 und   
 durch ' -       abschätzen. Somit ist

'  -  '   /.    Andererseits gilt (unter Verwendung der Jensenschen Ungleichung)

'  - 
 









 

  '        



   


  '*  Zusammen ergibt sich also

  '*   '   /.    Im Fall, dass der Schlüssel unter Gleichverteilung gezogen wird, erreicht '   den maximalen Wert    , was auf die gesuchte Abschätzung für *' führt. Wir fassen zusammen. Satz 81 Werden mit einem Kryptosystem Klartexte  
 der Länge  mit einem unter Gleichverteilung gezogenen Schlüssel    verschlüsselt, und ist   

 
 für den zugehörigen Kryptotextraum 
        
 , so gilt für die erwartete Anzahl *' der unechten Schlüssel,

   *'  



1 Klassische Verfahren

53

Setzen wir in obiger Abschätzung *'
, so erhalten wir folgenden Schätzwert für die Eindeutigkeitsdistanz 
des Kryptosystems:

        
 /
.     ' . 



Die Differenz    ' . wird auch als absolute Redundanz /   . der Klartextsprache bezeichnet (d.h. es gilt 
     /  .). Beispiel 82 Für Transpositionen bei englischsprachigem Klartext ergeben sich die folgenden Schätzwerte für die Eindeutigkeitsdistanz 
(wobei wir /  .
 annehmen, was einer relativen Redundanz von /.
    & entspricht): Kryptosystem Verschiebechiffre Affine Chiffre einfache Substitution Vigenère-Chiffre DES-Algorithmus

Schlüsselanzahl  

   
   

          

 




       





Dagegen erhalten wir für Blocktranspositionen folgende Schätzwerte für die Menge an Kryptotext, die zur eindeutigen Bestimmung des Schlüssels benötigt wird:

Analyse auf Basis von -Grammen (  $) Trigrammen Bigrammen (' . 
 ) Einzelzeichen (' . 
 )

10 7 24 40 

20 19 65 111 

Blocklänge $ 50 100 67 164 226 553 390 954  

1 000 2 665 9 473 15 502 

Auch wenn der Schätzwert für 
bei der Analyse auf Basis von Einzelzeichen einen kleineren Wert ergeben würde, wissen wir, dass eine solche Analyse nicht zum Ziel führen kann, und zwar unabhängig davon, über wie viel Kryptotext der Gegner verfügt.

54

2 Symmetrische Kryptosysteme

2 Symmetrische Kryptosysteme 2.1 Produktchiffren Produktchiffren erhält man durch die sequentielle Anwendung mehrerer Verschlüsselungsverfahren. Sie können extrem schwer zu brechen sein, auch wenn die einzelnen Komponenten leicht zu brechen sind. Definition 83

(Produktkryptosystem)

Seien 
           und 
           Kryptosysteme mit 
 . Dann ist das Produktkryptosystem von  und

 definiert als   
           mit

     
       und     
       für alle    ,    und         . Der Schlüsselraum von    umfasst also alle Paare     von Schlüsseln    und    , wobei wir voraussetzen, dass die Schlüssel unabhängig gewählt werden (d.h. es gilt    
  ). Beispiel 84 Sei


     

 . Man sieht leicht, dass die affine Chiffre
      mit

! und 




das Produkt
   der multiplikativen Chiffre 
         mit der additiven Chiffre 
         ist, da für jeden Schlüssel 
     




gilt:   
  
       Für 
   erhalten wir das Kryptosystem 
           mit  




und       
   
   
       für jeden Schlüssel        . Da die Abbildung           eine Bijektion zwischen den Schlüsselräumen   und  ist und die Schlüssel unter Gleichverteilung gewählt werden, sind die Kryptosysteme
   und


   als gleich (besser: äquivalent, siehe übungen) anzusehen, d.h.  und  kommutieren. # Definition 85

(endomorph, idempotent)

Ein Kryptosystem
       mit
heißt endomorph. Ein endomorphes Kryptosystem heißt idempotent, falls 
ist.

2 Symmetrische Kryptosysteme

55

Beispiel 86 Eine leichte Rechnung zeigt, dass die additive, die multiplikative und die affine Chiffre idempotent sind. Ebenso die Blocktransposition sowie die Vigenère- und Hill-Chiffre. Will man durch mehrmalige Anwendung (Iteration) derselben Chiffriermethode eine höhere Sicherheit erreichen, so darf diese nicht idempotent sein. Man kann beispielsweise versuchen, ein nicht idempotentes System durch die Kombination
   zweier idempotenter Verfahren  und  zu erhalten. Wegen

          





        

                   

  

dürfen hierbei  und  jedoch nicht kommutieren.

Im Rest dieses Kapitels werden wir nur noch das Binäralphabet

   als Klar- und Kryptotextalphabet benutzen und auch der Schlüsselraum wird von der Form    sein, wobei  die Schlüssellänge bezeichnet. Eine iterierte Blockchiffre wird typischerweise durch eine Rundenfunktion (round function )  und einen Schlüsselgenerator (key schedule algorithm )  beschrieben. Ist 3 die Rundenzahl, so erzeugt  bei Eingabe eines Schlüssels  eine Folge   
         von 3 Rundenschlüsseln   für . Mit diesen wird ein Klartext 
&
durch 3 -malige Anwendung der Rundenfunktion  zu einem Kryptotext 
& verschlüsselt:

&     &
 .. .

  

&

 &
 

Um  wieder zu entschlüsseln, muss die inverse Rundenfunktion 
 mit umgekehrter Rundenschlüsselfolge         benutzt werden:

&
  
   &  .. .

&
 
    &  Beispiele für iterierte Chiffren sind der aus 16 Runden bestehende DES-Algorithmus und der AES mit einer variablen Rundenzahl 3      , die wir in späteren Abschnitten behandeln werden.

56

2 Symmetrische Kryptosysteme

2.2 Substitutions-Permutations-Netzwerke In diesem Abschnitt betrachten wir den prinzipiellen Aufbau von iterierten Blockchiffren. Als Basisbausteine für die Rundenfunktion eignen sich Substitutionen und Transpositionen besonders gut. Aus Effizienzgründen sollten die Substitutionen nur eine relativ kleine Blocklänge $ haben. Definition 87 (Teilwort) Für ein Wort 4
4    4     und Indizes        bezeichne 4"  # das Teilwort 4     4 von 4. Im Fall 
$ bezeichnen wir das Teilwort 4" $  $# auch einfach mit 4  , d.h. es gilt 4
4    4
, wobei 4 
$.

(! 
 
 eine Substitution, die Binärblöcke 4 der Länge $ in Binärblöcke 1
(! 4 der Länge $  überführt (engl. auch als S-Box bezeichnet). Sei

¼


 

S-Box

 
   

Durch parallele Anwendung von  dieser S-Boxen erhalten wir folgende Substitution




¼
,

4    

(! 4     (! 4
 

Um eine S-Box (!         durch Software zu implementieren, werden $  bit Speicherplatz benötigt (im Fall $
$  also $  bit). Für $
$
 wären dies beispielsweise 
bit, was bereits Smartcard-Anwendungen ausschließen würde. ¼

Für eine Permutation ( "       $      $ bezeichnen wir die zugehörige Transposition auf

mit 5 ,

5 4    

4     4 
 

Definition 88 (Substitutions-Permutations-Netzwerk) Sei

   und sei



für natürliche Zahlen $   . Ein Substitutions-Permutations-Netzwerk (SPN) wird durch Permutationen (!         und ("       $       $ sowie durch einen Schlüsselgenerator          
  beschrieben. Der Generator  erzeugt aus einem (externen) Schlüssel       eine Folge   
          von 3  Rundenschlüsseln  , unter denen ein Klartext      
gemäß folgendem Algorithmus in einen Kryptotext 
#       
überführt wird:

2 Symmetrische Kryptosysteme

Algorithmus 89

57

#   

1 &
  2 for    to 3  do 3 4  &
   4 1  4  5 &  5 1  6 end 7 4  &
   8 1  4  9   1   

Zu Beginn jeder Runde        3  wird &
 zunächst einer XOR-Operation mit dem Rundenschlüssel  unterworfen (dies wird round key mixing genannt), deren Resultat 4 den S-Boxen zugeführt wird. Auf die Ausgabe 1 der S-Boxen wird in jeder Runde   3  die Transposition 5 angewendet, was die Eingabe & für die nächste Runde   liefert. Am Ende der letzten Runde 
3 wird nicht die Transposition 5 angewandt, sondern der Rundenschlüssel   auf 1 addiert. Durch diese (whitening genannte) Vorgehensweise wird einerseits erreicht, dass auch für den letzten Chiffrierschritt der Schlüssel benötigt und somit der Gegner von einer partiellen Entschlüsselung des Kryptotexts abgehalten wird. Zum Zweiten ermöglicht dies eine (legale) Entschlüsselung nach fast demselben Verfahren (siehe übungen).

Beispiel 90 Sei $

3
 und sei 
 . Für  wählen wir die Funktion   
          mit 
 "     #. Weiter seien (!         und ("              die folgenden Permutationen (wobei die Argumente und Werte von ( ! hexadezimal dargestellt sind; siehe auch Abbildung 1):

        
  6 (!      6   
    und

                ("                  Für den Schlüssel 
          liefert  beispielsweise die Rundenschlüssel   
          mit  
        
        
        
      
    

58

2 Symmetrische Kryptosysteme

 

 
























 
















 






 

 




  

Abbildung 1 Ein Substitutions-Permutations-Netzwerk.

2 Symmetrische Kryptosysteme

unter denen der Klartext durchläuft:

59


     die folgenden Chiffrierschritte


    
&
&
  
   
4

4
     
1 5 1 
  
& .. .

5 1 
   
& &   
     
4

4
     
1 4   
     
 

2.3 Lineare Kryptoanalyse von SPNs Zuerst stellen wir eine Reihe von Ergebnissen aus der Wahrscheinlichkeitstheorie bereit. Für eine Zufallsvariable + mit Wertebereich 2 + 
   und 
 "+
# bezeichne 7+  den Wert 7+ 
   (auch bias von + genannt). Sind +   + unabhängige Zufallsvariablen mit Wertebereich 2 +  
   und bias 7
7+ , dann ist 

"+  +
#
 "+
+
#  "+
+
#
   7    7     7    7 
  7 7

und

"+  +
#
 "+
 +
#  "+
 +
#
   7    7     7    7 
  77  d.h. es gilt 7+  + 
7 7 . 

Diese Beobachtung lässt sich leicht verallgemeinern. Lemma 91 (Piling-up lemma) Seien

2 + 
  . Dann gilt

+      + unabhängige Zufallsvariablen mit

7+      + 







7+ 

Beweis: Wir führen den Beweis durch Induktion über . Induktionsanfang (
): Klar.

60

2 Symmetrische Kryptosysteme




Induktionsschritt (  ): Seien +       + unabhängige Zufallsvariablen mit 2 + 
   und gelte nach IV  "+       +
#
 


  7 , wobei 7
7+  ist. Dann folgt



"+      +
#  "+      +
#   "+
#

 "+      +
#   "+
#  




   
 7    7     
 7    7 






 


   7 



 Beispiel 92 Seien +  +  + Zufallsvariablen mit 7+ 
  für 
  . Dann gilt nach obigem Lemma 7 
7+  + 
  für    %   . Man beachte, dass die Zufallsvariablen +   + und +  + nicht unabhängig sind, und daher das Piling-up lemma nicht anwendbar ist. Dieses würde nämlich für die Zufallsvariable

+  +   +  + 
+  + einen bias von 7
  
  ergeben, was dem tatsächlichen Wert 7+   + 
7
  widersprechen würde. Lineare Approximation von S-Boxen Sei (!         eine S-Box. Geben wir eine zufällig unter Gleichverteilung gewählte Eingabe 8
8     8 in (! ein, so erfüllt die zugehörige Ausgabe 9
9    9¼ für jeden Eingabevektor 4      und jeden Ausgabevektor 1     ¼ die Gleichung ¼

Wegen  "8

  ( 4
1 !  "9
1  8
4#
sonst.


4#

 folgt


 ( 4
1 !  "9
1 8
4#
sonst.

Wäre (! linear, so ließe sich jede Zufallsvariable 9  in der Form

9
8      8   für geeignete Indizes     %    %   $ und eine Konstante      darstellen. Die Idee hinter der linearen Kryptoanalyse ist nun, Gleichungen der Form

9      9
8      8

¼



2 Symmetrische Kryptosysteme

61

zu finden, die mit großer WK gelten. Definieren wir für die Zufallsvariablen

      und     

¼

8
  8 und 9
  9  ¼

so sind wir also an solchen Werten für  und  interessiert, für die das Ereignis 9
8  (oder gleichbedeutend: 8  9 
) eine möglichst große Wahrscheinlichkeit besitzt. Dies bedeutet, dass die Zufallsvariable 8   9   einen möglichst großen bias 78  9   haben sollte, oder, da

78  9  
78  9  ist, dass der bias von 8   9 betragsmäßig möglichst groß sein sollte. 8   9 ist also eine um so bessere lineare Approximation an ( ! , je größer 78   9  ist. Beispiel 93 Betrachten wir die S-Box ( !         aus Beispiel 90, so nimmt die Zufallsvariable 8       8  9      9  jeden der folgenden Werte mit Wahrscheinlichkeit

  an:

8        

8        

8        

8        

9        

9        

9        

9        

8  8  9  9              

Um nun 78  9  zu berechnen, müssen wir nur die Anzahl .  der Zeilen bestimmen, für die 8
9 ist. Dann gilt  "8  9
#
 "8
9 #
.   und somit

7 
78  9 
.   
.    Für 
 und 
  gibt es z.B. . 
Zeilen (Zeile 5 und Zeile 10) mit 8
8  8
9
9  9 , d.h. 7 

 , wobei wir für  und  die Hexadezimalschreibweise benutzen. Die folgende Tabelle zeigt für alle Werte von  und

62

2 Symmetrische Kryptosysteme

 (hexadezimal dargestellt) die Anzahlen . .                                                   
.. .

6        

.. .


   

    

   

   

   

6    

       

Lineare Kryptoanalyse eines SPN Wir betrachten nun das SPN aus Beispiel 90 und führen eine lineare Kryptoanalyse durch. Dabei handelt es sich um einen Angriff bei bekanntem Klartext, d.h. es steht eine Menge von : Klartext-Kryptotext-Paaren    zur Verfügung, die alle mit dem gleichen unbekannten Schlüssel  erzeugt wurden.

Seien          die zu  gehörigen Rundenschlüssel. Das Ziel besteht zunächst einmal darin, eine lineare Approximation für die Abbildung   4  (wobei die Rundenschlüssel          benutzt werden) zu finden. Hierzu benutzen wir die beiden folgenden linearen Approximationen an die S-Box ( ! :

;
8  8  8  9 mit einem bias von 7 
.   
  
  und ; 
8  9  9 mit einem bias von 7 
.   
  

 . Konkret benutzen wir die lineare Approximation ; für die S-Box  , ;
8  8   8  9  und die lineare Approximation ;  für die S-Boxen  ,  ,  (siehe auch Abbildung 2), ;
8   9   9  ;
8   9   9  ;
8  9  9   Indem wir nun die linearen Approximationen ;       ; der S-Boxen  ,  ,  und

 „zusammen schalten“, erhalten wir für ein       die gesuchte lineare Approximation

+  +  +  8   8  8  8 
;  ;  ;  ;   von   4 . An dieser Stelle ergeben sich folgende drei Fragen.

(3)

2 Symmetrische Kryptosysteme

63

 

 
























 
















 






 

 




  

Abbildung 2 Eine lineare Approximation an ein Substitutions-Permutations-Netzwerk.

64

2 Symmetrische Kryptosysteme

1. Warum gilt ?   8 ? 2. Wie gut ist die lineare Approximation +   +  +  8   8  8 

3. Wie können wir mit ihrer Hilfe den Schlüssel bestimmen? Wir gehen zunächst auf Frage 2 ein. Wären die Zufallsvariablen ;       ; unabhängig, so würde uns das Piling-up lemma den Wert     
  für den bias von ;      ; liefern. Obwohl dies nicht der Fall ist, stellt sich in der Praxis heraus, dass sich der tatsächliche Wert 7
7;       ;  nicht zu sehr von dem “hypothetischen” Wert   unterscheidet, und somit   7+  +  +  8   8  8  8  

 

ist. Um Frage 1 zu beantworten, drücken wir die 8 -Variablen, die in ;       ; vorkommen, durch + -Variablen und 9 -Variablen sowie durch Schlüsselbits   aus:

8 8  8 8  8  8









+   +    +   2    
9     2    
9     2  
9   

 führt dies auf die Darstellung Mit 
             

+  +  +  9   9  9  9    von ;      ; . Jetzt müssen wir nur noch die verbliebenen 8  -Variablen und Schlüsselbits ersetzen:

9  9 9 9 

Mit 







9  -Variablen durch

8      8    8    8     


           führt dies schließlich auf die Darstellung ;      ;
+  +  +  8   8  8  8    

Nun kommen wir zu Frage 3. Wir wissen bereits, dass die Wahrscheinlichkeit, dass ein zufälliger Klartext + zu einem Zwischenresultat 8  mit

+  +  +  8   8  8  8 
führt, hoch oder niedrig ist.

(4)

2 Symmetrische Kryptosysteme

65

Gehen wir nun davon aus, dass eine repräsentative Auswahl von KlartextKryptotext-Paaren    darstellt, so wird die Anzahl der Paare    in , die  erfüllen, ebenfalls eine Mehrheit oder eine Minderheit in bilden. Man beachte, dass  und sich aus einem Kryptotext  die zugehörigen Werte für die Variablen 8  , 8 , 8
  8 unter Benutzung von ( ! leicht berechnen lassen, sofern die 8 Schlüsselbits in  und   bekannt sind.   Die Idee besteht nun darin, für jeden Subschlüssel-Kandidaten (engl. candidate subkey )      die Anzahl 0.  .  aller Paare    in zu bestimmen, .  . für     die Gleichung  bei Benützung des Schlüssel-Kandidaten .   .  erfüllen. Für den richtigen Kandidaten wird diese Anzahl ungefähr bei   "   liegen, wogegen bei Benutzung eines falschen Subschlüssels mit einer Anzahl von circa   zu rechnen ist. Ist : genügend groß, so lassen sich auf diese Weise 8 bit von   (und damit von  ) bestimmen. Algorithmus 94 L INEAR ATTACK  : ( !
  1 for .  .      to (F,F) do 0.  .   end 2 3 for each     do 4 for .  .      to 6 6  do  .  5 1   6 7 8

 .  1  
   4  (! 1    4  (!
 1 if       4  4  4  4
then 0.  .   0.  .   end

9 10 11 end 12 end 13    14 for .  .      to 6 6  do < .  .   0.  .    15 16 if < .  .    then 17   < .  .  18 =  .  .  end 19 end 20 Ausgabe: =

Im allgemeinen werden für eine erfolgreiche lineare Attacke circa :  7
 KlartextKryptotext-Paare benötigt, wobei  eine „kleine“ Konstante ist (im Beispielfall reichen :   Paare, d.h.   , da 7

  ist.

66

2 Symmetrische Kryptosysteme

2.4 Differentielle Kryptoanalyse von SPNs Bei der differentiellen Kryptoanalyse handelt es sich um einen Angriff bei frei wählbarem Klartext. Genauer gesagt, basiert der Angriff auf einer Menge von : KlartextKryptotext-Doppelpaaren         mit der Eigenschaft, dass alle Klartext-Paare    die gleiche Differenz 
   bilden. Definition 95

(Eingabe- und Ausgabedifferenz)

Seien       zwei Eingaben für eine S-Box ( !      ¼    und seien 
(!  und  
(!   die zugehörigen Ausgaben. Dann wird  
   die Eingabedifferenz (engl. input-x-or) und 
(!   (!   die Ausgabedifferenz (engl. output-x-or) des Paares    genannt. Für eine vorgegebene Eingabedifferenz       sei weiter

$ 
            
 
           die Menge aller Eingabepaare, die die Differenz   realisieren. Berechnen wir für alle Eingabepaare      $  die zugehörigen Ausgabedif¼ ferenzen, so verteilen sich diese mehr oder weniger gleichmäßig auf die  mögli¼  chen Werte in    . Je ungleichmäßiger die auftretenden Ausgabedifferenzen verteilt sind, je leichter lässt sich eine differentielle Kryptoanalyse durchführen. Man beachte, dass im Fall einer linearen S-Box nur die Ausgabedifferenz ( !   auftritt, da dann (!   (!  
(!     ist. Definition 96

(Differential, Weitergabequotient)

Sei      eine Eingabe- und sei       eine Ausgabedifferenz für eine S-Box ( ! . Dann heißt     Differential. Die Anzahl der Eingabepaare    , die die Eingabedifferenz   in die Ausgabedifferenz   überführen, bezeichnen wir mit     , d.h. ¼

   
    $   (!   (!  
  Der Weitergabequotient (engl. propagation ratio) von rential     ist

( ! für ein Diffe-

 

>   
    

>    ist also die (bedingte) Wk

"(!   (!  
    
 # dass zwei zufällig gewählte Eingaben die Ausgabedifferenz   erzeugen, wenn sie die Eingabedifferenz   bilden. 

2 Symmetrische Kryptosysteme

67

Beispiel 97 Betrachten wir die S-Box ( !         aus Beispiel 90, so erhalten wir für die Eingabedifferenz  
  die Menge

$ 
         

von möglichen Eingabepaaren, die auf folgende Ausgabedifferenzen (!   (!   führen:

 
  


                                                                                                         Die Ausgabedifferenz  
 kommt also .   
 Mal vor, während die Differenzen  , ,   und  je zwei Mal und die übrigen Werte überhaupt nicht vorkommen (siehe Zeile  in nachfolgender Tabelle). Führen wir diese Berechnungen für jede der 
 Eingabedifferenzen       aus, so erhalten wir die folgenden Werte für die Häufigkeiten .     der Ausgabedifferenz   bei Eingabedifferenz   ( und  sind hexadezimal dargestellt):           
  6         .. .

.. .

.. .

.. .

  6   Wie können wir nun die ungleichmäßige Verteilung der Ausgabedifferenzen zur Bestimmung von Schlüsselbits ausnützen? Eine erste Antwort auf diese Frage gibt die folgende Beobachtung.

68

2 Symmetrische Kryptosysteme

Beobachtung 98 Für die Eingabe 4  der S-Box  in Runde  gilt

4 
& 
       







S-Box 



Daher hängt die Eingabedifferenz

4   4  
& 
       & 
      
& 
   & 
   von  nicht von den Schlüsselbits in Runde  ab, wohl aber die Ausgabedifferenz 1   1  
(! & 
       (! & 
       Können wir nun in einem SPN für bestimmte S-Boxen  Differentiale     finden, so dass die Eingabedifferenz dieser Differentiale mit der (permutierten) Ausgabedifferenz der Differentiale in der jeweils vorhergehenden Runde übereinstimmt (siehe Abbildung 3), so können wir diese Differentiale zu einer so genannten Differentialspur (engl. differential trail) zusammen setzen. Könnten wir annehmen, dass die beteiligten S-Boxen  (diese werden auch als aktiv bezeichnet) die Differenzen unabhängig voneinander gemäß      weitergeben, so wäre der Weitergabequotient der Spur gleich dem Produkt der Weitergabequotienten aller beteiligten Differentiale. (Obwohl diese Annahme nicht richtig ist, bestätigt die Praxis die daraus abgeleitete Konsequenz). Beispiel 97 (Fortsetzung) Betrachten wir das SPN aus Beispiel 90, so lassen sich folgende Differentiale zu einer Spur für die Abbildung   4  kombinieren (siehe auch Abbildung 3): Für  : das Differential    
  mit > 


für für

 ,

    
  mit > 
  und     
   mit >  
 .

  : das Differential    und  : das Differential

Gemäß dieser Spur führt also eine Eingabedifferenz


 

2 Symmetrische Kryptosysteme

69

 

 
























 
















 






 

 




  

Abbildung 3 Eine Differentialspur für ein Substitutions-Permutations-Netzwerk.

70

2 Symmetrische Kryptosysteme

mit hypothetischer Wk

 
 
    auf die Differenz

  

1 
     welche wiederum mit Wk 1 auf die Differenz

4 
  führt. D.h. wir erhalten für die Abbildung   4  die Spur

   
       mit einem hypothetischen Weitergabequotienten von >    


 
.

Sei nun     eine Spur für die Abbildung   4  mit einem hypothetischen Weitergabequotienten >    
7. Weiter sei eine Menge von : Klartext-KryptotextDoppelpaaren        , die alle mit dem gleichen unbekannten Schlüssel  erzeugt wurden und zusätzlich die Eigenschaft haben, dass die Klartextdifferenz  
  
 ist. Dann wird ca. ein 7-Anteil dieser Doppelpaare der Spur      folgen und daher bei Verschlüsselung mit  Zwischenergebnisse 4  und 4  liefern, die die Differenz 4 
4  4 
 aufweisen. Doppelpaare mit dieser Eigenschaft werden richtige Doppelpaare (für die Spur    ) genannt. Beobachtung 99 Für die Ausgabe 1   der S-Box  in Runde 

1
   und die Eingabe 4  der S-Box  in Runde 3 ist

4
(!
  1 
(!
     

 S-Box 

 





  


3 gilt

2 Symmetrische Kryptosysteme

71

Ist  nichtlinear, so hängt die aus den Kryptotextblöcken   und   zurückgerechnete Eingabedifferenz

4 
4  4 
(!
       (!
     

von den Schlüsselbits in   ab. Ist also        ein richtiges Doppelpaar, so sind sowohl die Eingabedifferenz  
4  von  als auch die Kryptotextblöcke

 und  bekannt. Folglich kommen nur solche Subkey-Werte  für   in Frage, für die

(!
      (!
    


(5)

ist. Erfüllt  Gleichung (5), so sagen wir auch,  ist mit dem Doppelpaar         konsistent. Gemäß Beobachtung 99 kann jedes richtige Doppelpaar dazu benutzt werden, die in Frage kommenden Werte für bestimmte Blöcke des Rundenschlüssels   einzuschränken. Ist hinreichend groß, so wird sich schließlich der richtige Teilschlüssel als derjenige heraus kristallisieren, der mit den meisten Doppelpaaren konsistent ist. Wir benutzen nun die in Beispiel 97 gefundene Spur für einen Angriff mittels differentieller Analyse. Beispiel 97 (Fortsetzung) Wegen

4 
 1 
  
kann        nur dann ein richtiges Doppelpaar für die Spur      sein, wenn 

ist. Da falsche Doppelpaare nichts zur Bestimmung des Schlüssels   beitragen (im Wesentlichen erzeugen sie nur „Hintergrundrauschen“), werden sie am besten ausgefiltert (zumindest soweit sie als solche erkennbar sind).

In Algorithmus 97 wird nun für jeden Subschlüssel-Kandidaten .   .  für      die Anzahl ? .  .  aller Doppelpaare         in bestimmt,     die nicht als falsch erkannt werden und mit .   .  konsistent sind. Ausgegeben wird der Kandidat .  .  mit dem größten ? -Wert. Algorithmus 98 D IFFERENTIAL ATTACK  : ( !
 

1 for .  .      to (F,F) do ? .  .  end 2 3 for each         do  und 
 then 4 if 
  5 6 7 8

for .  .      to 6 6  do  .  1    .  1  
   4  (! 1 

72

2 Symmetrische Kryptosysteme

9 10 11 12 13 14 15 16

  4  (!
 1    .    1      .    1      4   (!
 1    4   (!
 1 4   4  4 4   4  4 if 4 
 und 4 
 then ? .  .   ? .  .  end

17 18 end end 19 end 20    21 for .  .      to 6 6  do 22 if ? .  .    then 23   ? .  .  24 =  .  . end 25 end 26 Ausgabe: =

Im allgemeinen werden für eine erfolgreiche differentielle Attacke circa :  7
 Klartext-Kryptotext-Doppelpaare benötigt, wobei 7 der Weitergabequotient der benutzten Spur und  eine „kleine“ Konstante ist (im Beispielfall reichen :   Doppelpaare, wobei 7
   ist).

2.5 Der Data Encryption Standard (DES) Der DES wurde von IBM im Zuge einer im Mai 1973 veröffentlichten Ausschreibung des NBS (National Bureau of Standards; heute National Institute of Standards and Technology, NIST) als ein Nachfolger von Lucifer entwickelt, im März 1975 veröffentlicht, und im Januar 1977 als Verschlüsselungsstandard der US-Regierung für nicht geheime Nachrichten genormt. Obwohl der DES ursprünglich nur für einen Zeitraum von 10 bis 15 Jahren als Standard dienen sollte, wurde er circa alle 5 Jahre (zuletzt im Januar 1999) überprüft und als Standard fortgeschrieben. Bereits im September 1997 veröffentlichte das NIST eine Ausschreibung für den AES (Advanced Encryption Standard) genannten Nachfolger des DES. Nach einer mehrjährigen Auswahlprozedur wurde im November 2001 der Rijndael-Algorithmus als AES genormt. Der DES ist eine Feistel-Chiffre mit 16 Runden. Die Rundenfunktion  einer FeistelChiffre berechnet das Zwischenergebnis &  aus den beiden Hälften . 
 und /
 von

2 Symmetrische Kryptosysteme

73

&
 gemäß der Vorschrift    .
 /
 
. /  wobei sich & 


. / zusammensetzt aus .
/
 und /
.
   /
     

 32





 

  

 

      32

32

 48

32

Der DES chiffriert Binärblöcke der Länge 64 und benutzt hierzu einen Schlüssel mit 56 Bit. Der Schlüssel ergibt zusammen mit 8 Paritätsbits (die Bits 8, 16,. . . , 64) einen ebenfalls 64 Bit langen Schlüsselblock  . Es gibt somit       verschiedene Schlüssel. Im Einzelnen werden folgende Chiffrierschritte ausgeführt:

1. Zuerst wird der Klartextblock  einer Initialpermutation ,5 unterzogen:

        ,5 
 
    

2. Danach wird 16 Mal die Rundenfunktion  mit den Rundenschlüsseln          angewendet, wobei die Funktion               wie folgt berechnet wird:

74

2 Symmetrische Kryptosysteme 32 1 2 3 4 5 4 5 6 7 8 9 8 9 10 11 12 13 12 13 14 15 16 17 16 17 18 19 20 21 20 21 22 23 24 25 24 25 26 27 28 29 28 29 30 31 32 1 Expansion 



    

32





  14

4 13 0 15 7 4 1 14 15 12 8

48

48












32

     



32





16 7 20 21 29 12 28 17 1 15 23 26 5 18 31 10 2 8 24 14 32 27 3 9 19 13 30 6 22 11 4 25

Permutation



2 15 11 8 3 10 6 12 5 9 14 2 13 1 10 6 12 11 9 5 13 6 2 11 15 12 9 7 3 10 4 9 1 7 5 11 3 14 10 0

  15

1 8 14 6 11 3 4 9 3 13 4 7 15 2 8 14 12 0 14 7 11 10 4 13 1 5 13 8 10 1 3 15 4 2 11

  10

    je 6 Bit                     je 4 Bit      48

1 4 8 2

0 9 14 13 7 0 9 13 6 4 9 1 10 13 0

6 3 8 6

7 0 8 6

2 13 12 1 10 6 12 6 9 7 12 0

0 9 3 5

0 3 5 6

7 8 0 13

5 10 11 5 2 15 14 9

3 15 5 1 13 12 7 11 4 2 8 4 6 10 2 8 5 14 12 11 15 1 15 3 0 11 1 2 12 5 10 14 7 9 8 7 4 15 14 3 11 5 2 12

 7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 15 13 8 11 5 6 15 0 3 4 7 2 12 1 10 14 9 10 6 9 0 12 11 7 13 15 1 3 14 5 2 8 4 3 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14

 2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 9 14 11 2 12 4 7 13 1 5 0 15 10 3 9 8 6 4 2 1 11 10 13 7 8 15 9 12 5 6 3 0 14 11 8 12 7 1 14 2 13 6 15 0 9 10 4 5 3

 12 1 10 15 9 2 6 8 0 13 3 4 14 7 5 11 10 15 4 2 7 12 9 5 6 1 13 14 0 11 3 8 9 14 15 5 2 8 12 3 7 0 4 10 1 13 11 6 4 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13

 4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 1 13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 6 1 4 11 13 12 3 7 14 10 15 6 8 0 5 9 2 6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12

  13

2 8 4 1 15 13 8 7 11 4 1 2 1 14 7

6 15 11 1 10 9 3 14 5 0 12 7 10 3 7 4 12 5 6 11 0 14 9 2 9 12 14 2 0 6 10 13 15 3 5 8 4 10 8 13 15 12 9 0 3 5 6 11

Substitutionsboxen

Bei Eingabe / 
     wird /
 durch die Expansionsabbildung  auf einen 48-Bit Block  /
  erweitert. Dieser wird mit   bitweise addiert (x-or); als Ergebnis erhält man den Vektor 
 / 
     . Danach wird  in acht 6-Bit Blöcke        aufgeteilt, die mittels 8 S-Boxen        auf 4-Bit Blöcke 
   reduziert werden. Die S-Boxen sind in Form einer Tabelle dargestellt, die wie folgt ausgewertet wird:

3.

Ist 
     , so findet man    in Zeile   und Spalte     (jeweils aufgefasst als Binärzahl) der Tabelle für  . Zum Beispiel ist     
 , da in Zeile  
und Spalte  
 der  -Tabelle die Zahl 
  eingetragen ist. Die Konkatenation der von den acht S-Boxen gelieferten Bitblöcke      ergibt einen 32-Bit Vektor , welcher noch der Permutation 5 unterworfen wird. Aus dem nach der 16. Iteration erhaltenen Bitvektor & 
. / wird durch Vertauschen der beiden Hälften und Anwendung der inversen Initialpermutation der Kryptotext  gebildet:

. /  
,5
 / .  Die Schlüsselgenerierung. Zuerst wählt die Funktion 5  (permuted choice 1) aus dem Schlüssel  die kryptographisch relevanten Bits aus und permutiert sie. Das erhaltene Ergebnis wird in zwei 28-Bit Blöcke unterteilt. Diese beiden Blöcke werden dann

2 Symmetrische Kryptosysteme

75

in 16 Runden jeweils zyklisch um ein oder zwei Bit verschoben (siehe dazu Tabelle . ). Schlüssel 



     

 

28



28




.. .

  .. .   

28



28

57 1 10 19 63 7 14 21

64

     

28



28




.. .

  .. .   

28

   

48

    

48

   

48

14 17 11 24 1 5 3 28 15 6 21 10 23 19 12 4 26 8 16 7 27 20 13 2 41 52 31 37 47 55 30 40 51 45 33 48 44 49 39 56 34 53 46 42 50 36 29 32 permuted choice 2 Iteration







28

49 41 33 25 17 9 58 50 42 34 26 18 2 59 51 43 35 27 11 3 60 52 44 36 55 47 39 31 23 15 62 54 46 38 30 22 6 61 53 45 37 29 13 5 28 20 12 4 permuted choice 1



1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Anzahl der Links-Shifts

  1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1

Aus den beiden Blöcken nach Runde  bestimmt die Funktion 5 (permuted choice 2) jeweils den Rundenschlüssel   durch Entfernen der 8 Bits an den Stellen 9, 18, 22, 25, 35, 38, 43 und 56 sowie einer Permutation der verbleibenden 48 Bits. Eigenschaften des DES. Der DES hat sich zwar weitgehend durchgesetzt, jedoch wurde er anfangs von manchen US-Behörden und -Banken nicht verwendet. Der Grund dafür liegt in folgenden Sicherheitsbedenken, die nach seiner Veröffentlichung im Jahre 1975 geäußert wurden: – Die 56-Bit Schlüssellänge bietet eventuell eine zu geringe Sicherheit gegen Ausprobieren aller Schlüssel bei einem Angriff mit bekanntem oder gewähltem Klartext. – Die Entwurfskriterien für die einzelnen Bestandteile, insbesondere für die Boxen, sind nicht veröffentlicht worden. Es wurde der Verdacht geäußert, dass der DES mit Hilfe von Falltürinformationen leicht zu brechen sei. – Kryptoanalytische Untersuchungen, die von IBM und der US National Security Agency (NSA) durchgeführt wurden, sind nicht veröffentlicht worden. Als jedoch Biham und Shamir Anfang der 90er Jahre das Konzept der differentiellen

76

2 Symmetrische Kryptosysteme

Kryptoanalyse veröffentlichten, gaben die Entwickler von DES bekannt, dass sie diese Angriffsmöglichkeit beim Entwurf von DES bereits kannten und speziell die S-Boxen entsprechend konzipiert hätten. Im Fall von DES ist die lineare Kryptoanalyse effizienter als die differentielle Kryptoanalyse. Da hierzu jedoch circa  Klartext-Kryptotext-Paare notwendig sind (deren Generierung bei einem von Matsui, dem Erfinder der linearen Kryptoanalyse, unternommenen Angriff bereits 40 Tage in Anspruch nahm), stellen diese Angriffe keine realistische Bedrohung dar. Dagegen wurde im Juli 1998 mit einer von der Electronic Frontier Foundation (EFF) für 250 000 Dollar gebauten Maschine namens “DES Cracker” eine vollständige Schlüsselsuche in circa 56 Stunden durchgeführt (was den Gewinn der von RSA Laboratory ausgeschriebenen “DES Challenge II-2” bedeutete). Und im Januar 1999 gewann Distributed.Net, eine weltweite Vereinigung von Computerfans, den mit 10 000 Dollar dotierten “DES Challenge III”. Durch den kombinierten Einsatz eines Supercomputer namens “Deep Crack” von EFF und 100 000 PCs, die weltweit über das Internet kommunizierten, wurden nur 22 Stunden und 15 Minuten benötigt, um den Schlüssel für ein Klartext-Kryptotextpaar mit dem Klartext „See you in Rome (second AES Conference, March 22-23, 1999)“ zu finden. Definition 100

(schwache Schlüssel)

Ein DES-Schlüssel  heißt schwach, falls alle durch ihn erzeugten Rundenschlüssel gleich sind (d.h. es gilt   . . . ,   =1). Es gibt vier schwache Schlüssel (siehe Übungen):

0101010101010101 FEFEFEFEFEFEFEFE 1F1F1F1F0E0E0E0E E0E0E0E0F1F1F1F1 und für sie gilt

DES DES 


Neben diesen schwachen Schlüsseln existieren noch sechs weitere sogenannte „semischwache“ Schlüsselpaare    , für die gilt (siehe Übungen) DES   DES 


2.6 Endliche Körper Wie wir bereits wissen, bildet
 für primes  einen endlichen Körper der Größe . Dieser Körper läßt sich für jede Zahl    zu einem Körper der Größe   erweitern. Da bis auf Isomorphie nur ein Körper dieser Größe existiert, wird er einfach mit   

2 Symmetrische Kryptosysteme

77

oder   bezeichnet. Um diesen Körper zu konstruieren, betrachten wir zunächst den Polynomring
"# über
. Definition 101

(Polynomring)

Sei  prim. Dann enthält
"# alle Polynome


       
in der Variablen  mit Koeffizienten   
, 
.  heißt Grad von  (kurz: =
).
"# bildet mit der üblichen Polynomaddition und Polynommultiplikation einen Ring.

Ein Polynom  teilt ein Polynom   (kurz:  ), falls ein Polynom  
"# existiert mit  
. Teilt  die Differenz     zweier Polynome, so schreiben wir hierfür

 
  und sagen,   ist kongruent zu   modulo . Weiterhin bezeichne     den bei der Polynomdivision von   durch  auftretenden Rest, also dasjenige Polynom  vom Grad =  % = , für das ein Polynom  
"# existiert mit  
 . Ähnlich wie beim Übergang von
zu

können wir für ein fest gewähltes Polynom  vom Grad =
 jedem Polynom  
"# mittels      eindeutig ein Polynom vom Grad höchstens   zuordnen. Auf diese Weise erhalten wir den Restklassenpolynomring
"#  aller Polynome vom Grad höchstens  , wobei die Addition und Multiplikation wie in
"#, gefolgt von einer Reduktion modulo , definiert ist. Und wie

ist
"#  genau dann ein Körper, wenn  keinen nichttrivialen Teiler besitzt. Definition 102

(irreduzibel)

Ein Polynom  
"# heißt irreduzibel, falls keine Polynome   
"# vom Grad = =   existieren mit 
    
"# vom Da für jede Zahl    ein irreduzibles Polynom 
 
 Grad  existiert, lässt sich auf diese Weise für jede Primzahlpotenz   ein Körper der Größe  konstruieren. Hierbei können wir jedes Körperelement 
 
    


78

2 Symmetrische Kryptosysteme

durch die Folge  
    
    seiner Koeffizienten darstellen. Im Fall 
ent
 
 spricht dann die Addition zweier Polynome 

  und 

  in   der bitweisen Addition modulo 2 (x-or),






    

    


    
 
    
 Die Multiplikation in   lässt sich wegen  
    auf die Addition und (wiederholte) Multiplikation mit dem Polynom 
 zurückführen. Wegen 
 
   
ist  
   

 
 

       
 

  
 d.h. die Multiplikation von  mit  entspricht einem Linksshift um eine Stelle, dem sich im Fall 

 noch die Addition von  
    
anschließt:        
    



    

 
    




 Beispiel 103 Sei 
und   
"# vom Grad ,


. Zunächst benötigen wir ein irreduzibles Polynom


      
 Da  im Fall 

den nichttrivialen Teiler 
 hat und im Fall  
nicht den Grad  hat, genügt es, die 4 Kandidaten  
   
    
    
    zu betrachten. Da nun aber

 
    und

   
  

ist, gibt es in
"# nur zwei irreduzible Polynome vom Grad :    . Nehmen wir bspw. 
  , so ist

   
 

  und 

2 Symmetrische Kryptosysteme

und in
"#

79

  


  , da   
   
      

ist. Wie das folgende Beispiel zeigt, lässt sich das multiplikative Inverse eines Polynoms 


in   mit dem erweiterten Euklidschen Algorithmus berechnen. Beispiel 104 Sei 
und seien 
      und 


   zwei Polynome. Dann können wir mit dem Euklidschen Algorithmus den (in Bezug auf den Grad) größten gemeinsamen Teiler   von  und  berechnen:

 
 
    

      
            
    

  
    

   
   

Es ist also  
 
. Der erweiterte Euklidsche Algorithmus berechnet nun Polynome   und   gemäß der Vorschrift  

     
  wobei 
 
 und 

 und

 

     
  wobei 
 
und 

 welche für 
     die Gleichung     
  erfüllen:     

   
     

 
  

  
    

   
     

    
     

             
 Aus der letzten Zeile können wir das multiplikative Inverse   
    von  modulo  ablesen. 2.7 Der Advanced Encryption Standard (AES) – Im September 1997 veröffentlichte das NIST eine Ausschreibung für den AES, in der eine Blocklänge von 128 Bit und variable Schlüssellängen von 128, 192 und 256 Bit gefordert wurden. Einreichungsschluss war der 15. Juni 1998.

80

2 Symmetrische Kryptosysteme

– Von den 21 Einreichungen erfüllten 15 die geforderten Kriterien. Diese stammten aus den Ländern Australien, Belgien, Costa Rica, Deutschland, Frankreich, Großbritannien, Israel, Japan, Korea, Norwegen sowie den USA und wurden auf der 1. AES-Konferenz am 20. August 1998 als AES-Kandidaten akzeptiert. – Im August 1999 wählte NIST auf der 2. AES-Konferenz in Rom die Finalisten MARS, RC6, Rijndael, Serpent und Twofish aus. – Im April 2000 wurde der Rijndael-Algorithmus auf der 3. AES-Konferenz zum Sieger erklärt und im November 2001 als AES genormt. Die wichtigsten Entscheidungskriterien waren – Sicherheit, – Kosten (Effizienz bei Software-, Hardware- und Smartcard-Implementationen) sowie – Algorithmen- und Implementations-Charakeristika (unter anderem Flexibilität und Einfachheit des Designs). Die Blocklänge und die Schlüssellänge können beim Rijndael unabhängig voneinander im Bereich 128, 192 oder 256 Bit gewählt werden. Die Rundenzahl 3 des Rijndael hängt wie folgt von der Blocklänge und der gewählten Schlüssellänge ab:

3    

    

   

   

Wir beschränken uns hier auf die Beschreibung des AES mit 128 Bit Blocklänge und 128 Bit Schlüssellänge. Im Einzelnen werden folgende Chiffrierschritte ausgeführt: A DD ROUND K EY 
 for i:= 1 downto 9 do S UB B YTES S HIFT ROWS M IX C OLUMNS A DD ROUND K EY    end S UB B YTES S HIFT ROWS A DD ROUND K EY  
 1. Zuerst wird der Klartextblock  einer Addition mit dem 128-Bit Rundenschlüssel 
unterworfen. Diese Operation wird mit A DD ROUND K EY bezeichnet.

2 Symmetrische Kryptosysteme

81

2. Danach werden  Runden ausgeführt, wobei in jeder Runde  eine Substitution namens S UB B YTES, eine Permutation namens S HIFT ROWS, eine lineare Substitution namens M IX C OLUMNS und eine A DD ROUND K EY Operation mit dem Rundenschlüssel   durchgeführt werden. 3. Es folgt Runde 10 mit den Operationen S UB B YTES, S HIFT ROWS und A DD ROUND K EY  
. Der Klartext (und alle daraus berechneten Zwischenergebnisse) werden in Form eines Arrays

*

*
*
*


*
 * * *

*
 * * *

*
 * * *

dargestellt, das wie folgt initialisiert wird:


  

   

  


   

Die Substitution S UB B YTES basiert auf einer 8-Bit S-Box ( SUBBYTES , die durch folgenden Algorithmus berechnet wird (die Indexrechnung in Zeile 8 erfolgt modulo 8). Algorithmus 105

(S

UB B YTES

    


1 Eingabe:     
 2   B INARY TO F IELD    
 3 if 
then 4   F IELD I NV  end 5     
 F IELD TO B INARY  6     
    7 for   to 7 do 8              end 9 Ausgabe:     


Die hierbei benutzten Funktionen sind wie folgt definiert: – F IELD I NV

       berechnet das multiplikative Inverse im Körper  

"#     , B INARY T O F IELD         berechnet aus der 8-Bit Koeffizienten

–

Darstellung das zugehörige Körperelement.

– F IELD T O B INARY RY T O F IELD .

       berechnet die Inverse der Funktion B INA -

82

2 Symmetrische Kryptosysteme

Beispiel 106 Wir berechnen ( SUBBYTES    . Die Funktion B INARY T O F IELD liefert das zugehörige Polynom


B INARY TO F IELD   
    Aus Beispiel 104 kennen wir bereits das multiplikative Inverse

   

von  in   . Die Funktion F IELD T O B INARY liefert die zugehörige KoeffizientenDarstellung F IELD T O B INARY   
   

Es folgt die Berechnung der Ausgabe     

   mittels




         

  
 
        
 
  
   
    oder hexadezimal dargestellt:

usw. Somit ist (SUBBYTES (SUBBYTES 53
ED.

Wir können die AES S-Box in Form einer   -Matrix angeben, wobei in Zeile + und Spalte - der Wert ( SUBBYTES +-  eingetragen ist:

+ 0 1 2 3 4 5 . . . F

0 63 CA B7 04 09 53

1 7C 82 FD C7 83 D1

2 77 C9 93 23 2C 00

3 7B 7D 26 C3 1A ED

4 F2 FA 36 18 1B 20

5 6B 59 3F 96 6E FC

6 6F 47 F7 05 5A B1

7 C5 F0 CC 9A A0 5B

8 30 AD 34 07 52 6A . . .

9 01 D4 A5 12 3B CB

A 67 A2 E5 80 D6 BE

B 2B AF F1 E2 B3 39

C FE 9C 71 EB 29 4A

D D7 A4 D8 27 E3 4C

E AB 72 31 B2 2F 58

F 76 C0 15 75 84 CF

8C A1 89 0D BF E6 42 68 41 99 2D 0F B0 54 BB 16

S HIFT ROWS ist eine  -Bit Permutation, die wie folgt definiert ist:

*

*
*
*


*
 * * *

*
 * * *

*
 * * *



*

* * *

*
 * * *


*
 * *
*

*
 *
* *

M IX C OLUMNS ist eine lineare 32-Bit Substitution, die auf den Spalten der Zwischenergebnisse operiert. Zu ihrer Berechnung wird folgende Funktion benutzt:

2 Symmetrische Kryptosysteme

83

– F IELD M ULT              führt die Multiplikation im Körper    aus. Algorithmus 107 M IX C OLUMNS
      

1 Eingabe: 
       2 for   to 3 do :  B INARY TO F IELD  end 3 4 4
 F IELD M ULT :
 F IELD M ULT  :  : : 5 4  F IELD M ULT :  F IELD M ULT  :  : :
6 4  F IELD M ULT :  F IELD M ULT  :  :
: 7 4  F IELD M ULT :  F IELD M ULT  :
 : : 8 for   to 3 do 9   F IELD TO B INARY4  end 10 Ausgabe: 
      

M IX C OLUMNS führt eine lineare Transformation in    aus, die sich auch wie folgt beschreiben lässt (hierbei benutzen wir die Koeffizientendarstellung der Polynome in  , etwa  für  ):




 

  

   



     




     

            





Besonders elegant lässt sich die Operation M IX C OLUMNS im Polynom Restklassenring   " #    beschreiben. Sei  

   das durch die Spalte 
       repräsentierte Polynom in diesem Ring und sei   das Polynom  
     . Dann ist M IX C OLUMNS  
   D.h., M IX C OLUMNS ist eine multiplikative Chiffre mit festem Schlüssel   im Ring  " #   . Da das Polynom    nicht irreduzibel in   " # ist, ist  " #    zwar kein Körper. Da jedoch   invertierbar im Ring   " #    ist, kann die Inverse zu M IX C OLUMNS mittels M IX C OLUMNS
  

    berechnet werden, wobei 
  
      ist. Die Schlüsselgenerierung. Beim 10-Runden AES mit Block- und Schlüssellänge

$

  werden 11 Rundenschlüssel 
      
der Länge 128 benutzt. Jedes   besteht also aus 16 Bytes bzw. 4 Worten mit jeweils 4 Bytes. Reihen wir die 11 Rundenschlüssel aneinander, so entsteht ein Array &" #     &"# von 44 Worten, die gemäß folgendem Algorithmus aus dem 128-Bit Schlüssel  berechnet werden.

84

2 Symmetrische Kryptosysteme

Algorithmus 108 K EY E XPANSION 

1 Eingabe: 
 " #     "# 2 / @"#   3 / @" #  4 / @"#   5 / @"#   6 / @"#   7 / @"#  8 / @"#   9 / @"#   10 / @"#   11 / @" #   12 for   to 3 do 13 &"#   "#  " #  " #  " # end 14 for    to 43 do 15 :=  &" # 16 if   then 17 :=  S UB WORD ROT WORD :=  / @" &"#  &" #  := end 18 19 Ausgabe: &" #     &"#

# end

Die hierbei benutzten Funktionen sind wie folgt definiert: – ROT W ORD                             führt eine zyklische Verschiebung der 4 Eingabebytes um ein Byte nach links durch: ROT W ORD 
      
      
 – S UB W ORD                             ersetzt jedes Eingabebyte   durch ( SUBBYTES  : S UB W ORD 
      


S UB B YTES
      
(S B 
 (S B   (S UB YTES

UB YTES

UB B YTES

  (S

UB B YTES

 

2.8 Betriebsarten von Blockchiffren Für den DES wurden vier verschiedene Betriebsarten vorgeschlagen, in denen grundsätzlich jede Blockchiffre  mit beliebiger Blocklänge $ betrieben werden kann. Bei den ersten beiden Betriebsarten (ECB und CBC) werden Kryptotextblöcke der Länge $

2 Symmetrische Kryptosysteme

85

übertragen. Mit einer Blockchiffre kann aber auch ein Stromsystem realisiert werden, mit dem sich Kryptotextblöcke einer beliebigen Länge :,   :  $, übertragen lassen (OFB und CFB).

ECB-Mode (electronic code book; elektronisches Codebuch): Die Binär-Nachricht  wird in 64-Bit Blöcke &  zerlegt. Der letzte Block &  wird, falls nötig, mit einer vorher vereinbarten Bitfolge aufgefüllt. Die Blöcke werden nacheinander mit demselben Schlüssel  einzeln verschlüsselt, übertragen und auf Empfängerseite mittels der zu  gehörigen Dechiffrierfunktion wieder entschlüsselt:






     

 









     

 










  Sender Empfänger   

 







Um zu verhindern, dass ein Eindringling den Kryptotext verändert, ohne dass der Empfänger dies bemerkt, wird jeder Kryptotextblock nicht nur von dem zugehörigen Klartextblock, sondern auch von allen vorausgehenden Blöcken abhängig gemacht.

CBC-Mode (cipher block chaining; Blockverkettung des Schlüsseltextes): Jeder Klartextblock & wird mit dem Kryptotextblock   &
  bitweise (modulo 2) addiert, bevor er verschlüsselt wird (zur Verschlüsselung von &  wird ein Initialisierungsvektor 1 verwendet:

86

2 Symmetrische Kryptosysteme 





Sender Empfänger







  

    

 















  

    

 







  

    

 

OFB-Mode (output feedback; Rückführung der Ausgabe): Die Binär-Nachricht  wird in :-Bit Blöcke (für festes ::   :  $) zerlegt. Die Chiffrierfunktion   dient zur Erzeugung einer pseudozufälligen Folge von :-Bit Blöcken, die bitweise (modulo 2) zu den entsprechenden Klartextblöcken addiert werden. Als Eingabe für die Chiffrierfunktion   dient ein Schieberegister, das anfangs mit einem Initialisierungsvektor ,9 geladen ist. Bei jeder Übertragung eines :-Bit Klartextblockes & erzeugt die Chiffrierfunktion   zunächst einen Ausgabevektor, von dem nur die ersten : Bits verwendet werden. Diese dienen sowohl zur Verschlüsselung von &  , als auch zur Modifikation des Eingaberegisters, in das sie von rechts geschoben werden:








64










Klartext







64

 64

   Sender Empfänger





64



Klartext

CFB-Mode (cipher feedback; Rückführung des Kryptotextes): Zur Erneuerung des Eingaberegisters wird nicht die   -Ausgabe, sondern der :-Bit Kryptotextblock verwendet:

2 Symmetrische Kryptosysteme








87

64












Klartext





64

 64

   Empfänger Sender





64



Klartext

88

3 Zahlentheoretische Grundlagen

3 Zahlentheoretische Grundlagen In diesem Abschnitt stellen wir die Hilfsmittel aus der Zahlentheorie bereit, die wir zum Verständnis der Public-Key Verfahren, die im nächsten Abschnitt vorgestellt werden, benötigen. Satz 109 (Euler-Fermat) Für alle  

gilt

$



Beweis: Sei


4      4$
  und  

beliebig. Wegen   4 


  4 für 
 
 


 folgt


  4        4$
. Dies impliziert $ 4
$  
 4
$
  $ 4 . Also muss $

 sein. 







Korollar 110 (Satz von Fermat) Ist  eine Primzahl und  eine natürliche Zahl, die nicht durch  teilbar ist, also  
, so ist 
  durch  teilbar:


  

3.1 Diskrete Logarithmen Nehmen wir ein beliebiges Element  aus

und betrachten die Folge 

,   ,  , . . . , so wissen wir nach dem Satz von Euler-Fermat, dass spätestens für " wieder 
 gilt. Definition 111


, =


(Ordnung)

Es sei    und

 
. Die Ordnung von  modulo  ist

(

=    


Für das folgende besonders interessant sind Elemente  aus

, die ganz

aufspannen. Definition 112

(Primitivwurzel/Erzeuger)

Eine Zahl  heißt Primitivwurzel modulo falls



            $

  ist.

 (oder Erzeuger von

),

Ein Element  

ist also genau dann ein Erzeuger, wenn (

" ist. Falls

einen Erzeuger besitzt, wird

auch zyklisch genannt. Da 
          

  eine Untergruppe von

ist, ist (
 für alle  

ein Teiler von ", d. h. " 
 . Allgemeiner gilt (siehe Übungen)









 

3 Zahlentheoretische Grundlagen

89

Satz 113 (Gauß) Genau für           %  )( ist

zyklisch. (Ohne Beweis) Wählen wir als Basis einen Erzeuger  von

, so ist die Exponentiation =   eine bijektive Abbildung von der Menge       "  auf

. Die zugehörige Umkehrabbildung spielt eine sehr wichtige Rolle in der Kryptographie. Definition 114

(Index/diskreter Logarithmus)

Sei  ein Erzeuger von

und  

. Dann heißt der eindeutig bestimmte Exponent =        "  mit




Index oder diskreter Logarithmus modulo =

 ).

 von  zur Basis  (kurz:

Während die diskrete Exponentialfunktion =   durch Wiederholtes Quadrieren und Multiplizieren (siehe nächsten Abschnitt) effizient berechnet werden kann, sind bis heute keine effizienten Verfahren zur Berechnung des diskreten Logarithmus bekannt. Beispiel 115

=


, 
.    

0 1 2 3 4 5 6 7 8 9 1 2 4 8 5 10 9 7 3 6

1 2 3 4 5 6 7 8 9 10 0 1 8 2 4 9 7 3 6 5

#

Die nächsten beiden Sätze benötigen wir zur Bestimmung der Anzahl aller Erzeuger von
, falls  prim ist. Satz 116 (Euler) Sei   , dann gilt

 


"


wobei die Summe über alle Teiler    von  läuft. Beweis: Mit " 
 



 
 ist

 
 ist " 
"
 und damit

 


"


#

 " 
. Wegen 


  




 " 
" 
 







90

3 Zahlentheoretische Grundlagen

Satz 117 (Lagrange) Sei  eine Primzahl und sei

   
. Dann hat die Polynomkongruenz

 
         
 
höchstens  verschiedene Lösungen modulo .





(6)

Beweis: Durch Induktion über  (es wird nur die Körpereigenschaft von
 benutzt).


: klar.  
: Angenommen, die Polynomkongruenz (6) habe   verschiedene Lösungen  , . . . ,  modulo . Mit   
 
 
   
    
         % 

%  
 
 

           
  %  folgt


    
              
    !      % Aus   
       und  

 folgt !   (für 
     ), was im Widerspruch zur Induktionsvoraussetzung steht, da das Polynom ! vom Grad   ist.  Satz 118 (Gauß) Ist  prim, so gibt es genau "  Erzeuger von
. Beweis: Für jeden Teiler  von "
  sei


 
  ( 
 Da die Menge 
 aus allen Erzeugern von
 gebildet wird, müssen wir  
 
"  zeigen. Zuerst überlegen wir uns, dass die Menge  für ein beliebiges    in der Menge   = 
 enthalten ist, woraus     " folgt. Jedes    erfüllt die Kongruenz    , die nach dem Satz von Lagrange (Satz 117) höchstens  verschiedene Lösungen modulo  besitzt. Da neben  auch  , . . . ,  Lösungen dieser Kongruenz sind, die alle modulo  verschieden sind, folgt

         .

3 Zahlentheoretische Grundlagen

91

Angenommen, es gibt ein  in  mit

= 
  . Dann folgt        , also (      %  (Widerspruch).

   

Da die Mengen  eine Partition von
 bilden, folgt mit Satz 116, dass






  
 


ist. Da aber, wie oben gezeigt,      
 
"  gelten. Satz 119 Sei  prim. Dann ist   teiler  von   gilt:






"

" ist, muss  
" und insbesondere




 genau dann ein Erzeuger, wenn für jeden Prim
&

 

Beweis: Falls  
 ein Erzeuger ist, so gilt 

  für alle Exponenten      } und somit auch für alle Exponenten = der Form    ,  prim.

=



Ist dagegen  
 kein Erzeuger, so ist (   %  , und da (  ein Teiler von   ist, existiert eine Zahl   mit   (  
 . Sei  ein beliebiger Primteiler von . Dann gilt


&   &     &  

 Folgender probabilistische Algorithmus berechnet einen Erzeuger Primteiler  von   bekannt sind.






, falls alle

Algorithmus 120 C OMPUTE G ENERATOR         

1 Eingabe: Primzahl , Primteiler         von   2 repeat 3 rate zufällig           4 until 
&

  für 
      5 Ausgabe: 

Da "       für hinreichend große  ist, findet der Algorithmus in jedem Schleifendurchlauf mit Wahrscheinlichkeit "          einen Erzeuger. Die erwartete Anzahl der Schleifendurchläufe ist also   .

3.2 Modulares Potenzieren Modulare Potenzen    lassen sich durch Wiederholtes Quadrieren und Multiplizieren in     =    Schritten berechnen (Zeitkomplexität   , wobei  die Länge der Eingabe in Binärdarstellung ist).

92

3 Zahlentheoretische Grundlagen



Dazu sei =

=   mit 
 =, d.h. die =  bilden die Dualdarstellung von =. Dann können wir den Exponenten = sukzessive mittels 

=
und 
 =  für 
       zu =
 berechnen. Der folgende Algorithmus berechnet nach diesem Schema in der Variablen  die Potenzen     für 
     . Algorithmus 121 M OD P OT =  1  2       3 for    to  do 4      5         6 end 7 return 

Beispiel 122 Sei 
 , =
 und Algorithmus    
:

   

= 
 
               


. Dann erhalten wir mit obigem

wobei 




  


=   

#

Alternativ können wir auch das Horner-Schema zur Berechnung von = benutzen: Sei 
=
 und sei 

 =
 für 
     , dann ist =

. Dies führt auf folgenden Algorithmus, der in der Variablen  die Potenzen  '   für 
     berechnet. Algorithmus 123 M OD P OT   =  1  2 for    downto do          3 4 end 5 return 

Beispiel 124 Mit diesem Algorithmus erhalten wir natürlich ebenfalls 
:

  

3 Zahlentheoretische Grundlagen

   

93

= 
'          

wobei 




 



=  
 

#

3.3 Quadratische Reste In diesem Abschnitt beschäftigen wir uns mit dem Problem, Lösungen für eine quadratische Kongruenzgleichung




(7)

zu bestimmen. Zunächst gehen wir der Frage nach, wie sich feststellen lässt, ob überhaupt Lösungen existieren. Definition 125

(Quadratischer (Nicht-)Rest, Legendre-Symbol)

Ein Element  

heißt quadratischer Rest modulo  (kurz:   ÉÊ
), falls ein  

existiert mit 
. Andernfalls heißt  quadratischer Nichtrest (kurz:   ÉÆÊ
). Sei   eine Primzahl und

 
. Dann heißt

$ 


       ÉÊ 




  ÉÆÊ

das Legendre-Symbol von  modulo . Die Kongruenzgleichung (7) besitzt also für ein  

genau dann eine Lösung, wenn   ÉÊ
ist. Wie das folgende Lemma zeigt, kann die Lösbarkeit von (7) für primes  effizient entschieden werden. Am Ende dieses Abschnitts werden wir noch eine andere Methode zur effizienten Berechnung des Legendre-Symbols kennenlernen. Lemma 126 Sei  
,   prim, und sei 
   für einen beliebigen Erzeuger  von
. Dann sind die folgenden drei Bedingungen äquivalent:

b)


  ,  ist gerade,

c)

  ÉÊ .

a)

Beweis:

94

3 Zahlentheoretische Grundlagen

  :

 für ein ungerades 
  . Dann ist 
  
 
  


 

Angenommen,  

      



   : Ist    für 
 gerade, so folgt     , also   ÉÊ .    : Sei   ÉÊ , d. h.    für ein  
. Dann folgt mit dem Satz von Fermat,  
   
   Satz 127 (Eulers Kriterium) Für alle  
,   prim, gilt

  
   

Beweis: Nach obigem Lemma reicht es zu zeigen, dass  
  " sein muss. Da jedoch die Kongruenz     nach dem Satz von Lagrange (Satz 117) nur die beiden Lösungen  und  hat, folgt dies aus der Tatsache, dass  
 Lösung dieser Kongruenz ist.  Korollar 128 Für alle   
,   prim, gilt a) b)


 


  



         
   .

     

  

Als weiteres Korollar aus Eulers Kriterium erhalten wir eine Methode, quadratische Kongruenzgleichungen im Fall    zu lösen. Für beliebige Primzahlen  ist kein effizienter, deterministischer Algorithmus bekannt. Es gibt jedoch einen probabilistischen Algorithmus von Adleman, Manders und Miller (1977). Korollar 129 Sei   prim, dann besitzt die quadratische Kongruenzgleichung    für jedes   ÉÊ genau zwei Lösungen. Im Fall    sind dies " (für 
  ) von denen genau eine ein quadratischer Rest ist. Beweis: Sei   ÉÊ , d. h. es existiert ein  
 mit   . Mit  ist auch  eine Lösung von    , die von  verschieden ist ( ist ungerade). Nach Lagrange (Satz 117) existieren keine weitere Lösungen. Sei nun   . Dann gilt

           









nach Korollar 128. Demnach ist genau eine der beiden Lösungen " ein quadratischer Rest. Schließlich liefert Eulers Kriterium für 
   Also folgt    .




  



3 Zahlentheoretische Grundlagen

95

Zum Schluss dieses Abschnitts erweitern wir das Legendre-Symbol zum JacobiSymbol und zeigen, wie auch dieses effizient berechnet werden kann. Definition 130

(Jacobi-Symbol)

Das Jacobi-Symbol ist für alle ungeraden    und  

durch

          %  

 





definiert, wobei       die Primfaktorzerlegung von  ist.

 


 für Man beachte, dass im Gegensatz zum Legendre-Symbol die Eigenschaft
 ein  

nicht unbedingt mit   ÉÊ
gleichbedeutend ist. Interessanterweise ist das Jacobi-Symbol auch ohne Kenntnis der Primfaktorzerlegung des Moduls effizient berechenbar. Der Algorithmus basiert auf den folgenden beiden Sätzen, die wir ohne Beweis angeben. Satz 131 (Quadratisches Reziprozitätsgesetz, Gauß) Es seien und teilerfremd. Dann gilt

   , ungerade

    
       
   sonst
 


  




Satz 132 Für ungerades  gilt

 


 


   

   " 


  "

Korollar 133 Das Jacobi-Symbol ist effizient berechenbar. Beweis: Dies folgt, ähnlich wie beim Euklidschen Algorithmus, aus folgenden Gleichungen.

    
       


      

       




falls 


falls  ungerade

falls 
  

 ungerade falls 
    ungerade 

Beispiel 134 Das Jacobi-Symbol zu 73 modulo 83:

%  


                 

  




#

96

3 Zahlentheoretische Grundlagen

3.4 Primzahlen Sei (

   
mit

(
         die Anzahl der Primzahlen kleiner gleich . Mit ( 
 bezeichnen wir die Anzahl der Primzahlen kleiner gleich , die von der Form 
    für ein    sind. Satz 135 (Primzahlsatz, Dirichlet, Hadamard, de la Vallée Poussin) Ist

 
, so gilt

(
 & "  

Insbesondere gilt also

 (   

10 4 4,34

100 25 21,7

( &   1 000 168 144,8

10 000 1 229 1 085,8

10 100 1 240 1 095,5

100 000 9 592 8 685,9

1 000 000 78 498 72 382,2

10 000 000 664 579 620 420,7

Beispiel 136 Die Anzahl der Primzahlen in einem Intervall " # ist demnach näherungsweise 

 . Für das Intervall "    # ergibt sich z. B. ein Näherungswert von    , während der tatsächliche Wert gleich 11 ist. # Beispiel 137 Für die Anzahl  

 aller 100-stelligen Primzahlen (in Dezimaldarstellung) erhalten wir z. B. den Näherungswert



 

 

               

Vergleicht man diese Zahl mit der Anzahl aller 100-stelligen Dezimalzahlen, so sehen wir, dass ungefähr jede 230-te 100-stellige Dezimalzahl prim ist. # Der Beweis des Primzahlsatzes ist sehr aufwendig. Mit elementaren Mitteln lässt sich jedoch folgender Satz beweisen, der für die meisten Anwendungen vollkommen ausreicht. Satz 138 (Tschebyscheff) Für alle   gilt (   (Ohne Beweis)

    bedeutet   
.


 

. 

 

3 Zahlentheoretische Grundlagen

97

Der Solovay-Strassen Test Eulers Kriterium besagt, dass im Falle  prim für alle  
 die Kongruenz 
     gilt. Der Solovay-Strassen-Test basiert auf der Tatsache, dass für zusammengesetztes  mindestens die Hälfte aller  
 diese Kongruenz nicht erfüllen. Für    sei '
 
  

 
 

 

Satz 139 Eigenschaften von '  : a) b)

    '
(,  zusammengesetzt und ungerade



'   

$ . 

Beweis: Teil a folgt unmittelbar aus Eulers Kriterium. Für Teil b sei  zusammengesetzt und ungerade. Es ist leicht zu sehen, dass die Menge 8

 ' eine Untergruppe von
 bildet. Da somit 8  ein Teiler von " ist, reicht es zu zeigen, dass mindestens ein Element &  '  existiert. 1. Fall :

2. Fall :

 ist quadratfrei, d. h. 
      für  verschiedene Primzahlen. Dann garantiert der Chinesische Restsatz die Existenz einer Zahl  
 mit   * und    für 
     , wobei * beliebig aus ÉÆÊ gewählt ist. Nun gilt          
        

 aber 


 , da andernfalls  
    folgen würde, was im Widerspruch zu  
    steht.  ist nicht quadratfrei, d. h. es gibt eine Primzahl  mit   . Betrachte 
   
. Dann gilt      


     die Primfaktorzerlegung von  ist. Wegen   folgt wobei &     
. Andererseits 


 gelten, da sonst muss aber    
  
   
     
     
      
  da     für   . Also folgt 
    , und damit wäre  ein Teiler  
  von , was ein Widerspruch ist.

Obiger Satz führt unmittelbar auf folgenden effizienten probabilistischen Primzahltest, der nach Solovay und Strassen benannt ist (  und ungerade, sowie   ):

98

3 Zahlentheoretische Grundlagen

Algorithmus 140 S OLOVAY S TRASSEN



1 while    do 2    3 wähle zufällig ein          4 if (

 
 oder   ' ) then 5 return “zusammengesetzt” 6 end 7 end 8 return “prim”

Ist  eine Primzahl, so gibt der Algorithmus mit Wahrscheinlichkeit 1 „prim“ aus, andernfalls erzeugt er mit einer Wahrscheinlichkeit größer als 
 die Ausgabe „zusammengesetzt“. Da obiger Algorithmus (mit beliebig kleiner Wahrscheinlichkeit) eine falsche Ausgabe produzieren kann, handelt es sich um einen sogenannten Monte-Carlo-Algorithmus (mit einseitigem Fehler, da es nur im Fall  zusammengesetzt zu einer falschen Ausgabe kommen kann). Im Gegensatz hierzu gibt ein sogenannter Las-Vegas-Algorithmus nie eine falsche Antwort. Allerdings darf ein LasVegas-Algorithmus (mit kleiner Wahrscheinlichkeit) die Antwort verweigern, also ein „?“ ausgeben.

Der Miller-Rabin Test Für    sei  
 ,  ungerade, und

'


 
  


  und 


  für 
     $

Satz 141 Eigenschaften von '  : a) b)

    '
(,  zusammengesetzt und ungerade



(ohne Beweis.) Algorithmus 142 M ILLER -R ABIN



1 while    do    2 3 wähle zufällig ein          4 if (  ' ) then 5 return “zusammengesetzt” 6 end 7 end 8 return “prim”

'   

$

    .

4 Asymmetrische Kryptosysteme

99

4 Asymmetrische Kryptosysteme Diffie und Hellman kamen 1976 auf die Idee, dass die Geheimhaltung des Chiffrierschlüssels keine notwendige Voraussetzung für die Sicherheit eines Kryptosystems sein muss. Natürlich setzt dies voraus, dass die vom Sender und Empfänger benutzten Schlüssel  und   voneinander verschieden sind und dass insbesondere der Dechiffrierschlüssel   nur sehr schwer aus dem Chiffrierschlüssel  berechenbar ist. Ist dies gewährleistet, so kann jedem Kommunikationsteilnehmer + ein Paar von zusammen zugeteilt werden. + kann nun den Chiffrierschlüssel   gehörigen Schlüsseln      unter Verschluss halöffentlich bekannt geben, muss aber den Dechiffrierschlüssel   ten. Die Tatsache, dass sich mit   die Nachrichten nicht wieder entschlüsseln lassen, hat den entscheidenden Vorteil, dass   über einen authentisierten Kanal zum Sender gelangen kann (d.h. es ist zwar nicht notwendig,   geheim zu halten, aber die Herkunft von  muss verifizierbar sein). – Von einem symmetrischen Kryptosystem spricht man, wenn die Kenntnis des Chiffrierschlüssels gleichbedeutend mit der Kenntnis des Dechiffrierschlüssels ist, der eine also leicht aus dem anderen berechnet werden kann. – Dagegen sind bei einem asymmetrischen Kryptosystem nur die Dechiffrierschlüssel geheimzuhalten, während die Chiffrierschlüssel öffentlich bekanntgegeben werden können. Für symmetrische Kryptosysteme sind auch die Bezeichnungen konventionelles Kryptosystem, Kryptosystem mit geheimen Schlüsseln oder Secret-Key-Kryptosystem üblich, wogegen asymmetrische Kryptosysteme auch häufig auch als Kryptosysteme mit öffentlichen Schlüsseln oder Public-Key-Kryptosysteme bezeichnet werden. Bei einem symmetrischen Kryptosystem sind die Rollen von Sender und Empfänger untereinander austauschbar (beziehungsweise symmetrisch), da die Vertraulichkeit der Nachrichten auf einem gemeinsamen Geheimnis beruht, welches sich die beiden Kommunikationspartner in Form des zwischen ihnen vereinbarten Schlüssels verschaffen. Der prinzipielle Unterschied zwischen symmetrischer und asymmetrischer Verschlüsselung kann sehr schön am Beispiel eines Tresors veranschaulicht werden, den Alice dazu verwendet, Bob geheime Dokumente zukommen zu lassen. Symmetrische Verschlüsselung: Alice und Bob besitzen beide den gleichen Schlüssel . Alice schließt mit ihrem Schlüssel die Nachricht in den Tresor ein und Bob öffnet ihn später wieder mit seinem Schlüssel. Das Tresorschloss lässt sich also mit  sowohl auf- als auch zuschließen. Asymmetrische Verschlüsselung: Alice schließt die Nachricht mit dem Schlüssel  ( in den Tresor ein. Danach lässt sich das Tresorschloss mit diesem Schlüssel nicht  mögmehr öffnen. Dies ist nur mit dem in Bobs Besitz befindlichen Schlüssel  (  jelich. Obwohl also beide Schlüssel in das Schloss passen, können  ( und ( weils nur in eine von beiden Richtungen gedreht werden.

100

4 Asymmetrische Kryptosysteme

 ist, kann sie im Gegensatz Da Alice nicht im Besitz von Bobs privatem Schlüssel  ( zu Bob nicht alle mit  ( verschlüsselten Nachrichten entschlüsseln, insbesondere keine Kryptotexte, die Bob von anderen Teilnehmern zugeschickt werden. Zu beachten ist  von Bob nur eine Nachrichtenüberauch, dass mit den beiden Schlüsseln  ( und ( mittlung von Alice an Bob möglich ist. Für die umgekehrte Richtung müssen dagegen  von Alice benutzt werden. die beiden Schlüssel   und 

4.1 Das RSA-System Das RSA-Kryptosystem basiert auf dem Faktorisierungsproblem und wurde 1978 von seinen Erfindern Rivest, Shamir und Adleman veröffentlicht. Während beim Primzahlproblem nur eine Ja-Nein-Antwort auf die Frage „Ist  prim?“ gesucht wird, muss ein Algorithmus für das Faktorisierungsproblem im Falle einer zusammengesetzten Zahl mindestens einen nicht-trivialen Faktor berechnen. Für jeden Teilnehmer des RSA-Kryptosystems werden zwei große Primzahlen   und Exponenten =  mit =   $  bestimmt, wobei 
   und "
     ist. Öffentlicher Schlüssel: Geheimer Schlüssel:


= ,  
 .

Jede Nachricht  wird durch eine Folge         von natürlichen Zahlen dargestellt, die einzeln wie folgt ver- und entschlüsselt werden.

 % 

 =  
     
   Die Chiffrierfunktionen  und können durch „Wiederholtes Quadrieren und Multiplizieren“ effizient berechnet werden. Der Schlüsselraum ist also


  

es ex. Primzahlen  und  mit 
 und  
$

und enthält alle Schlüsselpaare =        mit =   $ . Satz 143 Für jedes Schlüsselpaar =     und alle  
 gilt

    Beweis: Sei =  
  "  für eine natürliche Zahl  .

4 Asymmetrische Kryptosysteme

1. Fall:

2. Fall:

101

 
: Mit dem Satz von Euler-Fermat folgt unmittelbar    $  

 
: Dann ist  
& und es gilt 
$   
& für eine natürliche Zahl $. Daher folgt &
 
  &   

&
  
  

und

3. Fall: 4. Fall:

 
$       Somit erhalten wir   & .

 
: analog zu Fall 2.

 
: Dann gilt     .



Zur praktischen Durchführung 1. Bestimmung von  und  : Man beginnt mit einer Zahl  der Form    (mit  
) und der verlangten Größenordnung (z. B.  

) und führt einen Primzahltest für   durch. Ist die Antwort negativ, testet man der Reihe nach die Zahlen  ,  ,  ,  ,  ,   , ,   ,   , . . . bis eine Primzahl  gefunden ist. Wegen     und da nur 8 von 30 Zahlen getestet werden,   sind hierzu ungefähr 

     Primzahltests durchzuführen (bei 100stelligen Dezimalzahlen sind das um die 92 Tests).

2. Bestimmung von :  soll teilerfremd zu "
     sein. Diese Bedingung wird z. B. von jeder Primzahl größer als    erfüllt.

3. Bestimmung von =: Da

 "
 ist, liefert der erweiterte Euklidsche Algorithmus das multiplikative Inverse = von  modulo ".

4. Ver- und Entschlüsselung: Modulares Exponentieren durch wiederholtes Quadrieren und Multiplizieren. Es gibt auch Hardware-Implementierungen, die (unter Verwendung des Chinesischen Restsatzes) mit Geschwindigkeiten von bis zu 225 Kbits/sec arbeiten und somit circa 1500 mal langsamer als der DES sind.

Kryptoanalytische Betrachtungen 1. Die Primfaktoren  und  sollten nicht zu nahe beieinander liegen, da sonst durch das Verfahren der Differenz der Quadrate faktorisiert werden kann:



102

4 Asymmetrische Kryptosysteme

Sei    . Dann gilt mit 


2.


& und 
 
 






  
    
   ) Durch Suchen einer Zahl   , so dass   eine Quadratzahl ist, d. h.  
  , können 
 ) und 
  ermittelt werden. Für 
  ist zum Beispiel * +
 . Bereits für 
 ist  
   

 eine Quadratzahl, woraus wir die beiden Faktoren 
 
 und 
 
 erhalten. Das kleinste gemeinsame Vielfache 
     sollte möglichst groß sein, damit nicht ein zu  äquivalentes  durch Raten oder durch eine systematische Suche gefunden werden kann. Wie folgende Äquivalenzumformungen zeigen, ist nämlich ein Exponent  äquivalent zu , falls    ist.



,    





,     



,    &


  =      =    =   
   =   &
  =       

    



(Satz von Gauß)

Wegen

    
     

    sollte

    also relativ klein sein, d. h.   und   müs-

sen große, nicht gemeinsam vorkommende Primfaktoren enthalten. Um dies zu erreichen, wählt man zur Bestimmung von  und  jeweils eine große Primzahl  bzw.  und testet die Zahlen $   , (für $
     ) mit einem Primzahltest. Hierzu sind gewöhnlich      Tests auszuführen (nach Elliot und Halberstam).









3. Ist damit zu rechnen, dass ein Benutzer die gleiche Nachricht  an mehrere Empfänger schickt, sollten die Module 
   aller Teilnehmer paarweise verschieden gewählt werden. Ist sonst nämlich

=   = 
 (die Wahrscheinlichkeit hierfür ist ungefähr ), so kann  leicht aus =  , = , 
    und 
    berechnet werden: 1. Fall:

    . Dann ist

     , d. h. das System ist gebrochen.

2. Fall:

  
. Berechne mit dem erweiterten Euklidschen Algorithmus Zahlen   
 mit   =   =
 und   
  , wobei o. B. d. A.  % sei. Dann ist 
  $
 , also 
 
    $
 
            

4 Asymmetrische Kryptosysteme

4. Sei 
   (mit berechnet werden:






103

   ;   ). Dann können   leicht aus  und "

"
     "
      
        "  
  
   

Satz 144 Es gibt einen Las-Vegas Algorithmus, der bei Eingabe von  1 eine Faktorisierung von  mit Wahrscheinlichkeit    ausgibt, falls 
   (  prim) und 1 ein Vielfaches von " ist. Beweis: (konstruktive Beweisführung durch Angabe des Algorithmus) Wir wandeln den Miller-Rabin Primzahltest in einen Las-Vegas Algorithmus ab, der bei Eingabe von  und 1 mit hoher Wahrscheinlichkeit einen Faktor von  ausgibt. Algorithmus 145 RSA-FACTORIZE (1
  ,  ungerade) 1 2 3 4 5 6 7 8 9 10 11 12 13

wähle zufällig     if

    then output

  end   
  while 

  do      end if   " then output “?” else output

   end

1

     

Das folgende Lemma beweist die Korrektheit von RSA-FACTORIZE. Aus Zeitgründen verzichten wir auf den Nachweis, dass dem Algorithmus mit einer Wahrscheinlichkeit    eine Faktorisierung von  gelingt.  Lemma 146 Seien   zwei Lösungen der Kongruenz   

   ein nicht-trivialer Faktor von . Beweis: Wegen   

  existiert ein : 
mit   
      
:  

 mit 

 " . Dann ist

104

4 Asymmetrische Kryptosysteme

Da jedoch weder   noch   durch  teilbar ist, folgt

 

   . 

Bemerkung 147 Falls es möglich wäre, aus , =, 
   die Parität von  in Polynomialzeit zu bestimmen, so könnte auch der gesamte Klartext  in Polynomialzeit aus , = und  berechnet werden. Das letzte Bit des Klartextes ist also genau so sicher wie der gesamte Klartext: Falls RSA nicht total gebrochen werden kann, kann auch nicht das letzte Bit des Klartextes ermittelt werden. Sei nämlich klartext-half 
half


 

und klartext-parity 
parity


falls    
  falls       





falls  ungerade falls  gerade

dann kann wegen half
parity  die Berechnung von klartext-half  auf die Berechnung von klartext-parity  reduziert werden: klartext-half 
klartext-parity

   
klartext-parity   

Also lässt sich  mit Hilfe von klartext-half (oder von klartext-parity) leicht durch eine Intervallschachtelung bestimmen: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

     for   to  do !"#  klartext-half       end low  high   for   to  do mid  highlow if !"#
 then low  mid else high  mid end end output high

Beispiel 148 Sei 
 , =
 und 
 . Angenommen, klartext-half liefert die Werte !"     #
   . Dann führt die Intervallschachtelung

4 Asymmetrische Kryptosysteme

 0 1 2 .. . 10

105

low 0 728,5 728,5 .. .

high 1 457 1 457 1 092,75 .. .

mid 728,5 1 092,75 910,62 .. .

998,84 998,84

1 000,26 999,55

999,55 –

auf den Klartext 
high
.

#

4.2 Das Rabin-System Wie das RSA-Verfahren beruht das Rabin-System darauf, dass es zwar effiziente Algorithmen für das Testen der Primzahleigenschaft gibt, effiziente Faktorisierungsalgorithmen aber nicht bekannt sind. Im Gegensatz zum RSA-Verfahren, von dem nicht bekannt ist, dass es mindestens so schwer zu brechen ist wie das Faktorisierungsproblem, ist genau dies beim Rabin-System der Fall. Die Sicherheit des Rabin-Systems ist also äquivalent zur Schwierigkeit des Faktorisierungsproblems. Es verwendet als Falltürfunktion eine quadratische Polynomfunktion modulo dem Produkt 
   zweier großer Primzahlen. Jeder Teilnehmer wählt ein Paar   von Primzahlen mit der Eigenschaft      und eine Zahl =         . Die Zahlen  und = werden öffentlich bekannt gegeben, die Faktorisierung von  wird jedoch geheimgehalten. Öffentlicher Schlüssel: Geheimer Schlüssel:

=   .

Jede Nachricht  wird in eine Folge von natürlichen Zahlen aufgeteilt, die der Reihe nach wie folgt verschlüsselt werden.



       

  = 
   =  
 Zur Entschlüsselung eines Kryptotextes          muss der legale Empfänger  die quadratische Kongruenzgleichung    =   lösen, die äquivalent zu der Kongruenz 
  =  
  = 

   

¼

(quadratische Ergänzung) ist, wobei

  das multiplikative Inverse zu 2 modulo  ist. Unter Verwendung des folgenden Satzes können die vier Lösungen   (für     ) dieser Kongruenx effizient von  bestimmt werden. Satz 149 Sei 
   für Primzahlen   mit    . Dann besitzt die quadratische Kongruenz    für jedes   ÉÊ genau vier Lösungen, wovon nur eine ein quadratischer Rest ist.

106

4 Asymmetrische Kryptosysteme

Beweis: Mit    besitzen wegen 
   auch die beiden quadratischen Kongruenzen    und  &  Lösungen, und zwar jeweils genau zwei:     und    , die sich nach Korollar 129 bestimmen lassen. Mit dem Chinesischen Restsatz können wir je eine Lösung der beiden Systeme

    &

*  * &  bestimmen, die sich aus der linearen Darstellung    $  
 von

  
 zu 
$   und *
   ergeben. Nun ist leicht zu sehen, dass 
   *     
   *     
   *     
   *     vier verschiedene Lösungen der quadratischen Kongruenz     sind. Es können

*

aber auch nicht mehr als vier Lösungen existieren, da sich daraus für mindestens eine der beiden Kongruenzen     und  &  mehr als zwei Lösungen ableiten ließen.

Um schließlich zu zeigen, dass genau eine der vier Lösungen ein quadratischer Rest ist, nehmen wir o. B. d. A. an, dass    ÉÊ ,   ÉÆÊ und   ÉÊ& ,   ÉÆÊ& sind. Betrachten wir folgendes Lemma als Zwischenschritt. Lemma 150 Jeder quadratische Rest  modulo  ist auch quadratischer Rest modulo , falls  Teiler von  ist.

  ÉÊ     ÉÊ

Beweis:

  



  ÉÊ

 
      
       ÉÊ 



Mit diesem Lemma folgt, daß       keine quadratischen Reste modulo  sein können. Weiterhin gibt es Zahlen $ 
,  
& mit $   und   &  .

+  * , 

  $ *     $ *     $ *  

also ist  ein quadratischer Rest modulo .



&



$    &   

 

& 



Als weitere zahlentheoretische Funktion mit für die Kryptographie wichtigen Eigenschaften erhalten wir also die Quadratfunktion    ÉÊ  ÉÊ , die nach vorigem Satz bijektiv ist (falls ) 
   für Primzahlen ,  mit    ). Ihre Umkehrfunktion    heißt diskrete Wurzelfunktion, und kann (nur) bei Kenntnis

4 Asymmetrische Kryptosysteme

107

der Primfaktoren  und  von  effizient berechnet werden. Bis heute ist kein effizientes Verfahren bekannt, mit dem man ohne Kenntnis der Faktorisierung von  für ein  
 entscheiden kann, ob   ÉÊ  ist oder nicht. Das Problem, aus den vier Kandidaten den richtigen Klartext auzuwählen, kann entweder unter Ausnutzung der Redundanz der Klartextsprache (es muss sich ein „sinnvoller“ Text ergeben) oder durch Senden folgender Zusatzinformation gelöst werden. Sei 

  =, dann lässt sich  (und damit ) durch Angabe der beiden Bits




!



 


, ¼

falls sonst

und




 

falls   sonst




 

eindeutig unter den vier Lösungen von    


  =  kennzeichnen, da             
      

  
  

ist. Beispiel 151 Wählen wir 
,  Öffentlicher Schlüssel: Geheimer Schlüssel:


 und =
, so ergeben sich =
 
 
 
.

Um den Klartext 
 zu verschlüsseln, wird der Kryptotext


    
     
 erzeugt. Da
  =

 
 ist, kann dieser durch Lösen der quadratischen Kongruenz

 

 


entschlüsselt werden. Hierzu löst der legale Empfänger zunächst die beiden Kongruenzen    und     


"    , also 
, 
 (da sich hier der Exponent  aus 

    zu 
ergibt; vgl. Korollar 129) und  
"   , also 
, 
 (da sich hier  aus 

    zu 
 ergibt). Wegen     
, d. h. 
, *
  
, lassen sich  und  mit zu

dem Chinesischen Restsatz zu den vier Lösungen

    zusammensetzen.







     
      
       
       
 #

108

4 Asymmetrische Kryptosysteme

Es ist klar, dass das System gebrochen ist, sobald  in seine Primfaktoren   zerlegt werden kann. Wie wir gleich sehen werden, sind für Zahlen  von dieser Bauart das Faktorisierungsproblem und das Problem, eine Lösung der quadratischen Kongruenz    für ein gegebenes   ÉÊ zu finden, äquivalent. Kann also das RabinSystem gebrochen werden, so muss ein effizienter Algorithmus S QRT existieren, der bei Eingabe  ,   ÉÊ  , eine Quadratwurzel 
S QRT   von  modulo  berechnet. Unter Verwendung von S QRT lässt sich ein effizienter probabilistischer Algorithmus R ABIN -FACTORIZE angeben, der  faktorisiert: Algorithmus 152 R ABIN -FACTORIZE



wähle zufällig       
 

1 repeat 2      3   S QRT  4 until 

 "  5 return

 





Die Korrektheit des Algorithmus folgt unmittelbar aus Lemma 146. Zudem ist leicht zu sehen, dass der Algorithmus bei jeder Ausführung der repeat-Schleife mit Wahrscheinlichkeit   einen Faktor von  findet. Folglich ist die Wahrscheinlichkeit, dass mehr als  Schleifendurchläufe ausgeführt werden, genau   .