IT-Security Teil 4: Restklassenwi.f4.htw-berlin.de/users/messer/LV/AI-ITSec-SS19/Folien/ISM-04/04... · ITSec – SS 2019 – Teil 4/Restklassen 4 Übersicht • Etwas Modulo-Arithmetik

05.04.19 1ITSec – SS 2019 – Teil 4/Restklassen

IT-Security

Teil 4: Restklassen

2ITSec – SS 2019 – Teil 4/Restklassen

Literatur I

[4-1] Beutelspacher, A.; Schwenk, J.; Wolfenstetter, K.-D.: Moderne Verfahren der Kryptographie. 4. Auflage, Vieweg 2001

[4-2] Schmeh, Klaus: Kryptografie. dpunkt, 6. Auflage, 2016http://darkblue.ch/programming/Kryptografie_Verfahren_Protokolle.pdf

[4-3] Hoffmann, Dirk: Einführung in die Informations- und Codierungstheorie. Springer, 2014

[4-4] Reiss, Kristina; Schmieder, Gerald: Basiswissen Zahlentheorie. Springer, 3. Auflage, 2014

[4-5] Buchmann, Johannes: Einführung in die Kryptographie. 6. Auflage, Springer, 2016

[4-6] Freiermuth, Karin; Hromkovic, Juraj; Keller, Lucia; Steffen, Björn: Einführung in die Kryptologie. Vieweg+Teubner, 2010


Literatur II - Links

[4-7] https://de.wikipedia.org/wiki/Erweiterter_euklidischer_Algorithmus

[4-8] https://www.arndt-bruenner.de/mathe/scripts/erweitertereuklid.htm

[4-9] https://av.tib.eu/media/19885 https://av.tib.eu/media/19886 https://av.tib.eu/media/19887

[4-10] http://www.inf.fh-flensburg.de/lang/krypto/algo/euklid.htm

[4-11] https://mathepedia.de/Erweiterter_euklidischer_Algorithmus.html


Übersicht

• Etwas Modulo-Arithmetik

• Restklassen

• Der euklidische Algorithmus

• Der erweiterte euklidische Algorithmus


Definitionen und ein Satz I

ℤ Menge der ganzen Zahlenℕ Menge der ganzen positiven Zahlen mit 0ℕ\{0} ℕ ohne 0

Satz

Für alle Zahlen a∊ℤ, m∊ℤ\{0} gibt es genau ein q∊ℤ und r∊ℕmit

a = q*m+r,

wobei 0 <= r < |m| ist.

q wird Quotient genannt (a/m),r wird Rest genannt und ist immer positiv zwischen 0 und |m|-1.


Definitionen und ein Satz II

Ganzzahlige Division: DIVq= a DIV m, wobei a, m, q aus ℤ, mit m<>0q ist die größte Ganzzahl < a/m bzw. kleinste Ganzzahl > a/m

Rest modulo: MODr= a MOD m, wobei a, m, q aus ℤ, mit m<>0, r aus ℕ,

Konvention (wird meist eingehalten):q (wie Quotient) möge der ganzzahlige Quotient seinr (wie Rest) möge der Modulo-Wert seinp (wie Primzahl) möge eine Primzahl seinm (wie Modul) möge die Zahl hinter mod/MOD seinn möge eine natürliche Zahl einschließlich 0 sein


Definitionen und ein Satz III

Aus Satz (verkürzt) a = b*q+r folgtmit der Definition von DIV und MOD damit:

Mit a, m aus ℤ, mit m<>0, r aus ℕ gilt:

a = (a DIV m)*m + a MOD m

odera MOD m = a - (a DIV m)*m

Das Modul m kann auch negativ sein:In a MOD m = a - (a DIV m)*m ist das Produkt positiv.Daraus folgt a MOD m = a MOD -m

In dieser Veranstaltung(und in der Kryptographie)wird nur mit positivenModulen gerechnet.

Das ist die Definition vomRest und die Bedingung

der Euklid'schen Division


Definitionen und ein Satz IV - Beispiele

