Ez még abban az időben történt, amikor a számítógépeket nem volt olyan egyszerű rákötni projektorra és a prezentációkat irásvetítő fóliára kellett szerkeszteni.
Cipóriánnak eszébe jutott egy zseniális terv a városi bank kirablására. Nagyon szerette volna cinkostársainak megmutatni tervét, mely oly zseniálisan egyszerű volt, hogy egy oldalra ráfért az egész. Cipórián viszont nagyon félt, hogy rivális csoportok vagy esetleg a rendőrség kezébe kerülhetnek a tervek. Így azt találta ki, hogy több fóliát fog használni, melyek egymásra téve (és átvilágítva) pont a kívánt ábrát adják ki. Úgy gondolta, hogy maximum két fóliát esetleg ellophatnak tőle, ezért úgy szerkesztette meg őket, hogy bármelyik kettőt kivéve a csomagból abból a két fóliából semmilyen információt ne lehessen megtudni a tervéről.
Hogy csinálhatta?
Az egyszerűség kedvéért feltehető, hogy csak fekete-fehér, vagy esetleg szürkeskálás ábráról van szó. Az ábrát vehetjük diszkrét pontokból (pixelekből) állónak.
Az eredményül kapott ábrának (ha az összes fóliát egymásra rakjuk) nem kell feltétlenül nagyon kontrasztosnak vagy élesnek lennie, a lényeg, hogy felismerhető legyen.
Minden fóliát fel kell használni!
Mivel ez nem egy olyan egyszerű, magától értetődő feladat, tessék nyugodtan ötletelni a kommentekben!
Comments are closed.
Nekem van egy kiinduló ötletem, de még rengeteget kell rajta dolgozni…
Az egész abból a feltevésből indul ki, hogy ha egymásra rakok az
írásvetítőn fóliákat, akkor a kivetített kép a fóliákon lévő
szürkeárnyalatos képek pontonkénti összegét fogja mutatni.
A másik kiindulópont az a hagyományos kulcsszétosztási módszer, amikor
N emberre akarok rábízni egy kulcsot, amihez egyszerre legalább 1 ≤ K
≤ N embernek kell közülük együttműködni (a klasszikus “egyszerre
ketten kell elfordítani két kulcsot a páncélterem kinyitásához”
matematikai modellje). Ennek egy nagyon egyszerű megoldása, hogy
veszünk egy K fokú polinomot, és kiértékeljük N db adott
alappontban. Mindenki egy (x_i, y_i := p(x_i)) párt kap, és ha
összejönnek K-an, akkor Lagrange-interpolációval pontosan
rekonstruálni tudják p-t.
Csináljuk tehát a következőt: legyen N > 2 a felhasználható fóliák
száma, és keressünk a képnek, mint ℂ → ℝ függvénynek egy (N-1)-edfokú
polinom-approximációját, legyen a továbbiakban ez p. Ezek után
készítsük el az N db fóliát olymódon, hogy egy adott (x_0, …, x_N)
alappontrendszerhez minden i. fólia az x_i középpontú
Lagrange-alappolinom p(x_i) érték szerint skálázott változata: vagyis
a fólián kb. azt látjuk, mintha “felülről” ránéznénk az
i. Lagrange-alappolinomra, és térképként besatíroznánk, hogy hol
milyen nagy a függvényérték.
Ekkor az így kapott fóliákat egymásra téve és kivetítve éppen a
Lagrange-polinomok egy lineáris kombinációját kapjuk, és a súlyozás
pont p-nek az alappontokban vett értéke. Mivel N fóliánk van, és p
(N-1)-edfokú, nyilván visszakaptuk az eredeti polinomunkat, vagyis az
eredeti kép approximációját. Ha viszont csak két fólia van a
kezünkben (vagy bármennyi, de nem mind az N), akkor gyakorlatilag
semmit nem tudunk mondani a polinomról.
A dologban csak az a bibi, hogy ez így egydimenzióban biztosan
működne, de kicsit fishy, hogy egyáltalán hogyan approximáljuk a
valósértékű, komplex számsíkon értelmezett képünket polinommal, meg
hogy működik-e ez az egész, ha a polinom értékeinek csak a nagyságát
(abszolútértékét) tároljuk (hiszen a fólia pontjaiba csak egy-egy
szürkeárnyalatot tudunk rakni).
Ez szerintem kurva jó, csak abban nem vagyok teljesen biztos, hogy semmi információhoz nem jut a csávó, ha két diát ellop, mer azér valami közelítést már az a két dia is kell, hogy adjon. Vagy nem?
Ha N-et nem ismeri, akkor kontinuum számosságúnál is több olyan polinom van, amelynek fólia-sorában szerepelne ugyanaz a két fólia. Ha N-t ismeri, akkor csak kontinuum számosságú 🙂
Gondolom olyan a módszer amit a rendőrség is ismerhet.
Extrém esetként meg akartam kérdezni, hogy 1 pixeles képre is működik -e, de úgy látom, valószínűleg nem.
Remélem nem egy ‘xor vetítő’, hanem az általánosban megismert 🙂
@csakazertse: Természetesen mint minden rendes titkosításnál, itt is abból kell kiindulni, hogy az ellenség ismeri az algoritmusunkat.
Egy pixeles képre pl. lehet a következőt csinálni: N fólia közül m darabra szürke pontot teszünk, a többit átlátszóra hagyjuk, m > N/2 fekete eredeti pixel esetén, fehér esetén fordítva. Az eredményben így az 50%-os szürkénél kicsit sötétebb pixelt kapunk ha fekete pixelből indultunk ki, fehér esetén egy picit világosabbat.
Ezt persze könnyen általánosíthatjuk többpixeles képre is.
A gond az, hogy két fóliát megkaparintva 50%-nál átlagosan nagyobb eséllyel lehet eltalálni, hogy az adott pixel fekete vagy fehér volt. Így nem teljesül, hogy nem kap információt a támadó.
Cactus megoldása tökéletes lenne, csak ki kéne rendesen dolgozni. Tisztázni kéne először is, hogy működik-e a Lagrange komplexváltozós függvényekre. Aztán érdekes lenne látni, hogy az alappontok száma és a képvisszaadás minősége milyen összefügésben van; hány fólia kell tisztességes minőségű kép előállításához, stb.
Az is érdekes lenne, hogy lehet-e gyengíteni a dolgon, hogy csak az eredetileg elvárt két fóliás megfejthetetlenséget hozza.
@_Cactus_: Ne aggódj a kvantálás miatt, legfeljebb majd valami ügyes nyomdai eljárással megoldjuk, hogy folytonosak legyenek az átmenetek. 🙂 (Bár persze tudjuk, hogy igazából valós számok nem léteznek :P)
A kontrasztosság, élesség arra enged következtetni, hogy fóliák helyett nem működne ff bmp fájlokra és OR műveletre sem.
közben megláttam az előző választ is ..
@-Maya: Nem is arra gondoltam, hanem hogy pontonként csak abszolútértékeket tudunk szummálni, nem pedig komplex értékeket.
@-Maya: A Lagrange-interpoláció működik komplex polinomokra, nem azzal van itt a baj (sőt, talán az az egyetlen, amivel nincs baj:))