Normaforma egyenletek alkalmazása a

Normaforma egyenletek alkalmaz´ asa a kriptogr´ afi´ aban doktori (PhD) ´ertekez´es t´ezisei ¨ dmo ¨ n Jo ´ zsef Ko

Debreceni Egyetem Term´eszettudom´anyi Kar Debrecen, 2004

Bevezet´ es Az ´ertekez´es n´egy fejezetb˝ol ´all. Az els˝oben a jel¨olt [12] k¨onyve alapj´an r¨ovid ¨osszefoglal´ ast adunk a modern - bonyolults´agelm´eleti alapokon kidolgozott ´ kriptogr´afia alapfogalmair´ol. Erintj¨ uk az eg´eszs´eg¨ ugyi informatikai vonatkoz´asokat is (l´asd [8], [13], [14] ´es [11]). A m´asodik fejezetben els˝osorban a [21], [17] ´es [10] k¨onyvek alapj´an ¨osszefoglaljuk az egyir´any´ u f¨ uggv´enyek legfontosabb tudnival´oit. L´enyeges megjegyezni, hogy nem ismert matematikai bizony´ıt´ as arra, hogy ezek az egyir´any´ u f¨ uggv´enyek val´ oban l´eteznek. Elterjedt haszn´alatuk l´etjogosults´ag´at csup´an a gyakorlati tapasztalatok igazolj´ak. Helyesebb lenne az egyir´any´ u f¨ uggv´eny jel¨olt elnevez´es, de m´egis ink´abb az irodalomban szok´asos egyir´any´ u f¨ uggv´eny sz´ohaszn´alatn´al maradunk. A harmadik fejezet tartalmazza ´ertekez´es¨ unk u ´j eredm´enyeit. Egy u ´j egyir´ any´ u hash f¨ uggv´eny elk´esz´ıt´es´et ´ırjuk le, amihez a diofantikus egyenletek elm´elet´et alkalmazzuk. C´elunk el´er´es´ehez azonban nem az egyenletek megold´asainak megtal´al´ as´ ahoz vezet˝o algoritmusokkal foglalkozunk, hanem - ´eppen ellenkez˝ oleg az olyan egyenleteket igyeksz¨ unk alkalmazni, amelyek megold´asa nem l´atszik kivitelezhet˝onek. Egyir´any´ u f¨ uggv´eny¨ unk invert´ al´ asi neh´ezs´eg´et az algebrai sz´amelm´eletb˝ol j´ol ismert ´altal´ anos normaforma egyenletek megold´as´anak neh´ezs´eg´ere alapozzuk. ´ egyir´any´ Uj u f¨ uggv´eny¨ unk seg´ıts´eg´evel k´esz´ıt¨ unk egy egyir´ any´ u hash f¨ uggv´enyt, amelyet aj´anlunk a gyakorlati felhaszn´al´ as sz´am´ara. ´ Ertekez´ es¨ unk f˝o eredm´enye, hogy bizony´ıtjuk (l´asd m´eg [3]), hogy az NP,s f¨ uggv´eny u ¨tk¨oz´esmentes, ha a modulus elegend˝oen nagy. Ez pedig azt jelenti, hogy alkalmas egyir´any´ u hash f¨ uggv´enynek. A negyedik fejezetben tal´alhat´ok a MAPLE rendszer1

ben k´esz´ıtett alkalmaz´ asok forr´ask´ odjai, amelyeket az ´altalunk - szint´en MAPLE-ben - k´esz´ıtett algoritmusok tesztel´es´ehez haszn´altunk.

Egyir´ any´ u f¨ uggv´ enyek Az egyir´any´ u f¨ uggv´enyekkel kapcsolatos fogalmak pontos defin´ıci´ oj´ at adjuk meg, felhaszn´alva a [17] ´es [10] k¨onyveket. 1. Defin´ıci´ o. A ν : N → R f¨ uggv´eny elhanyagolhat´ o, ha minden c ≥ 0 konstanshoz l´etezik kc eg´esz u ´gy, hogy minden k ≥ kc eset´en ν(k) < k −c . 2. Defin´ıci´ o. Az f : {0, 1}∗ → {0, 1}∗ f¨ uggv´eny (er˝ os) egyir´ any´ u f¨ uggv´eny ha: (1) L´etezik PPT (polinomi´ alis val´ osz´ın˝ us´egi) algoritmus, amelynek x inputja eset´en az output f (x) lesz. (2) B´ armely A PPT algoritmushoz l´etezik egy νA elhanyagolhat´ o f¨ uggv´eny u ´gy, hogy b´ armely elegend˝ oen nagy k eset´en: · ¸ R k P f (z) = y : x ∈ {0, 1} ; y = f (x); z = A(k, y) ≤ νA (k), ahol a val´ osz´ın˝ us´eget u ´gy vessz¨ uk, hogy az x-ek befutj´ ak lehets´eges ´ert´ekeiket ´es az A algoritmus is az ´ermefeldob´ asait. R

Itt az x ∈ {0, 1}k azt jelenti, hogy az x sz´ ot v´eletlenszer˝ uen v´alasztjuk az ¨osszes lehets´eges k hossz´ us´ ag´ u bin´aris szavak k¨oz¨ ul. A defin´ıci´ oban szerepl˝o k konstans az u ´gynevezett biztons´agi param´eter, amely jellemez egy adott kriptorendszert. A k param´eter ´altal´ aban megegyezik az x input bin´aris hossz´aval. A szakirodalom foglalkozik m´asfajta egyir´any´ u f¨ uggv´eny defin´ıci´ oval is, de mi a tov´ abbiakban ezt az er˝os v´altozatot haszn´aljuk. 2

