Cäsar

Aufgabe

So funktioniert die Cäsar-Verschlüsselung

Jeder Buchstabe wird um eine feste Zahl von Stellen im Alphabet verschoben; nach Z geht es bei A weiter. Diese Zahl ist der Schlüssel. Unverschlüsselter Text heißt Plaintext, verschlüsselter Text Ciphertext. Mit dem Schlüssel $1$ wird aus HELLO der Ciphertext IFMMP:

Zum Rechnen nummeriert man die Buchstaben: A (oder a) ist $0$, B ist $1$, …, Z ist $25$. Ist $p_i$ die Nummer des $i$-ten Buchstabens im Plaintext und $k$ der Schlüssel, dann ist die Nummer des $i$-ten Buchstabens im Ciphertext

$c_i = (p_i + k)$ % 26

Dabei bedeutet % 26 „Rest bei der Division durch 26“; so geht es nach Z wieder bei A los. Beispiel Hey mit dem Schlüssel $3$:

Warum das Verfahren nach Cäsar heißt, steht am Ende der Seite unter „Zum Weiterlesen“.

Demo

Spezifikation

Entwerfen und implementieren Sie ein Programm, caesar, das Nachrichten mit der Cäsar-Verschlüsselung verschlüsselt.

• Implementieren Sie Ihr Programm in C in einer Datei namens caesar.c in einem Ordner namens caesar.
• Ihr Programm muss ein einzelnes Kommandozeilenargument akzeptieren, eine nicht-negative Ganzzahl. Nennen wir diese im weiteren Verlauf der Einfachheit halber $k$.
• Wenn Ihr Programm ohne Kommandozeilenargumente oder mit mehr als einem Kommandozeilenargument ausgeführt wird, sollte Ihr Programm eine Fehlermeldung Ihrer Wahl (mit printf) ausgeben und sofort einen Wert von 1 aus main zurückgeben (was normalerweise einen Fehler signalisiert).
• Wenn eines der Zeichen des Kommandozeilenarguments keine Dezimalziffer ist, sollte Ihr Programm die Nachricht Usage: ./caesar key ausgeben und einen Wert von 1 aus main zurückgeben.
• Gehen Sie nicht davon aus, dass $k$ kleiner oder gleich 26 ist. Ihr Programm sollte für alle nicht-negativen Ganzzahlwerte von $k$ funktionieren, die kleiner als $2^{31} - 26$ sind. Das heißt, Sie müssen sich keine Sorgen machen, wenn Ihr Programm irgendwann nicht mehr funktioniert, wenn der Benutzer einen Wert für $k$ wählt, der zu groß oder fast zu groß ist, um in einen int zu passen. (Erinnern Sie sich daran, dass ein int überlaufen kann.) Ansonsten gilt aber: Auch wenn $k$ größer als 26 ist, sollten in das Programm eingegebene alphabetische Zeichen auch bei der Ausgabe alphabetische Zeichen bleiben. Wenn $k$ beispielsweise $27$ ist, sollte A nicht zu \ werden, auch wenn \, laut asciitable.com, 27 Positionen von A im ASCII-Code entfernt ist; A sollte zu B werden, da B 27 Positionen von A entfernt ist, vorausgesetzt, Sie laufen von Z zu A über.
• Ihr Programm muss plaintext: (mit zwei Leerzeichen, aber ohne Zeilenumbruch) ausgeben und den Benutzer dann einen string mit dem Plaintext eingeben lassen (mithilfe von get_string).
• Ihr Programm muss ciphertext: (mit einem Leerzeichen, aber ohne Zeilenumbruch) gefolgt vom entsprechenden Ciphertext des Plaintexts ausgeben, wobei jedes alphabetische Zeichen im Klartext um k Positionen “rotiert” wird; nicht-alphabetische Zeichen sollten unverändert ausgegeben werden.
• Ihr Programm muss die Groß-/Kleinschreibung beibehalten: Großbuchstaben müssen, trotz Rotation, Großbuchstaben bleiben; dasselbe gilt für Kleinbuchstaben.
• Nachdem der Ciphertext ausgegeben wurde, sollten Sie einen Zeilenumbruch ausgeben. Ihr Programm sollte dann durch Rückgabe von 0 aus main beendet werden.

Hilfestellung

Wie soll man anfangen? Nähern wir uns dieser Aufgabe Schritt für Schritt.

Pseudocode

Schreiben Sie zuerst eine main Funktion in caesar.c, die das Programm nur mit Pseudocode skizziert, auch wenn Sie (noch!) nicht sicher sind, wie Sie es mit richtigem Code implementieren sollen.

int main(int argc, string argv[])
{
    // Make sure program was run with just one command-line argument

    // Make sure every character in argv[1] is a digit

    // Convert argv[1] from a `string` to an `int`

    // Prompt user for plaintext

    // For each character in the plaintext:

        // Rotate the character if it's a letter
}

