Algorytmy tekstowe i szyfrowanie

Czego się dziś nauczysz

Przygotowanie: lekcje 01–29. Przewidywany czas: 45–90 minut z zadaniami. Przykłady wymagają .NET 8 lub nowszego, z włączonymi ImplicitUsings i Nullable.

Szyfr Cezara — przesunięcie w alfabecie

Najstarszy opisany szyfr podstawieniowy: każdą literę zastępujemy literą oddaloną o ustaloną liczbę pozycji. Przy przesunięciu 3 litera A staje się D, a Z wraca na początek i staje się C.

jawny:      A B C D E F G ... X Y Z
zaszyfrowany: D E F G H I J ... A B C
              └──── przesuniecie o 3 ────┘

Z lekcji 07 wiesz, że znak jest liczbą. To wszystko, czego potrzeba: odejmij kod litery 'A', dodaj przesunięcie, weź resztę z dzielenia przez 26 i wróć do litery.

static char PrzesunLitere(char znak, int przesuniecie)
{
    if (!char.IsLetter(znak))
    {
        return znak;                       // cyfry, spacje i kropki zostawiamy
    }

    char baza = char.IsUpper(znak) ? 'A' : 'a';
    int pozycja = znak - baza;             // 0 dla A, 25 dla Z
    int nowa = (pozycja + przesuniecie) % 26;

    if (nowa < 0)
    {
        nowa += 26;                        // dla ujemnego przesuniecia
    }

    return (char)(baza + nowa);
}

Deszyfrowanie to ta sama metoda

Skoro szyfrowanie przesuwa o k, to deszyfrowanie przesuwa o -k. Nie potrzeba drugiej metody — wystarczy zmienić znak argumentu.

string tajne = Zaszyfruj("Atak o swicie", 3);
string jawne  = Zaszyfruj(tajne, -3);

Dlaczego to nie jest zabezpieczenie

Szyfr Cezara ma dokładnie 25 sensownych kluczy. Program, który wypróbuje wszystkie i wypisze wyniki, łamie go w ułamku sekundy — a człowiek rozpoznaje właściwy wariant na pierwszy rzut oka.

for (int klucz = 1; klucz <= 25; klucz++)
{
    Console.WriteLine($"{klucz,2}: {Zaszyfruj(tajne, -klucz)}");
}

To atak siłowy (ang. brute force): sprawdzamy wszystkie możliwości. Działa zawsze, gdy kluczy jest mało.

Szyfr podstawieniowy z dowolnym przestawieniem alfabetu ma już 26! ≈ 4 · 10²⁶ kluczy i atak siłowy przestaje mieć sens. Mimo to też jest łamany — analizą częstości. W polskim tekście litera a występuje najczęściej, w angielskim e. Wystarczy policzyć znaki w szyfrogramie i przypisać najczęstsze do najczęstszych.

Szyfr podstawieniowy i XOR

Dowolne przestawienie alfabetu

Zamiast przesuwać o stałą liczbę, możemy podać cały przestawiony alfabet jako klucz. Litera o pozycji i w alfabecie jawnym zamienia się na znak o pozycji i w kluczu.

const string ALFABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string KLUCZ   = "QWERTYUIOPASDFGHJKLZXCVBNM";

static char Podstaw(char znak, string z, string na)
{
    int i = z.IndexOf(char.ToUpper(znak));

    if (i < 0)
    {
        return znak;               // znak spoza alfabetu zostawiamy
    }

    char wynik = na[i];
    return char.IsLower(znak) ? char.ToLower(wynik) : wynik;
}

Szyfrowanie to Podstaw(znak, ALFABET, KLUCZ), a deszyfrowanie — te same argumenty w odwrotnej kolejności: Podstaw(znak, KLUCZ, ALFABET). Jedna metoda w obie strony.

XOR — szyfr, który jest własną odwrotnością

Operator bitowy ^ z lekcji 10 ma własność, która czyni z niego najprostszy szyfr: (a ^ k) ^ k = a. Ta sama operacja z tym samym kluczem szyfruje i odszyfrowuje.

static string XorHex(string tekst, char klucz)
{
    StringBuilder wynik = new StringBuilder();

    foreach (char znak in tekst)
    {
        int zaszyfrowany = znak ^ klucz;
        wynik.Append(zaszyfrowany.ToString("X2")).Append(' ');
    }

    return wynik.ToString().TrimEnd();
}

Przykład: szyfruj, odszyfruj, złam

using System.Text;

