Der Satz von Euler

Veröffentlicht am 18. Oktober 2018 von juergen

Der Satz von Euler stellt eine Verallgemeinerung des „kleinen Satzes von Fermat“ auf beliebige Moduli $n \in \mathbb{N}$ dar.

Der Satz von Euler besagt folgendes:

Falls der $ggT(a,n)=1 \Longrightarrow a^{\varphi(n)} \equiv 1 \ mod \ n$

Beweis:
Es gilt: $ggT(a,n)=1$ ( $a,n$ sind teilerfremd).
1) man nehme zu $n$ teilerfremde Zahlen aus $\mathbb{Z}_n$ : $k_1,\ k_2, \ \cdot\cdot\cdot,\ k_{\varphi(n)}$
2) man multipliziere $k_1,\ \cdot\cdot\cdot, \ k_m$ mit $a$ und erhält: $ak_1, \ ak_2, \ \cdot\cdot\cdot, \ ak_{\varphi(n)} \Longrightarrow ggT(ak_i,n)=1$

Einschub Beispiel:
$n=9: \varphi(9)=6 \Longrightarrow 1,\ 2,\ 4, \ 5, \ 7, \ 8$
für $a=2$ (da 2 teilerfremd zu $n$ )

$\\ 2 \cdot 1 \ mod \ 9=\textbf{2}, \\ \ 2 \cdot 2 \ mod \ 9=\textbf{4},\\ \ 2 \cdot 4 \ mod \ 9=\textbf{8}, \\ \ 2 \cdot 5 \ mod \ 9=\textbf{1}, \\ \ 2 \cdot 7 \ mod \ 9=\textbf{5}, \\ \ 2 \cdot 8 \ mod \ 9=\textbf{7} \Longrightarrow es \ entsteht \ eine \ Permutation.$

Beweis (Fortsetzung):
3) Bilden des Produktes aller $k_i$ und aller $ak_i$ $\Longrightarrow k_1 \cdot k_2 \cdot k_3 \cdot\cdot\cdot k_{\varphi(n)} \equiv ak_1 \cdot ak_2 \cdot ak_3 \cdot\cdot\cdot ak_{\varphi(n)} \ mod \ n$
4) Nun kann abschließend durch $k_i$ geteilt werden, da alle $k_i$ teilerfremd zu $n$ sind.
$\Longrightarrow 1 \equiv a^{\varphi(n)} \ mod \ n \quad (q.e.d)$

Der Satz von Euler dient der Reduktion großer Exponenten $modulo \ n$ . Praktische Anwendung findet er u.a. in der Kryptographie beispielsweise beim RSA-Verschlüsselungsverfahren.

Der kleine und der große Satz von Fermat

Veröffentlicht am 16. Oktober 2018 von juergen

Antworten

Der kleine Satz von Fermat

Der kleine Satz von Fermat trifft folgende Aussage:
Wenn $p \in \mathbb{P}$ (also wenn $p$ eine Primzahl ist) und wenn $p \nmid a$ ( $p$ teilt nicht $a$ ) dann gilt für alle $a$ aus $\mathbb{Z}$ :

$a^{p-1} \equiv 1 \ mod \ p$

Beweis:
Seien $a,2a, \ \cdot\cdot\cdot,\ (p-1)a$ von $p-1$ verschiedene Zahlen. Dann kann gezeigt werden, dass es zu jedem $j \in \{1,\ \cdot\cdot\cdot,\ p-1 \}$ genau ein $k \in \{1, \ \cdot\cdot\cdot, \ p-1\}$ gibt, so dass

$j \cdot a \equiv k \ mod \ p$ (1)

vorliegt. Im Widerspruch zur Behauptung wird nun angenommen, dass $j \neq j'$ und $k \in \{1, \ \cdot\cdot\cdot, \ p-1\}$ vorgefunden werden kann, so dass

$j \cdot a \equiv k \equiv j' \cdot a \ mod \ p$ (2)

gilt. Da $p$ eine Primzahl und kein Teiler von $a$ ist, muss $ggT(a,p)=1$ sein. Auf Grund dessen, kann durch $a$ gekürzt werden und man erhält:

$j \equiv j' \ mod \ p$