A gyakorlati alkalmaz´asokban nem egy egyir´any´ u f¨ uggv´enyt, hanem egy egyir´ any´ u f¨ uggv´eny csal´ adot szok´ as haszn´alni: 3. Defin´ıci´ o. Legyen I egy indexhalmaz. Minden i ∈ I eset´en Di ´es Ri v´eges sz´ amhalmazok. Az F = {fi : Di 7→ Ri }i∈I halmazt egyir´ any´ u f¨ uggv´ eny csal´ adnak nevezz¨ uk, ha teljes´ıti az al´ abbi felt´eteleket: (1) L´etezik S1 PPT algoritmus, ami a k inputra el˝ o´ all´ıt egy legfeljebb k bin´ aris hossz´ us´ ag´ u i ∈ I indexet. (2) L´etezik S2 PPT algoritmus, amely az i ∈ I inputra x ∈ Di outputot szolg´ altat. (3) L´etezik A1 PPT algoritmus, amely az i ∈ I ´es x ∈ Di inputra fi (x) outputot szolg´ altat, azaz A1 (i, x) = fi (x). (4) B´ armely A PPT algoritmushoz l´etezik egy νA elhanyagolhat´ o f¨ uggv´eny u ´gy, hogy b´ armely elegend˝ oen nagy k eset´en: · ¸ R R P fi (z) = y : i ∈ I, ∈ Di ; y = fi (x); z = A(i, y) ≤ νA (k). Ahol a val´ osz´ın˝ us´eget u ´gy ´ertelmezz¨ uk, hogy az i ´es x befutj´ ak lehets´eges ´ert´ekeiket ´es az A algoritmus is az ´ermefeldob´ asait. ´ Ertekez´ es¨ unkben meghat´aroz´o jelent˝os´ege van a hash f¨ uggv´enyeknek. 4. Defin´ıci´ o. A h f¨ uggv´enyt hash f¨ uggv´enynek nevezz¨ uk, ha legal´ abb az al´ abbi k´et felt´etelt teljes´ıti: (1) ¨ osszenyom´ as: a h f¨ uggv´eny egy tetsz˝ oleges bin´ aris hossz´ us´ ag´ u x inputot egy r¨ ogzitett m´eret˝ u h(x) outputba k´epezi le. (2) k¨ onny˝ u kisz´ am´ıtani: adott h ´es x input eset´en h(x) kisz´ am´ıt´ asa legfeljebb polinomi´ alis algoritmussal lehets´eges. 3

5. Defin´ıci´ o. Inverzk´ ep rezisztencia: el˝ ore megadott y outputhoz kereszt¨ ulvihetetlen egy x input megad´ asa u ´gy, hogy h(x) = y teljes¨ ulj¨ on. 6. Defin´ıci´ o. M´ asodik inverzk´ ep rezisztencia: el˝ ore megadott x1 inputhoz kereszt¨ ulvihetetlen egy x2 (6= x1 ) m´ asodik input megad´ asa u ´gy, hogy h(x1 ) = h(x2 ) teljes¨ ulj¨ on. 7. Defin´ıci´ o. Egy h hash f¨ uggv´eny u ¨tk¨ oz´ esmentes (collision resistant), ha tetsz˝ oleges x1 ´es x2 ´ert´ekekre ´es elegend˝ oen nagy k-ra, ha x1 6= x2 , akkor P [h(x1 ) = h(x2 )] ≤ ν(k), ahol a val´ osz´ın˝ us´eget u ´gy ´ertelmezz¨ uk, hogy az x1 , x2 ∈ {0, 1}k ´ert´ekek egym´ ast´ ol f¨ uggetlen¨ ul befutj´ ak lehets´eges ´ert´ekeiket. 8. Defin´ıci´ o. (Strict avalanche criterion) Az f f¨ uggv´eny er˝ os lavina hat´ assal rendelkezik, ha egy input bit megv´ altoztat´ asa az ¨ osszes output bit v´ altoz´ as´ at okozza 21 val´ osz´ın˝ us´eggel. Ez l´enyeg´eben azt jelenti, hogy egy input bit v´altoz´ asa eset´en az output bitek ´atlagosan fele megv´altozik. A bitek megv´altoz´ as´ at a k´odol´ aselm´eletb˝ ol ismert Hamming-t´ avols´ ag seg´ıts´eg´evel lehet m´erni. Ennek defin´ıci´ oja a k¨ovetkez˝ o: 9. Defin´ıci´ o. (Hamming-t´ avols´ ag) Legyen az x, y ∈ Z sz´ amok bin´ aris reprezent´ aci´ oja x = (ξ1 , ...ξn ) illetve y = (η1 , ...ηn ), ahol ξi , ηi ∈ {0, 1}. Ekkor a k´et sz´ am Hamming-t´ avols´ aga: %(x, y) =

n X

ξi ⊕ ηi ,

i=1

ahol ⊕ jelenti a bitenk´ent vett kiz´ ar´ o vagy m˝ uveletet. A tov´ abbiakban a k¨ozismert egyir´any´ u f¨ uggv´enyek le´ır´ as´ aval, t´ıpusaival ´es azok alkalmaz´ as´ aval, valamint a felt¨or´esi lehet˝os´egekkel foglalkozunk. 4

Normaforma egyenlet alkalmaz´ as´ an alapul´ o egyir´ any´ u f¨ uggv´ eny Az egyir´any´ u f¨ uggv´enyek kutat´as´anak igen kiterjedt irodalma van, amelyek k¨oz¨ ul csak n´eh´any fontosabbat emel¨ unk most ki: [9], [5], [4], [18] ´es [25]. A normaforma egyenlet alkalmaz´as´ an alapul´o egyir´any´ u f¨ uggv´eny kisz´am´ıt´as´ahoz h´arom m´odszert hasonl´ıtunk ¨ossze. Ezek az N , NP ´es NP,s lek´epez´esek, melyeknek sorrendis´ege mutatja a konstrukci´o fejl˝od´es´et. A gyakorlatban val´ o haszn´alatra az NP,s f¨ uggv´enyt aj´anljuk, amely az NP f¨ uggv´eny modul´aris aritmetik´at haszn´al´o v´altozata. Legyen θ egy n-ed fok´ u algebrai eg´esz, ´es jel¨olje T (X) ∈ Z [X] a Q f¨ol¨otti minim´al polinomj´at. Legyen K := Q(θ), ´es jel¨olje σi : K → C a K sz´amtest k¨ ul¨onb¨oz˝o be´agyaz´asait a koplex sz´amtestbe. Tov´abb´a, valamely α ∈ K eset´en jel¨olje α(i) := σi (α) (i = 1, . . . , n) az α konjug´altjait. Legyenek α1 , α2 , ..., αm ∈ K Q-linearisan f¨ uggetlen algebrai eg´eszek. Tekints¨ uk az L(X) = α1 X1 + ... + αm Xm line´aris form´at, ahol m ≤ n ´es legyen (i)