22 MOD 7 = 1, denn 3*7=21-22 MOD 7 = 6, denn -4*7= -28

0 MOD 3 = 01 MOD 3 = 12 MOD 3 = 23 MOD 3 = 04 MOD 3 = 1

-1 MOD 3 = 2-2 MOD 3 = 1-3 MOD 3 = 0-4 MOD 3 = 2-5 MOD 3 = 1

Es gilta = (a DIV m)*m + a MOD ma DIV m = (a - a MOD m)/m

0 DIV 3 = 01 DIV 3 = 02 DIV 3 = 03 DIV 3 = 14 DIV 3 = 1


Bemerkung

• In den Programmiersprachen wird häufig nicht die hier angegebene mathematische Definition von MOD benutzt.

• Es kann sein, dass dort negative Reste berechnet werden.

Hier ein Beispiel aus PHP:

$a= 10 % 7; 10 mod 7 = 3

$a= -10 % 7 -10 mod 7 = -3

$a= 10 % -7; 10 mod -7 = 3

$a= -10 % -7; -10 mod -7 = -3

Das mod-Ergebnis wird wie mit +-Vorzeichen berechnet, und das Vorzeichen des Ergebnisses ist bei gleichen Vorzeichen der Operanden +, sonst -.


Addition und Subtraktion I

Wertebereich: ℕ für das Ergebnis

Addition Modulo m:Es wird wie gewöhnlich addiert, wobei anschließend solange msubtrahiert/addiert wird, bis das Ergebnis >= 0 und <m ist.

Subtraktion Modulo m:Es wird wie gewöhnlich subtrahiert, wobei anschließend solange maddiert/subtrahiert wird, bis das Ergebnis >= 0 und <m ist.

Beispiele:( 3 + 5) MOD 8 = 0

(-3 + 5) MOD 8 = 2( 3 – 6) MOD 9 = 6(-3 – 6) MOD 9 = 0


Teilbarkeit I

Definition

a∊ℤ\{0} teilt b∊ℤ, wenn es ein k∊ℤ gibt, so das b = k*a

Dies wird geschrieben als a|b.

Oder anders:

a teilt b = a|b, wenn b MOD a = 0 oder wenn b = k*a gilt also wenn b ein Vielfaches von a ist.


Teilbarkeit II

Sätze

[1] a|b ∧ a|c => a|(b+c) [2] a|b ∧ a|c => a|(b-c)[3] a|b ∧ a|c => a|(k

1*b+k

2*c) (Linearkombination)

Beweise folgen direkt aus der Definition:

[2]: a|b ∧ a|c => a|(b-c):

Mit b = k1*a falls a|b und analog c = k

2*a

a|(b-c)=> a|(k1*a-k

2*a) = a|a*(k

1-k

2)

analog für die umgekehrte Richtung

Analog für [1] und [3]


Kongruent modulo I

a MOD m = b MOD m, falls m | (a – b) mit a, b∊ℤ, m∊ℕ\{0}, dann heißt a zu b kongruent modulo m

d.h. mit m | (a – b) gibt es ein k mit k*m = a – bd.h. die Differenz muss ein Vielfaches von m seind.h. wenn k*m = a – b gilt, dann auch a = b + k*md.h. k*m ist dann in a = b + k*m die Differenzdaraus folgt unmittelbar mit k∊ℤ:

(a+k*m) MOD m = a MOD m

a ist kongruent zu b modulo m wird auch geschrieben: a ≡ b (mod m)

a ≡ b (mod m) bedeutet, dass die Reste bezüglich m gleich sind.

"(mod m)" bezieht sich auf die Gleichheit ≡ und ist keine modulo-Operationwie MOD.


Kongruent modulo II

{0, 1, 2, …, m-1} bei MOD m

Da a MOD m = b MOD m mit a ∊ℤ, b∊ℕ und b<m gilt,kann immer im Bereich:

gerechnet werden. Wenn ein Ergebnis einer Rechnung außerhalb liegt,kann es jederzeit durch Addieren oder Subtrahieren von k*min diesen Bereich gebracht werden.

