Zadanie 1. Wytwórnia mleka czekoladowego

Do produkcji mleka czekoladowego używa się wielu rodzajów kakao. Rodzaje te opisane są liczbami naturalnymi. Receptura jest ściśle chroniona, a zarządzaniem dostawą składników zajmuje się komputer. W zakładzie korespondencja jest szyfrowana za pomocą asymetrycznego algorytmu szyfrującego RSA wykorzystującego udostępnioną wszystkim podmiotom pulę kluczy publicznych. System ten jest wykorzystywany do prowadzenia zabezpieczonej wymiany danych między podmiotami zakładu produkcyjnego.

Zadanie 1.1

Magazyn wymagał uzupełnienia zapasów ziaren kakao różnego typu. W tym celu komputer wysłał do dostawcy wiadomość z zaszyfrowanymi kodami produktów, które powinny zostać zamówione. Ponieważ dla danych rodzajów mleka czekoladowego ziarna kakao trzymane są w osobnych sekcjach, wysłane kody mogą się powtarzać. Aby dowiedzieć się, które rodzaje kakao mają zostać wysłane, dostawca musi odszyfrować kody z użyciem swoich kluczy prywatnych, które umieszczono w pliku z danymi.

W pliku dostawy.txt znajduje się 100 wierszy. Każdy wiersz składa się z trzech liczb naturalnych. Pierwsza i druga liczba to elementy klucza prywatnego dostawcy, trzecia liczba to szyfrogram będący zaszyfrowanym kodem przypisanym do danego typu ziaren kakao. Każda z tych wartości jest oddzielona od pozostałych znakiem odstępu.

Napisz program, który rozszyfruje podane wiadomości z użyciem kluczy prywatnych dostawcy. Wyniki zapisz w pliku wyniki_1.txt.

2165 5561 5463
4811 7387 2197

10
13

d    n    szyfrogram
2165 5561 5463
4811 7387 2197

odszyfrowana wiadomość
10
13

Do oceny oddajesz:

• plik wyniki_1.txt zawierający odpowiedź (odszyfrowane wiadomości; każda wiadomość w nowej linii);

• plik(i) z komputerową realizacją zadania (kodem programu).

Rozwiązanie

Zaczynamy od wczytania z pliku elementów kluczy prywatnych i szyfrogramów:

ile ← 100
d[0..ile-1] ← Wczytaj z pliku 'dostawy.txt' pierwsze elementy kluczy prywatnych
n[0..ile-1] ← Wczytaj z pliku 'dostawy.txt' drugie elementy kluczy prywatnych
W[0..ile-1] ← Wczytaj z pliku 'dostawy.txt' szyfrogramy do odszyfrowania

W kolejnym kroku tworzymy funkcję, która zgodnie ze wzorem $W^{d}modn$ odszyfruje wiadomość. Zwróćmy uwagę, że potrzebna jest operacja potęgowania. Ponieważ nie dysponujemy operatorem potęgowania, napiszemy również funkcję wykonującą to działanie.

funkcja rozszyfruj(d, n, W)
	zwróć potęga(W, d) mod n

W przedstawionej funkcji używamy nieutworzonej jeszcze funkcji obliczającej potęgę liczby. Zapiszmy ją. Wykorzystamy algorytm szybkiego potęgowania, który został opisany w e‑materiałach: Analiza podejścia rekurencyjnego i iteracyjnegoPNMlyY9MbAnaliza podejścia rekurencyjnego i iteracyjnego i Algorytmy iteracyjne i liczbowe – potęgowanie liczbPeGPO00R1Algorytmy iteracyjne i liczbowe – potęgowanie liczb.

Możemy wykorzystać wersję rekurencyjną lub iteracyjną algorytmu.

Wersja rekurencyjna:

funkcja potęga(W, d)
	jeżeli W = 0
		zwróć 1
	jeżeli d mod 2 = 1
		zwróć W * potęga(W, d - 1)
	w przeciwnym razie
		wartość ← potęga(W, d / 2)
	return wartość * wartość