(i) Xm . L(i) (X) = α1 X1 + ... + αm

A N ormK/Q (L(X)) =

n Y

L(i) (X)

i=1

polinomot normaform´anak nevezz¨ uk. K¨onnyen l´athat´ o, hogy N ormK/Q (L(X)) egy n-ed fok´ u, eg´esz egy¨ utthat´ os homog´en polinom. Tekints¨ uk most azt a speci´alis esetet, amikor α1 = 1, α2 = θ, ..., αm = θm−1 . Felt´etelezz¨ uk m´eg, hogy 1, θ, ..., θm−1 egy 5

hatv´any eg´esz b´azisa ZK -nak, ahol ZK jel¨ oli a K sz´ amtest eg´eszeinek gy˝ ur˝ uj´et. ´Igy minden normaforma racion´alis egy¨ utthat´os line´aris transzform´aci´ oval konvert´ alhat´ o az al´abbi speci´alis alakba: N (X) = N ormK/Q (X1 + θX2 + · · · + θm−1 Xm ).

(1)

´Igy az ´altal´ anoss´ ag megs´ert´ese n´elk¨ ul haszn´alhatjuk ezt a form´at. Lek´epez´es¨ unk els˝o v´altozata az al´abbi:. 1. Konstrukci´ o. Defini´ aljuk az N : Zm → Z lek´epez´est az al´ abbi m´ odon: N : (x1 , . . . , xm ) 7→ N ormK/Q (x1 + θx2 + · · · + θm−1 xm ). Lek´epez´es¨ unk m´asodik v´altozat´ aban legyen P (X) ∈ Z[X] r¨ogz´ıtett n-ed fok´ u (n ≥ 3) f˝opolinom, amelynek nincsenek t¨obbsz¨ or¨ os gy¨okei. Jel¨olje α1 , . . . , αn a P polinom gy¨okeit ´es legyen L(i) (X) :=

m X

αij−1 Xj ,

ahol i = 1, . . . , n ´es m ≤ n.

j=1

Legyen defini´alva a P polinomhoz tartoz´o normaforma az al´abbi m´odon: n Y L(i) (X). NP (X) := i=1

Val´ oj´ aban NP (X) a normaforma egy ´altal´ anos´ıt´ asa, egy speci´alis sz´etes˝ o forma. 2. Konstrukci´ o. Defini´ aljuk az NP : Zm → Z lek´epez´est a k¨ ovetkez˝ o m´ odon: NP : (x1 , . . . , xm ) 7→ NP (x1 , . . . , xm ). 6

(2)

Mivel NP (X) egy eg´esz egy¨ utthat´os homog´en polinom, ez´ert az NP (x) f¨ uggv´eny´ert´ek minden x ∈ Zm eset´en racion´alis eg´esz lesz. Kriptogr´afiai szempontb´ol jobbnak t˝ unik v´eges testet alkalmazni. Legyen valamely s ∈ Z eset´en Zs := Z/sZ. ´Igy lek´epez´es¨ unk harmadik v´altozata az al´abbi: 3. Konstrukci´ o. Legyen s := pq, ahol p ´es q megfelel˝ oen nagy pr´ımsz´ amok. Defini´ aljuk az NP,s : Zm → Z lek´ e pez´ e st az al´ abbi s s m´ odon: NP,s : (x1 , ..., xm ) 7→ NP (x1 , . . . , xm ) mod s. A k¨ovetkez˝ okben megmutatjuk, hogy az N (x), NP (x) ´es NP,s (x) f¨ uggv´eny´ert´ekek kisz´am´ıt´asa k¨onny˝ u, ha x ∈ Zm . H´arom k¨ ul¨ onb¨oz˝o algoritmust mutatunk be a f¨ uggv´eny´ert´ekek kisz´am´ıt´as´ara. Az N (x) ´ert´ek kisz´am´ıt´as´ara fogunk koncentr´ alni, mivel az ott alkalmazott algoritmusok ´es a hozz´ajuk tartoz´o bonyolults´agi ´ert´ekek k¨onnyen ´atvihet˝ok a m´asik k´et f¨ uggv´enyre. A f¨ uggv´eny´ert´ek k¨onny˝ u kisz´am´ıthat´ os´ aga azt jelenti, hogy van olyan polinomi´alis bonyolults´ag´ u algoritmus, amellyel a f¨ uggv´eny´ert´ek egy´ertelm˝ uen meghat´arozhat´ o. A bonyolults´ agot minden esetben az input ´ert´ekek X maximuma ´es az n foksz´ am f¨ uggv´eny´eben adjuk meg. A norma defin´ıci´oja alapj´an nem lehet eg´esz aritmetik´aval sz´amolni, ez´ert meghat´arozzuk a k¨ozel´ıt˝o sz´am´ıt´ as hib´aj´ anak fels˝o korl´atj´at is. A bonyolults´agra pedig az al´abbi eredm´enyt kapjuk: 1. T´ etel. [2] Az N (x) f¨ uggv´eny´ert´ek¡ meghat´ aroz´ as´ ¢anak bonyo2 6 4 lults´ aga az (1) defin´ıci´ o alapj´ an O n + n log PmX , ahol a O konstansa csak A ´ert´ek´et˝ ol f¨ ugg, ahol A = es j=1 αj ≥ 2 ´ ¯ n¯ o ¯ (i) ¯ αj = max ¯αj ¯ : 1 ≤ i ≤ n . A f¨ uggv´eny´ert´ekek azonban meghat´arozhat´ ok eg´esz aritmetik´aval is. Ehhez az L(i) (X) line´aris form´ak m´atrix reprezent´aci´oj´at alkalmazzuk. Bizony´ıtjuk a k¨ovetkez˝ o t´etelt: 7

