Prímszámkódolás Applet fejlesztése Java nyelven. Kaczur Sándor Gábor Dénes Főiskola Informatikai Intézet

Prímszámkódolás – Applet fejlesztése Java nyelven Kaczur Sándor Gábor Dénes Főiskola Informatikai Intézet [email protected] Absztrakt A titkosírással foglalkozó algoritmusok népszerűsége töretlen. A főiskolai hallgatók széleskörűen érdeklődnek a téma iránt, az egész egyszerű módszerektől kezdve az igen összetett adatszerkezeteket és bonyolult programstruktúrákat használó algoritmusokig. Egy LCMS-ben elkészített oktatóanyag alkalmazása esetén praktikus, ha abba szervesen beépül egy grafikus felhasználói felülettel rendelkező, azonnal kipróbálható, tesztelhető szoftver. Ezt biztosítja a Java Applet technológia. A cikk ismerteti egy hallgatói projektmunkaként elkészíthető, prímszámkódolást megvalósító alkalmazás tervezésének/elkészülésének folyamatát.

Bevezetés A Gábor Dénes Főiskola mérnök informatikus szakos hallgatói több féléven át tanulják a programozást Java nyelven. Ez két kötelező (Programozási alapok, Programozási technológia) és két – szoftverfejlesztési sávhoz kötődő – választható (Alkalmazásfejlesztés technológia, Elosztott alkalmazások) tantárgyat jelent. Programozási nyelvtől függetlenül oktatjuk az Objektumorientált szoftverfejlesztés tantárgyat, valamint külön a Vizuális programozás tantárgyat is. Tantárgytól és számonkérési módszertől függetlenül alkalmazzuk a projektmódszert. Ekkor a hangsúly nem magára a tanítási, tanulási folyamatra, hanem az önálló ismeretszerzésre helyeződik. Többféle célt határoztunk meg. Egyrészt a különböző szakmai tantárgyak tananyagához kapcsolódó problémák, részproblémák, módszerek, algoritmusok megértését követően azok gyakorlatban történő megvalósításához a hallgatók hatékony eszközként használják a programozási tantárgyakban megszerzett ismeretanyagot. Mindezt kisebb, esetleg egymásra épülő projektfeladatok kiadásával, csoportmunkára ösztönözve valósítjuk meg. Másrészt a csoportmunkában való együttműködés, a reproduktív, de inkább produktív gondolkodás, valamint a szükséges interdiszciplináris megközelítés sokféle szakmai és humán kompetenciát fejleszt. Harmadrészt az elkészült projektmunkák (esetleg TDK dolgozatok, szakdolgozatok) ismertetése jó megmérettetési, versenyeztetési lehetőséget biztosít. Negyedrészt a projektmunkák eredményei (publikáció, poszter, szakmai előadás, dolgozat, szoftver, elektronikus tananyag) minden hallgató számára hozzáférhetőek az ILIAS elektronikus távoktató rendszerünkben [1], így színesítik/bővítik a már meglévő oktatási segédanyagainkat. Prímszámkódolás Az algoritmus közismert [2-5]. Szükség van a feladó (adó, küldő, továbbító) és a címzett (vevő, fogadó) részéről két – lehetőleg nagy – prímszámra, legyen ez p és q. Ezeket titokban tartjuk, és legyen a=p*q. Legyenek e és f olyan számok, amelyekre e*f-1 osztható q-1 és p-1 értékkel. A rejtjelezéshez mindkét fél nyilvánossá teszi az a alapszámát és az e kódszámát, de titokban tartja f-et. Az üzenetet annak betűi sorszáma alapján számmá alakítjuk. Minden kapott szám kétjegyű lesz. A feladó a címzett e kódszámával az e-edik hatványra emeli a kapott kódszámokat, meghatározza a címzett alapszámával osztva a maradékot. Az üzenet végére odakódolja a saját titkos f számával dolgozva az aláírását. A címzett az üzenetet úgy dekódolja, hogy az a alapszáma mellett a titkos f számát használja az e helyett. A kapott szám az üzenet betűinek sorszáma lesz. Az aláírásnál a feladó nyilvános e számával dekódol. Tehát, ha a-val és e-vel kódoltunk, akkor

