<< . .

. 8
( : 33)



. . >>

rungsblöcke beim Ver- und beim Entschlüsseln verwendet werden. Nur der erste
Geheimtextblock c1 wird evtl. falsch entschlüsselt.

3.4.3 Cipher Feedback Mode “ CFB

Beim CFB-Modus wird ein sogenannter Bit-Strom, das ist ein Element t ∈ Z2 ,
erzeugt, mit dem wie bei einer Vernam-Chiffre verschlüsselt wird. Der Bit-Strom t
wird blockweise aus dem schon bestimmten Chiffrat erzeugt. Insbesondere kann
die Blockl¤nge m für t von n abweichen. Es muss nur m ¤ n gelten. Der Klartext
N wird hier in Blöcke N = (x1 , . . . , xr ) der L¤nge m eingeteilt.
Wie beim CBC-Modus brauchen wir einen Initialisierungsblock I1 ∈ Z2 . Um eine
n

kompakte Schreibweise zu ermöglichen, de¬nieren wir die Abschneidefunktion
± : Z 2 ’ Z 2 , x1 x2 . . . x n ’ x1 x2 . . . x m .
n m


Diese Abbildung gibt also nur die ersten m Bit des Inputs aus und schneidet den
Rest ab. Es gilt dann im i-ten Schritt
±( f (Ii , k))
:=
ti
xi + ti
:=
ci
:= Ii,m+1 Ii,m+2 . . . Ii,n ci,1 ci,2 . . . ci,m
Ii+1

Im letzten Schritt werden die ersten m Bit von Ii abgeschnitten und ci angeh¤ngt.
Die Entschlüsselung unterscheidet sich nur im zweiten Schritt. Dort wird xi :=
ci + ti gesetzt. Der Vorteil dieses Modus besteht darin, dass der teure (zeitauf-
w¤ndige) erste Schritt von Sender und Empf¤nger simultan durchgeführt wer-
den kann.
Durch eine verkürzte Blockl¤nge m < n wird die Übertragung einzelner Blöcke
beschleunigt. Andererseits muss bei kleinem m der Verschlüsselungsalgorithmus
f h¤u¬ger angewendet werden. Hier muss ein Ausgleich geschaffen werden, der
stark von der benutzten Blockchiffre und von praktischen Erw¤gungen abh¤ngt.

Bemerkung
Dieses Verfahren kann nicht mit asymmetrischen Verfahren angewendet werden,
weil Sender und Empf¤nger verschlüsseln können müssen.

3.4.4 Output Feedback Mode “ OFB
Der OFB-Modus ist dem CFB-Modus sehr ¤hnlich. Wir nutzen dieselben Voraus-
setzungen und eine Initialisierung I1 und setzen
f (Ii , k)
:=
Ii+1
xi + ±(Ii+1 ) .
:=
ci

Da die Ii unabh¤ngig von schon vorher übertragenen Daten berechnet werden
kann, ist das Verfahren sehr schnell. Es hat aber ¤hnliche Nachteile wie der ECB-
Modus, weil keine Rückkopplung zwischen den einzelnen Blöcken statt¬ndet.
56 3 Block-Chiffren “ AES und DES

3.5 Differentielle und lineare Kryptoanalyse *
Die differentielle Kryptoanalyse wurde 1990 in [3] erstmals veröffentlicht. Sie
stellte damals einen großen Fortschritt in der Kryptoanalyse dar. Natürlich wur-
de sie insbesondere am DES getestet und es stellte sich bald heraus, dass DES
bestens dagegen gerüstet war. Das war kein Zufall. Tats¤chlich war die differen-
tielle Kryptoanalyse beim Design von DES einbezogen worden. Sp¤ter wurde
argumentiert, dass eine Offenlegung der Design-Kriterien des DES auch die dif-
ferentielle Kryptoanalyse offengelegt h¤tte. Genau das wollten die zust¤ndigen
US-Behörden nicht, um ihren Vorsprung in der Kryptoanalyse zu sichern.
Die lineare Kryptoanalyse wurde von Mitsuru Matsui in [16] vorgeschlagen und
am Beispiel des DES untersucht.
Die Grundidee besteht darin, in einer rundenbasierten Block-Chiffre die Runden-
funktion oder Bausteine davon wie z. B. S-Boxen durch af¬ne Abbildungen zu
approximieren.

