ALG)7

13.1. Kodowanie danych i arytmetyka dużych liczb 297

liczby pierwsze 5, NI i N2 (typowo 100 cyfrowe) i udostępnia publicznie tylko ich iloczyn5 N =NIkN2 oraz pewną liczbę P, spełniającą warunek:

PxS mod (NI-I) x(N2-l)=I.

Zostało udowodnione, że dla każdego ciągu kodowego M (tekst zostaje zamieniony na odpowiadający mu ciąg liczbowy o pewnej skończonej długości) spełniona jest równość: M^IS mod N = M.

Kodowanie sprowadzi się zatem do obliczenia rówmości:

{ciąg kodowy}=£or/rr/(!Vl)= M¹' mod N,

natomiast dekodowanie jest równoważne obliczeniu:

M=clekoduj({ciąg kodowy})= {ciąg kodowy}^s mod N.

Pomimo pozornej trudności wykonania operacji na bardzo dużych liczbach, okazuje się, że własności funkcji modulo powodują, iż zarówno ciąg kodowy, jak i jego zaszyfrowana postać należą do tego samego zakresu liczb. Złamanie systemu RSA byłoby możliwe, jeśli umielibyśmy na podstawie znanych wartości N i P odtworzyć utajnione .9, potrzebne do rozkodowania wiadomości! Nie znaleziono do tej pory algorytmu, który potrafiłby wykonać to zadanie w rozsądnym czasie.

Wszelkie algorytmy kryptograficzne napotykają na problem wykonywania obliczeń na bardzo dużych liczbach całkowitych. Okazuje się, że obliczenia te mogą zostać znacznie uproszczone, pod warunkiem traktowania tych liczb jako współczynników wielomianów. Weźmy dla przykładu liczbę:

12 9876 0002 6000 0000 0054

W systemie o podstawie a-10 powyższa liczba może zostać przedstawiona jako:

a:²¹ +2x¹⁰ +(9x^iv + 8a:¹⁸ + 7x¹⁷ +6xⁱ⁶) + (2xⁱ²) + (6jcⁱⁱ) + (5xⁱ +4).

Jeśli x— 10 wydaje nam się za małe, to identyczną liczbę otrzymamy podstawiając, np. a-10000:

(1 2x^a ) + (9876jc³ ) + (2.x³) + (6x) + 54.

⁵ Ponieważ nie są aktualnie znane szybkie metody rozkładu na czynniki pierwsze, dokonanie takiego rozkładu przez osobę postronnąjest wysoce nieprawdopodobne.