Szyfry polialfabetyczne (lub wieloalfabetyczne)

Krecik

2003-11-21 22:52:19
2003-11-21 22:52:19
3 komentarze
5592 odsłony

SZYFRY POLIALFABETYCZNE (wieloalfabetyczne)

Aby utrudnić zadanie kryptologom należy wyrównać częstość występowania znaków i ich sekwencji. Cel ten można osiągną między innymi stosując cyklicznie wiele alfabetów szyfrujących. Powstaje w ten sposób tzw. Szyfr polialfabetyczny (lub wieloalfabetyczny). Jako przykład rozważmy tu algorytm szyfru Vigenera (nie dokładnie, ale na nim oparty). Tablica (pole?) robocze tego szyfru ma 'kształt' kwadratu (w długości zależnej od języka) np. 26x26 (jeżeli chcielibyśmy go ujednolicić dla wszystkich języków będzie to 256x256 - tablica ASCII) i zawiera pewną liczbę (dla angielskiego 26) szyfrów monoalfabetycznych (np. ROT-1). I weźmy na przykład tablicę dla znaków języka angielskiego. Pierwszy wiersz, tzw. wiersz A zawiera litery zapisane w kolejności ABCD...WXYZ. Wiersz następny B zawiera np. BCDE...XYZA. Ostatni wiersz takiej tablicy - wiersz Z zawiera ZABC...VWXY. (Ilustracja tekiej tablicy na końcu artykułu). Podobnie jak szyfr monoalfabetyczny, również szyfr Vigenera ma klucz. Nie jest to jednak ciąg 26 różnych znaków, lecz zazwyczaj krótkie, łatwe do zapamiętania słowo, bądź fraza, np: PREHISTORIA. Aby zaszyfrować daną wiadomość, wpisujemy cyklicznie litery klucza ponad kolejnymi znakami tekstu źródłowego (jest to tylko ilustracja, mająca ułatwić zrozumienie tematu), w taki sposób:

<tt>P R E H I S T O R I A P R E H I S T O R
m a m u t y w y g i n e l y b a r d z o

I A P R E H I S T  ...
d a w n o t e m u  ...</tt>

(pominąłem tu znak ' ' w celu ułatwienia sobie zadania :) )
Litera klucza zapisana nad literą tekstu jawnego (źródłowego) określa, według którego wiersza (lub kolumny - bez różnicy) tablicy należy ją zaszyfrować. I tek: literę m szyfrujemy według wiersza P, literę a według wiersza R, kolejną literę m według wiersza E i tak dalej... Zatem te same litery tekstu źródłowego będą zależne od ich położenia w tym tekście (czyli: litera a może raz zostać zaszyfrowana jak np. c, a raz jako np. f). Podobnie di- i tri- gramy będą rozbite, przez zastępowanie ich różnymi sekwencjami znaków.
Jeszcze trudniejszy do złamania szyfr uzyskujemy używając dla wierszy tablicy dowolnie wybranych szyfrów monoalfabetycznych, nie ograniczając się do jednego (np. szyfru Cezara). Jedynym problemem jest wtedy to, że wspomniana wyżej tablica 26 znaków jest częścią składową klucza szyfru i musiałaby być przechowywana i trzeba ją przechowywać na użytek każdego szyfranta osobno.

SPOSOBY ROZSZYFROWYWANIA

Szyfr wieloalfabetyczny, mimo że bezsprzecznie lepszy do monalafabetycznego, również można łatwo złamać, i to w trybie braku wzorca. Warunkiem jest posiadanie dość sporej liczby tekstów zaszyfrowanych. Podstawą rozwiązania problemu jest odgadnięcie długości klucza użytego do zaszyfrowania. Rozpoczynać pracę kryptolog zakłada, że klucz ma długość k. Następnie formujemy te teksty w wierszo o długości k każdy. Jeśli założono dobrą długość k to kolejne litery kolejnych wierszy będą zaszyfrowane według tego samego. Powinny one mieć wówczas taki sam rozkład częstotliwości występowania znaków jak język normalny (niezaszyfrowany). Zdecydowany brak takich prawidłowości będzie znaczył, że źle obraliśmy wielkość k. Kiedy już zaobserwujemy ową prawidłowość, wówczas tekst w każdej kolumnie rozszyfrowujemy używając metod służących do odczytania szyfrów monoalfabetycznych.

PS> METODA KLUCZA NIEPRZEŁAMYWALNEGO</span>