Aufgaben
Zeigen Sie, dass die Multiplikation von Polynomen assoziativ ist.
3.1
Zeigen Sie, dass für alle a, b ∈ K[X] mit ab = 1 gilt a, b ∈ K.
3.2
3.3 Führen Sie den Beweis von Lemma 3.4 zu Ende.
3.4 Beweisen Sie Lemma 3.5.
3.5 Bestimmen Sie alle irreduziblen Polynome der Grade 2, 3, 4 über Z2 und Z3 .
3.6 Nutzen Sie die Ergebnisse aus der vorigen Aufgabe, um zu zeigen, dass das
AES-Polynom m aus dem Beispiel auf Seite 39 irreduzibel ist.
3.7 Es sei f ein Polynom, das im Körper L eine Nullstelle ± hat. Zeigen Sie: ±
ist genau dann eine mehrfache Nullstelle von f , wenn f (a) = f (a) = 0. Dabei
bedeutet f die Ableitung des Polynoms, die wie in der Analysis de¬niert ist. Es
gilt die Produktregel.
3.8 Veri¬zieren Sie 5E · 08 = C6 und E4 · C6 = 01. Folgern Sie, dass ±51 = 1 in
F28 . Dabei kann man die Tatsache, 51 = 32 + 16 + 3 zusammen mit den Rechnun-
gen auf Seite 43 nutzen, um die Rechnung erheblich zu vereinfachen. (Vgl. auch
das Lemma 6.15.)
3.9 Zeigen Sie, dass die Abbildungen Shift-Rows und Mix-Columns aus dem
AES (siehe Seite 49) F28 -linear sind.
3.10 Zeigen Sie, dass die Abbildung Expansion aus dem DES (Abschnitt 3.3.2)
linear ist, indem Sie eine Matrix-Darstellung dafür angeben.
3.11 Zeigen Sie, dass die S-Box S1 aus dem DES nicht linear und auch nicht
af¬n ist.
4 Komplexit¤t und
Einwegfunktionen

Für die Sicherheit mancher moderner kryptogra¬scher Systeme ist es entschei-
dend, dass das Faktorisieren großer natürlicher Zahlen als schwierig anzusehen
ist. Wir werden im vorliegenden Kapitel ein Maß für diesen etwas schwammigen
Begriff schwierig erl¤utern. Dazu betrachten wir die Komplexit¤t von algorithmisch
behandelbaren Problemen.
Die Komplexit¤t eines Algorithmus sch¤tzt die Laufzeit des Algorithmus für große
Eingabewerte asymptotisch unter Verwendung des Landau-Symbols O ab. So wird
ein Vergleich der Schwierigkeitsgrade von mathematischen Problemen möglich.
Weil wir aber nur Aussagen über die Laufzeiten im Unendlichen gewinnen, sind
damit keine Aussagen über den praktischen Nutzen verbunden. Für solche Aus-
sagen müssen genauere Untersuchungen durchgeführt werden.
Für die Kryptologie besonders interessant ist die Frage, ob es Probleme mit ge-
wissen Zusatzeigenschaften gibt, die beweisbar nur in nicht-polynomialer Zeit ge-
löst werden können und daher als schwierig einzustufen sind. Diese Frage ist eng
mit einer weiteren, bisher ungelösten Frage verbunden: Sind die Komplexit¤ts-
klassen P und NP gleich? Sehr vereinfacht ausgedrückt gibt es in der Klasse NP
vermutlich mathematische Probleme, die viel schwieriger zu lösen sind als die
Probleme der Klasse P .
Wir bestimmen explizit die Laufzeiten der Addition und Multiplikation ganzer
Zahlen und Polynome, der Divison mit Rest für ganze Zahlen und Polynome
wie auch die Laufzeiten des euklidischen Algorithmus und der Bestimmung von
Inversen von Elementen aus der primen Restklassengruppe Z — “ es sind dies die
n
grundlegenden Operationen, die in der Kryptologie durchgeführt werden.
Einwegfunktionen sind Funktionen, die im Sinne der Komplexit¤t leicht berechnet,
aber nur schwer invertiert werden können. Solche Funktionen sind die Basis für
alle asymmetrischen kryptogra¬schen Systeme.



4.1 Komplexit¤t

Wir werden die Laufzeit von Algorithmen mit dem asymptotischen Verhalten
von Funktionen vergleichen. Dazu betrachten wir vorab reellwertige Funktionen
und fragen nach ihrem Verhalten im Unendlichen. Wir erinnern zun¤chst an einige
Begriffe aus der Analysis.
58 4 Komplexit¤t und Einwegfunktionen

4.1.1 Die Ordnung von Funktionen

