Zahlentheorie

Zahlentheorie:

Hallo Free-Hack Community,
mit diesem Post möchte ich ein paar mathematische Formeln erklären, die im Bereich der Ver- und Entschlüsselung unerlässlich sind.
Im Verlauf dieses Beitrags werde ich Versuchen die Zusammenhänge so einfach und präzise wie möglich zu beschreiben.

Restwertalgorithmus:
Dieser Algorithmus arbeitet mithilfe des Restwertes einer Division um eine Zahl aus dem Dezimalsystem in das Dualsystem zu konvertieren.

Ziel ist es, die Zahl 131 aus dem Dezimalsystem in das Dualsystem zu konvertieren.
Um das zu erreichen, dividieren wir diese Zahl durch 2 und notieren uns den Rest, wenn die Zahl bis zur 0 dividiert wurde erhalten wir die Zahl im Dualsystem, indem wir die notierten Reste von unten nach oben lesen.

Bsp: 131 : 2 = 65 Rest 1
65 : 2 = 32 Rest 1
32 : 2 = 16 Rest 0
16 : 2 = 8 Rest 0
8 : 2 = 4 Rest 0
4 : 2 = 2 Rest 0
2 : 2 = 1 Rest 0
1 : 2 = 0 Rest 1

131 = 10000011

Kongruenz und Restklassen:

Hier werde ich jetzt die Grundlagen der Rechnung mit modulo erläutern, da diese Rechnung im vorherigen Beispiel schon Anwendung gefunden hat.

131 = 1 Mod 2 (131 kongruent 1 modulo 2)
hier ist 1 der Rest und 2 das Modul(p. Moduln)

Anhand dieser Rechnung lässt sich auch die Restklasse definieren. Aus Gründen der Einfachheit wähle ich hier jedoch die Restklasse des Modul 5.

Restklasse modulo 5
Rest 0 {...;-15;-10;-5;0;5;10;15;...}
Rest 1 {...;-14; -9;-4;1;6;11;16;...}
Rest 2 {...;-13; -8;-3;2;7;12;17;...}
Rest 3 {...;-12; -7;-2;3:8;13;18;...}
Rest 4 {...;-11; -6;-1;4;9;14;19;...}

Daraus folgt, dass eine Zahl kongruent zu jeder Zahl ist, die in ihrer Restklasse liegt.
In der Folge bedeutet das, dass die Zahlen a und b genau dann kongruent zueinander sind, wenn sie sich um ein Vielfaches des Modul unterscheiden. (also in der selben Restklasse liegen).

Daraus folgt, dass eine Zahl kongruent zu jeder Zahl ist, die in ihrer Restklasse liegt.
In der Folge bedeutet das, dass die Zahlen a und b genau dann kongruent zueinander sind, wenn sie sich um ein Vielfaches des Modul unterscheiden. (Also in derselben Restklasse liegen).

Wochenlogformel:
Diese Erkenntnisse können wir nun dazu benutzen, um ein Problem zu lösen, welches auch in der Informatik Anwendung findet, nämlich die Berechnung des Wochentages.

Eine mögliche Fragestellung wäre diese:
Wenn der 01.01.1900 ein Montag war, welcher Wochentag war der 15.05.1955?

Um diese Aufgabe zu lösen, müssen wir auf die Schaltjahre berücksichtigen.
Die Regel ob ein Jahr ein Schaltjahr ist lautet: Alle 4 Jahre
Ausnahme: Alle Jahre die durch 100 teilbar sind, außer die Jahre, die durch 400 Teilbar sind.
(Deshalb war das Jahr 2000 ein Schaltjahr.)

Jetzt müssen wir nurnoch die Anzahl der Tage ermitteln, welchen zwischen beiden Daten liegen und diese modulo 7 rechnen.
Das Ergebnis dieser Rechnung stellt nun die Verschiebung der Wochentage dar.

(13*366)+(42*365)+31+28+31+30+14 mod 7
(6 * 2)+(0 * 1)+3+ 0+ 3+ 2+0 mod 7
12+3+3+2 = 20
20 mod 7
20 = 6 mod 7

