Galerija

Mašina Enigma u kućnoj radinosti, deo 3

Evo nas i u trećem delu, konačno ću progovoriti o samom unutrašnjem mehanizmu mašine Enigme i načinu kako sam napisao računarski simulator po originalnom elektromehaničkom dizajnu.

Mašina Enigma, kao što smo videli u prvom delu je kripto mašina sa simetričnim ključem. Odnosno ako unesemo neki znak A, proizvešće po složenim pravilima neki znak X, ali zato će, potpuno simetrično, ako unesemo znak X izaći ponovo znak A. Zvuči banalno, na prvi pogled izgleda isto kao i Cezarov disk za zamenu slova, koju bi danas i osnovac mogao da provali čak i bez znanja šifre. Ali stvar uopšte nije tako jednostavna. Naime, srce mehaničkog sklopa predstavljaju 3 valjka koji svaki put kada unesete neki simbol, oni se okrenu za jedan korak. I to čine po sistemu starih kasetofona koji su brojali obrtaje. Kada prvi valjak ili rotor stigne do zadnjeg slova, što je uvom slučaju abecedno slovo Z, onda se za jedan pomeri i sledeći valjak u nizu, na kraju kada se dođe do pozicije ZZZ, sva tri valjka će se vratiti na početni položaj AAA. Ta činjenica čini sistem neuporedivo sigurnijim od Cezarovog diska jer svaki put kada unesete slovo, stanje u mašini se menja. Tako da ako biste uneli 10 puta za redom slovo A, na izlazu bi bilo 10 različitih slova, a nikako jedan te isti.

1. Baterija 2. Taster 3. Zamenjivač slova prvi put 4. Ulazak u 3 valjka 5. Prolazak kroz 3 valjka 6. Simetrični reflektor 7.  8. Zamenjivač slova, drugi put 9. Lampica

1. Baterija
2. Taster
3. Zamenjivač slova prvi put
4. Ulazak u 3 valjka
5. Prolazak kroz 3 valjka
6. Simetrični reflektor
7.
8. Zamenjivač slova, drugi put
9. Lampica

Dakle AAAAAAAAAA bi se presikalo u, na primer, HUEMQPILCW. I onda ako biste vratili valjke u početni položaj i otkucali HUEMQPILCW, mašina bi izbacila AAAAAAAAAA. Zaista zvuči magično. I jeste. Razlog zašto su Nemci verovali da su njihove tajne sigurne je zato što ovaj mehanizam otežava napad preko praćenja frekvencije slova. Kako ima 3 valjka i 26 simbola na svakom, stanje u mašini se vraća u početni položaj tek nakon 26^3 = 17576 slova. Kako, rekao bih, ni jedna poruka ikada šifrovana ovim sistemom nije prešla tu dužinu, veoma je teško meriti ikakve frekvencije ponavljanja znakova. Praktično, nema ponavljanja. Svako slovo se preslikava svaki put u neko drugo slovo, nikada u isto. No, ni svemu tome nije kraj, možda se mašina ne može napasti merenjem frekvencije pojavljivanja slova, ali ipak 18 hiljada je veoma mali broj kombinacija, čak i za ono vreme 30-tih godina prošlog veka, to bi se lako dalo provaliti silom mehaničkim računarima, tako što bi se probale sve kombinacije. Zato, osim 3 valjka, Enigma ima i zamenjivač slova. Radi se o pločici na prednjoj strani ispod tastature koja ima 26 parova konektora, par za svako slovo abecede. Uz mašinu je išlo najpre šest, a kasnije deset kablova. Svaki od tih kablova bi premostio slova, tako da bi A išlo recimo u M, F u D, i tako dalje. To je dodalo oko 150 triliona drugih kombinacija, da bi isklučilo napad slepom silom.

Za korisnika, na kraju lozinka, je sačinjena od 3 slova za valjkove, po 1 slovo za svaki valjak i 10 parova slova za kablove za zamenu slova. Sve ukupno 23 slova. Bilo je tu još nekih komplikacija, ali nećemo ulaziti dalje u detalje.

Kako je mašina omogućavala simetričnost? U shemi aparata možete videti, da je Enigma električna mašina. Kada se pritisne neki taster, zatvori se električno kolo koje spaja bateriju za lampicu. Lampica zasvetli ispod slova u koji se originalno slovo preslikava. Taster je najpre spojen za zamenjivač slova i tu se dogodi prva zamena. Zatim žica vodi do prvog valjka, koji je u svojoj unutrašnjosti fiksni zamenjivač slova, i tu se dogodi druga zamena. Tako se desi 3 puta kroz sva 3 valjka, valjak 1, pa 2 pa 3. Zatim sledi ključni deo mašine, koji se zove reflektor ili ogledalo, odnosno simetrični povezivač slova, koji uvek povezuje slova na simetričan način, dakle ako A ide u M, M uvek ide u A, ako B ide u F, F uvek ide u B. Reflektor je baza čitavog sistema i omogućava da se poruka može dešifrovati istom onom kombinacijom kojom je šifrovana. Nakon reflektora, žice opet prolaze nazad kroz valjak 3, pa 2, pa 1, pa onda opet kroz zamenjivač slova ispod tastature i na kraju dođe do lampice. Nakon što lampica zasvetli i taster se pusti, valjci škljocnu jedan korak unapred. Dakle, slovo od tastera do lampice u svakom koraku se zameni 9 puta. I to je to, tako radi cela mašina.

