╚ßst 27 - CW 37/97

Modulßrnφ aritmetika a Üifrovßnφ

Mßme-li zaÜifrovat nebo pouze zak≤dovat n∞jakou zprßvu, je tato zprßva v∞tÜinou v n∞jakΘm p°irozenΘm jazyku (angliΦtina, ΦeÜtina, n∞mΦina atd.). Pro jednoduchost uva₧ujme dßle zprßvu psanou v angliΦtin∞, tak₧e mßme k dispozici prßv∞ 26 pφsmen (nerozliÜujeme velkß Φi malß pφsmena, resp. interpunkci). Zak≤dovßnφ zprßvy lze pak p°irozen²m zp∙sobem provΘst nßsledovn∞:

A B C D E F...V W X Y Z

00 01 02 03 04 05...21 22 23 24 25.

V Φem se pak zak≤dovan² text 19042319 liÜφ od zdrojovΘho textu TEXT? JednoduÜe v tom, ₧e na cel²ch Φφslech 0, 1, -1, 2, -2 atd. lze nßsobit a sΦφtat (odΦφtat) a tyto matematickΘ operace lze p°irozen²m zp∙sobem p°enΘst na mno₧inu {0, ..., 25}. P°itom "souΦet", resp. "souΦin" dvou Φφsel z tΘto mno₧iny musφ b²t op∞t Φφslo z tΘto mno₧iny, tj. to jedinΘ mo₧nΘ Φφslo, kterΘ se od obvyklΘho souΦtu, resp. souΦinu cel²ch Φφsel liÜφ o n∞jak² celoΦφseln² nßsobek poΦtu prvk∙ tΘto mno₧iny, tj. o Φφslo 26. ╪φkßme pak, ₧e sΦφtßme, resp. nßsobφme modulo m, kde m = 26. P°itom Φφslo p°irozenΘ m naz²vßme modulem.

Pro poΦφtßnφ s cel²mi Φφsly mßme celou °adu v²poΦetn∞ rychl²ch algoritm∙ (nap°. Euklid∙v algoritmus pro v²poΦet nejv∞tÜφho spoleΦnΘho d∞litele, resp. jeho binßrnφ verzi, ve kterΘ se nepou₧φvß dlouhΘ d∞lenφ, ale jen odΦφtßnφ a d∞lenφ dv∞ma, tj. realizovanΘ posunem).

Zßsadnφm pojmem z elementßrnφ teorie Φφsel je pojem kongruence -- °φkßme, ₧e dv∞ celß Φφsla x a y jsou kongruentnφ modulo m (pφÜeme x=y mod m), pokud se x a y liÜφ o n∞jak² celoΦφseln² nßsobek modulu m. OznaΦme f(m) poΦet p°irozen²ch Φφsel nesoud∞ln²ch s m, tj. je-li nap°φklad m prvoΦφslo, p°irozenß Φφsla nesoud∞lnß s m jsou po °ad∞ 1, 2, 3,..., m-1, pak f(m) = m-1. Funkce f(m) se naz²vß Eulerova funkce.

Pierre de Fermat (1601-1695) dokßzal, ₧e pro prvoΦφslo p a p°irozenΘ Φφslo a nesoud∞lnΘ s p platφ nßsledujφcφ: a^p-1=1 mod p tj. (p-1)-nφ mocnina Φφsla a je tvaru 1+kp pro vhodnΘ celΘ Φφslo k. Toto tvrzenφ zobecnil Leonard Euler (1707--1783) tak, ₧e pro p°irozenΘ Φφslo m a p°irozenΘ Φφslo a nesoud∞lnΘ s m platφ nßsledujφcφ: a^f(x)=1 mod m. P°itom prvoΦφsla m∙₧eme charakterizovat pomocφ Wilsonovy v∞ty jako₧to p°irozenß Φφsla m v∞tÜφ ne₧ 1 takovß, ₧e (m-1)! je kongruentnφ s (m-1) modulo m.

Pokud navφc Φφslo a z Eulerovy v∞ty spl≥uje podmφnku, ₧e a^x nenφ kongruentnφ s jedniΦkou modulo m pro p°irozenß Φφsla x=1,2,...,f(m)-1, nazveme a primitivnφm ko°enem modulo m. M∙₧eme pak definovat diskrΘtnφ logaritmus. Uva₧me tedy to p°irozenΘ Φφslo m, kterΘ mß primitivnφ ko°en a. Pro vÜechna x=1,2,...,f(m)-1 tak, ₧e mßme y=a^x mod m, nazveme x diskrΘtnφm logaritmem z Φφsla y p°i zßkladu a modulo m. PφÜeme pak x=log_ay mod m.