Das bedeutet, das sich die Wochentage um 6 Einheiten verschoben haben, also von Montag auf Sonntag.
Das bedeutet, das der 15.05.1955 ein Sonntag war.

Inversen:

additives Inverse:

Ein Additives Inverse ist eine Zahl, welche zu einer anderen addiert wird, um auf das neutrale Element der entsprechenden algebraischen Struktur zu kommen.
Inversen werden zum bsp. benutzt um verschlüsselte Texte wieder zu entschlüsseln.
Dieses neutrale Element ist bei der Addition 0:
a + n = a ; n => 0
Um das additive Inverse zu bestimmen, müssen wir einen großen Aufwand betreiben.
Zu beachten ist außerdem das ein Inverses immer in der Restklasse einer Zahl liegt und nicht in der Menge der Zahlen einer Restklasse.

Bsp: e + d = 0 mod m
d ist das additive Inverse zu e
2 + 4 = 0 mod 6
4 ist das additive Inverse zu 2

multiplikatives Inverse:

Die Berechnung von multiplikativen Inversen gestaltet sich dagegen etwas schwieriger. Hier müssen wir jetzt nichtmehr auf das Ergebnis 0 kommen sondern auf das Ergebnis 1:
a * n = a ; n = 1

Für e != 0 in der Restklasse m gilt: Es gibt genau ein Multiplikatives Inverse genau dann, wenn e und m teilerfremd sind.

Um ein Multiplikatives Inverse zu bestimmen, können wir den
euklidischen Algorithmus und den erweiterten euklidischen Algorithmus benutzen.

Als Beispiel werd ich das Inverse zu 7 in der Restklasse 10 berechnen.

7 * d = 1 mod 10
Als erstes überprüfen wir mit dem
euklidischen Algorithmus => ggT(10,7)

10 = 1 * 7 + 3
7 = 2 * 3 + 1
3 = 3 * 1 + 0

Nun benutzen wir den erweiterten euklidischen Algorithmus, um das Invers zu bestimmen.

1 = 7 - (2 * 3)
1 = 7 - ( 2 * (10 - (1 * 7))
1 = 7 - ( 2 * 10 - 2 * (1 * 7))
1 = 7 - ( 2 * 10 - 2 * 7)
1 = 7 - 2 * 10 + 2 * 7
1 = -2 * 10 + 3 * 7

Somit ergibt sich das multiplikative Inverse d = 3

Der euklidischen Algorithmus funktioniert so ähnlich wie der Restwertalgorithmus. Die Zahl links vom gleich wird in eine Summe und einen Faktor zerlegt. Der Summand ist der Rest und der Faktor ist die Anzahl, wie oft hier im Beispiel die 7 in die 10 gepasst hat.

Der erweiterte euklidischen Algorithmus baut auf dem euklidischen Algorithmus auf. Die Zeile beim euklidischen Algorithmus, in der wir einen Rest von 1 erhalten haben, stellen wir nach 1 um und setzen jeweils den Rest der vorhergegangenen Ebene ein.

Caesar-Shiffre:

Die Idee die hinter der Ceasar-Shiffre steckt ist eine zyklische Verschiebung um den Schlüssel e.

Im folgenden Beispiel werde ich dieses Verschlüsselungsverfahren erläutern und ein Wort verschlüsseln, sowie entschlüsseln.

Nachricht: K L E O P A T R A
10 11 4 14 15 0 19 17 0

y = x + e mod 26

y = 13 | 14 | 7 | 17 | 18 | 3 | 22 | 20 | 3
N O H R S D W U D

Additives Inverse zu e = 3 ist d = 23

x = y + d mod 26

x = 10 | 11 | 4 | 14 | 15 | 0 | 19 | 17 | 0
K L E O P A T R A


PS: Fragen und Verbesserungsvorschläge bitte via PM an mich.
Rechtschreibfehler könnt ihr behalten ;)

MfG Impi