Es sei X eine unbeschr¤nkte Teilmenge des R k , k ∈ N, z. B. X = N k . Für zwei
Funktionen f , g : X ’ R schreiben wir f = O(g), wenn es Zahlen C, r ∈ R >0
gibt, sodass
| f (x)| ¤ C |g(x)| für alle x ∈ X mit |x| > r .
Da wir nur Aussagen über große x machen, sprechen wir vom asymptotischen
Verhalten.
Das O soll an das Wort Ordnung erinnern. Es werden aber eher Sprechweisen wie
f ist O(g), in Worten f ist Groß-O von g, benutzt.
Streng genommen ist O(g) eine Menge von Funktionen und die Schreibweise
f = O(g) eine etwas unpr¤zise, aber nützliche Abkürzung für f ∈ O(g).
In der Praxis verwendet man oft Funktionen zum Vergleich, die besonders einfach
sind. So l¤sst man beispielsweise alle Koef¬zienten weg.
Vor den ersten Beispielen führen wir noch eine übliche Notation ein. Für jede
reelle Zahl x bezeichne

x := max {z ∈ Z ; z ¤ x}

das größte Ganze von x.

Beispiel
Konstante Funktionen X ’ R , x ’ c sind in O(1).

Jede Polynomfunktion f ∈ R[x] mit n = deg f ist in O(x n ).

Für die Funktion f mit f (x) = 1 + x2 gilt

1
f (x) = O(x) und f (x) = x + O .
x

Dabei ist die letzte Gleichung wie folgt zu verstehen:

1
f (x) ’ x = 1 + x2 ’ x ∈ O .
x

Zum Nachweis untersuche man die Grenzwerte
f (x)
lim x( f (x) ’ x) .
bzw.
lim
x
x’∞ x’∞

Für die Logarithmusfunktion loga zur Basis a gilt

log x
loga x = = O (log x) .
log a

In der O-Notation ist also die Basis des Logarithmus irrelevant.
4.1 Komplexit¤t 59

Die Anzahl der Bits einer natürlichen Zahl N ist O(log N). Genauer: Die An-
zahl f (N) der Stellen in g-adischer Darstellung, g ∈ N ≥2 , betr¤gt

f (N) = logg N + 1 = O(log N) .

Der Wert von g spielt asymptotisch keine Rolle.

Bemerkung
Für den logarithmus naturalis verwenden wir die Bezeichnung log = loge oh-
ne Angabe der Basis. Sollte es einmal (wie etwa bei den obigen asymptotischen
Betrachtungen) nicht auf die Basis ankommen, so bevorzugen wir auch im Fall
g = e die einfache Schreibweise log anstelle logg .


4.1.2 Die Laufzeit von Algorithmen

Das Ziel dieses Abschnitts ist es, die Laufzeit von Algorithmen abzusch¤tzen und
zu vergleichen. Dabei nutzen wir ein sehr grobes Maß: Wir z¤hlen die nötigen
Iterationen in Abh¤ngigkeit von der Größe der Eingabe bezogen auf eine einfa-
che Grundoperation. Wir abstrahieren dadurch von der Hardware, die natürlich
die tats¤chlich benötigte Zeit entscheidend mitbestimmt. Insbesondere kann die
Grundoperation durchaus eine größere Anzahl von Prozessorzyklen in Anspruch
nehmen und selbst zeitaufw¤ndig sein. Sie muss aber O(1) sein, darf also nicht
von der Größe der Eingabe abh¤ngen.
Unsere Angaben werden immer asymptotisch sein, dabei ignorieren wir die De-
tails der Implementierung, also die konkrete Umsetzung eines Algorithmus in eine
Programmiersprache. Auch diese beein¬‚usst durchaus erheblich die tats¤chlich
benötigte Zeit.
Asymptotische Aussagen sagen insbesondere nichts über die Laufzeit für kleine
Eingangsgrößen aus. Um darüber Ergebnisse zu erzielen, muss man die Konstan-
ten genau studieren.
Ist n die Größe der Eingabe (etwa die Anzahl der Bits) in einen Algorithmus, so
heißt der Algorithmus
polynomial, wenn die Laufzeit O(n± ), ± ∈ R >0 , ist,

linear, falls er polynomial mit ± = 1 ist,

quadratisch, falls er polynomial mit ± = 2 ist,

exponentiell, wenn die Laufzeit O(e± n ), ± ∈ R >0 , betr¤gt.

In diesem Sinne ist die Laufzeit des Einlesens der Daten linear. Insbesondere hat
das Einlesen einer natürlichen Zahl N nach dem letzten Beispiel die Laufzeit
O(log N). Wir werden im n¤chsten Abschnitt sehen, dass der übliche Algorith-
mus für die Addition natürlicher Zahlen linear, der für die Multiplikation qua-
dratisch ist.
60 4 Komplexit¤t und Einwegfunktionen

