Block-Cipher (Schritt für Schritt)

Phase 1: Problem verstehen

Einstiegsfragen

  • Was bedeutet Verschlüsselung allgemein?
  • Bei der Caesar-Verschlüsselung werden Buchstaben ersetzt. Was passiert hier stattdessen?
  • Schauen wir uns ein Beispiel an. Was würde mit ‘ABC’ passieren, wenn wir die Positionen wie folgt tauschen: Position 0→2, 1→0, 2→1?

Durchspielen am Beispiel

An der Tafel: “HELLOWORLD” mit Key “201”. Aus der Aufgabenstellung: Der Permutationsschlüssel “201” bedeutet: Position 0 geht nach 2, Position 1 geht nach 0, Position 2 geht nach 1.

1. String aufteilen:
   HEL | LOW | ORL | D??

2. Was bedeutet Key "201"?
   0 → 2
   1 → 0 
   2 → 1

3. Ersten Block permutieren:
   H E L    Position:  0 1 2
   ↓ ↓ ↓    
   E L H    Neue Pos:  2 0 1

Phase 2: Grundgerüst implementieren

Start mit einfachem Programm 

#include <cs50.h>
#include <stdio.h>
#include <string.h>

int main(int argc, string argv[])
{
    if (argc != 2)
    {
        printf("Usage: ./permute text\n");
        return 1;
    }

    string text = argv[1];
    printf("Input text: %s\n", text);
    
    return 0;
}

Fragen:

  • Was brauchen wir als nächstes? Wie können wir den Text in Blöcke aufteilen?
  • Welche Konstante sollten wir definieren?
  • Wie können wir durch den Text in 3er-Schritten iterieren?

Pseudocode: Blockweise iterieren 

SIZE = 3

// Einstieg: Erstmal nur Blocks ausgeben
FÜR Position = 0 BIS Textlänge SCHRITTWEITE SIZE:
    AUSGABE "Block beginnt bei Position", Position
    FÜR j = 0 BIS SIZE:
        AUSGABE Text[Position + j]
    AUSGABE " | "

Erste Erweiterung 

#define BLOCK_SIZE 3

int main(int argc, string argv[])
{
    if (argc != 2)
    {
        printf("Usage: ./permute text\n");
        return 1;
    }
    
    printf("Blocks: ");
    for (int i = 0; i < strlen(text); i += BLOCK_SIZE)
    {
        // Jeden Block ausgeben
        for (int j = 0; j < BLOCK_SIZE; j++)
        {
            printf("%c", text[i + j]);
        }
        printf(" | ");
    }
    printf("\n");
}

Soweit so gut.

Nehmen wir an, wir hätten eine Funktion, die einen Block verarbeitet: VERARBEITE Block.

Dann wäre es gut, wenn wir beim Iterieren etwas hätten, das den aktuellen Block enthält, also so:

// Verbesserung: Mit Array für jeden Block
FÜR Position = 0 BIS Textlänge SCHRITTWEITE SIZE:
    ERSTELLE Block[SIZE]  // Temporäres Array für aktuellen Block
    FÜR j = 0 BIS SIZE:
        Block[j] = Text[Position + j]
    
    VERARBEITE Block
    AUSGABE Block

Die Block-Extraktion lagern wir am besten in eine Funktion aus.

Phase 3: Block-Extraktion

Aufgabe

Schreiben Sie eine Funktion, die einen einzelnen Block in ein char-Array kopiert:

  • Der Block beginnt bei Position start im Text.
  • Er soll BLOCK_SIZE Zeichen lang sein.
  • Verwenden Sie ein char-Array als Parameter für den erstellten Block.
  • Die Funktion gibt nichts zurück.

Besprechung der Lösung 

void extract_block(string text, int start, char block[])
{
    for (int j = 0; j < BLOCK_SIZE; j++)
    {
        block[j] = text[start + j];
    }
}

Diskussionsfragen:

  • Warum verwenden wir char[] statt string?
  • Was könnte schiefgehen, wenn der Text zu kurz ist?
  • Wie können wir das prüfen?

Phase 4: Permutation implementieren

Implementierung 

// Einfache Variante: Hart kodiert für Key "201"
EINGABE: Block[BLOCK_SIZE]

ERSTELLE Temp[BLOCK_SIZE]     // Warum brauchen wir das?
Temp[2] = Block[0]   // 0 geht nach 2
Temp[0] = Block[1]   // 1 geht nach 0
Temp[1] = Block[2]   // 2 geht nach 1

KOPIERE Temp zurück nach Block

oder in C:

// Erstmal mit festem Key "201" testen
void permute_block(char block[])
{
    char temp[BLOCK_SIZE];
    
    // Position 0 geht nach 2
    temp[2] = block[0];
    
    // Position 1 geht nach 0
    temp[0] = block[1];
    
    // Position 2 geht nach 1
    temp[1] = block[2];
    
    // Zurückkopieren
    for (int i = 0; i < BLOCK_SIZE; i++)
    {
        block[i] = temp[i];
    }
}

Fragen zur Verbesserung:

  • Was ist problematisch an diesem Code?
  • Wie könnten wir den Key flexibel machen?
  • Warum brauchen wir temp[]?

Aufgabe

Erweitern Sie die Funktion so, dass sie einen Key als int-Array akzeptiert und diesen nutzt:

void permute_block(char block[], int key[])

Tipp: key[i] gibt an, wohin Position i gehen soll"

EINGABE: Block[BLOCK_SIZE], Key[BLOCK_SIZE]

