Worksheet: Unterschied zwischen den Versionen

aus ZUM-Wiki, dem Wiki für Lehr- und Lerninhalte auf ZUM.de
Wechseln zu: Navigation, Suche
(→‎Vigenère-Verschlüsselung)
Zeile 70: Zeile 70:
 
<br />
 
<br />
 
Suche dir selbst einen Klartext und verschlüsslele ihn mit einem Wort deiner Wahl.<br /><br /><br /><br /><br />}}
 
Suche dir selbst einen Klartext und verschlüsslele ihn mit einem Wort deiner Wahl.<br /><br /><br /><br /><br />}}
 +
 +
== RSA ==
 +
 +
Problematisch bei den bisherigen Verfahren ist, dass es sich um symmetrische Verfahren handelt: Sender und Empfänger arbeiten mit demselben Schlüssel. Beide müssen sich also vorher über den Schlüssel verständigen - aber wie?
 +
 +
Dieses Problem beheben asymmetrische Verfahren: Der Sender verschlüsselt mit einem Schlüssel <math>k</math>, der Empfänger entschlüsselt mit einem Schlüssel <math>l</math>, und <math>l</math> ist aus <math>k</math> praktisch nicht herzuleiten. Der Empfänger teilt dann den Sendern den Schlüssel <math>k</math> mit, mit dem die Sender Nachrichten für den Empfänger verschlüsseln sollen. Der Empfänger behält <math>l</math> schön für sich: Damit kann nur er und sonst niemand die Botschaft entschlüsseln. Auf diesem Prinzip beruht RSA, ein Verschlüsselungsverfahren, das von Rivest, Shamir und Adleman entwickelt wurd.
 +
 +
=== Konstruktion der Schlüssel ===
 +
 +
'''Konstruktion des öffentlichen Schlüssels (public key):'''
 +
 +
# Bestimme zwei (sehr große) Primzahlen <math>p</math> und <math>q</math>
 +
# Bilde <math>N = p\cdot q</math>
 +
# Bestimme <math>\varphi(N)</math> mit <math>\varphi(N)=\varphi(p\cdot q)=\varphi(p)\cdot\varphi(q)=(p-1)\cdot (q-1)</math>
 +
# Wähle eine Zahl <math>1<e<\varphi(N)</math> mit <math>ggT(e,\varphi(N))=1</math>
 +
# Der öffentliche Schlüssel ist dann <math>(e,N)</math>
 +
 +
'''Konstruktion des privaten Schlüssels (private key):'''
 +
 +
# Bestimme das Inverse <math>d</math> zu <math>e</math> mod <math>\varphi(N)</math>, also <math>e\cdot d\equiv 1</math> mod <math>\varphi(N)</math>. Man macht dies am einfachsten mit dem erweiterten euklidischen Algorithmus, man berechnet also <math>e\cdot d + q\cdot\varphi(N) = 1</math>.
 +
# Der private Schlüssel ist dann <math>(d,N)</math>
 +
 +
Somit ist <math>(e,N)</math> der öffentliche und <math>(d,N)</math> der private Schlüssel. Den öffentlichen Schlüssel <math>(e,N)</math> gibt man anderen Personen, die Geheimbotschaften an einen schicken können sollen (man darf den z.B. ins Internet stellen). Den privaten Schlüssel <math>(d,N)</math> behält man tunlichst für sich und gibt ihn keinesfalls weiter - dieser dient dem Entschlüsseln der Geheimbotschaften. Die Zahle <math>p</math>, <math>q</math> und <math>\varphi(N)</math> sind Abfall. Diese sollten aber ebenso niemandem in die Hände fallen, also besser wegwerfen!
 +
 +
=== Ver- und Entschlüsselung ===
 +
 +
Der Sender verschlüsselt eine geheime Botschaft <math>T</math> (in diesem Fall eine Zahl) mit folgender Berechnung:
 +
 +
<math>G = T^e</math> mod <math>N</math>
 +
 +
