Az RSA titkosítás
ha
Nyílt kulcsú titkosításnak nevezünk egy E : A → B és D : B → A leképezés-párt, • bármely a ∈ A-ra D(E(a)) = a (ekkor E szükségképpen injektív leképe-
zés),
• E ismeretében E(a) könnyen számítható, • E ismeretében D(b) nehezen határozható meg (b ∈ B ), • D ismeretében D(b) könnyen számítható (b ∈ B ). E a titkosítás nyílt, D pedig a titkos kulcsa.
A nyílt kulcsú titkosítás lényege, hogy üzenetet bárki küldhet a segítségével, azonban az üzeneteket csak akkor lehet 'gyorsan' megfejteni, ha ismerjük a titkos kulcsot is. Az RSA-módszer lényege, hogy keresünk két nagy prímszámot (mondjuk 100 jegy¶eket), legyenek ezek p és q . Legyen n = pq , és legyen e, d olyan, hogy (p − 1)(q − 1) | ed − 1. Nyilvános az n és e, titkos p, q és d. Itt a titkosítandó szavak az n-es maradékok, a titkosítás az e. hatványra emelés modulo n, a megfejtés pedig a d. hatványra emelés. Legyen x ∈ N. Ekkor ha (x, n) = 1, akkor a Fermat-tétel szerint (xe )d ≡ xed ≡ 1 x ( mod n), hiszen ϕ(n) = (p − 1)(q − 1), vagyis ed ≡ 1 ( mod n). A titkosítás és a megfejtés gyors, hiszen a k. hatványra emelés nagyjából ln k id®be kerül. Jelenlegi ismereteink szerint a megfejtés d ismerete nélkül nehéz: lényegében csak próbálgatással lehetséges, vagyis ha meg szeretnénk fejteni egy üzenetet (y ∈ N szám), akkor végig kell próbálni az összes n-es maradékot, e. hatványra emelni ®ket, és megnézni, hogy y -t kapunk-e eredményül. Kérdés, hogy el® tudunk-e állítani gyorsan a feltételeknek megfelel® p, q, n, e és d természetes számokat. A f® nehézség nagy prímszámok el®állításában van. A nagy prímszámtétel szerint nagyjából minden 460. 100-jegy¶ szám prím, így ha egy számról gyorsan el tudjuk dönteni, hogy prím-e, akkor jó eséllyel 5 − 600 próbálgatás után találunk 100 jegy¶ prímet. Ezzel p, q és n adott. Ekkor megfelel® e és d az ed ≡ 1 ( mod (p − 1)(q − 1)) kongruencia megoldásával kapható (e szabadon választható a (p − 1)(q − 1)-hez relatív prím számok közül). A fenti titkosítás biztonsága els®sorban azon a tényen múlik, hogy nagy (100 jegy¶) számok prímtényez®s felbontásának meghatározása jelen ismereteink szerint nagyon lassú (hiszen p és q ismeretében d már könnyen meghatározható). Az RSAmódszer kis módosításával elérhet®, hogy a módszer hatékony feltörése ekvivalens legyen az összetett számok felbontásával (elvileg el®fordulhat, hogy valaki meg tudja oldani az xe ≡ y kongruenciákat n felbontása nélkül is). Kérdés azonban, hogy el tudjuk-e dönteni nagy számokról, hogy prímszámok-e. Erre az els® ötletet a Fermat-tétel adja, hiszen ha p prím, akkor bármely a < p esetén ap−1 ≡ 1 ( mod p). Ez ad egy próbára lehet®séget: ha adott n, megviszgáljuk, hogy egy n-nél kisebb x maradékra xn−1 ≡ 1? Ha nem, akkor n biztosan összetett, azonban ha 1, akkor semmit nem állíthatunk. Sajnos nem segít, ha akár sok maradékot is megvizsgálunk, ugyanis vannak olyan n összetett számok, melyekre minden, n-hez relatív prím x esetén xn−1 ≡ 1 (ezek a Carmichael számok). Ugyanakkor az ötlet továbbfejleszthet®... Miller-Rabin prímteszt
Legyen n természetes szám. Kérdés, hogy n prímszám-e. 1
2
Ha p prímszám, akkor persze xp−1 ∼ = 1 bármely x < p-re. Azonban p − 1 páros szám (a 2-t nem valószín¶, hogy bárki tesztelni szeretné), legyen d = p−1 2 . Ekkor (xd )2 ∼ = 1. Azonban modulo p csak két négyzetgyöke van az 1-nek: 1 és −1. Vagyis xd ∼ = 1 vagy xd ∼ = −1. Az els® esetben ha d is páros, az el®z® megismételhet®, és így tovább. Összefoglalva: ha p prímszám, akkor legyen p − 1 = 2k t, ahol t páratlan. Ekkor k bármely x < p maradék esetén az xt , x2t , x4t , . . . , x2 t számokra igaz, hogy vagy i mindegyik kongruens 1-gyel modulo p, vagy pedig van olyan i < k, melyre x2 t ≡ −1. Legyen most n tetsz®leges páratlan természetes szám, és legyen n − 1 = 2k t. De níció: Az x maradékot jó maradéknak nevezzük modulo n, ha bármely k esetén az xt , x2t , x4t , . . . , x2 t számokra igaz, hogy vagy mindegyik kongruens 1i gyel modulo p, vagy pedig van olyan i < k, melyre x2 t ≡ −1. Például modulo 21 a 7 nem jó maradék, hiszen 75 ≡ 7, 710 ≡ 9, 720 ≡ 1. Itt igaz, hogy az n − 1. utolsó hatvány 1-gyel kongruens, azonban az el®tte lév® nem −1-gyel, hanem 9-cel kongruens.
1. Tétel.
Legyen n páratlan szám. Ha n prím, akkor az összes nemnulla n-es maradék jó maradék. Ha azonban n összetett szám, akkor a nemnulla n-es maradékok legalább 43 -e rossz maradék.
A fenti tétel lehet®vé tesz egy nem determinisztikus, azonban elég gyors prímtesztet. Ez a Miller-Rabin teszt: ha n természetes szám, választunk egy n-es maradékot, és megnézzük, hogy az jó-e. Ha nem jó, akkor n összetett szám. 100 maradékot tesztelve, ha van köztük rossz, akkor persze n természetes, ha viszont nincs, akkor 100 azt állítjuk, hogy n prím. Ebben az esetben az el®z® tétel szerint 41 < 10−60 valószín¶séggel tévedünk, ez pedig már elhanyagolhatóan kicsi. 1. Algebrai kódok
Ajánlott irodalom: Czédli Gábor: Boole-függvények
2. De níció. 3. De níció.
A továbbiakban
2 jelöli a {0, 1} halmazt.
Kódolásnak nevezünk egy E : 2n → 2m leképezést. A halmazt a kódszavak halmazának, vagy röviden kódnak nevezzük.
C = E(2n )
A továbbiakban E mindig egy 2n -b®l 2m -be men® leképezés lesz, C = E(2n ).
4. De níció. olyan
D: S →
Legyen S = C vagy S = 2m . Dekódolófüggvénynek nevezünk egy 2m leképezést, amelyre y = D(E(y)) teljesül bármely y ∈ 2n esetén.
A hibajavító / hibajelz® kódolások lényege, hogy ha valaki egy bizonyos y n hosszú bitsorozatot szeretne eljuttatni valahova egy olyan adattovábbító csatornán, mely egy adott 0 < p < 12 valószín¶séggel ront el minden egyes bitet (most feltesszük, hogy a továbbított bitek száma megegyezik a küldött bitek számával), akkor nem y -t küldi el, hanem E(y)-t, amely (esetleg hibásan) megérkezik a címzetthez. A címzett ezután végrehajtja E(y)-on az általa is ismert D dekódolófüggvényt, így megkapja y -t. Ha azonban E(y) hibásan érkezik meg, el®fordulhat, hogy E(y) ∈ / C . Ekkor dekódolás közben a címzett érzékeli, hogy hiba történt az adattovábbításban (ekkor kérheti az adatok ismételt elküldését). Ha nem túl sok hiba történt, akkor esetleg a hibákkal együtt is dekódolni tudja a küldeményt. A továbbiakban a 'nem túl sok' kifejezést járjuk jobban körül.
3
5. De níció. Az E kódolást k-hibajelz®nek nevezzük, ha dekódoláskor minden olyan hibára fény derül, ahol legfeljebb k darab bit került hibásan továbbításra, másrészt viszont van olyan k +1 hibás bitet tartalmazó üzenet, melyben a hiba nem mutatható ki. 6. De níció.
Az E kódolást k -hibajavítónak nevezzük, ha dekódoláskor minden olyan hiba kijavítható, ahol legfeljebb k darab bit került hibásan továbbításra, másrészt viszont van olyan k + 1 hibás bitet tartalmazó üzenet, melyet rosszul javít ki.
Legyen n = 3, m = 4. Egy kódolás lehet, hogy egy 3-hosszú sorozat helyett azt a 4-hosszú sorozatot küldjük el, melynek utolsó bitje a sorozatban szerepl® egyesek paritása. Tehát például E(101) = 1010, de E(111) = 1111. A dekódolás egyszer¶: le kell vágni az üzenet utolsó bitjét. Könnyen látható, hogy itt ha csak 1 bit kerül hibásan továbbításra, akkor észrevesszük a hibát (ekkor az utolsó bit paritása nem lesz megfelel®). Azonban ha már kett® bit hibádzik, akkor a dekódolás már nem érzékel hibát, hiszen a paritás változatlan marad. Vagyis a fenti "levágjuk az utolsó bitet" dekódolás 1-hibajelz®. Vegyük észre, hogy ezen kódolás esetén nemigen van lehet®ség hibajavító dekódolást alkalmazni (képtelenség kitalálni, melyik bit sérülhetett meg). Általában lehet bármely n esetén paritásellen®rz® kódolást alkalmazni. Legyen most n = 2, m = 6. Ekkor a 6-szoros ismétléskód az az E leképezés, amely az ab bitsorozathoz az aaaaaabbbbbb bitsorozatot rendeli. Itt a dekódolás: a "többség dönt", vagyis az els® hat bitb®l megnézzük, melyik szerepelt többször, majd a következ® 6-ból is, majd ez lesz a dekódolás (döntetlen esetén mondjuk mindig 0-át adunk). Ez az ismétl®kód 2-hibajavító: ha csak 2 bit sérül, akkor mindig visszakapjuk a küldeményt, azonban ha már 3, akkor nem biztos, például ha az 11 sorozatot szeretnénk továbbítani, és hiba miatt a 010101111111 sorozat érkezik meg, akkor a dekódolás 01-et szolgáltat. Természetesen a fenti példa általánosítható, így beszélhetünk k-szorozó kódolásról. Könny¶ belátni, hogy a k-szorozó kódolás k−1 2 -hibajavító.
7. De níció.
Legyen i, j ∈ értjük. Jele: d(i, j). Adott C, x 6= y} értéket.
8. Tétel.
2m . Ekkor i és j távolságán az eltér® bitek számát C kód esetén d(C, C) jelöli a min {d(x, y) : x, y ∈
d függvény távolságfüggvény, vagyis bármely x, y, z ∈ 2m esetén d(x, z) ≤ d(x, y) + d(y, z), valamint d(x, y) = 0 ⇔ x = y . A
Bizonyítás: Triviális, az x és z közötti eltérések száma nem lehet nagyobb, mint az x és y , illetve az y és z közötti eltérések számának összege (ha egy bitben eltérés van, akkor ez az eltérés megjelenik x és y , vagy y és z között).
9. Tétel.
hibajavító.
Legyen
d = d(C, C). Ekkor az E kódolás (d −
1)-hibajelz® és d−1 2 -
Bizonyítás: Ha a küldött bitsorozat, és a megkapott bitsorozat d − 1-nél nem kevesebb helyen tér el, akkor a fogadó észleli a hibát, hiszen a kódszavak minimális távolsága d, így egész biztos, hogy ha d − 1-nél nem több bit kerül hibásan továbbításra, akkor nem kódszót kapunk. Ugyanakkor ha már d bit sérül, akkor el®fordulhat, hogy a hibásan továbbított bitsorozat is kódszó lesz, így a dekódoló
4
nem észleli a hibát. A hibajavítás hasonlóképpen megy: ha csak d−1 2 db bit sérül, akkor észlelvén a hibát, a dekódoló megkeresi a kódolandó üzenethez legközelebb es® kódszót. Mivel bármely két kódszó távolsága legalább d, ezért ez a legközelebbi kódszó egyértelm¶, és megegyezik a küldött szóval, ha viszont d−1 2 -nél több bit sérül, akkor már el®fordulhat, hogy a dekódolás tévedést eredményez. A kódoláselméletet megalapozó f® tétel a következ®.
10. Tétel.
(Shannon) Legyen 0 < p < 21 , q = 1−p és e > 1 úgy, hogy e−1 < 1+p log2 p+q log2 q . Ekkor tetsz®leges pozitív -hoz van olyan n0 ∈ N, hogy bármely n0 ≤ n ∈ N esetén létezik olyan E : 2n → 2[en] kódolás, hogy p hibaesélyes továbbítás esetén hibajavító dekódolást alkalmazva minden egyes x ∈ 2n szó esetén a hibás dekódolás valószín¶sége -nál kisebb lesz.
Hamming - kódok
11. De níció.
A C kódot lineárisnak nevezzük, ha az E : 2n → 2m kódolás lineáris (mint Z2 feletti vektorterek közötti leképezés). A C kódot perfektnek nevezzük, ha d(C, C) = 2k + 1 páratlan és bármely x ∈ 2m esetén létezik olyan y ∈ C , amelyre d(x, y) ≤ k . Tehát egy kód perfekt, ha a kódszavak körüli k sugarú gömbök lefedik 2m -t.
12. De níció. Az x ∈ 2m kódszó hosszán a d(0, x) távolságot értjük. Jele: kxk. 13. Tétel. Ha a C kód lineáris, akkor d(C, C) = min {kxk : x ∈ C, x 6= 0}. Legyen 1 < r ∈ N, m := 2r − 1, n := m − r és de niáljuk az M = (mij ) m × r-es mátrixot úgy, hogy annak i-ik sora éppen az i szám kettes számrendszerbeli alakja legyen (szükség esetén balról nullákkal kiegészítve). Az E kódolás egy x = (x1 , x2 , . . . , xn ) ∈ 2n vektorhoz azt a z = (y0 , y1 , x1 , y2 , x2 , x3 , x4 , y3 , . . . , xn ) ∈ 2m
vektort rendeli, amelyre zM = 0. Tehát x bitjei közé jelz®biteket szúrunk be úgy, hogy yi éppen a z 2i -edik bitje legyen.
14. De níció. 15. Tétel. Az
A fenti kódolást az
r-edik Hamming-kódolásnak nevezzük.
r-edik Hamming-kódolás lineáris, perfekt kódolás, valamint a kódszavak közötti minimális távolság 3.
Bizonyítás: A kódolás egyértelm¶, hiszen az yi jelz®bitek a zM = 0 egyenletrendszerb®l egyértelm¶en (és könnyen) meghatározhatók. Könnyen ellen®rizhet®, hogy a minimális távolság 3, hiszen C -ben nincs 1, illetve 2 normájú elem, azonban 3 normájú van, mégpedig z = (1, 1, 1, 0, . . . , 0). A perfektség igazolása is egyszer¶.
BCH kódok
16. Tétel. (BCH kódok alaptétele) Legyen q egy prímszám, d és r pedig természetes számok úgy, hogy 1 < d < q r . Legyen α egy primitív elem a q r elemszámú testben, i = 1, 2, . . . , d−1-re pedig legyen gi (x) ∈ Zq [x] az αi minimálpolinomja. Jelölje g(x)
5
a gi (x) polinomok legkisebb közös többszörösét. Ekkor g(x) bármely 0-tól különböz®, q r −1-nél kisebb fokú Zq [x]-beli többszörösében legalább d együttható különbözik 0-tól.
17. De níció.
Legyen d, r ∈ N, 1 < d < 2r , legyen f egy r -edfokú olyan irreduZ2 felett, amelyre a Z2 [x]/(f ) test x eleme primitív (ilyen polinom mindig létezik). Legyen gi az xi ∈ Z2 [x]/(f ) test minimálpolinomja, és jelölje g a gi polinomok (1 ≤ i < d) legkisebb közös többszörösét. Legyen m olyan egész, amelyre g ∗ < m < 2r és legyen n = m − g ∗ . Ekkor az E : 2n → 2m , u 7→ ug kódolást (itt 2k elemeit polinomokkal azonosítjuk) a d minimális távolsághoz tervezett cibilis polinom
BCH-kódolásnak nevezzük (Bose, Chaudbury és Hocquenghem találmánya).
18. Tétel.
E lineáris kódolás, és a kódszavak közti minimális távolság legalább d.
A BCH-kódolás esetén a kódszavak a küldend® üzenetnél éppen g ∗ db bittel hosszabbak, ezért a kódolás annál hatékonyabb, minél nagyobbnak választjuk mmet (mondjuk éppen 2r − 1-nek), és minél kisebb g ∗ . Ezért fontos az alábbi észrevétel.
19. Tétel.
Páratlan
d esetén g ∗ ≤
r(d−1) . 2
