RSA Einführung, Einweg und Asymmetrie

RSA ist eine deutlich sichere Methode als Caesar und Vigenère um Nachrichten zu verschicken.

Sie beruht auf der Asymmetrie und der Einwegfunktion (der Falltürfunktion).


Einwegfunktion am Beispiel von RSA:

Da es sehr schwer ist eine sehr große Zahl, ursprünglich aus 2 sehr großen Primzahlen gebildet, in seine Primfaktoren zu zerlegen, ist die Funktion "Multipliziere zwei sehr große Primzahlen" eine Einwegfunktion. 


Asymmetrie am allgemeinem Beispiel:

Ich lege meinen Klartext in eine Kiste und mache ein Schloss (public key) drum, welches jeder sehen kann. Den Schlüssel (private key) dafür habe nur ich. Nun schicke ich die Kiste zum Empfänger, dieser tut sein Schloss (public key) um die Kiste drum, welches jeder sehen kann. Den Schlüssel (private key) dafür hat nur er. Dann schickt er mir die Kiste zurück und ich entferne mit meinem Schlüssel (private key) mein Schloss (public key). Dann schicke ich die Kiste zurück an den Empfänger. Der Kann dann mit seinem Schlüssel (private key) sein Schloss (public key) entfernen und die Nachricht lesen ohne das je ein Schlüssel übermittelt werden musste, was sehr unsicher ist.


Verschlüsselungsverfahren, die zwei verschiedene Schlüssel verwenden, einer zum Verschlüsseln und einer zum Entschlüsseln, sind asymmetrische Verschlüsselungsverfahren. Bei asymmetrischen Verfahren ist kein Schlüsselaustausch notwendig.



Halten wir fest:

Wählt Bob zwei (große!!) Primzahlen  und  und hält diese geheim, so kann er gefahrlos das Produkt  veröffentlichen. Niemand außer ihm wird an die Primfaktoren  und herankommen.



RSA ist knackbar, dauert jedoch nur sehr lange. 
Deswegen benutzen zum Beispiel schnelle Dienste wie mobile Datenübertragung nur einfache Schlüssel.
Sehr schwere Schlüssel werden, jedoch erst mit Rechnern die erst in einigen Jahren verfügbar sind, knackbar sein.



Quelle: http://www.matheprisma.uni-wuppertal.de/Module/RSA/, Seite 4/12

Vigenére knacken

Um die Vigenére-Verschlüsselung zu knacken sind 3 Schritte notwendig:

1. Im Geheimtext müssen gleiche Buchstabenfolgen gesucht werden, die sich wiederholen. Jede mehrmals vorkommende Buchstabenfolge wird notiert und der Abstand zur Gleichen ermittelt.
2. Die Länge des Schlüsselworts kann nur aus einem Teiler der Abstände bestehen.
3. Das Schlüsselwort kann mit Hilfe einer Tabelle ermittelt werden. Hier gibt es so viele Spalten, wie das Schlüsselwort lang ist und für jeden Buchstaben im Alphabet eine Zeile. Dann wird durch die Häufigkeitsanalyse ermittelt, wie die einzelnen Buchstaben des Schlüsselworts lauten.

Vigenére-Verschlüsselung

Die bekannteste Art der polyalphabetischen Chiffrierung ist die Vigenère-Verschlüsselung.