Wegen $j,j' \in \{1, \ \cdot\cdot\cdot, \ p-1\}$ ist daher $j = j'$ im Widerspruch zu $j \neq j'$ . Die Behauptung (1) ist daher richtig.

Die jeweils zusammengehörenden Kongruenzen (1) für $j=1, \ 2, \cdot\cdot\cdot, \ (p-1)$ können nun mit $a$ erweitert werden und man erhält dann:

$1 \cdot 2 \cdot\cdot\cdot(p-1) \equiv a \cdot 2a \cdot\cdot\cdot (p-1)a \equiv a^{p-1}1 \cdot 2 \cdot\cdot\cdot (p-1) \ mod \ p$

Da $1 \cdot 2 \cdot\cdot\cdot (p-1)=(p-1)!$ und die Primzahl $p$ teilerfremd sind können diese Konkruenzen durch $(p-1)!$ dividiert werden und man erhält die obige Behauptung.

Der große Satz von Fermat

Der große Satz von Fermat wird hier nur der Vollständigkeit halber kurz vorgestellt, da wenn man vom „kleinen Satz von Fermat“ hört, man sich berechtigterweise auch die Frage stellt, ob es dann auch einen „großen Satz von Feramt“ gibt.

Der große Satz von Fermat besagt: Ist $n=\{n \in \mathbb{N} \ | \ n >2\}$ , so kann die $n-te \ Potenz$ jeder natürlichen Zahl ungleich null nicht in die Summe zweier $n-ter \ Potenzen$ natürlicher Zahlen ungleich null zerlegt werden.

Dies bedeutet formal ausgedrückt:

$a^n+b^n=c^n$

Obige Gleichung ist für positive ganze Zahlen $a, \ b, \ c, \ n$ unlösbar wenn $n$ größer als zwei ist.

Kongruenz (Zahlentheorie)

Veröffentlicht am 15. Oktober 2018 von juergen

Antworten

Laut Wikipedia sind zwei Zahlen $a$ und $b$ kongruent $modulo \ m$ , wenn sie bei der Division durch $m$ denselben Rest haben. Dies ist genau dann der Fall, wenn sie sich um ein ganzahliges Vielfaches von $m$ unterscheiden.
Stimmen die Reste nicht überein, so nennt man die Zahlen inkongruent $modulo \ m$ . Jede Kongruenz modulo einer ganzen Zahl ist eine Kongruenz auf dem Ring der ganzen Zahlen.

Verdeutlicht wird dies anhand folgender Beispiele:

$7 \equiv 19 \ mod \ 4$ ; da $7 \ mod \ 4=3$ und $19 \ mod \ 4=3$ ist.
$5 \equiv 27 \ mod \ 11$ ; da $5 \ mod \ 11 = 5$ und $27 \ mod \ 11=5$ ist.
$3 \not\equiv 23 \ mod \ 22$ ; da $3 \ mod \ 22 = 3$ und $23 \ mod \ 22 =1$ ist.

Ein einfaches Python-Programm zum bestimmen der Kongruenz zweier Zahlen $a$ und $b$ modulo $m$ für $a,b,m \in \mathbb{Z}$ kann wie folgt implementiert werden:

def isKongruent(a, b, m):
    restA = a % m
    restB = b % m
    if restA == restB:
        return True
    else:
        return False
    
if __name__ == '__main__':
    print("Sind a und b kongruent mod m?", isKongruent(7, 19, 4))

Obiges Programm liefert als Wahrheitswert True da $7 \equiv 19 \ mod \ 4$ ist.

Die Eulersche Phi-Funktion

Veröffentlicht am 11. Oktober 2018 von juergen

Antworten

Die Eulersche $\varphi$ -Funktion gibt für jede natürliche Zahl $n$ an, wie viele zu $n$ teilerfremde natürliche Zahlen es gibt, die nicht größer als $n$ sind.

Definition:

Sei $n \in \mathbb{N}$ :
Die Eulersche $\varphi$ -Funktion ist dann definiert durch:
$\varphi(n):=|\{1\leq x \leq n \ | \ ggT(x,n)=1\}|$ dabei bezeichnet $ggT(x,n)$ den größten gemeinsamen Teiler von $x,n$ .