Wersja iteracyjna:

funkcja potęga(W, d)
	W = 1
        dopóki d > 0
            jeżeli d mod 2 = 1
                wynik ← wynik * podstawa
            d ← d div 2
            W ← W * W
        zwróć wynik

Wykorzystamy wersję rekurencyjną.

Wywołujemy w pętli funkcję odszyfrowującą dla każdego odczytanego z pliku zestawu danych. Zapisujemy wynik do odpowiedniego pliku.

Zamykamy pliki.

Kompletny pseudokod:

funkcja rozszyfruj(d, n, W)
	zwróć potęga(W, d) mod n
    
funkcja potęga(W, d)
	jeżeli W = 0
		zwróć 1
	jeżeli d mod 2 = 1
		zwróć W * potęga(W, d - 1)
	w przeciwnym razie
		wartość ← potęga(W, d / 2)
	zwróć wartość * wartość        
    
ile ← 100
d[0..ile-1] ← Wczytaj z pliku 'dostawy.txt' pierwsze elementy kluczy prywatnych
n[0..ile-1] ← Wczytaj z pliku 'dostawy.txt' drugie elementy kluczy prywatnych
W[0..ile-1] ← Wczytaj z pliku 'dostawy.txt' szyfrogramy do odszyfrowania

dla i = 0, 1, 2, ..., ile - 1 wykonuj
    wiadomość = rozszyfruj(d, n, W)
    zapisz wiadomość w nowej linii pliku 'wyniki_1.txt'
zamknij plik 'dostawy.txt'
zamknij plik 'wyniki_1.txt'

Zadanie 1.2

Po realizacji zamówienia do komputera zajmującego się zarządzaniem składnikami w wytwórni wysyłana jest wiadomość z informacją o tym, kiedy zamówione kakao dotrze do magazynu. W treści znajduje się zakodowana informacja o liczbie dni, które upłyną od otrzymania zlecenia do pojawienia się dostawy w magazynie. Wiersze z liczbą dni odpowiadają wierszom z zamówieniami z zadania 1.1.

Aby zachować poufność korespondencji, wiadomość należy również zaszyfrować. Szyfrowanie odbywa się za pomocą kluczy publicznych podanych w pliku z danymi.

W pliku wiadomosci.txt znajduje się 100 zestawów danych (oddzielnie dla każdego wiersza z zamówieniem) potrzebnych do zaszyfrowania wiadomości. Każdy zestaw zapisany jest w odrębnym wierszu i składa się z trzech liczb naturalnych oddzielonych znakiem spacji. Każdy wiersz składa się z dwóch liczb będących elementami klucza publicznego oraz wiadomości do zaszyfrowania zawierającej liczby dni, które upłyną od otrzymania zlecenia do pojawienia się dostawy w magazynie.

Napisz program, który zaszyfruje wiadomości podane w pliku zgodnie z przyporządkowanymi im kluczami publicznymi. Wyniki zapisz w pliku wyniki_2.txt.

5 5561 10
3 7387 13

5463
2197

e n    W
5 5561 10
3 7387 13

zaszyfrowana wiadomość
5463
2197

Do oceny oddajesz:

• plik wyniki_2.txt zawierający odpowiedź (zaszyfrowane wiadomości; każda wiadomość w nowej linii);

• plik(i) z komputerową realizacją zadania (kodem programu).

Rozwiązanie

Zacznijmy od wczytania z pliku wiadomości, które mamy zaszyfrować:

ile ← 100
e[0..ile-1] ← Wczytaj z pliku 'wiadomosci.txt' pierwsze elementy kluczy publicznych
n[0..ile-1] ← Wczytaj z pliku 'wiadomosci.txt' drugie elementy kluczy publicznych
W[0..ile-1] ← Wczytaj z pliku 'wiadomosci.txt' wiadomości do zaszyfrowania

