Scorched (brændt) – 2-11. Diffie-Hellmann kryptering, Hovedkomponentanalyse

Hej på bloggen.
Engang imellem blandes matematik og fysik en del sammen, for eksempel er der meget matematik i fluid mekanik, som Charlie snakkede om. Han nævnte Euler, Prandtl og Viete som folk, der havde arbejdet i det område. De er omtalt her, i øvrigt sammen med Newton, med fokus på deres rolle i netop Fluid mekanik.
Ellers var der matematik i Diffie Hellman kryptering (brugt af Ethan og brandeksperten) og der var Principal Component Analysis.

Diffie Hellmann

I 1976 publicerede Whitfield Diffie og Martin Hellman en artikel, “New Directions in Cryptography”. Artiklen handler om at udveksle nøgler til at kommunikere i hemmelighed. To personer ønsker at udveksle hemmelige beskeder ved at afsenderen krypterer beskeden, sender den over en offentligt tilgængelig kanal (telefonen, internet, i avisen,…) og modtageren dekrypterer. Nøglerne er den information, de to skal være enige om for at kunne henholdsvis kryptere og dekryptere.
Det nye var, at man faktisk kan udveksle nøglerne via den offentlige kanal. Umiddelbart lyder det jo ret urimeligt, for kan en tredie person så ikke sidde og opsnappe nøglerne for derefter at kunne læse de hemmelige beskeder? Som tidligere omtalt på bloggen er der forskel på at kunne regne noget ud i princippet og så rent faktisk at kunne regne det ud indenfor f.eks. universets forventede levetid – eller måske bare 100 år; det skulle vel kunne gøre det.
Den slags systemer kaldes Public Key Systemer – nøglerne er offentlige, men man kan alligevel ikke dekryptere beskeden.
Diffie og Hellman var muligvis ikke de første med ideen. I GCHQ (Government Communications Headquarters), som er (eller var?) en del af britisk efterretningsvæsen, havde man allerede i 1970 fat i ideen, men holdt det hemmeligt. Se i øvrigt Martin Hellmans beretning om at arbejde med kryptografi med trusler om retssager hængende over hovedet, fordi artiklerne blev offentliggjort. Han stiller også spørgsmålstegn ved GCHQ’s påstand. Hvordan kan man verificere, at de havde ideen først, når de ikke havde offentliggjort den? Det gjorde de i 1996.
Diffie Hellman nøgleudveksling forgår som følger: Alice og Bob vil udveksle nøgler. En fælles nøgle er et tal, Alice og Bob er enige om, og som andre ikke kender.
Vi tager først et eksempel:
1) Alice og Bob bliver enige om p=23, g=5 (f.eks. ved, at Alice sender de tal til Bob)
2) Alice vælger et hemmeligt tal, a=6, udregner g^a=5^6 og tager rest ved division med p=23. Det giver 8. Det tal sender hun til Bob.
3) Bob vælger sit eget hemmelige tal, b=15, udregner g^b=5^15 og resten ved division med p=23. Det giver 19, og det sender han til Alice.
4) Alice udregner nu 19^a=19^6, tager rest ved division med p=23 og får 2.
5) Bob udregner 8^15, rest ved division med p=23 og får 2.

Nu er 2 deres fælles hemmelige nøgle. Andre kender ikke a og b, så de kan ikke lave trin 4 og 5, selvom de har aflyttet det tidligere.

I virkeligheden skal p være et meget stort primtal. Tallet g er en primitiv rod af p, det vil sige, at når man udregner tallene g, g^2, g^3 ,… og tager rest ved division med p, så kommer man igennem alle tallene 1,2,3,…,p-1.
Hvis vi i eksemplet med p=23 havde valgt g=2, havde vi som g,g^2,… fået
2,4,8,16,9,18,13,3,6,12,1 og så forfra. Altså ikke alle tal fra 1 til 22.
Med 5 får man 5, 2, 10, 4, 20, 8, 17, 16, 11, 9, 22, 18, 21, 13, 19, 3, 15, 6, 7, 12, 14, 1 og det var alle tal fra 1 til 22.
Som man kan se, giver division med rest noget ret uoverskueligt, og det er hele fidusen: Selvom man kender Alices a^g mod p (resten efter division med p) og man kender både g og p, kan man ikke nemt finde a, hvis ellers p er et stort primtal. Hvor stort, det skal være, afhænger af, hvor sikker kommunikationen skal være. Videnskabsministeriet har en vejledning Praktisk brug af kryptering og digital signatur hvor man skriver om Diffie Hellman.
RSA som jeg tidligere har omtalt er en asymmetrisk metode, hvor kun den ene part skal kunne dekryptere, svarende til, at Alice vil sende til Bob, men ikke omvendt. Alice skal så ikke have noget hemmeligt for andre.

Principal Component Analysis

Charlie havde fundet 600 variable, som karakteriserer en påsat brand, og indtastet (fået nogen til at indtaste) disse variable for 5000 brande i Los Angeles området. Derefter har han “projiceret på en 15 dimensional hyperplan”. Han har med andre ord fundet 15 kombinationer af de 600 variable, som bedst karakteriserer forskellige brandtyper.
Det er en slags data mining, som vi har haft med på bloggen før. Man leder efter “klumper” af data, og om man kan karakterisere “klumperne” med f.eks. summen af alle 600 variable, differensen mellem de to første, 7 gange den tredie plus 8 gange den syttende… eller noget lignende. Om man altså kan nøjes med færre tal end de 600. Og Charlie kan nøjes med 15 tal for hver brand – ret smart.
Deraf ser han, at der er to forskellige metoder, altså to forskellige pyromaner.

Charlies ekspertviden om at være 17 år og rigtig dygtig fagligt, men helt ved siden af socialt, var også nyttig.

I øvrigt var der et nyt ansigt: fysikeren Bill Walde, som lavede en opstilling af et forsøg med en røgeksplosion. Han spilles af Bill Nye, som har et TV-show “Bill Nye, the Science Guy”, hvor han netop laver diverse eksperimenter som det vi så her med at genantænde et stearinlys. Ham ser vi igen i sæson 3.

Hilsen Lisbeth www.math.aau.dk/~fajstrup
numb3rs@math.aau.dk