Beispiele:

$\varphi(12)=4\Longrightarrow$ denn in der Menge $\{1 \cdot\cdot\cdot 12\}$ sind nur die Zahlen 1, 5, 7, 11 teilerfremd.
$\varphi(13)=12\Longrightarrow$ da 13 eine Primzahl ist, sind alle Zahlen die kleiner sind als 13 teilerfremd.

Es lassen sich nun folgende Aussagen treffen:

1) Für jede Primzahl $p \in \mathbb{N}$ gilt: $\varphi(p)=p-1$ .
2) Sei $p \in \mathbb{N}$ eine Primzahl und $k \in \mathbb{N}$ . Dann gilt: $\varphi(p^k)=p^k-p^{k-1}=p^k\cdot(1-\frac{1}{p})$

Beispiel zu 2):

$\varphi(12)=\varphi(2^2 \cdot 3^1) \\ =\qquad\qquad \ 2^2 \cdot (1-\frac{1}{2}) \cdot 3^1 \cdot (1-\frac{1}{3}) \\ =\qquad \qquad \ (2^2-2^{2-1})\cdot(3^1-3^{1-1}) \\ =\qquad\qquad \ 2 \cdot 2 \\ =\qquad\qquad \ 4$

In Python lässt sich die Berechnung von $\varphi(n)$ relativ einfach wie folgt implementieren:

def calcphi(phivonN):
    i = 1
    wertPhi = 0
    while i < phivonN:
        if testggT(i, phivonN) == 1:
            wertPhi += 1
        i += 1
    return wertPhi

def testggT(i, phivonN):
    while phivonN!=0:
        i ,phivonN = phivonN, i % phivonN
    return i

if __name__ == '__main__':
    phivonN = 12
    print("Phi(",phivonN,")", "= ", calcphi(phivonN))

Division mit Rest (modulo-Funktion)

Veröffentlicht am 11. Oktober 2018 von juergen

Antworten

Sowohl im Ring der ganzen Zahlen (ganze Zahlen können ohne Einschränkung addiert, subtrahiert und multipliziert werden) als auch im Polynomring über einem Körper kann stets die Division mit Rest (euklidischer Ring) durchgeführt werden.

Formaler Algorithmus:

Seien .

1) Berechne den ganzzahligen Quotienten  von  und .
2) Berechne den Rest .
3) Gebe  und  aus.

Dann gilt:  mit .

Beispiele:

$3 \ mod \ 11=3$
$-8 \ mod \ 6=-8- \lfloor \frac{-8}{6} \rfloor \cdot 6=-8-(-2) \cdot 6=-8+12=4$
$12 \ mod \ 5=2$

Primzahlen

Veröffentlicht am 9. Oktober 2018 von juergen

Antworten

Unter einer Primzahl versteht man eine von 1 verschiedene natürliche Zahl, die nur durch 1 und durch sich selbst teilbar ist.
Die Menge der Primzahlen wird in der Regel mit dem Symbol $\mathbb{P}$ bezeichnet. Mit $\mathbb{P}$ verknüpft ist die Folge $(p_n)_{n \in \mathbb{N}}$ der nach ihrer Größe geordneten Primzahlen, die man auch Primzahlfolge nennt.

Demanch gilt:

$\mathbb{P} \supset \mathbb{N} = \{p_n \ | \ n \ \in \mathbb{N} \}$

Da wir nun festgelegt haben, was eine Primzahl ist, stellt sich nun die Frage, wofür werden diese in der Kryptographie verwendet und warum haben diese einen so großen Stellenwert inne?
In der Kryptographie basieren viele Verschlüsselungsverfahren auf Primzahlen, so z.B. das RSA (Rivest-Shamir-Adleman)-Verfahren.

Beispiel einer verschlüsselten Übertragung anhand des RSA-Verfahrens:
Die Personen Alice und Bob möchten verschlüsselt kommunizieren. Zuerst möchte Bob Alice eine geheime Nachricht schicken. Um dies zu ermöglichen, trifft Alice folgende Vorbereitungen:

1) Alice wählt zufällig zwei Primzahlen  und . 
2) Sie berechnet  und . 
3) Dann wählt Sie  mit . 
4) Alice bestimmt  mit . 
5) Dann ist  der öffentliche und  der geheime Schlüssel. 
6) Die Werte  und  löscht Alice.

Bob möchte nun Alice die Nachricht $x \in \{0,...,N-1 \}$ schicken. Er geht nun wie folgt vor:

7) Bob berechnet  und schickt  an Alice. 
8) Alice berechnet .

Es stellen sich nun z.B folgende Fragen:

Wie findet man ausreichend große Primzahlen $p$ und $q$ ?
Was bedeutet die Funktion $\varphi(N) \ (Eulersche Phi-Funktion)$ ?
Wie wird die Rechenoperation $modulo$ (Division mit Rest) angewendet ?

Auf diese Fragen wird in Beiträgen in den Kategorien Zahlentheorie und Primzahltest noch näher eingegangen.

Modulare Exponentiation („schnelles Potenzieren“)

Veröffentlicht am 8. Oktober 2018 von juergen

Antworten

Die modulare Exponentiation spielt in der Kryptographie sowie zum ver- als auch zum entschlüsseln von Nachrichten eine wichtige Rolle. Beim RSA-Verfahren z.B. besteht die Chiffrierung in der Berechnung von $m^b \ mod \ n$ .

Verschiedene Möglichkeiten eine Potenzierung duchzuführen:

Eine naive Methode wäre es durch eine Reihe von Multiplikationen
$m^b \ mod \ n$ zu berechnen. Demnach wären $b-1$ Multiplikation notwendig.
Eine weitere Methode wäre das Wiederholte Quadrieren:
$m^{16} = ( ( ( a^2 ) ^2 ) ^2 ) ^2$
Ein effizienteres Potenzieren kann auch wie folgt durchgeführt werden:
$m^{26} = m^{16} \cdot m^8 \cdot m^2$
Ein gutes Rezept für ein schnelles Potenzieren ist für ein allgemeines $m^b \$ b ins Binärsystem zu überführen:
$b = b_0 \cdot 2^0 + b_1 \cdot 2^1 + ... + b_k \cdot 2^k \$
anschließend berechnet man wiederholt Quadrate von $m$ , dies erzeugt nacheinander: $m, m^2, (m^2)^2, ..., (m^2)^k \$ und multipliziert ein $(m^2)^j$ zum Endergebnis wenn $b_j = 1$ . Daraus ergibt sich eine höchste Anzahl an Multiplikationen von $2 \cdot \lceil log_2(b) \rceil$ .

Programmbeispiel der modularen Exponentiation

Es gilt z.Bsp.:
$m^{23}=m^{22} \cdot m$

daraus folgt für $m^{22}$ :
$m^{22}=(m^{11})^2$

Rekursiv kann die modularen Exponentiation wie folgt für $m^b$ mit $b \in \mathbb{N}_0$ beschrieben werden:

Eine rekursive Implementierung der obigen Rekursionsformeln mit $m=2, \ b=4, \ n=5$ in Python mit dem Rückgabewert als Ergebnis 1:

def modexp(m, b, n):
    if b == 0:
        return 1
    if b % 2==1:
        return modexp(m, b-1, n)*m % n
    else:
        return modexp(m, b//2, n)**2 % n
    
if __name__ == '__main__':
    print(modexp(2,4,5))

Eine iterative Implementierung von $m^b \ mod \ n$ in Python nach der „naiven Methode“ sieht wie folgt aus:

def modexpIt(m, b, n):
    bs=1
    while(b > 0):
        bs *= m
        b -= 1
    erg = bs % n
    return erg
    
if __name__ == '__main__':
    print(modexpIt(2,4,5))

Das obige Beispiel verdeutlicht nocheinmal, dass für die Berechnung von $m^b \ mod \ n$ b-1 Multiplikation bzw. b-1 Schleifendurchläufe notwendig sind.
Bezugnehmend auf das Laufzeitverhalten der Iterativen Implementierung zur Berechnung von $m^b \ mod \ n$ kann man somit sagen, dass diese $O(c)$ (für $c=b-1$ ) beträgt $\Longrightarrow$ lineares Laufzeitverhalten.

Binäres Potenzieren

Das binäre Potenzieren ist eine effizientere Methode für die Exponentation, als die zuvor beschriebenen Verfahren. Sie funktioniert wie folgt:

Für $a^b$ wobei $a,b \in \mathbb{Z}$ wird $b$ binär dargestellt. Für jede 1 wird nun die Operation quadrieren und multiplizieren (QM) und für jede 0 die Operation quadrieren (Q) durchgeführt. Wobei die führende 1 gestrichen werden kann, da die Binärdarstellung für $b>0$ immer mit einer 1 beginnt und damit auch die erste Anweisung mit QM, ergibt sich hierfür $1^2 \cdot a = 1$ .

Beispiel:

für $a=5$ und $b=13 \Longrightarrow 5^{13}$ .

$b_2 \ (dual) \ =1101$ die führende 1 wird nun gestrichen $\Longrightarrow$ 101. Nun werden für $a$ folgende Operationen durchgeführt:

QM $\longrightarrow$ Q $\longrightarrow$ QM

Für $a$ ergibt sich nun:

$a^2 \cdot a \longrightarrow$ QM
$(a^2 \cdot a)^2 \longrightarrow$ Q
$((a^2 \cdot a)^2)^2 \cdot a \longrightarrow$ QM

Kongret für $a=5$ erhält man:

$((5^2 \cdot 5)^2)^2 \cdot 5 = 1220703125$

In der Programmiersprache Python lässt sich das Ganze wie folgt beschreiben:

'''Umwandlung in binaer und Ergebnis als Liste zurueckliefern'''
def sammleBin(exponent):
    binListe = []
    tmpgerade = 0
    if exponent % 2 == 0:
        tmpgerade = exponent
        exponent = exponent + 1
    while exponent != 0:
        binListe.insert(0,exponent % 2)
        exponent = exponent // 2
    if tmpgerade != 0:
        binListe[len(binListe)-1] = 0
    '''erstes Element aus Liste entfernen'''
    del binListe[0]
    return binListe

'''Entsprechende Operationen durchfuehren (QM oder Q)'''
def binPotenz(basis, expo):
    binListe = sammleBin(expo).copy()
    wert = basis
    for i in range(0, len(binListe)):
        if(binListe[i] == 1):
            wert = basis * (wert**2)
        else:
            wert = wert**2
    return wert

if __name__ == '__main__':
    print("",binPotenz(5, 13))

Nähere Informationen über die Binäre Exponentiation findet man bei Wikipedia.

Kryptographie

Veröffentlicht am 2. Oktober 2018 von juergen

Antworten

Inhalte der Kryptographie

Verschlüsselung
digitale Unterschriften
Identifikationsprotokolle
Secret sharing
symmetrische (AES) / asymmetrische (RSA) Verschlüsselung
Stromchiffren
Schlüsselaustausch
Kryptoverfahren mit elliptischen Kurven

Die moderne Kryptographie beruht auf unterschiedlichen mathematischen Rechenverfahren. Im wesentlichen sind diese: die schnelle modulare Exponentiation $m^b \ mod \ n$ , der darauf aufbauende Primzahltest und der erweiterte euklidische Algorithmus (engl. expanded greatest common divisor EGCD).

Es gibt viele Gründe, sich aus sicherheitstechnischen Überlegungen mit Kryptographie zu beschäftigen. Die Kryptographie ist aber insbesondere auch ein interdisziplnäres Feld in der Mathematik, das sich Resultaten aus Computeralgebra, Algebra, Zahlentheorie, Komplexitätstheorie usw. bedient und so zeigt , wie sich verschiedene Zweige der Mathematik in aktuellen Technologien wiederfindet.

IT-Sicherheit

IT- und Systemsicherheit

Archiv für den Monat: Oktober 2018

Der Satz von Euler

Der kleine und der große Satz von Fermat

Der kleine Satz von Fermat

Der große Satz von Fermat

Kongruenz (Zahlentheorie)

Die Eulersche Phi-Funktion

Division mit Rest (modulo-Funktion)

Primzahlen

Modulare Exponentiation („schnelles Potenzieren“)

Programmbeispiel der modularen Exponentiation

Binäres Potenzieren

Kryptographie

Inhalte der Kryptographie