Z pogranicza

Szyfry monoalfabetyczne

  • 2007-12-16 21:26
  • 9 komentarzy
  • 3332 odsłony
  • Oceń ten tekst jako pierwszy
<center>

RODZAJE SZYFRÓW MONOALFABETYCZNYCH

</center>

Szyfry monoalfabetyczne są najprostszymi sposobami szyfrowania danych. Ogólna zasada szyfrów monoalfabetycznych polega na zastępowaniu jakiegoś znaku zawsze na odpowiadający mu według tablicy naszego szyfru.


Najprostszym i najstarszym przykładem takiego szyfru jest dość znany szyfr Cezara, w którym każdą z liter zamieniamy na literę położoną o 3 pozycje dalej w alfabecie. Więc tak zaszyfrowane słowo "mamut" będzie miało formę "pdpxw".  Bardziej ogólnie ten typ szyfru nazywa się ROT-k, w którym k stanowi liczbę o którą przesuwamy litery w alfabecie, więc szyfr Cezara można nazwać ROT-3 (i tu mam problem, bo według niektórych książek Szyfr Cezara  to ROT-13, a nie ROT-3). W naszym wypadku można przyjąć, że liczba k (ta o którą przesuwamy litery) jest rodzajem klucza rozszyfrowującego.


Kolejnym ulepszeniem tego rodzaju szyfrów jest przyporządkowywanie każdemu znakowi testu źródłowego pewnego innego znaku z tablicy szyfrowej. Przykładową tablicą może być np.. (dla liter)


a b c d e f g h i j k l m n o p q r s t u v w x y z

q w e r t y u i o p a s d f g h j k l z x c v b n m


Systemy tego typu nazywa się czasami ogólnie podstawieniem monoalfabetycznym. Kluczem jest w tym wypadku ciąg 26 (oczywiście dotyczy to języka angielskiego) liter odpowiadający zaszyfrowanej postaci całego alfabetu. Przy zastosowaniu powyższego klucza słowo "mamut", zostanie zaszyfrowane jako "dqdxe".





<center>

SPOSOBY ROZSZYFROWYWANIA

</center>

Opiszę tu dwa sposoby na rozszyfrowywanie szyfrów monoalfabetycznych, do obu jednak jest potrzebna jakaś ilość zaszyfrowanych tekstów, a im dłuższych tym lepiej.


Pierwszy sposób opiera się na tym, że w naszym języku pewne litery występują częściej niż inne. Na przykłada w j. angielskim (nie udało mi się znaleźć polskich danych) najczęstszą występującą literą jest e, następne w kolejności są
t, o, a, n, i, r, s, h, d, l, c, f, u, m, p, y, w, g, b, v, k, x, j, q i z, najczęściej występującymi digramami są : th, in, er, re, an, he, ar, en, ti, te, at, on, ha , ou, it, es, st, or, nt, hi, ea, ve, co, de, ra, ro, a najczęstszymi trigramami są: the, ing, and, ion, ent, for, tio, ere, her, ate, ver, ter, tha, ati, hat, ers, his, res, ill, are, con, nce, all, eve, ith, ted
(dane z różnych książek o matematyce). Aby więc rozszyfrować szyfr należy obliczyć średnią częstość występowania znaków (stąd najlepiej mieć sporo tekstu zaszyfrowanego, wtedy jest dokładniejszy pomiar). Zakładamy więc teraz hipotezę (przyjmujemy oczywiście, że tekst został napisany po angielsku), że najczęściej występującą literą jest jest e, a kolejną t. Teraz należy wyszukać najczęściej występujący trigram występujący w postaci tXe i możemy przyjąć, że literą X jest h. Postępując dalej według tego wzorca można w końcu rozszyfrować cały dokument.



Drugim sposobem na rozszyfrowywanie szyfru monoalfabetycznego może być zgadywanie znaczenia wyrazów i fraz. Na przykład jeśli zaszyfrowany tekst jest informacją techniczną firmy elektronicznej, możemy się spodziewać, że wystąpi tam wyraz "elektryczny". Możemy łatwo stwierdzić, że pierwsza i druga litera jest taka sama, a 7 i ostatnia też są takie same. Teraz wyszukujemy w teksie frazy X?X???Y???Y. Jeśli znajdziemy taką frazę możemy dalej się upewniać, czy jest to właśnie to, a  później na tej podstawie (i tym sposobem) dalej rozszyfrowywać cały tekst.  







[DODATEK]
CZĘSTOTLIWOŚĆ (PRAWDOPODOBIEŃSTWO) WYSTĘPOWANIA LITER W JĘZYKU POLSKIM:

(Dane zebrane przy pomocy mojego programu na tekscie liczącym 294256 samych liter i odstępów. Z tego powodu nie mogę zagwarantować 100% poprawności tych danych.)


A-0,07505710</font>

I-0,07251509</font>

R-0,03533318</font>

Ą-0,01022919</font>

J-0,01795036</font>

S-0,03422530</font>

B-0,01344068</font>

K-0,02663327</font>

Ś-0,00736094</font>

C-0,03224403</font>

L-0,01870140</font>

T-0,03345386</font>

Ć-0,00484952</font>

Ł-0,02248042</font>

U-0,01897667</font>

D-0,02822372</font>

M-0,02515837</font>

V-0,00042480</font>

E-0,06543622</font>

N-0,04647314</font>

W-0,03707656</font>

Ę-0,01081371</font>

Ń-0,00100593</font>

X-0,00013594</font>

F-0,00183854</font>

