| Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
AL_20_10 - Rejestr |
Do budowy pseudolosowych generatorów strumieniowych często wykorzystuje się rejestry. Generatory takie mają szerokie zastosowanie w kryptografii. Im bardziej wyrafinowany system generujący bity, tym trudniej jest go złamać. Nasz generator jest oparty na rejestrze przesuwnym ze sprzężeniem zwrotnym. Działanie jego jest bardzo proste. Ustalamy według pewnego schematu (o tym w dalszej części zadania) komórki rejestru, z których sumowane są bity modulo 2. Wynik jest wygenerowanym bitem, który także jest wstawiany na koniec rejestru, natomiast pozostałe są przesuwane o jeden bit w prawo.
Aby uzyskać maksymalny cykl takiego generatora należy oprzeć go o wielomian pierwotny modulo 2 (autor zadania zadbał o to, żeby tylko takie pojawiły się na wejściu). Wielomian, który został przedstawiony w zadaniu ma postać:
x8+x4+x3+x2+1
Rejestr ma zawsze długość stopnia wielomianu. W tym przypadku jest to 8 bitów. Zaczepy bitów, które będziemy dodawać modulo 2 ustawiamy odpowiednio na 8, 4, 3 oraz 2 miejscu (wyraz wolny nie bierze udziału).
Rysunek przedstawia generator dla wielomianu podanego w przykładzie:
Zadanie polega na odszyfrowaniu wiadomości zaszyfrowanej tym generatorem.
Szyfrowanie
Najpierw ustawiamy ziarno - wartości początkowe bitów zawartych w poszczególnych komórkach rejestru. Następnie uruchamiamy generator pewną ilość razy. Następnie generujemy partie po osiem bitów i xorujemy je z kodem ASCII danej litery. W ten sposób powstaje szyfrogram w postaci sekwencji bitów - jedna litera = 8 bitów. Twoje zadanie polega na odszyfrowaniu wiadomości i przedstawieniu jej w postaci znakowej.
Wejście
W pierwszym wierszu jedna liczba n określająca stopień wielomianu pierwotnego (n < 10000).
W drugim wierszu n+1 współczynników tego wielomianu począwszy od tego, który stoi przy najwyższej potędze (współczynniki należą do zbioru {0, 1}.
Następnie ustawienie ziarna - n bitów rejestru.
W czwartym wierszu jedna liczba u określająca po ilu uruchomieniach generatora, bity będą brane pod uwagę.
W ostatnim wierszu szyfrogram o długości 8⋅s (1 ≤ s ≤ 500000).
Dodatkowo n⋅s < 108 oraz n⋅u < 108
Wyjście
Oryginalna wiadomość.
Przykład
Wejście: 8 1 0 0 0 1 1 1 0 1 1 1 1 0 0 1 0 1 2 0101001000010101100000101011011011010101 Wyjście: haker
| Dodane przez: | Marcin Kasprowicz |
| Data dodania: | 2014-12-17 |
| Limit czasu wykonania programu: | 1s-3s |
| Limit długości kodu źródłowego | 50000B |
| Limit pamięci: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Języki programowania: | All except: ASM64 GOSU |
ukryj komentarze
|
2014-12-28 00:19:25 Marcin Kasprowicz
Zmiana limitu czasowego jednego testu |
|
|
2014-12-27 21:42:35 Marcin Kasprowicz
W teście przykładowym wkradł się bug :( Jednej zmiennej nie wyzerowałem, a przez godzinę szukałem błędu. Testy i przykład są już ok. Rejudge Ostatnio edytowany: 2014-12-27 23:36:17 |
|
|
2014-12-27 21:40:47 Mateusz Puczel
Mi również w teście przykładowym szyfrogram słowa "haker" wychodzi inny. |
|
|
2014-12-27 21:39:01 Mateusz Wasylkiewicz
Można prosić o jakiś przykład szyfrowania generatorem? Wychodzi mi, że generator z testu przykładowego wygeneruje ciąg: 01001110100111010... u = 2, więc rozpatrujemy bity od drugiego. Jeśli oryginalną wiadomością był "haker", to xorujemy 10011101 z kodem ASCII 'h', czyli 01101000, co daje 11110101, a miało być 1110111. Potem xorujemy dalszą część wygenerowanych bitów, 00111010 z literą 'a', czyli 01100001, co daje 01011011, i znowu się nie zgadza, bo miało być 00010000. Gdzie jest błąd w moim rozumowaniu? |
|
|
2014-12-27 21:29:48 Mateusz Puczel
W wygenerowanych partiach po 8 bitów, najmniej znaczące bity zostały wygenerowany najwcześniej czy najpóźniej? "W czwartym wierszu jedna liczba u określająca po ilu uruchomieniach generatora, bity będą brane pod uwagę." Czy po dokładnie u-tym uruchomieniu otrzymany bit liczy się do szyfrowania czy dopiero następne? |
|
|
2014-12-27 20:59:22 Marcin Kasprowicz
generowany bit jest sumą bitów na ustalonych pozycjach i właśnie ten bit idzie na sam koniec kolejki rejestru oraz jest wygenerowanym bitem używanym do szyfrowania. Ostatni bit po prawej stronie jest kasowany. Rzeczywiście rysunek trochę wprowadza w błąd, zaraz go poprawię Ostatnio edytowany: 2014-12-27 21:05:16 |
|
|
2014-12-27 20:58:28 Marcin Kasprowicz
sumowane są bity z ustalonych pozycji, czyli 8, 4, 3 i druga pozycja rejestru |
|
|
2014-12-27 20:36:16 Mateusz Wasylkiewicz
Czy generowanymi bitami są sumy bitów modulo 2 z ustalonych pozycji (jak jest napisane w treści), czy bity najbardziej po lewej w rejestrze (jak sugeruje rysunek)? |
RSS