Az One Time Pad titkosítás régóta érdekel. A matematikusok bizonyára megvetik, mint kutatásra és gondolkodásra nem érdemes eljárást - tényleg olyan egyszerű mint a faék, de Shannon azért érdemesnek találta matematikailag bizonyítani a feltörhetetlenségét.
Mivel érdekel a rádiókommunikáció, gondolatkísérletként elképzeltem, hogy a mai tárolókapacitások mellett reális lehetőség lehetne a digitalizált információ kódolása OTP eljárással. Egy 32Gbyte-os memóriakártya rendkívül hosszú ideig biztosíthatja a kódoláshoz/dekódoláshoz szükséges valódi véletlen jelfolyamot.
Amint az többször bebizonyosodott, semmi újat nem tudok kitalálni, a mellékelt linken egy katonai rádiót találtam ami egyéb trükkök mellett OTP titkosítást is használ.
A magam örömére csináltam egy One-Time-Pad titkosítót, a hexásítással összekombinálva .. inkább csak előtanulmánynak a témában. Itt a kódoló-dekódoló úgynevezett "deszkamodellje", amiből majd lehet komplett és grafikus izét csinálni - ha lesz időm rá.
mmormota úgy értette, hogy először titkosítod (zip, rar, stb.), aztán alakítod hexavá. Az előbbire használhatsz zip-et vagy rar-t, az utóbbira mondjuk yenc-et. Ezek mind igyenesek.
OK, köszönöm, de se időm se kedvem programot írni, vlami freeware kész alkalmazás kellene. Azután lehet hogy mégis rászánom magam egy egyszerű logika megírására.
Google nem igazán segít, csak file szintűeket találtam.
mert semmi nem garantálja, hogy egyszerű próbálgatással nem trafálok bele elsőre
Determinisztikus algoritmusra gondoltam. Azt akartam mondani, hogy a diszkrét logaritmus probléma mindenki kedvence, de azt csak sejtjük vagy tapasztaljuk, hogy ez a probléma algoritmikusan nehéz, de lehet, hogy valójában nem is nehéz.
D-vel, mint jelszóval indítsunk egy key-schedule-t, és abból olvassunk ki 2db N bites számot, a-t és b-t. keressük az alábbi egyenlet megoldását:
ax=b (mod p)
p egy prímszám amire p=2q+1, ahol q prímszám. ezt előre meg kell határozni, tulajdonképpen f paramétere, tehát f egy függvényosztály. adott implementációnál egy alkalmas méretű p választandó.
előzőleg meg kell vizsgálni, hogy a jó-e. nem jó, ha a2= {0, 1, q} (mod p). erre állítólag még gyorsabb megoldás is van, mint kiszámolni a négyzetet, de mindegy, mert az is gyors.
ha a jó, akkor a feladat kész van. ha a nem jó, akkor újabb számpárt olvasunk a key-schedule-ból, amig jó nem lesz.
legyen definíció szerint w(d0, n) a fenti sorozat n. tagja.
nevezzük
valamint W(d0, dn, n) = 1, ha w(d0, n) = dn és 0 ha nem. (azóta megtudtam, hogy ezek szerint w az NP és coNP metszetben van.) (és azt is, hogy emiatt nem érdemes NP teljes problémákat keresni, hacsak nem NP=coNP, de ez nem valószínű. de szerencsére nem is kell nekem NP teljes.)
w legyen P-n kívüli, kiszámítási idejére legyen igaz a már említett átlag ~= max. ideális esetben min ~= max.
W legyen P-beli.
a d típusa szabadon választható, de számítógépen praktikusan ábrázolható legyen.
ez a kiírás az előzőektől abban különbözik, hogy w rekurzív, tehát az értelmezési tartománya és az értékkészlete megegyezik. ez azonban nem igazán plusz nehézség, mert lehet w(d) = v(h(d)) ahol h egy hash függvény, aminek értékkészlete olyan, amit szeretnénk, értelmezési tartománya meg gyakorlatilag bármi.
ha D az adatunk. tehát a támadónak kéne találni egy d-t az adott h-hoz, majd találni egy D-t a d-hez, ami ráadásul megfelel az ő igényeinek, és értelmes. ez jóval több időt igényel, mint a hash lánc újraszámolása.
En egy szoval nem mondtam, hogy gyors lenne. :-) Viszont ez egy parhuzamosan vegezheto feladat. Ha en tudom, hogy az n-edik rekordban tarolt DNS mintat szeretnem modositani, h tisztara mossak egy politikust/maffiozot, akkor megtehetem ezt ugy, hogy az elso n-1-ig legeneralom ugyanazt a hasht ado rekordokat. Gyakorlatilag persze ez valoban szinte kivitelezhetetlen ha mar eleg nagy n-rol van szo, de per definicio nem hamisithatatlan.
Teny, h ez a gyakorlati megvalosithatosagot igy nem zarja ki.
No, akkor nem maradt mas amibe belekossek, ugyhogy mutass egy ilyen fuggvenyt. :-)
nincs szükség az egyediség garantálására. arra van csak szükség, hogy h-ból ne lehessen generálni d-t. egyébként a valódi implementációban még ez sem volna elég, mert ugye a d nem lesz azonos az adattal, hanem azt egy gyors szokványos hash függvény adja:
d = H(D, helőző)
ha D az adatunk. tehát a támadónak kéne találni egy d-t az adott h-hoz, majd találni egy D-t a d-hez, ami ráadásul megfelel az ő igényeinek, és értelmes. ez jóval több időt igényel, mint a hash lánc újraszámolása.
a te érvelésed szerint egyébként a digitális aláírás sem jó, mert nem bizonyító erejű. mondjuk egy 2256 méretű search space az nekem elég biztonságos, és gyanítom, hogy a bíróságnak is.
Kicsit jobban belegondolva, a tranzakcios log rekurziv titkositasa is felvet nehany kerdest:
Amennyiben garantalni akarjuk az egyediseget ugy vmilyen perfect hashing modszert kell alkalmazni, es a fv. rekurziv volta miatt permutacionkent valtozik. Azaz pl. csak 100 bevitt mintara mar 100! lehetoseget kell biztositani a hash fv. ertektartomanyan.
Es akkor meg nem vettuk figyelembe maganak a tarolt adatoknak a helyszuksegletet es valtozekonysagukat.
Ha feladjuk a perfect hashinget akkor viszont meg elvesztettuk a meghamisithatatlansagot. Igaz ugyan, hogy nagyon nehez, illetve nem is tetszoleges modon lehetne hamisitani, de akkor mar nem tudnank garantalni, hogy vki utolag nem cserelte e ki mondjuk az n. elemtol lefele egy ugyanolyan hash erteket ado 0..n-1 mintara az elemeket.
Ugy erzem ezesetben is praktikus okok allnak ellent a megvalosithatosagnak.
"Egyfelol a burokracia legyozese vagyis a maffiozo/politikus kizarasra nehez (ha nem lehetetlen) barmilyen rendszert kitalalni ami mindennemu rosszhiszemuseg ellen ved."
ám én éppen ezt tűztem ki célul :)
"Egy ilyen adatbazisnal valoszinusitheto hogy egyszerre tortennenek modositasok,"
ezt éppenséggel ki kell zárni. a hashing nyilván egyetlen szálon történik. az innen kezdve technikai részletkérdés, hogy mi van, ha még tart az előző, de közben újabb rekordot kéne beszúrni. ilyenkor egyszerűen üresen lehet hagyni, és amikor a hashelő felszabadul, folytatja a következő üressel, amig van. jólrendezés se számít, mert a sorrend igazából lényegtelen. maga a hashing kapja fel a rekordokat, és fűzi fel egy láncra.
"Ezt figyelembe veve azzal a kivansaggal, hogy f() kiszamolasa idoben kelloen sokaig tartson, praktikusan kivetelezhetetlenne tenne ezt a rendszert."
ezt nem tudom értelmezni. f lassúsága éppenhogy a lényege az egésznek. gyakorlatilag a hash számítása folyamatos, soha egy pillanatra le nem áll, emiatt lesz lehetetlen "utolérni". ez is egy fontos része, ha nincs új adat, amit hashelni kéne, akkor hasheli a semmit. ezeket az üres szakaszokat sem lehet utólag kivágni, mert akkor meg feltűnően kevés lesz a sor. hiszen meg kell lennie a napi 24 órányi munka eredményének.
"A masik lehetoseg az, hogy hisztorikusan tarolod az adatokat, tehat minden rekord hozzacsapodik az eddigiekhez,"
ezzel kezdtem :) az adatbázis úgy van megtervezve, hogy csak új adat kerül bele, törlés és módosítás nincsen. ez egyébként amúgy is jó gondolat, ha a nyomonkövethetőség szempont, tehát igazából nem kell nagyon átszabni emiatt.
"Mindenesetre az adminisztrator szemelye a legtobb esetben point of failure lehet."
ám nem az én megoldásomnál. ott az admin bele tud szólni, hogy mi kerüljön az adatbázisba, de ha egyszer belekerült, utólag nem lehet piszkálni.
Egyfelol a burokracia legyozese vagyis a maffiozo/politikus kizarasra nehez (ha nem lehetetlen) barmilyen rendszert kitalalni ami mindennemu rosszhiszemuseg ellen ved.
De a konkret problemara utalva, konstruktiv otlet nelkul rogton mutatnek egy problemat:
Egy ilyen adatbazisnal valoszinusitheto hogy egyszerre tortennenek modositasok, viszont a rendszer rekurziv volta miatt ez problemas.
Ha non-blocking tipusu optimistic-lockot hasznalsz, akkor minden m es n rekord (m > n) modositasa eseten m azonnal eldobhato. Tehat aktualis mindig a legkisebb rendszamu rekordot lehetne csak modositani.
Azaz gyakorlatilag egy queue-bol kene kiolvasni a beerkezo adatokat, es minden egyes adatbevitelnel az attol magasabb rendszamu rekordokat is ujra kellene szamolni.
Kozben arra is figyelni kell, hogy a queue-bol is jolrendezve jojjenek a rekordok.
Ezt figyelembe veve azzal a kivansaggal, hogy f() kiszamolasa idoben kelloen sokaig tartson, praktikusan kivetelezhetetlenne tenne ezt a rendszert.
A masik lehetoseg az, hogy hisztorikusan tarolod az adatokat, tehat minden rekord hozzacsapodik az eddigiekhez, igy mukodnek pl. az in-memory adatbazisok, amik az adatreprezentaciot csak a gyors eleresu memoriaban taroljak es sorosan taroljak a modositasokat.
Ebben az esetben mondjuk az mukodo megoldasnak tunik (nem gondolkoztam el komolyabban rajta), hogy a tranzakcios logot rekurzivan kodoljuk.
A gyakorlatban ezekrol az adatbazisokrol idorol idore azert snapshotokat csinalnak, es nem a kalyhatol indulnak ha ujra kell oket inditani, igaz ennek az is oka, h jellemzoen ott hasznaljak oket, ahol nagy a terheles sok irassal es olvasassal es nagyon rovid valaszido az elvart, igy ezek a logok viszonylag hamar nagyon nagyra nonek.
Mindenesetre az adminisztrator szemelye a legtobb esetben point of failure lehet.
