14787. Termin drugi [AL_06_09]

Zadanie:

http://pl.spoj.com/problems/AL_06_09/

Skrócony opis problemu:

Problem przedstawia szyfrowanie z kluczem publicznym.

Na początek bierzemy pewien ciąg (superrosnący) a_k, którego każdy wyraz jest większy od sumy wyrazów poprzednich. Następnie ustalamy dwie względnie pierwsze liczby n i m, takie, że n jest względnie pierwsze ze wszystkimi elementami ciągu a_k oraz m jest większe od  sumy wszystkich wyrazów ciągu a_k. Każdy wyraz ciągu szyfrujemy według zasady:

b_i =  a_i $\cdot$ n mod m, dla 1 $\leq$ i $\leq$ k 

W ten sposób otrzymaliśmy ciąg b_k.

Wiadomość, którą chcemy zaszyfrować dzielimy na segmenty binarne o długości k a następnie szyfrujemy w taki sposób, że sumujemy tylko te elementy ciągu b_k., które odpowiadają wartości 1 w segmencie binarnym.

Np. jeśli ciąg b_k. ma postać: {1, 3, 5, 10}, dla n = 4, a wiadomość ma trzy segmenty o długości 4:

1100 0110 1111

to szyfrogram będzie wyglądał następująco:

I segment: 1 + 3 = 4

II segment: 3 + 5 = 8

III segment: 1 + 3 + 5 + 10 = 19.

Ciąg {4, 8, 19} jest szyfrogramem.

Na podstawie danych: n, m, k, ciągu a_k oraz szyfrogramu należy podać oryginalną wiadomość w postaci binarnej.

Rozwiązanie:

W celu odszyfrowania wiadomości odbiorca musi określić element odwrotny dla n modulo m. Ponieważ n i m są względnie pierwsze, taki element istnieje. Wykorzystujemy w tym celu rozszerzony algorytm Euklidesa. Następnie każdą liczbę szyfrogramu mnożymy przez n^-1 mod m. W ten sposób otrzymujemy wartości wiadomości w postaci liczby. Nazwijmy ją W.

Teraz wykorzystując ciąg a_k określamy bity szukanej wiadomości według schematu:

Sprawdzamy, czy największy wyraz (ostatni) ciągu jest nie większy niż liczba W. Jeśli tak, to ostatni bit k-elementowego segmentu będzie równy 1 i liczbę W zmniejszamy o wartość tego ciągu wyrazu, w przeciwnym wypadku 0.

Przykład:

Niech a_k ma postać: {1, 3, 5, 10}, n  = 7, m = 23, k = 4,
Oraz cztery elementy szyfrogramu: {10, 22, 31, 5}.

Obliczamy element odwrotny: n^-1 = 10.

Wyznaczamy kolejne liczby W_i , gdzie 1 $\leq$ i $\leq$ 4

W₁ = 10 $\cdot$ 10 mod 23 = 8
W₂ = 10 $\cdot$ 22 mod 23 = 13
W₃ = 10 $\cdot$ 31 mod 23 = 11
W₄ = 10 $\cdot$ 5 mod 23 = 4

Teraz tworzymy szukane segmenty:

{1, 3, 5, 10}: 8 = 0$\cdot$1 + 1$\cdot$3 + 1$\cdot$5 + 0$\cdot$10 = 0110

{1, 3, 5, 10}: 13 = 0$\cdot$1 + 1$\cdot$3 + 0$\cdot$5 + 1$\cdot$10 = 0101

{1, 3, 5, 10}: 11 = 1$\cdot$1 + 0$\cdot$3 + 0$\cdot$5 + 1$\cdot$10 = 1001

{1, 3, 5, 10}: 4 = 1$\cdot$1 + 1$\cdot$3 + 0$\cdot$5 + 0$\cdot$10  = 1100

Wyjście: 0110010110011100

Omawiany problem należy do grupy algorytmów plecakowych wykorzystywanych w kryptografii.