Kryptologie/Caesar-Verschlüsselungsverfahren – Wikiversity (2024)

Einleitung

Das Beispiel des Caesar-Verschlüsselungsverfahrens in der Lerneinheit zu Symmetrische Verschlüsselungsverfahren hat das Prinzip hinter dem Caesar-Verschlüsselungsverfahren bereits veranschaulicht. Wenn Sie die Seite studiert haben, sollten Sie bereits selbst einen Text mithilfe des Verfahrens verschlüsseln können. Es lohnt sich aber trotzdem das Verfahren auch aus einer verstärkt mathematischen Perspektive zu betrachten. Die mathematischen Grundlagen dieses Verfahren sind nämlich ebenfalls wichtige Grundlagen für komplexere und modernere (asymmetrische) Kryptosysteme, wie beispielsweise dem RSA-Kryptosystem. Wir nutzen diese Lerneinheit daher, um in wichtige Grundlagen der Zahlentheorie einzuführen und somit die Stofffülle bei weiteren Lerneinheiten zu reduzieren.

Zeichenkodierung des Caesar-Verschlüsselungsverfahrens

Zeichenkodierung und Anzahl der Elemente einer Menge
Zeichenkodierung
Seien und Zeichen der entsprechenden Alphabete und eine Funktion mit , die die Zeichen eines beliebigen Alphabets auf ein Alphabet gleicher Länge. Dabei wird auf kein Zeichen von mehrfach abgebildet, aber jedes Zeichen von wird auf ein Zeichen von abgebildet. Es existiert außerdem die Umkehrfunktion mit genau dann, wenn . Wir nennen die Funktion Zeichenkodierung und die Umkehrfunktion Zeichendekodierung von und [1].
Anzahl der Elemente einer Menge
Sei eine endliche Menge, dann ist Anzahl der Elemente von [2].

Besteht das Alphabet des Klartexten nicht nur aus numerischen Zeichen, so übertragen wir diese zunächst für das Caesar-Verschlüsselungsverfahren in ein numerisches Alphabet . Wir wählen hierfür ein Alphabet , das die gleiche Anzahl an Zeichen wie aufweist^[3]. Wir zeigen dies anhand einer beispielhaften Zeichenkodierung, die wir im Folgenden auch verwenden werden.

Wir definieren Start- und Zielalphabet:

Startalphabet

Zielalphabet

Bemerkung: bezeichnet die Anzahl der Elemente von .

Die zugehörige Zeichenkodierung lautet:

,

mit , , ..., .

Um die Zeichen des Alphabets erneut in Zeichen des Alphabets umzuwandeln, wenden wir die Umkehrfunktion an. Dabei gilt:

,

mit , , ... ^[1].

Algorithmus

Sei mit ein Schlüssel, sei ein Klartext und der zugehörige Geheimtext. Beide bestehen aus Zeichen des Alphabets .

Der Algorithmus der Caesar-Verschlüsselung lautet:

Schlüsselerzeugung

Anzahl der Elemente einer Menge, Kongruenz, Restklasse und Repräsentant
Anzahl der Elemente einer Menge
Sei eine endliche Menge, dann ist Anzahl der Elemente von [2].
Kongruenz
Seien und , dann gilt [4].
Restklasse
Sei modulo einer Zahl die Menge aller ganzen Zahlen, die den gleichen Rest bei Division durch aufweisen wie . Dann ist die Restklasse zu [5].
Repräsentant (einer Restklasse)
Ein Element einer Restklasse nennen wir Repräsentant der Restklasse[6]. Die Elemente modulo nennen wir Standardrepräsentant.

Wähle mit zufällig und gleichverteilt.

Verschlüsselungsalgorithmus

.

Entschlüsselungsalgorithmus

^[7].

Korrektheit des Caesar-Verschlüsselungsverfahren

Voraussetzung

Sei und

Zu zeigen

Für alle und gilt (da Ver- und Entschlüsselungsfunktion den identischen Schlüssel verwenden)

Beweis

, nach Definition

, nach Definition

, da

Bemerkung

• In der Praxis muss der entsprechende Algorithmus auf jedes Zeichen des Klar- oder Geheimtextes einzeln angewandt werden (siehe Beispiel).
• Wir definieren den Caesar-Algorithmus mit Hilfe der Modulo-Funktion, da wir diese für den RSA-Algorithmus ebenfalls benötigen.
• Theoretisch sind auch Schlüssel größer als denkbar, aber da die Algorithmen mit Modulo arbeiten, sind beispielsweise und Repräsentanten der gleichen Restklasse im Restklassenring
• Wollen wir einen Klartext mit lateinischen Buchstaben verschlüsseln, so müssen wir zunächst eine Zeichenkodierung des Klartextes in ein numerisches Alphabet vornehmen. Analog dazu, müssen wir den Geheimtext in das lateinische Alphabet übertragen, wenn unserer Geheimtext aus Buchstaben bestehen soll.