ERSTELLE Temp[BLOCK_SIZE]
FÜR i = 0 BIS BLOCK_SIZE:
    Temp[ Key[i] ] = Block[i]   // Position i geht nach Position Key[i]

KOPIERE Temp zurück nach Block

oder in C:

void permute_block(char block[], int key[])
{
    char temp[BLOCK_SIZE];
    for (int i = 0; i < BLOCK_SIZE; i++)
    {
        temp[key[i]] = block[i];
    }
    for (int i = 0; i < BLOCK_SIZE; i++)
    {
        block[i] = temp[i];
    }
}

Phase 5: Key-Validierung

Analyse

  • Welche Bedingungen muss ein gültiger Key erfüllen?
  • Was passiert bei ungültigen Keys wie ‘011’ oder ‘234’?

Implementation der Validierung 

// Nur Grundprüfung
WENN Keylänge ≠ BLOCK_SIZE:
    FEHLER "Key muss Länge 3 haben"

FÜR JEDE Ziffer IN Key:
    WENN Ziffer < 0 ODER Ziffer ≥ BLOCK_SIZE:
        FEHLER "Ungültige Ziffer im Key"

Das reicht aber noch nicht.

011 ist keine gültige Permutation, 510 auch nicht.

// Weitere Prüfungen
ERSTELLE Used[BLOCK_SIZE] = {0,0,0}  // Zähler für jede Position

FÜR JEDE Ziffer IN Key:
    WENN Ziffer < 0 ODER Ziffer ≥ BLOCK_SIZE:
        FEHLER "Ungültige Ziffer"
    Used[Ziffer]++

FÜR i = 0 BIS BLOCK_SIZE:
    WENN Used[i] ≠ 1:
        FEHLER "Jede Position muss genau einmal vorkommen"

Also in C:

bool is_valid_key(string key_str)
{
    // Längenkontrolle
    if (strlen(key_str) != BLOCK_SIZE)
    {
        return false;
    }
    
    // Array für Positionszählung
    int used[BLOCK_SIZE] = {0};
    
    // Jeden Key-Character prüfen
    for (int i = 0; i < BLOCK_SIZE; i++)
    {
        // Ist es eine gültige Ziffer?
        if (key_str[i] < '0' || key_str[i] >= '0' + BLOCK_SIZE)
        {
            return false;
        }
        
        // Position markieren
        int pos = key_str[i] - '0';
        used[pos]++;
    }
    
    // Jede Position genau einmal?
    for (int i = 0; i < BLOCK_SIZE; i++)
    {
        if (used[i] != 1)
        {
            return false;
        }
    }
    
    return true;
}

Verständnisfragen

  • Warum subtrahieren wir ‘0’ von key_str[i]?
  • Was bedeutet used[pos]++?
  • Wie prüfen wir, ob jede Position genau einmal vorkommt?

Phase 6: Integration

Finale Version demonstrieren

Was passiert, wenn man einen Text übergibt, der 4 Zeichen lang ist?

Wie verhindern wir das?

// Text-Länge prüfen
WENN Textlänge % BLOCK_SIZE ≠ 0:
    FEHLER "Textlänge muss durch BLOCK_SIZE teilbar sein"

bzw. in C:

int main(int argc, string argv[])
{
    if (argc != 3)
    {
        printf("Usage: ./permute key text\n");
        return 1;
    }

    string key_str = argv[1];
    string text = argv[2];
    
    if (!is_valid_key(key_str))
    {
        printf("Invalid key\n");
        return 1;
    }
    
    if (strlen(text) % BLOCK_SIZE != 0)
    {
        printf("Text length must be multiple of %i\n", BLOCK_SIZE);
        return 1;
    }

    // Key-String in int-Array konvertieren
    int key[BLOCK_SIZE];
    for (int i = 0; i < BLOCK_SIZE; i++)
    {
        key[i] = key_str[i] - '0';
    }
    
    // Text blockweise verarbeiten
    printf("Output: ");
    for (int i = 0; i < strlen(text); i += BLOCK_SIZE)
    {
        char block[BLOCK_SIZE];
        extract_block(text, i, block);
        permute_block(block, key);
        
        // Block ausgeben
        for (int j = 0; j < BLOCK_SIZE; j++)
        {
            printf("%c", block[j]);
        }
    }
    printf("\n");
}

Ideen für weitere Aufgaben zum Üben

  1. Wie würden wir die Entschlüsselung implementieren?
  2. Was müsste sich ändern für variable Blocklängen? (erst wenn wir dynamische Speicherverwaltung behandelt haben)
  3. Wie könnten wir mit Texten umgehen, deren Länge kein Vielfaches von BLOCK_SIZE ist?

Debugging-Tipps

  • Nach kleinen Änderungen Kompilieren, um Fehlersuche zu beschleunigen
  • Printf nach jedem Schritt für Zwischenergebnisse
  • Kleine Testfälle wie “ABC” mit Key “201”
  • Systematisches Testen der Randfälle:
    • Zu kurzer Text
    • Ungültige Keys
    • Spezielle Zeichen im Text

Testfälle

Textlänge nicht teilbar durch 3

./permute 201 HELL

Ungültige Keys

./permute 011 HELLOWORLD  // Ziffer doppelt
./permute 234 HELLOWORLD  // Ziffer zu groß
./permute 21  HELLOWORLD  // Key zu kurz`

Spezialfälle

./permute 201 ""         // Leerer Text
./permute 201 "ABC"      // Minimale Länge
./permute 201 "ABCDEF"   // Mehrere Blöcke`
Block-Cipher (Lösung)