2. T´ etel. [3] Legyen P egy n-ed fok´ u f˝ opolinom, amelynek nincsenek t¨ obbsz¨ or¨ os gy¨ okei. Jel¨ olje α a P egy gy¨ ok´et. Legyen x ∈ Zm ´es legyen NP (x) defini´ alva (2) szerint. Akkor az NP (x) f¨ uggv´eny´ert´ek eg´esz aritmetik´ aval meghat´ arozhat´ o. 1. Megjegyz´ es. A 2. T´etel igaz az (1)-ben defini´ alt N (x) f¨ uggv´eny´ert´ek kisz´ am´ıt´ as´ anak eset´ere is. Legyen T (x) = P (x) ´es legyen p´eld´ aul θ = α1 , ekkor a t´etelben le´ırt kisz´ am´ıt´ asi m´ odszer l´enyeg´eben ugyan´ ugy haszn´ alhat´ o. Az algoritmus bonyolults´ ag´ ara pedig a k¨ovetkez˝ o eredm´enyt kapjuk: 3. T´ etel. [3] Ha az eg´esz aritmetik´ at alkalmaz´ o algoritmust haszuggv´eny´ert´ek kisz´ am´ıt´ as´ ara, akkor annak bonyon´ aljuk az NP (x) f¨ lults´ aga O(n7 + n6 log X + n5 log2 X), ahol a O konstansa csak a P (X) polinom egy¨ utthat´ oit´ ol f¨ ugg. 2. Megjegyz´ es. Tekintettel a 1.Megjegyz´esre, a 3.T´etelben megadott bonyolults´ ag igaz a (1)-ben defini´ alt N (x) f¨ uggv´eny´ert´ek kisz´ am´ıt´ as´ anak bonyolults´ ag´ ara is. A f¨ uggv´eny´ert´ekek meghat´arozhat´ ok modul´ aritmetik´ val¤ £aMris ¤ £aM −1 is, amelyben minden x ∈ Z sz´ amhoz, amire − 2 ≤x≤ 2 teljes¨ ul, egy v elem˝ u vektort tudunk rendelni a k¨ovetkez˝ o m´odon: ψ(x) = x(M ) = (x mod m1 , ..., x mod mv ), ahol M := m1 m2 · · · mv ´es az m1 , ..., mv > 0 sz´amok p´aronk´ent relat´ıv pr´ımek. Az x(M ) vektort szok´as az x eg´esz sz´am modul´aris reprezent´ aci´ oj´ anak nevezni. Mivel a ψ: x ↔ x(M ) lek´epez´es egy gy˝ ur˝ u homomorfizmus, az eg´esz aritmetik´at haszn´al´ o algoritmusunk ´atalak´ıthat´ o u ´gy, hogy a modul´aris reprezent´ aci´ o alkalmaz´ as´ aval tov´ abb cs¨okkentj¨ uk a bonyolults´ agot. Az al´abbi eredm´enyeket kapjuk: 8

4. T´ etel. [2] Az N (x) f¨ uggv´eny´ert´ek modul´ aris aritmetik´ aval t¨ ort´en˝ o meghat´ aroz´ as´ anak bonyolults´ aga O(n7 + n6 log X + n2 log3/2 X), ahol a O konstansai csak a T (X) polinom egy¨ utthat´ oit´ ol f¨ uggnek. 5. T´ etel. [3] Az NP (x) f¨ uggv´eny´ert´ek modul´ aris aritmetik´ aval t¨ ort´en˝ o meghat´ aroz´ as´ anak bonyolults´ aga O(n7 + n6 log X + n2 log3/2 X), ahol a O konstansa csak a P (X) polinom egy¨ utthat´ oit´ ol f¨ ugg. Az NP,s (x) f¨ uggv´eny´ert´ek kisz´am´ıt´as´ara a k¨ovetkez˝ o eredm´enyt kapjuk: 6. T´ etel. [3] Az NP,s (x) f¨ uggv´eny´ert´ek kisz´ am´ıt´ as´ anak bonyolults´ aga O(n5 log2 s), ahol a O konstansa abszol´ ut. Elk´esz´ıtj¨ uk mindh´arom algoritmus implement´ aci´ oj´ at MAPLE rendszerben, ´es tesztelj¨ uk a fut´asid˝oket. Ezek azt mutatj´ ak, hogy az N (x), NP (x) ´es NP,s (x) f¨ uggv´eny´ert´ekek kisz´am´ıt´ asa - a gyakorlatban is - val´oban k¨onny˝ u. A legjobbnak a m´atrix reprezent´aci´ot alkalmaz´o algoritmus bizonyult. Meg kell azonban azt is vizsg´alnunk, hogy az N , NP ´es NP,s lek´epez´esek inverz´enek kisz´am´ıt´asa mennyire neh´ez feladat. Ehhez elegend˝o az NP (X) = b, illetve NP (X) = b mod s normaforma egyenletek megold´as´anak lehet˝os´egeit ´attekinteni, ahol 0 6= b ∈ Z ´es a megold´asokat az x ∈ Zm vektorok k¨oz¨ ott keress¨ uk. Az ilyen ´altal´anos normaforma egyenletek megold´as´ ara jelenleg nem ismert a gyakorlatban is haszn´alhat´ o algoritmus, s˝ot m´eg az is nyitott k´erd´es, hogy a probl´ema algoritmussal megoldhat´oe. Mint ismeretes, Jurij Matijaszevics [16] 1970-ben bizony´ıtotta, hogy nem l´etezik olyan algoritmus, amely az ´altal´ anos diofantikus egyenletek megoldhat´os´ag´at eld¨onten´e. A normaforma egyenletekkel szoros kapcsolatban ´all´ o line´aris rekurz´ıv sorozatokr´ol sz´ol Cerlienco, Mignotte ´es Piras [6] k¨ovetkez˝o sejt´ese: 9