Kolejnym utrudnieniem dla starającego się rozszyfrować nasz szyfr ( :) ) jest zastosowanie klucza dłuższego niż szyfrowany tekst. Sprawia to, że omówiona metoda staje się praktycznie bezużyteczna. Konstrukcja szyfru nieprzełamywalnego jest w zasadzie łatwa. Należy ustalić określony łańcuch bitów jako klucz. Następnie tekst jawny przekształcamy również na ciąg bitów (korzystając z kodu ASCII). Końcowym krokiem jest obliczenie funkcji XOR obu powyższych ciągów i utworzenie wynikowego ciągu bitów. Wynikowy tekst zaszyfrowany nie może być odczytany, ponieważ każdy tekst jawny jest jednakowo prawdopodobny. Kryptogram taki nie daje kryptologowi żadnych informacji. Metoda ta, zwana metodą klucza jednorazowego ma jednak jedną dużą wadę. Klucza nie da się zapamiętać. Nadawca i odbiorca muszą zatem mieć jego wzór na piśmie. Poza tym objętość szyfrowanego tekstu jest ograniczona długością stosowanego klucza.

[DODATEK]

Wzmiankowana w tekscie tablica ilustrująca szyfr algorytmem Vigenera dla języka angielskiego. (Musiałem sobie do napisania tego program napisać:) )

</table>

[DODATEK]

FUNKCJA SZYFROWANIA:


char *text = "ALAMAZIELONEGOKOTA";
char *pass = "ABCDEF";

//tworzenie 'tablicy szyfru':
char *tablica = "ABCDEFGHIJKLMNOPQRSTUWXYZ";
char *tab;
tab = new char [strlen(tablica)];
for(int i=0; i<strlen(tablica); i++)
tab[i] = new char[strlen(tablica)];

//wypełnianie tej tablicy szyfrem wg. algorytmu Vigenera (trochę mało konomiczny sposób, bo własny):
int pos=0;
for(int i=0; i<strlen(tablica); i++)
{
for(short int j=0; j<strlen(tablica)+1; j++)
{
int ps = pos+j;
if(ps>strlen(tablica))
{
ps = ps-strlen(tablica);
}
tab[i][j]=tablica[ps];
}
pos++;
}
//SZYFROWANIE:
for(int i=0; i<strlen(text); i++)
{
//znak szyfrowany:
char znak = text[i];
//znak szyfrujący:
int rest = i%strlen(pass);
char pchr = pass[rest];

    //szukanie litery zaszyfrowanej:
    //szuaknie wiersza według którego będziemy szyfrować:
    int wiersz = 0;
    for(int k=0; k<strlen(tablica); k++)
        {
        if(tab[0][k]==pchr)
            {
            wiersz = k;
            break;
            }
        }
    //i zanjdujemy literę zaszyfrowaną:
    int kolumna = 0;
    for(int k=0; k<strlen(tablica); k++)
        {
        if(tab[k][0]==znak)
            {
            kolumna = k;
            break;
            }
        }
    //tu już nie miałem siły truć się char`em: :)
    Edit2->Text = Edit2->Text + tab[kolumna][wiersz];
    }

for (int i = 0; i < strlen(tablica); i++)
delete[] tab[i];
delete[] tab;

<br>
<br>
2. FYNKCJA DESZYFROWANIA:
```cpp
char *text = "AMCPEEIFNRRJGPMRYF";
char *pass = "ABCDEF";

//tworzenie 'tablicy szyfru':
char *tablica = "ABCDEFGHIJKLMNOPQRSTUWXYZ";
char **tab;
tab = new char *[strlen(tablica)];
for(int i=0; i<strlen(tablica); i++)
    tab[i] = new char[strlen(tablica)];

//wypełnianie tej tablicy szyfrem wg. algorytmu Vigenera (trochę mało konomiczny sposób, bo własny):
int pos=0;
for(int i=0; i<strlen(tablica); i++)
        {
        for(short int j=0; j<strlen(tablica)+1; j++)
                {
                int ps = pos+j;
                if(ps>strlen(tablica))
                    {
                    ps = ps-strlen(tablica);
                    }
                tab[i][j]=tablica[ps];
                }
        pos++;
        }

//DESZYFROWANIE:
for(int i=0; i<strlen(text); i++)
        {
        //znak szyfrowany:
        char znak = text[i];
        //znak szyfrujący:
        int rest = i%strlen(pass);
        char pchr = pass[rest];

        //szukanie litery zaszyfrowanej:
        int wiersz = 0;
        for(int k=0; k<strlen(tablica); k++)
            {
            if(tab[0][k]==pchr)
                {
                wiersz = k;
                break;
                }
            }
        int kolumna = 0;
        for(int k=0; k<strlen(tablica); k++)
            {
            if(tab[k][wiersz]==znak)
                {
                kolumna = k;
                break;
                }
            }
        //brakło sił do char:
        Edit2->Text = Edit2->Text + tab[kolumna][0];
        }

for (int i = 0; i < strlen(tablica);  i++)
    delete[] tab[i];
delete[] tab;

PS> po czymś takim, człowiek zaczyna rozumieć po co jest AnsiString :)