Cryptography Reference
In-Depth Information
11.1
Ein bisschen Mathematik
Ich wünschte, es gäbe ein triviales Beispiel für ein asymmetrisches Verschlüsse-
lungsverfahren. Doch leider ist dies nicht der Fall. Es gibt allgemein nur relativ
wenige asymmetrische Verfahren und noch weniger, die wirklich sicher sind. Alle
haben sie gemeinsam, dass man mathematische Vorkenntnisse benötigt, um sie zu
verstehen. Einige dieser Vorkenntnisse will ich Ihnen in diesem Kapitel vermit-
teln. Über meine Betrachtungen wird ein Mathematiker vielleicht nur milde
lächeln. Mir geht es jedoch nicht darum, streng mathematisch vorzugehen. Viel-
mehr will ich die wichtigsten mathematischen Zusammenhänge auf möglichst
einfache Weise erklären und verzichte daher weitgehend auf Sätze und Beweise.
11.1.1
Modulo-Rechnen
Beginnen wir unsere Betrachtungen mit dem sogenannten
Modulo-Rechnen
.
Modulo-Rechnen ist das Rechnen mit natürlichen Zahlen von 0 bis zu einer
bestimmten Größe
n
(wir zählen die Null hierbei zu den natürlichen Zahlen, auch
wenn das nicht überall üblich ist). Zahlen, die größer oder gleich
n
sind, gibt es in
diesem Zusammenhang nicht. Nach
n
-1 wird wieder bei Null angefangen zu zäh-
len. Beispielsweise kann man die Stundenanzeige einer Digitaluhr als Modulo-24-
Zähler betrachten. Eine solche Anzeige zählt die Stunden von 0 bis 23 und fängt
anschließend wieder bei 0 an. Im Folgenden bezeichnet
n
immer eine natürliche
Zahl.
a
und
b
sind ebenfalls natürliche Zahlen, die stets zwischen 0 und
n
-1 liegen.
Modulo-Addition und -Subtraktion
Die beiden wichtigsten Modulo-Rechenarten, die
Modulo-Addition
und die
Modulo-Subtraktion
, entsprechen dem herkömmlichen Abziehen und Zusam-
menzählen, allerdings mit einer kleinen Änderung: Ist bei der Addition das Ergeb-
nis größer oder gleich
n
, dann zieht man
n
davon ab. Ist analog bei einer Subtrak-
tion das Ergebnis kleiner null, dann zählt man
n
dazu. Bei einer Modulo-
Addition oder -Subtraktion erhält man also in jedem Fall eine Zahl zwischen 0
und
n
-1. Um Modulo-Rechenarten von den bekannten zu unterscheiden, schreibt
man am Ende einer Gleichung jeweils »(mod
n
)«.
Beispiele:
3+5=1 (mod 7)
2+2=4 (mod 13)
3-6=6 (mod 9)
3+6=0 (mod 9)