1. Sejt´ es. L´etezik k pozit´ıv eg´esz sz´ am ´es ξ (1) , . . . , ξ (k) eg´eszekb˝ ol ´ all´ o line´ aris rekurz´ıv sorozat a k¨ ovetkez˝ o tulajdons´ aggal: Algoritmussal nem d¨ onthet˝ o el, hogy vannak-e olyan n1 , . . . , nk ∈ Nk (1) (k) ´ert´ekek, amelyekre ξn 1 + · · · + ξn k = 0. Ezt felhaszn´alva, tal´an bel´athat´ o lenne, ha igaz ez a sejt´es, akkor a normaforma egyenletek megoldhat´os´ aga algoritmikusan nem d¨onthet˝ o el. Pontosabban, kimondhat´o a k¨ovetkez˝ o sejt´es: 2. Sejt´ es. Ha az 1. Sejt´es igaz, akkor nem l´etezik olyan algoritmus, amelyik nem elfajul´ o normaforma egyenletekr˝ ol eld¨ onti, hogy megoldhat´ oak-e. Megvizsg´aljuk a Thue-egyenlet eset´et, amely tekinthet˝ o egy speci´alis normaforma egyenletnek. Legyen F (X, Y ) ∈ Z[X, Y ] irreducibilis polinom ´es deg(F ) ≥ 3. Ekkor minden nem nulla b ∈ Zre az F (X, Y ) = b

(3)

diofantikus egyenletet Thue-egyenletnek nevezz¨ uk, ahol a megold´asok (x, y) ∈ Z2 sz´ amp´ arok. L´athat´ o, hogy a Thue-egyenlet l´enyeg´eben az NP (X) = b normaforma egyenlet k´et ismeretlenes specializ´al´ asa (m = 2, n ≥ 3). A. Thue 1909-ben a [23] cikkben bizony´ıtotta, hogy (3)-nak csak v´eges sok megold´asa van. 1968-ban A. Baker [1] effekt´ıv fels˝o korl´ atot hat´arozott meg a megold´asok abszol´ ut ´ert´ek´enek maximum´ ara, ami annyit jelent, hogy a (3) Thue egyenlet megold´asai algoritmussal meghat´arozhat´ oak. Huszonegy ´evvel k´es˝ obb, 1989ben Tzanakis ´es de Weger [24] gyakorlatban haszn´alhat´o algoritmust adott a (3) egyenlet megold´asainak megkeres´es´ere az LLL algoritmus (l´asd [7] 2.6.3. Algoritmus) felhaszn´al´ as´ aval. Thue-egyenletek gyakorlati megold´as´ anak eset´ere N.P. Smart [22] elv´egezte a bonyolults´ agi elemz´est, amelyb˝ol kider¨ ul, hogy ilyen egyenletek megold´asa ´altal´ aban exponenci´alis bonyolults´ ag´ u. 10

A fentiek alapj´ an l´ athat´ o, hogy az NP (x) = b, illetve NP (x) = b mod s egyenlet megold´ asainak meghat´ aroz´ asa el´eg neh´ez probl´ema. ´ Igy az N , NP ´es NP,s f¨ uggv´enyek lehetnek egyir´ any´ u f¨ uggv´eny jel¨ oltek, k¨ ul¨ on¨ osen akkor, ha a v´ altoz´ ok sz´ ama legal´ abb 3. ´ Ertekez´ es¨ unkben az NP ´es NP,s f¨ uggv´enyek k´et fontos tulajdons´ag´at - az u ¨tk¨oz´esmentess´eget ´es a lavina hat´ast - vizsg´aljuk meg. Az NP,s f¨ uggv´eny u ¨tk¨oz´eseinek bek¨ovetkez´esi val´ osz´ın˝ us´eg´et a Pcoll = P [NP,s (x) = NP,s (y) : x, y ∈ Zs m ] kifejez´es ´ert´eke mutatja meg. ´ Ertekez´ es¨ unk f˝o eredm´enye a k¨ovetkez˝o k´et t´etel: 7. T´ etel. [3] Legyen P (X) ∈ Z[X] egy legal´ abb harmadfok´ u f˝ opolinom, amelynek nincsenek t¨ obbsz¨ or¨ os gy¨ okei. Legyenek p ´es q olyan pr´ımsz´ amok, hogy q > p > q/2 ´es s := pq. Tegy¨ uk fel, hogy lnko(m, ϕ(s)) = 1. Jel¨ olje N (P, b, s) az NP (x1 , . . . , xm ) ≡ b (mod s) kongruencia megold´ asainak sz´ am´ at. ul, akkor • Ha lnko(b, s) = 1 teljes¨ 1

|N (P, b, s) − sm−1 | < c1 (P )sm−1− 4 • egy´ebk´ent pedig N (P, b, s) < c2 (P )sm−1 . A t´etelben lnko(n, m) jel¨oli az n ´es m eg´eszek legnagyobb k¨oz¨ os oszt´oj´at, ϕ(x) pedig, szok´as szerint, az Euler f´ele ϕ-f¨ uggv´enyt. 8. T´ etel. [3] Legyen P (X) ∈ Z[X] egy legal´ abb harmadfok´ u f˝ opolinom, amelynek nincsenek t¨ obbsz¨ or¨ os gy¨ okei. Legyenek p ´es q pr´ımsz´ amok olyanok, hogy q > p > q/2 ´es s := pq. Tegy¨ uk 11

fel, hogy lnko(m, ϕ(s)) = 1. Akkor az NP,s f¨ uggv´eny Pcoll u ¨tk¨ oz´esi val´ osz´ın˝ us´ege teljes´ıti a Pcoll <

C , s

