26379번 - DeCSS 1 다국어

문제

Content Scramble System (CSS) je metoda kojom se kriptira sadržaj na DVD medijima kako bi mu mogli pristupati samo licencirani uređaji. U varijanti ovog sustava kojom se bavimo, ključ K je niz od točno 42 bita k₁, k₂, . . . , k₄₂, dok je sadržaj niz od n byte-ova. Sadržaj se kriptira tako da se najprije na temelju ključa generira takozvani tok ključa T(K) – također niz od n byte-ova te se, zatim, primijeni operacija bitovni ekskluzivni ILI na odgovarajuće elemente sadržaja i toka ključa.

Ako je poznat kriptirani tekst, te neki byte-ovi sadržaja, onda možemo odrediti odgovarajuće byte-ove toka ključa. Vaš je zadatak da na temelju djelomično poznatog toka ključa T(K) odredite jedan mogući ključ K.

Funkcija T(K) koja generira tok ključa se zasniva logičkom sklopu Linear-feedback shift register (LFSR). Stanje LFSR-a se sastoji od m bitova b₁, b₂, . . . , b_m, a funkcionalnost se definira tako da se odredi skup povratnih pozicija. U jednom ciklusu LFSR generira jedan bit izlaza te promjeni stanje na sljedeći način:

1. Izračuna se izlazni bit b tako da se zbroje bitovi na povratnim pozicijama. Ako je rezultat paran onda je b jednak 0, a inače je jednak 1. Dakle, b je ekskluzivno ILI bitova na povratnim pozicijma.
2. Svi bitovi stanja se pomiču ulijevo, bit b₁ se odbacuje, dok se bit b postavlja na zadnju poziciju. Dakle novo stanje je b₂, b₃, . . . , b_m, b.

Jedan korak LFSR-a se sastoji od 8 ciklusa, a rezultat je jedan byte koji čine izlazni bitovi ciklusa redom s desna nalijevo. Točnije, ako su izlazni bitovi ciklusa redom i₁, i₂, . . . , i₈, onda je rezultat koraka cijeli broj između 0 i 255 čiji je binarni zapis (i₈i₇...i₁)₂.

CSS koristi dva ovakva sklopa:

• LFSR17 veličine 17 bitova u kojem su pozicije 1 i 15 označene kao povratne, a početno stanje čine redom bitovi ključa k₁, k₂, . . . , k₁₇.
• LFSR25 veličine 25 bitova u kojemu su pozicije 1, 4, 5, i 13 označene kao povratne, a početno stanje čine redom bitovi ključa k₁₈, k₁₉, . . . , k₄₂.

Slika 1: Generiranje toka ključa

Tok ključa T(K) se generira na sljedeći način:

1. Sklopovi LFSR17 i LFSR25 se postave u početno stanje pomoću ključa K na opisani način.
2. Vrijednost varijable c se postavi na 0.
3. Ponavlja se n puta:
   1. Izvede se jedan korak sklopa LFSR17, neka je x rezultat koraka.
   2. Izvede se jedan korak sklopa LFSR25, neka je y rezultat koraka.
   3. Izračuna se zbroj z = x + y + c
   4. Ukoliko je z ≥ 256, z se umanji za 256, a c se postavi na 1. Inače se c postavi na 0.
   5. Sljedeći byte toka ključa je upravo z.

Zadan je tok ključa u kojem su neki byte-ovi poznati, a neki su nepoznati. Odredite jedan mogući ključ K od kojeg se na opisani način može dobiti tok koji odgovara zadanom.

입력

Prvi red sadrži prirodni broj n, duljinu zadanog toka ključa. Sljedeći red sadrži n cijelih brojeva t₁, t₂, . . . , t_n – redom byte-ovi toka ključa. Ukoliko je k-t_i byte nepoznat vrijedi t_k = −1, a ukoliko je poznat vrijedi 0 ≤ t_k ≤ 255.

출력

U prvi red ispišite bitove traženog ključa k₁, k₂, . . . , k₄₂ bez razmaka.

Napomena: Rješenje će uvijek postojati, iako ne mora biti jedinstveno.

제한

점수

Ovo je zadatak samo s izlazom – ne šaljete izvorni kod na evaluaciju već je samo potrebno riješiti 10 test podataka koje možete preuzeti sa sustava za evaluaciju. Opisi test podataka su sadržani u sljedećoj tablici.

힌트

Pojašnjenje prvog primjera: Sljedeća tablica sadrži detalje generiranja prva četiri byte-a toka ključa. Prvi redak tablice sadrži početno stanje, a svi ostali redci stanje neposredno nakon završetka određenog ciklusa odnosno koraka. U svakom LFSR-u su sivom bojom označene povratne pozicije te je podcrtan posljednji bit koji je ujedno bio i izlazni bit u tom ciklusu.