csak a-val és f-fel lehet megfejteni az üzenetet és fordítva. (Ez a két leképezés egymás inverze [4].) Projektfeladat 2-3 hallgató együttműködésével készüljön oktatóanyag a prímszámkódolás témakörben! A megjelenési formája legyen az ILIAS-ban elérhető elektronikus tananyag objektum! Az oktatóanyag a következő négy fejezetből álljon!  Az Elméleti háttér fejezet röviden, tömören ismertesse a prímszámkódolás alkalmazási területeit, az algoritmus működését, a kódolás és dekódolás folyamatát!  A Részletesen levezetett példa fejezet mutassa be egy kellően összetett, de még könynyen megérthető példán keresztül az algoritmus elemi lépéseit!  Az Elkészült program fejezet tartalmazza a Java Applet technológiával elkészült oktatóprogramot, amely részletesen bemutatja az algoritmus működését! Ezt kellően át kell gondolni! Kiemelten fontos a megfelelő objektumorientált szemlélet és a felhasználóbarát felhasználói felület (2. ábra)!  A Tesztkérdések fejezet biztosítson – megfelelő számú és változatosan elkészített tesztkérdések alkalmazásával, a témakörből való felkészültség esetén – önellenőrzési lehetőséget! Részprobléma: prímszám vagy sem? Különböző – egyre hatékonyabb – függvényeket készítve le kell tesztelni, hány lépésben kaphatjuk meg az 1 és 1000 közötti prímszámok számát. Csak az egyes függvényeken belüli lokális hatékonyság legyen fontos! Egy-egy függvény döntse el a paramétereként kapott számról, hogy prímszám-e! Tegyük fel, hogy a függvények csak pozitív egész paramétert kaphatnak! Néhány prímteszt függvény a megvalósításhoz (1. ábra):

1. ábra: Néhány prímteszt függvény megvalósítása Java nyelven

A hat különböző – egyre hatékonyabb – módon implementált függvény az alábbi lépésszámokat adja (ebben a sorrendben): 500500, 19615, 5288, 4780, 4457, 2019, természetesen ez csupán a ciklusok lépésszáma. Könnyen belátható, mennyire fontos szempont a hatékonyság ennél a feladatnál, a 168 prímszám megszámlálásához. Útban a specifikáció felé A feladat komplex, szerteágazó ismeretanyagot igényel. A megvalósításhoz többféle nézőpontból is hozzá lehet fogni. Az elméleti háttérben is különböző mélységekig lehet elmélyülni. Ezeket teljes összefüggésében látni kell, mert minden mindennel összefügg és kihat a megoldás – az oktatóanyag – minőségére. A megközelítés lehet algoritmus-, adatszerkezet-, feladattípus-orientált. A helyesség bizonyításához szükséges elméleti háttér [4] alapos ismerete – főleg a bizonyítás szintű megközelítés – az oktatóprogram megvalósításhoz nélkülözhető.