P°edpoklad toho, ₧e a je primitivnφ ko°en, je nutn² a zajistφ nßm, ₧e pro ka₧dΘ takovΘ y existuje prßv∞ jedno x, x=1,2,...,f(m)-1 a tedy je diskrΘtnφ logaritmus dob°e definovßn. P°itom se dß ov∞°it, ₧e exponencißlnφ funkce a^x modulo m se snadno spoΦφtß, ale obrßcen² postup -- diskrΘtnφ logaritmovßnφ je obtφ₧n² a srovnateln² s faktorizacφ p°irozenΘho Φφsla, tj. rozkladem na souΦin prvoΦφsel. TakovΘ funkce se naz²vajφ jednosm∞rnΘ a s ·sp∞chem se vyu₧φvajφ v kryptografii.

P°istupme nynφ k rozkladu p°irozenΘho Φφsla na prvoΦinitele. Jednß se v podstat∞ o t°i ·koly:

-- Je-li dßno p°irozenΘ Φφslo n, mßme rychle rozhodnout, zda n spl≥uje n∞jakou podmφnku, kterß je spln∞na ka₧d²m prvoΦφslem a tedy rozhodnout, zda je to urΦit∞ Φφslo slo₧enΘ, nebo zda je to asi prvoΦφslo (tzv. test na slo₧enost);

-- Vφme-li, ₧e n je asi prvoΦφslo, musφme dokßzat, ₧e n je skuteΦn∞ prvoΦφslem, nebo to vyvrßtit (tzv. test na prvoΦφselnost);

-- Vφme-li, ₧e n je slo₧enΘ, je t°eba nalΘzt netrivißlnφho d∞litele d Φφsla n. UvedenΘ kroky m∙₧eme opakovat pro Φφsla n a n/d.

PopiÜme nynφ n∞kterΘ zßkladnφ metody nalezenφ rozkladu. Nejznßm∞jÜφ je tzv. Eratosthenovo sφto (p°ibli₧n∞ 200 let p°. n. l.), kde zkouÜφme d∞lit n postupn∞ vÜemi prvoΦφsly 2, 3, 5... a₧ do jistΘ hranice -- pokud je touto hranicφ druhß odmocnina z n, provedeme vÜechny t°i ·koly souΦasn∞. V p°φpad∞, ₧e n je p°φliÜ velkΘ, b²vß v²hodnΘ d∞lit prvoΦφsly a₧ do vhodnΘ hranice, abychom se zbavili mal²ch faktor∙.

V∞nujme se nynφ test∙m na slo₧enost. Zdßnliv∞ dobrou podmφnkou se zdß b²t Wilsonova v∞ta, ale problΘm je, jak spoΦφtat pro velkß n dostateΦn∞ rychle Φφslo (n-1)! mod n. V²hodn∞jÜφ je proto pou₧φt Fermatovu v∞tu, proto₧e umoc≥ovßnφ lze provßd∞t modulo n opravdu rychle.

Mßme tedy zjistit, zda je n Φφslo slo₧enΘ. Pokud nalezneme p°irozenΘ Φφslo a, a<n, pro kterΘ nenφ a^n-1 kongruentnφ s 1 modulo n, vφme okam₧it∞, ₧e n je Φφslo slo₧enΘ. ╚φslo a se pak naz²vß sv∞dek slo₧enosti Φφsla n.

Pokud je vÜak a^n-1 kongruentnφ s 1, nem∙₧eme z toho usoudit nic a musφme zkouÜet dßle. Po jistΘm poΦtu pokus∙, kdy nenajdeme sv∞dka slo₧enosti, pak postup ukonΦφme a s jistou pravd∞podobnostφ usoudφme, ₧e n je prvoΦφslo.

Slo₧enß Φφsla, pro kterß platφ, ₧e a^n-1 je kongruentnφ s 1, se naz²vajφ Carmichaelova Φφsla (je jich nekoneΦn∞ mnoho) a nelze je v²Üe uveden²m postupem odhalit. Proto se pou₧φvajφ jistß zesφlenφ Fermatovy v∞ty (nap°. tzv. Miller-Rabin∙v test, kter² mß kubickou Φasovou nßroΦnost na v²poΦet a pravd∞podobnost, ₧e nßm objevφ ka₧dΘ slo₧enΘ Φφslo, je vysokß).