O-0,06363846</font>

Y-0,03364417</font>

G-0,01223085</font>

Ó-0,00616470</font>

Z-0,05051044</font>

H-0,00823093</font>

P-0,02662308</font>

_-0,15023993</font>

ż-0,00787070ź-0,00076124 

</font>
_-0,15023993 - to poprostu odstęp






[DODATEK]
PRZYKŁAD (de)KODERA ALGORYTMU ROT-13 W BCB:

void__fastcallTForm1::Button1Click(TObject*Sender)
{
    Stringtext = Edit1->Text;
    Stringtab1="ABCDEFGHIJKLMabcdefghijklm";
    Stringtab2="NOPQRSTUVWXYZnopqrstuvwxyz";
 
    for(inti=1;i<text.Length()+1;i++)
    {
        booljest=false;
 
        for(intj=1;j<tab1.Length();j++)
        {
            if(text.SubString(i,1)==tab1.SubString(j,1))
            {
                jest=true;
                text=text.delete(i,1);
                text=text.Insert(tab2.SubString(j,1),i);
                break;
            }
       }
 
       if(jest==false)
 
           for(intj=1;j<tab2.Length();j++)
          {
              if(text.SubString(i,1)==tab2.SubString(j,1))
              {
                  text=text.delete(i,1);
                  text=text.Insert(tab1.SubString(j,1),i);
                  break;
              }
          }
    }
 
    Edit1->Text=text;
 
}

9 komentarzy

Koziołek 2007-12-18 13:50

Do rozkładu, prawdopodobieństwo pomyłki liczone w najprostszy sposób czyli pierwiastek z liczby prób to 0.00184347536% zatem jest nieźle.

flabra 2003-11-07 20:37

Krecik ma napisane w swych danych 15 lat. Wiem, że wiekszość kłamie, nie pisze nic albo pisze bzdury (hehe), ale Jemu jestem w stanie uwierzyć. Więc proszę Cię Kapustka, nie namawiaj do picia młodzierzy.

Kapustka 2003-11-03 13:42

Jak ktoś na tym forum zapowiada, że napisze o kombinatoryce, to po kilku dniach znika z powierzchni wyznaczonej przez trzy punkty: gg, email,4p. Podejrzana to sprawa i dochodzenie jest w toku (aktualna poszlaka to: zrozpaczeni wobec niemocy napisania artu do którego się zobowiązali zaszywają się i nie przestają pić przez 5 tygodni)

Mam nadzieję że, drogi Kreciku, nie znikniesz z tej powierzchni, bo artykuł napisałeś ciekawy i twoje zniknięcie byłoby niepowetowaną stratą zarówno dla 4p jak i twojej wątroby.

Gorąco Pozdrawiam.

Krecik 2003-11-02 14:51

Najbliższy będzie albo o szyfrach polialfabetycznych albo o przestawieniowych...

Albo w ogóle o kombinatoryce...

Dryobates 2003-11-02 11:30

1. ROT-3 - szyfr Cezara, ROT-13 to kompletnie inny szyfr. Cechą tego drugiego jest to, że dwukrotne jego użycie (alfabet łaciński) powoduje rozszyfrowanie tekstu (czyli szyfruje się tą samą procedurą co deszyfruje)
2. W języku polskim: http://www.ceti.pl/poleng/zasoby/dane/tstat/

Marooned 2003-11-02 01:27

To chyba pierwszy art w całym serwisie, który jest interesujący (dla mnie) - bez urazy dla innych autorów. Choć część tych informacji znałem wcześniej. Jak wstanę, to go przeczytam w całości. :)

my_nick 2003-11-02 13:47

Jesli chodzi o ROT-k  dla alfabetu polskiego - to by było chyba ROT-17? Problem tylko w tym, jak poukładać tablicę konwersji:

1. AĄBCĆ....XYZŻŹ
2. ABC...XYZĄĆĘ...

I co zrobić z X i Q? Moim zdaniem najlepiej by wyszła pierwsza tablica, z X i Q włącznie.
Dalej: ROT-k dla cyfr (często liczby są ważną informacją którą trzeba zaszyfrować). Można zrobić proste ROT-10 dla każdej pojedyńczej cyfry, ale dla lepszego efektu dałoby się użyć np. osoblego k dla jedności, dziesiątek, setek itp. po czym odkodowanie następowałoby według klucza 10-k. Oczywiście dałoby się łatwo odgadnąć klucze - np. wiedząc, że tekst traktuje o II wojnie światowej, trzeba znaleźć czterocyfrową liczbę i kombinować z nią tak, żeby wyszło 1939 po czym można rozszyfrowywać dalsze liczby (w ten sposób, po datach, Anglicy dekodowali szyfrowane m.in. ROTem liczbowym depesze niemieckie podczas wojny).
PS. Jak będziesz pisać o szyfrowaniu jednostronnym, mogę ci podrzucić mój wynalazek w tej dziedzinie, zaprojektowany do haseł jednostronnych, praktycznie niemożliwy do rozszyfrowania. (Żeby nie było, że się chwalę: wady też ma. Ale działa. :)).

PS2. Adam, zwiększ to cholerne okienko do pisania komentarzy! ;)

lofix 2003-11-02 00:01

ja proponuje (jako laik) jakies przyklady w C lub paszczaku

Krecik 2003-11-02 00:14

Starczy? Niczego innego nie mam na stanie :) [to by było akurat podstawienie monoalfabetyczne]

Ale mogę napisać algorytm ROT-k, ze zmiennym k... Jutro siądę...