Program koji sam uradio je napisan u programskom jeziku C++ i pisan je da apsolutno emulira mehaničko električne mehanizme da bolje ilustruje princip rada. Kako sam program napisao na opšti način, lako možete podesiti broj slova koji u početnom stanju radi sa 26 slova, a vi možete povećavati sve do 255 ako to želite. Uz to i početni broj valjaka je 3, kao u originalnom dizajnu, ali i to se može povećati na proizvoljan broj. I broj kablova za zamenu slova na prednjem panelu možete povećavati. Uz te 3 promene, broj kombinacija se penje vrtoglavom brzinom, tako da ubrzo može da premaši broj atoma u svemiru. Nema tog kompjutera danas koji bi to mogao da provali slepom silom, ali kako ćemo videti u sledećem prilogu, Tjuring i nije koristio slepu silu za razbijanje, već kombinaciju nekih teorijskih nedostataka mašine koje do sada nisam spominjao i relativno malu slepu silu.

Šifre su se nalazile u posebnim knjigama i važile su samo jedan dan. Bile su štampane na papiru koji se lako rastvara u vodi

Šifre su se nalazile u posebnim knjigama i važile su samo jedan dan. Bile su štampane na papiru koji se lako rastvara u vodi

Program koristi čak i nazive promenljivih na engleskom jeziku, izvinjavam se na tome, ali to mi je profesionalna deformacija nakon decenija bavljenja informatikom, ali engleski je de fakto jezik programera.

Evo primera. Ako postavimo lozinku kao:

Rotors Start Positions:
TWT

Cable Plugs:
HB
VN
KQ
CX
PT
UO

i ako originalna poruka bude:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
OVOJETESTKORISCENJAKRIPTOMASINEENGIMASASAMODVADESETSESTSLOVACAKIBEZRAZMAKA

onda će šifrovana biti:

ZVKQNXMEGCZFIPTCBEOZZLKYZTPMYNXNHNQYXCEEBLRJD
YCBSKJZZYLGLCETFGIYSTBDAVIHJWLOPXJBUXNDBBBRSXPYCNVWTZTBDMZACLLBPTDVEFQFCWE

i naravno ako ubacite šifrovanu na ulaz, na izlazu će se pojaviti ponovo razumljiva poruka.

Mašina nije 100% verodostojna, jer me je mrzelo da tražim tačna spajanja žica unutar svakog rotora, kao što su bili u originalu, pa sam tako na početku programa stvorio slučajnim brojevima 26 spojeva za svaki valjak. Ako vam je stalo, ima sajtova na kojima se i ta informacija može naći, mada je to potpuno nebitno sa edukativne strane. Naravno, ako želite da koristite mašinu za realno šifrovanje, morate uspostaviti fiksno kablovanje unutar valjkova tako da i pošiljalac i primalac imaju istu napravu. To se lako prepravi u programu, dovoljno je izbacite random deo sa fiksnom inicijalizacijom vektora u funkciji Rotor::init(). Samo lozinka mora biti pokretna.

Obavezno pročitajte i prethodni deo ove priče.

Evo listinga programa u jeziku C++:

#include <iostream>

#define ALPHABET_SIZE 26
#define FIRST_CHAR 'A'
#define NUM_ROTORS 3
#define NUM_CABLES 6

struct Rotor
{
    int RedirectorForward[ALPHABET_SIZE];
    int RedirectorBack[ALPHABET_SIZE];
    int position;

    Rotor()
    {
        init();
    }

    struct pair
    {
        int letter;
        int number;
    };

    void init()
    {
        position=0;

        pair RandomSet[ALPHABET_SIZE];

        bool LetterRemapsToItself;
        do
        {
            LetterRemapsToItself=false;
            for(int i=0;i<ALPHABET_SIZE;i++)
            {
                RandomSet[i].letter=i;
                RandomSet[i].number=rand();
            }
            qsort(RandomSet, ALPHABET_SIZE, sizeof(pair), CompareFun);
            for(int i=0;i<ALPHABET_SIZE;i++)
            {
                if(i==RandomSet[i].letter)
                    LetterRemapsToItself=true;
                RedirectorForward[i]=RandomSet[i].letter;
                RedirectorBack[RandomSet[i].letter]=i;
            }
        }while(LetterRemapsToItself);
    }

    void SetPosition(int position)
    {
        this->position=position;
    }

    int EncodeLetterForward(int letter)
    {
        return RedirectorForward[(position+letter)%ALPHABET_SIZE];
    }

    int EncodeLetterBack(int letter)
    {
        int ret=RedirectorBack[letter]-position;
        if(ret<0)
            ret+=ALPHABET_SIZE;

        return ret%ALPHABET_SIZE;
    }