V∞nujme se nynφ test∙m na prvoΦφselnost. Vstupem je Φφslo n, o kterΘm s velkou pravd∞podobnostφ platφ, ₧e je to prvoΦφslo. To je vÜak t°eba dokßzat. Lze to provΘst nap°. n-1 testem Poclingtona a Lehmera, testem Goldwassera a Kiliana pomocφ eliptick²ch k°ivek, Atkinovou metodou, resp. metodou Jacobiho sum, p°iΦem₧ v²poΦetnφ slo₧itost posledn∞ jmenovanΘ metody se blφ₧φ slo₧itosti polynomißlnφ.

Hledßnφ netrivißlnφho d∞litele lze provΘst samoz°ejm∞ metodou pokusnΘho d∞lenφ. Z metod pou₧φvan²ch v praxi jmenujme Lehmannovu metodu, Pollardovu rho-metodu, Pollardovu (p-1) metodu, Lenstrovu metodu eliptick²ch k°ivek, metodu kvadratickΘho sφta a metodu sφta v ΦφselnΘm t∞lese.

Metoda sφta v ΦφselnΘm t∞lese je potencißln∞ nejrychlejÜφ znßmß metoda rozklßdßnφ velk²ch p°irozen²ch Φφsel. Bohu₧el, v²poΦty p°i pou₧itφ tΘto metody jsou opravdu velmi komplikovanΘ (je zde pot°eba zkonstruovat a popsat nejmenÜφ t∞leso algebraick²ch Φφsel obsahujφcφ jistΘ p°edem zvolenΘ algebraickΘ Φφslo a pak provΘst jistΘ prosφvßnφ mo₧n²ch v²sledk∙). Tedy tato v²hodnost se zaΦne projevovat a₧ pro dosti velkß Φφsla (o alespo≥ 130 dekadick²ch cifrßch). Ale pro Φφsla ve specißlnφm tvaru (Mersenneova, Fermatova Φφsla) m∙₧e b²t nßroΦnost metody zjednoduÜena a stßvß se pou₧itelnou i pro 120cifernß Φφsla.

PoprvΘ byla tato metoda s ·sp∞chem pou₧ita v roce 1990 p°i rozkladu devßtΘho Fermatova Φφsla n=2⁵¹²+1, kterΘ mß 155 cifer, na prvoΦinitele. Za pomoci mnoha dobrovolnφk∙ prost°ednictvφm elektronickΘ poÜty byl vynalo₧en ekvivalent n∞kolika let procesorovΘho Φasu na jednom poΦφtaΦi. Zφskanß data pak byla zpracovßna Gaussovou eliminacφ °φdkΘ matice nad dvojprvkov²m t∞lesem. Hledßme toti₧ lineßrnφ zßvislosti mezi °ßdky velmi velkΘ matice, kterß mß vÜak v ka₧dΘm °ßdku jen n∞kolik jedniΦek a zbytek °ßdku tvo°φ nuly. Z tΘto matice sestavφme mnohem menÜφ matici, v nφ₧ se provede Gaussova eliminace obvykl²m zp∙sobem.

Tv∙rci algoritmu RSA, spoΦφvajφcφho na p°edpokladu, ₧e je v²poΦetn∞ prakticky nezvlßdnutelnΘ faktorizovat dostateΦn∞ velkΘ p°irozenΘ Φφslo, vsadili 100 dolar∙ na to, ₧e nikdo nerozluÜtφ jejich anglick² text zaÜifrovan² pomocφ RSA s ve°ejn²m exponentem e =9007 a modulem o 129 cifrßch. V dubnu 1994 pak bylo oznßmeno, ₧e se poda°ilo metodou kvadratickΘho sφta roznßsobit 129cifernΘ Φφslo RSA-129, a tak odhalit v²Üe uveden² text, p°iΦem₧ tato Φinnost m∞la podle odhadu profesora Rivesta trvat vφce ne₧ 40 000 000 000 000 000 let.

O dva roky pozd∞ji, v dubnu 1996 byl proveden rozklad 130cifernΘho Φφsla RSA-130 metodou sφta v ΦφselnΘm t∞lese. Zb²vß tak opravdu jen relativn∞ velmi mßlo, aby byl proveden ·sp∞Ün² ·tok na standardnφ modul RSA o 512 bitech.

Vidφme, ₧e na prvnφ pohled trivißlnφ problΘm rozkladu vyu₧φvß netrivißlnφch v²sledk∙ teorie Φφsel a je pro velkß p°irozenß n stßle velmi nßroΦn². Je tedy vhodn² (p°i vhodnΘ volb∞ Φφsla n) pro pou₧itφ p°i Üifrovßnφ (algoritmus RSA s v∞tÜφm modulem, nap°φklad 1 024 nebo 2 048 bit∙ apod.).