A megvalósításhoz átgondolandó szempontok:  Általában mit várunk egy oktatóprogramtól? Hogyan illeszkedik ez a prímszámkódolás szakterülethez? Milyen látens igényeink vannak/lehetnek?  Hogyan állítható elő a megfelelő p és q? Adott halmazbeli konstansok, vagy algoritmus generálja?  Mekkora legyen a p és q? Legfeljebb mekkorák lehetnek? Miért célszerű a felső korlát (pl.: 100)?  Bekérjük a felhasználótól p-t és q-t? Ha igen, ellenőrizni kell! Lehetnek egyformák?  Engedjük inkább ésszerű határok között kiválasztani p és q-t!  Milyen alapértelmezést célszerű felkínálni p-re és q-ra?  Célszerű az oszthatóság biztosítása miatt e-t és f-et a p és q ismeretében előállítani. Ez sok-sok számpár, tetszőlegesen lehet ezek közül választani?  Milyen karaktereket akarunk titkosítani/megfejteni? Mekkora a halmaz elemszáma? Különböznek-e a kis- és nagybetűk? Mi a jelkészlet? ASCII, unikód, egyéni? Bármi lehet (pl.: magyar ABC-beli nagybetűk, írásjelek nélkül), csak egyértelműek legyenek sorszámozhatók.  Milyen üzeneteket tud az adó küldeni a vevőnek? Előre elkészített, fix üzenetek közül lehet választani? Bármilyen üzenetet megadhat a felhasználó? Ha igen, tudni kell azt sifrírozni/desifrírozni úgy, hogy értelmes legyen!  Kell-e mindkét félnek aláírás? Milyen hosszú legyen az aláírás? Akár egy karakter is elegendő lehet.  Kell-e kivételt kezelni?  Előfordulhat-e túlcsordulás, egyéb számábrázolási probléma? Kell-e nagypontosságú aritmetikával dolgozni? Kell-e saját számtípust megvalósítani?  Milyen komponensek alkalmasak a felhasználói felület megvalósítására? Szövegmező, léptetőmező, lista, nyomógomb, rádiógomb, jelölőnégyzet, kombinált lista, panel...  Milyen praktikus, időben egymást követő lépésekben kell működnie a programnak?  Milyen Java Applet specifikus dolgok vannak? Milyen alapvető eltérések vannak/lennének egy konzolos, desktop vagy Midlet alkalmazással/megvalósítással szemben?  Igényelheti-e a megvalósítás saját komponens kifejlesztést? Mely esetben? Feltétlenül szükséges saját komponens? Ha igen, honnan célszerű leszármaztatni?  Milyen kompromisszumokat kell kötni az alkalmazáslogika és a GUI összefüggésében?  A megállapodások alapján merre tolódik a hangsúly? A fix prímszámok előállítása bármilyen eszközzel történhet, de kiegészítő adatszerkezetet igényel, amit karban kell tartani. A program által generált prímszámok, számpárok előállítása számítás- és időigényes lehet.  Milyen algoritmust célszerű írni annak eldöntésére, hogy egy szám prímszám-e? Miért lényeges ennek hatékonysága? Mekkora az algoritmus időigénye, tárigénye, bonyolultsága? Például: osztók megszámlálása 1-től n-ig, osztók megszámlálása 2-től gyök(n)-ig, osztók keresése 2-től egészrész(gyök(n))-ig, 2-nél kisebb egyenlő számok egyedi kezelése után osztók keresése 3-tól gyök(n)-ig kettesével, rekurzív módszer, Miller teszt [7], kis Fermat-tétel [8], Fermat-prímteszt [9], Lucas-Lehmer teszt [10], AKS-algoritmus [11].  A felhasználói felület egymással eseménykezeléssel összekapcsolt komponensei nagymértékben csökkenthetik a hibalehetőségeket. Például a feladó p és q prímszámának megadásával előáll az a, és a p-től és q-tól függő (csak a hozzájuk kiválasztható) megfelelő e és f számok. A vevőnél ugyanígy.

 

      

A felhasználói felület megfelelő sebességű frissítését is meg kell oldani! Hogyan lehet a léptetőmezőben csak prímszámokkal dolgozni? Eleve prímszámok vannak benne? Esetleg a léptetés a következő, illetve megelőző prímszámra ugrik? A prímszámok közötti különbség nem állandó, hogyan programozható ez a saját eseménykezelés? Milyen Look and Feel használata célszerű? Hogyan célszerű kialakítani a felületen a komponensek tulajdonosi hierarchiáját? Lehet, hogy egyszerre nem látszik minden? Milyen UML ábrá(ka)t célszerű készíteni a tervezés során, elősegítve a megértést és a későbbi „leprogramozást”? Milyen sztereotípusok alkalmazása célszerű? Hogyan praktikus a feladatot – egymásra épülő – részekre osztani? Milyen osztályokat kell megtervezni, létrehozni? Hány objektum együttműködése valósítja meg a programot? Milyen az ezek közötti kapcsolat? Teljes OO szemléletben készül-e/készült-e az oktatóprogram?

Az elkészült Prímszámkódolás oktatóanyag Az ILIAS-ra feltöltött Prímszámkódolás oktatóanyag több kapcsolódó tantárgy esetén is használható. Alkalmas arra is, hogy kiindulópontot nyújtson és mintát adjon a további hasonló projektmunkákhoz, azok specifikálásához.

2. ábra: A projektmunka eredménye, a Prímszámkódolás Java Applet az ILIAS rendszerben

