Szakmódszertan
PRÍMSZÁMOK ÉS A TITKOSÍRÁS Meszéna Tamás Ciszterci Rend Nagy Lajos Gimnáziuma és Kollégiuma, Pécs,
[email protected], az ELTE Fizika Tanítása doktori program hallgatója ÖSSZEFOGLALÁS Úgy tapasztaltam, széles körben ismert az a tény, hogy a manapság használatos titkosítási eljárások a prímszámokhoz kötődnek. Arról azonban sokkal kevesebb embernek van elképzelése, hogy pontosabban milyen kapcsolat van e két dolog között, pedig az elv középiskolás szinten is elmagyarázható. Erre teszek kísérletet a következő cikkben egy konkrét, kis számokat használó példán keresztül. BEVEZETÉS Középiskolai tanárként szinte mániákusan keressük azokat a témákat, melyek saját tantárgyunkban szélesebb rétegek számára is érdekes lehet. Biztosan ilyen a titkosírás, mely mindig megmozgatja a diákok fantáziáját. Könnyen elérhető, óriási irodalma van, miután több ezer éves történelemmel rendelkezik. Éppen ezért ideális területe az önálló kutatómunkának, többen tudnak egyidejűleg foglalkozni vele, hiszen van akit a középkor, van akit a II. Világháború érdekel inkább.
1. ábra. A Rononci-kódex és az Enigma: a németek által a II. Világháborúban használt titkosító gép.
Aki a diákok közül nem próbálta még, lelkesen szokta kipróbálni, hogyan lehet kézzel, írásban megfejteni pár soros, tetszőleges szöveget, amit egyszerű helyettesítéses eljárással kódolt valamelyik társuk.
335
Szakmódszertan
2. ábra. Július Cézár titkosítási eljárása egyszerű eltolással.
Érdemes a diákokkal beszélnünk arról, mekkora segítséget jelent egy hosszabb általános szöveg megfejtéséhez, ha ismerjük a nyelvet, amelyen íródott, és az adott nyelv betűinek gyakoriság táblázatát használjuk a megfejtéshez. Később, nehezítésképpen, kódolhatunk egymásnak olyan szövegeket, melyek a magyar nyelv gyakoriság értékeitől lényegesen eltérő betűösszetétellel rendelkeznek. FELTŰNNEK A PRÍMSZÁMOK G. H. Hardy (1877-1947), a prímszámok elméletének egyik legkiemelkedőbb kutatója a XX. század első felében, ezt írja Egy matematikus védekezése című könyvében: Soha nem tettem semmi "hasznosat". Semelyik felfedezésem sem volt, és nem valószínű, hogy valaha is legyen, közvetlenül vagy közvetve, jó vagy rossz hatással a világ folyására... Hardy véleményével szemben ma a prímszámok jelentik a diplomáciai, gazdasági, katonai titkosítás alapját. 1977-ben született meg az RSA prímszámalapú titkosírási rendszer, mely elnevezését a három felfedező matematikus vezetéknevének kezdőbetűi után kapta.
3. ábra. Ronald R. Rivest, Adi Shamir, Leonard Adleman. [3] Eljárásuk lényegét szeretnénk bemutatni, ami kis számokkal egyszerűen végigszámolható, megérthető.
336
Szakmódszertan SZÜKSÉGES MATEMATIKAI FOGALMAK, TÉTELEK [1] A gimnáziumi tananyagon túlmenően szükségünk van néhány fogalomra, tételre, melyek bizonyítása, részletes vizsgálata nem szükséges a módszer megértéséhez, elegendő puszta ismeretük. Először is a kongruencia fogalmát kell megismerni, amit egy egyszerű példán keresztül rögtön megértethetünk. A 17 ≡ 2 (mod 5) annyit jelent mindössze, hogy a 17 5-tel osztva ugyanazt a maradékot adja, mint a 2, vagyis a 17 kongruens a 2-vel mod 5. A kongruenciákra vonatkozó Kis Fermat-tétel kimondja: ha a-val egy tetszőleges egész számot jelölünk, és p prím, akkor ap ≡ a (mod p). Nem kell bizonyítanunk a tételt, de egy példán ellenőrizve a jelentése világosabb lesz, és közben megismerjük, gyakoroljuk a kongruenciákkal való számolást. A Kis Fermat-tétellel összefüggő Euler-tétel speciális esete: Ha k ≡ 1 (mod (p – 1)(q – 1)), ahol p,q prímszámok, akkor ak ≡ a (mod pq). Itt is érdemes egyszerű számolással ellenőrizni egy esetet, közben barátkozni az állítással. AZ RSA NYILVÁNOS KULCSÚ TITKOSÍRÁS Az eljárás lényege a következő: Választunk két prímszámot: p és q, ezeket összeszorozzuk: n = pq. Keresünk olyan k számot, amely 1 maradékot ad (p -1)(q – 1)-gyel osztva. Utána k-t felbontjuk két szám szorzatára: k = ed, ahol az e számot használjuk a kódoláshoz (encoding), és d-t a dekódoláshoz .
4. ábra. Kódolás - dekódolás. Kis számokkal végig számolva ez a következő módon néz ki: Legyen p = 19 és q = 13, ekkor n = pq = 247, (p – 1)(q – 1) = 18 ∙ 12 = 216. k = 217; k = ed alapján pl. 217 = 7 ∙ 31, vagyis e = 7 és d = 31. Az üzenet, amit szeretnénk kódolva elküldeni, legyen mondjuk: HELLO, amit számsorozattá kell alakítani. Erre a célra használhatjuk akár az ASCII kódokat, de saját készítésű kódtáblával talán még érdekesebb. 1. táblázat. Az ABC betűi, és nekik megfelelő kódok a
b
c
d
e
f
g
h
i
j
k
l
m
n
O
p
q
r
S
t
u
v
w
x
y
z
vége
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
337
Szakmódszertan Ezzel a kódolással a következőt kapjuk: HELLO 7 4 11 11 14 26 Ha b = üzenet, és c = kódolt üzenet, akkor c-t úgy kapjuk, hogy c ≡ be (mod pq) teljesüljön. Ekkor: 77 ≡ 45 (mod 247) 47 ≡ 82 (mod 247) 117 ≡ 106 (mod 247) 147 ≡ 79 (mod 247) 267 ≡ 26 (mod 247) [2] A kódolt üzenet így alakul tehát: 45 82 106 106 79 26 A dekódolás a következő módon történik: ha c = kódolt üzenet, és b = dekódolt üzenet, akkor b-t úgy kapjuk, hogy b ≡ cd (mod pq) teljesüljön. Vagyis ki kell számítani, hogy 4531 ≡ ? (mod 247). Ez zsebszámológéppel több lépésben könnyen elvégezhető, és azt kapjuk, hogy: 4531 ≡ 7 (mod 247). Majd hasonlóképpen: 8231 ≡ 4 (mod 247) 10631 ≡ 11 (mod 247) 7931 ≡ 14 (mod 247) 2631 ≡ 26 (mod 247). [2] A dekódolt üzenet így: 7 4 11 11 14 26, vagyis HELLO! Könnyen látható, azért kapjuk vissza az eredeti számsorozatot, mert az Euler-tételt alkalmazzuk: kiindulunk b-ből, kódoljuk, c = be, majd ezt dekódoljuk, (be)d = bk ≡ b (mod pq), ami az eredeti üzenet. Ez így persze egyszerű helyettesítő eljárás lenne (jól elbonyolítva), ami a gyakoriság táblázatok alapján gyorsan megfejthető. Ez a probléma azonban könnyen kiküszöbölhető a számsorozat egybeírásával, majd meghatározott egységekre bontásával. AZ RSA A VALÓSÁGBAN Minden titkosírásnál kell legyen titokban tartott információ. Aki megszerzi ezt a titkos információt, az meg tudja fejteni a kódolt üzenetet. Nem ismétlődő elemeket tartalmazó kódkönyv segítségével elvileg feltörhetetlen titkosítás készíthető. Ezeknek a könyveknek a biztonságos előállítása, szállítása és őrzése azonban nagy kockázatot jelent. Ezért különösen jó, hogy ennél az eljárásnál csak d értékét kell féltve őrizni. Mindössze egyetlen egy szám! Valójában p és q prímek a 100 számjegyű nagyságrendbe esnek, így n 200 számjegyű lehet. Nyilvánosságra hozzuk n és e értékét (a példánkban 247 és 7), így bárki tud kódolt üzenetet küldeni, mivel a kódoláshoz nincs másra szükség, mint a számsorozattá alakított üzenet egységeit hatványozni, és a hatványokról megállapítani az n-nel való osztás maradékát. Akinek az üzenetet küldtük, az ismeri (a nyilvános n és e értékén kívül) d értékét is. A megérkezett kódot egységenként d-edik hatványra emeli, kiszámítja az n-nel való osztás maradékát, és visszakapja az eredeti üzenetet. Aki nem ismeri d értékét, mert előle eltitkoltuk, de fel akarja törni a titkosítást, annak a megfejtéshez, dekódoláshoz tehát d értékére van szüksége. (Vegyük észre, hogy d értéke nélkül még az sem tud üzenetet dekódolni, aki rendszeresen kódol üzeneteket n és e ismeretével.) Ennek meghatározásához k-t kell ismerni, hiszen k = ed. A k értéke egyébként 338
Szakmódszertan nem egyértelmű, mert több ilyen tulajdonságú szám is lehet, de minden k érték egyformán jó, ami teljesíti a megadott feltételt, A k számot p és q értékéből kaphatjuk meg, mivel k ≡ 1 (mod (p – 1)(q – 1)). Vagyis n-t kell prímtényezőire bontanunk, hogy megkapjuk p és q értékét. Ezt nevezzük faktorizációnak, amikor az n összetett számot akarjuk prímtényezőire bontani. Ebből látszik: a titkosított szöveg megfejtése attól függ, fel tudunk-e bontani egy ismert számot prímtényezőire. FAKTORIZÁCIÓ A faktorizációra az ókor óta ismert módszer az Erathosztenészi szita. Ennél elegendő a prímosztókat vizsgálni az n szám négyzetgyökéig, de nagy számokra így sem elég hatékony. A felbontási módszerek alapkérdése a lépésszám: vagyis hogyan függ a felbontáshoz szükséges lépések száma n-től? Azok a módszerek, amelyek n exponenciális függvényei, alkalmatlanok nagy számok faktorizálására. A matematikusok hihetetlen erőfeszítéseket tettek hatékonyabb algoritmusok kidolgozására, de a probléma nagyon nehéz. Néhány érdekesség a faktorizáció történetéből: 1874-ben úgy gondolták, a 10 jegyű 8 616 460 799 számot soha nem lesz képes az ember felbontani. Ezzel szemben az 1970-es években 20 számjegyig tudják elvégezni a felbontást, természetesen már a számítógépek segítségével. 1977 augusztusában jelenik meg a Scientific American-ben, hogy egy 129 jegyű számot, amit két prímszám szorzataként kaptak, (ezt nevezzük RSA 129-nek), évmilliókba telik faktorizálni. Itt p és q 64 számjegyű, és a cikkben 100 $-t ajánlottak egy, ennek a számnak a segítségével titkosított mondat megfejtéséért. [3] 1980-ban 50 számjegyig tudtak faktorizálni. 1991-ben érték el a 100 számjegyet a felbontásban 1994-ben faktorizálták az RSA 129-t. 1999-ben faktorizálták az RSA 155-t. [3] 2009-ben egy 232 jegyű számot egy év alatt faktorizáltak több száz számítógép összekapcsolásával, összesen 2000 év gépidő felhasználásával. IRODALOMJEGYZÉK 1. Freud─Gyarmati: Számelmélet, Nemzeti Tankönyvkiadó, 2000 2. Sramó B.: A titkosírás szerepe a XX. században, Gábor Ferenc pályázat, Ciszterci Rend Nagy Lajos Gimnáziuma, Pécs, 2009. 3. http://www.acm.org/fcrc/PlenaryTalks/rivest.pdf 4. http://home.fazekas.hu/~Isuranyi/2010_11_eloadasok/Titkosiras_1.pdf 5. http://matek.fazekas.hu/portal/kutatomunkak/codes/codesm.html 6. http://www.cs.elte.hu/blobs/diplomamunkak/alkmat/2011/gerbicz_robert.pdf
339
