von Armin Kast
Überall dort, wo Daten geheimgehalten werden sollen, benötigt man Verfahren,
mit denen diese Daten verschlüsselt bzw. wieder entschlüsselt werden können.
Ein Ver- bzw. Entschlüsseln bezeichnet man als "Crypt" / "Decrypt"
oder aber auch "Chiffrieren" / "Dechiffrieren". Sinn und
Zweck ist es schon immer gewesen, einen einfachen Algorithmus zu erarbeiten,
mit welchem ein einfaches Ver-. bzw. Entschlüsseln möglich ist.
Der Sender möchte dem Empfänger eine geheime Nachricht übermitteln. Dazu muß der Sender die Nachricht verschlüsseln und dann dem Empfänger in irgendeiner Form zukommen lassen. Dieser wiederum muß die Nachricht entschlüsseln, um den Inhalt lesen zu können. Eine denkbar einfache Methode besteht darin, daß sich beide Seiten auf einen Schlüssel festlegen, mit welchem die Daten verschlüsselt werden. Wird dieser Schlüssel aber über einen längeren Zeitraum beibehalten, so hat es ein Dritter, der die Daten ja abfangen könnte, recht leicht, eben diesen zu "knacken". Denn mit ebenso ausgeklügelten Algorithmen und Auszählvorgängen ist es möglich, einen solchen Schlüssel herauszufinden. XXX Eine solche Größe des Nachrichtengehaltes nach einer Statistik nennt man "Entropie" [CS]. Somit hängt die Entropie direkt von der Wahrscheinlichkeit eines Zeichens in dem übertragenen Datenblock ab. Im Deutschen findet man im allgemeinen die Buchstaben "ETAONI" am häufigsten. Die Entropie hängt auch immer vom Autor und Nachrichteninhalt ab. Jeder besitzt einen eigenen Stil, eine Nachricht niederzuschreiben. Der eine eher kurz und knapp, ein anderer vielleicht ausführlicher. Die Entropie wird durch das Zählen der einzelnen Buchstaben in einem Text bestimmt.
N = die Anzahl der verwendeten (unterschiedlichen) Zeichen
I = der Informationsgehalt eines Zeichens ( wird errechnet )
I = ld N bit/Zeichen { ld = Logarithmus Dualis }
¦ Gesetzmäßigkeiten ¦
¦ ln(x) ¦
¦ log (1/x) = - log (x) ; log (x) = --------- ¦
¦ a a a ln(a) ¦
¦ ¦
¦ ln(x) ¦
¦ --> ld(x) = -------- [ da die Basis 2 (Dual) ist ] ¦
¦ ln(2) ¦
+------------------------------------------------------+
I[y(i)] = ld ( 1 / p(i) ) bit
I[y(i)] = -ld[x(i)] = ld 1 - ld x(i)
n
H = - õ x(i) * ld[x(i)]
i=1
n = die Anzahl der verwendeten Zeichen eines Textes
p(i) = die Einzelwahrscheinlichkeit des Zeichens x(i)
Die Einzelwahrscheinlichkeit für ein Zeichen kann
zwischen 0 und 1 liegen : 0 ¾ X ¾ 1
Wir ermitteln per Zufall eine Reihe von 6 Buchstaben aus
den Buchstaben ABC und erhalten --> ABBCAC
Da A zweimal in den 6 Buchstaben auftaucht, ist
[A] = 2/6 = 1/3 = .333 = 33,3 % ( Wahrscheinlichkeit für A )
z.B.: Informationsgehalt für das Alphabet mit 26 Buchstaben
ln(26)
--> I = -------- = 4,700439 bit/Zeichen
ln(2)
Bei einer Verschlüsselung gibt es einige Punkte zu beachten:
Ein einfacher, aber nicht sicherer Verschlüsselungsmechanismus ist der "Caesar-Chiffre", der von Julius Caesar erfunden wurde. Dieser Substitutionschiffre funktioniert nach dem Verschiebeprinzip. Man verschiebt einfach die zwei Alphabetreihen gegeneinander. Caesars Offset (Offset = Abstand von 0) war 3.
ABCDEFGHIJKLMNOPQRSTUVWXYZ
ABCDEFGHIJKLMNOPQRSTUVWXYZ ( um drei nach links verschoben )
und dann wieder von rechts aufgefüllt..
ABCDEFGHIJKLMNOPQRSTUVWXYZ
DEFGHIJKLMNOPQRSTUVWXYZABC
--> A = D
--> B = E
--> C = F u.s.w.
ANGRIFF IM MORGENGRAUEN --> DQJULII LP PRUJHQJUDXHQ
ANGRIFF IM MORGENGRAUEN
D = 2 P = 2 ---> 10 Buchstaben verwendet
H = 2 Q = 3 õ = 21 (ohne Leerzeichen)
I = 2 R = 1
J = 3 U = 3 --> I = ln(10) / ln(2) = 3.321928 Bit/Zeichen
L = 2 X = 1
Wahrscheinlichkeiten (X[Zeichen]) der Zeichen : 0 ¾ X ¾ 1
Es ergeben sich folgende Wahrscheinlichkeiten :
[J] = 3 / 21 = 0.1428571 = 14.29 % ebenso für [Q] und [U]
[D] = 2 / 21 = 0.0952381 = 9.52 % ebenso für [H]; [L]; [I] und [P]
[R] = 1 / 21 = 0.0476190 = 4.76 % ebenso für [X]
n
H = - õ x(i) * ld[x(i)] |
i=1 | mit n = 10
H = -( 3 * -0.40105 + 4 * -0.32308 + 2 * -0.20916 ) = 2.91379
Die Entropie dieser Textzeile liegt also bei 2.91379 BIT.
Da im Deutschen die Buchstaben "ETAONI" am häufigsten auftreten, werden wir zuerst versuchen, J durch E und Q durch E zu ersetzen um so den Code zu "knacken". Da es sich hier nur um ein paar Worte handelt, bei denen die Entropie schwerer zu erkennen ist, brauchen wir schon ein wenig Zeit, um diesen Code zu "knacken", obwohl es bei dieser Art nur 26 Möglichkeiten der Verschlüsselung gibt!
Häufigkeiten der Buchstaben der deutschen Sprache in % : [AB]
|
Buch |
% |
Buch |
% |
Buch |
% |
Buch |
% |
|
A |
6,51 |
h |
4,76 |
O |
2,51 |
v |
0,76 |
|
B |
1,89 |
i |
7,55 |
p |
0,79 |
w |
1,89 |
|
C |
3,06 |
j |
0,27 |
q |
0,02 |
x |
0,03 |
|
D |
5,08 |
k |
1,21 |
r |
7,00 |
y |
0,04 |
|
E |
17,4 |
l |
3,44 |
s |
7,27 |
z |
1,13 |
|
F |
1,66 |
m |
2,53 |
t |
6,15 |
|
|
|
G |
3,01 |
n |
9,78 |
u |
4,35 |
Häufigkeiten der Bigramme der deutschen Sprache in % : [AB]
|
Bi |
% |
Bi |
% |
|
En |
3,88 |
te |
2,26 |
|
Er |
3,75 |
de |
2,00 |
|
Ch |
2,75 |
nd |
1,99 |
|
Ei |
1,88 |
es |
1,52 |
|
In |
1,67 |
ie |
1,79 |
( Bei Kombinationen wie z.B.: ea , et liegen die Anteile unter 0,50 % )
Nun man kann auch das Alphabet durcheinanderwürfeln und sich ein Wort ausdenken, in dem jeder Buchstabe nur einmal vorkommt wie z.B. "PIROSCHKA". Die restlichen Buchstaben des Alphabets schreibt man nun in umgekehrter Reihenfolge hinter das "Schlüsselwort".
ABCDEFGHIJKLMNOPQRSTUVWXYZ --> ANGRIFF IM MORGENGRAUEN
PIROSCHKAZYXWVUTQNMLJGFEDB PVHNACC AW WUNHSVHNPJSV
+--------
¦
+- unser Schlüsselwort
Mit solchen Methoden wird die Entschlüsselung für einen "Kryptoanalytiker" schon recht schwierig.
Dem zuvor behandelten "monoalphabetischen Chiffre" steht der "polyalphabetische Chiffre" entgegen, der, wie der Name schon sagt, mehrere (auch gleiche) Chiffrealphabete zum Einsatz bringt. Dieses Verfahren bezeichnet man auch als "Vigeneré-Chiffre", da es von diesem französischen Diplomaten Mitte des 16. Jahrhunderts entwickelt wurde. Das Vigenére-Quadrat ist folgendermaßen aufgebaut [AB] :
00000000011111111112222222
12345678901234567890123456
00 = abcdefghijklmnopqrstuvwxyz
-------------------------------
01 = ABCDEFGHIJKLMNOPQRSTUVWXYZ
02 = BCDEFGHIJKLMNOPQRSTUVWXYZA
03 = CDEFGHIJKLMNOPQRSTUVWXYZAB
04 = DEFGHIJKLMNOPQRSTUVWXYZABC
05 = EFGHIJKLMNOPQRSTUVWXYZABCD
06 = FGHIJKLMNOPQRSTUVWXYZABCDE
07 = GHIJKLMNOPQRSTUVWXYZABCDEF
08 = HIJKLMNOPQRSTUVWXYZABCDEFG
09 = IJKLMNOPQRSTUVWXYZABCDEFGH
10 = JKLMNOPQRSTUVWXYZABCDEFGHI
11 = KLMNOPQRSTUVWXYZABCDEFGHIJ
12 = LMNOPQRSTUVWXYZABCDEFGHIJK
13 = MNOPQRSTUVWXYZABCDEFGHIJKL
14 = NOPQRSTUVWXYZABCDEFGHIJKLM
15 = OPQRSTUVWXYZABCDEFGHIJKLMN
16 = PQRSTUVWXYZABCDEFGHIJKLMNO
17 = QRSTUVWXYZABCDEFGHIJKLMNOP
18 = RSTUVWXYZABCDEFGHIJKLMNOPQ
19 = STUVWXYZABCDEFGHIJKLMNOPQR
20 = TUVWXYZABCDEFGHIJKLMNOPQRS
21 = UVWXYZABCDEFGHIJKLMNOPQRST
22 = VWXYZABCDEFGHIJKLMNOPQRSTU
23 = WXYZABCDEFGHIJKLMNOPQRSTUV
24 = XYZABCDEFGHIJKLMNOPQRSTUVW
25 = YZABCDEFGHIJKLMNOPQRSTUVWX
26 = ZABCDEFGHIJKLMNOPQRSTUVWXY
Die Anwendung dieses Chiffre ist relativ einfach. Das über dem Klartext stehende Schlüsselwort entscheidet darüber, welche Zeile aus dem Quadrat genommen werden soll.
In dieser Variante wird das Leerzeichen nicht verschlüsselt, was man im Normalfall aber tun sollte, um Wortgruppen zu verbergen. Dies ist kein Problem, wenn man einfach das Leerzeichen dem Alphabet voranstellt:
01 = _ABCDEFGHIJKLMNOPQRSTUVWXYZ
02 = ABCDEFGHIJKLMNOPQRSTUVWXYZ_
03 = BCDEFGHIJKLMNOPQRSTUVWXYZ_A u.s.w.
Hierzu nun ein kleines Beispiel : Wir wählen als Schlüssel das Wort "DFPUG" und schreiben dieses so oft hintereinander bis die gleiche Anzahl Zeichen des Klartextes erreicht ist.
Schlüssel : DFPUGDFPUGDFPUGDFPUGDFP
Klartext : Angriff im Morgengrauen
Geheim : Dsvloik cs Rdlmhsvlgxjc
Schritt 1: Schlüssel = D , Klartext = A
Schritt 2: Der Schlüssel definiert die Zeile --> 04 wegen (D)
Der Klartext (A) wird in der Zeile 00 gesucht. Ziehen wir nun in Gedanken eine horizontale Linie durch 04 (D) und eine vertikale Linie von A nach unten, so schneiden sich die Linien im Punkt (D) --> dies ist der erste Geheimbuchstabe
00 = ¦bcdefghijklmnopqrstuvwxyz
-----¦-------------------------
01 = ¦BCDEFGHIJKLMNOPQRSTUVWXYZ
02 = ¦CDEFGHIJKLMNOPQRSTUVWXYZA
03 = ¦DEFGHIJKLMNOPQRSTUVWXYZAB
--------DEFGHIJKLMNOPQRSTUVWXYZABC
für den zweiten Buchstaben : Klartext = n , Schlüssel = F
00 = abcdefghijklmnopqrstuvwxyz
----------¦--------------------
01 = ABCDE¦GHIJKLMNOPQRSTUVWXYZ
02 = BCDEF¦HIJKLMNOPQRSTUVWXYZA
03 = CDEFG¦IJKLMNOPQRSTUVWXYZAB
04 = DEFGH¦JKLMNOPQRSTUVWXYZABC
05 = EFGHI¦KLMNOPQRSTUVWXYZABCD
06 = FGHIJ¦LMNOPQRSTUVWXYZABCDE
07 = GHIJK¦MNOPQRSTUVWXYZABCDEF
08 = HIJKL¦NOPQRSTUVWXYZABCDEFG
09 = IJKLM¦OPQRSTUVWXYZABCDEFGH
10 = JKLMN¦PQRSTUVWXYZABCDEFGHI
11 = KLMNO¦QRSTUVWXYZABCDEFGHIJ
12 = LMNOP¦RSTUVWXYZABCDEFGHIJK
13 = MNOPQ¦STUVWXYZABCDEFGHIJKL
14 -------STUVWXYZABCDEFGHIJKLM --> Geheimzeichen = s
15 = OPQRSTUVWXYZABCDEFGHIJKLMN
Bei solchen Verfahrensweisen wird es schon sehr schwer, den verschlüsselten Text zu "knacken".
In einer XOR-Verknüpfung steht im Gegensatz zur OR-Verknüpfung jedesmal eine 1, wenn beide zu vergleichenden Bits ungleich sind, und eine 0, wenn beide Bits gleich sind. In einigen literarischen Werken findet man auch diese Art der Verschlüsselung unter der Bezeichnung "Vigeneré-Verfahren", wobei hier die gesamte ASCII-Palette ( 0...255 ) als "Alphabet" dient.
Í------À Í-------À
¦ OR ¦ Í-----------À ¦ XOR ¦ Í-----------À
Ë------¢ ¦ / ¦ 1 ¦ 0 ¦ Ë-------¢ ¦ / ¦ 1 ¦ 0 ¦
¦---Ï---Ï---¦ ¦---Ï---Ï---¦
¦ 1 ¦ 1 ¦ 0 ¦ ¦ 1 ¦ 0 ¦ 1 ¦
Ã---+---+---Â Ã---+---+---Â
¦ 0 ¦ 0 ¦ 0 ¦ ¦ 0 ¦ 1 ¦ 0 ¦
Ë-----------¢ Ë-----------¢
Beispiel 1.)
Verschlüsselung von Entschlüsselung von
-------------------- ---------------------
A = Klartext E = Geheimzeichen
D = Schlüssel D = Schlüssel
D = 01000100 D = 01000100
A = 01000001 E = 00000101
----------------- XOR ---------------- XOR
E = 00000101 A = 01000001
Beispiel 2.)
Verschlüsselung von Entschlüsselung von
-------------------- ---------------------
n = Klartext E = Geheimzeichen
F = Schlüssel F = Schlüssel
n = 01101110 ( = 00101000
F = 01000110 F = 01000110
----------------- XOR ---------------- XOR
( = 00101000 n = 01101110
Das Verfahren an sich wurde 1976 durch Whitfield Diffie und Martin Hellman in ihrer Arbeit "New Directions in Cryptography" vorgeschlagen. Da beide aber nicht über Methoden verfügten ( zu dieser Zeit zumindest ), welche alle (nachfolgende) gestellten Bedingungen [FB] [CS] :
[ allgemein Definition ]
---------------------------------------------------------------
- Jedermannsschlüssel = P ( P = Public Key )
- Geheimschlüssel = S ( S = Secret Key )
- Botschaft = M ( M = Message )
- verschlüsselte Botschaft ( C = Cipher )
C = P(M)
[ Bedingungen ]
---------------------------------------------------------------
(i) S( P (M) ) = M für jede Botschaft M
(ii) Alle Paare ( S , P ) sind verschieden
(iii) Die Ableitung von S aus P ist ebenso schwer wie das Entschlüsseln von M ohne Kenntnis des Schlüssel S
(iv) Sowohl S als auch P lassen sich leicht berechnen.
erfüllten, konnten sie keine Methode zur Chiffrierung erstellen. Erst 1977 bemühten sich Ronald Rivest, Adi Shamir und Leonard Adleman ( R S A ), dieses Problem anzugehen und mit einer genialen Lösung zum Abschluß zu bringen, indem sie einfach ein Stück klassischer Zahlentheorie (Satz von Euler) nutzten. Der RSA-Algorithmus basiert direkt auf der Anwendung des Satzes von Euler (1707-1783).
Bei dieser Chiffriermethode ergibt sich ein Mehr an Sicherheit durch nachfolgende Vorgehensweise:
Bei einer Übermittlung geheimer Informationen, bei welchen mit verschiedenen Schlüsseln gearbeitet wird, muß der Empfänger einer Botschaft auch immer Besitz des aktuell gültigen Schlüssels sein. D.h. der Schlüssel müßte zwangsläufig auch zum Empfänger transportiert werden. Gelangt ein solcher Schlüssel in die falschen Hände, so könnte derjenige die Botschaft(en) ohne weiters entschlüsseln/dechiffrieren. Dies kann man durch das sogenannte PUBLIC KEY-VERFAHREN verhindern, denn bei dieser Methode sind alle Schlüssel, welche zum Verschlüsseln einer Nachricht verwandt wurden, öffentlich, d.h. selbst mit Kenntnis des Chiffrierverfahrens und der Chiffrierschlüssel kann der Text nicht entschlüsselt werden. Bei diesem Verfahren arbeitet man mit drei verschiedenen Schlüsseln.
Schritt 1 : Ermitteln der Schlüssel - Alle verwendeten Schlüssel werden vom EMPFÄNGER nach einem bestimmten Verfahren ermittelt.
Schritt 2 : Chiffrieren der Nachricht - Die öffentlichen Schlüssel n und e werden an den ABSENDER der Nachricht übermittelt. Dieser verschlüsselt dann nach einem ebenfalls öffentlichen Verfahren mit den ihm übermittelten Schlüsseln n und e .
Schritt 3 : Dechiffrieren der Nachricht - Der EMPFÄNGER entschlüsselt mit dem gleichen Verfahren und den Schlüsseln n und d .
Der Vorteil dieses Verfahrens ist, daß der Dechiffrierschlüssel nicht aus der Hand gegeben wird ( keinerlei Transporte zum Empfänger bei geändertem Schlüssel ). Eine Dechiffrierung ist auch bei Kenntnis der Public Keys ( öffentlicher Schlüssel ) und des angewandten Verfahrens nicht möglich. ( Achtung: Dies gilt ab einer Größenordnung für n >= 10^200 !! ) .
Wie konnten Rivest, Shamir und Adleman nun eine Methode zur Verschlüsselung entwickeln ? Eine recht einfache Funktion, die PHI-Funktion, brachte den Durchbruch in der Entwicklung des RSA-Verfahrens:
Die PHI-Funktion beschreibt die Anzahl der natürlichen Zahlen, kleiner als eine festgelegte Zahl n, welche keinen gemeinsamen Teiler außer 1 und der Zahl selbst haben.
Beispiel : Die Zahlen von 1 bis 12 --> 1 2 3 4 5 6 7 8 9 10 11 12
12 ist teilbar durch 1,2,3,4,6,12 und teilerfremd zu 5,7,8,9,10,11
--> Phi(12) = 6 ( gewertet wird die Anzahl der Zahlen, durch
die n NICHT teilbar ist. )
Anders verhält sich dies bei Primzahlen.
Die Zahlen von 1 bis 13 --> 1 2 3 4 5 6 7 8 9 10 11 12 13
13 ist nur teilbar durch 1 und 13 (also Prim) .
--> Phi(13) = 12
Hieraus wurden folgende Erkenntnisse gezogen:
a) Ist n eine Primzahl, so gilt : Phi(n) = n - 1
b) Ist n ein Produkt aus zwei Primzahlen so gilt :
Phi(p*q) = (p-1) * (q-1)
Euler fand heraus, daß, wenn man zwei zueinander teilerfremde Zahlen n und m wählt, zwischen diesen folgender Zusammenhang besteht:
Phi(n)
m MOD n = 1 ; mit b) ergibt sich daraus
Phi((p-1)*(q-1))
m MOD p*q = 1
e
generell : Verschlüsseln mit m MOD n
d
Entschlüsseln mit m MOD n
( m = Nachricht , e = ENCRYPT-Schlüssel , d = DECRYPT-Schlüssel
n = p*q )
Die beiden Zahlen d und e stehen als "multiplikatives Invers" zueinander. D.h. ist d = 7 und e = 1/7, so ist d * e = 1 und ( e*d ) MOD n = 1 erfüllt die Bedingung! So ist es möglich, die mit e verschlüsselte Nachricht mit d wieder zu entschlüsseln. Wie wir die beiden Schlüssel e und d ermitteln, werden wir etwas später erfahren.
Anmerkungen: In einigen Literaturstellen ( z.B. [DG] ) findet man des öfteren folgende Schreibweise :
e * d 1 mod Phi(n)
Das steht hier für "kongruent modulo p" --> (mod p)
und ist hier nicht mit einer Gleichsetzung zu verwechseln !
z.B.: 13 3 ( mod 10 ) --> 13 mod 10 = 3
D.h. ( e * d ) mod Phi(n) = 1 entspricht e * d 1 mod Phi(n)
1. Ermitteln der Schlüssel für das PUBLIC-KEY-Verfahren :
Suchen Sie zwei verschieden Primzahlen p und q und errechnen Sie aus diesen den ersten Schlüssel n = p * q ( Als Hilfestellung gibt es auf DisketteXXX die Datei PRIMZAHL.EN, in welcher alle Primzahlen < 1000 aufgeführt sind )
Legen Sie den geheimen Schlüssel d fest , wobei gelten muß : d > p und d > q ; d muß außerdem ebenfalls eine Primzahl sein.
Als nächstes bestimmen wir den öffentlichen Schlüssel e , für den die Bedingung
e * d MOD ( p - 1 ) * ( q - 1) = 1 gelten muß.
Man bezeichnet das Produkt aus ( p - 1 ) * ( q - 1 ) auch als Phi(n)
[ Þ = phi ]
2. Das Chiffrieren einer Botschaft
Eine zu verschlüsselnde Nachricht muß zunächst mit einer Zahl x codiert werden, wobei gelten muß : 0 ¾ x ¾ n - 1
( x ist in unserem Fall der ASCII-Code der einzelnen Buchstaben oder aber eineXXX gewählteXXX Codierungstabelle ).
Bei der Wahl der Codierung und der beiden zu wählenden Primzahlen p und q müssen die o.a. Bedingungen berücksichtigt werden. Sodann kann die Nachricht x verschlüsselt werden, indem man x^e MOD n = y berechnet. y ist dann unsere verschlüsselte Nachricht für welche ebenfalls gelten muß : 0 ¾ y ¾ n - 1
3. Das Dechiffrieren einer Nachricht
Mit nachfolgender Berechnungsformel wird dann unsere Nachricht wieder dechiffriert.
y^d MOD n = x ( x = entschlüsselte Nachricht )
Ein Beispiel :
Wir wählen als Primzahlen für : p = 7
q = 11
daraus folgt n = 7 * 11 = 77
da d > p und d > q sein muß, wählen wir d = 47
nun gilt es e * d MOD ( p - 1 ) * (q - 1) = 1 zu ermitteln
da d, p und q bekannt sind, gilt : e * 47 MOD ( 7 - 1 ) * ( 11 - 1) = 1
Mittels des Algorithmus nach BERLEKAMP (der auf der Idee des Euklidschen Algorithmus basiert - Bestimmung des größten gemeinsamen Teilers - ) ist es möglich, e zu ermitteln, so daß die Bedingung e * d MOD phi(n) = 1 erfüllt wird. ( Siehe Programmcode BERLE.C )XXX
Struktogramm für den Berlekamp-Algorithmus:
Lese Parameter ein <-- Gewünschtes d (Untergrenze) sowie Phi(n)
DO WHILE Schlüssel e und d noch nicht gefunden
IF d eine Primzahl THEN ; Primzahlentest durchführen
Intialisiere r,p,q ; Arbeitsvariablen r,p,q
DO WHILE r <> 0
Berechne c,r
IF r <> 0 THEN Berechne q,q FI
OD
e <-- p
IF e,d noch nicht in Ordnung THEN d <-- d + 2 FI
ELSE
Fehlermeldung --> d ist keine Primzahl
Programm verlassen
FI
OD
IF Berechnung nicht möglich THEN Gib Fehler aus FI
Mittels des Berlekampalgorithmus wird mit einem gewählten d = 47 der zweite Schlüssel e bestimmt.
--> e = 23 , d = 47 --> 23 * 47 MOD 60 --> 1081 MOD 60 = 1
Somit haben wir unser e ermittelt : e = 23. Wollen wir nun den Buchstaben "D" verschlüsseln, so gehen wir folgendermaßen vor :
Verschlüsseln : 68^d MOD p*q --> 68^47 MOD 77
Da aber eine Berechnung mit solch großen Zahlen recht problematisch werden kann ( Gültigkeitsbereich für z.B. LONG INT - Zahlen ), erreichen wir schnell einen OVERFLOW im Prozessor. [ 68^47 = 1.342514228e1E86 , eine gigantische Zahl mit 86 Stellen ]. Dies bedeutet, daß wir uns hinsichtlich der Ver- und Entschlüsselung etwas einfallen lassen müssen. Mittels "wiederholtem Quadrieren und Multiplizieren" [DG] läßt sich diese enorm große Zahl recht schnell zerlegen und das Ergebnis erzielen. Dazu wandelt man den Exponenten ( unseren Schlüssel ) in die BINÄRE-Schreibweise um.
23d --> 000010111
+-------------------------------- 2^7 -> 0 * 2^7 = 0
¦ +---------------------------- 2^6 -> 0 * 2^6 = 0
¦ ¦ +------------------------ 2^5 -> 0 * 2^5 = 0
¦ ¦ ¦ +-------------------- 2^4 -> 1 * 2^4 = 16
¦ ¦ ¦ ¦ +---------------- 2^3 -> 0 * 2^3 = 0
¦ ¦ ¦ ¦ ¦ +------------ 2^2 -> 1 * 2^2 = 4
¦ ¦ ¦ ¦ ¦ ¦ +-------- 2^1 -> 1 * 2^1 = 2
¦ ¦ ¦ ¦ ¦ ¦ ¦ +---- 2^0 -> 1 * 2^0 = 1
+-------------------------------+ ----------
¦128¦ 64¦ 32¦ 16¦ 8¦ 4¦ 2¦ 1¦ õ 23
+---+---+---+---+---+---+---+---¦
¦ 0 ¦ 0 ¦ 0 ¦ 1 ¦ 0 ¦ 1 ¦ 1 ¦ 1 ¦
+-------------------------------+
¦ ¦ ¦ ¦ +---- z0 = 1
¦ ¦ ¦ +-------- z1 = 1
¦ ¦ +------------ z2 = 1
¦ +---------------- z3 = 0
+-------------------- z4 = 1
( Ab hier werden die 0000000000000000000000000 Bits gezählt )
Konstrukt : y = x^e ; e=n-stellige natürliche Zahl ; siehe [DG]
e(i) = i-tes Bit von e ; { 0 , 1 }
------------------------------------------------------------------------
Variante 1 (Allgemein) :
--> Serielles Quadrieren und Multiplizieren :
y <-- 1
FOR i = 1 TO 0 DO
y <-- y^2
IF e(i) = 1 THEN y <-- y * x FI ; FI steht für ENDIF
OD ; OD steht für ENDDO
Variante 2 (Allgemein) :
--> Paralleles Quadrieren und Multiplizieren :
y <-- 1 , r <-- x
FOR i = 0 TO n-1 DO
IF e(i) = 1 THEN y <-- y * r FI ; FI steht für ENDIF
r <-- r^2
OD ; OD steht für ENDDO
Wir wählen Variante 1 und erhalten mit [ y^d MOD n = x ]
----------------------------------------------------------------------------
x = die zu verschlüsselnde Information ( ASCII-Codes )
b = Anzahl der Bits ( erstes gesetztes Bit von links gesehen gibt Anfang vor )
a = 1
i = b + 1
Wiederhole
i = i - 1
a = a^2 MODULAXXX n
Ist z(i) = 1 dann a = a * x MODULAXXX n
Solange bis i = 0 ist
[ x MODULAXXX y --> x - Ganzzahlenanteil(X/Y) * Y --> x - FLOOR(X/Y) * Y ]
Daraus ergibt sich :
Verschlüsseln --> e = ENCRYPT = 23 ( Öffentlicher Schlüssel )
Durchläufe : x = 68 ; b = 5 ; e = 23 ; i = 6 ; n = 77 ; d = 47
--------------------------------------------------------------------
1--> i = 4 :: a = 1^2 mod 77 = 1 :: z(4) = 1 --> a = 1 * 68 mod 77 = 68
2--> i = 3 :: a = 68^2 mod 77 = 4 :: z(3) = 0 --> a = 4
3--> i = 2 :: a = 4^2 mod 77 = 16 :: z(3) = 1 --> a = 16 * 68 mod 77 = 10
4--> i = 1 :: a = 10^2 mod 77 = 23 :: z(2) = 1 --> a = 23 * 68 mod 77 = 24
5--> i = 0 :: a = 24^2 mod 77 = 37 :: z(1) = 1 --> a = 37 * 68 mod 77 = 52
=====> a = 52 ( Das ist der verschlüsselte Code "D" --> "4")
Entschlüsseln mit d = 47 --> d = DECRYPT ( NICHT öffentlicher Schlüssel )
47d --> 00010111 -> z5 = 1
( d = 47 ) z4 = 0
z3 = 1
z2 = 1
z1 = 1
z0 = 1
Durchläufe : x = 68 ; b = 6 ; e = 23 ; i = 7 ; n = 77 ; d = 47
--------------------------------------------------------------------
1--> i = 5 :: a = 1^2 mod 77 = 1 :: z(5) = 1 --> a = 1 * 52 mod 77 = 52
2--> i = 4 :: a = 52^2 mod 77 = 9 :: z(4) = 0 --> a = 9
3--> i = 3 :: a = 9^2 mod 77 = 81 :: z(3) = 1 --> a = 81 * 52 mod 77 = 54
4--> i = 2 :: a = 54^2 mod 77 = 67 :: z(2) = 1 --> a = 67 * 52 mod 77 = 19
5--> i = 1 :: a = 19^2 mod 77 = 53 :: z(1) = 1 --> a = 53 * 52 mod 77 = 61
6--> i = 0 :: a = 61^2 mod 77 = 25 :: z(0) = 1 --> a = 25 * 52 mod 77 = 68
=====> a = 68 ( Das ist der entschlüsselte Code "4" --> "D")
ACHTUNG!!! Da wir nur ein n=77 für diesen RSA-Algorithmus ermittelt haben, können wir nur ASCII-Zeichen(x) zwischen 0¾ x ¾ n-1 verschlüsseln. Dies bedeutet, daß nur ASCII-Zeichen zwischen 1 und 76 verschlüsselt werden können, bzw. wenn wir mit A = 1... Z = 26 arbeiten und mit a = 27.... z = 53 und den Sonderzeichen, so kommen wir mit x = 77 - 2 = 75 Zeichen noch gerade so hin. Deshalb sollte man darauf achten, daß man n recht groß ermittelt, wobei für eine ASCII-Verschlüsselung der Bereich 0 ¾ x ¾ 255 als ausreichend anzusehen ist. Hierfür empfiehlt sich ein n im Bereich : 256 < n < 1000 . Überschreiten wir diese Grenze, so übertreffen die Rückgabewerte den Wert 255, und das Zeichen ist als ASCII-Zeichen nicht mehr darstellbar!
Es ergibt sich aber ein weiteres Problem, wenn wir mit recht großen Zahlen arbeiten. Die verschlüsselten Buchstaben (Informationen) können unter Umständen recht groß werden.
Ein Beispiel : Wir wählen p = 107 und q = 109 --> phi(n) = 11448
Mittels des BerlekampprogrammsXXX, bei welchem wir als
Untergrenze 110 wählen (wg. d > p & d > q ),
erhalten wir d = 127 und e = 631 sowie n = 11663.
Dies ( n - 1 = 11662 ) stellt also die größtmögliche
auftretende Zahl dar.
Ermitteln wir nun die Verschlüsselung des Buchstabens "A" ( dezimal 65 ) mittels des Schlüssels e = 631, erhalten wir den Code 2307 zurück. Dies bedeutet, daß die zurückgegebene Ziffernfolge größer ist als unser ASCII-Zeichenvorrat und wir dieses "Zeichen" nicht mehr als ASCII-Zeichen zurückschreiben bzw. darstellen können!
Wenn wir diesen Code 2307 wieder mit d = 127 entschlüsseln, erhalten wir unseren Buchstaben "A" ( ASCII-Code = 65 ) wieder zurück.
Bleiben wir allerdings unter einer gewissen Grenze mit unserem n, so können wir die zu verschlüsselnden Informationen immer noch als ASCII-Code darstellen ( im Bereich zwischen 1 und 255 ). Ansonsten erhalten wir für jede verschlüsselte Information ein Zahlenpaket, dessen Maximalwert durch n - 1 bestimmt wird ( Wertebereich : 0 ¾ x ¾ n -1 ). Diese Datenmengen wachsen dann wiederum proportional mit n an. Um Platz zu sparen, kann man diese Informationen packen, z.B. dadurch, daß man sie in hexadezimaler Form speichert oder aber feste Gruppen bildet, die dann wiederum als ASCII-Code interpretiert werden können.
Chiffre Gruppe1 Gruppe2
2307 --> 023d 007d --> um zwei Stellen gepackt
Wie man hier unschwer erkennen kann, wurde aus unserem A die Zeichenfolge XXX XXX , was eine Zunahme um ein Zeichen bedeutet !
Ein größeres Problem können aus diesem Grunde auch Feldlängen werden. Wollen wir die erhaltenen (verschlüsselten) Informationen in einem Feld ablegen, so brauchen wir ein vielfaches des uns zur Verfügung stehenden Platzes mit jedem Größerwerden von n . Ein Beispiel :
"Das ist ein Test" --> Eine Zeichenkette mit 16 Bytes die in ein C(20) großes Datenfeld bequem hineinpaßt. Wenn diese Zeichenkette nun mit einem großen n verschlüsselt ( Annahme n sei 1872665 ) wird, dann müssen wir pro verschlüsseltem Buchstaben nun 7 Bytes also 16 * 7 = 112 Bytes zur Verfügung haben. In diesem Falle würde uns der Rest, also 112 - 20 = 92 Bytes, verlorengehen, und die Informationen könnten nicht mehr entschlüsselt werden! Das ideale Verfahren ist also immer, ein Zeichen mittels einem kleinen n in ein anderes zu überführen. Nur können bei einem kleinen n recht schnell mittels Faktorisierung die beiden Schlüssel e und d gefunden werden!
Eine gute Möglichkeit besteht darin, den Quellcode zu packen und dann die Pakete zu verschlüsseln :
Wir wählen eine neue Ordnung für die von uns verwendeten Zeichen :
Leerzeichen = 00 A = 01 B = 02 C = 03 ..... Z = 26
a = 27 ..................... z = 52
ü = 53 ................. bis _ = 98
Die höchste Ziffer, die in unserem neuen System nun auftreten könnte, wäre 98. Dies bedeutet: Wenn wir diese Zahl in einem Zweierpaket betrachten, kommt 9898 als Maximalwert heraus, in einem Dreierpaket 989898 u.s.w. Wollten wir nun mit einem Dreierpaket arbeiten, welches aus 6 Ziffern besteht, so sollte auch unser n nur aus 6 Ziffern bestehen und als minimale Größe 989898 + 1 = 989899 aufweisen (wegen 0 <= y <= n - 1)! Wir wählen hierzu ein q=977 sowie
ein p=1021 --> p*q= 997517; Phi(n)=995520. Damit sind die Bedingungen erfüllt, und die Daten lassen sich bequem zusammenfassen. Das Berlekampverfahren liefert uns für die Verschlüsselung ein e = 207919 sowie ein d = 1039, wenn wir dort als Untergrenze 1030 angeben. Verschlüsseln wir nun die Ziffernfolge 676767 mittels e = 207919, so erhalten wir die Ziffernfolge 465828. Zerlegen wir diese Ziffernfolge wieder in drei Pakete --> 46 58 28, erhalten wir mit unserem gewählten Ordnungssystem die ASCII-Zeichenfolge --> XXX t(b ( für den Fall, daß 58 als XXX ( gewählt wurde ). Das ganze bietet nun auch noch doppelte Sicherheit, da ein Angreifer zuerst einmal unseren Code "knacken" und die dann erhaltenen Zeichen, welche unserer Codiertabelle entsprechen, richtig einordnen muß !
Jetzt dehnen wir das ganze bis an die Primzahl < 1000 für ein Viererpaket :
q = 9907 ; p = 9967 --> Berlekamp liefert uns ein d = 9973 und ein
e = 18313237 für eine Untergrenze von 9968.
p*q = 98743069 ; darin können wir ein Ordnungssystem für maximal 96 Zeichen
unterbringen --> 97979797.
Im Allgemeinen sollen für das RSA-Verfahren Zahlen größer 10^200 verwendet werden. Das sind Zahlen mit 200 Stellen, und dies wird sehr problematisch mit dem Adreßraum unseres Computers. Verwenden wir in C die Zahlen vom Typ DOUBLE [64 Bit] --> ± 10^307 .... ± 10^308 so können wir gerade einmal Zahlen einer Länge mit ca. 150 Stellen verarbeiten, da durch die Multiplikation [ c * c ] die Stellenanzahl der Zahl maximal verdoppelt wird !
123456 * 123456 = 15241383936 ( Durch Multiplikation von 6 auf 11 Stellen
angewachsen ) !
999999 * 999999 = 999998000001 ( Maximum --> 12 Stellen ) !
Das RSA-Verfahren zu "knacken", ist im Grunde auch kein Problem, denn man braucht nur die Schlüsselzahl durch Faktorisierung in die beiden Primzahlen p und q zu zerlegen. Aber dies ist ein Kapitel für sich, da die Mathematik keinerlei Algorithmen kennt, mit deren Hilfe diese riesigen Zahlen ( 200 Stellen und mehr ) in einer annehmbaren Zeit faktorisiert werden könnten.
Im Jahre 1993 wurde eine alte Wette aus den 70ern wieder aufgegriffen und tatsächlich gelöst. Als Grundlage diente das Internet, worin alle Beteiligten ihre Teilaufgaben lösten und die Ergebnisse an die Veranstalter zurücksandten. Es ging darum, eine bekannte Zahl (RSA-129) mit 129 Stellen zu faktorisieren, wobei der öffentliche Schlüssel n bekannt war : [CS]
RSA-129 = p * q = n
RSA-129 = 1143816257578888676692357799761466120102182967212423625625618429357069352457338
97830597123563958705058989075147599290026879543541
.. eine Zahl mit 129 Stellen.
p = 490529510847650949147849619903898133417764638493387843990820577
q = 2769132993266709549961988190834461413177642967992942539798288533
Diese Zahl wurde 1993 erfolgreich, durch etwa 600 Helfer in mehr als 20 Ländern aus 5 Kontinenten dieser Erde, in knapp 8 Monaten faktorisiert. Wenn man die Rechenleistung der beteiligten Rechner zusammenzählt, kommt man auf eine geschätzte Leistung von 5000 MIPs.
Der Kryptologe Schneier hat eine Formel aufgestellt, nach der sich die Faktorisierungszeit ermitteln läßt. Geht man hier von der RSA-129 Zahl aus, so erhält man nachfolgende Tabelle. [CS]
|
Schlüssellänge [BIT] |
Zeitfaktor relativ zu RSA-129 |
|
429 |
1.0 |
|
512 |
7.66719 |
|
1024 |
1.05473 * 10^5 |
|
2048 |
2.97180 * 10^10 |
|
4096 |
4.28061 * 10^17 |
|
8192 |
1.02939 * 10^27 |
|
16384 |
1.90839 * 10^39 |
Für bessere Verfahren, die in der Zukunft entwickelt werden, verkürzen sich die Faktorisierungszeiten entsprechend.
Die hier entwickelten Programmteile sollen als Grundlage für weitere Entwicklungen gesehen werden. Dieser Grundstock ermöglicht es Ihnen, die Verfahrensweisen kennenzulernen, um daraus praktischen Nutzen ziehen zu können. Sie wurden jedoch nur zu Lernzwecken und noch nicht für den praktischen Einsatz konzipiert, da es hier mehr um den Lernerfolg als um schnelle Programmabläufe geht. Deshalb werden einige C-Routinen den C-Profis etwas zu "weit" und zu "träge" programmiert vorkommen, aber sie sollen auch von einen Anfänger verstanden werden können, um die Prozesse nachzuvollziehen. Derjenige, welcher "schnellen Code" benötigt, möge die Programme zu seinen Zwecken optimieren und verbessern, welche im C-Quellcode der DisketteXXX beiliegen, und sie anschließend wieder den Mitgliedern der dFPUG zur Verfügung stellen.
( Die C-Programme wurden mit WATCOM c++/10.0a compiliert )
berlekamp.c / berlkamp.exe - Ermitteln der Schlüssel e und d mit gegebenem phi
crypt.c / crypt.exe - Verschlüsseln eines Wertes mit Anzeige der Werte am Bildschirm.
ermittpq.c / ermittpq.exe - Faktorisierung von p*q bei bekanntem n ( ACHTUNG : Der Faktorisierungsprozeß kann sich bei größeren Zahlen zwischen einigen Stunden bis hin zu einigen Tagen ziehen. )
primzahl.en - Eine Datei, in welcher alle Primzahlen bis 1.000 aufgelistet sind.
Die mitgelieferten Bibliotheken
CRYPT.PLB --------- für FoxPro DOS Version 2.x
CRYPT16.FLL --------- für FoxPro WIN Version 2.x
CRYPT32.FLL --------- für VisualFoxPro
stellen folgende Funktionen zur Verfügung:
IST_PRIM(<nZahl>)
Prüfen, ob das Argument eine Primzahl ist.
Rückgabe ist logisch .T. oder .F.
z.B.: ? IST_PRIM( 9977 ) --> .F.
? IST_PRIM( 9929 ) --> .T.
BERLEKAMP(<nUntergrenze_d>,<Ermitteltes Phi(n)>) ¦
Ermitteln des d und e für die Verschlüsselung.
Rückgabe ist .T., wenn BERLEKAMP erfolgreich war, ansonsten .F.
Wurde die Funktion erfolgreich durchlaufen, so legt diese die beiden Variablen berle_d und berle_e an.
=BERLEKAMP(1030,995520) ---> liefert .T.
? berle_d ---> 1039
? berle_e ---> 207919
RSA_CRYPT(<nCode>,<Schlüssel.e_d>,<Schlüssel.n>)
Verschlüsseln eines numerischen Wertes.
Rückgabe ist ein Integer-Wert der verschlüsselten Zeichenkette. (siehe Beispielprogramm)
XOR_CRYPT(<cInformation>,<cSchlüssel>)
Übergeben werden eine Zeichenkette und ein Schlüsselwort.
Rückgabe ist die verschlüsselte Zeichenkette.
z.B.: cINFO = "Angriff im Morgengrauen"
cKEY = "dFPUG"
encrypt = XOR_CRYPT( cINFO , cKEY )
? encrypt
decrypt = XOR_CRYPT( encrypt , cKEY )
? decrypt
*
Nachstehende Quellen wurden verwendet :
[AB], Albrecht Beutelsbacher, Kryptologie
VIEWEG, - ISBN 3-528-38990-7, 34,- DM, 180 Seiten
( Recht gut und einfach für Anfänger verständlich mit vielen detailierten Beispielen beschrieben. Eine Einführung in die Wissenschaft vom Verschlüsseln, Verbergen und Verheimlichen. )
[CS], Claus Schröder, Verschlüsselungsverfahren für PC-Daten, Bookware mit CD-ROM
FRANZIS - ISBN 3-7723-5043-7 ( 69,- DM ) 220 Seiten
( Schlicht und ergreifend: Eine fundierte Einführung in die Technik der Verschlüsselung. Der Autor erklärt einfach und für jedermann verständlich die verschiedenen Verfahren, mit denen man Informationen vor dem Zugriff Unbefugter schützen kann. Auf der mitgelieferten CD-ROM befindet sich auch eine Vollversion des bekannten Verschlüsselungsprogrammes "WISO-Crypt für Windows". )
[DG], Dieter Gollmann, Algorithmen-Entwurf in der Kryptographie ( Aspekte komplexer Systeme ), B¨I¨ Wissenschaftsverlag - ISBN 3-411-16671-1 ( 68,- DM ) 160 Seiten
( Habilitationsschrift, enstanden an der Fakultät für Informatik an der Universität Karlsruhe. Recht komplexes Werk, das viele elementare Grundkenntnisse der Mathematik vorraussetzt. )
[FB], Friedrich L. Bauer, Entzifferte Geheimnisse - Methoden und Maximen der Kryptologie
SPRINGER - ISBN 3-540-58118-9 ( 58,- DM ) 400 Seiten
( Ein Buch, das aus Vorlesungsskripten der TU-München enstanden ist und dem Leser viele interressante Einblicke in die Kryptologie vermittelt. Das Buch setzt nur elementare mathematische Kenntnisse vorraus. Mit einer Fülle spannender, lustiger und bisweilen anzüglicher Geschichten aus der historischen Kryptologie gewürzt, ist es auch für den Laien reizvoll zu lesen. )