Zur Chiffrierung der Nachrichten benötigt man ein Schlüsselwort (nicht mehr nur einen Schlüsselbuchstaben wie bei Caesar und das Vigenère-Quadrat. Dabei kann das Schlüsselwort jede beliebige Buchstabenfolge sein.

Das Schlüsselwort wird so häufig wiederholt, wie der Klartext lang ist. Und dann wird mithilfe des Vigenère-Quadrats jeder Buchstabe für sich, wie bei Caesar, chiffriert.

Schlüsselwort
BOND
Schlüsselwort
BONDBONDBONDBONDBONDBO
Klartext
TREFFINDERGRUENENTANNE
Geheimtext
UFRIGWAGFFTUVSAHOHNQOS


Um die Vigenére-Verschlüsselung zu implementieren muss ersteinmal der Algorithmus von Caesar geändert werden:

1. Die Eingabe des Schlüssels ist nicht mehr ein char sondern ein String.
2. Beim casten des Schlüssels wird nun nicht mehr nur der Charakter Schlüssel sondern der jeweilige Schlüsselbuchstabe in den ASCII Code konvertiert.
3. Beim chiffrieren eines Textes muss ein Index für den Schlüssel mit der Länge des Schlüssels festgelegt werden. Er beginnt bei 0 und erhöht sich jeweils um 1 nach einem Schleifendurchlauf. Dabei muss modulo gerechnet werden mit der Länge des Schlüssels.

Beim dechiffrieren läuft das Prozedere genau andersrum.

Quelle: http://www.gat-blankenburg.de/pages/fach/info/vigen.htm

Die Häufigkeitsanalyse

Die Häufigkeitsanalyse ist eine Methode zur Entschlüsselung (Dechiffrierung) verschlüsselter Texte. Sie kann den Schlüssel einer geheimen Botschaft ermitteln, dadurch, dass jeder Buchstabe statistisch unterschiedlich häufig verwendet wird. Somit kann zu jedem verschlüsselten Buchstaben der statistisch passendste Buchstabe gesucht. Somit kann die Verschiebung des Alphabets durch den Schlüssel ermittelt werden. Am einfachsten geht dies mit den Buchstaben E und N. Die Häufigkeitsanalyse wird bei der Caesar und Vigenère-Verschlüsselung angewendet.

Hier findet Ihr die unterschiedlichen Häufigkeiten der Buchstaben im Deutsch und im Englischen um damit Eure geheimen Botschaften zu entschlüsseln:

Buchstabe	Deutsch	Englisch	Buchstabe	Deutsch	Englisch
a	6,5 %	8,2 %	n	9,8 %	6,7 %
b	1,9 %	1,5 %	o	2,5 %	7,5 %
c	3,0 %	2,8 %	p	0,8 %	1,9 %
d	5,1 %	4,3 %	q	0,02 %	0,1 %
e	17,4 %	12,7 %	r	7,0 %	6,0 %
f	1,7 %	2,2 %	s	7,3 %	6,3 %
g	3,0 %	2,0 %	t	6,2 %	9,1 %
h	4,8 %	6,1 %	u	4,4 %	2,8 %
i	7,6 %	7,0 %	v	0,7 %	1,0 %
j	0,3 %	0,2 %	w	1,9 %	2,4 %
k	1,2 %	0,8 %	x	0,03 %	0,2 %
l	3,4 %	4,0 %	y	0,04 %	2,0 %
m	2,5 %	2,4 %	z	1,1 %	0,1 %

Caesar Verschlüsselung

Die Caesar Verschlüsselung, oder auch unter dem Namen Caesar Chiffre bekannt, ist ein einfaches symmetrisches Verschlüsselungsverfahren aus Zeiten der Römer. Namensgebend ist demnach der römischen Feldherrn Gaius Julius Caesar.

Einige kennen diese Art der Verschlüsselung wahrscheinlich aus Kinderzeiten. Damals haben wir mit zwei aufeinander geklebten Scheiben Wörter verschlüsselt.

Konkret basiert die Caesar Chiffre auf einer monographischen und monoalphabetischen Substitution. Ausgangspunkt ist das Alphabet so wie wir es kennen. Nun wird jeder Buchstaben durch einen neuen Buchstaben ersetzt, nämlich der Buchstabe, der um drei Stellen versetzt ist. Aus einem "A" wird durch eine Verschiebung um drei Zeichen also der Buchstabe "D", ein "B" wird ein "E", das "C" ein "F" usw. Da das ganze zyklisch ist, wird das "X" durch ein "A" ersetzt, das "Y" durch ein "B" und das "Z" durch ein "C". Damit ergibt sich am Ende folgende "Umwandlungstabelle":

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

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

Möchte man nun also das Wort: "kryptowissen" verschlüsseln, muss man lediglich oben in der Tabelle nach dem Buchstaben schauen und diesen Buchstaben mit dem darunter ersetzen. So ist "kryptowissen" verschlüsselt gleich: "nubswrzlvvhq" 

Um die Caesar-Verschlüsselung in ein Programm zu integrieren sollte das Programm alle Buchstaben in Großbuchstaben konvertieren, alle Umlaute sollten vom User in Buchstaben konvertiert werden und auf alle Leerstellen sollte verzichtet werden.

Um das verschieben der Buchstaben immer zu gewährleisten wird mit dem modulo gearbeitet. Der modulo ist so etwas wie das Rechnen mit Rest in der Grundschule.

Die kurze algorithmische Darstellung sieht dann wie folgt aus:

Der Buchstabe b soll mit dem Schlüssel s chiffriert werden:

C(b, s) = ((int) b + (int) s ) mod 26

Der Buchstabe b soll mit dem Schlüssel s dechiffriert werden:

D(b, s) = ((int) b - (int) s ) mod 26

Die Caesar-Verschlüsselung leidet unter zwei schwären Mängeln:

1. Der Algorithmus ist nicht besonders kompliziert.
2. Es gibt nur eine geringe Zahl von Schlüsseln (25 Schlüssel)

Quellen: http://www.kryptowissen.de/caesar-chiffre.html