egyenl˝ otlens´eget, ahol a C konstans csak a P polinomt´ ol f¨ ugg. A bizony´ıt´ ashoz alkalmazzuk S. Lang ´es A. Weil [15] t´etel´et, amely szerint ha a p pr´ım modulus elegend˝oen nagy, akkor az f ≡ 0 (mod p) egyenlet N (f, p) megold´asainak sz´ama teljes´ıti az ¯ ¯ ¯N (f, p) − pm−1 ¯ < C(f )pm−1− 12 egyenl˝ otlens´eget, ahol a C(f ) konstans ´ert´eke kiz´ar´ olag az f (X1 , . . . , Xm ) abszol´ ut irreducibilis polinomt´ ol f¨ ugg. Az abszol´ ut irreducibilit´as bizony´ıt´ as´ ahoz k´et lemm´ara lesz sz¨ uks´eg¨ unk. Az els˝o a klasszikus Sch¨ oneman - Eisenstein t´etel megfelel˝oje polinom gy˝ ur˝ ukre ´es egy k¨ovetkezm´enye Capelli t´etel´enek (l´asd [20] 662. oldal). 1. Lemma. Legyen P (X) ∈ C[X] egy polinom, amelynek van legal´ abb egy egyszeres gy¨ oke. Akkor a Z n −P (X) ∈ C[X, Z] polinom abszol´ ut irreducibilis minden n ≥ 1 eset´en. 2. Lemma. Legyen f (X) := f (X1 , . . . , Xm ) :=

n Q

(αi1 X1 + · · · +

i=1

αim Xm ) ∈ C[X1 , . . . , Xm ] egy forma, amelyre teljes¨ ul, hogy αij ∈ n Q m Q C minden 1 ≤ i ≤ n, 1 ≤ j ≤ m eset´en, ´es αij 6= 0. i=1 j=1

Tov´ abb´ a tegy¨ uk fel, hogy l´etezik 1 ≤ j1 < j2 ≤ n u ´gy, hogy ½ ¾ αkj1 αij1 6∈ : 1 ≤ k ≤ n, k 6= i . αij2 αkj2 Akkor az f (X) − a polinom irreducibilis C[X]-ben minden 0 6= a ∈ C eset´en. 12

3. Megjegyz´ es. Ha az s modulus el´eg nagy, akkor az NP,s f¨ uggv´eny a 7. Definici´ o szerint u ¨tk¨ oz´esmentes. Az NP,s ´es NP f¨ uggv´enyek lavina hat´as´ anak tesztel´es´ehez egy MAPLE programot k´esz´ıt¨ unk, amely az al´abbi relat´ıv Hammingt´avols´agokat hat´arozza meg: RHP,s :=

ρ(NP,s (x), NP,s (x0 )) l(s)

´es

ρ(NP (x), NP (x0 )) , l(NP (x0 )) ahol az x egy input az x0 pedig a hozz´a tartoz´o egy bitben megv´altoztatott input, valamint l(.) jel¨oli a bin´aris hossz f¨ uggv´enyt ´es ρ(., .) a 9. Definici´oban megadott Hamming-t´avols´agot. A tesztet t¨obb alkalommal is ezerszer futtattuk v´eletlenszer˝ uen gener´alt 21024 nagys´agrend˝ u input adatokkal. Az x0 input egyetlen bitj´enek megv´altoztat´asa szint´en v´eletlenszer˝ u volt. Az RHP,s ´ert´ekek ´atlaga 0.50 volt, 0.004 sz´or´ assal. Az NP f¨ uggv´eny tesztje egy kicsit rosszabb eredm´enyt hozott, az RHP ´ert´ekek ´atlaga 0.48 volt, 0.003 sz´or´assal. Ez a f¨ uggv´eny csak k¨ozel´ıt˝ oleg teljes´ıti az 8. Defin´ıci´oban megfogalmazott er˝os lavinahat´as krit´eriumot. RHP :=

uggv´eny teljes´ıti az 8. Defin´ıci´ oban megfogal3. Sejt´ es. Az NP,s f¨ mazott er˝ os lavinahat´ as krit´eriumot. Azt, hogy az NP,s f¨ uggv´eny invert´al´ asa ´altal´ aban neh´ez, az al´abbi felt´etel fejezi ki. 10. Defin´ıci´ o. Er˝ os Modul´ aris Normaforma Felt´etel (SMNA): Minden Q polinom ´es A PPT algoritmus eset´en, ha az s elegend˝ oen nagy 1 , P [A(s, b) = (x1 , ..., xm ) u ´gy, hogy b = NP,s (x1 , ..., xm )] < Q(k) 13