Tworzymy funkcję, w której wykorzystamy wzór $W^{e}modn$ do szyfrowania wiadomości. Pamiętajmy, że tak jak w przypadku rozwiązania zadania 1.1 potrzebujemy funkcji wykonującej operację potęgowania. Wykorzystamy w tym celu funkcję z rozwiązania zadania 1.1.

funkcja zaszyfruj(e, n, W)
	zwróć potęga(W, e) mod n

Wywołujemy funkcję szyfrującą dla wartości kluczy publicznych i szyfrowanych wiadomości za pomocą pętli i zapisujemy wynik do pliku docelowego.

Zamykamy pliki.

Cały pseudokod prezentuje się następująco:

funkcja zaszyfruj(e, n, W)
	zwróć potęga(W, e) mod n
    
funkcja potęga(W, d)
	jeżeli W = 0
		zwróć 1
	jeżeli d mod 2 = 1
		zwróć W * potęga(W, d - 1)
	w przeciwnym razie
		wartość ← potęga(W, d / 2)
	return wartość * wartość
        
ile ← 100
e[0..ile-1] ← Wczytaj z pliku 'wiadomosci.txt' pierwsze elementy kluczy publicznych
n[0..ile-1] ← Wczytaj z pliku 'wiadomosci.txt' drugie elementy kluczy publicznych
W[0..ile-1] ← Wczytaj z pliku 'wiadomosci.txt' wiadomości do zaszyfrowania

dla i = 0, 1, 2, ..., ile - 1 wykonuj
    szyfrogram ← zaszyfruj(e[i], n[i], W[i])
    zapisz szyfrogram w nowej linii pliku 'wyniki_2.txt'
    
zamknij plik 'wiadomosci.txt'    
zamknij plik 'wyniki_2.txt'

Zadanie 1.3

W zakładzie nastąpił wyciek danych, w wyniku którego odtajnione zostały klucze publiczne i prywatne powiązanych podmiotów. Konieczne jest wygenerowanie nowych par kluczy z wykorzystaniem innych par liczb pierwszych. Klucze mają być stosowane z szyfrem RSA, a co za tym idzie, muszą spełniać określone warunki: pierwszy człon klucza publicznego e musi być liczbą względnie pierwszą do wartości φphi(n) wyznaczonej funkcją Eulera, a pierwszy człon klucza prywatnego d powinien stanowić odwrotność modulo φphi(n) liczby e, podczas gdy drugi człon kluczy n określa największą możliwą wielkość liczbową wiadomości.

W pliku liczby.txt znajduje się 100 par liczb pierwszych p i q, mających zostać użytych do wygenerowania par kluczy: publicznego i prywatnego. Każda para liczb pierwszych zapisana jest w osobnym wierszu.

Napisz program, który bazując na podanych w pliku liczby.txt liczbach pierwszych, wygeneruje człony kluczy publicznego i prywatnego e, d i n, spełniających wymogi podanego algorytmu szyfrującego. Wyniki zapisz w pliku wyniki_3.txt.

11 5
11 23

3 27 55
3 147 253

Do oceny oddajesz:

• plik wyniki_3.txt zawierający odpowiedź (wyznaczone człony kluczy publicznego i prywatnego w kolejności e, d, n; zestawy członów kluczy zapisane w osobnym wierszu; poszczególne człony kluczy oddzielone są pojedynczym znakiem odstępu);

• plik(i) z komputerową realizacją zadania (kodem programu).

Rozwiązanie

Znając liczby pierwsze, możemy wyznaczyć liczbę n, czyli ich iloczyn. Następnie korzystamy z funkcji Eulera w postaci $\phi \left(n\right)=\left(p-1\right)\left(q-1\right)$ do wyznaczenia liczby e, spełniającej założenia: $1 < \mathrm{e} < \phi \left(n\right)$ takiej, że e jest względnie pierwsza z $\phi \left(n\right)$. Na koniec wyznaczamy wartość d, czyli odwrotność modulo z $\mathrm{e}mod\phi \left(n\right)$.