    int rotate()
    {
        position++;
        if(position==ALPHABET_SIZE)
        {
            position=0;
            return true;
        }
        else
            return false;
    }

private:
    static int CompareFun(const void * a, const void * b)
    {
        pair *aa=(pair *)a;
        pair *bb=(pair *)b;

        return aa->number - bb->number;
    }
};

struct Reflector:public Rotor
{
    Reflector()
    {
        for(int i=0;i<ALPHABET_SIZE;i++)
        {
            RedirectorForward[i]=ALPHABET_SIZE-1-i;
            RedirectorBack[i]=-1;
        }
    }
};

struct Plugboard:public Rotor
{
    Plugboard()
    {
        for(int i=0;i<ALPHABET_SIZE;i++)
        {
            RedirectorForward[i]=i;
            RedirectorBack[i]=i;
        }
    }

    bool AddCable(int letter1, int letter2)
    {
        if(RedirectorForward[letter1]!=letter1 || RedirectorForward[letter2]!=letter2)
            return true;

        RedirectorForward[letter1]=letter2;
        RedirectorForward[letter2]=letter1;

        return false;
    }
};

struct Enigma
{
    Rotor rotors[NUM_ROTORS];
    Reflector reflector;
    Plugboard plugboard;

    void SetRotorPositions(int *p)
    {
        for(int i=0;i<NUM_ROTORS;i++)
            rotors[i].SetPosition(p[i]);
    }

    unsigned char EncodeLetter(unsigned char in)
    {
        int InterLetter=in-FIRST_CHAR;

        InterLetter=plugboard.EncodeLetterForward(InterLetter);

        for(int i=0;i<NUM_ROTORS;i++)
            InterLetter=rotors[i].EncodeLetterForward(InterLetter);

        InterLetter=reflector.EncodeLetterForward(InterLetter);

        for(int i=NUM_ROTORS-1;i>=0;i--)
            InterLetter=rotors[i].EncodeLetterBack(InterLetter);

        InterLetter=plugboard.EncodeLetterForward(InterLetter);

        unsigned char OutLetter=InterLetter+FIRST_CHAR;

        for(int i=0;i<NUM_ROTORS-1;i++)
            if(rotors[i].rotate())
                rotors[i+1].rotate();

        return OutLetter;
    }

    void EncodeString(std::string &in, std::string &out)
    {
        for(size_t i=0;i<in.length();i++)
        {
            unsigned char InLetter=in[i];
            unsigned char OutLetter=EncodeLetter(InLetter);
            out[i]=OutLetter;
        }
    }

    bool AddPlugCable(int letter1, int letter2)
    {
        return plugboard.AddCable(letter1, letter2);
    }
};

void PrintString(std::string &s)
{
    for(int i=0;i<s.length();i++)
    {
        unsigned char c=s[i];
        if(c<' ')
            std::cout << '<';
        else if(c>126)
            std::cout << '>';
        else
            std::cout << c;
    }

    std::cout << std::endl;
}

int main(int argc, char *argv[])
{
    std::string in=
        "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
        "OVOJETESTKORISCENJAKRIPTOMASINEENGIMASASAMODVADESETSESTSLOVACAKIBEZRAZMAKA";

    std::string out1(in.length(), ' ');
    std::string out2(in.length(), ' ');

    Enigma enigma;

    srand(time(NULL));

    int RotorPositions[NUM_ROTORS];
    std::cout << "Rotors Start Positions:" << std::endl;
    for(int i=0;i<NUM_ROTORS;i++)
    {
        RotorPositions[i]=rand()%ALPHABET_SIZE;
        std::cout << (unsigned char)(RotorPositions[i]+FIRST_CHAR);
    }
    std::cout << std::endl;
    std::cout << std::endl;

    std::cout << "Cable Plugs:" << std::endl;
    for(int i=0;i<NUM_CABLES;i++)
    {
        bool AlreadyExists;
        int l1, l2;
        do
        {
            l1=rand()%ALPHABET_SIZE;
            l2=rand()%ALPHABET_SIZE;
            AlreadyExists=enigma.AddPlugCable(l1, l2);
        }while(AlreadyExists);
        std::cout << (unsigned char)(l1+FIRST_CHAR) << (unsigned char)(l2+FIRST_CHAR) << std::endl;
    }
    std::cout << std::endl;

    enigma.SetRotorPositions(RotorPositions);
    enigma.EncodeString(in, out1);
    enigma.SetRotorPositions(RotorPositions);
    enigma.EncodeString(out1, out2);
    PrintString(out2);
    std::cout << std::endl;
    PrintString(out1);
    std::cout << std::endl;

    return 0;
}

Ja pišem vama, a vi meni recite šta mislite. Voleo bih da saznam o…

Advertisements

2 comments on “Mašina Enigma u kućnoj radinosti, deo 3

  1. Povratni ping: Od Eugenetike do Singulariteta | Markus Maki

  2. Povratni ping: Mašina Enigma u kućnoj radinosti, deo 2 | Markus Maki

Zatvoreno za komentare.