Továbbfejlesztési lehetőségek Mivel a megvalósítás több szinten is történhet, így a továbbfejlesztési lehetőségek is szerteágazóak. Tipikus továbbfejlesztési igények:  Jelszavak, állományok titkosítása, megfejtése.  Kísérlet titkosított jelszavak, fájlok megfejtésére, teljesen hiányos vagy részben hiányzó adatokkal, természetesen behatárolt feltételek mellett (pl.: max. p és q) brute force módszerekkel.  Az oktatóprogram állítsa elő a levezett példát is.  Más – titkosíráshoz kötődő – algoritmusok megvalósítása: rácsrejtjelezés, abacus numeralis, geometriai kódolás, kínai abc (pl. [6] alapján).  Tetszőleges jelkészlet alkalmazási lehetősége az üzenetben, akár unikód karakterkészlet is.  Titkosított hálózati adatforgalom szimulációs szoftverének elkészítése (ez TDK témának is alkalmas és továbbfejleszthető szakdolgozattá is). Összegzés, tapasztalatok A hatékony projektmunkához elengedhetetlen, hogy a különböző felkészültségű és különböző szakterületben jártas hallgatók zökkenőmentesen tudjanak kommunikálni. Ehhez válogatni kell őket, a tanári orientáció feltétlenül szükséges. Ha kialakult egy-egy csoport, akkor megfelelő módon egymásra épülő részfeladatokra kell bontani a projektfeladatot és ki kell osztani a munkát. Előnyös, ha ez csoporton belül történik Nagyon fontos, hogy a hallgatók értsék egymás nyelvét, ehhez kellő gyakorlat vagy a részfeladatok közötti redundancia szükséges [12, 13]. Eddigi – hallgatói projektmunka koordinálásakor szerzett – tapasztalataim a következők:  Hatékony projektmunkára – sajnos – nem minden hallgató alkalmas.  Az elején – amíg szokatlan nekik ez a munkaforma – sokszor kell noszogatni, bátorítani a hallgatókat. Ekkor még motiválja őket a teljesítmény, a jobb jegy, esetleg a részteljesítés (10-50%).  Az elméleti háttér önmagában kevésbé motiválja a hallgatókat, ezen egy levezetett példával, esetleg – korábbi projektmunkaként elkészült – mintaprogrammal (nem forráskóddal!), tesztadatokkal lehet segíteni.  A specifikáció megértése vagy önálló elkészítése után már mindent bevetnek a hallgatók a megvalósítás érdekében. Ekkor már egymást biztatják és észre sem veszik, mennyi mindent megtanulnak a cél érdekében.  Mindig nagy izgalommal készülnek a hallgatók a végső bemutatóra, amikor elmondhatják, milyen problémákkal kerültek szembe a megvalósítás során és hogyan oldották meg azokat.  A hallgatók reálisan értékelik, pontozzák saját magukat és társaikat is, ebbe ritkán kell beavatkozni, többnyire csak a megerősítést, vagy a szakmai kiegészítést várják.  A kiadott projektfeladatoknak többféle nézőpontból megközelíthetőnek, gyakorlatiasnak, többféle nehézségi szinten megoldhatónak és kellően összetettnek kell lennie egyben. References [1] GDF ILIAS, https://ilias.gdf.hu, 2010.06.25. [2] RSA-eljárás, http://hu.wikipedia.org/wiki/RSA-elj%C3%A1r%C3%A1s, 2010.06.25. [3] Megdönthető-e az RSA algoritmus?, http://www.cs.elte.hu/~jaksy/elte/rsa/index.html, 2010.06.25.

[4] RSA algoritmus, http://www.inf.u-szeged.hu/~cimreh/n10alg28el.pdf, 2010.06.25. [5] RSA, http://en.wikipedia.org/wiki/RSA, 2010.06.25. [6] Révay Zoltán: Titkosírások (Fejezetek a rejtjelezés történetéből), Szeged, Lazi Bt., 2001, ISBN 963 9227 82 X, p. 300 [7] Primality Providing 2.3: Strong probable-primality and a practical test, http://primes.utm.edu/prove/prove2_3.html#MillersERHTest, 2010.06.25. [8] Primality Providing 2.2: Fetmat, probable-primality ans pseudoprimes, http://primes.utm.edu/prove/prove2_2.html#FLittleT, 2010.06.25. [9] Fermat-prímteszt, http://hu.wikipedia.org/wiki/Fermat-pr%C3%ADmteszt, 2010.06.25. [10] Lucas-Lehmer Test, http://mathworld.wolfram.com/Lucas-LehmerTest.html, 2010.06.25. [11] AKS-algoritmus, http://hu.wikipedia.org/wiki/Pr%C3%ADmteszt, 2010.06.25. [12] Pap-Szigeti Róbert: Módszertani lehetőségek a felsőoktatás megújításában, előadás, MFI Konferencia, 2008, Kecskemét [13] Tóth Péter Dr.: A problémamegoldó gondolkodás fejlesztésének módszertana, előadás, 2007, Budapest, http://www.fovpi.hu/data/cms42006/toth_peter_2007FPN.ppt, 2010.06.25.