Zaczniemy od zapisania podanych liczb pierwszych:

ile ← 100
p[0..ile-1] ← Wczytaj z pliku 'liczby.txt' pierwsze liczby z par liczb pierwszych
q[0..ile-1] ← Wczytaj z pliku 'liczby.txt' drugie liczby z par liczb pierwszych

Następnie, bazując na odczytanych liczbach pierwszych, wykonamy w pętli przechodzącej po wszystkich odczytanych parach liczb serię czynności. Pierwszą z nich będzie wyznaczenie wartości liczby n.

ile ← 100
p[0..ile-1] ← Wczytaj z pliku 'liczby.txt' pierwsze liczby z par liczb pierwszych
q[0..ile-1] ← Wczytaj z pliku 'liczby.txt' drugie liczby z par liczb pierwszych

dla i = 0, 1, 2, ..., ile - 1 wykonuj
	n ← p[i] * q[i]

Kolejnym krokiem będzie wyznaczenie dla każdej pary liczb pierwszych wartości e. W tym celu potrzebne będą między innymi funkcje pomocnicze wyznaczające wartość funkcji Eulera i największy wspólny dzielnik podanych liczb pierwszych.

Funkcja wyznaczająca wartość funkcji Eulera przyjmie postać funkcji zwracającej iloczyn podanych liczb pierwszych pomniejszonych o 1.

funkcja euler(p,q)
	zwróć (p-1) * (q-1)

Kolejnym etapem będzie stworzenie funkcji wyznaczającej największy wspólny dzielnik, w której skorzystamy z algorytmu EuklidesaP7OAFYVSialgorytmu Euklidesa.

funkcja NWD(p,q)
	dopóki p ≠ q wykonuj
    	jeżeli p > q
        	p ← p - q
        w przeciwnym razie
        	q ← q - p
    zwróć p

Po napisaniu obu funkcji pomocniczych możemy przystąpić do tworzenia funkcji wyznaczającej wartość e. W funkcji tej za pomocą pętli przejdziemy po liczbach z przedziału $\left(1, \phi \left(n\right)\right)$, sprawdzając, czy są względnie pierwsze (czy ich największy wspólny dzielnik jest równy 1).

funkcja wyznacz_e(p, q)
	euler ← euler(p, q)
	dla i = 2, 3, ... (euler - 1) wykonuj:
    	jeżeli NWD(i, euler) = 1
        	zwróć i

Następnie wartość zwracaną przez tę funkcję zapisujemy do zmiennej.

ile ← 100
p[0..ile-1] ← Wczytaj z pliku 'liczby.txt' pierwsze liczby z par liczb pierwszych
q[0..ile-1] ← Wczytaj z pliku 'liczby.txt' drugie liczby z par liczb pierwszych

dla i = 0, 1, 2, ..., ile - 1 wykonuj
	n ← p[i] * q[i]
	e ← wyznacz_e(p[i],q[i])

Przechodzimy do funkcji wyznaczającej odwrotność modulo φphi(n) liczby e. Tworzymy cztery zmienne (a, b, c, d) – w dwóch zapisujemy wartość e oraz wartość funkcji Eulera $\phi \left(n\right)$, a w pozostałych pomocnicze wartości 1 oraz 0. Następnie tworzymy pętlę, która będzie wykonywała się do momentu, aż wartość zmiennej, do której przypisaliśmy wartość e, wyniesie 0. Jeżeli wartość a (wstępnie liczba e) będzie mniejsza od b (wartość funkcji Eulera), to zamieniamy ich wartości w zmiennych oraz zamieniamy wartości pozostałych zmiennych pomocniczych. Ustalamy wartość zmiennej pomocniczej na wartość zwracaną przez dzielenie całkowite a przez b. Następnie zmniejszamy wartość zmiennej c o iloczyn zmiennej pomocniczej oraz zmiennej d. Zmniejszamy również wartość zmiennej a o iloczyn zmiennej pomocniczej oraz zmiennej b. Tu następuje ustalanie wartości odwrotności modularnej. Wykorzystana też zostaje funkcja pomocnicza zamieniająca wartości zmiennych.