<math>G</math> ist der Geheimtext und wird dem Empfänger übermittelt. Der Empfänger kann nun den Geheimtext <math>G</math> folgendermaßen entschlüsseln:
 +
 +
<math>T = G^d</math> mod <math>N</math>
 +
 +
denn:
 +
 +
Wir wissen, <math>e\cdot d \equiv 1</math> mod <math>\varphi(N)</math>, also <math>e\cdot d = 1 + r\cdot \varphi(N)</math> für ein <math>r\in\mathbb{Z}</math>
 +
 +
Außerdem wissen wir mit dem Satz von Euler, dass <math>a^{\varphi(m)}\equiv 1</math> mod <math>m</math>, falls <math>ggT(a,m)=1</math>.
 +
 +
Somit ergibt sich: <math>G^d\equiv (T^e)^d \equiv T^{e\cdot d} \equiv T^{1+r\cdot\varphi(N)}\equiv T\cdot T^{r\cdot\varphi(N)}\equiv T\cdot (T^{\varphi(N)})^r \equiv T\cdot 1^r\equiv T</math> mod <math>N</math>
 +
 +
Voraussetzung dafür ist, dass <math>ggT(T,N)=1</math>, und dies erreicht man einfach, in dem man die zu verschlüsselnden Zahlen nicht so groß wählt wie die Primzahlen, die man zur Konstruktion von <math>N</math> verwendet.
 +
 +
Das ganze an einem Beispiel:
 +
 +
# Wir wählen <math>p=7</math> und <math>q=11</math>
 +
# Somit ist <math>N=77</math> und <math>\varphi(N)=60</math>
 +
# Wir wählen <math>e=47</math> (es gilt nämlich <math>ggT(47,60)=1</math>)
 +
# Wir bestimmten <math>d</math> mit <math>47\cdot d\equiv 1</math> mod <math>60</math>, und der erweiterte euklidische Algorithmus liefert <math>d=23</math>
 +
# Der öffentliche Schlüssel ist nun <math>(47,77)</math>, der geheime ist <math>(23,77)</math>.
 +
 +
Wir verschlüsseln die Zahl <math>T=2</math>:
 +
 +
<math>G = 2^{47}\equiv 18</math> mod <math>77</math>
 +
 +
Und wir entschlüsseln:
 +
 +
<math>18^{23}\equiv ... \equiv 2</math> mod <math>77</math>
 +
 +
So ein Glück.
  
 
== Fragen ==
 
== Fragen ==

Version vom 25. Juni 2013, 13:47 Uhr

Druckversion

Die Cäsar Codierung

Bei der Cäsar-Verschlüsselung handelt es sich um eine monoalphabetische Substitution. Das bedeutet, dass bei der Veschlüsselung nur ein einziges festes Alphabet zur Verschlüsselung verwendet wird. Folgendes Beispiel soll das ganze verdeutlichen, bei dem zum Klartext (als Zahl) drei addiert werden um die Geheimbotschaft zu erhalten.

Der Klartext lautet: ICHLIEBEDICH
Geheimbotschaft:

Suche dir selbst einen Klartext und verschlüssele ihn.


Somit handelt es sich bei der Cäsar-Verschlüsselung um ein einfaches, aber sehr unsicheres Verschlüsselungsverfahren, das man mit folgenden Funktionen beschreiben kann:

  • Verschlüsselungsfunktion: E_k:\mathbb{Z}_{26}\rightarrow\mathbb{Z}_{26} mit
  • Entschlüsselugsfunktion: D_k:\mathbb{Z}_{26}\rightarrow\mathbb{Z}_{26} mit


Offensichtlich macht die Anwendung von D_k die vorherige Anwendung von E_k wieder rückgängig.
Das Verfahren ist allerdings total unsicher (warum?). Eine beliebige Permutation der Buchstaben anstelle einer einfachen Verschiebung macht es auch nicht besser (warum?).
Man kann sich das auch damit verdeutlichen, indem man sich die "Bastelanleitung" (Anleitung) einer "Verschlüsselungsscheibe" oder Chiffrierscheibe anschaut. Eine solche Scheibe kann man auch schon mit Kindern in der Grundschule anfertigen.