ahol xi ∈ Z ´es 1 ≤ max {|xi |} ≤ s − 1, valamint a val´ osz´ın˝ us´eget u ´gy kell venni, hogy az xi inputok befutj´ ak lehets´eges ´ert´ekeiket, ´es az A algoritmus is az ´ermefeldob´ asait. 4. Megjegyz´ es. Az el˝ obbihez hasonl´ oan az NP (X) f¨ uggv´enyhez lehet defini´ alni az Er˝ os Normaforma Felt´etelt (SNA), ami az NP f¨ uggv´eny invert´ al´ as´ anak kereszt¨ ulvihetetlens´eg´et fejezi ki. Bizony´ıthat´ o a k¨ovetkez˝ o t´etel. 9. T´ etel. Az SMNA, illetve SNA teljes¨ ul´ese eset´en az NP,s , illetve az NP f¨ uggv´eny egyir´ any´ u hash f¨ uggv´eny. A kriptogr´afiai gyakorlat ´altal´ aban nem egy egyir´any´ u f¨ uggv´enyt alkalmaz, hanem ink´abb egyir´ any´ u f¨ uggv´eny csal´ adot. Egy ilyen csal´adot fogunk k´esz´ıteni az NP,s f¨ uggv´eny felhaszn´al´ as´ aval. Tekints¨ uk az al´abbi konstrukci´ ot: 4. Konstrukci´ o. Legyen P (X) ∈ Z[X] egy olyan f˝ opolinom, amelynek nincsenek t¨ obbsz¨ or¨ os gy¨ okei. Legyenek p ´es q elegend˝ oen nagy pr´ımsz´ amok u ´gy, hogy q > p > q/2 ´es s := pq. Tegy¨ uk fel tov´ abb´ a, hogy lnko(m, ϕ(s)) = 1. Defini´ aljuk a P = {P (X) : deg(P (X)) = n ≥ 4, r¨ ogz´ıtett } polinom halmazt ´es az ) ( n Y Li (X), mods) MNFF = NP,s : Zm s 7→ Zs ; NP,s (X) = ( i=1

P ∈P

f¨ uggv´eny csal´ adot, ahol 3 ≤ m ≤ n, ´es az L(i) (X) defin´ıci´ oja ugyanaz, mint kor´ abban. Az al´abbi t´etelt nyerj¨ uk: 10. T´ etel. Ha minden P (X) ∈ P polinomhoz tartoz´ o NP,s f¨ uggv´eny teljes´ıti az SMNA-t, akkor az MNFF f¨ uggv´eny halmaz egy egyir´ any´ u hash f¨ uggv´eny csal´ ad. 14

5. Megjegyz´ es. A fentihez hasonl´ o m´ odon lehet az NP f¨ uggv´eny alkalmaz´ as´ aval megkonstru´ alni az NFF f¨ uggv´enycsal´ adot, amelyr˝ ol bizony´ıtani lehet, hogy SNA eset´en az NFF egy egyir´ any´ u f¨ uggv´enycsal´ ad. Megvizsg´aljuk, hogy mik´ent kell megv´alasztani a P (X) polinomot, hogy a lehet˝o legegyszer˝ ubben lehessen sz´amolni a f¨ uggv´eny´ert´eket. Legyen P (X) := X n − 1 u ´gy, hogy n ≥ 3. Jel¨olje ζ ennek egy gy¨ok´et ´es legyen L(X) := X1 + ζX2 + · · · + ζ n−1 Xn . A ζ j L(X) = Xn−j+1 +ζXn−j+2 +· · ·+ζ j−1 Xn +ζ j X1 +· · ·+ζ n−1 Xn−j egyenletb˝ol, amely minden 1 ≤ j ≤ n eset´en fenn´all, l´athat´ o, hogy az NP,s (X) egy   X1 X2 . . . Xn Xn X1 . . . Xn−1    . . . . . . . . . . . . . . . . . . . . X2 X3 . . . X1 ciklikus m´atrix determin´ansa, amely nagyon egyszer˝ u form´aj´ u. m−1 Ha L(X) = X1 + ζX2 + · · · + ζ Xm , ahol m < n, akkor Xm+1 , . . . , Xn helyett minden sorban n − m darab 0 ´all, de a determin´ans ´ert´eke nem lesz 0, csak a form´aja lesz m´eg egyszer˝ ubb. V´eg¨ ul egy rekurz´ıv hash f¨ uggv´enyt konstru´ alunk az NP,s (x1 , ..., xm ) f¨ uggv´eny alkalmaz´as´aval. Legyen adott az M u ¨zenet, amelyet egy tetsz˝oleges hossz´ us´ ag´ u bin´aris sz´onak tekint¨ unk. Ezt sz´etv´agjuk x1 , ..., xk r´eszszavakra u ´gy, hogy minden xi (1 ≤ i ≤ k) egy eg´esz sz´amot reprezent´ aljon az [1, s − 1] intervallumban. Tegy¨ uk fel, hogy k ≥ m, egy´ebk´ent pedig eg´esz´ıts¨ uk ki a sorozatot null´akkal. El˝osz¨ or defini´aljuk a h(x1 , . . . , xm ) := NP,s (x1 , . . . , xm ) 15

kezd˝ o´ert´eket, majd pedig legyen rekurz´ıv m´odon h(x1 , . . . , xm+t(m−1) ) := NP,s (h(x1 , . . . , xm+(t−1)(m−1) ), xm+(t−1)(m−1)+1 , . . . , xm+t(m−1) ). Ha k valamely alkalmas t ∈ Z sz´amra nem m+t(m−1) alak´ u, akkor eg´esz´ıts¨ uk ki az M u ¨zenetet 0-val, mindaddig, m´ıg k megfelel˝ o alak´ u lesz. ´Igy kapunk egy gyakorlatban is haszn´alhat´ o h egyir´any´ u hash f¨ uggv´enyt. Ez a f¨ uggv´eny minden iter´aci´ os l´ep´esben megtartja u ¨tk¨ oz´esmentes tulajdons´ag´ at ´es sejthet˝oen rendelkezik lavina hat´assal is (l´asd 8. T´etel ´es 3. Sejt´es). Ezek a tulajdons´agok garant´ alj´ ak biztons´agos haszn´alat´ at. Az ´ertekez´es tartalmaz m´eg k´et konkr´et sz´am´ıt´ asi p´eld´ at, amely bemutatja, hogyan haszn´alhat´ o a h f¨ uggv´eny egyir´any´ u hash f¨ uggv´enyk´ent a kriptogr´afiai gyakorlatban.

Summary In this thesis we present a new one-way function with collision resistance and avalanche effect. The security of this function based on the difficulty of solving a general norm form equation. Let P (X) ∈ Z[X] be a monic polynomial of degree n ≥ 3 having no multiple roots. Denote by α1 , . . . , αn the roots of P and put L(i) (X) :=

m X

αij−1 Xj

for i = 1, . . . , n and m ≤ n.

j=1

Define the norm form corresponding to the polynomial P by NP (X) :=

n Y i=1

16

L(i) (X).

In fact, NP (X) is a generalization of the concept of norm form and is a special decomposable form. Define the mapping NP : Zm → Z in the following way: NP : (x1 , . . . , xm ) 7→ NP (x1 , . . . , xm ). Since NP (X) is a homogeneous polynomial of degree n, with integer coefficients the function value NP (x) will be a rational integer for every x ∈ Zm . Let p and q be primes such that q > p > q/2 and s := pq. Define the mapping NP,s : Zm s → Zs in the following way: NP,s : (x1 , ..., xm ) 7→ NP (x1 , . . . , xm ) (mod s). We present three algorithms for the calculation of the value NP (x) and NP,s (x). Their complexity are discussed and the running time of their imlementations in MAPLE are compared. And so we proved that the value NP (x) and NP,s (x) can be computed efficiently. Denote by Pcoll = P [NP,s (x) = NP,s (y) : x, y ∈ Zs m ] the probability of the collision for the function NP,s . Our main result is the following two theorems. Theorem 7 Let P (X) ∈ Z[X] be a monic polynomial of degree at least 3 having no multiple roots. Let p and q be primes such that q > p > q/2 and s := pq. Suppose that gcd(m, ϕ(s)) = 1. Let N (P, b, s) denote the number of solutions of the congruence NP (x1 , . . . , xm ) ≡ b (mod s). • If gcd(b, s) = 1 we have 1

|N (P, b, s) − sm−1 | < c1 (P )sm−1− 4 • othervise N (P, b, s) < c2 (P )sm−1 . 17

Theorem 8 Let P (X) ∈ Z[X] be a monic polynomial of degree at least 3 having no multiple roots. Let p and q be primes such that q > p > q/2 and s := pq. Suppose that gcd(m, ϕ(s)) = 1. Then the probability of collision Pcoll for the function NP,s satisfies the inequality C Pcoll < , s where the constant C depends only on the polynomial P . We tested a MAPLE implementation of the function NP,s (x) and we can showed that this function has avalanche effect. We construct an application, which uses this function as a oneway hash function. This application can check passphrase of user of a computer. An other application makes the hash value of a message. So we propose to apply the function NP,s in the practice of the cryptography as a one-way hash function. Further we found also some fact, which show that NP,s is probably a family of one-way functions.

Hivatkoz´ asok [1] A. Baker, Contributions to theory of diophantine equations I. and II., Phil. Trans. Roy. Soc. London Ser A., 263 (1968) 173-208. ´rczes, J. Ko ¨ dmo ¨ n, Methods for the calculation of [2] A. Be values of a norm form, Publ. Math. Debrecen, 63 (2003), 751-768. ´rczes, J. Ko ¨ dmo ¨ n, A. Petho ˝ , A one-way func[3] A. Be tion based on norm form equations, Periodica Math. Hungar. (megjelen´es alatt). 18

[4] J. Black, S. Halevi, H. Krawczyk, T. Krovetz, P. Rogaway, UMAC: Fast and Secure Message Authetication, In Advances in Cryptology - CRYPTO ’99 (1999), vol. 1666 of Lecture Notes In Computer Science, Springer-Verlag, pp. 216-233. [5] J. Buchmann, S. Paulus, A one-way function based on ideal arithmetic in number fields, Lect. Notes Comput. Sci. 1294 (1997), 385-394. [6] L. Cerlienco, M. Mignotte, F. Piras, Suites r´ecurrentes lin´eaires. Propri´et´es alg´ebriques et arithm´etiques. (Linear recurrent sequences. Algebraic and arithmetic properties), L’Enseign. Math. 33 (1987), 67-408. [7] H. Cohen, A course in computational algebraic number theory, Springer Verlag, 1993. ´kes E., Surja ´ n Gy., ugyi informatika, Szerk: Ke [8] Eg´eszs´eg¨ ´ nyi L., Kozmann Gy., Medicina K¨onyvkiad´ Balka o, 2000. [9] O. Goldreich, L. Levin, N. Nisan, On constructing 1-1 one-way functions, Electronic colloquium on computational complexity, TR-95-029, 6/25/95, 1995. [10] S.Goldwasser, M.Bellare, Lecture Notes on Cryptography, MIT Press, Cambridge, Massachusetts 2001. [11] Handbook of medical informatics, Eds: J. H. van Bemmel, M. A. Musen, Springer Verlag, 2002. ¨ dmo ¨ n J., Kriptogr´ [12] Ko afia, Az informatikai biztons´ ag alapjai, A PGP kriptorendszer haszn´ alata, ComputerBooks K¨onyvkiad´o, 1999. ¨ dmo ¨ n J., Adatv´edelem, adatbiztons´ ag az eg´eszs´eg¨ ugyben, [13] Ko Lege Artis Medicinae 4, (1997), 278-281. 19

¨ dmo ¨ n J., Az eg´eszs´eg¨ [14] Ko ugyi adatv´edelem szab´ alyoz´ asa, Orvosi Hetilap 140 (1999), 1113-1115. [15] S. Lang, A. Weil, Number of points of varieties in finite fields, Am. J. Math. 76 (1954), 819-827. [16] Y.V.Matiyasevich, Press,1993.

Hilbert’s

Tenth

Problem,

MIT

[17] A.J.Menezes, P.C.van Oorschot, S.Vanstone, Hadbook of Applied Cryptography, CRC Press, 1997. [18] J. Patarin, Secret public key schemes, In:Public-Key Criptography and Computational Number Theory, (ed. by K. Alster, J. Urbanowicz and H. C. Williams), 221-237. Walter de Gruyter, 2001. ˝ , Algebraische Algorithmen, Vieweg Verlag,1999. [19] A.Petho ´dei, Algebra I, Akademische Verlagsgeselschaft Geest [20] L. Re & Portig K.-G., Leipzig, 1959. [21] B. Schneier, Applied Cryptography, John Wiley & Sons, 1996. [22] N.P.Smart, How Difficult is it to Solve a Thue Equation?, In ANTS-2, LNCS 1122, 363-373, 1996. ¨ [23] A. Thue, Uber Ann¨ aherungswerte algebraischer Zahlen, J. Reine Angew. Math. 135 (1909), 284-305. [24] N. Tzanakis, B.M.M. de Weger, On the practical solution of the Thue equation, J. Number Theory, 31 (1989), 99-132. [25] D.L. Whiting, M.J. Sabin, Montgomery Prime Hashing for Message Authentication, CT-RSA 2003 (ED: M. Joye), LNCS 2612, pp. 50-67, Springer-Verlag, 2003.

20