class Program
{
    static char PrzesunLitere(char znak, int przesuniecie)
    {
        if (!char.IsLetter(znak)) return znak;

        char baza = char.IsUpper(znak) ? 'A' : 'a';
        int nowa = (znak - baza + przesuniecie) % 26;
        if (nowa < 0) nowa += 26;

        return (char)(baza + nowa);
    }

    static string Cezar(string tekst, int przesuniecie)
    {
        StringBuilder wynik = new StringBuilder(tekst.Length);

        foreach (char znak in tekst)
        {
            wynik.Append(PrzesunLitere(znak, przesuniecie));
        }

        return wynik.ToString();
    }

    static void Main()
    {
        string jawny = "Spotkanie o 7 rano!";
        string tajny = Cezar(jawny, 3);

        Console.WriteLine($"jawny : {jawny}");
        Console.WriteLine($"tajny : {tajny}");
        Console.WriteLine($"wrocil: {Cezar(tajny, -3)}");
        Console.WriteLine();

        Console.WriteLine("Atak silowy na szyfrogram:");
        for (int klucz = 1; klucz <= 5; klucz++)
        {
            Console.WriteLine($"  klucz {klucz,2}: {Cezar(tajny, -klucz)}");
        }
    }
}

jawny : Spotkanie o 7 rano!
tajny : Vsrwndqlh r 7 udqr!
wrocil: Spotkanie o 7 rano!

Atak silowy na szyfrogram:
  klucz  1: Urqvmcpkg q 7 tcpq!
  klucz  2: Tqpulbojf p 7 sbop!
  klucz  3: Spotkanie o 7 rano!
  klucz  4: Rontjzmhd n 7 qzmn!
  klucz  5: Qnmsiylgc m 7 pylm!

Co dzieje się po kolei

• Cyfra 7, spacje i wykrzyknik przechodzą bez zmian — warunek char.IsLetter odsiewa je na wejściu.
• Wielkość liter jest zachowana, bo bazą jest 'A' albo 'a' zależnie od znaku. Bez tego wielkie litery wypadłyby poza alfabet.
• Przy kluczu ujemnym (znak - baza + przesuniecie) bywa ujemne — poprawka nowa += 26 jest tu jedynym powodem, dla którego deszyfrowanie w ogóle działa.
• StringBuilder z lekcji 29 zamiast sklejania: dla długiego tekstu różnica jest wyraźna, a kod nie jest dłuższy.
• Atak siłowy pokazuje właściwy tekst już przy trzeciej próbie. Tyle jest wart ten szyfr.

Suma kontrolna — wykrywanie błędów, nie ukrywanie

Szyfrowanie ukrywa treść. Suma kontrolna robi coś innego: pozwala wykryć, że dane zostały przekłamane. Spotykasz ją codziennie — w numerze PESEL, NIP, ISBN i numerze konta.

// cyfra kontrolna PESEL: wagi 1,3,7,9,1,3,7,9,1,3
static bool CzyPoprawnyPesel(string pesel)
{
    if (pesel.Length != 11) return false;

    int[] wagi = { 1, 3, 7, 9, 1, 3, 7, 9, 1, 3 };
    int suma = 0;

    for (int i = 0; i < 10; i++)
    {
        if (!char.IsDigit(pesel[i])) return false;

        suma += (pesel[i] - '0') * wagi[i];
    }

    int kontrolna = (10 - suma % 10) % 10;

    return kontrolna == pesel[10] - '0';
}

Zestawienie elementów

Na co uważać

Zadania

Co trzeba zapamiętać

• Szyfr Cezara przesuwa litery o stałą wartość; deszyfrowanie to przesunięcie o tę samą wartość ze znakiem minus.
• W C# % zachowuje znak dzielnej — dla wyniku ujemnego trzeba dodać rozmiar alfabetu.
• Zachowanie wielkości liter wymaga wyboru bazy 'A' albo 'a' dla każdego znaku osobno.
• Cezar ma 25 kluczy i łamie się atakiem siłowym; szyfr podstawieniowy — analizą częstości liter.
• XOR jest własną odwrotnością, dlatego ta sama metoda szyfruje i odszyfrowuje; wynik pokazujemy szesnastkowo.
• Suma kontrolna nie ukrywa danych — pozwala wykryć przekłamanie, jak cyfra kontrolna w numerze PESEL.
• To są ćwiczenia algorytmiczne, nie zabezpieczenia. Prawdziwe dane chroni się gotowymi bibliotekami.

Dokumentacja: Microsoft Learn — temat tej lekcji.