3-24 The Janus list.

Matematikken denne gang var primært krypteringsalgoritmer: Bacons kode, straddling dambræt (to straddle betyder- ifølge Gyldendals røde ordbøger – at skræve, at stritte med benene, at være ubeslutsom, at skyde sig ind på, så vælg selv, hvad I vil oversætte med her…), Merkle Hellman rygsækalgoritme, Musikkoder (?). Og så var der igen en reference til spilteori – “k-level thinking” og kongen, der lovede en kvik undersåt et hvedekorn på første felt i et skakbræt, to på det næste, 4 på det næste etc. Altså 1+2+2^2+2^3+2^4+…+2^63 hvedekorn.

Om hvedekornene:
Det bliver til rigtig mange: Man kan vise, at
1+2+2^2+2^3+2^4+…+2^63 =2^64-1=18.446.744.073.709.551.615

Mere generelt er 1+a+a^2+a^3+…+a^63=(a^64-1)/(a-1) hvilket man kan overbevise sig om ved at gange med a-1 på begge sider. Mange led “spiser hinanden”.
Når a=2 er nævneren på højresiden så 1.

Et andet argument fås ved at gå via totalssystemet for dem, der forstår det:

1+2+2^2+2^3+2^4+…+2^63 er i totalssystemet 111111…1111 (64 cifre) Hvis man lgger 1 til, får man 100000…0000 (65 cifre) altså et 1-tal på pladsen svarende til 2^64.

Charlie sagde i øvrigt et forkert ciffer, – han sagde et nital i stedet for et nul et sted, men det var ikke en pointe – bare en fejl fra Krumholz’ side. Tror jeg da…

Bacons kode
Her er oversættelsen fra bogstaver til tal til A’er og B’er – (det sidste svarer til at skrive talene i totalssystemet, hvis man synes, det er nemmere at forstå).
a = 0 = AAAAA g = 6 = AABBA n = 12 = ABBAA t = 18 = BAABA
b = 1 = AAAAB h = 7 = AABBB o = 13 = ABBAB u,v=19 = BAABB
c = 2 = AAABA ij = 8 = ABAAA p = 14 = ABBBA w = 20 = BABAA
d = 3 = AAABB k = 9 = ABAAB q = 15 = ABBBB x = 21 = BABAB
e = 4 = AABAA l = 10 = ABABA r = 16 = BAAAA y = 22 = BABBA
f = 5 = AABAB m = 11 = ABABB s = 17 = BAAAB z = 23 = BABBB
Bemærk, at der kun er 24 bogstaver – man havde ikke i og j som forskellige bogstaver og tilsvarende med u og v på Bacons tid.
Bacon oversatte så A og B til f.eks. kursiv og ikke-kursiv i en lang tekst. Så kan man skjule sin besked i en tekst, der ser uskyldig ud, bortset fra, at nogen ikke kan bestemme sig til, om de bruger kursiv eller ej. Eller man kan bruge store bogstaver for A og små for B, så HUNdEHOVed betyder AAABAAAABB, som jo er cd i koden ovenfor.

Straddling checkerboard

Igen drejer set sig i første omgang om at oversætte fra bogstaver til tal. Problemet i den slags koder, hvor man oversætter hvert bogstav til et andet symbol – et tal, et andet bogstav eller nogen symboler, man selv har fundet på, er, at man ved, at visse bogstaver optræder hyppigere end andre i sædvanlig tekst. Og så kan man bryde koderne ved frekvensanalyse: e er det bogstav, der forekommer hyppigst på dansk, så man gætter på, at det symbol, der optræder hyppigst i den krypterede tekst, skal oversætte til e. Og så videre. Man kan gøre noget tilsvarende med grupper af symboler og sammenligne med hyppigt forekommende ord i dansk. Det er dog ikke helt simpelt, for hyppigheden af bogstaverne afhænger af typen af tekst – se hos sproget.dk om bogstaver og om ord.

I straddling checkerboard forsøger man at omgå det problem. Jeg tillader mig at antage, at de otte mest hyppige bogstaver på dansk er strandeo (men det afhænger jo altså af, hvilke tekster, man undersøger) Dem skriver jeg ind på 8 af de ti pladser i anden række et 4 gange 10 skakbræt, hvor der i øverste række står 0123…9. Resten af bogstaverne fordeles i felterne nedenfor