Das führt zur Ersparnis bei großen Zahlen.

Leider muss kurzzeitig außerhalb des Bereichs [0,m-1] gerechnet werden,so dass für diese Fälle Speicherplatz reserviert sein muss.


Ein paar Sätze I

Allgemein gilt (a, k aus ℤ, m∊ℕ\{0}):

[S1] (a + k*m) ≡ a (mod m) (folgt aus Definition)[S2] k*m ≡ 0 (mod m) (folgt aus [S1])[S3] a MOD m = a, falls 0<= a < m

Addition (a, b aus ℤ, m∊ℕ\{0}):

[S4] a + b ≡ a MOD m + b MOD m (mod m)

Subtraktion (a, b aus ℤ, m∊ℕ\{0}):

[S5] a - b ≡ a MOD m - b MOD m (mod m)


Ein paar Sätze II – Beweis für Addition

Zu zeigen ist: (a + b) MOD m = (a MOD m + b MOD m) MOD mEs gilt:[a] z = m*(z DIV m) + z MOD mEs gilt:[b] (z + a*m) MOD m = z MOD m, da a*m MOD m = 0

[1] (a + b) MOD m[2] (a + b) MOD m = (m*a DIV m + a MOD m + m*b DIV m + b MOD m) MOD m // da [a][3] = (m*(a DIV m + b DIV m) + a MOD m + b MOD m) MOD m[4] = (0 + a MOD m + b MOD m) MOD m // da [b][5] (a + b) MOD m = (a MOD m + b MOD m) MOD m

Analog geht dies für die Subtraktion und Multiplikation.


Multiplikation

Multiplizieren wird auf mehrfaches Addieren zurückgeführt.Es wird wie gewöhnlich multipliziert und dann solange m abgezogenbzw. addiert bis das Ergebnis >= 0 und <m ist.

Beispiele:

4 * 5 MOD 7 = 6, denn 4*5-> 20-7-7 -> 63 * 4 MOD 5 = 2 4 * 4 MOD 5 = 1

Dazu gibt es noch folgende Sätze:

[S6] a*b ≡ b*a (mod m) (Kommutativgesetz)

[S7] (a*b)*c ≡ a*(b*c) (mod m) (Assoziativgesetz)

[S8] a*b ≡ a MOD m * b MOD m (mod m)


Division

Gibt es für ein a ein b mit a*b MOD m = 1?

b ist das inverse Element bzgl. * : a-1, also a*a-1 MOD m = 1.

Das inverse Element bzgl. * existiert nur dann, wenn a und m teilerfremd sind, also wenn sie außer 1 keinen gemeinsamen Teiler haben – also insbesondere, wenn m eine Primzahl ist, dann gibt esfür alle Werte ein inverses Element bzgl. der Multiplikation.

Beispiel:5-1 MOD 7 = 3, wobei 5 und 7 teilerfremd sindda5 * 5-1 MOD 7 = 5 * 3 MOD 7 = 1 (mod 7)

also

6 / 5 MOD 7 ⇒ 6 * 5-1 MOD 7 = 6 * 3 MOD 7 = 4


Bestimmung des inversen Elements (Division) I

Bei m=7 wie viel ist 3-1?{0,1,2,3,4,5,6}Rest muss 1 sein:

Bei m=6 wie viel ist 3-1?{0,1,2,3,4,5}Rest muss 1 sein:

3*0= 0 mod 7 = 0

3*1= 3 mod 7 = 3

3*2= 6 mod 7 = 6

3*3= 9 mod 7 = 2

3*4= 12 mod 7 = 5

3*5= 15 mod 7 = 1

3*6= 18 mod 7 = 4

3*7= 21 mod 7 = 0

3*0= 0 mod 6 = 0

3*1= 3 mod 6 = 3

3*2= 6 mod 6 = 0

3*3= 9 mod 6 = 3

3*4= 12 mod 6 = 0

3*5= 15 mod 6 = 3

