Cäsar

Aufgabe

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!

Unverschlüsselter Text wird allgemein als Plaintext, verschlüsselter Text als Ciphertext bezeichnet. Das verwendete Geheimnis wird Schlüssel genannt.

So wird mit einem Schlüssel von $1$ aus dem Plaintext HELLO der Ciphertext IFMMP:

Formal gesehen verschlüsselt Cäsar’s Algorithmus (auch Cäsar-Verschlüsselung genannt) Nachrichten, indem er jeden Buchstaben um $k$ Positionen “dreht”. Wenn $p$ ein Klartext (d.h. eine unverschlüsselte Nachricht), $p_i$ das $i^{te}$ Zeichen in $p$, und $k$ ein geheimer Schlüssel ist (d.h. eine nicht negative ganze Zahl), dann wird jeder Buchstabe $c_i$ im Ciphertext $c$ berechnet als,

$c_i = (p_i + k)$ % 26

wobei % 26 hier “Rest bei der Division durch 26” bedeutet. Diese Formel lässt die Verschlüsselung vielleicht komplizierter erscheinen, als sie ist. Letztlich handelt es sich aber nur um eine kompakte Art, den Algorithmus präzise auszudrücken. Stellen Sie sich A (oder a) als $0$, B (oder b) als $1$, …, H (oder h) als $7$, I (oder i) als $8$, …, und Z (oder z) als $25$ vor. Nehmen wir an, Cäsar möchte jemandem vertraulich Hi sagen, wobei er dieses Mal einen Schlüssel von $3$ verwendet. Sein Klartext, $p$, lautet also Hi, wobei das erste Zeichen seines Klartextes, $p_0$, H (alias 7) ist und das zweite Zeichen seines Klartextes, $p_1$, i (alias 8) ist. Das erste Zeichen seines Ciphertextes, $c_0$, ist also K, und das zweite Zeichen seines Ciphertextes, $c_1$, ist also L. Alles klar soweit?

Dann wollen wir jetzt ein Programm schreiben, mit dem Sie ganz einfach Nachrichten mit der Cäsar-Verschlüsselung verschlüsseln können. Wenn der Benutzer das Programm ausführt, sollte er durch ein Kommandozeilenargument festlegen, welcher Schlüssel zur Verschlüsselung der Nachricht benutzt werden soll. Die Nachricht selbst gibt der Benutzer wie bislang zur Laufzeit ein. Wir sollten nicht notwendigerweise davon ausgehen, dass der Schlüssel des Benutzers eine Zahl ist; wenn es allerdings eine Zahl ist, können Sie davon ausgehen, dass es sich um eine positive ganze Zahl handelt.

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 style50 zu analysieren:

style50 caesar.c