Der er to pladser i øverste række, der ikke er fyldt ud, under 2 og under 6. De bruges til at “nummerere” de to sidste rækker.
Skal jeg nu skrive bogstavet a, skriver jeg 3. bogstavet r er 7. Bogstavet f står også under 3, men det skriver jeg 23 – række nummer 2, plads 3. Og for b skrives 62 for rækken nummer 6 og plads 2.

28229620825 kan nu brydes, nar jeg har mit skakbræt: Den starter med et 2-tal, så det må være et rækkenummer. Altså er første bogstav 28 svarende til L det næste er 22, altså I, så er 9 bogstavet S, 6 må være et rækkenummer, så vi skal finde bogstavet 62, altså B etc. (der står LISBETH.) Man kan kryptere yderligere ved at tage de talfølgen og bruge en anden algoritme på den. Man kan også lade tallene i første række fremkomme ved en indviklet metode etc.
Metoden har været brugt som en del af kryptering af mindst en spion for Sovjet Unionen, Reino Häihänen

Merkle Hellman rygsæk
Merkle Hellman kryptering refererer til et Public Key System, hvor man kan offentliggøre den måde, man skal kryptere på (en offentlig nøgle), så folk kan skrive hemmelige beskeder til en. Men uden at de derved selv kan dekryptere – altså læse beskeder skrevet med den kryptering. Metoden ovenfor er ikke af den type – har man tabellen til kryptering, kan man også dekryptere.

Et rygsækproblem handler om at fylde en rygsæk optimalt – i.e. at løse et optimeringsproblem under visse bibetingelser: Hvis vi har visse værdier på det, vi kan vælge at proppe i rygsækken (eller bilens bagagerum), hvad skal vi så tage med, når vi ikke kan have plads til det hele.

I kryptering er problemerne af typen:
Man har en stribe hele tal. 1,5,7,13,22 for eksempel.
Nu kan vi kryptere beskeder med 5 cifre i totalssystemet ved at lade 1 betyde “skal med” 0 “skal ikke med”, så 10110 giver 1+7+13= 21 fordi 1 skal med, 5 skal ikke med, 7 skal med, 13 skal med og 22 skal ikke med.
Dekrypteringen består nu i at skrive 22 som en sum af nogen af tallene 1,5,7,13,22.
Det er et “subset-sum” problem, og de er NP-fuldstændige, altså meget tidkrævende på en computer. (Den tid, der skal bruges, vokser meget hurtigt som funktion af, hvor stor en mængde tal, vi har som udgangspunkt.) Problemet er selvfølgelig, at det så vil være vanskeligt for den rigtige modtager at dekryptere beskeden, og det var jo ikke meningen.
I midlertid er der visse af den type “subset-sum” problemer, som er lettere at løse, nemlig dem, hvor rækken af tal, vi går ud fra, opfylder, at hvert tal er større end summen af de foregående. (Tænk over det. Hvis det tal, vi skal skrive som en sum, er større end det sidste tal, skal det sidste tal være med – ellers skal det ikke være med. Skal det med, trækker vi det fra. Nu ser vi på, om det næstsidste tal skal med etc.) det er et let rygsækproblem

I Merkle Hellmann var det i virkeligheden et let rygsækproblem, der blev brugt. Man tog en stribe tal, a1,a2,a3,a4,… som kunne bruges i et let problem. Så tog man et stort tal N,større end summen af a’erne, et tal k, som er primisk med N (deres største fælles divisor er 1) og udregnede for alle a’erne resten af ra ved division med N. Den stribe tal offentliggøres, og det ligner nu et svært rygsækproblem. For at dekryptere kan man oversætte til det lette problem ved passende algebra – læs mere her eller mange andre steder på nettet.
Merkle Hellmann kan imidlertid brydes i polynomiel tid, og det er jo skidt, så det bruges ikke mere. Det viste Adi Shamir i 1982. I øvrigt er Shamir den ene af de tre, der lavede RSA (Rivest, Adleman og Shamir), som har overlevet som public keysystem.