Beispiel

Wir wollen den Klartext "ASTERIX" mit dem Schlüssel aus der Menge verschlüsseln und einen Geheimtext mit lateinischen Buchstaben erhalten. Da es sich bei unserem Klartext ein Wort mit Zeichen des lateinischen Alphabets handelt, müssen wir eine Zeichenkodierung durchführen.

Zeichenkodierung

Zeichenkodierung und Anzahl der Elemente einer Menge
Zeichenkodierung
Seien und Zeichen der entsprechenden Alphabete und eine Funktion mit , die die Zeichen eines beliebigen Alphabets auf ein Alphabet . Dabei wird auf kein Zeichen von mehrfach abgebildet, aber jedes Zeichen von wird auf ein Zeichen von abgebildet. Es existiert außerdem die Umkehrfunktion mit genau dann, wenn für . Wir nennen die Funktion Zeichenkodierung und die Umkehrfunktion Zeichendekodierung von und [1].
Anzahl der Elemente einer Menge
Sei eine endliche Menge, dann ist Anzahl der Elemente von [2].

Wir definieren zunächst Definitions- und Zielmenge:

mit

und unsere Zeichenkodierung :

,

mit , , ..., (vgl. Tabelle 2).

Die Umkehrung lautet:

mit , , ..., (vgl. Tabelle 2).

Tabelle 2: Zuordnung der Zeichenkodierung

Klartext (Definitionsmenge)	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
Zugeordnete Zahl (Zielmenge)	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25

Verschlüsselungsalgorithmus

Kongruenz
Kongruenz
Seien und , dann gilt [4].

Entschlüsselungsalgorithmus

Verschlüsselung des Wortes "ASTERIX"

1. Zeichen A

2. Zeichen S

3. Zeichen T

4. Zeichen E

5. Zeichen R

6. Zeichen I

7. Zeichen X

Nun haben wir für jedes Zeichen des Klartextes die zum Zeichen des Geheimtextes zugehörige Zahl berechnet. Wir müssen nun noch die Umkehrfunktion von auf die Standardrepräsentanten der Restklassen anwenden, wenn wir den Geheimtext im lateinische Alphabet erhalten wollen.

, , , , , und .

Der Geheimtext lautet also "HZALYPE".

Entschlüsselung des Wortes "HZALYPE"

1. Zeichen H

Kongruenz
Kongruenz
Seien und , dann gilt [4].

2. Zeichen Z

3. Zeichen A

4. Zeichen L

5. Zeichen Y

6. Zeichen P

7. Zeichen E

Analog zur Verschlüsselung müssen wir nun erneut die Umkehrfunktion auf die Standardrepräsentanten der Restklassen anwenden.

, , , , , und .

Der Klartext lautet nach dem Entschlüsselungsalgorithmus "ASTERIX" und stimmt somit mit dem verschlüsselten Klartext überein.

Sicherheit

Die Caesar-Verschlüsselung stellt ein besonders unsicheres Verschlüsselungsverfahren dar, weil es nur 25 unterschiedliche Restklassen als Schlüssel gibt Wäre nämlich , dann würde der Klartext zu einem identischen Geheimtext verschlüsselt^[9]. Ist einem Angreifer das Verschlüsselungsverfahren bekannt, so muss er also nur alle 25 relevanten Schlüssel in die Entschlüsselungsfunktion einsetzen und kontrollieren, bei welchem Schlüssel der Geheimtext in den Klartext entschlüsselt wird. Man nennt diese Art des Angriffs Brute-Force-Attacke^[10][11]. Es ergeben sich noch weitere Angriffsmöglichkeiten, wie beispielsweise die Häufigkeitsanalyse. Diese beruht bei dem Caesar-Verschlüsselungsverfahren darauf, dass die einzelnen Buchstaben der Definitionsmenge immer durch die selben Buchstaben der Zielmenge ersetzt werden. Die Häufigkeitsverteilung Buchstaben in Texten ist je nach Sprache unterschiedlich^[8]. Beispielsweise ist der Buchstabe E mit ca. 18% der am häufigsten verwendete Buchstabe in deutschsprachigen Texten (vgl. Tabelle 3)^[8]. Wird ein deutscher Klartext verschlüsselt und der Geheimtext enthält besonders häufig den Buchstaben L, so kann man zunächst vermuten, dass der Buchstabe E des Klartextes durch den Verschlüsselungsalgorithmus durch ein L im Geheimtext ersetzt wurde. Dies entspricht dem Schlüssel , da der Abstand zwischen E und L im Alphabet 7 ist. Der Text kann anschließend mit der Entschlüsselungsfunktion mit getestet werden^[12].