3*6= 18 mod 6 = 0

Es gibt kein inverses Element zu 3.


Bestimmung des inversen Elements (Division) II

Beispiel 1: a=5, m=7

1*5 ≡ 5 (mod 7)2*5 ≡ 3 (mod 7)3*5 ≡ 1 (mod 7)4*5 ≡ 6 (mod 7)5*5 ≡ 4 (mod 7)6*5 ≡ 5 (mod 7)

Beispiel 2: a=3, m=6,

1*3 ≡ 3 (mod 6)2*3 ≡ 0 (mod 6)3*3 ≡ 3 (mod 6)4*3 ≡ 0 (mod 6)5*3 ≡ 3 (mod 6)

0 1 2 3 4 5 6

0 0 0 0 0 0 0 0

1 0 1 2 3 4 5 6

2 0 2 4 6 1 3 5

3 0 3 6 2 5 1 4

4 0 4 1 5 2 6 3

5 0 5 3 1 6 4 2

6 0 6 5 4 3 2 1

0 1 2 3 4 5

0 0 0 0 0 0 0

1 0 1 2 3 4 5

2 0 2 4 0 2 4

3 0 3 0 3 0 3

4 0 4 2 0 2 2

5 0 5 4 3 2 1Multiplikationstafeln


Potenzieren I

Potenzieren (Exponentiation) wird auf mehrfaches Multiplizierenzurückgeführt.

ab ≡ c (mod m)

Beispiel:

34 ≡ ? (mod 5) ⇒ 3*3*3*3 ≡ 1 (mod 5)


Potenzieren II – schneller Algorithmus

aq = an+m = an*..*am wobei q=n+..+m, n, m 2er-Potenzen sind

Die Potenz aq wird als Produkt von Faktoren an*am dargestellt,

die 2er-Potenzen bilden.

Dazu wird die Potenz q als Binärzahl umgerechnet und dieseals Polynom zur Basis 2 bestimmt.

Die einzelnen Faktoren dieses Polynoms sind dann die Werte für n..m.

Beispiel:

a23 = a10111B = a1+2+4+16 = a * a2 * a4 * a16

Statt 22 Multiplikationen: 7 Multiplikationen


Potenzieren III – schneller Algorithmus

func pow(nat a, n>=0) { nat res:= 1 nat t:= a while n>0 { if n mod 2 == 1 then res:= res*t fi t:= t*t n:= n DIV 2 } return res}

func powmod(nat a, n>=0, m) { nat res:= 1 nat t:= a while n>0 { if n mod 2 == 1 then res:= res*t mod m fi t:= t*t mod m n:= n DIV 2 } return res}

Berechnung von anBerechnung von an mod m


Potenzieren IV – schneller Algorithmus

• n-1 Quadrierungen, wobei n die Nummer der höchsten Stelle des Exponenten in Binärdarstellung mit 1 ist

• (Für jede 1 im Binärwert eine weitere Multiplikation) - 1

• Typische Zahl: 65537 = 10000000000000001B (2**16+1)

16 Quadrierungen (17. Stelle mit 1 beginnend gezählt)2 Einsen, d.h. eine weitere Multiplikation, also 17,statt 65536 Multiplikationen

Aufwand

Siehe dazu: http://de.wikipedia.org/wiki/Binäre_Exponentiation


Kleiner Satz von Fermat I

Der kleine Satz von Fermat:

(1)ap ≡ a (mod p), mit a>0 und p ist eine Primzahl

Wenn a und p teilerfremd sind (oder: wenn a kein Vielfaches von p ist),kann die folgende zweite Form benutzt werden:

(2) ap-1 ≡ 1 (mod p), mit a>0, ggT(a,p)=1 und p ist eine Primzahl

Um von (1) nach (2) zu kommen, muss (1) auf beiden Seiten durch adividiert werden, was aber nur geht, wenn das multiplikative Inverse existiert;das tut es nur dann, wenn ggT(a,p)=1 ist.

