Hej Bloggere.
Matematikken i dette afsnit af Numb3rs var, set fra min udkigspost, Om fjernbetjente bildøre, Farey-følger, cellulære automater, trafikovervågningssystemer og noget med, hvordan bookmakere sætter odds. I får en hel del om bildøre og om Farey-følger, men de cellulære automater og odds må I vente med til en anden gang.
Om fjernbetjente bildøre
Hvad skal en fjernbetjening til bildøre egentlig kunne?
1) Åbne min bil og ikke naboens
2) Hvis jeg opsnapper signalet fra naboens fjernbetjening, kan det ikke genbruges – jeg kan ikke åbne naboens bil ved at sende det signal til den.
Problemet er i kategorien “deling af hemmeligheder”, og “identifikation” (authentication – er den, jeg modtager signalet fra, den rigtige) men det er lidt mere indviklet. Jeg har læst mig frem til, hvordan General Motors gør: Bilen og nøglen har fra starten indkodet to hemmelige tal.
Men dem kan nøglen ikke sende – så er betingelse 2) ikke opfyldt.
I det Lean-systemet, som bl.a. bruges af General Motors, er metoden patenteret i to patenter
Pseodorandom number generation and cryptographic authentication
og
Method of generating secret identification numb3rs
En af dem, der har lavet systemet, Philip Koopman, skrev et indlæg om systemet på vores amerikanske søsterblog her.
Kort fortalt fungerer det sådan:
Nøglen genererer et tilfældigt tal. Det sættes sammen med det ene af de hemmelige tal (foran eller bagved eller de flettes sammen 22222 flettes med 33333 som 2323232323) og det samlede tal krypteres.
Det andet hemmelige tal krypteres og de to krypterede tal sættes sammen – efter hinanden eller flettet.
Så krypteres igen. Resultatet sendes til bilen som en række 0’er og 1’er.
Bilen dekrypterer, finder de to hemmelige tal og det tilfældige tal. Den gemmer det tilfældige tal (hvis ellers de hemmelige tal passer) og låser bilen op.
Næste gang bruges det tilfældige tal, som bil og nøgle nu deler, til at lave det nye (pseudo)tilfældige tal. Man krypterer det, og sætter det sammen med det andet hemmelige tal, og så starter man som ovenfor.
Bilen kan nu genfinde det tilfældige tal fra før, foruden de to oprindelige hemmelige tal.
Krypteringen er ikke så stærk som den, der bruges i bankoverførsler og lignende, og systemet kan altså brydes, hvis man har nøglen og kan se en række af de signaler, den sender. Derfor kan man, så vidt jeg ved, også kopiere nøgler, hvis man er kvik og har det rette udstyr.
I Lean systemet er krypteringen forskellig fra gang til gang, og afhænger af den fra sidste gang, så når bilen dekrypterer, skal bil og nøgle være synkroniserede, altså enige om, hvilken kryptering/dekryptering, der bruges. Det kan bilen ikke vide, hvis nu ungerne har leget med nøglen, eller jeg har sat mig på den og dermed trykket, uden at bilen var i nærheden. Så bilen afprøver de næste 256 dekrypteringsmåder. Hvis ikke de giver et resultat, der matcher, åbner den ikke. (Det tager ialt 1/2 sekund). Virker nøglen ikke, kan man genstarte ved at trykke på to knapper (tror jeg nok), og så starter proceduren forfra. Det samme sker, hvis batteriet er løbet tør.
Og hvor er så matematikken? I kryptering, i generering af tilfældige tal og i generering af de hemmelige tal til bil og nøgle på fabrikken: hvordan sikrer man, at man ikke genbruger dem? Når man samtidig ikke ønsker at have en database med alle de hemmelige tal; den kunne blive stjålet, og så kunne man låse sig ind i alle General Motors biler. Det er det, det andet patent handler om. De hemmelige tal frembringes fra støjen fra en ventilator! Og man bruger en såkaldt hashfunktion (nej, det har intet med hash at gøre) på de to tal. Det tal, man får ud af det, gemmer man. Hvis to nye hemmelige tal giver samme tal i hashfunktionen, kasseres de. Pointen er, at databasen med alle hashværdierne ikke kan bruges til at genfinde de oprindelige hemmelige tal.
I øvrigt er der også matematik involveret, når signalet sendes – der er en fejlkorrigerende kode, som sørger for, at det signal, bilen får, kan rettes til, hvis det er blevet forstyrret på vejen fra nøgle til bil. Læs mere om fejlkorrigerende koder og i øvrigt om deling af hemmeligheder på Olav Geils populariseringsside. Se f.eks. det korte foredrag om fejlkorrigerende koder. Og måske linket til DTU længere nede.
Tilfældige tal kan frembringes på mange måder. Amita nævner cellulære automater, og det er det, der giver Charlie løsningen. Dem må I vente med til en anden dag. Fareyfølgerne er i næste indlæg på bloggen.
Hilsen Lisbeth www.math.aau.dk/~fajstrup
numb3rs@math.aau.dk