Bemerkung: Warum konnte Caesar seine Klartexte guten Gewissens mit diesem Verschlüsselungsverfahren verschlüsseln? Die Antwort ergibt ich aus der Zeit, zu der Caesar lebte. Das Verfahren war zu dieser Zeit nämlich weitgehend unbekannt und es war eine legitime Annahme, dass Dritte den Geheimtext für eine Nachricht in einer ihnen unbekannten Sprache halten würden. Für die Sicherheit der Caesar-Verschlüsselung war es also wichtig, den Algorithmus und nicht nur den Schlüssel geheim zu halten^[12][13].

Lernaufgabe

Aufgabe 1

Berechnen Sie die Entschlüsselung von folgendem Geheimtext mit der Entschlüsselungsfunktion des Caesar-Verschlüsselungsverfahrens und .

"QVRFCVAARAQVREBRZRE"

Lösung
Wir wenden den Entschlüsselungsalgorithmus mit und anschließend die Umkehrfunktion der Zeichenkodierung an, um den Klartext für zu erhalten: Der Klartext für lautet: DIESPINNENDIEROEMER Der Klartext scheint Sinn zu ergeben. Ob es tatsächlich der gesuchte Klartext ist, können wir auf Anhieb nicht sicher sagen, da der Geheimtext mit einem anderen ebenfalls einen sinnvollen Klartext ergeben hätte.

Aufgabe 2

Wir haben unbemerkt folgenden Geheimtext abgefangen:

RLWWTPYTYDPTYPCRPDLXESPTETDETYOCPTEPTWPLFQRPEPTWEOPCPYPTYPYOTPMPWRPCMPHZSYPYPTYPYLYOPCPYOTPLBFTELYPCFYOOPYOCTEEPYOTPUPYTRPYOTPTYTSCPCPTRPYPYDACLNSPVPWEPYTYFYDPCPCRLWWTPCRPYLYYEHPCOPYOTPDPLWWPFYEPCDNSPTOPYDTNSFYEPCPTYLYOPCOFCNSTSCPDACLNSPOFCNSTSCPPTYCTNSEFYRPYFYOTSCPRPDPEKPOTPRLWWTPCHPCOPYGZYOPYLBFTELYPCYOFCNSOPYQWFDDRLCFYYLGZYOPYMPWRPCYOFCNSXLECLYLFYODPBFLYLRPEPTWEOTPELAQPCDEPYGZYOTPDPYGZPWVPCYDTYOOTPMPWRPCHPTWDTPGZYOPCKTGTWTDLETZYFYOOPCVFWEFCOPDCZPXTDNSPYGZWVPDPYEQPCYEDTYOFYOHPTWLXHPYTRDEPYZQEVLFQWPFEPKFTSYPYVZXXPYFYOOLDPTYQFPSCPYHLDOTPWPFEPGPCHPTNSWTNSEFYOHPTWDTPOPYRPCXLYPYLXYLPNSDEPYHZSYPYOTPLFQOPCLYOPCPYDPTEPOPDCSPTYPDHZSYPYFYOXTEOPYPYDTPTXXPCVCTPRQFPSCPYOLSPCMPCECPQQPYLFNSOTPSPWGPETPCOTPFPMCTRPYRLWWTPCLYELAQPCVPTEHPTWDTPTYQLDEELPRWTNSPYDNSWLNSEPYXTEOPYRPCXLYPYVLPXAQPYTYOPXDTPDTPPYEHPOPCGZYTSCPXRPMTPELMHPSCPYZOPCDPWMDETYOPCPYRPMTPEVCTPRQFPSCPYGZYTSYPYPTYEPTWOPYHTPRPDLREOTPRLWWTPCTYYPSLMPYMPRTYYELYOPCCSZYPPCHTCOMPRCPYKEGZYOPCRLCZYYPOPXZKPLYFYOGZYOPXWLYOPOPCMPWRPCPCMPCFPSCELFNSGZYOPCDPTEPOPCDPBFLYPCFYOSPWGPETPCLFDOPYCSPTYPCWTPREYLNSYZCOPYKFOLDRPMTPEOPCMPWRPCMPRTYYELYOPYLFPDDPCDEPYRCPYKPYRLWWTPYDPDPCDECPNVEDTNSMTDKFXFYEPCPYEPTWPOPDCSPTYPDPDDNSLFEYLNSYZCOZDEPYLBFTELYTPYPCDECPNVEDTNSGZYOPCRLCZYYPMTDKFXAJCPYLPPYRPMTCRPFYOOPXUPYTRPYEPTWOPDZKPLYDOPCMPTDALYTPYTDEPDDNSLFEYLNSYZCOHPDEPY

