forked from wieerwill/Informatik
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathNetwork Security - Cheatsheet.tex
6093 lines (5787 loc) · 454 KB
/
Network Security - Cheatsheet.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]{Network Security}
\fancyfoot[L]{\thepage/\pageref{LastPage}}
\renewcommand{\headrulewidth}{0pt} %obere Trennlinie
\renewcommand{\footrulewidth}{0pt} %untere Trennlinie
\pdfinfo{
/Title (Network Security - 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}
\subsection{Sicherheitsziele}
\begin{description*}
\item[Vertraulichkeit] Confidentiality, Anonymität
\begin{itemize*}
\item nur bestimmtem Personenkreis zugänglich
%\item Die Vertraulichkeit von Entitäten wird auch als Anonymität bezeichnet
\end{itemize*}
\item[Integrität der Daten] Data Integrity
\begin{itemize*}
\item jede Veränderung von Daten zu erkennen
%\item Dies setzt voraus, dass der Ersteller bestimmter Daten identifiziert werden kann
\end{itemize*}
\item[Rechenschaftspflicht] Accountability
\begin{itemize*}
\item für Kommunikationsereignis verantwortliche Stelle identifizieren
\end{itemize*}
\item[Verfügbarkeit] Availability
\begin{itemize*}
\item Dienste sollten verfügbar sein und korrekt funktionieren
\end{itemize*}
\item[Kontrollierter Zugang] Controlled Access
\begin{itemize*}
\item nur autorisierte Stellen erhalten Zugriff
\end{itemize*}
\end{description*}
\subsection{Bedrohungen}
\begin{description*}
\item[Maskerade] oder Man-in-the-Middle-Angriff
\begin{itemize*}
\item Entität gibt sich als eine andere Entität aus
\end{itemize*}
\item[Lauschangriff] Eavesdropping
\begin{itemize*}
\item Entität liest Informationen, die sie nicht lesen soll
\end{itemize*}
\item[Verletzung der Berechtigung] Authorization Violation
\begin{itemize*}
\item Entität nutzt Dienst, für die sie nicht vorgesehen ist
\end{itemize*}
\item[Verlust oder Veränderung] von (übertragenen) Informationen
\begin{itemize*}
\item Daten werden verändert oder zerstört
\end{itemize*}
\item[Verweigerung von Kommunikationsakten] Denial of Communication Acts, Repudiation
\begin{itemize*}
\item Enität leugnet fälschlicherweise seine Teilnahme %an einer Kommunikationshandlung
\end{itemize*}
\item[Fälschung von Informationen] Forgery of Information
\begin{itemize*}
\item Entität erstellt neue Informationen im Namen anderer Entität
\end{itemize*}
\item[Sabotage] oder Denial-of-Service-Angriffe
\begin{itemize*}
\item Verfügbarkeit und ordnungsgemäße Funktionieren beeinträchtigen
\end{itemize*}
\end{description*}
\subsection{Analyse der Netzwerksicherheit}
\begin{itemize*}
\item Risikopotenzial der allgemeinen Bedrohungen für nutzenden Einheiten
\item Aufwand (Zeit...) zur Durchführung bekannter Angriffe
\item im Allgemeinen unmöglich, unbekannte Angriffe zu bewerten
%\item kann besser nach den feinkörnigeren Angriffen auf der Nachrichtenebene strukturiert werden
\end{itemize*}
\subsection{Angriffe auf Nachrichtenebene}
\begin{itemize*}
\item Passive Angriffe: Lauschangriff
\item Aktive Angriffe: Verzögerung/Löschen/Einfügen/Modifizieren von PDUs (Protocol Data Units)
\item erfolgreiche Durchführung erfordert
\begin{itemize*}
\item keine erkennbaren Nebeneffekte auf andere Kommunikationen% (Verbindungen/verbindungslose Übertragungen)
\item keine Nebenwirkungen auf andere PDUs der gleichen Verbindung %verbindungslosen Datenübertragung zwischen den gleichen Entitäten
\end{itemize*}
%\item Eine Sicherheitsanalyse einer Protokollarchitektur muss diese Angriffe entsprechend den Schichten der Architektur analysieren
\end{itemize*}
\columnbreak
\subsection{Schutzmaßnahmen der Informationssicherheit}
\begin{itemize*}
\item Physische Sicherheit
\begin{itemize*}
\item Schlösser oder andere physische Zugangskontrollen
\item Manipulationssicherung empfindlicher Geräte
\item Umweltkontrollen
\end{itemize*}
\item Personelle Sicherheit
\begin{itemize*}
\item Identifizierung von sensiblen Positionen
\item Verfahren zur Überprüfung der Mitarbeiter
\item Sicherheitsschulung und -bewusstsein
\end{itemize*}
\item Administrative Sicherheit
\begin{itemize*}
\item Kontrolle des Imports von Fremdsoftware
\item Verfahren zur Untersuchung von Sicherheitsverstößen
\item Überprüfung von Prüfpfaden
\item Überprüfung von Kontrollen der Rechenschaftspflicht
\end{itemize*}
\item Strahlungssicherheit
\begin{itemize*}
\item Kontrolle von Funkfrequenzen und anderen elektromagnetischen Abstrahlungen
\item Bezeichnet als TEMPEST-Schutz
\end{itemize*}
\item Mediensicherheit
\begin{itemize*}
\item Absicherung der Speicherung von Informationen
\item Kontrolle der Kennzeichnung, Vervielfältigung und Vernichtung von sensiblen Informationen
\item Sicherstellen, dass Medien mit sensiblen Informationen sicher vernichtet werden
\item Scannen von Medien auf Viren
\end{itemize*}
\item Lebenszyklus-Kontrollen
\begin{itemize*}
\item Vertrauenswürdiger Systementwurf, -implementierung, -bewertung und -übernahme
\item Programmierstandards und -kontrollen
\item Kontrollen der Dokumentation
\end{itemize*}
\item Computer-Sicherheit
\begin{itemize*}
\item Schutz von Informationen während der Speicherung/Verarbeitung in einem Computersystem
\item Schutz der Datenverarbeitungsgeräte selbst
\end{itemize*}
\item Sicherheit der Kommunikation
\begin{itemize*}
\item Schutz von Informationen während des Transports von einem System zu einem anderen
\item Schutz der Kommunikationsinfrastruktur selbst
\end{itemize*}
\end{itemize*}
\subsection{Sicherheitsdienste}
\begin{itemize*}
\item abstrakter Dienst, der bestimmte Sicherheitseigenschaft gewährleisten soll
\item realisiert mit Hilfe von kryptografischen Algorithmen und Protokollen oder herkömmlichen Mitteln
\item Dokument auf USB-Stick vertraulich, indem es verschlüsselt gespeichert und Datenträger in Tresor verschlossen
\item Kombination aus kryptografischen und anderen Mitteln am effektivsten
\item Kryptographischer Algorithmus: mathematische Umwandlung von Eingabedaten in Ausgabedaten
\item Kryptografisches Protokoll: Reihe von Schritten und Austausch von Nachrichten %zwischen mehreren Einheiten, um ein bestimmtes Sicherheitsziel zu erreichen
\end{itemize*}
\begin{description*}
\item[Authentifizierung] Authentication
\begin{itemize*}
\item grundlegendste Sicherheitsdienst,
\item Entität besitzt Identität, die sie vorgibt zu haben
\end{itemize*}
\item[Integrität] Integrity
\begin{itemize*}
\item Daten nicht unentdeckt verändern können
\end{itemize*}
\item[Vertraulichkeit] Confidentiality
\begin{itemize*}
\item Geheimhaltung geschützter Daten
\end{itemize*}
\item[Zugriffskontrolle] Access Control
\begin{itemize*}
\item Zugriff auf Dienste/Information nur mit Berechtigung %Kontrolliert, dass jede Identität nur auf die Dienste und Informationen zugreift, zu denen sie berechtigt ist
\end{itemize*}
\item[Nicht-Abstreitbarkeit] Non Repudiation %Schützt davor, dass an einem Kommunikationsaustausch beteiligte Entitäten später fälschlicherweise abstreiten können, dass der Austausch stattgefunden hat
\end{description*}
\subsection{Sicherheitsunterstützende Mechanismen}
\begin{description*}
\item[Schlüsselverwaltung] alle Aspekte des Lebenszyklus von kryptografischen Schlüsseln
\item[Zufallszahlengenerierung] Generierung von kryptographisch sicheren Zufallszahlen
\item[Ereigniserkennung/Sicherheitsprüfpfad] Erkennung und Aufzeichnung von Ereignissen, zur Erkennung von Angriffen oder Bedingungen, die von Angriffen ausgenutzt werden könnten
\item[Erkennung von Eindringlingen] Analyse der aufgezeichneten Sicherheitsdaten, um erfolgreiche Einbrüche oder Angriffe zu erkennen
\item[Beglaubigung] Registrierung durch vertrauenswürdige Partei, die bestimmte Eigenschaften der Daten bestätigen kann
\item[Traffic Padding \& Cover Traffic] Erzeugung von gefälschtem Verkehr, um die Analyse des Verkehrsflusses zu verhindern
\item[Routing-Kontrolle] Beeinflussung des Routings von PDUs in Netzwerk
\end{description*}
\subsection{Kryptologie}
\begin{description*}
\item[Kryptologie] Wissenschaft, die sich mit sicherer und meist geheimer Kommunikation beschäftigt
\item[Kryptographie] die Lehre, mit der Informationen in verschlüsseltem Text verborgen und später von legitimen Nutzern mit Hilfe eines geheimen Schlüssels offengelegt werden können
\item[Kryptoanalyse] die Wissenschaft der Wiedergewinnung von Informationen aus Chiffren ohne Kenntnis des Schlüssels
\item[Chiffre] Methode zur Umwandlung einer Nachricht (Klartext), um ihre Bedeutung zu verschleiern
\item[Verschlüsselung] von Daten: Umwandlung von Klartextdaten in Chiffretext, um deren Bedeutung zu verbergen
\item[Signierung] von Daten: Berechnung eines Prüfwerts oder digitalen Signatur für gegebenen Klartext oder Geheimtext, der anderen Stellen, die auf die signierten Daten zugreifen können, überprüft werden kann
\item[Symmetrische] Kryptografie, die 1 Schlüssel für die Ver-/Entschlüsselung oder die Signierung/Prüfung verwendet
\item[Asymmetrische] Kryptografie mit 2 verschiedenen Schlüsseln für die Ver-/Entschlüsselung oder die Unterzeichnung/Prüfung
\item[Kryptografische Hash-Funktionen] mit 0 Schlüsseln (,,Schlüssel'' wird an Daten ,,angehängt'' oder ,,vermischt'')
\end{description*}
\subsection{Kryptoanalyse}
\begin{itemize*}
\item Arten der Kryptoanalyse
\begin{itemize*}
\item Nur Chiffretext: bestimmte Muster können erhalten bleiben
\item Bekannte Chiffretext-Klartext-Paare
\item Gewählter Klartext oder gewählter Chiffretext
\item Differentielle Kryptoanalyse und lineare Kryptoanalyse
\item Neuer: verwandte Schlüsselanalyse
\end{itemize*}
\item Kryptoanalyse der Public-Key-Kryptographie
\begin{itemize*}
\item Schlüssel öffentlich zugänglich, kann ausgenutzt werden
\item zielt eher darauf ab, das Kryptosystem selbst zu knacken
\item näher an reinen mathematischen Forschung %als klassische Kryptoanalyse
\item Berechnung von diskreten Logarithmen
\item Faktorisierung von großen ganzen Zahlen
\end{itemize*}
\end{itemize*}
\subsubsection{Brute-Force-Angriff}
\begin{itemize*}
\item probiert alle möglichen Schlüssel aus, bis er verständlichen Klartext findet
\item Jeder kryptog. Algorithmus kann mit BF angegriffen werden
\item Im Durchschnitt Hälfte aller möglichen Schlüssel ausprobieren
\end{itemize*}
\subsubsection{Wie groß ist groß?}
\begin{tabular}{l|l}
Referenz & Größe \\\hline
Sekunden in einem Jahr & ca. $3 *10^7$ \\
Taktzyklen pro Jahr (50 MHz Computer) & ca. $1,6 *10^{15}$ \\
Binäre Zeichenketten der Länge 64 & $2^{64}$ ca. $1,8 * 10^{19}$ \\
Binäre Zeichenfolgen der Länge 128 & $2^{128}$ ca. $3,4 * 10^{38}$ \\
Binäre Zeichenfolgen der Länge 256 & $2^{256}$ ca. $1,2 * 10^{77}$ \\
Elektronen im Universum & $8,37 * 10^{77}$
\end{tabular}
\subsubsection{Eigenschaften von Verschlüsselungsalgorithmen}
\begin{itemize*}
\item \textbf{Fehlerfortpflanzung} charakterisiert Auswirkungen von Bit-Fehlern bei Übertragung von Chiffretext zu rekonstruiertem Klartext
\item Je nach Verschlüsselungsalgorithmus können pro fehlerhaftem Chiffretext-Bit ein oder mehrere fehlerhafte Bits im rekonstruierten Klartext vorhanden sein
\item \textbf{Synchronisierung} charakterisiert die Auswirkungen verlorener Chiffretext-Dateneinheiten auf den rekonstruierten Klartext
\item Einige Verschlüsselungsalgorithmen können sich nicht von verlorenem Chiffretext erholen und benötigen daher eine explizite Neusynchronisierung im Falle verlorener Nachrichten
\item Andere Algorithmen führen eine automatische Neusynchronisierung nach 0 bis n (je nach Algorithmus) Chiffretextbits durch
\end{itemize*}
\subsection{Klassifizierung von Verschlüsselungsalgorithmen}
\begin{itemize*}
\item Art der Operationen
\begin{description*}
\item[Substitution] jedes Element des Klartextes in anderes Element umwandeln
\item[Transposition] Elemente des Klartextes neu anordnen
\end{description*}
\item Anzahl der verwendeten Schlüssel
\begin{description*}
\item[Symmetrisch] denselben Schlüssel
\item[Asymmetrisch] unterschiedliche Schlüssel
\end{description*}
\item Art und Weise, in der Klartext verarbeitet wird
\begin{description*}
\item[Stromchiffren] arbeiten mit Bitströmen und verschlüsseln ein Bit nach dem anderen
\begin{itemize*}
\item Idee lineare rückgekoppelter Schieberegister
\item meiste Stromchiffren verbreiten keine Fehler
\item anfällig für den Verlust der Synchronisation
\end{itemize*}
\item[Blockchiffren] arbeiten mit Blöcken der Breite b, wobei b vom jeweiligen Algorithmus abhängt
\end{description*}
\end{itemize*}
\section{Symmetrische Kryptographie}
\subsection{Symmetrische Verschlüsselung}
\begin{itemize*}
\item Derselbe Schlüssel $K_{A,B}$ wird für die Verschlüsselung und Entschlüsselung von Nachrichten verwendet
\item Wenn P die Klartextnachricht bezeichnet, bezeichnet $E(K_{A,B}, P)$ den Chiffretext und es gilt $D(K_{A,B}, E(K_{A,B}, P)) = P$
\item Alternativ schreibt man manchmal $P_{K_{A,B}}$ oder $E_{K_{A,B}}(P)$
\end{itemize*}
\subsection{Symmetrische Block-Verschlüsselungsarten}
\subsubsection{Electronic Code Book Mode (ECB)}
\begin{itemize*}
\item Jeder Block $P_i$ der Länge $b$ wird unabhängig verschlüsselt: $C_i = E(K, p_i)$
\item Bitfehler in Chiffretextblock $C_i$ führt zu völlig falsch wiederhergestellten Klartextblock $P_i'$
\item Verlust der Synchronisation hat keine Auswirkungen, wenn ganzzahlige Vielfache der Blockgröße b verloren gehen% Geht eine andere Anzahl von Bits verloren, ist eine explizite Neusynchronisation erforderlich.
\item Nachteil: identische Klartextblöcke werden zu identischem Chiffretext verschlüsselt
\end{itemize*}
\begin{center}
\includegraphics[width=.6\linewidth]{Assets/NetworkSecurity-electronic-code-book-mode.png}
\end{center}
\subsubsection{Cipher Block Chaining Mode (CBC)}
\begin{itemize*}
\item Vor Verschlüsselung eines Klartextblocks $P_i$ wird dieser mit dem vorangegangenen Chiffretextblock $C_{i-1}$ XOR-verknüpft
\begin{itemize*}
\item $C_i = E(K, C_{i-1} \oplus P_i)$
\item $P_{i'} = C_{i-1} \oplus D(K, C_i)$
\item Um $C_1$ zu berechnen, einigen sich beide Parteien auf einen Anfangswert (IV) für $C_0$
\end{itemize*}
\item Fehlerfortpflanzung: Ein verfälschter Chiffretextblock führt zu zwei verfälschten Klartextblöcken, da $P_i'$ aus $C_{i-1}$ und $C_i$
\item Synchronisation: Wenn die Anzahl der verlorenen Bits ein ganzzahliges Vielfaches von b ist, wird ein zusätzlicher Block $P_{i+1}$ verzerrt, bevor die Synchronisation wiederhergestellt wird %Wenn eine andere Anzahl von Bits verloren geht, ist eine explizite Neusynchronisation erforderlich
\item Vorteil: identische Klartextblöcke werden zu nicht-identischem Chiffretext verschlüsselt
\end{itemize*}
\begin{center}
\includegraphics[width=.6\linewidth]{Assets/NetworkSecurity-cipher-block-chaining-mode.png}
\end{center}
\subsubsection{Ciphertext Feedback Mode (CFB)}
\begin{itemize*}
\item Ein Blockverschlüsselungsalgorithmus, der mit Blöcken der Größe b arbeitet, kann in einen Algorithmus umgewandelt werden, der mit Blöcken der Größe $j (j<b)$ arbeitet
\begin{itemize*}
\item $S(j, x)$ bezeichnen die $j$ höherwertigen Bits von $x$
\item $P_i$, $C_i$ den $i$-ten Block von Klartext und Geheimtext der Länge $j$ bezeichnen
\item IV ist ein Anfangswert beider Parteien
\item $R_1 = IV$
\item $R_n = (R_{n-1}*2^j\ mod\ 2^b)\oplus C_{n-1}$
\item $C_n = S(j,E_K(R_n))\oplus P_n$
\item $S(j,E_K(R_n))\oplus C_n = S(j,E_K(R_n))\oplus S(j,E_K(R_n))\oplus P_n$
\item $S(j,E_K(R_n))\oplus C_n = P_n$
\end{itemize*}
\item Ein gängiger Wert für j ist 8 für die Verschlüsselung von einem Zeichen pro Schritt
\item Fehlerfortpflanzung: Da die Chiffretextblöcke schrittweise durch das Register geschoben werden, verfälscht ein fehlerhafter Block $C_i$ den wiederhergestellten Klartextblock $P_i'$ sowie die folgenden $\lceil b / j\rceil$-Blöcke
\item Synchronisation: Wenn die Anzahl der verlorenen Bits ein ganzzahliges Vielfaches von j ist, werden $\lceil b / j\rceil$ zusätzliche Blöcke verfälscht, bevor die Synchronisation wiederhergestellt ist% Wenn eine beliebige andere Anzahl von Bits verloren geht, ist eine explizite Neusynchronisierung erforderlich
\item Nachteil: Die Verschlüsselungsfunktion E muss häufiger berechnet werden, da eine Verschlüsselung von $b$ Bit durchgeführt werden muss, um $j$ Bit des Klartextes zu verbergen
%\item Beispiel: Bei Verwendung von DES mit Verschlüsselung von jeweils einem Zeichen $\Rightarrow$ muss die Verschlüsselung 8-mal häufiger durchgeführt werden
\end{itemize*}
\subsubsection{Output-Feedback-Modus (OFB)}
\begin{itemize*}
\item Pseudozufallsfolge $R_i$ verwendet, die nur von $K$ und $IV$ abhängt
\begin{itemize*}
\item $S(j, x)$ bezeichnen die $j$ höherwertigen Bits von $x$
\item $P_i$, $C_i$ bezeichnen den $i$-ten Block von Klartext und Chiffretext der Länge $j$
\item $IV$ sei ein Anfangswert beider Parteien
\item $R_1 = IV$
\item $R_n = (R_{n-1}* 2^j\ mod\ 2^b )\oplus S(j,E_K(R_{n-1}))$ %// j-bit Linksverschiebung + verschlüsselter alter Wert
\item $C_n = S(j,E_K(R_n))\oplus P_n$
\item $S(j,E_K(R_n))\oplus C_n = S(j,E_K(R_n))\oplus S(j,E_K(R_n))\oplus P_n$
\item $S(j,E_K(R_n))\oplus C_n = P_n$
\end{itemize*}
\item Der Klartext wird mit der Pseudo-Zufallssequenz XOR-verknüpft, um den Chiffretext zu erhalten und umgekehrt
\item Fehlerfortpflanzung: Einzelbitfehler führen nur zu Einzelbitfehlern $\rightarrow$ keine Fehlermultiplikation
\item Synchronisierung: Wenn einige Bits verloren gehen, ist eine explizite Re-Synchronisation erforderlich
\item Vorteil: Die Pseudo-Zufallsfolge kann vorberechnet werden, um die Auswirkungen der Verschlüsselung auf die Ende-zu-Ende-Verzögerung gering zu halten
\item Verschlüsselungsfunktion muss häufiger berechnet werden, da eine Verschlüsselung von $b$ Bit durchgeführt werden muss, um $j$ Bit des Klartextes zu verbergen
\item Es ist für einen Angreifer möglich, bestimmte Bits des Klartextes zu manipulieren
\end{itemize*}
\begin{center}
\includegraphics[width=.6\linewidth]{Assets/NetworkSecurity-output-feedback-mode.png}
\end{center}
\subsection{Datenverschlüsselungsstandard (DES)}
\begin{itemize*}
\item symmetrische Blockchiffre mit Blöcken der Länge 128 Bit
\item unter Verwendung von Schlüsseln der Länge 128 Bit
\item NSA reduzierte Blockgröße auf 64 Bit, die Größe des Schlüssels auf 56 Bit und änderte Details in den Substitutionsfeldern
\end{itemize*}
% \includegraphics[width=\linewidth]{Assets/NetworkSecurity-des-algorithm.png}
\begin{center}
\includegraphics[width=.6\linewidth]{Assets/NetworkSecurity-des-single-iteration.png}
\end{center}
\subsubsection{DES - Einzelne Iteration}
\begin{itemize*}
\item Die rechten 32 Bit der zu verschlüsselnden Daten werden mit Hilfe einer Expansions-/Permutationstabelle auf 48 Bit erweitert
\item linke und rechte 28 Bit des Schlüssels werden zirkulär nach links verschoben und der resultierende Wert wird mit Hilfe einer Permutations-/Kontraktionstabelle auf 48 Bit verkürzt
\item beide oben genannten Werte XOR-verknüpft und in Auswahl- und Ersetzungsbox eingegeben
\item Intern wird diese Operation durch 8 so genannte s-Boxen realisiert, von denen jede einen Sechs-Bit-Wert auf einen Vier-Bit-Wert gemäß einer boxspezifischen Tabelle abbildet, was insgesamt zu einem 32-Bit-Ausgang führt
\item Ausgang des obigen Schritts wird erneut permutiert und mit den linken 32 Bit der Daten XOR-verknüpft, was zu den neuen rechten 32 Bit der Daten führt
\item Die neuen linken 32 Bit der Daten sind der rechte Wert der vorherigen Iteration
\end{itemize*}
\subsubsection{DES - Entschlüsselung}
\begin{itemize*}
\item Unter Verwendung der Abkürzung $f(R, K)$ kann der Verschlüsselungsprozess wie folgt geschrieben werden
\begin{itemize*}
\item $L_i = R_{i-1}$
\item $R_i = L_{i-1}\oplus f(R_{i-1}, K_i)$
\item Aufteilung der Daten in zwei Hälften und Organisation der Verschlüsselung gemäß den obigen Gleichungen
\item wird als Feistel-Netzwerk bezeichnet
\end{itemize*}
\item Der DES-Entschlüsselungsprozess ist im Wesentlichen derselbe wie die Verschlüsselung. Er verwendet den Chiffretext als Eingabe für den Verschlüsselungsalgorithmus, wendet aber die Unterschlüssel in umgekehrter Reihenfolge an
\item Die Ausgangswerte sind also
\begin{itemize*}
\item $L_0' || R_0' =$ InitialPermutation (Chiffretext)
\item Chiffretext = InverseInitialPermutation ($R_{16} || L_{16}$)
%\item $L_0' || R_0' =$ InitialPermutation (InverseInitialPermutation ($R_{16}|| L_{16}))=R_{16}|| L_{16}$
\end{itemize*}
\item Nach einem Schritt der Entschlüsselung
\begin{itemize*}
\item $L_1' = R_0' = L_{16} = R_{15}$
\item $R_1' = L_0' \oplus f(R_0', K_{16})=R_{16}\oplus f(R_{15},K_{16})=,,L_{15}\oplus f(R_{15},K_{16})''\oplus f(R_{15},K_{16}) =L_{15}$
\end{itemize*}
\item Diese Beziehung gilt für den gesamten Prozess als
\begin{itemize*}
\item $R_{i-1} = L_i$
\item $L_{i-1} = R_i\oplus f(R_{i-1}, K_i) = R_i\oplus f(L_i, K_i)$
\end{itemize*}
\item Der Ausgang der letzten Runde ist schließlich
\begin{itemize*}
\item $L_{16}' || R_{16}' = R_0 || L_0$
\end{itemize*}
\item Nach der letzten Runde führt DES einen 32-Bit-Tausch und die inverse
Anfangspermutation durch
\begin{itemize*}
\item InverseInitialPermutation($L_0|| R_0$) = InverseInitialPermutation(InitialPermutation(Klartext)) = Klartext
\end{itemize*}
\end{itemize*}
\subsubsection{DES - Sicherheit}
\begin{itemize*}
\item Schwächen der Schlüssel
\begin{itemize*}
\item Schwache Schlüssel: Vier Schlüssel sind schwach, da sie Unterschlüssel erzeugen, die entweder alle 0 oder alle 1 enthalten.
\item Halbschwache Schlüssel: Es gibt sechs Schlüsselpaare, die Klartext zu identischem Chiffriertext verschlüsseln, da sie nur zwei verschiedene Unterschlüssel erzeugen
\item Möglicherweise schwache Schlüssel: Es gibt 48 Schlüssel, die nur vier verschiedene Unterschlüssel erzeugen
\item Insgesamt werden $64$ von $72057594037927936$ als schwach angesehen
\end{itemize*}
\item Algebraische Struktur
\begin{itemize*}
\item Wäre DES geschlossen, dann gäbe es für jedes $K_1,K_2$ ein $K_3$, so dass: $E(K_2,E(K_1,M))=E(K_3,M)$, also wäre die doppelte Verschlüsselung nutzlos
\item Wäre DES rein, dann gäbe es für jedes $K_1,K_2,K_3$ ein $K_4$, so dass $E(K_3,E(K_2,E(K_1,M)))=E(K_4,M)$, also wäre die dreifache Verschlüsselung nutzlos
\item DES ist weder geschlossen noch rein, daher kann ein Mehrfachverschlüsselungsschema verwendet werden, um die Schlüssellänge zu erhöhen
\end{itemize*}
\item Differentielle Kryptoanalyse
\begin{itemize*}
\item Im Jahr 1990 veröffentlichten E. Biham und A. Shamir diese Analysemethode
\item Sie sucht gezielt nach Unterschieden in Chiffretexten, deren Klartexte bestimmte Unterschiede aufweisen, und versucht, daraus den richtigen Schlüssel zu erraten
\item Der grundlegende Ansatz benötigt einen ausgewählten Klartext zusammen mit seinem Chiffretext
\item DES mit 16 Runden ist gegen diesen Angriff immun, da der Angriff $2^{47}$ gewählte Klartexte oder $2^{55}$ bekannte Klartexte benötigt
\item Die Entwickler von DES erklärten in den 1990er Jahren, dass sie in den 1970er Jahren über diese Art von Angriffen Bescheid wussten und dass die s-Boxen entsprechend entworfen wurden
\end{itemize*}
\item Schlüssellänge: Da 56-Bit-Schlüssel in $10,01$ Stunden durchsucht werden kann, wenn man $10^6$ Verschlüsselungen/$\mu s$ durchführen kann, kann DES nicht mehr als ausreichend sicher angesehen werden
\end{itemize*}
\subsubsection{Erweiterung der Schlüssellänge von DES}
\begin{itemize*}
\item Doppelter DES: Da DES nicht geschlossen ist, führt die doppelte Verschlüsselung zu einer Chiffre, die 112-Bit-Schlüssel verwendet
\begin{itemize*}
\item kann mit Aufwand von $2^{56}$ angegriffen werden.
\item Da $C=E(K_2,E(K_1,P)) \Rightarrow X:=E(K_1,P)=D(K_2,C)$
\item Wenn ein Angreifer ein bekanntes Klartext/Chiffretext-Paar erhalten kann, kann er zwei Tabellen erstellen (meet-in-the-middle-attack)
\begin{itemize*}
\item Tabelle 1 enthält die Werte von $X$, wenn $P$ mit allen möglichen Werten von $K$ verschlüsselt ist
\item Tabelle 2 enthält die Werte von $X$, wenn $C$ mit allen möglichen Werten von $K$ entschlüsselt wird
\item Sortiere die beiden Tabellen und konstruiere Schlüssel $K_{T1}|| K_{T2}$ für alle Kombinationen von Einträgen, die den gleichen Wert ergeben.
\end{itemize*}
\end{itemize*}
\item Da es für jeden beliebigen Klartext $2^{64}$ mögliche Chiffretext-Werte gibt, die mit Double-DES erzeugt werden könnten, gibt es beim ersten bekannten Klartext/Chiffretext-Paar durchschnittlich $2^{112}/2^{64}=2^{48}$ Fehlalarme
\item Jedes weitere Klartext/Chiffretext-Paar verringert die Chance, einen falschen Schlüssel zu erhalten, um den Faktor $1/2^{64}$, so dass bei zwei bekannten Blöcken die Chance $2^{-16}$ beträgt
\item Der Aufwand, der erforderlich ist, um Double DES zu knacken, liegt also in der Größenordnung von $2^{56}$, was nur geringfügig besser ist als der Aufwand von $2^{55}$, der erforderlich ist, um Single DES mit einem Angriff mit bekanntem Klartext zu knacken, und weit entfernt von den $2^{111}$, die wir von einer Chiffre mit einer Schlüssellänge von 112 Bit erwarten würden
\item Diese Art von Angriff kann durch die Verwendung eines dreifachen Verschlüsselungsschemas umgangen werden, wie es 1979 von W. Tuchman vorgeschlagen wurde
\item $C=E(K_3,D(K_2,E(K_1,P)))$
\item Die Verwendung der Entschlüsselungsfunktion D in der Mitte ermöglicht die Verwendung von Dreifachverschlüsselungsgeräten mit Gegenstellen, die nur Einfachverschlüsselungsgeräte besitzen, indem $K_1=K_2=K_3$ gesetzt wird
\item Dreifachverschlüsselung kann mit zwei (Einstellung $K_1=K_3$) oder drei verschiedenen Schlüsseln verwendet werden
\item Bislang keine praktischen Angriffe gegen dieses Verfahren bekannt
\item Nachteil: die Leistung beträgt nur $1/3$ der einfachen Verschlüsselung, so dass es besser sein könnte, gleich eine andere Chiffre zu verwenden, die eine größere Schlüssellänge bietet
\end{itemize*}
\subsection{Fortgeschrittener Verschlüsselungsstandard AES}
\begin{itemize*}
\item Oktober 2000: Rijndael als Vorschlag des NIST für AES
\item Rundenbasierte symmetrische Chiffre
\item Keine Feistel-Struktur (versch. Ver- und Entschlüsselung)
\item Schlüssellänge: 128, 192, oder 256 Bit
\item Blocklänge: 128, 192 oder 256 Bit (nur 128 standardisiert)
\item Anzahl der Runden: 10, 12, 14
\item Der Algorithmus arbeitet mit
\begin{itemize*}
\item $state[4, 4]$: ein Byte-Array mit 4 Zeilen und 4 Spalten %(für 128-Bit-Blockgröße)
\item $key[4, 4]$: ein Array mit 4 Zeilen und 4 Spalten %(für 128-Bit-Schlüsselgröße)
\end{itemize*}
\item Verschlüsselung: (für eine Block- und Schlüsselgröße von 128 Bit) in Runden $1-9$ werden vier Operationen verwendet
\begin{description*}
\item[ByteSub] nicht-lineare Byte-Substitution durch feste Tabelle (s-Box)
\item[ShiftRow] Zeilen des Zustands zyklisch um verschiedene Offsets verschoben
\item[MixColumn] die Spalten von $state[]$ werden als Polynome über $GF(2^8)$ betrachtet und modulo $x^4+1$ mit einer festen Matrix multipliziert: $\begin{pmatrix} 02&03&01&01\\ 01&02&03&01 \\ 01&01&02&03\\ 03&01&01&02 \end{pmatrix}$
\item[RoundKey] ein Round-Key wird mit dem Status XORiert
\item[Runde 10] nutzt Operation MixColumn NICHT
\end{description*}
% \includegraphics[width=\linewidth]{Assets/NetworkSecurity-rijndael-one-round.png}
\item Entschlüsselung
\begin{itemize*}
\item Rundenschlüssel und Operationen in umgekehrter Reihenfolge
\item MixColumn-Schritt kann nur durch Multiplikation mit der inversen Matrix (auch über $GF(2^8)$) invertiert werden
\item $\begin{pmatrix} 0e&0b&0d&09\\ 09&0e&0b&0d\\ 0d&09&0e&0b\\ 0b&0d&09&0e \end{pmatrix}$
\item Oft werden tabellarische vorberechnete Lösungen verwendet, die mehr Platz benötigen
\end{itemize*}
\end{itemize*}
Sicherheit
\begin{itemize*}
%\item Die einfache mathematische Struktur von AES ist der Hauptgrund für seine Geschwindigkeit, führte aber auch zu Kritik
\item Nur die ByteSub-Funktion ist wirklich nichtlinear und verhindert effektive Analyse
\item AES kann als große Matrix-Operation beschrieben werden
\item Bereits während der Standardisierung wurden Angriffe für reduzierte Versionen entwickelt
\begin{itemize*}
\item Ein Angriff mit $2^{32}$ gewähltem Klartext gegen eine 7-Runden-Version von AES
\item Signifikante Reduktion der Komplexität auch für eine 9-Runden-Version von AES mit 256-Schlüsselgröße mit einem zugehörigen Schlüsselangriff
\end{itemize*}
\item 2011 erster Angriff gegen vollständigen AES bekannt
\begin{itemize*}
\item Schlüsselwiederherstellung in $2^{126.1}$ für AES mit 128 Bit, $2^{189.7}$ für AES mit 192 Bit, $2^{254.4}$ für AES mit 256 Bit
\item Praktischer Angriff (geht nicht von verwandten Schlüsseln aus)
\item nur ein kleiner Kratzer in Anbetracht von 10 Jahren kryptographischer Forschung
\end{itemize*}
\end{itemize*}
\subsection{Stromchiffre-Algorithmus RC4}
\begin{itemize*}
\item Stromchiffre, die 1987 von Ron Rivest erfunden wurde
\item RC4 wird im Output-Feedback-Modus (OFB) betrieben
\begin{itemize*}
\item Der Verschlüsselungsalgorithmus erzeugt eine Pseudozufallsfolge $RC4(IV,K)$, die nur vom Schlüssel K und einem Initialisierungsvektor IV abhängt
\item Der Klartext $P_i$ wird dann mit der Pseudozufallssequenz XOR-verknüpft, um den Chiffretext zu erhalten %und umgekehrt
\item $C_1 = P_1\oplus RC4 (IV_1,K)$
\item $P_1 = C_1\oplus RC4 (IV_1,K)$
\end{itemize*}
\item Pseudo-Zufallsfolge wird oft als Keystream bezeichnet
\item Keystream niemals wiederverwenden, entscheidend für Sicherheit (XOR zweier Klartexte erhalten)
%\item Wenn der Keystream wiederverwendet wird (d.h. $IV_1=IV_2$ mit demselben $K$), dann kann das XOR zweier Klartexte erhalten werden %$C_1\oplus C_2= P_1\oplus RC4(IV, K)\oplus P_2\oplus RC4(IV,K) = P_1\oplus P_2$
\item RC4 verwendet einen Schlüssel variabler Länge bis zu 2048 Bit
\item Eig. dient Schlüssel als Seed für Pseudo-Zufallsgenerator
\item RC4 arbeitet mit zwei 256-Byte-Arrays: $S[0,255], K[0,255]$
\begin{enumerate*}
\item Initialisierung der Arrays
%\begin{Shaded} % \begin{Highlighting}[] % \ControlFlowTok{for}\NormalTok{ (i = }\DecValTok{0}\NormalTok{; i < }\DecValTok{256}\NormalTok{; i++){} % \NormalTok{ S[i] = i; }\CommentTok{// Array S[] mit 0 bis 255 füllen} % \NormalTok{}} % \CommentTok{// Füllen des Arrays K[] mit dem Schlüssel und IV durch Wiederholung, bis K[] gefüllt ist} % \NormalTok{n = }\DecValTok{0}\NormalTok{;} % \ControlFlowTok{for}\NormalTok{ (i =}\DecValTok{0}\NormalTok{; i < }\DecValTok{256}\NormalTok{; i++) {} % \NormalTok{ n = (n + S[i] + K[i]) MOD }\DecValTok{256}\NormalTok{; swap(S[i], S[n]); } % \NormalTok{}} % \end{Highlighting} %\end{Shaded}
\item Erzeugen des Schlüsselstroms (nach Init $i=0;n=0;$)
%\begin{Shaded} % \begin{Highlighting}[] % \NormalTok{i = (i + }\DecValTok{1}\NormalTok{) MOD }\DecValTok{256}\NormalTok{; n = (n + S[i]) MOD }\DecValTok{256}\NormalTok{;} % \NormalTok{swap(S[i], S[n]);} % \NormalTok{t = (S[i] + S[n]) MOD }\DecValTok{256}\NormalTok{;} % \NormalTok{Z = S[t]; }\CommentTok{// Z enthält 8 Bit des durch eine Iteration erzeugten Schlüsselstroms} % \end{Highlighting} %\end{Shaded}
\item XOR-Verknüpfung des Schlüsselstroms mit dem Klartext% oder Chiffretext
\end{enumerate*}
\item Sicherheit von RC4
\begin{itemize*}
\item Sicherheit gegen Brute-Force-Angriffe
\item variable Schlüssellänge bis 2048 Bit
\item durch Verringerung der Schlüssellänge beliebig unsicher
\item RSA Data Security Inc. behauptet, RC4 sei immun gegen differentielle und lineare Kryptoanalyse und es seien keine kleinen Zyklen bekannt
\end{itemize*}
\item RC4 mit 40-Bit-Schlüsseln hatte einen besonderen Exportstatus%, selbst als andere Chiffren nicht aus den USA exportiert werden durften
\begin{itemize*}
\item SSL verwendet RC4 mit 40-Bit-Schlüsseln %als Standardalgorithmus
\item Schlüssellänge von 40 Bit nicht immun gegen Brute-Force
\end{itemize*}
\item Je nach Schlüsselplanung kann RC4 stark verwundbar sein
\item empfohlen min. erste 3072 Bytes des Schlüsselstroms zu verwerfen
\item sollte nicht mehr verwendet werden%, auch nicht bei längeren Schlüsseln
\end{itemize*}
\subsection{KASUMI}
\begin{itemize*}
\item Verwendet zur Verschlüsselung von Anrufen in GSM und UMTS
\item Entwickelt für Hardware-Implementierung ($<10k$ Gatter)
\item Schnelle Implementierung möglich
\item 64-Bit-Blockgröße, 128-Bit-Schlüssellänge
\item 8 Runden Feistel-Netzwerk
\item Sicherheitsspanne nicht sehr groß
\end{itemize*}
\begin{center}
\includegraphics[width=.6\linewidth]{Assets/NetworkSecurity-kasumi-singe-iteration.png}
\end{center}
\begin{itemize*}
\item linke 32 Bit der zu verschlüsselnden Daten werden durch zwei nichtlineare Funktionen FO und FL verändert, die beide Schlüsselmaterial verwenden
\item Reihenfolge, in der FO und FL angewendet werden, hängt von Rundenzahl ab
\item FL teilt die Daten in 16-Bit-Wörter auf, die mit Schlüsselmaterial kombiniert, permutiert und mit den Originalwerten XOR-verknüpft werden
\item FO ist ein 3-Runden-Feistel-Netzwerk mit einer Modifizierungsfunktion FI, die selbst ein Feistel-ähnliches Netzwerk ist, das zwei s-Boxen verwendet
\item Der Ausgang des obigen Schritts wird mit den rechten 32 Bit der Daten XOR-verknüpft, was zu den neuen rechten 32 Bit der Daten führt
\item neue linke 32-Bit der Daten ist rechte Wert der vorherigen Iteration
\end{itemize*}
Sicherheit
\begin{itemize*}
\item reduzierte Version (6 Runden) kann durch unmögliche differentielle Kryptoanalyse angegriffen werden, bei der unmögliche Zustände der Chiffre aus Chiffretext/Klartext-Paaren abgeleitet werden (Zeitkomplexität von $2^{100}$)
%\begin{itemize*}
%\item Erste Veröffentlichung bereits ein Jahr nach der Standardisierung
%\end{itemize*}
\item Für Vollversion von KASUMI verwandte Schlüsselangriffe möglich
\begin{itemize*}
\item Ausgewählter Klartextangriff, bei dem der Angreifer dieselben Daten mit mehreren ,,verwandten'' Schlüsseln verschlüsseln kann
\item Zeitkomplexität von $2^{76.1}$ und $2^{32}$ im besten Fall
\item Bedingungen, unter denen Angreifer Zugang zu verwandten Schlüsseln in 3G-Netzen haben, sehr selten
%\item MISTY von diesen Angriffen nicht betroffen
\end{itemize*}
\item ETSI hat jedoch SNOW 3G eingeführt, um auf eine vollständige Verletzung von KASUMI vorbereitet zu sein
\begin{itemize*}
\item Stromchiffre basierend auf LFSR, in 7.500 ASIC-Gattern %implementiert
\item anfällig für verwandte Schlüsselangriffe
\end{itemize*}
\end{itemize*}
\section{Asymmetrische Kryptographie}
\begin{itemize*}
\item zwei verschiedene Schlüssel $-K$ und $+K$
\item mit Chiffretext $c=E(+K, m)$ und $+K$ sollte es nicht möglich sein, $m=D(-K,c) =D(-K,E(+K,m))$ zu berechnen
\item Berechnung von $-K$ bei $+K$ nicht möglich sein sollte
\item $-K_A$ nur einer Entität A bekannt, privater Schlüssel
\item $+K_A$ öffentlich bekannt, öffentlicher Schlüssel
\begin{description*}
\item[Verschlüsselung] Nachricht mit $+K_A$ verschlüsselt, kann nur mit $-K_A$ entschlüsselT werden
\item[Signieren] Nachricht mit $-K_A$ verschlüsselt, kann jeder Signatur mit $+K_A$ verifizieren
\item[Achtung] Entscheidend ist, dass jeder nachprüfen kann, dass er wirklich den öffentlichen Schlüssel von A kennt und nicht den Schlüssel eines Gegners
\end{description*}
\item Entwurf von asymmetrischen Kryptosystemen
\begin{itemize*}
\item Finde einen Algorithmus und eine Methode, zwei Schlüssel $-K$, $+K$ so zu konstruieren, dass es nicht möglich ist, $E(+K, m)$ mit der Kenntnis von $+K$ zu entschlüsseln
\item Schlüssellänge sollte ,,überschaubar'' sein
\item Verschlüsselte Nachrichten sollten nicht beliebig länger sein als unverschlüsselte Nachrichten
\item Ver- und Entschlüsselung sollten nicht zu viele Ressourcen verbrauchen (Zeit, Speicher)
\item Idee: Man nehme ein Problem aus dem Bereich der Mathematik/Informatik, das schwer zu lösen ist, wenn man nur $+K$ kennt, aber leicht zu lösen, wenn man $-K$ kennt
\end{itemize*}
\end{itemize*}
\begin{description*}
\item[Knapsack-Probleme] Grundlage der ersten funktionierenden Algorithmen, leider fast alle als unsicher erwiesen
\item[Faktorisierungsproblem] Grundlage des RSA-Algorithmus
\item[Diskreter-Logarithmus-Problem] Grundlage von Diffie-Hellman und ElGamal
\end{description*}
\subsection{Einige mathematische Hintergründe}
\begin{itemize*}
\item Sei $\mathbb{Z}$ die Menge der ganzen Zahlen, und $a,b,n\in\mathbb{Z}$
\item $a$ teilt $b(a| b)$ wenn es eine ganze Zahl $k\in\mathbb{Z}$ gibt, so dass $a\times k=b$
\item $a$ ist prim, wenn a positiv und einzige Teiler von a $1$ und $a$
\item $r$ ist der Rest von a geteilt durch $n$, wenn $r=a-\lfloor a / n \rfloor\times n$, wobei $\lfloor x\rfloor$ die größte ganze Zahl kleiner oder gleich $x$ ist
%\begin{itemize*}
% \item Beispiel: 4 ist der Rest von 11 geteilt durch 7 als $4=11-\lfloor 11/7\rfloor\times 7$
% \item Wir können dies auch anders schreiben: $a=q\times n + r$ mit $q=\lfloor a/n\rfloor$
%\end{itemize*}
\item Für Rest $r$ von a durch n schreiben wir $a\ MOD\ n$
\item b ist kongruent $a\ mod\ n$, wenn es bei der Division durch n den gleichen Rest wie a hat. Also teilt n $(a-b)$, und wir schreiben $b\equiv a\ mod\ n$
%\item Beispiele: $4\equiv 11\ mod\ 7$, $25\equiv 11\ mod\ 7$, $11\equiv 25\ mod\ 7$, $11\equiv 4\ mod\ 7$, $-10\equiv 4\ mod\ 7$
\item Da der Rest r der Division durch n immer kleiner als n ist, stellt man manchmal die Menge ${x\ mod\ n | x\in\mathbb{Z}}$ durch Elemente der Menge $\mathbb{Z}_n={0, 1, ..., n-1}$ dar
\end{itemize*}
\begin{tabular}{l|l}
Eigenschaft & Ausdruck \\\hline
Kommutativ & $(a + b)\ mod\ n = (b+ a)\ mod\ n$ \\
& $(a \times b)\ mod\ n = (b \times a)\ mod\ n$ \\
Assoziativ & $[(a + b) + c]\ mod\ n =[a + (b + c)]\ mod\ n$ \\
& $[(a \times b) \times c]\ mod\ n =[a \times (b \times c)]\ mod\ n$ \\
Distributiv & $[a \times (b + c)]\ mod\ n =[(a \times b) + (a \times c)]\ mod\ n$ \\
Identitäten & $(0 + a)\ mod\ n = a\ mod\ n$ \\
& $(1 \times a)\ mod\ n = a\ mod\ n$ \\
Inverse & $\forall a \in \mathbb{Z}n: \exists (-a)\in \mathbb{Z}n : a + (-a) \equiv 0\ mod\ n$ \\
& p is prime $\Rightarrow \forall a\in \mathbb{Z}p: \exists (a-1) \in \mathbb{Z}p: a \times (a-1) \equiv 1\ mod\ p$
\end{tabular}
Größter gemeinsamer Teiler
\begin{itemize*}
%\item $c = gcd(a, b) :\Leftrightarrow ( c | a) \wedge ( c | b) \wedge ,,\forall d: ( d | a ) \wedge ( d | b) \Rightarrow ( d | c )''$ und $gcd(a, 0 ) : = | a |$
\item Der gcd-Rekursionssatz $\forall a, b \in \mathbb{Z}^+: gcd(a, b) = gcd(b, a\ mod\ b)$
%\item Da $gcd(a, b)$ sowohl a als auch b teilt, teilt es auch jede Linearkombination von ihnen%, insbesondere $(a- \lfloor a / b \rfloor \times b) = a\ mod\ b$, also $gcd(a, b) | gcd(b, a\ mod\ b)$
%\item Da $gcd(b, a\ mod\ b)$ sowohl b als auch $a\ mod\ b$ teilt, teilt es auch jede Linearkombination von beiden, insbesondere $\lfloor a / b \rfloor \times b + (a\ mod\ b) = a$, also $gcd(b, a\ mod\ b) | gcd(a, b)$
%\item Euklidischer Algorithmus: aus $a, b$ berechnet $gcd(a, b)$
%\begin{Shaded}
% \begin{Highlighting}[]
% \DataTypeTok{int}\NormalTok{ Euclid(}\DataTypeTok{int}\NormalTok{ a, b){}
% \ControlFlowTok{if}\NormalTok{ (b = }\DecValTok{0}\NormalTok{) { }\ControlFlowTok{return}\NormalTok{(a); }}
% \NormalTok{ {}\ControlFlowTok{return}\NormalTok{(Euclid(b, a\ mod\ b);} }
% \NormalTok{}}
% \end{Highlighting}
%\end{Shaded}
\item Erweiterter euklidischer Algorithmus%: für $a, b$ berechnet $d, m, n$ so, dass $d = gcd(a, b) = m \times a + n \times b$
%\begin{Shaded}
% \begin{Highlighting}[]
% \KeywordTok{struct}\NormalTok{{}\DataTypeTok{int}\NormalTok{ d, m, n} ExtendedEuclid(}\DataTypeTok{int}\NormalTok{ a, b)}
%% \NormalTok{{ }\DataTypeTok{int}\NormalTok{ d, d}\CharTok{\textquotesingle{},}\ErrorTok{ m, m}\CharTok{\textquotesingle{}}\NormalTok{, n, n}\CharTok{\textquotesingle{};}
% \ControlFlowTok{if}\NormalTok{ (b = }\DecValTok{0}\NormalTok{) {}\ControlFlowTok{return}\NormalTok{(a, }\DecValTok{1}\NormalTok{, }\DecValTok{0}\NormalTok{); }}
% \NormalTok{ (d}\CharTok{\textquotesingle{},}\ErrorTok{ m}\CharTok{\textquotesingle{}}\NormalTok{, n}\CharTok{\textquotesingle{})}\ErrorTok{ = ExtendedEuclid(b, a MOD b);}
% \NormalTok{ (d, m, n) = (d}\CharTok{\textquotesingle{},}\ErrorTok{ n}\CharTok{\textquotesingle{}}\NormalTok{, m}\CharTok{\textquotesingle{} }\ErrorTok{{-} \\lfloor a / b \\rfloor \\times n}\CharTok{\textquotesingle{}}\NormalTok{);}
% \ControlFlowTok{return}\NormalTok{(d, m, n); }}
% \end{Highlighting}
%\end{Shaded}
\begin{itemize*}
\item Grundfall $(a,0): gcd(a, 0) = a = 1 \times a + 0 \times 0$
\item Induktion von $(b, a\ mod\ b)$ auf $(a, b)$
\begin{itemize*}
\item ExtendedEuclid berechnet $d', m', n'$ korrekt
\item $d=d'=m'\times b+n'\times (a\ mod\ b)=m'\times b+n'\times (a-\lfloor a/b\rfloor\times b)=n'\times a+(m'-\lfloor a/b\rfloor\times n')\times b$
\end{itemize*}
\item Laufzeit von $Euclid$ und $ExtendedEuclid$ ist $O(log\ b)$
\end{itemize*}
\item Lemma: Sei $a,b\in\mathbb{N}$ und $d=gcd(a,b)$. Dann gibt es $m,n\in\mathbb{N}$ so, dass: $d=m\times a+n \times b$
\item Euklid: Wenn eine Primzahl das Produkt zweier ganzer Zahlen teilt, dann teilt sie mindestens eine der ganzen Zahlen: $p|(a\times b)\Rightarrow (p| a)\times(p| b)$
%\begin{itemize*}
% \item Der Beweis: Es sei $p|(a\times b)$
% \item Wenn $p| a$ dann sind wir fertig
% \item Wenn nicht, dann $gcd(p,a) = 1 \Rightarrow\exists m, n\in\mathbb{N}:1=m\times p+n\times a \Leftrightarrow b=m\times p \times b + n \times a \times b$
% \item Da $p|(a\times b)$, teilt p beide Summanden der Gleichung und somit auch die Summe, die b ist
%\end{itemize*}
\item Fundamentalsatz der Arithmetik: Die Faktorisierung in Primzahlen ist bis zur Ordnung eindeutig
%\item verwende Theorem 2, um folgende Korollarie zu beweisen
%\begin{itemize*}
% \item Wenn $gcd(c,m)=1$ und $(a\times c)\equiv(b\times c)mod\ m$, dann $a\equiv b\ mod\ m$
%\item Der Beweis: Da $(a\times c)\equiv(b\times c)mod\ m\Rightarrow\exists n\in\mathbb{N}:(a\times c)-(b\times c)=n\times m$
%\item $\Leftrightarrow ( a - b ) \times c = n \times m$
%\item $\Leftrightarrow p_1\times ...\times p_i\times q_1\times ...\times q_j=r_1\times ...\times r_k\times s_1\times ...\times s_l$
% \item $p$, $q$, $r$ und $s$ sind Primzahlen und müssen nicht verschieden sein aber da $gcd(c,m)=1$, gibt es keine Indizes g, h, so dass $q_g = s_h$
%\item Wir können also die Gleichung fortlaufend durch alle q's teilen, ohne jemals ein $s$ zu ,,eliminieren'' und erhalten schließlich etwas wie $\Leftrightarrow p_1\times ...\times p_i=r_1\times ...\times r_o\times s_1\times ...\times s_l$ (beachten Sie, dass es weniger r's geben wird)
% \item[$\Leftrightarrow$] $(a-b)=r_1\times ...\times r_o\times m\Rightarrow a \equiv b\ mod\ m$
%\end{itemize*}
\item Bezeichne $\phi(n)$ die Anzahl der positiven ganzen Zahlen, die kleiner als n und relativ zu n prim sind
\begin{itemize*}
\item Beispiele: $\phi(4) = 2$, $\phi(6)=2$, $\phi(7)=6$, $\phi(15)=8$
\item Wenn p eine Primzahl ist $\Rightarrow\phi(p)=p-1$
\end{itemize*}
\item Euler: Seien n und b positive und relativ primäre ganze Zahlen, d.h. $gcd(n, b) = 1 \Rightarrow b \phi(n) \equiv 1\ mod\ n$
\begin{itemize*}
%\item Sei $t=\phi(n)$ und $a_1,...a_t$ seien die positiven ganzen Zahlen kleiner als $n$, die relativ zu $n$ prim sind. Definieren Sie $r_1,...,r_t$ als die Residuen von $b\times a_1\ mod\ n , ..., b\times a_t\ mod\ n$, d.h.: $b\times a_i \equiv r_i\ mod\ n$.
\item Beachten Sie, dass $i\not= j \Rightarrow r_i\not= r_j$%. Wäre dies nicht der Fall, hätten wir $b\times a_i\equiv b\times a_j\ mod\ n$ und da $gcd(b,n)=1$, würde Korollar 1 $a_i\equiv a_j\ mod\ n$ implizieren, was nicht sein kann, da $a_i$ und $a_j$ per Definition verschiedene ganze Zahlen zwischen 0 und n sind
%\item Wir wissen auch, dass jedes $r_i$ relativ prim zu n ist, denn jeder gemeinsame Teiler k von $r_i$ und $n$ , d.h. $n=k\times m$ und $r_i=p_i\times k$, müsste auch $a_i$ teilen,
%\item da $b\times a_i$gleich $(p_i\times k)\ mod\ (k\times m)\Rightarrow\exists s\in\mathbb{N}:(b\times a_i)-(p_i\times k)=s\times k\times m \Leftrightarrow (b\times a_i)=s\times k\times m+(p_i\times k)$
%\item Da k jeden der Summanden auf der rechten Seite dividiert und k nicht durch b dividiert (n und b sind relativ prim), müsste es auch $a_i$ dividieren, das relativ prim zu n sein soll
%\item Somit ist $r_1, ...,r_t$ eine Menge von $\phi(n)$ verschiedenen ganzen Zahlen, die relativ prim zu $n$ sind. Das bedeutet, dass sie genau dasselbe sind wie $a_1,...a_t$, nur dass sie in einer anderen Reihenfolge stehen. Insbesondere wissen wir, dass $r_1\times ...\times r_t=a_1\times ...\times a_t$
\item Wir verwenden nun die Kongruenz $r_1\times ...\times r_t\equiv b\times a_1\times ...\times b\times a_t\ mod\ n$ $\Leftrightarrow r_1\times ...\times r_t\equiv b_t\times a_1\times ...\times a_t\ mod\ n$ $\Leftrightarrow r_1\times ...\times r_t\equiv b_\times r_1\times ...\times r_t\ mod\ n$
\item Da alle $r_i$ relativ prim zu $n$ sind, können wir Korollar 1 anwenden und durch ihr Produkt dividieren: $1\equiv b_t\ mod\ n \Leftrightarrow 1\equiv b\phi(n)\ mod\ n$
\end{itemize*}
\item Chinesischer Restssatz Theorem
\begin{itemize*}
\item Seien $m_1,...,m_r$ positive ganze Zahlen, die paarweise relativ prim sind,
\item d.h. ganz $i\not= j:gcd(m_i, m_j) = 1$. Seien $a_1,...,a_r$ beliebige ganze Zahlen
\item Dann gibt es eine ganze Zahl a derart, dass
\begin{itemize*}
\item $a\equiv a_1\ mod\ m_1$
\item $a\equiv a_2\ mod\ m_2$
\item ...
\item $a\equiv a_r\ mod\ m_r$
\end{itemize*}
\item Außerdem ist a eindeutig modulo $M := m_1\times ...\times m_r$
\item Für alle $i\in{1,...,r}$ definieren wir $M_i:=(M/m_i)\phi(m_i)$
\item Da $M_i$ per Definition relativ prim zu $m_i$ ist, können wir Theorem 3 anwenden und wissen, dass $M_i\equiv 1\ mod\ m_i$
\item Da $M_i$ durch $m_j$ für jedes $j\not= i$ teilbar ist, haben wir $\forall j\not= i:M_i\equiv 0\ mod\ m_j$ \item Wir können nun die Lösung konstruieren, indem wir definieren: $a:= a_1\times M_1+a_2\times M_2+...+a_r\times M_r$
%\item Die beiden oben angeführten Argumente bezüglich der Kongruenzen der $M_i$ implizieren, dass a tatsächlich alle Kongruenzen erfüllt
%\item Um zu sehen, dass a eindeutig modulo $M$ ist, sei b eine beliebige andere ganze Zahl, die die r Kongruenzen erfüllt. Da $a\equiv c\ mod\ n$ und $b\equiv c\ mod\ n \Rightarrow a \equiv b\ mod\ n$ haben wir $\forall i\in{1,...,r}:a\equiv b\ mod\ m_i\Rightarrow\forall i\in{1,. ...,r}:m_i|(a-b) \Rightarrow M|(a-b)$, da die $m_i$ paarweise relativ prim sind $\Leftrightarrow a\equiv b\ mod\ M$
\end{itemize*}
\item Lemma: Wenn $gcd(m,n)=1$, dann ist $\phi(m\times n)=\phi(m)\times \phi(n)$
%\begin{itemize*}
%\item Sei a eine positive ganze Zahl, die kleiner als und relativ prim zu $m\times n$ ist. Mit anderen Worten: a ist eine der ganzen Zahlen, die von $\phi(m\times n)$ gezählt werden.
%\item Betracht $a\rightarrow(a\ mod\ m, a\ mod\ n)$. Die ganze Zahl $a$ ist relativ prim zu m und relativ prim zu n. Also ist $(a\ mod\ m)$ relativ prim zu m und $(a\ mod\ n)$ ist relativ prim zu n, da: $a=\lfloor a/m\rfloor\times m + (a\ mod\ m)$, wenn es also einen gemeinsamen Teiler von $m$ und $(a\ mod\ m)$ gäbe, würde dieser Teiler auch a teilen. %Somit entspricht jede Zahl a, die durch $\phi(m\times n )$ gezählt wird, einem Paar von zwei ganzen Zahlen $(a\ mod\ m,a\ mod\ n)$, wobei die erste durch $\phi(m)$ und die zweite durch $\phi(n)$ gezählt wird.
%\item Aufgrund des zweiten Teils von Satz 4 ist die Einzigartigkeit der Lösung $a\ mod\ (m\times n)$ der simultanen Kongruenzen: $a \equiv(a\ mod\ m)\ mod\ m$, $a \equiv(a\ mod\ n)\ mod\ n$ können wir ableiten, dass verschiedene ganze Zahlen, die durch $\phi(m\times n)$ gezählt werden, verschiedenen Paaren entsprechen
%\item Um dies zu sehen, nehmen wir an, dass $a\not=b$, gezählt durch $\phi(m\times n)$, demselben Paar $(a\ mod\ m, a\ mod\ n)$ entspricht. Dies führt zu einem Widerspruch, da b auch die Kongruenzen erfüllen würde: $b\equiv (a\ mod\ m)\ mod\ m$ $b\equiv (a\ mod\ n)\ mod\ n$ aber die Lösung dieser Kongruenzen ist eindeutig modulo $(m \times n)$
%\item $\phi(m \times n)$ ist höchstens die Anzahl solcher Paare: $\phi(m \times n)\leq \phi(m)\times \phi(n)$
%\item Betrachten wir nun ein Paar von ganzen Zahlen $(b,c)$, von denen eine mit $\phi(m)$ und die andere mit $\phi(n)$ gezählt wird:
%Mit Hilfe des ersten Teils von Satz 4 können wir eine einzige positive ganze Zahl a konstruieren, die kleiner als und relativ prim zu $m\times n$ ist: $a\equiv b\ mod\ m$ und $a\equiv c\ mod\ n$. Die Anzahl solcher Paare ist also höchstens $\phi(m \times n):\phi(m \times n)\leq\phi(m)\times\phi(n)$
%\end{itemize*}
\item Definition: endliche Gruppen
\begin{itemize*}
\item Eine Gruppe $(S, \oplus)$ ist eine Menge S zusammen mit einer binären Operation $\oplus$, für die die folgende Eigenschaften gelten
\item Geschlossenheit: Für alle $a, b \in S$ , haben wir $a \oplus b \in S$
\item Identität: Es gibt ein Element $e \in S$ , so dass $e \oplus a = a \oplus e = a$ für alle $a \in S$
\item Assoziativität: Für alle $a, b, c \in S$ , gilt $( a \oplus b ) \oplus c = a \oplus ( b \oplus c )$
\item Inversen: Für jedes $a \in S$ , gibt es ein einziges Element $b \in S$ , so dass dass $a \oplus b = b \oplus a = e$
\item Erfüllt eine Gruppe $( S , \oplus)$ das Kommutativgesetz $\forall a, b \in S : a \oplus b = b \oplus a$ dann nennt man sie eine abelsche Gruppe
\item Wenn eine Gruppe $( S , \oplus)$ nur eine endliche Menge von Elementen hat, d.h. $|S| < \infty$, dann wird sie eine endliche Gruppe genannt
\end{itemize*}
%\item Beispiele:
%\begin{itemize*}
% \item $(\mathbb{Z}_n , +_n)$
% \begin{itemize*}
% \item mit $\mathbb{Z}_n:={,,0''_n,,,1''_n,...,,,n-1''_n}$
% \item wobei $,,a''_n:={b \in \mathbb{Z} | b \equiv a mod n}$ und
% \item $+_n$ ist so definiert, dass $,,a''_n+_n,,b''_n=,,a+b''_n$
% \item eine endliche abelsche Gruppe ist. Für den Beweis siehe die Tabelle mit den Eigenschaften der modularen Arithmetik
% \end{itemize*}
% \item $(\mathbb{Z}^*_n , \times_n)$
% \begin{itemize*}
% \item mit $\mathbb{Z}^*_n :={,,a''_n\in \mathbb{Z}_n | gcd(a,n)=1}$, und
% \item $\times_n$ ist so definiert, dass $,,a''_n\times_n ,,b''_n=,,a\times b''_n$
% \item eine endliche abelsche Gruppe ist. Man beachte, dass $\mathbb{Z}^*_n$ nur die Elemente von $\mathbb{Z}_n$ enthält, die eine multiplikative Inverse modulo n haben. Zum Beweis siehe Eigenschaften der modularen Arithmetik
% \item Beispiel: $\mathbb{Z}^*_{{15}={,,1''}{15},,,2''_{{15},,,4''}{15},,,7''_{{15},,,8''}{15},,,11''_{{15},,,13''}{15},,,14''_{15}}$, als $1\times 1\equiv 1 mod 15$, $2 \times 8 \equiv 1 mod 15$, $4 \times 4 \equiv 1 mod 15$, $7 \times 13 \equiv 1 mod 15$, $11 \times 11 \equiv 1 mod 15$, $14 \times 14 \equiv 1 mod 15$ \end{itemize*}
%\end{itemize*}
\item Wenn klar ist, dass es sich um $(\mathbb{Z}_n, +_n)$ oder $(\mathbb{Z}^*_n,\times_n)$ handelt, werden Äquivalenzklassen $,,a''_n$ oft durch ihre repräsentativen Elemente a dargestellt und $+_n$ und $\times_n$ durch $+$ bzw. $\times$ bezeichnet
\item Definition: endliche Felder
\begin{itemize*}
\item Ein Feld $(S,\oplus, \otimes)$ ist eine Menge S zusammen mit zwei Operationen $\oplus$, $\otimes$, so dass
\item $(S,\oplus)$ und $(S\backslash{e_{\oplus}},\otimes)$ sind kommutative Gruppen, d.h. nur das Identitätselement bezüglich der Operation $\oplus$ muss kein Inverses bezüglich der Operation $\otimes$ haben
\item Für alle $a,b,c\in S$ haben wir ein $\otimes(b\oplus c)=(a\otimes b)\oplus(a\otimes c)$
\end{itemize*}
\item Wenn $| S|<\infty$ dann heißt $(S,\oplus,\otimes)$ ein endliches Feld
%\item Beispiel: $(\mathbb{Z}_p, +_p, \times_p)$ ist ein endliches Feld für jede Primzahl p
\item Definition: Primitive Wurzel, Generator
\begin{itemize*}
\item Sei $(S,\circ)$ eine Gruppe, $g\in S$ und $g^a:=g\circ g\circ...\circ g$ (a mal mit $a\in\mathbb{Z}^+$)
\item Dann heißt g eine primitive Wurzel oder ein Generator von $(S,\circ):\Leftrightarrow{g^a|1\leq a\leq | S|}=S$
%\item Beispiele:
%\begin{itemize*}
% \item 1 ist eine primitive Wurzel von $(\mathbb{Z}_n, +_n)$
% \item 3 ist eine Primitivwurzel von $(\mathbb{Z}^*_7, \times_7)$
%\end{itemize*}
\item Nicht alle Gruppen haben Primitivwurzeln, und diejenigen, die sie haben, nennt man zyklische Gruppen
\end{itemize*}
\item Theorem: $(\mathbb{Z}^*_n, \times_n)$ hat eine primitive Wurzel $\Leftrightarrow n\in{2,4,p,2\times p^e}$, wobei p eine ungerade Primzahl ist und $e\in\mathbb{Z}^+$
\item Theorem: Wenn $(S,\circ)$ eine Gruppe ist und $b\in S$, dann ist $(S',\circ)$ mit $S'={b^a| a\in\mathbb{Z}^+}$ ebenfalls eine Gruppe
\begin{itemize*}
\item Da $S'\subseteq S, heißt (S',\circ)$ eine Untergruppe von $(S,\circ)$
\item Wenn b eine Urwurzel von $(S,\circ)$ ist, dann ist $S'=S$
\end{itemize*}
\item Definition: Ordnung einer Gruppe und eines Elements
\begin{itemize*}
\item Sei $(S,\circ)$ eine Gruppe, $e\in S$ ihr Identitätselement und $b\in S$ irgendein Element von $S$
\item Dann heiße $| S|$ die Ordnung von $(S,\circ)$
\item Sei $c\in\mathbb{Z}^+$ das kleinste Element, so dass $b^c=e$ ist (falls ein solches c existiert, falls nicht, setze $c=\infty$). Dann wird c die Ordnung von b genannt
\end{itemize*}
\item Lagrange) Ist G eine endliche Gruppe und H eine Untergruppe von G , so ist $| H|$ Teiler von $|G|$
%\item Wenn also $b in G$ ist, dann ist die Ordnung von b Teiler von $|G|$.
\item Theorem: Ist G eine zyklische endliche Gruppe der Ordnung n und d ist Teiler von n, dann hat G genau $\phi(d)$ Elemente der Ordnung $d$. Insbesondere hat G $\phi(n)$-Elemente der Ordnung $n$
\item Grundlage des Algorithmus, der zyklische Gruppe $\mathbb{Z}^*_p$ und Urwurzel g davon findet
\begin{itemize*}
\item Man wählt eine große Primzahl q, so dass $p=2q+1$ eine Primzahl ist
\item Da $p$ prim ist, besagt Satz 5, dass $\mathbb{Z}^*_p$ zyklisch ist
\item Die Ordnung von $\mathbb{Z}^*_p$ ist $2\times q$ und $\phi(2\times q)=\phi(2)\times \phi(q)=q-1$, da $q$ prim ist
\item Die Wahrscheinlichkeit, dass eine Primitivwurzel zufällig ausgewählt wird, beträgt also $(q-1)/2q \approx 1/2$
\item Um effizient zu prüfen, ob ein zufällig gewähltes g eine Urwurzel ist, müssen wir nur prüfen, ob $g^2\equiv 1\ mod\ p$ oder $g^q\equiv 1\ mod\ p$ ist. Wenn nicht, dann muss seine Ordnung $|\mathbb{Z}^*_p|$ sein, da Satz 7 besagt, dass die Ordnung von g $|\mathbb{Z}^*_p|$ teilen muss
\end{itemize*}
\item Definition: diskreter Logarithmus
\begin{itemize*}
\item Sei p eine Primzahl, g eine Urwurzel von $(\mathbb{Z}^*_p,\times_p)$ und c ein beliebiges Element von $\mathbb{Z}^*_p$. Dann gibt es z so, dass: $g^z\equiv c\ mod\ p$
\item z wird der diskrete Logarithmus von c modulo p zur Basis g genannt
%\item Beispiel 6 ist der diskrete Logarithmus von 1 modulo 7 zur Basis 3 als $3^6\equiv 1 mod 7$
\item Die Berechnung des diskreten Logarithmus z bei gegebenem g, c und p ist ein rechnerisch schwieriges Problem, und die asymptotische Laufzeit der besten bekannten Algorithmen für dieses Problem ist exponentiell zur Bitlänge von p
\end{itemize*}
\end{itemize*}
\subsection{Der RSA Public Key Algorithmus}
\begin{itemize*}
\item 1977 von R. Rivest, A. Shamir und L. Adleman erfunden %und basiert auf Theorem 3
\item Seien $p, q$ verschiedene große Primzahlen und $n=p\times q$. Nehmen wir an, wir haben auch zwei ganze Zahlen e und d, so dass: $d\times e \equiv 1\ mod\ \phi(n)$
\item M sei eine ganze Zahl, die die zu verschlüsselnde Nachricht darstellt, wobei M positiv, kleiner als und relativ prim zu n ist
%\item Beispiel: Verschlüsseln mit = 99, A = 10, B = 11, ..., Z = 35. Somit würde ,,HELLO'' als 1714212124 kodiert werden. Falls erforderlich, ist M in Blöcke kleinerer Nachrichten aufzuteilen: 17142 12124
\item Zum Verschlüsseln berechne: $E = M^e\ mod\ n$ (mit dem Quadrat- und Multiplikationsalgorithmus effizient)
\item Zum Entschlüsseln berechne: $M'=E^d\ mod\ n$
\begin{itemize*}
\item Da $d\times e\equiv 1\ mod\ \phi(n)\Rightarrow\exists k\in\mathbb{Z}:(d\times e)-1=k\times\phi(n)\Leftrightarrow(d\times e)=k\times\phi(n)+1$
\item $M'\equiv E^d\equiv M^{e\times d}\equiv M^{k\times\phi(n)+1}\equiv 1^k\times M\equiv M\ mod\ n$
\end{itemize*}
\item Da $(d\times e)=(e\times d)$ funktioniert die Operation auch in umgekehrter Richtung, d.h. man kann mit d verschlüsseln und mit e entschlüsseln
\begin{itemize*}
\item erlaubt es, die gleichen Schlüssel d und e zu verwenden
\item Empfang von Nachrichten, die mit eigenen öffentlichen Schlüssel verschlüsselt
\item Senden von Nachrichten, die mit eigenen privaten Schlüssel signiert
\end{itemize*}
\item Schlüsselpaar für RSA einrichten
\begin{itemize*}
\item Wählen zufällig zwei Primzahlen $p$ und $q$ (jeweils 100-200 Ziffern)
\item Berechne $n=p\times q,\phi(n)=(p-1)\times (q-1)$
\item Wähle zufällig $e$, so dass $gcd(e,\phi(n))=1$
\item Berechne mit dem erweiterten euklidischen Algorithmus d und c, so dass $e\times d+\phi(n)\times c=1$, wobei zu beachten ist, dass dies impliziert, dass $e\times d\equiv 1\ mod\ \phi(n)$
\item der öffentliche Schlüssel ist das Paar $(e,n)$
\item der private Schlüssel ist das Paar $(d,n)$
\end{itemize*}
\item Sicherheit des Verfahrens liegt in Schwierigkeit der Faktorisierung von $n=p\times q$, da es einfach ist, $\phi(n)$ und dann $d$ zu berechnen, wenn $p$ und $q$ bekannt sind
%\begin{itemize*}
% \item Wenn p und q bestimmte Eigenschaften erfüllen, sind die besten bekannten Algorithmen exponentiell zur Anzahl der Ziffern von n
% \item Bitte beachten Sie, dass es bei einer unglücklichen Wahl von p und q Algorithmen geben könnte, die effizienter faktorisieren können, und dass Ihre RSA-Verschlüsselung dann nicht mehr sicher ist
% \item Daher sollten p und q ungefähr die gleiche Bitlänge haben und ausreichend groß sein
% \item $(p-q)$ sollte nicht zu klein sein
% \item Wenn man einen kleinen Verschlüsselungsexponenten, z.B. 3, wählen will, kann es zusätzliche Einschränkungen geben, z.B. $gcd(p-1, 3) = 1$ und $gcd(q-1,3)=1$
% \item Die Sicherheit von RSA hängt auch davon ab, dass die erzeugten Primzahlen wirklich zufällig sind
%\end{itemize*}
\end{itemize*}
\subsection{Diffie-Hellman-Schlüsselaustausch}
\begin{itemize*}
\item erstmals 1976 veröffentlicht%, in der auch die Grundidee der asymmetrischen Kryptographie vorgestellt wurde
\item ermöglicht es zwei Parteien A und B, sich über einen öffentlichen Kanal auf ein gemeinsames Geheimnis zu einigen
\item Öffentlicher Kanal bedeutet, dass ein potentieller Angreifer E alle zwischen A und B ausgetauschten Nachrichten lesen kann
\item Es ist wichtig, dass A und B sicher sein können, dass der Angreifer nicht in der Lage ist, Nachrichten zu verändern, da er in diesem Fall einen Man-in-the-Middle-Angriff starten könnte
\item Die mathematische Grundlage ist das Problem, diskrete Logarithmen in endlichen Feldern zu finden
\item DH-Austausch ist kein asymmetrischer Verschlüsselungsalgorithmus
\item Wenn $A$ und $B$ sich auf ein gemeinsames Geheimnis $s$ einigen wollen und ihr einziges Kommunikationsmittel ein öffentlicher Kanal ist, können sie wie folgt vorgehen
\begin{itemize*}
\item $A$ wählt eine Primzahl $p$, eine primitive Wurzel $g$ von $\mathbb{Z}^*_p$ und eine Zufallszahl $q$
\begin{itemize*}
\item $A$ und $B$ können sich vor der Kommunikation auf die Werte $p$ und $g$ einigen oder $A$ wählt $p$ und $g$ und sendet sie mit seiner ersten Nachricht
\item $A$ berechnet $v=g^q\ mod\ p$ und sendet an $B:\{p,g,v\}$
\end{itemize*}
\item $B$ wählt eine Zufallszahl $r$
\begin{itemize*}
\item $B$ berechnet $w=g^r\ mod\ p$ und sendet an $A:\{p,g,w\}$ (oder $\{w\}$)
\end{itemize*}
\item Beide Seiten errechnen das gemeinsame Geheimnis
\begin{itemize*}
\item $A$ errechnet $s=w^q\ mod\ p$
\item $B$ errechnet $s'=v^r\ mod\ p$
\item Da $g^{q\times r}\ mod\ p = g^{r \times q}\ mod\ p$ ist, gilt: $s=s'$
\end{itemize*}
\item Ein Angreifer E, der den öffentlichen Kanal abhört, kann das Geheimnis $s$ nur berechnen, wenn er entweder $q$ oder $r$ berechnen kann, die die diskreten Logarithmen von $v$, $w$ modulo $p$ zur Basis $g$ sind
\end{itemize*}
\item Wenn der Angreifer E in der Lage ist, Nachrichten auf dem öffentlichen Kanal zu verändern, kann er eine Man-in-the-Middle-Angriff starten