Vigenère-Verschlüsselung

Ein bisschen gewitzter als die Cäsar-Verschlüsselung ist die Vigenère-Verschlüsselung (es handelt sich hier um eine polyalphabetische Substition). Dabei wird das folgende Vigenère-Quadrat benutzt.

Vigenère-Quadrat
  Text  
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 

S
c
h
l
ü
s
s
e
l 		A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
B C D E F G H I J K L M N O P Q R S T U V W X Y Z A
C D E F G H I J K L M N O P Q R S T U V W X Y Z A B
D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
E F G H I J K L M N O P Q R S T U V W X Y Z A B C D
F G H I J K L M N O P Q R S T U V W X Y Z A B C D E
G H I J K L M N O P Q R S T U V W X Y Z A B C D E F
H I J K L M N O P Q R S T U V W X Y Z A B C D E F G
I J K L M N O P Q R S T U V W X Y Z A B C D E F G H
J K L M N O P Q R S T U V W X Y Z A B C D E F G H I
K L M N O P Q R S T U V W X Y Z A B C D E F G H I J
L M N O P Q R S T U V W X Y Z A B C D E F G H I J K
M N O P Q R S T U V W X Y Z A B C D E F G H I J K L
N O P Q R S T U V W X Y Z A B C D E F G H I J K L M
O P Q R S T U V W X Y Z A B C D E F G H I J K L M N
P Q R S T U V W X Y Z A B C D E F G H I J K L M N O
Q R S T U V W X Y Z A B C D E F G H I J K L M N O P
R S T U V W X Y Z A B C D E F G H I J K L M N O P Q
S T U V W X Y Z A B C D E F G H I J K L M N O P Q R
T U V W X Y Z A B C D E F G H I J K L M N O P Q R S
U V W X Y Z A B C D E F G H I J K L M N O P Q R S T
V W X Y Z A B C D E F G H I J K L M N O P Q R S T U
W X Y Z A B C D E F G H I J K L M N O P Q R S T U V
X Y Z A B C D E F G H I J K L M N O P Q R S T U V W
Y Z A B C D E F G H I J K L M N O P Q R S T U V W X
Z A B C D E F G H I J K L M N O P Q R S T U V W X Y


G
e
h
e
i
m
t
e
x
t

(entnommen aus der Wikipedia-Seite zur polyalphabetischen Substitution)

Nehmen wir mal den selben Klartext wie bei der Cäsar-Verschlüsselung. Mit dem Klartext und einem Geheimwort (im Folgenden RING) verschlüsseln wir nun unseren Klartext.
Geheimwort: Fehler beim Parsen(Lexikalischer Fehler): \ \ \ \ \ 

RINGRINGRING

Klartext: Fehler beim Parsen(Lexikalischer Fehler): \ \ \ \ \ \ \ \ \ \ 

ICHLIEBEDICH

Geiheimbotschaft:

Suche dir selbst einen Klartext und verschlüsslele ihn mit einem Wort deiner Wahl.




RSA

Problematisch bei den bisherigen Verfahren ist, dass es sich um symmetrische Verfahren handelt: Sender und Empfänger arbeiten mit demselben Schlüssel. Beide müssen sich also vorher über den Schlüssel verständigen - aber wie?

Dieses Problem beheben asymmetrische Verfahren: Der Sender verschlüsselt mit einem Schlüssel k, der Empfänger entschlüsselt mit einem Schlüssel l, und l ist aus k praktisch nicht herzuleiten. Der Empfänger teilt dann den Sendern den Schlüssel k mit, mit dem die Sender Nachrichten für den Empfänger verschlüsseln sollen. Der Empfänger behält l schön für sich: Damit kann nur er und sonst niemand die Botschaft entschlüsseln. Auf diesem Prinzip beruht RSA, ein Verschlüsselungsverfahren, das von Rivest, Shamir und Adleman entwickelt wurd.

