forked from wieerwill/Informatik
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathKryptographie.tex
2639 lines (2011 loc) · 292 KB
/
Kryptographie.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
\documentclass[a4paper]{article}
\usepackage[ngerman]{babel}
\usepackage[utf8]{inputenc}
\usepackage{multicol}
\usepackage{calc}
\usepackage{ifthen}
\usepackage[landscape]{geometry}
\usepackage{amsmath,amsthm,amsfonts,amssymb}
\usepackage{color,graphicx,overpic}
\usepackage{xcolor, listings}
\usepackage[compact]{titlesec} %less space for headers
\usepackage{mdwlist} %less space for lists
\usepackage{pdflscape}
\usepackage{verbatim}
\usepackage[most]{tcolorbox}
\usepackage[hidelinks,pdfencoding=auto]{hyperref}
\usepackage{bussproofs}
\usepackage{fancyhdr}
\usepackage{lastpage}
\pagestyle{fancy}
\fancyhf{}
\fancyhead[L]{Kryptographie}
\fancyfoot[L]{\thepage/\pageref{LastPage}}
\renewcommand{\headrulewidth}{0pt} %obere Trennlinie
\renewcommand{\footrulewidth}{0pt} %untere Trennlinie
\pdfinfo{
/Title (Kryptographie - Cheatsheet)
/Creator (TeX)
/Producer (pdfTeX 1.40.0)
/Author (Robert Jeutter)
/Subject ()
}
%%% Code Listings
\definecolor{codegreen}{rgb}{0,0.6,0}
\definecolor{codegray}{rgb}{0.5,0.5,0.5}
\definecolor{codepurple}{rgb}{0.58,0,0.82}
\definecolor{backcolour}{rgb}{0.95,0.95,0.92}
\lstdefinestyle{mystyle}{
backgroundcolor=\color{backcolour},
commentstyle=\color{codegreen},
keywordstyle=\color{magenta},
numberstyle=\tiny\color{codegray},
stringstyle=\color{codepurple},
basicstyle=\ttfamily,
breakatwhitespace=false,
}
\lstset{style=mystyle, upquote=true}
%textmarker style from colorbox doc
\tcbset{textmarker/.style={%
enhanced,
parbox=false,boxrule=0mm,boxsep=0mm,arc=0mm,
outer arc=0mm,left=2mm,right=2mm,top=3pt,bottom=3pt,
toptitle=1mm,bottomtitle=1mm,oversize}}
% define new colorboxes
\newtcolorbox{hintBox}{textmarker,
borderline west={6pt}{0pt}{yellow},
colback=yellow!10!white}
\newtcolorbox{importantBox}{textmarker,
borderline west={6pt}{0pt}{red},
colback=red!10!white}
\newtcolorbox{noteBox}{textmarker,
borderline west={3pt}{0pt}{green},
colback=green!10!white}
% define commands for easy access
\renewcommand{\note}[2]{\begin{noteBox} \textbf{#1} #2 \end{noteBox}}
\newcommand{\warning}[1]{\begin{hintBox} \textbf{Warning:} #1 \end{hintBox}}
\newcommand{\important}[1]{\begin{importantBox} \textbf{Important:} #1 \end{importantBox}}
% This sets page margins to .5 inch if using letter paper, and to 1cm
% if using A4 paper. (This probably isn't strictly necessary.)
% If using another size paper, use default 1cm margins.
\ifthenelse{\lengthtest { \paperwidth = 11in}}
{ \geometry{top=.5in,left=.5in,right=.5in,bottom=.5in} }
{\ifthenelse{ \lengthtest{ \paperwidth = 297mm}}
{\geometry{top=1.3cm,left=1cm,right=1cm,bottom=1.2cm} }
{\geometry{top=1.3cm,left=1cm,right=1cm,bottom=1.2cm} }
}
% Redefine section commands to use less space
\makeatletter
\renewcommand{\section}{\@startsection{section}{1}{0mm}%
{-1ex plus -.5ex minus -.2ex}%
{0.5ex plus .2ex}%x
{\normalfont\large\bfseries}}
\renewcommand{\subsection}{\@startsection{subsection}{2}{0mm}%
{-1explus -.5ex minus -.2ex}%
{0.5ex plus .2ex}%
{\normalfont\normalsize\bfseries}}
\renewcommand{\subsubsection}{\@startsection{subsubsection}{3}{0mm}%
{-1ex plus -.5ex minus -.2ex}%
{1ex plus .2ex}%
{\normalfont\small\bfseries}}
\makeatother
% Don't print section numbers
\setcounter{secnumdepth}{0}
\setlength{\parindent}{0pt}
\setlength{\parskip}{0pt plus 0.5ex}
% compress space
\setlength\abovedisplayskip{0pt}
\setlength{\parskip}{0pt}
\setlength{\parsep}{0pt}
\setlength{\topskip}{0pt}
\setlength{\topsep}{0pt}
\setlength{\partopsep}{0pt}
\linespread{0.5}
\titlespacing{\section}{0pt}{*0}{*0}
\titlespacing{\subsection}{0pt}{*0}{*0}
\titlespacing{\subsubsection}{0pt}{*0}{*0}
\begin{document}
\raggedright
\begin{multicols}{3}\scriptsize
% multicol parameters
% These lengths are set only within the two main columns
%\setlength{\columnseprule}{0.25pt}
\setlength{\premulticols}{1pt}
\setlength{\postmulticols}{1pt}
\setlength{\multicolsep}{1pt}
\setlength{\columnsep}{2pt}
\section{Einführung}
Kryptologie = Kryptographie (Entwicklung kryptographischer Verfahren) + Kryptoanalyse (Versuch kryptographische Verfahren zu brechen)
Die Kryptographie im engeren und ,,klassischen'' Sinn beschäftigt sich mit Verfahren, um in verschiedenen Kommunikationsszenarien eine gegen Angriffe von Gegnern (Mitlesen, Verändern, Unterschieben, Abstreiten) abgesicherte Kommunikation zu ermöglichen.
Die ,,moderne'' Kryptologie beschäftigt sich mit kryptographischen Verfahren, mit kryptoanalytischen Verfahren, mit Sicherheitskonzepten und mit mathematischen Methoden zur Untersuchung dieser Dinge, abstrakt und an konkreten Verfahren.
Aufgaben von Kryptosystemen
\begin{description*}
\item[Konzelation] Geheimhaltung/Vertraulichkeit/Zugriffsschutz(kein Unberechtigter kann Nachrichteninhalt mithören oder mitlesen
\item[Integrität/Fälschungsschutz] stelle sicher, dass Nachrichten auf dem Übertragungsweg nicht manipuliert worden sind
\item[Authentizität/Signaturen] Garantiere Absenderidentität; Bob kann kontrollieren, dass Nachricht vom behaupteten Absender Alice kommt
\item[Nichtabstreitbarkeit] Bob kann gegenüber Dritten beweisen,dass die Nachricht in der empfangenen Form vom behaupteten Absender Alice kam
\end{description*}
\note{Message Authentication Code (MAC)}{
Funktion, die aus einer Nachricht x einen Code $mac=MAC(x)$ berechnet. Diese Funktion ist ein Geheimnis von legitimen Sendern von Nachrichten an Bob. Insbesondere kann Eva bei gegebener Nachricht x' keinen korrekten MAC für x' berechnen. Bob verfügt über ein Prüfverfahren, das es ihm erlaubt, ein empfangenes Paar $(x,mac)$ darauf zu testen, ob der zweite Teil der zu x gehörende MAC-Wert ist. Wenn Alice die einzige Instanz ist, die die geheime Funktion MAC kennt, dann kann Bob sogar überprüfen, ob Alice tatsächlich die Absenderin ist.
}
\note{Cäsar-Chiffre}{
Cäsar ließ Texte verschlüsseln, indem man nimmt immer den Buchstaben, der im Alphabet drei Positionen ,,weiter rechts'' steht, mit ,,wrap around'' am Ende. Nachteil ist offensichtlich: Wer den Trick kannte, konnte jede Nachricht mitlesen. Es gibt einen Schlüssel
}
\note{Verschiebechiffre}{
Eine einfache ,,Verbesserung'' der Cäsar-Chiffre: Verschiebe zyklisch um eine andere Anzahl k von Buchstaben als nur 3. Um hier die Verschlüsselung und die Entschlüsselung durchzuführen, musste man als ,,Schlüssel'' nur das Bild von A kennen, alternativ die Verschiebeweite k als Zahl. Es gibt dann 21 Schlüssel.
}
\note{Substitutionschiffre}{
Sie sagt, dass das Bild eines Buchstabens ein ganz beliebiger anderer Buchstabe sein soll. Dabei müssen natürlich verschiedene Buchstaben auf verschiedene Buchstaben abgebildet werden. Es er gibt sich eine Chiffre, die durch eine Tabelle mit ganz beliebiger Buchstabenanordnung gegeben ist.
Wenn man hier ver- und entschlüsseln möchte, muss man die gesamte zweite Tabellenzeile kennen. Diese kann hier also als ,,Schlüssel'' dienen. Es gibt $21!\approx 5,11* 10^{19}$ viele verschiedene Schlüssel.
}
\note{Vigenère-Verschlüsselung (16.Jhd)}{
Man benutzt ein Schlüsselwort $a_0,...,a_{s-1}$ größerer Länge $s > 1$ über dem Alphabet $\{A,...,X\}$. $x=x_0...x_{n-1}$ ist der Klartext, $k=a_0 ...a_{s-1}$ der Schlüssel. Verschlüssle x mit den durch k gegebenen Verschiebungen wie folgt: $x_0$ mit $A \rightarrow a_0$ ,$x_2$ mit $A \rightarrow a_2,... ,x_{s-1}$ mit $A\rightarrow a_{s-1}$. Wenn der Schlüssel k aufgebraucht ist, benutze ihn wieder von vorne: Verschlüssle $x_i,i\geq s$, mit Verschiebung $A \rightarrow a_{i\ mod\ s}$.
}
kryptographische Verfahren mit Schlüsseln
\begin{description*}
\item[Symmetrisch (Private-Key)] Es gibt einen geheimen Schlüssel $k$, den beide der kommunizierenden Parteien kennen müssen. Bei Konzelationssystemen bedeutet dies etwa, dass das Verschlüsselungsverfahren und das Entschlüsselungsverfahren beide diesen Schlüssel $k=k'$ benutzen. Bsp. AES (Advanced Encryption Standard).
\item[Asymmetrisch (Public-Key)] Nur eine Seite hat einen geheimen Schlüssel $k'$, die andere Seite benutzt einen ,,öffentlichen'' Schlüssel $k\not =k'$. Bsp. RSA
\end{description*}
\note{Das Kerckhoffs-Prinzip (1883)}{
besagt,dass man davon ausgehen muss, dass Eva die Struktur des Verschlüsselungsverfahrens kennt und die Sicherheit nur von der Geheimhaltung des Schlüssels abhängen darf.
\begin{enumerate*}
\item Geheimhaltung eines Verfahrens ist schwer sicherzustellen
\item Verfahren sind aufwendig zu entwickeln. Ist das geheime Verfahren einmal bekannt, soist es nutzlos. (Mehrfach passiert: Enigma, GSM-Verfahren ,Stromchiffre RC4)
\item Allgemein bekannte Verfahren können von mehr Experten auf ,,Sicherheit'' geprüft werden. Findet niemand einen erfolgreichen Angriff, so kann man eher auf Sicherheit des Verfahrens vertrauen
\item Nur offen gelegte Verfahren können standardisiert werden und weite Verbreitung finden (DES, AES)
\end{enumerate*}
}
\section{Symmetrische Sicherheitsmodelle}
Angriffsszenarien/Bedrohungsszenarien
\begin{enumerate*}
\item ciphertext-only attack (COA): nur mithören
\item known-plaintext attack (KPA): Paare von Klartext und Chiffretext bekannt
\item chosen-plaintext attack (CPA): einige von Eva gewählte Klartexte verschlüsseln
\item chosen-cyphertext attack (CCA): einige von Eva gewählte Chiffretexte entschlüsseln
\item Eva hat hier Möglichkeiten 3. + 4.
\end{enumerate*}
Fähigkeiten von Eva (unter anderem)
\begin{enumerate*}
\item informationstheoretische Sicherheit: unbegrenzte Rechenkapazitäten
\item Konkrete Sicherheit: maximale Anzahl an Rechenoperationen (z.B. $2^{60}$) und begrenzter Speicher (z.B. 1000 TB)
\item Im Design des Verschlüsselungsverfahrens gibt es einen Stellhebel, einen ,,Sicherheitsparameter''. Je nach Leistungsfähigkeit von Eva kann man durch entsprechende Wahl dieses Parameters die Sicherheit des Systems an eine gegebene (geschätzte) Rechenzeitschranke anpassen.
\item Asymptotische Sicherheit: wenn asymptotisch der Rechenzeitaufwand für Eva zum Brechen des Systems schneller als polynomiell wächst, kann man sagen, dass sie für genügend lange Texte keine Chance mehr hat, das System erfolgreich zu brechen
\end{enumerate*}
symmetrische Konzelationssysteme, mit steigender Komplexität.
Alice und Bob haben sich auf einen Schlüssel geeinigt.
\begin{enumerate*}
\item Einmalige Verschlüsselung: Ein einzelner Klartext $x$ vorher bekannter Länge wird übertragen, Eva hört mit (COA)
\begin{itemize*}
\item Unvermeidlich: Triviale Information, z.B. dass eine Nachricht übertragen wurde
\item Vermeiden Eva erhält nicht-triviale Information, z.B. Klartext$=x$ oder Klartext weder $x_1$ noch $x_2$
\item Gegenstand der Steganographie sind Verfahren, Nachrichten so zu übertragen, dass noch nicht einmal die Existenz der Nachricht entdeckt werden kann.
\end{itemize*}
\item Frische Verschlüsselung: Mehrere Klartexte vorher bekannter Länge werden übertragen, Eva hört mit, kann sich einige Klartexte verschlüsseln lassen (CPA).
\begin{itemize*}
\item Triviale Information: z.B. Anzahl der Nachrichten oder Klartext, falls Eva sich zufälligerweise vorher den ,,richtigen'' Klartext hat verschlüsseln lassen.
\end{itemize*}
\item Uneingeschränkte symmetrische Verschlüsselung: Mehrere Klartexte verschiedener Länge, Eva hört mit, kann sich einige Klartexte verschlüsseln lassen (CPA).
\begin{itemize*}
\item Triviale Information: Analog zur frischen Verschlüsselung
\end{itemize*}
\end{enumerate*}
\subsection{Kryptosysteme und possibilistische Sicherheit}
\textbf{Definition 1.1} Ein Kryptosystem ist ein Tupel $S=(X,K,Y,e,d)$, wobei
\begin{itemize*}
\item X und K nicht leere endliche Mengen sind [Klartexte bzw. Schlüssel],
\item Y eine Menge ist [Chiffretexte], und
\item $e:X\times K\rightarrow Y$ und $d:Y\times K\rightarrow X$ Funktionen sind [Verschlüsselungsfunktion bzw. Entschlüsselungsfunktion],
\end{itemize*}
so dass Folgendes gilt:
\begin{enumerate*}
\item $\forall x\in X\forall k\in K:d(e(x,k),k) =x$ (Dechiffrierbedingung)
\item $\forall y\in Y\exists x\in X,k\in K:y=e(x,k)$ (Surjektivität)
\end{enumerate*}
Bemerkung: Surjektivität kann immer hergestellt werden, indem man $Y$ auf das Bild $Bi(e) =e(X\times K)$ einschränkt. Die Forderung ist für unsere Analysen aber bequem.
Für festes $k\in K$ wird die Funktion $e(.,k):X\rightarrow Y,x \rightarrow e(x,k)$ als Chiffre bezeichnet.
\textbf{Beispiel} $X=\{a,b\},K=\{k_0,k_1,k_2\},Y=\{A,B,C\}$. Die Funktion $e$ ist gegeben durch die erste, die Funktion $d$ durch die zweite der folgenden Tabellen. Dann ist $(X,K,Y,e,d)$ Kryptosystem, denn die Dechiffrierbedingung und die Surjektivität sind erfüllt.
\begin{tabular}{c|c|c}
e & a & b \\\hline
$k_0$ & A & B \\
$k_1$ & B & A \\
$k_2$ & A & C
\end{tabular}
\begin{tabular}{c|c|c|c}
d & A & B & C \\\hline
$k_0$ & a & b & a \\
$k_1$ & b & a & a \\
$k_2$ & a & a & b
\end{tabular}
Jede Chiffre $e(.,k)$ eines Kryptosystems muss injektiv sein. (Die Einträge in jeder Zeile der Tabelle für $e$ müssen verschieden sein.)
Das Vernam-Kryptosystem oder one-time pad der Länge $l$ ist das Kryptosystem $(\{0,1\}^l,\{0,1\}^l,\{0,1\}^l,\oplus_l,\oplus_l)$. Benannt nach Gilbert S. Vernam (1890, 1960), der im Jahr 1918 dieses System für fünf Bits in der Sprache einer Relais-Schaltung beschrieben und zum US-Patent angemeldet hat.
In diesem Fall ist es für nicht ganz kleine l offensichtlich unbequem, wenn nicht ganz unmöglich, die Ver-und Entschlüsselungsfunktion durch Tabellen anzugeben. Man benutzt hier und auch üblicherweise mathematische Beschreibungen.\\
Beispiel: $x=1011001,k=1101010$. Dann ist $y=e(x,k)=1011001\oplus_7 1101010 = 0110011$. Zur Kontrolle: $d(y,k) = 0110011\oplus_7 1101010 = 1011001 =x$.
Wir kontrollieren dass das Vernam-System tatsächlich ein Kryptosystem ist.
\begin{enumerate*}
\item Für $x\in X$ und $k\in K$ gelten $d(e(x,k),k)=(x\oplus_l k)\oplus_l k=x\oplus_l(k\oplus_l k) =x\oplus_l 0^l=x$, d.h. die Dechiffrierbedingung ist erfüllt.
\item Für $y\in Y$ gilt $e(y,0^l) =y$ und $y\in X,0^l\in K$. Also gilt Surjektivität.
\end{enumerate*}
\textbf{Definition} Ein Kryptosystem $S=(X,K,Y,e,d)$ heißt possibilistisch sicher, wenn $\forall y\in Y\forall x\in X\exists k\in K:e(x,k)=y$.
\begin{enumerate*}
\item Sei $S=(X,K,Y,e,d)$ Kryptosystem. Dann sind äquivalent:
\begin{itemize*}
\item $S$ ist possibilistisch sicher.
\item $\forall x\in X:e(x,K)=\{e(x,k)|k\in K\}=Y$.
\end{itemize*}
\item Das Vernam-Kryptosystem der Länge $l$ ist possibilistisch sicher: Seien $x\in X$ und $y\in Y$. Setze $k=x\oplus_l y$.Dann gilt $e(x,k)=x\oplus_l(x\oplus_l y)=(x\oplus_l x)\oplus_l y= 0^l\oplus_l y=y$.
\end{enumerate*}
\textbf{Definition} Für eine endliche, nichtleere Menge $X$ sei $K=P_X$ die Menge der Permutationen (bijektive Funktion $\pi:X\rightarrow X$) auf $X$. Das Substitutionskryptosystem auf $X$ ist das Tupel $(X,PX,X,e,d)$ mit $e(x,\pi)=\pi(x)$ und $d(y,\pi)=\pi^{-1} (y)$.
Wenn $\pi:X\rightarrow X$ eine Permutation ist, dann ist $\pi^{-1}:X\rightarrow X$ die Permutation mit $\pi^{-1}(\pi(x))=\pi(\pi^{-1}(x)) =x$ für alle $x\in X$.
Bei possibilistischer Sicherheit von Klartexten und Schlüsseln, die Zeichenreihen über einem Alphabet sind, müssen Schlüssel mindestens so lang sein wie der zu übermittelnde Text. unrealistisch $\rightarrow$ Possibilistisch sichere Systeme kommen daher nur als Bausteine in größeren Systemen vor.
\subsection{Elementare Wahrscheinlichkeitsrechnung}
\textbf{Definition}: Ein (diskreter) Wahrscheinlichkeitsraum ist ein Paar $(\Omega,Pr)$, wobei
\begin{itemize*}
\item $\Omega$ eine nichtleere endliche oder abzählbar unendliche Menge und
\item $Pr:P(\Omega)\rightarrow[0,1]$ eine Abbildung ($P(\Omega)=\{A|A\subseteq\Omega\}$ ist die Potenzmenge)
\end{itemize*}
\textbf{Definition} Sei $(\Omega,Pr)$ ein Wahrscheinlichkeitsraum und seien $A,B$ Ereignisse. Dann heißen A und B unabhängig, wenn $Pr(A\cap B)=Pr(A)*Pr(B)$ gilt.
\textbf{Definition} Sei $(\Omega,Pr)$ ein Wahrscheinlichkeitsraum und R eine endliche oder abzählbare Menge. Eine Zufallsvariable ist eine Abbildung $X:\Omega\rightarrow R$. Zufallsvariablen mit $R\subseteq R$ heißen reelle Zufallsvariable.
\subsection{Informationstheoretische Sicherheit}
Wenn sich durch das Beobachten einer Chiffre die Meinung von Eva über die Wahrscheinlichkeiten der verschiedenen Klartexte von der ursprünglichen Verteilung unterscheidet, hat Eva aus der Beobachtung von y eine gewisse Information erhalten.
In das math. Modell $\Omega=X\times K$ bauen wir die Vorstellung ein, dass $x\in X$ und $k\in K$ nach den Verteilungen $Pr_X$ (Teil der Anwendung) und $Pr_K$ (Teil des Kryptosystems) zufällig und unabhängig gewählt werden. Die Verteilung $Pr_X$ braucht beim Entwurf des Kryptosystems nicht einmal bekannt zu sein.
\textbf{Definition} Ein Kryptosystem mit Schlüsselverteilung (KSV) ist ein 6-Tupel $V=(X,K,Y,e,d,Pr_K)$, wobei
\begin{itemize*}
\item $S=(X,K,Y,e,d)$ das zugrundeliegende Kryptosystem ist
\item $Pr_K:K\rightarrow (0,1]$ die Schlüsselverteilung
\item Für $V=(X,K,Y,e,d,Pr_K)$ schreiben wir auch $S[Pr_K]$
\item $Pr_K(k)\in (0,1]$ also $Pr_K(k)> 0$ für alle $k\in K$
\item weiter $Pr_X:X\rightarrow [0,1]$ Klartextverteilung
\item $Pr:X\times K\rightarrow [0,1]$ durch $Pr((x,k)):=Pr_X(x)*Pr_K(k)$
\item Annahme modelliert, dass der Schlüssel k unabhängig vom Klartext durch ein von $Pr_K$ gesteuertes Zufallsexperiment gewählt
\end{itemize*}
\textbf{Beispiel} Sei $X=\{a,b,c\},K=\{0,1,2,3\},Y=\{A,B,C\}$ und die Verschlüsselungsfunktion sei durch die folgende Tabelle gegeben:
\begin{tabular}{c|c|c|c}
e & a(0,4) & b(0) & c(0,6) \\\hline
0 ($\frac{1}{4}$) & A & B & C \\
1 ($\frac{1}{8}$) & B & C & A \\
2 ($\frac{1}{2}$) & C & A & B \\
3 ($\frac{1}{8}$) & C & B & A
\end{tabular}
Die Wahrscheinlichkeiten $Pr_X(x)$ sind bei den Klartexten, die Wahrscheinlichkeiten $Pr_K(k)$ bei den Schlüsseln in Klammern notiert. Klartexte a und c sind aktiv, Klartext b ist passiv.
Einige einfache Zusammenhänge, für $x_0\in X,k_0\in K,y_0\in Y$
\begin{itemize*}
\item $X: X\times K \rightarrow X, (x,k)\rightarrow x$
\item $X: X\times K \rightarrow K, (x,k)\rightarrow k$
\item $Pr(x_0):=Pr(\{x_0\}\times K) = Pr_X(x_0)*Pr_K(K) = Pr_X(x_0)$.
\item $Pr(k_0):=Pr(X\times\{k_0\})=Pr_X(X)*Pr_K(k_0)=Pr_K(k_0)$
\item Man erhält die ursprünglichen Wahrscheinlichkeiten für Klartexte und Schlüssel zurück
\item Im Bsp $Pr(A)=\frac{1}{4}*0,4+ \frac{1}{8}*0,6 +\frac{1}{2}*0 +\frac{1}{8}* 0,6=0,25$
\item Im Bsp $Pr(c,A)=0,6*(\frac{1}{8}+\frac{1}{8})=0,15$
\item Im Bsp $Pr(c|A)=\frac{P(c,A)}{P(A)}=\frac{0,15}{0,25}=0,6$
\end{itemize*}
\textbf{Definition} $V=(X,K,Y,e,d,Pr_K)$ ein Kryptosystem mit Schlüsselverteilung
\begin{enumerate*}
\item Sei $Pr_X$ eine Wahrscheinlichkeitsfunktion auf den Klartexten. Dann heißt $V$ informationstheoretisch sicher bezüglich $Pr_X$, wenn für alle $x\in X,y\in Y$ mit $Pr(y)>0$ gilt: $Pr(x) = Pr(x|y)$.
\item Das KSV $V$ heißt informationstheoretisch sicher, wenn es bezüglich jeder beliebigen Klartextverteilung $Pr_X$ informationstheoretisch sicher ist.
\end{enumerate*}
\textbf{Satz: Informationstheoretische Sicherheit des Vernam-Systems} Sei $l>0$ und $S=(X,K,Y,e,d)$ mit $X=K=Y=\{0,1\}^l$ und $e=d=\oplus_l$ das Vernam-System der Länge $l$. Sei weiter $Pr_K:K\rightarrow [0,1]$ die Gleichverteilung. Dann ist $V=S[Pr_K]$ informationstheoretisch sicher.
Es wird sich herausstellen, dass informationstheoretische Sicherheit in bestimmten Fällen Gleichverteilung auf den Schlüsseln erzwingt und dass die informationstheoretische Sicherheit eines KSV nichts mit den konkreten Wahrscheinlichkeiten der Klartextverteilung $Pr_X$ zu tun hat, sondern nur die Menge $\{x\in X|Pr_X(x)> 0\}$ der ''aktiven'' Klartexte relevant ist.
$Pr(x|y) =\frac{Pr(x,y)}{Pr(y)}=\frac{Pr(y|x)*Pr(x)}{Pr(y)}=\frac{Pr_K(k_{x,y})*Pr(x)}{Pr(y)}=^* \frac{\frac{1}{|K|}*Pr(x)}{\frac{1}{|K|}}=Pr(x)$
\textbf{Satz} Sei $V= (X,K,Y,e,d,Pr_K)$ ein KSV mit $|X|=|Y|=|K|$. Dann sind äquivalent:
\begin{enumerate*}
\item $V$ ist informationstheoretisch sicher.
\item $(X,K,Y,e,d)$ ist possibilistisch sicher und $Pr_K(k)=\frac{1}{|K|}$ für alle $k\in K$.
\end{enumerate*}
Der Satz besagt, dass man informationstheoretisch sichere Systeme mit $|X|=|Y|=|K|$ daran erkennt, dass in der Verschlüsselungstabelle in jeder Spalte alle Chiffretexte vorkommen (possibilistische Sicherheit) und dass die Schlüsselverteilung $Pr_K$ uniform ist. Auch in jeder Zeile kommen natürlich alle Chiffretexte vor: das liegt aber einfach an der Dechiffrierbedingung. Die Klartextverteilung ist irrelevant.
Technisch hilfreich sind die folgenden Größen, die nur von der Verschlüsselungsfunktion und der Schlüsselverteilung abhängen
\begin{itemize*}
\item $P^x(y):=\sum_{k\in K, e(x,k)=y} Pr(k)$ für $x\in X,y\in Y$ (1.1)
\item Für alle $x\in X:Pr(x,y) = Pr(x)*P^x(y)$ (1.2)
\item wenn $Pr(x)> 0:Pr(y|x) = \frac{Pr(x,y)}{Pr(x)}=P^x(y)$ (1.3)
\end{itemize*}
\textbf{Lemma} Sei $V=(X,K,Y,e,d,Pr_K)$ KSV und seien $Pr_X$ und $Pr'_X$ Klartextverteilungen mit $Pr'_X(x)>0\Rightarrow Pr_X(x)>0$. Dann gilt: Ist $V$ informationstheoretisch sicher bzgl. $Pr_X$, so ist V informationstheoretisch sicher bzgl. $Pr'_X$. Besagt, dass man die Wahrscheinlichkeiten aktiver Klartexte beliebig ändern kann, ohne dass eine bestehende informationstheoretische Sicherheit zerstört wird.
Beweis: Sei $V$ informationstheoretisch sicher bzgl. $Pr_X$. Wir zeigen nacheinander vier Aussagen.
\begin{enumerate*}
\item $Pr_X(x)> 0 \Rightarrow Pr^x(y) = Pr(y|x) = Pr(y)$ für alle $y\in Y$
\item $Pr'_X(x)> 0 \Rightarrow Pr'(y|x) = Pr(y)$ für alle $y\in Y$
\item $Pr'(y)=Pr(y)$ für alle $y\in Y$
\item $Pr'(x)=Pr'(x|y)$ für alle $x\in X,y\in Y$ mit $Pr'(y)>0$
\end{enumerate*}
\textbf{Satz} Sei $V=(X,K,Y,e,d,Pr_K)$ KSV und sei $Pr_X$ eine Klartextverteilung. Dann sind äquivalent:
\begin{enumerate*}
\item V ist informationstheoretisch sicher für $Pr_X$.
\item Für jedes $x\in X$ und jedes $y\in Y$ gilt: $Pr(x,y)=Pr(x)Pr(y)$ (das Eintreten von x und das Eintreten von y sind unabhängig).
\item Für alle $x\in X$ mit $Pr(x)>0$ und alle $y\in Y$ gilt $Pr(y)=Pr(y|x)$ (andere Formulierung der Unabhängigkeit).
\item Für alle $x,x'\in X$ mit $Pr(x),Pr(x')>0$ und alle $y\in Y$ gilt $P^x(y)=P^{x'}(y)$.
\end{enumerate*}
Die informationstechnische Sicherheit drückt sich dadurch aus, dass diese Chiffretextwahrscheinlichkeiten auch für jeden Klartext (also jede Spalte) separat auftreten.
\subsection{Cyphertext-only-Angriffe: Vigenère-Chiffre}
Eine Folge $x=x_0 ...x_{l-1}$ von Buchstaben im Klartextalphabet $\{a,...,z\}$ der Größe 26. Ein informationstheoretisch sicheres Verfahren ist, für jede Buchstabenposition $0\geq i < L$ rein zufällig einen Schlüssel $k_i\in\{A,...,Z\}$ zu wählen und an Position $i$ die Verschiebechiffre mit Schlüssel $k_i$ anzuwenden. Der Schlüssel $k_0,...,k_{L-1}$ ist dann aber mindestens so lang wie die Klartextfolge. Allerdings ist das nach unseren bisherigen Ergebnissen auch unvermeidlich: Wenn $V=(X,K,Y,e,d,Pr_K)$ informationstheoretisch sicher ist, ist $(X,K,Y,e,d)$ possibilistisch sicher, also $|X|\geq |K|$.
\subsubsection{Viginère Angriffe bei bekannter Schlüssellänge}
\textbf{Definition} Eine Verschiebechiffre ist ein Kryptosystem $S=(Z_n,Z_n,Z_n,e,d)$ mit $e(x,k)=(x+k) mod\ n$. (Offensichtlich ist dann $d(y,k)=(y-k)mod\ n$.) Unser Beispiel ist der Fall $n=26$, also $X=Y=K=\{0,1,2,...,25\}$. Wir identifizieren die Elemente dieser Menge mit den Buchstaben $a,...,z$ (bei X) bzw. $A,...,Z$ (bei K und Y).
Die einfachste Methode ist folgende Version der Cäsar-Chiffre: Wähle einen Schlüssel k aus $K=\{0,1,...,25\}=\{A,...,Z\}$ zufällig. Um ,,Texte'' (d.h. Wörter über $\mathbb{Z}_n$) zu verschlüsseln, wird S buchstabenweise angewandt: Aus $x_0 x_1...x_{l-1}$ wird $e(x_0,k)e(x_1,k)...e(x_{l-1},k)$.
Diese Methode ist allerdings sehr leicht zu brechen, sogar ,,von Hand''. Es gibt mindestens die folgenden naheliegenden Möglichkeiten
\begin{enumerate*}
\item probiere die 26 möglichen Schlüssel aus, oder
\item zähle, welche Buchstaben am häufigsten im Chiffretext vorkommen und teste die Hypothese, dass einer von diesen für ,,e'' steht (Häufigkeitstabellen)
\end{enumerate*}
\textbf{Definition} Das Vigenère-Kryptosystem (mit Parametern $(n,S,L)\in\mathbb{N}^3$) ist das Kryptosystem ($(\mathbb{Z}_n)\geq L,(\mathbb{Z}_n)\geq S,(\mathbb{Z}_n)\geq L,e,d$), so dass für alle $s\geq S,l\geq L,x_i,k_j\in\mathbb{Z}_n$ gilt: $e(x_0...x_{l-1},k_0 ...k_{s-1})=y_0 ...y_{l-1}$ mit $y_i=(x_i+k_{i\ mod\ s}) mod\ n$, für alle $0\geq i < l$.
Die zentrale Idee ist, dass für die Verschlüsselung des ,,Teiltextes'' $y_i=y_iy_{i+s}y_{i+2s}...$, für $0\geq i<s$, der Buchstabe $k_i$ benutzt wurde, genau wie bei der einfachen Verschiebechiffre. Für $i,0\geq i<s$, bestimmt Eva also die in diesem Teiltext $y_i=y_iy_{i+s}y_{i+2s}...$ am häufigsten vorkommenden Buchstaben und testet die Hypothesen, dass diese für ,,e'' oder einen anderen häufigen Buchstaben stehen.
\begin{itemize*}
\item Chiffre: EYRYC FWLJH FHSIU BHMJO UCSEG TNEER...
\item $y^0 =EFFBUTFSSMJFPOFT$, häufig: F, Schlüssel $\rightarrow$ B
\item $y^1 =YWHHCNLXSIHXMZCNC$, häufig: Y, Schlüssel $\rightarrow$ U
\item $y^2 =RLSMSEJMTKZMMSRE$, häufig: I,V, Schlüssel $\rightarrow$ E,R
\item $y^3 =YJIJEELVKZVXVIVRYVV$, häufig: V, Schlüssel $\rightarrow$ R
\item $y^4 =CHUOGRVYCSBKWAFHSF$, häufig: S, Schlüssel $\rightarrow$ O
\item Schlüsselwort: BUERO
\end{itemize*}
\subsubsection{Der Kasiski-Test}
Die Schlüssellänge kann oft durch den Kasiski-Test näherungsweise bestimmt werden. Stimmt der Klartext im Abschnitt $i+s*l$ bis $j+s*(l+h)$ mit dem Klartext im Abschnitt von $i+s*l'$ bis $j+s*(l'+h)$ überein, so gilt dies auch für den Chiffretext $(1\geq i,j\geq s,l,l',h\in\mathbb{N})$. Kommt ein Teilwort im Klartext an zwei Positionen i und j und ist j-i ein Vielfaches von s, so werden die beiden Vorkommen des Wortes gleich verschlüsselt.
Für möglichst viele ,,lange'' (mind. 3) Wörter, die im Chiffretext mehrfach auftreten, notiere die Abstände des Auftretens. Dann suche ein großes s, das viele dieser Abstände teilt (nicht unbedingt alle).
\begin{itemize*}
\item Der Test funktioniert nur gut, wenn die Schlüssellänge s gering im Verhältnis zur Chiffretextlänge l ist.
\item Um ihn anwenden zu können, muss die Klartextsprache bekannt sein.
\item Der Test kann auch in der viel allgemeineren Situation benutzt werden, in der Schlüssel nicht s Verschiebungen, sondern s beliebige Substitutionschiffren auf $X$
\end{itemize*}
Was passiert im Extremfall $s=l$?
\begin{itemize*}
\item Grundsätzlich informationstheoretisch sicheres one-time pad ...
\item ... aber nur dann, wenn die Schlüssel gleichverteilt gewählt werden. Wenn der Schlüssel selbst ein Text ist, so weist der Chiffretext wieder statistische Merkmale auf, die zum Brechen ausgenutzt werden können.
\end{itemize*}
Effektive Verfahren der Schlüsselverlängerung (keine informationstheoretische Sicherheit)
\begin{itemize*}
\item Autokey-Vigenère: Schlüssel k, Klartext m. Dann wird klassische Vigenère-Chiffre mit Schlüssel km auf m angewendet.
\item Pseudozufallszahlen: Geheimer Schlüssel ist seed eines (Pseudo-)Zufallszahlengenerators, mit dem eine lange Schlüsselfolge $k_0,...,k_{l-1}$ erzeugt wird.
\end{itemize*}
\subsubsection{Koinzidenzindex und Friedman-Methode}
Die Methode beruht darauf, dass die Buchstabenhäufigkeiten fest stehen und sich bei der Verschlüsselung mit einer einfachen Substitutionschiffre nicht ändert. Ebenso ändert sich nicht die Wahrscheinlichkeit, bei der zufälligen Wahl eines Buchstabenpaars zwei identische Buchstaben zu erhalten.
Sei $x=x_0...x_{l-1}$ ein Klartext, sei $y=y_0...y_{l-1}$ der zugehörige Chiffretext, bei $s=1$ (an jeder Stelle derselbe Schlüssel). Seien $n_0,...,n_{25}$ die Anzahlen der Buchstaben $a,...,z$ in $x,n'_0,...,n'_25$ die in $y$. Wir wählen zufällig ein Paar von zwei Positionen in x (ohne ,,Zurücklegen''). Dafür gibt es $\binom{l}{2}$ Möglichkeiten. Genau $\binom{n_i}{2}$ viele davon führen dazu, dass man zweimal den Buchstaben Nummer i zieht, und $\sum_{0\geq i<26}\binom{n_i}{2}$ viele führen dazu, dass man an den beiden Positionen denselben Buchstaben sieht. Wir setzen $IC(x):=\frac{\sum_{0\geq i<26}\binom{n_i}{2}}{\binom{l}{2}}=\frac{\sum_{0\leq i<26}n_i(n_i-1)}{l(l-1)}$.
Diese Zahl nennt man den Koinzidenzindex von x. Sie ist die Wahrscheinlichkeit dafür, dass an den beiden zufällig gewählten Positionen der selbe Buchstabe steht. Weil die Verschlüsselung auf den Buchstaben eine Bijektion ist, also sich die vorkommenden Häufigkeiten durch die Verschlüsselung nicht ändern, gilt für $IC(y):=\frac{\sum_{0\geq i<26} n'_i(n'_i -1)}{l(l-1)}$ die Gleichung $IC(x)=IC(y)$.
Für lange Texte mit Häufigkeitsverteilung der Buchstaben nähert sich $IC(x)$ einem bestimmten Wert an. Wenn $p_i$ die Häufigkeit von Buchstabe i in der verwendeten Sprache ist, wird für lange Texte x die Näherung $\frac{n_i}{l}\approx\frac{n_i-1}{l-1}\approx p_i$ gelten, also $IC(x)\approx \sum_{0\geq i<26} p^2_i$ sein. Die Summe $\sum_{0\geq i<26} p^2_i$ hat beispielsweise einen Wert von etwa $0,076$ für deutsche und $0,066$ für englische Texte. %Wenn (in einer fiktiven Sprache) jeder Buchstabe dieselbe Wahrscheinlichkeit hat, ist $\sum_{0\geq i<26} p^2_i= 26*(\frac{1}{26})^2=\frac{1}{26}\approx 0,0385$; dies ist zugleich der minimal mögliche Wert.
Für die Ermittlung eines Schätzwertes für die Schlüssellänge s gehen wir wie folgt vor. Wir nehmen an, die zugrunde liegende Sprache ist Deutsch. Wir berechnen zunächst $IC(y)$ für den Chiffretext y. Die unbekannte Schlüssellänge nennen wir s. Dann berechnen wir eine Näherung für $IC(y)$, auf eine zweite Weise. Dies wird uns eine (Näherungs-)Gleichung für s liefern.
Bilde die Teilwörter $y^0,...,y^{s-1}$, jedes mit der Länge $\frac{l}{s}$. Innerhalb jedes Teilworts kommen Kollisionen ebenso häufig vor wie in einem gewöhnlichen Text mit nur einem Schlüssel, also erwarten wir zusammen $\binom{l/s}{2} IC(y^0)+...+\binom{l/s}{2} IC(y^{s-1})\approx\frac{1}{2}l(l/s-1)* 0,076$ viele ,,Kollisionen'' (Paare identischer Chiffretextbuchstaben) aus den einzelnen Teilwörtern.
Zwischen zwei Teilwörtern $y^u$ und $y^v$ erwarten wir $(l/s)^2*261\approx 0,0385(l/s)^2$ Kollisionen, aus allen $\binom{s}{2}$ Paaren von Teilwörtern zusammen also $\binom{s}{2} 0,0385(l/s)^2 =\frac{s(s-1)}{2}* 0,0385(l/s)^2 =\frac{1}{2} *0,0385 l^2 (1-\frac{1}{s})$ viele. Zusammen ist die erwartete Anzahl an Kollisionen in y gleich $\frac{1}{2}l(0,076(l/s-1) + 0,0385 l(1-\frac{1}{s}))$.
Diese Zahl sollte näherungsweise gleich $\frac{1}{2}l(l-1)IC(y)$ sein. Wir können die resultierende Gleichung $(l-1)IC(y) = 0,076(l/s-1) + 0,0385 l(1-\frac{1}{s})$ nach s auflösen und erhalten: $s\approx \frac{(0,076-0,0385)l}{(l-1)IC(y)-0,0385l+0,076}$.
Eine tatsächliche Durchführung des Verfahrens mit Chiffretexten erfordert viel Geduld.
\section{Frische Verschlüsselung und Blockchiffren}
Szenarium 2 (frische sym. Verschlüsselung): Alice möchte Bob mehrere verschiedene Klartexte vorher bekannter und begrenzter Länge übermitteln. Sie verwendet dafür immer denselben Schlüssel. Eva hört die Chiffretexte mit und kann sich sogar einige Klartexte mit dem verwendeten Schlüssel verschlüsseln lassen (chosen-plaintext attack).
Bemerkung: Das informationstheoretisch sichere Vernam-Kryptosystem ist nutzlos: Aus Kenntnis von $x\in\{0,1\}^l$ und $y=e(x,k)$ für ein einziges Paar $(x,k)\in X\times K$ kann Eva den Schlüssel $k=x\oplus_l y$ berechnen. Gleiches gilt für das Cäsar-System und das Vigenère-System.
\textbf{Definition} Ein Kryptosystem $S=(X,K,Y,e,d)$ ist possibilistisch sicher bzgl. Szenarium 2, wenn für jedes $1 \leq r\leq |X|$, jede Folge von paarweise verschiedenen Klartexten $x_1,x_2,...,x_r\in X$, jeden Schlüssel $k\in K$ und jedes $y\in Y\backslash\{e(x_i,k)| 1 \leq i < r\}$ ein Schlüssel $k'\in K$ existiert mit $e(x_i,k)=e(x_i,k')$ für alle $1\leq i< r$ und $e(x_r,k')=y$.
\textbf{Proposition} Für jede nichtleere Menge $X$ ist das Substitutionskryptosystem auf X possibilistisch sicher.
\textbf{Proposition} Sei $S=(X,K,Y,e,d)$ ein Kryptosystem, das possibilistisch sicher ist bzgl. Szenarium 2. Dann ist $\{e(.,k)|k\in K\}$ die Menge aller injektiven Abbildungen von X nach Y.
Ein Kryptosystem, das possibilistisch sicher bzgl. Szenarium 2 ist, hat mindestens $|\{\pi |\pi :X\rightarrow Y\text{ ist injektiv}\}|=\frac{|Y|!}{(|Y|-|X|)!} \geq |X|!$ Schlüssel. Mit $X=\{0,1\}^{128}$ gibt es $\geq 2^{128}!$ viele Schlüssel. Für die Speicherung eines Schlüssels braucht man durchschnittlich (Es gilt $log_2(N!)>N(log_2 N-log_2 e)> N(log_2 N- 1.45)$) $log(2^{128}!)> 2^{128}*(128- 1.45)> 2^{134}>(10^3 )^{13.4} > 10^{40}$ viele Bits, eine unpraktikable Zahl. Also können wir in realen Situationen im Szenarium 2 keine possibilistische Sicherheit, geschweige denn informationstheoretische Sicherheit erhalten.
\textbf{Definition} Sei $l>0$. Ein l-Block-Kryptosystem ist ein Kryptosystem $S=(\{0,1\}^l,K,\{0,1\}^l,e,d)$ mit $K\subseteq \{0,1\}^s$ für ein $s>0$.
\subsection{Substitutions-Permutations-Kryptosysteme (SPKS)}
Grundsätzlich handelt es sich um $mn$-Block-Kryptosysteme. Dabei werden die Klartexte $x=(x_0,...,x_{mn-1})\in\{ 0,1\}^{mn}$ als m-Tupel $(x^{(0)},x^{(1)},...,x^{(m-1)})$ von Bitvektoren der Länge n betrachtet. Dabei gilt $x(i)=(x_{in},x_{in+1},...,x_{(i+1)n-1})$, für $0\leq i<m$.
Ein Baustein der Verschlüsselungs- und Entschlüsselungsfunktion bei diesen Systemen sind Bitpermutationen auf Bitstrings der Länge l. Sei $\beta$ eine Permutation von $\{0,...,l-1\}$ und $x\in\{0,1\}^l$. Dann bezeichnet $x^{\beta}$ den Bitvektor $(x_{{\beta}(0)},x_{{\beta}(1)},...,x_{{\beta}(l-1)})$.
Kurz: $x^{\beta}_{(i)}=x_{{\beta}(i)}$, für $0\leq i<l$.
Sehr oft werden wir annehmen, dass $\beta$ selbst invers ist, dass also ${\beta}^{-1}=\beta$ ist für $0\leq i<l$). Dann erhält man $x^{\beta}$ aus x, indem man $x(i)$ an die Stelle ${\beta}(i)$ des neuen Vektors schreibt.
\textbf{Definition} Ein Substitutions-Permutations-Netzwerk (SPN) ist ein Tupel $N=(m,n,r,s,S,\beta,\kappa)$ wobei
\begin{itemize*}
\item positive ganzen Zahlen $m,n,r$ und $s$ die Wortanzahl, Wortlängen, Rundenzahl und Schlüssellänge
\item $S:\{0,1\}^n\rightarrow\{0,1\}^n$ eine bijektive Funktion (S-Box)
\item ${\beta}:\{0,...,mn-1\}\rightarrow\{0,...,mn-1\}$ selbstinverse Permutation (Bitpermutation)
\item $\kappa :\{0,1\}s\times\{0,...,r\}\rightarrow\{0,1\}^{mn}$ Rundenschlüsselfunktion
\end{itemize*}
Das zu N gehörende Substitutions-Permutations-Kryptosystem (SPKS) ist das mn-Block-Kryptosystem $B(N)=(\{0,1\}^{mn},\{0,1\}^s,\{0,1\}^{mn},e,d)$, das durch folgende Operationen beschrieben ist:
Chiffrierung: $e(x,k)$ wird für $x\in\{0,1\}^{mn}$ und $k\in\{0,1\}^s$ wie folgt berechnet:
\begin{enumerate*}
\item Initialisierung (,,Weißschritt''): Berechne $u=x\oplus_{mn} \kappa (k,0)$.
\item Verschlüsselung in Runden: für $i=1,...,r-1$ berechne
\begin{enumerate*}
\item $v(j)=S(u(j))$ für $0\leq j<m$ (jedes Wort einzeln durch die S-Box)
\item $w=v^{\beta}$ (Bitpermutation auf dem Gesamtwort der Länge mn)
\item $u=w\oplus_{mn} \kappa (k,i)$ (XOR mit dem Rundenschlüssel)
\item Schlussrunde: $v(j)=S(u(j))$ für $0\leq j<m$
\item Ausgabe: $y=v\oplus \kappa (k,r)$ (ohne Bitpermutation)
\end{enumerate*}
\end{enumerate*}
Dechiffrierung: $d(y,k)$ wird aus y und k nach demselben Verfahren berechnet, wobei jedoch
\begin{enumerate*}
\item die S-Box durch ihre Inverse $S^{-1}$ ersetzt wird und
\item die Rundenschlüsselfunktion $\kappa$ ersetzt wird durch die Funktion $\kappa':\{0,1\}^s\times\{0,...,r\}\rightarrow\{0,1\}^{mn}$, $(k,i)\rightarrow\begin{cases} \kappa (k,r-i)\quad\text{ für } i\in\{0,r\}\\ \kappa(k,r-i)^{\beta} \quad\text{ für } 0<i<r \end{cases}$
\end{enumerate*}
Vorteil der Struktur: Man kann dieselbe Hardware für Verschlüsselung und Entschlüsselung benutzen. Bei der Entschlüsselung läuft der Vorgang rückwärts ab, wobei die Runden anders gruppiert sind. Anstelle von S verwendet man $S^{-1}$. Da $\beta$ selbst invers ist, kann man für die Permutation auch bei der Dekodierung $\beta$ verwenden. Da Permutation und Schlüsselanwendung in den Runden vertauscht sind, muss man auf die Rundenschlüssel der ,,inneren'' Runden bei der Dekodierung auch noch $\beta$ anwenden.
\textbf{Beispiel} Wortanzahl $m=3$, Wortlänge $n=4$, Rundenzahl $r=3$, Schlüssellänge $s=24=6*n$ und $\kappa (k,i)=k^{(i)}k^{(i+1)}k^{(i+2)}$. Die Bitpermutation $\beta$ vertauscht die Bits $(0,4),(1,5),(2,8),(3,9),(6,10)$ und $(7,11)$ und ist damit selbst invers. Die S-Box ist gegeben durch die folgende zweizeilige Tabelle
\begin{tabular}{c|c|c|c|c|c|c|c|c}
b & 0000 & 0001 & 0010 & 0011 & 0100 & 0101 & 0110 & 0111 \\
S(b) & 0101 & 0100 & 1101 & 0001 & 0011 & 1100 & 1011 & 1000 \\\hline
b & 1000 & 1001 & 1010 & 1011 & 1100 & 1101 & 1110 & 1111 \\
S(b) & 1010 & 0010 & 0110 & 1111 & 1001 & 1110 & 0000 & 0111
\end{tabular}
Für $x= 0000 1111 0000$ und $k=0000 0001 0010 0011 0100 0101$ ergeben sich
\begin{enumerate*}
\item $\kappa (k,0) = 0000 0001 0010$ und damit $u= 0000 1110 0010$
\item $i=1$ $v=0101 0000 1101$, $w=0011 0101 0100$, $\kappa (k,1) = 0001 0010 0011$ und $u=0010 0111 0111$
\item $i=2$ $v=1101 1000 1000$, $w=1010 1100 0100$, $\kappa (k,2) = 0010 0011 0100$ und damit $u= 1000 1111 0000$
\item $v=1010 0111 0101$, $\kappa (k,3) = 0011 0100 0101$ und damit $y=1001 0011 0000$
\end{enumerate*}
\subsubsection{Einschub: Endliche Körper}
Die Struktur $\mathbb{Z}_2=(\{0,1\},\oplus,\odot, 0 ,1)$ ist ein Körper, wobei $\oplus$ für die XOR-Operation und für $\wedge$ (AND) steht.
Zu einem endlichen Körper $F$ bildet man den Polynomring $F[X]$. Ein solcher Ausdruck wird mit seiner Koeffizientenfolge $(...,0,0,a_n,...,a_1,a_0)$ identifiziert. Normalerweise lässt man Terme mit Koeffizient 0 weg. Über $\mathbb{Z}_2$ schreibt man wie üblich oft nur den Bitstring $a_n...a_1a_0$ ohne Klammern und Kommas.
Beispiel: In $\mathbb{Z}_2[X]$ liegen die Polynome $g=01011=(..., 0 , 1 , 0 , 1 ,1) =X^3 +X+1$ und $h=0110=(..., 0 , 1 , 1 ,0) =X^2 +X$.
Der Grad eines solchen Polynoms ist n, wenn n maximal mit $a_n\not = 0$ ist. Falls alle Koeffizienten gleich 0 sind ist der Grad $-\infty$. Man addiert und subtrahiert solche Polynome wie üblich und multipliziert sie wie üblich.
Beispiel: Die Summe von g und h ist $g+h=01101=(...,0,1,1,0,1)$, ihr Produkt ist $g*h=X^5+X^4+X^3+X=(...,0,0,1,1,1,0,1,0)=111010$.
Mit diesen Operationen erhält $F[X]$ die Struktur eines Rings: Die Addition ist Gruppe mit neutralem Element 0, die Multiplikation ist assoziativ mit neutralem Element $1=(...,0,0,0,1)$, die Distributivgesetze gelten.
Als Grundmenge des zu konstruierenden Körpers verwenden wir $F^k$, die Menge aller k-Tupel über F. Dies entspricht der Menge aller Polynome vom Grad bis zu $k-1$. Diese Menge hat genau $|F|^k$ Elemente. Im Fall $F=\mathbb{Z}_2$ erhalten wir $\{0,1\}^k$, die Menge aller Bitstrings der Länge k.
Als Addition $\oplus$ benutzen wir die gewöhnliche Addition von Polynomen, also die komponentenweise Addition der Tupel. Bei $F=\mathbb{Z}^k_2$ ist dies einfach das bitweise XOR. Wir geben die Additionstafel für $k=4$ an. Die Elemente des Körpers $GF(2^4)$ werden dabei wir üblich als Hexadezimalziffern geschrieben: $5\oplus C=0101\oplus 1100=1001=9$.
Die Multiplikation $\odot$ ist etwas komplizierter. Es wird ein irreduzibles Polynom $f=X^k+a_{k-1}* X^{k-1}+...+a_1*X+a_0$ vom Grad k (mit ,,Leitkoeffizient'' $a_k=1$) benötigt, also ein Koeffiziententupel $(1,a_{k-1},...,a_1,a_0)$ mit der Eigenschaft, dass man nicht $f=f_1*f_2$ schreiben kann, für Polynome $f_1$ und $f_2$, die Grad $\geq 1$ haben. Man kann zeigen, dass es für jedes $k\geq 2$ stets solche Polynome gibt. Sie können mit randomisierten Algorithmen effizient gefunden werden. Hier einige Beispiele für $F=\mathbb{Z}_2$. Wie üblich schreibt man die Koeffizientenfolge als Bitstring. Dieser Bitstring kann dann auch als natürliche Zahl (dezimal geschrieben) interpretiert werden.
\begin{tabular}{c|c|c|c}
k & irreduzibles Polynom vom Grad k über $\mathbb{Z}_2$ & Kurzform & Zahl \\\hline
1 & $X+ 1$ & 11 & 3 \\
2 & $X^2 +X+ 1$ & 111 & 7 \\
3 & $X^3 +X+ 1$ & 1011 & 11 \\
4 & $X^4 +X+ 1$ & 10011 & 19 \\
5 & $X^5 +X^2 + 1$ & 100101 & 37 \\
6 & $X^6 +X+ 1$ & 1000011 & 67 \\
7 & $X^7 +X^3 + 1$ & 10001001 & 137 \\
8 & $X^8 +X^4 +X^3 +X+ 1$ & 100011011 & 283
\end{tabular}
Das Polynom $X^2+1=(1,0,1)=101$ ist nicht irreduzibel, da über $\mathbb{Z}_2$ die Gleichung $(X+1)*(X+1)=X^2+1$ gilt.
Die Multiplikation funktioniert nun wie folgt: Wenn g und h gegeben sind, berechnet man das Prddukt $g*h$ (Grad maximal $2k-2$) und bestimmt den Rest $r$ von $g*h$ bei der Division durch $f$. Dieser Rest (genannt ,,$g*h mod f$'') ist das eindeutig bestimmte Polynom r vom Grad höchstens $k-1$, das $g*h=q*f+r$ erfüllt, für ein ,,Quotientenpolynom'' q.
Beispiel: Sei $k=4$ und $f=(1,0,0,1,1)=10011$. Die Faktoren seien $g=(1,0,1,1)=1011$ und $h=(0,1,1,0)=110$. Das Produkt ist $g*h=(1,1,1,0,1,0)=111010$. Wenn wir hier von $f*(X+1)=(1,1,0,1,0,1)=110101$ subtrahieren, erhalten wir das Produkt $(1,1,1,1)=1111$ im Körper.
Man kann durch geduldiges Multiplizieren und Bilden von Resten (also Dividieren von Polynomen) in dieser Weise eine komplette Multiplikationstabelle aufstellen. Geschickter ist Folgendes: Man berechnet alle Produkte $g*h mod f$, für die in g und in h jeweils die ersten beiden Bits oder die letzten beiden Bits 0 sind. (Wenn man beobachtet, dass $(0,0,0,1)=0001$ das neutrale Element ist, und die Kommutativität berücksichtigt, muss man nur 15 Produkte berechnen.) Es ergibt sich die folgende Tabelle.
\begin{tabular}{c|c|c|c|c|c|c|c}
$\odot$ & 0000 & 0001 & 0010 & 0011 & 0100 & 1000 & 1100 \\\hline
0000 & 0000 & 0000 & 0000 & 0000 & 0000 & 0000 & 0000 \\
0001 & 0000 & 0001 & 0010 & 0011 & 0100 & 1000 & 1100 \\
0010 & 0000 & 0010 & 0100 & 0110 & 1000 & 0011 & 1011 \\
0011 & 0000 & 0011 & 0110 & 0101 & 1100 & 1011 & 0111 \\
0100 & 0000 & 0100 & 1000 & 1100 & 0011 & 0110 & 0101 \\
1000 & 0000 & 1000 & 0011 & 1011 & 0110 & 1100 & 1010 \\
1100 & 0000 & 1100 & 1011 & 0111 & 0101 & 1010 & 1111
\end{tabular}
Wir notieren weiterhin Bitstrings $(a_3,a_2,a_1,a_0)=a_3a_2a_1a_0$ hexadezimal. Das Polynom $g=(1,0,1,1)=1011$ ist also $B=1000\oplus 0011=8\oplus 3$, das Polynom $h=(0,1,1,0)=0110$ ist $6=0100\oplus 0010=4\oplus 2$.
Die Tabelle sieht dann so aus:
\begin{tabular}{c|c|c|c|c|c|c|c|c}
$\odot$ & 0 & 1 & 2 & 3 & 4 & 8 & C \\\hline
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
1 & 0 & 1 & 2 & 3 & 4 & 8 & C \\
2 & 0 & 2 & 4 & 6 & 8 & 3 & B \\
3 & 0 & 3 & 6 & 5 & C & B & 7 \\
4 & 0 & 4 & 8 & C & 3 & 6 & 5 \\
8 & 0 & 8 & 3 & B & 6 & C & A \\
C & 0 & C & B & 7 & 5 & A & F
\end{tabular}
Nun wollen wir beliebige Polynome multiplizieren. Beispiel: Um $g=(1,0,1,1)=1011=B$ und $h=(0,1,1,0)=0110=6$ zu multiplizieren, rechnet man unter Benutzung der Tabelle und des Distributivgesetzes wie folgt (Multiplikation modulo f):
$B\odot 6=(8\oplus 3)(4\oplus 2)=(8\odot 4)\oplus(8\odot 2)\oplus(3\odot 4)\oplus(3\odot 2)=6\oplus 3\oplus C\oplus 6= 0110\oplus 0011 \oplus 1100 \oplus 0110 = 1111 = F$.
Mit etwas Geduld und unter Ausnutzung des Distributivgesetzes lässt sich auf diese Weise die folgende Multiplikationstabelle für die Elemente von $\mathbb{Z}^4_2$ finden.
\begin{tabular}{c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c}
& 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & A & B & C & D & E & F \\\hline
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
1 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & A & B & C & D & E & F \\
2 & 0 & 2 & 4 & 6 & 8 & A & C & E & 3 & 1 & 7 & 5 & B & 9 & F & D \\
3 & 0 & 3 & 6 & 5 & C & F & A & 9 & B & 8 & D & E & 7 & 4 & 1 & 2 \\
4 & 0 & 4 & 8 & C & 3 & 7 & B & F & 6 & 2 & E & A & 5 & 1 & D & 9 \\
5 & 0 & 5 & A & F & 7 & 2 & D & 8 & E & B & 4 & 1 & 9 & C & 3 & 6 \\
6 & 0 & 6 & C & A & B & D & 7 & 1 & 5 & 3 & 9 & F & E & 8 & 2 & 4 \\
7 & 0 & 7 & E & 9 & F & 8 & 1 & 6 & D & A & 3 & 4 & 2 & 5 & C & B \\
8 & 0 & 8 & 3 & B & 6 & E & 5 & D & C & 4 & F & 7 & A & 2 & 9 & 1 \\
9 & 0 & 9 & 1 & 8 & 2 & B & 3 & A & 4 & D & 5 & C & 6 & F & 7 & E \\
A & 0 & A & 7 & D & E & 4 & 9 & 3 & F & 5 & 8 & 2 & 1 & B & 6 & C \\
B & 0 & B & 5 & E & A & 1 & F & 4 & 7 & C & 2 & 9 & D & 6 & 8 & 3 \\
C & 0 & C & B & 7 & 5 & 9 & E & 2 & A & 6 & 1 & D & F & 3 & 4 & 8 \\
D & 0 & D & 9 & 4 & 1 & C & 8 & 5 & 2 & F & B & 6 & 3 & E & A & 7 \\
E & 0 & E & F & 1 & D & 3 & 2 & C & 9 & 7 & 6 & 8 & 4 & A & B & 5 \\
F & 0 & F & D & 2 & 9 & 6 & 4 & B & 1 & E & C & 3 & 8 & 7 & 5 & A
\end{tabular}
Das neutrale Element der Multiplikation ist das Polynom $1=(0,..., 0 ,1) = 0... 01$. Man beobachtet, dass in jeder Zeile (und ebenso in jeder Spalte) der Tabelle, außer der für das Nullpolynom, alle Elemente genau einmal vorkommen. Dies ist für jeden Körper F und jedes beliebige k so, und es folgt daraus, dass die Elemente der Menge $F^k-\{0\}$ ein Inverses haben.
Fakt: Wenn man die Multiplikation wie beschrieben definiert, mit einem irreduziblen Polynom f mit Leitkoeffizient $a_k=1$, dann gibt es für jedes Polynom $g\not=(0,...,0)$ vom Grad $<k$ (genau) ein Polynom h mit $g*h\ mod\ f=(0,...,0,1)=1$. Dieses Polynom h ist also $g^{-1}$, das multiplikative Inverse von g.
(Beweisidee: Man zeigt, dass die Abbildung $h\rightarrow g*h\ mod\ f$ in der Menge dieser Polynome injektiv ist. Ist $h_1*g\ mod\ f=h_2*g\ mod\ f$, so ist $(h_1-h_2)*g\ mod\ f= 0$, also ist $(h_1-h_2)*g$ durch f teilbar. Nach einem Lemma über irreduzible Polynome (analog zur Situation bei Primzahlen) folgt, dass f Teiler von $h_1-h_2$ oder Teiler von g sein muss. Weil $g$ nicht das Nullpolynom ist und Grad $<k$ hat, kann f kein Teiler von g sein. Also teilt f das Polynom $h_1-h_2$. Da auch dieses Grad $<k$ hat, muss $h_1-h_2$ das Nullpolynom sein, also $h_1=h_2$ gelten. Aus der Injektivität von $h\rightarrow g*h\ mod\ f$ folgt die Surjektivität, also gibt es ein $h$ mit $g*h\ mod\ f=1$.)
Weil die üblichen Rechenregeln in der Struktur $(F^k,\oplus,\odot,0,1)$ mit den angegebenen Operationen leicht nachzuweisen sind, bedeutet dies, dass wir einen Körper mit $|F|^k$ Elementen erhalten haben. Wir nennen ihn $F[X]/(f)$, für das gewählte irreduzible Polynom $f$ vom Grad $k$. Wenn $|F|^k=q$ ist, nennen wir diesen Körper $GF(q)$. Im Fall $F=\mathbb{Z}_2$ erhalten wir so Körper $GF(2^k)$, deren zugrunde liegende Menge einfach $\{0,1\}^k$ ist, die Menge der Bitstrings der Länge k.
Bemerkung: In der Algebra zeigt man folgende Fakten über endliche Körper:
\begin{itemize*}
\item Es gibt einen endlichen Körper $GF(q)$ mit $q$ Elementen genau dann wenn $q=p^r$ für eine Primzahl p und einen Exponenten $r\geq 1$.
\item Es ist gleichgültig, auf welchem Konstruktionsweg man zu einem Körper mit $q$ Elementen gelangt: alle diese Körper sind isomorph, also strukturell identisch. (Insbesondere ist der Körper $GF(2^k)$ immer ,,der gleiche'' , ganz egal welches irreduzible Polynom f man benutzt.) Die Tabellen für die Operationen können eventuell unterschiedlich aussehen, aber nur aufgrund von Umbenennungen von Objekten.
\end{itemize*}
Ab hier schreiben wir $+$ für die Körperaddition und $*$ für die Körpermultiplikation.
Bemerkungen zur Zeit- und Platzeffizienz: Allgemein, und für beliebig große k, kann man für ein festes Polynom f den Rest der Division durch f stets als Produkt des Zeilenvektors, der $g*h$ darstellt, mit einer festen $((2k-1)\times k)$-Matrix $M_f$ erhalten.
Damit ist die Komplexität der Multiplikation in einem solchen Körper definiert: Es muss das Produkt $g*h$ berechnet werden (,,Konvolution'' von zwei Bitvektoren) und dann eine Vektor-Matrix-Multiplikation ausgeführt werden. Über dem Körper $\mathbb{Z}_2$ lässt sich die Vektor-Matrix-Multiplikation mit Hilfe der wortweisen XOR-Operation sehr effizient durchführen. Wenn zusätzlich $f$ nur wenige Terme hat, hat $M_f$ nur wenige 1-Einträge und die Matrix-Vektor-Multiplikation läuft auf einer Addition weniger Shifts eines Vektors hinaus. Für die Konvolution ist effiziente Ausführung etwas schwieriger; es gibt aber moderne Prozessoren, die diese Operation für konstante Wortlängen bereitstellen, was diese Operation auch für beliebige Wortlängen beschleunigt.
Wenn die Bitlänge $k$ kurz und bekannt ist, wird man Tabellen benutzen. (Zum Beispiel benutzt AES einen Körper der Größe 256.) Für die Multiplikation verwendet man auch gerne Potenz- und Logarithmentabellen.
Fakt 2.7 Sei F ein endlicher Körper mit $q$ Elementen. Dann gibt es in F ein ,,primitives Element'' g, d.h., g erfüllt $\{g^i| 0 \geq i < q-1\}=F-\{0\}$. (g ist erzeugendes Element der multiplikativen Gruppe von F.)
Beispiel: Wir hatten oben eine Multiplikationstabelle für $GF(2^4)$ aufgestellt. Mit ihrer Hilfe findet man leicht die ersten 15 Potenzenvon 2:
Potenztabelle:
\begin{tabular}{c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c}
i & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 \\\hline
$exp_2(i)=2^i$ & 1 & 2 & 4 & 8 & 3 & 6 & C & B & 5 & A & 7 & E & F & D & 9
\end{tabular}
Diese Potenzen sind alle verschieden, also ist $g=2$ primitives Element. Die entsprechende Logarithmentab elle sieht so aus:
\begin{tabular}{c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c}
x & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & A & B & C & D & E & F \\\hline
& $log_2(x)$ & 0 & 1 & 4 & 2 & 8 & 5 & 10 & 3 & 14 & 9 & 7 & 6 & 13 & 11 12
\end{tabular}
Achtung: Der Index der Exponential- und der Logarithmenfunktion ist nicht die natürliche Zahl 2, sondern 2, das ist das Element $X=0010$ von $GF(2^4)$.
Allgemein: Wenn $g$ primitives Element ist, dann betrachtet man die Exponentialfunktion zur Basis $g$: $exp_g:\mathbb{Z}\in i\rightarrow g^i\in F-\{0\}$.
Diese ist periodisch: Wenn $i-j$ durch $q-1$ teilbar ist, dann ist $g^i=g^j$. Es genügt also, die Werte $g^i$ für $0\geq i<q-1$ zukennen. Man erstellt eine Tabelle mit diesen $q-1$ Werten.
Die Umkehrfunktion ist die Logarithmusfunktion $log_g$ zur Basis $g$. Sie ordnet jedem $x\in F-\{0\}$ den (eindeutig bestimmten) Wert $i\in\{0,1,...,q-2\}$ mit $x=g^i$ zu, genannt $log_g(x)$. Es gilt $log_g(g^i)=i$ für $i\in\{0,1,...,q-2\}$ und $g^{log_g(x)}=x$ für alle $x\in F-\{0\}$. Man erstellt ebenfalls eine Tabelle mit diesen Werten.
Nun kann man leicht multiplizieren.
Aufgabe: Berechne $z=x*y$.
Falls $x=0$ oder $y=0$ in $F$, ist $z=0$. Andernfalls schaue in die log-Tabelle, um $i=log_g(x)$ und $j=log_g(y)$ zu finden. Berechne $k=(i+j)\ mod\ (q-1)$. Das Ergebnis $z=g^k$ liest man nun in der exp-Tabelle an Stelle $k$ ab.
Beispiel: In $GF(2^4)$ seien $x=9$ und $y=C$ gegeben. Die $log_2$-Tabelle liefert $i=log_2(9)=14$ und $j=log_2(C)=6$. Wir erhalten $k= (14+6)\ mod\ 15 = 5$ und $z=g^5=6$ mit der $exp_2$-Tabelle. Man kontrolliert mit der Multiplikationstabelle für $GF(2^4)$, dass dort tatsächlich $9*C=6$ gilt.
Aufwand für eine Multiplikation: Drei Zugriffe auf Tabellen, eine modulare Addition!
Der Rechenaufwand für die Erstellung der Tabellen und auch ihr Platzbedarf ist $O(q)$ und damit akzeptabel, wenn $q$ nicht zu groß ist. Im Fall von $q=256$ hat man zwei Tabellen mit je $255$ Einträgen und kann damit sehr leicht in konstanter Zeit multiplizieren. Auch Tabellen für $q=2\frac{1}{6}=65536$ stellen weiter kein Problem dar. Für noch größere $q$ benötigt man weitere Tricks zum Ermitteln diskreter Logarithmen mit Hilfe von Tabellen der Größe etwa $\sqrt{q}$. (Wir werden später darauf zurückkommen.) Sollte $q$ sehr groß werden (Hunderte oder Tausende von Bits), wird man, wie oben skizziert, Konvolution und Matrix-Vektor-Multiplikation benutzen.
\subsubsection{AES: Advanced Encryption Standard}
Der ,,Advanced Encryption Standard(AES)'' ist ein symmetrisches Verschlüsselungsverfahren (d.h., beide Kommunikationspartner benutzen denselben Schlüssel). AES wird in vielen Standardverfahren beider Kommunikation im Internet benutzt, zum Beispiel bei Secure Socket Layer (SSL)/Transport Layer Security (TLS) und bei Secure Shell (SSH).
Die AES-Chiffren gehören in die Klasse der Substitutions-Permutations-Kryptosysteme, auch wenn es in Details Abweichungen von der in Abschnitt 2.1 vorgestellten Struktur gibt. Bei der standardisierten Version AES ist die Klartextlänge und Chiffretextlänge stets $l= 128$, die Schlüssellänge $128,192$ oder $256$ Bits. Wir konzentrieren uns auf die Variante mit Klartextlänge $128$, Schlüssellänge $128$. AES umfasst einige Spezialfälle der Rijndael-Familie von Chiffren, mit der Klartexte der Länge 128, 160,192, 224 oder 256 Bits ver- und entschlüsselt werden können.
In AES wird Arithmetik im Körper $GF(2^8)$ benutzt, dessen Elemente $8$-Bit-Vektoren, also Bytes, entsprechen.
Klartext und alle Zwischenergebnisse beider Ver- und Entschlüsselung sind Strings aus 128 Bits, die als 16 Wörter von 8 Bit Länge aufgefasst werden (1 Wort= 1 Byte= 2 Hexziffern). Die Bytes werden als Elemente von $GF(2^8)$ aufgefasst, konstruiert aus $\mathbb{Z}_2$ mit irreduziblem Polynom $f(X) =X^8 +X^4 +X^3 +X+ 1 (= (1, 0 , 0 , 0 , 1 , 1 , 0 , 1 ,1) )$.
Die 16 Bytes werden als $4\times 4$-Matrix (mit Einträgen aus $GF(2^8)=GF(256)$) aufgefasst. Die Leseanordnung ist dabei spaltenweise von links nach rechts, wobei Spalten von oben nach unten gelesen werden. Ein Bitstring $z\in\{0,1\}^{128}$ wird also in 16 Bytes $z^{(0)},z^{(1)},...,z^{(15)}$ mit $z=z^{(0)}z^{(1)}...z^{(15)}$ aufgeteilt und wie folgt als Matrix $A(z)\in(\{0,1\}^8)^{4\times 4}$ geschrieben: $A(z) =\begin{pmatrix} z^{(0)}& z^{(4)}& z^{(8)}& z^{(12)} \\ z^{(1)}& z^{(5)}& z^{(9)}& z^{(13)} \\ z^{(2)}& z^{(6)}& z^{(10)}& z^{(14)} \\ z^{(3)}& z^{(7)}& z^{(11)}& z^{(15)} \end{pmatrix}$.
Die Einträge einer solchen Matrix sind mit $0\geq i,j\geq 3$ indiziert, wie folgt: $A=\begin{pmatrix} A_{00}& A_{01}& A_{02}& A_{03}\\ A_{10}& A_{11}& A_{12}& A_{13}\\ A_{20}& A_{21}& A_{22}& A_{23}\\ A_{30}& A_{31}& A_{32}& A_{33}\end{pmatrix}$.
Aus jeder solchen Matrix ergibt sich durch spaltenweises Auslesen wieder ein Bitstring $A_{00} A_{10} A_{20} A_{30} A_{01} A_{11} A_{21} A_{31} A_{02} A_{12} A_{22} A_{32} A_{03} A_{13} A_{23} A_{33}$.
Abkürzungen für Zeilen und Spalten einer Matrix A:
\begin{itemize*}
\item Zeile $i: row_i(A)=(A_{i0},A_{i1},A_{i2} ,A_{i3})$, für $i=0,1,2,3$.
\item Spalte $j:col_j(A)=\begin{pmatrix} A_{0j}\\ A_{1j}\\ A_{2j}\\ A_{3j} \end{pmatrix}$, für $j=0,1,2,3$.
\end{itemize*}
Elementare Operationen auf Matrizen:
\begin{itemize*}
\item Für Matrizen A und B in $GF(2^8)^{4\times 4}$ bedeutet $A\oplus B$ die komponentenweise Anwendung der Addition im Körper $GF(2^8)$. (Diese ist wiederum $\oplus_8$, die bitweise XOR-Operation auf Bytes.)
\item Zyklischer Linksshift von Zeile i um $h=1,2,3$ Positionen:
\item $rotLeft_1((A_{i0}, A_{i1}, A_{i2}, A_{i3})) =(A_{i1}, A_{i2}, A_{i3}, A_{i0})$ usw.
\item Beispiel: $rotLeft_2((A1,06,4B,EF)) = (4B,EF,A1,06)$.
\item In AES wird Zeile i um i Positionen nach links rotiert. Die Abbildung ist also folgende: $\begin{pmatrix} A_{00}& A_{01}& A_ {02}& A_{03}\\ A_{10}& A_{11}& A_{12}& A_{13}\\ A_{20}& A_{21}& A_{22}& A_{23}\\ A_{30}& A_{31}& A_{32}& A_{33}\end{pmatrix} \rightarrow \begin{pmatrix} A_{00}& A_{01}& A_{02}& A_{03}\\ A_{11}& A_{12}& A_{13}& A_{10}\\ A_{22}& A_{23}& A_{20}& A_{21}\\ A_{33}& A_{30}& A_{31}& A_{32}\end{pmatrix}$
\item Diese Zeilenrotation ist eine Bitpermutation. Ihre Inverse besteht offenbar darin, Zeile i um i Positionen nach rechts zu rotieren. (Sie ist also nicht selbst invers)
\item Zyklischer Shift von Spalte $j$ um $h=1,2,3$ Positionen nach oben: $rotUp_1((A_{0j},A_{1j},A_{2j},A_{3j})^T) = (A_{1j},A_{2j},A_{3j},A_{0j})^T$ usw. (Benötigt bei der Rundenschlüsselerzeugung.)
\item ,,Lineare Spaltendurchmischung''
\item $col_j(A) \rightarrow M*col_j(A)$, für $0\geq j\geq 3$, für die feste Matrix $M=\begin{pmatrix} 02& 03& 01& 01\\ 01& 02& 03& 01\\ 01& 01& 02& 03\\ 03& 01& 01& 02\end{pmatrix}\in GF(2^8)^{4\times 4}$.
\end{itemize*}
Achtung: Gerechnet wird in $GF(2^8)$!
Beispiel: $M*\begin{pmatrix} 4F\\ B0\\ 3E\\ A0\end{pmatrix} = \begin{pmatrix} 02*4F\oplus 03*B0\oplus 01*3E\oplus 01*A0\\ ... \end{pmatrix} = \begin{pmatrix} 9E\oplus CB\oplus 3E\oplus A0 \\ ... \end{pmatrix} = \begin{pmatrix} CB\\...\end{pmatrix}$.
In AES werden einmal alle vier Spalten auf diese Weise transformiert. Dies kann man auch zu einer Matrixmultiplikation zusammenfassen: $A \rightarrow M*A$.
Diese Operation ,,vermischt'' die Einträge, ist aber keine Bitpermutation mehr, da Bits nicht nur vertauscht werden, sondern mit Körperoperationen verrechnet. Allerdings ist M invertierbar, sodass man die Operation auch wieder rückgängig machen kann, indem man mit $M^{-1}=\begin{pmatrix} 0E& 0B& 0D& 09\\ 09& 0E& 0B& 0D\\ 0D& 09& 0E& 0B\\ 0B& 0D& 09& 0E\end{pmatrix}$ multipliziert.
\begin{itemize*}
\item Die S-Box von AES ist eine feste bijektive Abbildung $\{0,1\}^8\rightarrow {0,1}^8$. Der mathematische Hintergrund der S-Box wird weiter unten diskutiert.
\item Rundenschlüssel: Aus Schlüssel $k\in\{0,1\}^{128}$ und Rundennummer r wird Rundenschlüssel $\kappa (k,r)\in\{0,1\}^{128}=(\{0,1\}^8)^{4\times 4}$ berechnet. Details hierzu folgen.
\end{itemize*}
\paragraph{AES-Chiffrieralgorithmus}
\begin{itemize*}
\item X:128-Bit-Klartext,
\item k:128-Bit-Schlüssel)
\item Umarrangiert: $X\in GF(2^8)^{4\times 4}$: Klartextmatrix; $k\in\{0,1\}^{128}$: Schlüssel.
\begin{enumerate*}
\item Initialschritt (,,Weißschritt''):
\begin{itemize*}
\item $U\leftarrow X\oplus \kappa (k,0)$ // addiere Rundenschlüssel für Runde $r=0$, als 128-Bit-String.
\end{itemize*}
\item Für $r=1,...,9$ tue
\begin{enumerate*}
\item Substitution: Anwendung der S-Box auf jedes Byte in U
\begin{itemize*}
\item $V_{ij}\leftarrow S(U_{ij})$, für $0\geq i,j\geq 3$;
\end{itemize*}
\item Zeilenrotation: i-te Zeile um i Positionen nach links
\begin{itemize*}
\item $row_i(W)\leftarrow rotLeft_i(row_i(V))$, für $0\geq i\geq 3$;
\end{itemize*}
\item Lineare Spalten durchmischung: M wie oben beschrieben
\begin{itemize*}
\item $Z\leftarrow M*W$, für $0\geq i\geq 3$;
\end{itemize*}
\item Schlüsseladdition: Rundenschlüssel für Runde r
\begin{itemize*}
\item $U\leftarrow Z\oplus \kappa (k,r)$ // komponentenweise Addition
\end{itemize*}
\end{enumerate*}
\item Verkürzte Schlussrunde, $r=10$, keine Spaltendurchmischung:
\begin{enumerate*}
\item Substitution
\begin{itemize*}
\item $V_{ij}\leftarrow S(U_{ij})$, für $0\geq i,j\geq 3$;
\end{itemize*}
\item Zeilenrotation
\begin{itemize*}
\item $row_i(Z)\leftarrow rotLeft_i(row_i(V))$, für $0\geq i\geq 3$;
\end{itemize*}
\item Schlüsseladdition
\begin{itemize*}
\item $Y\leftarrow Z\oplus \kappa (k,10)$
\end{itemize*}
\end{enumerate*}
\item Ausgabe: $Y\in GF(2^8)^{4\times 4}$, geschrieben als 128-Bit-Wort.
\end{enumerate*}
\end{itemize*}
Abbildung 3: Die S-Box für AES. $S(z_1 z_0)$ für Hexziffern $z_1,z_0$ steht in Zeile $z_1$, Spalte $z_0$. Beispiel: $S(A4)=49$.
\begin{tabular}{c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c}
& 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & A & B & C & D & E & F \\\hline
0 & 63 & 7C & 77 & 7B & F2 & 6B & 6F & C5 & 30 & 01 & 67 & 2B & FE & D7 & AB & 76 \\
1 & CA & 82 & C9 & 7D & FA & 59 & 47 & F0 & AD & D4 & A2 & AF & 9C & A4 & 72 & C0 \\
2 & B7 & FD & 93 & 26 & 36 & 3F & F7 & CC & 34 & A5 & E5 & F1 & 71 & D8 & 31 & 15 \\
3 & 04 & C7 & 23 & C3 & 18 & 96 & 05 & 9A & 07 & 12 & 80 & E2 & EB & 27 & B2 & 75 \\
4 & 09 & 83 & 2C & 1A & 1B & 6E & 5A & A0 & 52 & 3B & D6 & B3 & 29 & E3 & 2F & 84 \\
5 & 53 & D1 & 00 & ED & 20 & FC & B1 & 5B & 6A & CB & BE & 39 & 4A & 4C & 58 & CF \\
6 & D0 & EF & AA & FB & 43 & 4D & 33 & 85 & 45 & F9 & 02 & 7F & 50 & 3C & 9F & A8 \\
7 & 51 & A3 & 40 & 8F & 92 & 9D & 38 & F5 & BC & B6 & DA & 21 & 10 & FF & F3 & D2 \\
8 & CD & 0C & 13 & EC & 5F & 97 & 44 & 17 & C4 & A7 & 7E & 3D & 64 & 5D & 19 & 73 \\
9 & 60 & 81 & 4F & DC & 22 & 2A & 90 & 88 & 46 & EE & B8 & 14 & DE & 5E & 0B & DB \\
A & E0 & 32 & 3A & 0A & 49 & 06 & 24 & 5C & C2 & D3 & AC & 62 & 91 & 95 & E4 & 79 \\
B & E7 & C8 & 37 & 6D & 8D & D5 & 4E & A9 & 6C & 56 & F4 & EA & 65 & 7A & AE & 08 \\
C & BA & 78 & 25 & 2E & 1C & A6 & B4 & C6 & E8 & DD & 74 & 1F & 4B & BD & 8B & 8A \\
D & 70 & 3E & B5 & 66 & 48 & 03 & F6 & 0E & 61 & 35 & 57 & B9 & 86 & C1 & 1D & 9E \\
E & E1 & F8 & 98 & 11 & 69 & D9 & 8E & 94 & 9B & 1E & 87 & E9 & CE & 55 & 28 & DF \\
F & 8C & A1 & 89 & 0D & BF & E6 & 42 & 68 & 41 & 99 & 2D & 0F & B0 & 54 & BB & 16
\end{tabular}
\paragraph{Die S-Box von AES:}
Die S-Box ist als $16\times 16$-Tabelle gegeben, siehe Abb.3. Zur kompakten Darstellung wird ein Element $(a_7,a_6,a_5,a_4,a_3,a_2,a_1,a_0)$ von $GF(2^8)$ in zwei Hexziffern zerlegt: $(a_7,a_6,a_5,a_4)$ ist der Zeilenindex, $(a_3,a_2,a_1,a_0)$ der Spaltenindex der Position von $S((a_7,a_6,a_5,a_4,a_3,a_2,a_1,a_0))$.
Interessanterweise steckt hinter dieser chaotisch aussehenden Tabelle eine einfache Formel, die eine ,,nichtlineare'' Komponente in AES einbringt. Zu $x\in GF(2^8)$ betrachtet man $x^{-1}$, das multiplikative Inverse. Künstlich definiert man $00^{-1}:= 00$ (nur hier und nur für diesen Zweck). Weiter ist h eine invertierbare lineare Funktion auf dem $\mathbb{Z}_2$-Vektorraum $\{0,1\}^8$. Dazu werden die Elemente von $GF(2^8)$ als Spaltenvektoren aufgefasst, die 8 Bits enthalten.
$h((a_7,...,a_0))^T= \begin{pmatrix} 1& 1& 1& 1& 1& 0& 0& 0\\ 0& 1& 1& 1& 1& 1& 0& 0\\ 0& 0& 1& 1& 1& 1& 1& 0\\ 0& 0& 0& 1& 1& 1& 1& 1\\ 1& 0& 0& 0& 1& 1& 1& 1\\ 1& 1& 0& 0& 0& 1& 1& 1\\ 1& 1& 1& 0& 0& 0& 1& 1\\ 1& 1& 1& 1& 0& 0& 0& 1\end{pmatrix} * \begin{pmatrix} a_7\\ a_6\\a_5\\a_4\\a_3\\a_2\\a_1\\a_0\end{pmatrix}$
Dann ist die S-Box wie folgt definiert: $S(x)=h(x^{-1})\oplus_8 63$.
Auch hinter der Matrix M, die im Teil ,,Lineare Spaltendurchmischung'' benutzt wird, steckt eine relativ einfache lineare Operation über einer passenden algebraischen Struktur.
Wir nehmen den endlichen Körper $\mathbb{F}_{2^8}=GF(2^8)$ als Ausgangssituation und betrachten Polynome $b_0+b_1X+b_2X^2+b_3X^3$ vom Grad maximal 3 über diesem Körper. Diese bilden die Grundmenge des Rings $\mathbb{F}_{2^8} [X]/(X^4+1)$: Addition wie gewöhnlich, Multiplikation modulo $X^4+1$. Ein solches Polynom wird durch den Spaltenvektor $(b_0,b_1,b_2,b_3)^T\in (F_{2^8})^4$ beschrieben. Wir multiplizieren dieses Polynom über $F_{2^8} [X]/(X^4+1)$ mit dem festen Polynom $c(X)=02+01*X+01*X^2+03*X^3$. (Da die Koeffizienten Elemente von $F_{2^8}$ sind, werden sie durch zwei Hexziffern dargestellt.) Der Koeffizientenvektor $(c_0,c_1,c_2,c_3)^T$ des Produktpolynoms bildet die transformierte Spalte. Man kann nachrechnen, dass sie sich als $M*(b_0,b_1,b_2,b_3)^T$ ergibt.
Die Rundenschlüssel werden mit einem iterativen Verfahren berechnet. Dabei wird zunächst Spalte 3 intensiv manipuliert und auf Spalte 0 addiert.
\paragraph{AES-Rundenschlüsselberechnung}
$K_0 =\kappa (k,0)\leftarrow k$ //128-Bit-Schlüssel als $4\times 4$-Matrix
Für $r= 1,..., 10$ führe Runde r aus.
\begin{itemize*}
\item Input: Rundenschlüssel $K_{r-1}$ als $4\times 4$-Matrix
\item Output: Rundenschlüssel $K_r$ als $4\times 4$-Matrix
\item Berechnung von Spalte 0:
\begin{enumerate*}
\item Rotation (analog zur Zeilenrotation): $U\leftarrow rotUp_1(col_3(K_{r-1}))$ //Spalte 3 zyklisch eine Position nach oben
\item Substitution: $V_i\leftarrow S(U_i)$, für $0\geq i\geq 3$;
\item Konstantenaddition: $V_0\leftarrow V_0+02^{r-1}$; //Potenz in $GF(2^8)$;
\item Addition auf Spalte 0: $col_0(K_r)\leftarrow col_0(K_{r-1})+V$; //Vektoraddition;
\end{enumerate*}
\item Berechnung von Spalten 1 bis 3:
\item Iterative Addition: für $i=1,2,3: col_i(K_r)\leftarrow col_i(K_{r-1})+col_{i-1}(K_r)$; //Vektoraddition;
\item Ergebnis: $K_r=\kappa (k,r)$ für $r=0,1,...10$.
\end{itemize*}
Entschlüsselung:
Man geht nach dem schon diskutierten grundsätzlichen Ansatz bei Substitutions-Permutations-Kryptosystemen vor. Erst werden alle Rundenschlüssel berechnet. Diese werden in umgekehrter Reihenfolge benutzt. Für die Substitution wird stets die inverse S-Box $S^{-1}$ benutzt. Rotationen werden in umgekehrter Richtung ausgeführt. Die ,,lineare Spaltendurchmischung'' wird mit der zu $M$ inversen Matrix $M^{-1}$ ausgeführt. Ansonsten ist der Ablauf völlig analog der Verschlüsselung.
Aktuelle Lage:
Bisher gilt AES als praktisch sicher (insbesondere die 192-Bit- und die 256-Bit-Variante), wenn auch nicht in dem im Folgenden zu besprechenden technischen Sinn. Es wurden einige Angriffe vorgeschlagen, die zu schnellerem ,,Brechen'' führen als dem vollständigen Durchsuchen des Schlüsselraums (nur noch 299 Schlüssel müssen getestet werden... ), aber dies führt nicht zu praktisch durchführbaren Verfahren.
\subsubsection{Bemerkungen zu randomisierten Algorithmen}
Wir benötigen ein Algorithmenmodell, um die Angreifer in Eva zu modellieren. Offensichtlich wird sie alle ihr zur Verfügung stehenden Mittel einsetzen, insbesondere auch Zufallsexperimente (wenn es ihr nützt). Also müssen unsere Algorithmen auch Zufallsexperimente ausführen können. Grundsätzlich werden wir klassische Turingmaschinen bzw. üblichen Pseudocode (für gewöhnliche Computer) verwenden und ihre Laufzeit messen, allerdings mit einigen Änderungen/Erweiterungen/Einschränkungen, wie im Weiteren erläutert wird.
\paragraph{Ressourcenverbrauch}
Da wir nicht erwarten können, dass reale Kryptosysteme in einem idealen Sinn wie der informationstheoretischen Sicherheit sicher sind, wollen wir Sicherheit gegenüber einer Angreiferin Eva studieren, die nur beschränkte Ressourcen hat. Welche Ressourcen kommen in Frage? Sicherlich Zeit verbrauch bzw. Anzahl der Rechenoperationen, aber auch andere.
Vorüberlegung: Ein ,,zeiteffizienter'' Angriff (mit Klartextwahl, ,,chosen-plaintext attack'', CPA)
Sei $B=(\{0,1\}^l,\{0,1\}^s,\{0,1\}^l,e,d)$ ein Block-Kryptosystem und seien $x_i,y_i\in\{0,1\}^l$ für $1\geq i\geq t$ paarweise verschiedene Klar- bzw. Chiffretexte. Ein Schlüssel $k\in\{0,1\}^s$ ist konsistent mit den Paaren $(x_i,y_i)$, wenn $e(x_i,k)=y_i$ für alle $1\geq i\geq t$ gilt. Für realistische (d.h. praktisch relevante) SPKS gibt es im Fall $t\approx 5$ höchstens einen konsistenten Schlüssel. (Man denke an AES. $t=5$ bedeutet, dass $5*128$ Bit Information über $k$ vorliegen, eventuell redundant, aber $k$ ist nur $128$ Bit lang.)
Wir können also für Eva in Szenario 2 den folgenden Angriff nach dem CPA-Muster planen:
\begin{enumerate*}
\item Lasse fünf Klartexte $x_1,...,x_5$ zu $y_1,...,y_5$ verschlüsseln.
\item ,,Schaue nach'', welcher Schlüssel $k$ mit den Paaren $(x_1,y_1),...,(x_5,y_5)$ konsistent ist (wenigstens einer ist es und es gibt höchstens einen).
\item Höre Chiffretext $y$ ab und berechne $x=d(y,k)$ aus $y$.üm in Schritt 2. ,,nachsehen'' zu können, benötigt Eva eine Tabelle mit allen möglichen Chiffretextkombinationen für die fünf Klartexte $x_1,...,x_5$. Dafür gibt es $\geq |K|= 2^s$ Möglichkeiten, nämlich für jeden Schlüssel eine. Die Hashtabelle oder der Suchbaum (oder die entsprechende Struktur in einem Turingmaschinen-Programm) hat Größe $2^s$. Wenn der Programmtext oder die Turingmaschine binäre Suche (oder einen binären Suchbaum) benutzt, dann führt dieser ,,Angriff '' in Zeit $O(log(|K|)) =O(log(2^s)) =O(s)$ zum Klartext $x$.
\end{enumerate*}
Dieses Vorgehen ist natürlich unrealistisch, denn niemand kann ein so großes Programm schreiben oder speichern, wenn etwa (wie bei AES) die Zahl der Schlüssel $2^{128}>10^{38}$ beträgt. Um diesen Trick auszuschließen, werden wir den Ressourcenverbrauch eines Algorithmus als Summe von Laufzeit und Länge des Programmcodes (=Größe der Transitionstabelle der Turingmaschine) messen. Die Programmgröße ist eine untere Schranke für die Zeit, die Eva zur Erstellung ihres Programms benötigt. Unser Ressourcenmaß erfasst also die Zeit für die Erstellung und die Zeit für die Ausführung des Algorithmus.ünsere Algorithmen werden oft mit Kryptosystemen einer festen Blocklänge $l$ und einer fixen Anzahl von Klartext-/Chiffretext-Paaren arbeiten. Damit sind nur endlich viele Eingaben möglich, der Ressourcenverbrauch kann also nicht asymptotisch (,,bei großen Eingaben'') angegeben werden. Daher betrachten wir zunächst Algorithmen mit konstanter Laufzeit. Das führt dazu, dass alle eventuell vorhandenen Schleifen nur konstant oft durchlaufen werden. Damit können wir aber auf Schleifenanweisungen vollständig verzichten. Die resultierenden Programme heißen ,,Straight-Line-Programme''. Man kann sie sich in Pseudocode geschrieben vorstellen (ohne ,,while'' und ,,for'' und ohne Rückwärtssprünge), oder als Turingmaschinenprogramme mit der Eigenschaft, dass nie eine Programmzeile zweimal ausgeführt wird.
\paragraph{Randomisierung bei Straight-Line-Programmen}
In unseren Algorithmen wollen wir zusätzlich die Anweisung ,,$y\leftarrow flip(M)$'' erlauben, wobei $M$ eine endliche Menge ist. Die Idee dabei ist, dass der Variable $y$ ein zufälliges Element von $M$ (bzgl. der Gleichverteilung auf $M$) zugewiesen wird. Damit berechnen unsere Algorithmen keine Funktionen, sondern zufällige Werte, die durch eine Wahrscheinlichkeitsverteilung gesteuert werden.üm den Wahrscheinlichkeitsraum definieren zu können, machen wir die folgenden Annahmen (die keine Einschränkung darstellen):
\begin{enumerate*}
\item Bei nacheinander ausgeführten Kommandos der Form $y\leftarrow flip(M)$, mit identischem oder unterschiedlichem $M$, werden immer neue, unabhängige Zufallsexperimente ausgeführt.
\item Wie eben diskutiert, enthalten unsere Algorithmen keine Schleifen. Wir können daher jedes Ergebnis eines Zufallsexperiments in einer eigenen Variable speichern. Zusätzlich können wir die flip-Kommandos aus dem gesamten Programm, auch den bedingten Anweisungen, herausziehen und sie alle (vorab, auf Vorrat) ausführen. Damit können wir annehmen: Wenn die Anweisung $y\leftarrow flip(M)$ im Programmtext vorkommt, dann wird sie in jedem Durchlauf des Algorithmus (unabhängig von der Eingabe und den Ergebnissen der flip-Anweisungen) genau einmal ausgeführt.
\end{enumerate*}
Abkürzung: $flip(l)$ für $flip(\{0,1\}^l)$ (l-facher Münzwurf) und $flip()$ für $flip(1)$, also $flip(\{0,1\})$ (einfacher Münzwurf).
Sei nun A ein randomisierter Algorithmus (also ein Straight-Line-Programm), indem die $flip$-Anweisungen $y_i\leftarrow flip(M_i)$ für $1\geq i\geq r$ vorkommen. Dann verwenden wir als zugrundeliegenden Wahrscheinlichkeitsraum die Menge $M=M_1\times M_2\times...\times M_r$ mit der Gleichverteilung. Dies modelliert die Idee, dass die $r$ Zufallsexperimente jeweils mit der uniformen Verteilung und insgesamt unabhängig voneinander ausgeführt werden.
$I$ sei die Menge der Eingaben, $Z$ sei die Menge der Ausgaben.
Ist $x\in I$ eine Eingabe, so erhalten wir für jedes $m=(m_1,...,m_r)\in M$ genau eine Ausgabe $A^m(x)\in\mathbb{Z}$, indem wir in $A$ die Anweisung $y_i\leftarrow flip(M_i)$ durch $y_i\leftarrow m_i$ ersetzen. Auf diese Weise erhalten wir
\begin{itemize*}
\item Für jedes $m\in M$ eine Funktion $A^m:I\rightarrow Z,x \rightarrow A^m(x)$, und
\item für jedes $x\in I$ eine Zufallsgröße $A(x):M\rightarrow Z,m\rightarrow A^m(x)$.
\end{itemize*}
\textbf{Beispiel}2.8 Betrachte den folgenden Algorithmus:
\begin{itemize*}
\item $A(x:\{0,1\}^4):\{0,1\}$ // nach dem Doppelpunkt: Typ der Eingabe bzw. Ausgabe
\item $b_0 \leftarrow flip()$
\item $b_1 \leftarrow flip()$
\item $b_2 \leftarrow flip()$
\item $b_3 \leftarrow flip()$
\item $if b_0 = 1 \text{ then return } x(0)$
\item $if b_1 = 1 \text{ then return } x(1)$
\item $if b_2 = 1 \text{ then return } x(2)$
\item $if b_3 = 1 \text{ then return } x(3)$
\item return 1
\end{itemize*}
Dann ist $M=\{0,1\}^4$, und es gilt: $A^{0110}(1101)=1$ und $A^{0010}(1101)=0$. Kompakt: Wenn $b_0 b_1 b_2 b_3$ mit $i$ Nullen und einer $1$ (an Position $i$) beginnt, dann ist die Ausgabe $x(i)$, für $i=0,1,2,3$. Ist $b_0 b_1 b_2 b_3=0000$, so ist die Ausgabe 1. Also gilt: $Pr(A(1101)=0) = Pr(\{w\in\{0,1\}^4 |w_0=w_1=0, w_2=1\}) =(\frac{1}{2})^3 =\frac{1}{8}$ und $Pr(b_1=1) =Pr(\{w\in\{0,1\}^4 |w(1)=1\})=\frac{1}{2}$
Damit erhalten wir auch sinnvolle kombinierte und bedingte Wahrscheinlichkeiten: $Pr(A(1101)=0, b_0=0)= Pr(\{w\in\{0,1\}^4 |w_0=w_1=0, w_2=1\}) =\frac{1}{8}$ und $Pr(A(1101)=0| b_0=0) =\frac{Pr(A(1101)=0, b_0=0)}{Pr(b_0=0)}=\frac{1}{4}$
Wir können auch den Algorithmus $A$ so ändern, dass eine Anweisung $y_i\leftarrow flip(M_i)$ durch $y_i\leftarrow m^{(0)}_i$ ersetzt wird. (Diesen Algorithmus bezeichnen wir dann mit $A(y_i=m^{(0)}_i)$.) Es gilt dann für alle Eingaben $x$ und Ausgaben $z$: $Pr(A(x)=z| y_i=m^{(0)}_i) =Pr(A(y_i=m^{(0)}_i)(x) =z)$. Die verallgemeinerte Notation $A(y_1=m^{(0)}_1,...,y_s=m^{(0)}_s)$ erklärt sich von selbst.
\paragraph{Prozeduren als Parameter}
Wir werden Algorithmen $A$ betrachten, die als Eingabe eine Prozedur $B$ (z.B. die Verschlüsselungsfunktion einer Blockchiffre mit fest eingesetzem Schlüssel) erhalten. Diese Prozedur darf nur aufgerufen werden, sie wird nicht als Text in den Rumpf von $A$ eingefügt. Sie könnte aber wiederum zufallsgesteuert sein. Um den Wahrscheinlichkeitsraum von $A$ mit einem solchen Funktionsparameter zu bestimmen, müssen folgende Informationen gegeben sein:
\begin{itemize*}
\item $B$,
\item die Anzahl der Aufrufe von $B$ in $A$,
\item welche Aufrufe $y\leftarrow flip(M)$ in $B$ vorkommen.
\end{itemize*}
Wir behandeln dann die Variablen $y$ in verschiedenen Aufrufen von $B$ genau wie die aus einem gewöhnlichen randomisierten Programm (Umbenennen der Variablen, Herausziehen der Zufallsexperimente an den Anfang). In dem resultierenden Wahrscheinlichkeitsraum sind dann die Zufallsexperimente in den verschiedenen Aufrufen von $B$ und die in Teilen von $A$ außerhalb von $B$ unabhängig.
\subsubsection{Sicherheit von Block-Kryptosystemen}
Wir betrachten hier l-Block-Kryptosysteme $B=(X,K,Y,e,d)$ mit $X=Y=\{0,1\}^l$ und $K\subseteq\{0,1\}^s$ für ein $s$. $e$ ist die Verschlüsselungsfunktion und $d$ die Entschlüsselungsfunktion. Wir erinnern uns:
\begin{enumerate*}
\item Im Szenario 2 (chosen-plaintext attack,CPA) kann die Angreiferin Eva sich eine ,,geringe Zahl'' von Klartexten verschlüsseln lassen, also hat sie eine Liste von Klartext-Chiffretext-Paaren: $(x_1,y_1),...,(x_r,y_r)$. Nun kann jedenfalls nur ein ,,neuer'' Klartext $x$, also ein $x\in X\{x_1,...,x_r\}$, geheim übertragen werden. Die possibilistische Sicherheit verlangt genau, dass dies möglich ist: Wenn $y\in Y\{y_1,...,y_r\}$ ein neuer gegebener Chiffretext ist, dann gibt es für jeden Klartext $x\in X\{x_1,...,x_r\}$ einen Schlüssel $k$, der $x_i$ zu $y_i$ chiffriert, $1 \geq i\geq r$, und $x$ zu $y$ chiffriert.
\item Wenn dabei $r$ beliebig groß sein darf, können nach Prop.2.3 nur Substitutionskryptosysteme in diesem Sinne sicher sein. Da sie $|X|!$ Schlüssel haben müssen und daher immense Schlüssellänge (mindestens $|X|log|X|-O(|X|)$ Bits) erfordern, kommen sie in der Praxis nicht in Frage.
\end{enumerate*}
Idee eines neuen Sicherheitsbegriffs (für Block-Kryptosysteme): Gegeben sei eine Angreiferin Eva mit beschränkten Berechnungsressourcen. Wir fragen, wie sehr aus Evas Sicht das $l$-Block-Kryptosystem $B=(\{0,1\}^l,K,\{0,1\}^l,e,d)$ dem Substitutionskryptosystem $S'=(\{0,1\}^l,P\{0,1\}^l,\{0,1\}^l,e',d')$ (siehe Def.1.9) ähnelt. Ist es ihr mit ,,signifikanter Erfolgswahrscheinlichkeit'' möglich, aufgrund der ihr vorliegenden Information und im Rahmen ihrer Ressourcen, zu unterscheiden, welches der beiden Systeme verwendet wird? Wenn dies nicht der Fall ist, kann das Kryptosystem $B$ als sicher gelten, wie die folgende Überlegung zeigt.
Wenn Eva aufgrund der ihr vorliegenden Information (2.4) nicht mit nennenswerter Erfolgswahrscheinlichkeit unterscheiden kann, ob sie es mit der Chiffre $e(.,k)$ (für ein zufälliges $k\in K$) oder mit $e'(.,\pi)$ (für ein zufälliges $\pi\in P_{\{0,1\}^l}$) zu tun hat, dann hat sie aus der ihr vorliegenden Information keine nennenswerte Information über die konkrete Chiffree $(.,k)$ gelernt. Insbesondere kann sich ihre Information über die Klartextverteilung nicht (wesentlich) ändern, wenn ihr ein neuer Chiffretext $y$ vorgelegt wird, da bei $S'=(\{0,1\}^l,P\{0,1\}^l,\{0,1\}^l,e',d')$ keine solche Änderung eintritt.
Wir modellieren Verfahren, die eine Chiffre benutzen dürfen und dann ,,raten'' sollen, ob es eine Chiffre zu einem BKS $B$ oder eine Zufallspermutation ist, als randomisierte Algorithmen.
\textbf{Definition} 2.9 Ein l-Unterscheider ist ein randomisierter Algorithmus $U(F:\{0,1\}^l\rightarrow\{0,1\}^l):\{0,1\}$, dessen Laufzeit bzw. Ressourcenaufwand durch eine Konstante beschränkt ist.
Das Argument des l-Unterscheiders ist also eine Chiffre $F$. Diese ist als ,,Orakel'' gegeben, das heißt als Prozedur, die nur ausgewertet werden kann, deren Programmtext $U$ aber nicht kennt. Das Programm $U$ kann $F$ endlich oft aufrufen, um sich Paare wie in (2.4) zu besorgen. Danach kann $U$ noch weiter rechnen, um zu einer Entscheidung zu kommen. Das von $U$ gelieferte Ergebnis ist ein Bit.
Am liebsten hätte man folgendes Verhalten, für ein gegebenes Block-Kryptosystem $B$: Programm $U$ sollte 1 liefern, wenn $F$ eine Chiffre $e(.,k)$ zu $B$ ist, und $0$, wenn $F=\pi$ für eine Permutation $\pi\in P\{0,1\}^l$ ist, die keine $B$-Chiffre ist. Das gewünschte Verhalten wird sich bei $U$ natürlich niemals mit absoluter Sicherheit, sondern nur mit mehr oder weniger großer Wahrscheinlichkeit einstellen, je nach Situation.
\textbf{Beispiel}2.10 Als Beispiel betrachten wir das Vernam-Kryptosystem $B=B_{Vernam}$, siehe Beispiel 1.6. Wir definieren einen l-Unterscheider $U=U_{Vernam}$, der als Parameter eine Funktion $F:\{0,1\}^l\rightarrow\{0,1\}^l$ erhält und Folgendes tut:
\begin{enumerate*}
\item $k\leftarrow F(0^l)$
\item $y\leftarrow F(1^l)$
\item falls $1^l\oplus_l k=y$, dann gib $1$ aus, sonst $0$.
\end{enumerate*}
Dieser Unterscheider benutzt keine Zufallsexperimente, obwohl es ihm erlaubt wäre. Man sieht leicht Folgendes: Wenn $F(.) =e(.,k)$ für die Vernam-Chiffre mit beliebigem Schlüssel $k$, liefert $U_{Vernam}$ immer das Ergebnis 1. Wenn hingegen $F$ eine zufällige Permutation $\pi$ von $\{0,1\}^l$ ist, dann ist die Wahrscheinlichkeit, dass $F(1^l)=1^l\oplus_l F(0^l)$ gilt, genau $\frac{1}{2^{l-1}}$, also wird die Ausgabe $1$ nur mit sehr kleiner Wahrscheinlichkeit ausgegeben (wenn $l$ nicht ganz klein ist).
Wir definieren nun ein Spiel (,,game''), mit dem ein beliebiges Block-Kryptosystem $B$ und ein beliebiger Unterscheider $U$ darauf getestet werden, ob $B$ gegenüber $U$ ,,anfällig'' ist oder nicht. (Das Spiel ist ein Gedankenexperiment, es ist nicht algorithmisch.) Die Idee ist folgende: Man entscheidet mit einem Münzwurf (Zufallsbit b), ob $U$ für seine Untersuchungen als $F(.)$ eine zufällige Chiffre $e(.,k)$ von $B$ (,,Realwelt'') oder eine zufällige Permutation $\pi$ von $\{0,1\}^l$ (,,Idealwelt'') erhalten soll. Dann rechnet $U$ mit $F$ als Orakel und gibt dann seine Meinung ab, ob er sich in der Realwelt oder in der Idealwelt befindet. U ,,gewinnt'', wenn diese Meinung zutrifft.
\textbf{Definition} 2.11 Sei $B=(\{0,1\}^l,K,\{0,1\}^l,e,d)$ ein l-Block-Kryptosystem, und sei $U$ ein Unterscheider. Das zugehörige Experiment (oder Spiel) ist der folgende Algorithmus:
\begin{itemize*}
\item $GBU():\{0,1\}$ // kein Argument, Ausgabe ist ein Bit
\begin{enumerate*}
\item $b\leftarrow flip(\{0,1\})$
\begin{itemize*}
\item if $b=1$ (,,Realwelt'') then $k\leftarrow flip(K);F\leftarrow e(.,k)$ // Zufallschiffre von B
\item if $b=0$ (,,Idealwelt'') then $F\leftarrow flip(P\{0,1\}^l)$ // Zufallspermutation
\end{itemize*}
\item $b'\leftarrow U(F)$ // Der l-Unterscheider versucht herauszubekommen, ob $b=0$ oder $b=1$ gilt.
\item if $b=b'$ then return 1 else return 0. // 1 heißt, dass $U$ das richtige Ergebnis hat.
\end{enumerate*}
\end{itemize*}
Das verkürzte Experiment/Spiel $S^B_U$ (,,short'') gibt im 3.Schritt einfach $b'$ aus.
Der Wahrscheinlichkeitsraum für die Analyse des Spiels wird über die Zufallsexperimente zur Wahl von b, von k, der Zufallspermutation $\pi$ aus $P_{\{0,1\}^l}$ und die Zufallsexperimente in $U$ gebildet. Die Wahrscheinlichkeit dafür, dass der Unterscheider richtig liegt, ist $Pr(G^B_U=1)$, gemessen in diesem etwas verschachtelten Wahrscheinlichkeitsraum.
Wir erläutern intuitiv, wieso diese Definition eine sehr allgemeine Situation erfasst. Angenommen, Angreiferin Eva kann auf irgendeine algorithmische Weise mit einer gewissen positiven Wahrscheinlichkeit eine ,,nicht triviale Information'' über die Klartexte gewinnen, wenn diese mittels einer zufälligen Chiffre des l-Block-Kryptosystems $B$ verschlüsselt worden sind. Damit kann sie einen Unterscheider mit nichttrivialer Erfolgswahrscheinlichkeit bauen! Sie ruft die Verschlüsselungsfunktion $F$ auf, um einige selbstgewählte Klartexte $x_1,...,x_q$ zu $F(x_1)=y_1,...,F(x_q)=y_q$ zu verschlüsseln. Dann berechnet sie aus $y_1,...,y_q$ ihre ,,nichttriviale Information'' $I_1,...,I_q$ zu den entsprechenden Klartexten und prüft, ob $I_r$ auf $x_r$ zutrifft, für $r=1,...,q$. Gibt es eine gute Übereinstimmung, so geht sie davon aus, dass $F$ aus der ,,Realwelt'' stammt, also eine Chiffre von $B$ ist. Ansonsten vermutet sie, dass $F$ aus der ,,Idealwelt'' stammt, also eine zufällige Permutation ist.
\textbf{Beispiel}2.12 Für einen l-Bit-String $z$ sei $p(z)=\oplus_{1 \geq i\geq l} z_i$ seine Parität. Nehmen wir an, das Chiffrierverfahren von $N$ ist unvorsichtig geplant und zwar so, dass $p(e(x,k)) =p(x)$ ist für beliebige $x\in X$ und $k\in K$. Bei der Chiffrierung ändert sich also die Parität nicht. (Die Parität ist sicher ,,nichttriviale Information'', auch wenn sie vielleicht nicht unmittelbar nützlich ist.)
$U_{Paritaet}(F)$:
\begin{enumerate*}
\item Wähle Klartexte $x_1,...,x_q$ mit $p(x_1)=...=p(x_q) = 0$.
\item $y_r\leftarrow F(x_r)$, für $r=1,...,q$.
\item falls $p(y_1)=...=p(y_q)=0$, dann gib 1 aus, sonst 0.
\end{enumerate*}
Wenn wir in der ,,Realwelt'' sind $(b=1)$, also $F$ eine Chiffre $e(.,k)$ ist, dann ist die Antwort von $U$ immer ,,1'', also korrekt. Wenn wir in der ,,Idealwelt'' sind $(b=0)$, also $F$ eine zufällige Permutation ist, dann ist die Antwort nur mit Wahrscheinlichkeit $\frac{2^{l-1} (2^{l-1} -1)(2^{l-1}-2)...(2^{l-1} -q+ 1)}{2^l (2^l-1)(2^l-2)...(2^l-q+ 1)} \geq \frac{1}{2^q}$ falsch. (Alle Werte $F(x_1),...,F(x_q)$ müssen zufällig zu Chiffretexten geführt haben, die Parität 0 haben, von denen es $2^{l-1}$ viele gibt.) Es ergibt sich $Pr(G^B_U= 1)\geq\frac{1}{2} (1+1-2^{-q}) =1-2^{-(q+1)}$. Mit der effizienten Berechenbarkeit der ,,nichttrivialen Information'' hat man also einen Unterscheider gefunden, der $Pr(G^B_U=1)$ ,, groß'' macht.
Beispiel: Der folgende triviale l-Unterscheider $U_{trivial}$ erreicht $Pr(G^B_{U_{trivial}}= 1)=\frac{1}{2}$: $b\leftarrow flip(\{0,1\}); return\ b$.
Daher interessieren wir uns nicht für die Wahrscheinlichkeit $Pr(G^B_U= 1)$ ansich, sondern für den Abstand von $Pr(G^B_U=1)$ zu $Pr(G^B_{U_{trivial}}= 1) =\frac{1}{2}$:
\textbf{Definition} 2.13 Sei $U$ ein l-Unterscheider und $B$ ein l-Block-KS. Der Vorteil von $U$ bzgl. B ist $adv(U,B):= 2(Pr(G^B_U=1)-\frac{1}{2})$
Klar ist:
\begin{itemize*}
\item Für jeden l-Unterscheider $U$ und jedes l-Block-KS $B$ gilt $-1\geq adv(U,B)\geq 1$.
\item Werte $adv(U,B)<0$ sind uninteressant. (Wenn man einen Unterscheider $U$ mit $adv(U,B)<0$ hat, sollte man in $U$ die Ausgaben $0$ und $1$ vertauschen und erhält einen Unterscheider mit positivem Vorteil.)
\item Für den trivialen l-Unterscheider $U_{trivial}$ gilt $adv(U,B) = 0$.üm den Vorteil eines Unterscheiders auszurechnen, sind seine ,,Erfolgswahrscheinlichkeit'' und seine ,,Misserfolgswahrscheinlichkeit'' hilfreiche Werte: Der Erfolg von U bzgl. B ist (für das verkürzte Spiel $S=S_U^B$) $suc(U,B) := Pr(S\langle b= 1\rangle = 1)$, d.h. die Wahrscheinlichkeit, dass U die Verwendung des l-Block-KS B richtig erkennt. Der Misserfolg ist $fail(U,B) := fail(U) := Pr(S\langle b= 0\rangle = 1)$, d.h. die Wahrscheinlichkeit, dass U die Verwendung des idealen Substitutionskryptosystems nicht erkennt. Man kann in der Notation für ,,fail'' das ,,B'' auch weglassen, da im Fall $b=0$ das Kryptosystem B überhaupt keine Rolle spielt.
\end{itemize*}
\textbf{Lemma} 2.14 $adv(U,B) = suc(U,B)-fail(U)$.
Beweis: $Pr(G^B_U= 1) = Pr(S_U^B=b)$
\begin{itemize*}
\item $= Pr(S_U^B= 1,b= 1) + Pr(S_U^B= 0,b= 0)$
\item $= Pr(S_U^B= 1|b= 1)* Pr(b= 1) + Pr(S^B_U= 0|b= 0)*Pr(b= 0)$
\item $=\frac{1}{2}( Pr(S_U^B\langle b= 1\rangle = 1) + Pr(S_U^B\langle b= 0\rangle = 0))$
\item $=\frac{1}{2}( Pr(S_U^B\langle b= 1\rangle = 1) + (1-Pr(S_U^B\langle b= 0\rangle = 1)))$
\item $=\frac{1}{2}( (suc(U,B) + (1-fail(U)))$
\item $=\frac{1}{2}(suc(U,B)-fail(U)) + \frac{1}{2}$
\end{itemize*}
Durch Umstellen ergibt sich die Behauptung. Unterscheider mit Werten $adv(U,B)$ substanziell über 0 können als interessant (oder möglicherweise gefährlich) für B gelten. Wir müssen noch die beschränkten Ressourcen des Unterscheiders ins Spiel bringen.
\textbf{Definition} 2.15 Sei $l\in\mathbb{N}$, U ein l-Unterscheider, B ein l-Block-KS. Für $q,t\in\mathbb{N}$ heißt U $(q,t)$-beschränkt, wenn die Laufzeit des Aufrufs von U innerhalb von $G^B_U$ durch t beschränkt ist und dieser Aufruf die Funktion F mit höchstens $q$ verschiedenen Argumenten ausführt.
\textbf{Beispiel}2.10 (Fortsetzung) Der l-Unterscheider $U_{Vernam}$ wertet die Funktion $F$ an zwei Stellen $0^l$ und $1^l$ aus. Die Laufzeit des Aufrufs von $U$ ist beschränkt durch $c*l$ für eine Konstante $c\geq 1$. Also ist $U_{Vernam}$ $(2,c*l)$-beschränkt.
\textbf{Definition} 2.16 Sei $\epsilon>0$. Dann heißt $B(q,t,\epsilon)$-sicher, wenn für jeden $(q,t)$-beschränkten l-Unterscheider $U$ gilt $adv(U,B)< \epsilon$.
Man kann diese Bedingung auch umgedreht lesen, nämlich so: ,,Um mit Wahrscheinlichkeit größer als $\frac{1}{2}(1 +\epsilon)$ im Experiment $G^B_U$ die richtige Antwort 1 zu erzeugen, braucht ein l-Unterscheider mehr als q Auswertungen oder mehr Laufzeit/Platz als $t$.'' Mit beliebig hohen Rechenzeiten lassen sich praktisch alle Block-Kryptosysteme brechen, selbst mit sehr kleinem $q$.
\textbf{Beispiel}2.10 (Fortsetzung) Sei $B$ das Vernam-System der Länge $l$. Um den Vorteil von $U_{Vernam}$ bzgl. $B$ zu bestimmen, berechnen wir Erfolg und Misserfolg von $U$: Es gilt offensichtlich $1=Pr(S^B_U\langle b= 1\rangle = 1) = suc(U,B)$.
Es gilt $fail(U) = Pr(S^B_U\langle b= 0\rangle = 1) = Pr(S_U^B= 1|b= 0)$. Das verkürzte Experiment $S_U^B$ gibt 1 aus, wenn der Unterscheider $U$ dies tut. Dieser tut es aber genau dann, wenn $1^l\oplus_l F(0^l) =F(1^l)$ gilt, d.h. $fail(U) = Pr(S_U^B\langle b= 0\rangle = 1) = Pr(1^l\oplus_l F(0^l) =F(1^l)) = \frac{1}{2^l- 1}$.
Damit haben wir aber $adv(U,B) = suc(U,B)-fail(U) = 1-\frac{1}{2^l- 1}=\frac{2^l-2}{2^l-1}\approx 1$.
Das Vernam-System der Länge $l$ ist also nicht $(2,c*l,\frac{2^l- 2}{2^l- 1})$-sicher. Dafür realistische Werte von $l$ (z.B. 128) der Wert $\frac{2^l-2}{2^l-1}$ praktisch 1 ist, muss das Vernam-System im Szenario 2 als unsicher angesehen werden.
Natürlich sieht man auch mit bloßem Auge, dass die Vernam-Chiffre bei mehrfacher Verwendung nicht ,,sicher'' ist, da sie leicht entschlüsselt werden kann. Hier geht es aber um die Formulierung eines Sicherheitskonzepts, das allgemein anwendbar ist. Es ist beruhigend, dass im Fall der Vernam-Chiffre herauskommt, dass sie auch im Sinn dieser Definition unsicher ist.
Am obigen Beispiel eines Block-Kryptosystems, das die Parität von $x$ auf den Chiffretext $e(x,k)$ überträgt, sieht man aber auch, dass das Unterscheiderkonzept sehr empfindlich ist: Obwohl die Information über die Parity klein und harmlos scheint, erklärt es das System für nicht $(q,O(ql), 1-2^{-q})$-sicher, weil die Auswertung der Parität nur Zeit $O(l)$ kostet.
\textbf{Beispiel}2.17 Es sei $B$ ein l-Block-Kryptosystem. (Man denke an AES.) Wir nehmen (realistisch) an, dass $t$ (etwa $t=6$) Klartext-Chiffretext-Paare $(x_1,y_1),...,(x_t,y_t)$ in $B$ den Schlüssel $k$ der Länge $s=l$ eindeutig bestimmen, für mindestens die Hälfte der Schlüssel (*).
Der l-Unterscheider $U_{brute-force}$ wertet die Funktion F an $t+1$ Stellen $x_1,...,x_t,x$ aus, mit Ergebnissen $y_1,...,y_t,y$. Er probiert alle $2^l$ Schlüssel $k$, um einen zu finden, der $e(x_1,k)=y_1 ,...,e(x_t,k) =y_t$ erfüllt. Wenn kein solches $k$ gefunden wird, gibt $U$ den Wert $0$ aus.
Sonst wird getestet, ob $e(x,k)=y$ ist. Falls ja, wird $1$ ausgegeben, sonst $0$.
Das Verhalten lässt sich so beschreiben: In der ,,Realwelt'', wenn $F=e(.,k)$ ist für einen zufälligen Schlüssel $k$, dann findet $U$ dieses $k$ mit Wahrscheinlichkeit größer als $\frac{1}{2}$ (wegen (*)). Dann ist $e(x,k) =F(x)$ nach Wahl von $F$ und $y=F(x)$, weil $y$ so bestimmt wurde.
Also ist $e(x,k) =y$, also gibt $U$ den Wert 1 aus. In der ,,Idealwelt'' wird entweder kein passendes $k$ gefunden, oder wenn doch, dann ist die Wahrscheinlichkeit, dass $e(x,k) =y$ ist, wo $y$ einzufälliger Wert in $\{0,1\}^l-\{y_1,...,y_t\}$ ist, durch $1/(2^l-t)$ beschränkt. Damit ist $adv(U,B) = suc(U,B)-fail(U)\geq \frac{1}{2}-\frac{1}{2^l-t}\approx\frac{1}{2}$.
Die Laufzeit des Aufrufs von $U$ ist beschränkt durch $O(|K|) =O(2^l)$.
Daher ist $B$ nicht $(7, O(2^l),\frac{1}{2})$-sicher. Das ist natürlich nicht sehr schlimm, weil die Rechenzeit von $U$ unrealistisch hoch ist.
Schlussbemerkung: Gesucht wäre nun natürlich ein l-Block-Kryptosystem, das $(q,t,\epsilon)$-sicher ist, wobei $q$ und $t$ einigermaßen groß sind und $\epsilon$ möglichst klein ist. Es gibt unter bestimmten Annahmen (,,Existenz von Einwegfunktionen'') theoretisch konstruierbare Systeme, die für große $l$ einigermaßen effiziente (,,polynomiell in l'') Verschlüsselung und Entschlüsselung erlauben und im definierten Sinn für Angreifer mit (im Bezug zu $l$) nicht zu großen Ressourcen (,,polynomiell in l'') $\epsilon$-sicher sind, für recht kleine $\epsilon$ (der Wert $1/\epsilon$ darf polynomiell groß sein). Diese Systeme sind aber praktisch nicht verwendbar. Von praktisch relevanten Systemen wie AES weiß man nicht, für welche Werte sie sicher sind.
\section{Uneingeschränkte symmetrische Verschlüsselung}
Szenarium 3: Alice möchte Bob mehrere Klartexte beliebiger Länge schicken. Sie verwendet dafür immer denselben Schlüssel. Eva hört die Chiffretexte mit und kann sich einige wenige Klartexte mit dem verwendeten Schlüssel verschlüsseln lassen.
Erweiterungen im Vergleich zu vorher:
\begin{enumerate*}
\item Beliebig lange Texte sind erlaubt.
\item Mehrfaches Senden desselben Textes ist möglich; Eva sollte dies aber nicht erkennen.
\end{enumerate*}
Wir müssen die bisher benutzten Konzepte anpassen, um auch das mehrfache Senden derselben Nachricht zu erfassen. Ein grundlegender Ansatz, um mit identischen Botschaften umzugehen, ist Folgendes: Alices Verschlüsselungsalgorithmus ist randomisiert, liefert also zufallsabhängig unterschiedliche Chiffretexte für ein und denselben Klartext. Allerdings ist normalerweise die Anzahl der Zufallsexperimente fest und nicht von der Klartextlänge abhängig, sodass wir wie vorher davon ausgehen können, dass nur ein Experiment am Anfang ausgeführt wird. Auch der Sicherheitsbegriff und die Rechenzeitbeschränkungen müssen verändert werden.
Klartexte und Chiffretexte sind nun endliche Folgen von Bitvektoren (,,Blöcken'') der festen Länge $l$. Die Menge aller dieser Folgen bezeichnen wir mit $(\{0,1\}^l)^*$ oder kürzer mit $\{0,1\}^{l*}$. Es gibt also unendlich viele Klartexte und Chiffretexte. Die Menge der Schlüssel heißt $K$. Der Verschlüsselungsalgorithmus $E$ ist randomisiert und transformiert einen Klartext $x$ und einen Schlüssel $k$ in einen Chiffretext. Der Entschlüsselungsalgorithmus $D$ ist deterministisch und transformiert einen Chiffretext $y$ und einen Schlüssel $k$ in einen Klartext. Sicher muss man den Algorithmen eine Rechenzeit zugestehen, die von der Länge der zu verarbeitenden Texte abhängt. Als effizient werden Algorithmen angesehen, die eine polynomielle Rechenzeit haben. Es muss eine verallgemeinerte Dechiffrierbedingung gelten, die die Randomisierung der Verschlüsselung berücksichtigt.
\textbf{Definition} 3.1 Ein symmetrisches $l$-Kryptoschema ist ein Tupel $S= (K,E,D)$, wobei
\begin{itemize*}
\item $K\subseteq\{0,1\}^s$ eine endliche Menge ist (für ein $s\in\mathbb{N}$),