5-12 Jacked

I tænketanken ville Alan lave strøm af kolort. Det kan man godt, siger f.eks Live Science. Matematik var der også: Billedbehandling, “voxel based 3D-capture”, invers spilteori og noget med varmesignaturer (thermo signatures).
Billedbehandligene hentydede til et tidligere program, Jack of All Trades, hvor Charlie genskabte et billede, der var forvansket, fordi det var en spejlig i et termokrus. Diffeomorphic matching, kaldte de det.
Kryptering
Amita omtalte 128bit kryptering – den kryptering, Charlie og co skulle bryde for at kunne standse bussen. der findes mange forskellige krypteringsmetoder, men her hentydes nok til blokvis kryptering. Man deler sin tekst op i stykker – her har de længde 128 bits (tænk bare på bogstaver). Man bruger så en krypteringsnøgle (som man skal holde hemmeligt – dette er ikke public key kryptering). Hver blok er krypteret for sig. Krypteringen indeholder flere skridt, som allesammen skal være effektive.
En substitution opererer på en del af blokke (de første fire bogstaver) og giver en lige så lang del ud igen. Man skal kunne dekryptere, så to forskellige blokke ind skal give to forskellige blokke ud (injektivitet elller 1-1).
Eksempel: 0101 ind, 1001 ud. I en god substitution, skal hvert bogstav i output afhænge af hvert bogstav i input, så man ikke kan bryde krypteringen ved at prøve med 0100 for at se, hvad sidste bogstav bliver til. Mellem substitutionerne sidder permutationsskridt, hvor alle 128 bits byttes rundt. På den måde bliver output fra substitutionerne blandet mellem hinanden og kan så puttes ind i nye substitutioner. Jeg har et skema fra Wikipedia:

Her er S substitution, P er permutation og K er “key”, nøgle. Man bruger altså nøglen flere steder – f.eks. kanman lægge nøglens værdier sammen med det ord, der er output fra den seneste substitution. (Det hele er binært – 0 og 1- og 0+0=0, 0+1=1, 1+1=0, så nå man adderer bliver de bits, hvor nøglen har værdi 0, bevaret, de andre bliver ændret – fra 0 til 1 eller 1 til 0).

Denne type kryptering er beregningsmæssigt effektiv bl.a. fordi den er oplagt at udføre parallelt – hver af S operationerne kan gøres samtidig, hvir man har flere processorer. Desuden er dekryptering nemt; Man løber bare nedefra og op.
Hver for sig er de enkelte skridt nemme at bryde. Substitutionskryptering og permutationskryptering er ikke stærk kryptering. Og at lægge nøglen til er heller ikke, hvis man bruger samme nøgle mere end en gang. Men alti i alt – med tilstrækkeligt mange kombinationer ef S og P, får man en stærk kryptering, hvor kompleksiteten af at bryde koden er eksponentielt afhængig af nøglens længde.
Eksempler på denne type koder er DES (Data Encryption Standard), IDEA (International Data Encryption Algorithm) og AES (Advanced Encryption Standard).
Man kan bryde krypteringen ved at finde nøglen – et brute force angreb. Men at prøve alle nøgler er langvarigt og energikrævende. 128 bits svarer til 2^128 ( 2 ganget med sig selv 128 gange)=
340,282,366,920,938,463,463,374,607,431,768,211,456.
Jeg har googlet mig til, at den energi, der mindst indgår i bare at løbe igennem alle disse nøgler er 10^18 Joule (og så regner man ikke – man skal jo prøve dem af og se, om de virker). Det svarer til 30 Gigawatt i et år. Man kan på Energinet se den aktuelle elproduktion i Danmark. Der produceres lige nu (15/4 klokken 09.03) inklusive import fra Sverige og Norge og fratrukket eksport til Tyskland 4705 MW. altså 4 Gigawatt.

Så skal man bryde krypteringen, skal man gøre noget smartere.

Voxelbased 3D capture
En voxel er en lille kasse. Hvor man på computerskærmen har en opdeling i (små) rektangler, opdeler man et område i rummet i voxels.
3D capture går ud på at finde det rigtige 3D objekt, som giver anledning til et antal 2D repræsentation – man ser det fra siden, oppe fra og nedefra. Dette er naturligvis et varmt emne; Man får data fra overvågning og skal udlede, hvad det rigtige objekt er (hvis man er i krigerisk humør, kan man tænke på diverse våben, men det kunne jo også være kattekillinger).

Vores hjerne er rigtig god til det – hvis ellers vi ser noget, vi plejer at se. Man forsøger at lave computerprogrammer, der kan genskabe menneskers positioner og bevægelser. Og helst hurtigt (i real time). En ikke-krigerisk anvendelse er handicaphjælpemidler, hvor det er smart, hvis robotter kan genkende objekter – og “forstå kropssprog”. Der er smuk geometri, smarte algoritmer og meget andet i dette område, men jeg stopper her – forskningen kalder. Se for eksempel hos German Cheung fra Carnegie Mellon. Eller hos Aalborg Universitets Computer Vision gruppe

This entry was posted in Blog. Bookmark the permalink.