(2) bedeutet, dass p-1 auf den Exponenten beliebig oft addiert odersubtrahiert werden kann bzw. der Exponent mod p-1 genommen werden darf.


Kleiner Satz von Fermat II

ap-1 ≡ 1 (mod p), mit a>0, a<p und p ist eine Primzahl

Falls a=p, dann ist pp-1 mod p = 0 (linke Seite), was nicht 1 ist.ggT(a<p,p) mit p als Primzahl ist immer 1.

Beispiele für p=2, für die beiden Formen:

ap≡a(mod p) ap-1≡1(mod p)

a=1: 12 mod 2 = 1 mod 2 a=1: 11 mod 2 = 1 mod 2

a=2: 22 mod 2 = 2 mod 2 a=2: 21 mod 2 ≠ 1 mod 2, da ggT(2,2)=2


Kleiner Satz von Fermat IV - Anwendung

ap-1 ≡ a*ap-2 (mod p)

Dann gilt laut Fermat aber auch:

a*ap-2 ≡ 1 (mod p), ggT(a,p)=1 und p ist eine Primzahl

Das kann zur Berechnung des multiplikativen inversen Elementsbenutzt werden.

1 1*1*1*1*1= 1

2 2*2*2*2*2= 32 -> 4

3 3*3*3*3*3= 243 -> 5

4 4*4*4*4*4= 1024 -> 2

5 5*5*5*5*5= 3125 -> 3

6 6*6*6*6*6= 7776 -> 6

Beispiel mod 7

Für a=7, 14 etc. kommt immer 0 heraus.


Logarithmus, Wurzel

Diskreter Logarithmus (Modulo Logarithmus)

ax ≡ b (mod q)

Die Berechnung des diskreten Logarithmus ist sehr aufwändig, weshalbdies in der Kryptographie gerne ausgenutzt wird.

Modulo Wurzel

xa ≡ b (mod q)


Größter gemeinsamer Teiler (ggT) I

Eine Zahl c heißt größter gemeinsamer Teiler (ggT,gcd) zweierGanzzahlen a und b, wenn c beide Zahlen teilt und die größteist, die beide Zahlen teilt.

Die Idee besteht nun darin, die beiden Argumente schrittweise unterBeibehaltung des Ergebnisse so zu verkleinern, dass anhand einer derbeiden roten Formeln das Ergebnis bestimmt ist.

Satz:Für alle Zahlen a, b, k aus ℕ mit a>b gilt:Wenn k beide Zahlen a und b teilt, dann teilt auch k die Differenz a-b.

Es lässt sich beweisen: ggT(a,b) = ggT(a-b,b) mit a>=b

Oder anders formuliert: Ziehe immer die kleinere von der größerender beiden Zahlen ab bis sie gleich sind: das ist das Ergebnis,denn ggT(a,a) ist a.


Größter gemeinsamer Teiler (ggT) III

int Euklid(int a,b) { while a<>b { if a>b { a:= a-b;

} else { b:= b-a; } }return a;

}

int Euklid(int a,b) { while b>0 { if b<a { exchange(a,b); } b:= b-a; } return a;}

Diese Version entsprichteher dem Original:wechselseitiges "Wegnehmen"

ggT(a,b) = ggT(a,b-a) bzw. ggT(a,a-b)ggT(a,b) = ggT(b,a)ggT(a,a) = a


Berechnung des Modulo-Wertes

Wenn von der Zahl a≥b solange b abgezogen wird, bis a<b erreichtwird, ist der Wert von a MOD b berechnet worden.

int mod(int a≥0,b>0) { while a≥b { a:= a-b; }

return a;}

ggT(a,b) = ggT(a-b,b) mit a>=b..

ggT(a-b,b) = ggT(a-2*b,b) mit a-b>=b......

ggT(a,b) = ggT(a mod b,b) mit a>=b

Dies liegt an:a MOD m = a - (a DIV m)*m


Größter gemeinsamer Teiler (ggT) V

int EuklidMod(int a,b) { while a<>0 { if a>b {

a:= a MOD b; } else { exchange(a,b); }

}return b;

}