Bemerkung
Moderne Faktorisierungs-Algorithmen für natürliche Zahlen haben Laufzeiten

der Form
O(ec log N log log N ), c > 0 .
Das ist zwar nicht polynomial, aber besser als exponentiell. Man nennt sie des-
halb subexponentiell.


4.1.3 Multiplikation von Polynomen

Wir betrachten als erstes Beispiel die Laufzeit für die Multiplikation von Poly-
nomen f , g ∈ Z[X] mit beschr¤nkten Koef¬zienten. Das soll bedeuten, dass die
Asymptotik nur von m = deg f und n = deg g abh¤ngt. Das ist insbesondere für
Polynome über den Restklassenringen Z erfüllt. Hier liegen alle Koef¬zienten
zwischen 0 und ’ 1, weil sie in jedem Schritt modulo reduziert werden.
Die Formel auf Seite 35 zeigt, dass man zur Berechnung des i-ten Koef¬zienten
( f g)i von f g genau i + 1 Multiplikationen von Koef¬zienten durchführen muss.
Die Multiplikation der Koef¬zienten kann als Grundoperation gew¤hlt werden,
weil die Koef¬zienten unabh¤ngig von m und n beschr¤nkt sind. Da die Kosten
für die Addition wesentlich geringer sind, wird diese hier vernachl¤ssigt. Man
beachte auch, dass die Anzahl der Additionen ungef¤hr so groß wie diejenige
der Multiplikationen ist, sodass sich eine Berücksichtigung asymptotisch nicht
auswirken würde. Diese Überlegungen führen auf eine erste Absch¤tzung für
die Laufzeit:
(m + n + 1)(m + n + 2)
m+n
‘ (i + 1) = = O (m + n)2 .
2
i=0

Es geht aber besser: Wir nehmen ohne Einschr¤nkung m ≥ n an, dann sind für
i > n gewisse Produkte zwingend = 0. L¤sst man diese Produkte unberücksich-
tigt, so ergibt sich für die Gesamtzahl aller Multiplikationen:

(m + 1) (n + 1) = O(mn) .

Dabei wird einfach jeder Koef¬zient von f mit jedem von g kombiniert. Dieselben
Überlegungen greifen auch bei Polynomen über endlichen Ringen, wenn man
wieder die Ringmultiplikation als Grundoperation w¤hlt. Wir halten fest:

Lemma 4.1
Sind f und g Polynome über einem endlichen Ring oder über Z mit beschr¤nkten
Koef¬zienten, so betr¤gt die Laufzeit der Multiplikation dieser Polynome asymptotisch
O(deg f · deg g).

Bemerkung
Die Laufzeit des zuerst betrachteten naiven Algorithmus und die Aussage von
4.1 Komplexit¤t 61

Lemma 4.1 unterscheiden sich nicht sehr. Sind m und n ungef¤hr gleich groß,
dann sind beide quadratisch.
Ist aber n beschr¤nkt, so ist der naive Algorithmus immer noch quadratisch, w¤h-
rend das Lemma eine lineare Laufzeit liefert.

Im Folgenden untersuchen wir die Komplexit¤t einiger weiterer für kryptogra¬-
sche Anwendungen wichtiger Algorithmen.
Wie geschehen unterstellen wir bei allen Betrachtungen, dass gewisse Grund-
operationen in O(1) (also in konstanter Zeit) durchgeführt werden können.


4.1.4 Addition und Multiplikation ganzer Zahlen

Wir w¤hlen für zwei natürliche Zahlen a, b und g ∈ N ≥2 die g-adische Darstel-
lung. Das bedeutet:
m n
‘ ai g ‘ bj g j
a= und b = mit 0 ¤ ai , b j < g .
i
i=0 j=0

In der Praxis ist vor allem die Bin¤rdarstellung, d. h. der Fall g = 2 wichtig.
Der übliche (schon in der Grundschule gelehrte) Algorithmus zur Addition der
Zahlen a und b ist gegeben durch:

u0 := 0 und c := a + b + u ’ u · g für ∈ {0, . . . , max{n, m} + 1} .
+1

Dabei wird u +1 so gew¤hlt, dass 0 ¤ c < g. In jedem Schritt wird also modulo
g addiert. Man sieht leicht, dass u +1 ∈ {0, 1}. Man nennt u +1 den Übertrag an
der -ten Stelle. Es gilt dann

max{n,m}+1

a+b = c g.
=0

