Hallo Steem-Welt,
heute geht es mit der Kryptographie Reihe weiter.
Die Modulare Arithmetik ist zwar eine echt trockene Angelegenheit, jedoch essentiell wichtig für nahezu alle Krypto-Algorithmen.
Wer den ersten Teil der Reihe verpasst hat, kann meinen ersten Blogpost hier nachlesen.
Modulare Arithmetik
Modulo & Restklassen
Beispiel:
Gegeben sei eine endliche Menge Z7 = {0,1,2,3,4,5,6}
1+2 = 3
2*3 = 6
5+3 ≡ 1 mod 7
2-3 ≡ 6 mod 7
Definition Modulo
Seien a,r,m Elemente aus Z (Menge der Ganzzahlen) und m > 0
a ≡ r mod m
wenn (a-r) durch m teilbar ist (m|(a-r))
m nennt man Modulus und r Rest
Alternative Notation für a∈𝐙 ist
a = q*m+r f+r 0<=r<m
da m|(a-r) und m|q*m
Beispiel:
37 = 5 * 7 + 2 -> 37 ≡ 2 mod 7
Der Rest r ist mathematisch nicht eindeutig, zb 10 ≡ 3 mod 7, 10 ≡ 17 mod 7, 10 ≡ -4 mod 7
Definition Restklassen
Für die Menge Zm gibt es m Restklassen / Äquivalenzklassen r ∈ {0,...,m-1}
Eine Restklasse r besteht aus dem Rest r und der Addition mit allen Vielfachen des Modulos
r + q*m ∀q ∈ {...,-1,0,1,2,...}
Beispiel: Die Restklasse 3 von 𝚉7: {... -4, 3, 10,17,24, ...}
Alle Elemente dieser Restklassen r+q*m verhalten sich äquivalent
In allen Rechenoperationen dürfen die Zahlen in die Standardklassen umgerechnet werden
Zyklische endliche Ringe
Definition Zyklisch endlicher Ring
Ein ganzzahliger Ring ℤm besteht aus:
1. Der Menge ℤm = {0,1,2,...,m-1}
2. Zwei Operationen "+" und "*", und zwar für alle a,b ∈ℤm, so dass
- a+b ≡ c mod m
- a*b ≡ c mod m
Ein Ring hat folgende Eigenschaften:
- Geschlossen: Das Ergebnis einer Operation liegt immer im Ring
- Kommutativ: a+b=b+a & a*b=b*a ∀a,b ∈ℤm
- Assoziativ: a+(b+c)=(a+b)+c & a*(b*c)=(a*b)*c ∀a,b ∈ℤm
- Distributiv: a*(b+c) = a*b+a*c & (a+b)*c = ac+bc ∀a,b ∈ℤm
Bezüglich der Addition
- Neutrales Element: (=0) ∀a∈ℤm gilt, a+0≡a mod m
- Inverses Element: Für alle a∈ℤm gilt: es git ein Element -a, so dass gilt: a+(-a)≡0 mod m
Bezüglich der Multiplikation
- Neutrales Element: Für alle a∈ℤm gilt: a*1≡a mod m
- Inverses Element: Für Einige a∈ℤm gibt es ein Element a⁻¹, sodass gilt: a*a⁻¹ ≡1 mod m
Wenn ein inverses Element bezüglich der Multiplikation existiert, kann die Division
realisiert werden: b/a ≡ b*a⁻¹ mod m
Ein Element a∈ℤm hat eine multiplikative Inverse, wenn a teilerfremd / relativ-prim mit dem Modulo m ist.
Das heißt der ggt(a,m)=1
Anwendungsbeispiel
Definition: Affine Chiffre
Gegeben: x∈ℤm (klartext), y∈ℤm (Chiffretext),
- enck(x) : y ≡ a*x+b mod m
- deck(y) : x ≡ (y-b)*a⁻¹ mo1 = u·a + v·n.
Modulo n gerechnet ergibt sich 1 = u·a + v·n.
Modulo n gerechnet ergibt sich1 = u·a + v·n.
Modulo n gerechnet ergibt sichd m
Schlüssel k = (a,b) mit a,b∈ℤm und ggT(a,m)=1
Beispiel Affine Chiffre
Gegeben: ℤ(26) (alphabet), k=(a,b)=(3,12), x=14
Gesucht: y
y ≡ a*x+b mod m
≡ 3 * 14 + 12 mod 26
≡ 42 + 12 mod 26
≡ 16 + 12 mod 26
≡ 28 mod 26
≡ 2 mod 26
Entschlüsselung von y:
x ≡ (y-b) * a⁻¹ mod m
≡ (2-12) * 9 mod 26
≡ -10 * 9 mod 26
≡ 16 * 9 mod 26
≡ 144 mod 26
≡ 14 mod 26
Die Multiplikative Inverse von a=3 ist a⁻¹=9, da a*a⁻¹≡1 mod m
Teil 1: Einleitung & klassische Kryptographie
Ausblick
Im nächsten Post wird es um die symmetrische Kryptographie gehen.
Da wird dann auch wieder ein bisschen weniger Mathematik enthalten sein :D
Wie immer freue ich mich über Feedback und einen Upvote, wenn es euch gefallen hat. :)