int EuklidMod(int a,b) { while b<>0 {

t:= a MOD b; a:= b; b:= t; }return a;

}

Da nach einem a:= a MOD b nie a>b wahr ist, kann gleich getauscht werden.

gcd(a,b) = gcd(a,b mod a)gcd(a,b) = gcd(b,a)ggT(a,a) = a


Erweiterter Euklidischer Algorithmus I

Seien a, b ∊ℕ\{0} so lässt sich der ggT(a,b) als Linearkombination vona und b darstellen: ggT(a,b)= u*a+v*bmit u,v∊ℤ.

Beispiel mit a=2 und b=7

0 = 7*2 – 2*7 1 = -3*2 + 1*7 2 = 8*2 - 2*7 3 = -9*2 + 3*7 4 = -5*2 + 2*7 5 =

Dazu gibt es folgenden Satz

u*a+v*b=n ist genau dann ganz-zahlig lösbar, wenn ggT(a,b)|n gilt.

Nebenbei: Wenn ggT(a,b)<>1 ist,dann lassen sich nicht alle Zahlenals Linearkombination darstellen.


Erweiterter Euklidischer Algorithmus II

• Linearkombination einer Zahl z ist die Summe zweier Produkte, deren Teilfaktoren vorgegeben sind:z = u*a + v*b, wobei a und b vorgeben sind.

• Es kann mehrere Linearkombinationen derselben Zahl geben (nicht eindeutig), z.B.0 = 7*2 – 2*7 = 14*2 – 4*7 mit a=2 und b=7

• Und auch gibt es Paare a und b, mit denen nicht alle ganzen Zahlen als Linearkombinationen darstellen kann, z.B. lassen sich keine ungeraden Zahlen als Summe zweier gerader Zahlen darstellen.


Berechnung des multiplikativen Inversen

a*a-1 ≡ 1 (mod m) mit ggT(a,m)=1 das sind die Voraussetzungen

ggT(a,b)= u*a+v*balso

ggT(a,m)= u*a+v*m ≡ 1 (mod m)

aa-1

0


Erweiterter Euklid'scher Algorithmus mit Subtraktion

func BigInt BigInt BigInt egcd(BigInt a>=0,b>=0) { BigInt au,av,bu,bv; BigInt a,b,t; au:= 1; av:= 0; // a = au*a + av*b bu:= 0; bv:= 1; // b = bu*a + bv*b while a <> b { if a>b { a:= a-b; au:= au-bu; // linear av:= av-bv; } else { b:= b-a; bu:= bu-au; // linear bv:= bv-av; } } return a,au,av;}

Bitte beachten Sie, dass die u- und v-Werte negativ sein können, dann muss dies durch Addition des Moduls korrigiert werden.

Grün sind die Bestandteiledes ursprünglichen Algorithmus.


Erweiterter Euklid'scher Algorithmus mit mod

func BigInt BigInt BigInt egcdMod(BigInt a>=0,b>=0) { BigInt au,av,bu,bv,tu,tv; BigInt a,b,t; au:= 1; av:= 0; // a = au*a + av*b bu:= 0; bv:= 1; // b = bu*a + bv*b while b <> 0 { q:= a div b; t:= a mod b; tu:= au-q*bu; // linear: t:= a mod b tv:= av-q*bv; a:= b; au,av:= bu,bv; // linear: a:= b b:= t; bu,bv:= tu,tv; // linear: b:= t } return a,au,av;}

Bitte beachten Sie, dass die u- bzw. v-Werte negativ sein können, dann muss dies durch Addition des Moduls korrigiert werden.

Grün sind die Bestandteiledes ursprünglichen Algorithmus.


Nach dieser Anstrengung etwas Entspannung....

Documents

IT-Security Teil 4: Restklassenwi.f4.htw-berlin.de/users/messer/LV/AI-ITSec-SS19/Folien/ISM-04/04... · ITSec – SS 2019 – Teil 4/Restklassen 4 Übersicht • Etwas Modulo-Arithmetik