Mit gutem Recht kann man annehmen, dass die Bestimmung von c und u +1 in
jedem Schritt die Laufzeit O(1) hat. Das ist die Grundoperation in diesem Beispiel.
Es folgt:

Lemma 4.2
Die Laufzeit der Addition zweier Zahlen a und b aus N betr¤gt O(max{log a, log b}).

Der gezeigte Algorithmus ist also auf jeden Fall linear. Für die Multiplikation
natürlicher Zahlen geht man ganz analog vor. Die Grundoperation hierbei ist die
Multiplikation modulo g mit Übertrag, und man erh¤lt für die Laufzeit:

Lemma 4.3
Die Laufzeit der Multiplikation zweier Zahlen a und b aus N betr¤gt O(log a log b).
62 4 Komplexit¤t und Einwegfunktionen

Hierzu vergleiche man auch die Aussage in Lemma 4.1. Man kann n¤mlich
den üblichen Multiplikations-Algorithmus als Polynom-Multiplikation mit Über-
trag deuten.
Selbst bei diesen einfachen Operationen ist möglicherweise nicht das letzte Wort
gesprochen, wie zum Beispiel Aufgabe 4.3 zeigt.

Bemerkung
Der Multiplikations-Algorithmus von Schönhage und Strassen [24] hat die Kom-
plexit¤t O(n log n log log n), wobei n = log a ≈ log b. Das ist zwar besser als
unsere Laufzeitangabe in Lemma 4.3, wirkt sich aber erst ab n ≈ 10 000 in einer
tats¤chlichen Beschleunigung aus.


4.1.5 Division mit Rest

In Satz 3.2 wurde die Division mit Rest für Polynome über einem Körper einge-
führt. Sicher schon aus der Schule bekannt ist die für die Kryptologie fundamen-
tale Division mit Rest für ganze Zahlen. Der Vollst¤ndigkeit halber wiederholen
wir den Satz. Der Beweis kann fast wörtlich aus dem Beweis zu Satz 3.2 über-
nommen werden. An die Stelle der Abbildung deg tritt dabei die Betragsfunktion
| · |, wie man schon an der Formulierung sehen kann.

Satz 4.4 (Division mit Rest)
Zu ganzen Zahlen a, b, wobei b = 0, existieren eindeutig bestimmte q, r ∈ Z mit
a = b q + r und 0 ¤ r < |b| .

Bemerkung
Wir erinnern an eine Schreibweise, die aus der linearen Algebra bekannt ist. Man
sagt, zwei ganze Zahlen a und r sind kongruent modulo b, falls es ein q ∈ Z gibt
mit a = b q + r. Man schreibt dafür auch
a ≡ r (mod b) .
Der Satz zur Division mit Rest besagt, dass, im Falle b = 0, jede ganze Zahl a zu
einer Zahl r ∈ {0, . . . , |b| ’ 1} kongruent modulo b ist. Offenbar ist ≡ (mod b)
eine „quivalenzrelation, die Anzahl der „quivalenzklassen ist |b|.

Legt man den aus der Schule bekannten Algorithmus zur Division mit Rest zu-
grunde, so erhalten wir für die Laufzeit:

Lemma 4.5
Die Division mit Rest bei ganzen Zahlen a, b, wobei b = 0, d. h. die Bestimmung von
q, r ∈ Z mit a = b q + r und 0 ¤ r < |b|, hat die Laufzeit
a
O(log b log q) = O log b log .
b
4.1 Komplexit¤t 63

Eine typische Anwendung ist z. B. die Multiplikation zweier Zahlen a und b mo-
dulo m mit Faktoren 0 ¤ a, b < m: Die Division mit Rest wird auf a b angewendet,
um den kleinsten positiven Vertreter von a b ∈ Z m zu bestimmen. Man beachte,
dass a, b und a b ungef¤hr so groß wie m sind. Beide Teilschritte des Algorithmus,
n¤mlich die Multiplikation und die Division mit Rest, sind quadratisch, also kann
man zusammenfassen:

Lemma 4.6
Die Multiplikation modulo m hat die Laufzeit O((log m)2 ), ist also quadratisch.

Mit einem Beweis, der sich nicht wesentlich von dem für ganze Zahlen unter-
scheidet, ergibt sich für die Laufzeit für die Division von Polynomen mit Rest:

Lemma 4.7
Es seien a, b Polynome über einem Körper K, und es gelte b = 0. Die Division mit Rest,
also die Bestimmung von q, r ∈ K[X] mit a = b q + r und deg r < deg b, hat die
Laufzeit O(deg b deg q).


4.1.6 Komplexit¤tsklassen

<< . .

. 8
( : 33)



. . >>