[Kryptographie] Modulare Arithmetik

technotroll(45)

Published in

#deutsch

Words

593

Reading

3 min

Listen

Play

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