RSA-kryptering og minuttvisermatematikk.

pi_function_of_maths_wall_clock
Pi-klokker som denne kan kjøpes på: http://www.cafepress.co.uk/+pi+clocks

RSA-kryptering er fortsatt en av de aller mest populære formene for kryptering som finnes, og baserer seg på prinsippet at primtallsfaktorisering er vanskeligere enn å multiplisere to tall. Før vi går inn på selve krypteringen må vi se litt på et skikkelig kult område av algebra kalt modulær aritmetikk, eller «minuttvisermatematikk».

Når vi regner hva klokken er etter at en hvis mengde minutter skjer det en interessant ting som faktisk er et nøye studert fenomen innen matematikk. Hvis klokken er f.eks. 9:10 og det går 55 minutter så er ikke klokken 9:65, men heller 10:05. Så hvis vi ignorerer timene har vi at for minuttene så er 10+55=5 (mod 60), hvor vi putter den ekstra notasjonen (mod 60) bak uttrykket for å ikke forvirre med vanlig likhet. En annen måte å se på denne egenskapen er ved å fokusere på resten ved divisjon: 10/60 er 0 hele med 10 i rest, og etter addisjon med 55 har vi 65/60 som er 1 hel og 5 i rest, så nok en gang har vi 10+55=5 (mod 60) når vi fokuserer bare på resten. Vi kan gjøre modulær aritmetikk for alle tall større enn 1, og ikke bare 60 som i eksempelet over. For eksempel er modulær aritmetikk med tallet 2 en kul måte å vise egenskaper om par- og oddetall siden alle partall =0 (mod 2) og alle oddetall =1 (mod 2) (sjekk dette ved å tenke på hva resten er når man deler på 2). Det er mye kult vi kan vise om modulær aritmetikk, men la oss utsette det til vi ser hvorfor vi er interessert i denne type regning, og bare påpeke at i det første eksempelet begynner vi med et positivt tall (10) og legger til noe positivt (55) og ender opp med et tall (5) som er mindre enn det vi startet med.

numerology-basics Nesten alle krypteringsmetoder bruker sterke matematiske metoder for å sikre tryggheten av informasjonsoverføring. Den mest allment kjente delen av matematikk handler om tall (men veldig mye matematikk handler ikke om tall i det hele tatt, for eksempel topologi), så hva gjør man hvis man vil overføre annen informasjon enn ett og ett tall om gangen, som for eksempel tekst? En måte å gjøre dette på er å tilegne hver bokstav et unikt tall som posisjonen i alfabetet som på bildet til venstre. Så kan vi skrive «HALLO» som tallet 0801121215 og siden vi var smart nok til å legge til noe strategiske nuller foran 8 og 1 så er det enkelt å lese av dette tallet to og to siffer av gangen og gjøre det tilbake til den originale teksten. Det finnes en metode for å gjøre absolutt alle tegn og bokstaver du kan komme på om til tall alt UTF-8 som ligner veldig på det vi gjorde over, og det finnes metoder for å gjøre bilder, lyd og alt annet man kan tenke seg om til tall. Så det eneste som gjenstår nå er å se hvordan man kan overføre tall på en sikker måte når vi mistenker at noen andre «lytter» til all informasjon vi faktisk sender.

Stealing online information
Noen folk vil stjele informasjonen din.

Nå kommer vi endelig til RSA-kryptering og kan begynne å regne litt. For å bruke RSA må vi først generere noen tall som er kjent som nøkler som brukes til å kryptere og dekryptere tallet vårt før det sendes. Vi velger to store primtall p og q slik at produktet n=p*q er større enn tallet vi vil sende, og så må vi bruke litt tallteori. Regn ut Euler totienten til n, φ(n)=(p-1)(q-1), og finn et tall e, slik at 1<e<φ(n) og e er relativt primisk til φ(n) (dvs at e/φ(n) er en brøk som ikke kan forkortes). Vi la merke til over at å legge sammen to tall kan produsere et tall som er mindre enn begge, og det samme er sant for multiplikasjon; faktisk er det slik at for noen tall som e finnes det er annet tall d slik at d*e=1 (mod φ(n)). Og nå har vi alle nøklene vi trenger. Den private nøkkelen er d holdes hemmelig for alle andre enn den som skal dekryptere, mens de offentlige nøklene er e og n som kan sendes til den som skal overføre tallet til oss og det kule er at det ikke spiller noen rolle om andre også får tak i tallene e og n, så lenge de kommer frem uendret til senderen vår. La oss nå se på et eksempel med relativt små tall slik at vi kan se litt på hvordan alt dette fungerer og hvordan man bruker det i praksis.

man_writing_calculations_on_glas_450La p=61 og q=53 slik at n=p*q=3233. Vi regner ut φ(n)=60*52=3120, og vi kan velge e=17 og regne ut d=2753 ved å bruke noen resultater fra tallteori eller bare prøve seg frem. Så vi sender tallene e=17 og n=3233 til vår kompis som ønsker å sende oss tallet m=65 av en eller annen grunn. Kompisen vår krypterer m ved å regne ut m^e=65^17=6599743590836592050933837890625=2790=c (mod 3233) og sende dette tallet c til oss. Når vi mottar c=2790 kan vi regne ut c^d=2790^2753=noe veldig stort noe=65 (mod 3233). All regningen vi har gjort i dette eksempelet er regning som datamaskiner er veldig flinke og veldig raske til, og det er fortsatt sant om vi begynner med mye større primtall p og q. Denne metoden fungerer fordi det som har skjedd her er at det vi regner ut til slutt er (m^e)^d=m^(d*e)=m^1=m (mod n) som er en kombinasjon av regneregler man lærer på videregående og noen regneregler fra modulær aritmetikk og tallteori. Og grunnen til at dette er trygt er at selv om man vet både n og e er det vanskelig å regne ut d uten å vite p eller q fra før av, for disse utregningene kan ta flere dager selv på en superdatamaskin.