funkcja zamień(x, y)
	pom ← x
    x ← y
    y ← pom

funkcja odwrotność_modulo(e, p, q)
	a ← e
    b ← euler(p, q)
    c ← 1
    d ← 0
    dopóki a ≠ 0 wykonuj:
    	jeżeli a < b
        	zamień(a, b)
            zamień(c, d)
        pom ← a / b
        c ← c - pom * d
        a ← a - pom * b
	jeżeli(b ≠ 1)
    	jeżeli(d < 0)
        	d ← d + b
    	d ← d + euler(p, q)
        zwróć d

Następnie wywołujemy tę funkcję dla każdej pary liczb pierwszych, a wynik wywołania tej funkcji przypisujemy do zmiennej:

ile ← 100
p[0..ile-1] ← Wczytaj z pliku 'liczby.txt' pierwsze liczby z par liczb pierwszych
q[0..ile-1] ← Wczytaj z pliku 'liczby.txt' drugie liczby z par liczb pierwszych

dla i = 0, 1, 2, ..., ile - 1 wykonuj
	n ← p[i] * q[i]
    e ← wyznacz_e(p[i],q[i])
    d ← odwrotność_modulo(e, p[i], q[i])

Ostatnim krokiem będzie zapisanie wyznaczonych wartości parametrów e, d i n do odpowiedniego pliku wynikowego.

ile ← 100
p[0..ile-1] ← Wczytaj z pliku 'liczby.txt' pierwsze liczby z par liczb pierwszych
q[0..ile-1] ← Wczytaj z pliku 'liczby.txt' drugie liczby z par liczb pierwszych

dla i = 0, 1, 2, ..., ile - 1 wykonuj
	n ← p[i] * q[i]
    e ← wyznacz_e(p[i],q[i])
    d ← odwrotność_modulo(e, p[i], q[i])
    zapisz e d n w pliku 'wyniki_3.txt'

Zamykamy pliki.

Cały pseudokod wygląda następująco:

funkcja euler(p,q)
	zwróć (p-1) * (q-1)

funkcja NWD(p,q)
	dopóki p ≠ q wykonuj
    	jeżeli p > q
        	p ← p - q
        w przeciwnym razie
        	q ← q - p
    zwróć p

funkcja wyznacz_e(p, q)
	euler ← euler(p, q)
	dla i = 2, 3, ... (euler - 1) wykonuj:
    	jeżeli NWD(i, euler) = 1
        	zwróć i

funkcja zamień(x, y)
	pom ← x
    x ← y
    y ← pom

funkcja odwrotność_modulo(e, p, q)
	a ← e
    b ← euler(p, q)
    c ← 1
    d ← 0
    dopóki a ≠ 0 wykonuj:
    	jeżeli a < b
        	zamień(a, b)
            zamień(c, d)
        pom ← a / b
        c ← c - pom * d
        a ← a - pom * b
	jeżeli(b ≠ 1)
    	jeżeli(d < 0)
        	d ← d + b
    	d ← d + euler(p, q)
        zwróć d

ile ← 100
p[0..ile-1] ← Wczytaj z pliku 'liczby.txt' pierwsze liczby z par liczb pierwszych
q[0..ile-1] ← Wczytaj z pliku 'liczby.txt' drugie liczby z par liczb pierwszych

dla i = 0, 1, 2, ..., ile - 1 wykonuj
	n ← p[i] * q[i]
    e ← wyznacz_e(p[i],q[i])
    d ← odwrotność_modulo(e, p[i], q[i])
    zapisz e d n w pliku 'wyniki_3.txt'
    
zamknij plik 'liczby.txt'    
zamknij plik 'wyniki_3.txt'

Słownik