Berechnen Sie die Entschlüsselung von folgendem Geheimtext mit einer Häufigkeitsanalyse und der Entschlüsselungsfunktion der Caesar-Verschlüsselung. Geben Sie an, welchen Wert der zugehörige Schlüssel hat.

Lösung

Wir wenden zur Entschlüsselung eine Häufigkeitsanalyse auf den Geheimtext an, d.h. wir vergleichen die relative Buchstabenhäufigkeit der deutschen Sprache mit der Buchstabenhäufigkeit des Geheimtextes. Die Ergebnisse werden in Tabelle 1 (siehe Hinweis) festgehalten. Vergleicht man die relative Häufigkeit der am meisten vorkommenden Buchstaben in Tabelle 1, so sieht man, dass der Buchstabe P mit 20,13% am häufigsten vorkommt. Dies legt die Vermutung nahe, dass der Buchstabe im im Geheimtext dem häufigsten Buchstaben der deutschen Sprachen im Klartext entspricht. Wir können Tabelle 1 entnehmen, dass dieser Buchstabe ist. Da es sich bei der Caesar-Verschlüsselung um eine Verschiebung des Alphabets um Buchstaben handelt, betrachten wir den Abstand zwischen und . Wir stellen hierfür eine Verschiebungstabelle der lateinischen Buchstaben und den Zahlen von 1 bis 26 auf (siehe Hinweis 2). ist der 16. Buchstabe und der fünfte. Der Abstand ist also folglich und der Schlüssel verschiebt die Buchstaben um Stellen nach rechts. Wir probieren den Geheimtext mit zu entschlüsseln und erhalten den Klartext: GALLIENINSEINERGESAMTHEITISTINDREITEILEAUFGETEILTDERENEINENDIEBELGERBEWOHNENEINENANDERENDIEAQUITANERUNDDENDRITTENDIEJENIGENDIEINIHREREIGENENSPRACHEKELTENINUNSERERGALLIERGENANNTWERDENDIESEALLEUNTERSCHEIDENSICHUNTEREINANDERDURCHIHRESPRACHEDURCHIHREEINRICHTUNGENUNDIHREGESETZEDIEGALLIERWERDENVONDENAQUITANERNDURCHDENFLUSSGARUNNAVONDENBELGERNDURCHMATRANAUNDSEQUANAGETEILTDIETAPFERSTENVONDIESENVOELKERNSINDDIEBELGERWEILSIEVONDERZIVILISATIONUNDDERKULTURDESROEMISCHENVOLKESENTFERNTSINDUNDWEILAMWENIGSTENOFTKAUFLEUTEZUIHNENKOMMENUNDDASEINFUEHRENWASDIELEUTEVERWEICHLICHTUNDWEILSIEDENGERMANENAMNAECHSTENWOHNENDIEAUFDERANDERENSEITEDESRHEINESWOHNENUNDMITDENENSIEIMMERKRIEGFUEHRENDAHERBERTREFFENAUCHDIEHELVETIERDIEUEBRIGENGALLIERANTAPFERKEITWEILSIEINFASTTAEGLICHENSCHLACHTENMITDENGERMANENKAEMPFENINDEMSIESIEENTWEDERVONIHREMGEBIETABWEHRENODERSELBSTINDERENGEBIETKRIEGFUEHRENVONIHNENEINTEILDENWIEGESAGTDIEGALLIERINNEHABENBEGINNTANDERRHONEERWIRDBEGRENZTVONDERGARONNEDEMOZEANUNDVONDEMLANDEDERBELGERERBERUEHRTAUCHVONDERSEITEDERSEQUANERUNDHELVETIERAUSDENRHEINERLIEGTNACHNORDENZUDASGEBIETDERBELGERBEGINNTANDENAUESSERSTENGRENZENGALLIENSESERSTRECKTSICHBISZUMUNTERENTEILEDESRHEINESESSCHAUTNACHNORDOSTENAQUITANIENERSTRECKTSICHVONDERGARONNEBISZUMPYRENAEENGEBIRGEUNDDEMJENIGENTEILDESOZEANSDERBEISPANIENISTESSCHAUTNACHNORDWESTEN [15][16] Aufgrund der Länge und Komplexität des ermittelten Klartexten ist nicht anzunehmen, dass mit einem anderen Schlüssel ein zweiter möglicher Klartext ermittelt werden könnte und wir gehen davon aus, dass wir den von den Kommunikationspartnern verwendeten Schlüssel gefunden haben.