Konstruktion der Schlüssel

Konstruktion des öffentlichen Schlüssels (public key):

  1. Bestimme zwei (sehr große) Primzahlen p und q
  2. Bilde N = p\cdot q
  3. Bestimme \varphi(N) mit \varphi(N)=\varphi(p\cdot q)=\varphi(p)\cdot\varphi(q)=(p-1)\cdot (q-1)
  4. Wähle eine Zahl 1<e<\varphi(N) mit ggT(e,\varphi(N))=1
  5. Der öffentliche Schlüssel ist dann (e,N)

Konstruktion des privaten Schlüssels (private key):

  1. Bestimme das Inverse d zu e mod \varphi(N), also e\cdot d\equiv 1 mod \varphi(N). Man macht dies am einfachsten mit dem erweiterten euklidischen Algorithmus, man berechnet also e\cdot d + q\cdot\varphi(N) = 1.
  2. Der private Schlüssel ist dann (d,N)

Somit ist (e,N) der öffentliche und (d,N) der private Schlüssel. Den öffentlichen Schlüssel (e,N) gibt man anderen Personen, die Geheimbotschaften an einen schicken können sollen (man darf den z.B. ins Internet stellen). Den privaten Schlüssel (d,N) behält man tunlichst für sich und gibt ihn keinesfalls weiter - dieser dient dem Entschlüsseln der Geheimbotschaften. Die Zahle p, q und \varphi(N) sind Abfall. Diese sollten aber ebenso niemandem in die Hände fallen, also besser wegwerfen!

Ver- und Entschlüsselung

Der Sender verschlüsselt eine geheime Botschaft T (in diesem Fall eine Zahl) mit folgender Berechnung:

G = T^e mod N

G ist der Geheimtext und wird dem Empfänger übermittelt. Der Empfänger kann nun den Geheimtext G folgendermaßen entschlüsseln:

T = G^d mod N

denn:

Wir wissen, e\cdot d \equiv 1 mod \varphi(N), also e\cdot d = 1 + r\cdot \varphi(N) für ein r\in\mathbb{Z}

Außerdem wissen wir mit dem Satz von Euler, dass a^{\varphi(m)}\equiv 1 mod m, falls ggT(a,m)=1.

Somit ergibt sich: G^d\equiv (T^e)^d \equiv T^{e\cdot d} \equiv T^{1+r\cdot\varphi(N)}\equiv T\cdot T^{r\cdot\varphi(N)}\equiv T\cdot (T^{\varphi(N)})^r \equiv T\cdot 1^r\equiv T mod N

Voraussetzung dafür ist, dass ggT(T,N)=1, und dies erreicht man einfach, in dem man die zu verschlüsselnden Zahlen nicht so groß wählt wie die Primzahlen, die man zur Konstruktion von N verwendet.

Das ganze an einem Beispiel:

  1. Wir wählen p=7 und q=11
  2. Somit ist N=77 und \varphi(N)=60
  3. Wir wählen e=47 (es gilt nämlich ggT(47,60)=1)
  4. Wir bestimmten d mit 47\cdot d\equiv 1 mod 60, und der erweiterte euklidische Algorithmus liefert d=23
  5. Der öffentliche Schlüssel ist nun (47,77), der geheime ist (23,77).

Wir verschlüsseln die Zahl T=2:

G = 2^{47}\equiv 18 mod 77

Und wir entschlüsseln:

18^{23}\equiv ... \equiv 2 mod 77

So ein Glück.

Fragen

Hast du noch Fragen? Notiere sie dir hier, damit du sie in deiner Lerngruppe, in der Übungsstunde oder in der nächsten Plenumssitzung klären kannst!











Von „https://wiki.zum.de/index.php?title=PH_Heidelberg/Bausteine/Verschlüsselung/Worksheet&oldid=285443“