Befehlszeilen-Argumente zählen

Wie auch immer Ihr Pseudocode aussieht, lassen Sie uns zunächst nur den C-Code schreiben, der prüft, ob das Programm mit einem einzigen Befehlszeilenargument ausgeführt wurde.

Hierzu müssen Sie Änderungen an der main-Funktion vornehmen. Diese sollte "Usage: ./caesar key\n" ausgeben und dann durch die Rückgabe von 1 das Programm beenden, wenn der Benutzer keine Befehlszeilenargumente oder zwei oder mehr angibt. Wenn der Benutzer genau ein Befehlszeilenargument angibt, sollte das Programm erst einmal nichts ausgeben und einfach 0 zurückgeben. Das Programm sollte sich also wie im Folgenden gezeigt verhalten:

$ ./caesar
Usage: ./caesar key

$ ./caesar 1 2 3
Usage: ./caesar key

$ ./caesar 1

Überprüfen des Schlüssels

Jetzt, da Ihr Programm (hoffentlich!) die Eingaben wie vorgeschrieben akzeptiert, ist es Zeit für den nächsten Schritt.

Fügen Sie unterhalb von main eine Funktion hinzu, die z.B. only_digits heißt, die einen string als Argument nimmt und true zurückgibt, wenn dieser string nur Ziffern, 0 bis 9, enthält, andernfalls gibt sie false zurück. Stellen Sie sicher, dass Sie den Prototyp der Funktion auch über main einfügen.

Dann passen Sie main so an, dass diese only_digits auf argv[1] aufruft. Wenn diese Funktion false zurückgibt, dann sollte main "Usage: ./caesar key\n" ausgeben und 1 zurückgeben. Andernfalls sollte main weiterhin erst einmal nur 0 zurückgeben. Das Programm sollte sich also wie folgt verhalten:

$ ./caesar 42

$ ./caesar banana
Usage: ./caesar key

Verwenden des Schlüssels

Ergänzen Sie nun main so, dass es argv[1] in einen int umwandelt. Hierbei könnte Ihnen etwa atoi behilflich sein, das gemäß Handbuch in stdlib.hdeklariert ist. Benutzen Sie dann wie gewohnt get_string, um den Benutzer mit "plaintext: " nach einem Klartext zu fragen.

Als nächstes implementieren Sie eine Funktion, die z.B. rotate heißt, und als Eingabe einen char und einen int entgegennimmt. Der int legt dabei fest, um wie viele Positionen der übergebene char rotiert wird. Aber nur, wenn es ein Buchstabe ist! Wenn der char kein Buchstabe ist, sollte die Funktion stattdessen den gleichen char unverändert zurückgeben. Zusätzlich muss, falls erforderlich, der Überlauf von Z nach A (und von z nach a) behandelt werden.

Erweitern Sie main abschließend so, dass es "ciphertext: " ausgibt und dann über jedes char im Klartext des Benutzers iteriert, für jedes rotate aufruft und den Rückgabewert ausgibt.

Testen

Korrektheit

Führen Sie in Ihrem Terminal den folgenden Befehl aus, um die Korrektheit Ihrer Arbeit zu überprüfen:

check50 -l cs50/problems/2024/x/caesar

debug50 ./caesar KEY

debug50 ./caesar

Style

Führen Sie den folgenden Befehl aus, um den Stil Ihres Codes mit style50Prüfprogramm von CS50, das zeigt, wo Ihr Code von den Formatierungsregeln abweicht. In Grün zeigt es, was Sie ergänzen sollten, in Rot, was wegfallen soll. Glossar → zu analysieren:

style50 caesar.c

Zum Weiterlesen: Cäsar und seine Geheimschrift

Für die Lösung der Aufgabe nicht nötig.

Angeblich hat Cäsar vertrauliche Nachrichten „verschlüsselt“ (d.h. umkehrbar unkenntlich gemacht), indem er jeden Buchstaben um eine bestimmte Anzahl von Stellen verschob. Zum Beispiel könnte er A als B geschrieben haben, B als C, C als D, …, und am Ende beim Überschreiten des Alphabets, Z als A. Um jemandem “HELLO” zu sagen, könnte Cäsar also stattdessen “IFMMP” geschrieben haben. Der Empfänger dieser Nachricht müsste diese “entschlüsseln”, indem er die Buchstaben um die gleiche Anzahl von Stellen in die entgegengesetzte Richtung verschiebt.

Die Sicherheit dieses “Kryptosystems” beruhte darauf, dass nur Cäsar und die Empfänger das Geheimnis kannten, nämlich die Anzahl der Stellen, um die Cäsar seine Buchstaben verschoben hatte (z.B. 1). Nach heutigen Maßstäben ist diese Verschlüsselung nicht besonders sicher. Aber wenn man das womöglich als Erster überhaupt gemacht hat, ist es natürlich ziemlich sicher!