Aufgabe 3

Erläutern Sie, warum wir annehmen können, dass der Schlüssel auch für weitere Nachrichten zwischen den Kommunikationspartnern verwendet wird?

Lösung

Da die Caesar-Verschlüsselung ein symmetrisches Verfahren ist und die Schlüssel zwischen Kommunikationspartnern nur schwer sicher ausgetauscht werden können, wird der Schlüssel wahrscheinlich für mehrere Texte verwendet werden, solange er als sicher von den Kommunikationspartnern wahrgenommen wird. Wir werden also wahrscheinlich auch weitere Geheimtexte zwischen diesen beiden Kommunikationspartnern mit dem Schlüssel entschlüsseln können.

Lernempfehlung

Literatur

1. ↑ ^{1,0 1,1 1,2} Bauer, F. L. (2000). Entzifferte Geheimnisse: Methoden und Maximen der Kryptologie (3., überarb. und erw. Aufl). Springer. S. 34.
2. ↑ ^{2,0 2,1 2,2} Reiss, K., & Schmieder, G. (2014). Basiswissen Zahlentheorie: Eine Einführung in Zahlen und Zahlbereiche (3. Aufl.). Springer Spektrum. S. 30.
3. ↑ Schüller, A., Trottenberg, U., Wienands, R., Koziol, M., & Schneider, R. (2017). RSA – Primzahlen zur Verschlüsselung von Nachrichten. S. 5.
4. ↑ ^{4,0 4,1 4,2} Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Berlin, Heidelberg: Springer. S. 37.
5. ↑ Schüller, A., Trottenberg, U., Wienands, R., Koziol, M., & Schneider, R. (2017). RSA – Primzahlen zur Verschlüsselung von Nachrichten. S. 6.
6. ↑ ^{6,0 6,1} Ziegenbalg, J. (2015). Elementare Zahlentheorie: Beispiele, Geschichte, Algorithmen (2., überarb. Aufl). Springer Spektrum. S. 86.
7. ↑ Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Springer. S. 75.
8. ↑ ^{8,0 8,1 8,2} Bauer, F. L. (1997). Entzifferte Geheimnisse: Methoden und Maximen der Kryptologie (2., erw. Aufl). Springer. S. 286.
9. ↑ Miller, M. (2003). Symmetrische Verschlüsselungsverfahren. Vieweg+Teubner Verlag. S. 3.
10. ↑ Seite „Brute-Force-Methode“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 26. November 2019, 12:49 UTC. URL: https://de.wikipedia.org/w/index.php?title=Brute-Force-Methode&oldid=194393293 (Abgerufen: 20. Januar 2020, 13:54 UTC)
11. ↑ Beutelspacher, A., Neumann, H. B., & Schwarzpaul, T. (2010). Kryptografie in Theorie und Praxis: Mathematische Grundlagen für Internetsicherheit, Mobilfunk und elektronisches Geld (2., überarb. Aufl). Vieweg + Teubner. S. 67.
12. ↑ ^{12,0 12,1} "Caesar-Verschlüsselung". In: Serlo Education e.V. Bearbeitungsstand: 67331. URL: https://de.serlo.org/informatik/verschluesselung/caesar-verschluesselung-48121 (abgerufen am 11.12.2019; Formulierung verändert)
13. ↑ Pieprzyk, J., Hardjono, T., & Seberry, J. (2003). Fundamentals of Computer Security. Springer-Verlag. S. 6.
14. ↑ Bauer, F. L. (2013). Entzifferte geheimnisse: methoden und maximen der kryptologie. Springer-Verlag. S. 304.
15. ↑ De Bello Gallico: Liber I - Kapitel I. (17. Juli 2018). Wikibooks, Die freie Bibliothek. Abgerufen am 19. Februar 2020, 13:27 von https://de.wikibooks.org/w/index.php?title=De_Bello_Gallico:_Liber_I_-_Kapitel_I&oldid=854827. (Form verändert)
16. ↑ Caesar. De Bello Gallico. Buch 1. Kapitel 1.