Bombe-maskinen til Alan Turing kunne knekke kodespråket i nazistenes beskjeder til hverandre.
Bombe-maskinen til Alan Turing kunne knekke kodespråket i nazistenes beskjeder til hverandre.

Matematikk:
Årets Abelpris­vinnere følger i Alan Turings fotspor

Takket være en av årets Abelprisvinnerne finnes det krypteringsmetoder som selv en kvantedatamaskin ikke kunne ha knekket.

Nazistenes Enigma-maskin, som så ut som en gammeldags skrivemaskin, gjorde det mulig å sende krypterte beskjeder.

Tilsynelatende forandret maskinen hver bokstav til en hvilken som helst annen. En L kunne bli en A, mens en S kunne bli en W.

Og kodenøkkelen forandret seg annenhver eller hver dag.

Men ved Bletchley Park i England utviklet matematikeren Alan Turing en maskin kalt Bombe. Den kunne pløye gjennom tusenvis av mulige løsninger på koden.

Ved hjelp av Turings maskin, og nitid arbeid fra kvinnene som brukte den, kunne de allierte lese kommunikasjonen til tyskerne.

I dag ser verden annerledes ut. En helt vanlig datamaskin kunne knekket Enigma-koden på noen sekunder.

Men det finnes smartere måter å lage koder på.

Det har vinnerne av den prestisjetunge Abelprisen bidratt til.

Den ene har gjort det mulig å bygge en kode selv ikke de kraftigste kvantedatamaskinene bør kunne knekke. Den andre har gjort det mulig å bevise noe uten å avsløre innholdet i beviset.

Abelprisvinnerne László Lovász og Avi Wigderson har bidratt til å hviske ut grensene mellom matematikk og datavitenskap.
Abelprisvinnerne László Lovász og Avi Wigderson har bidratt til å hviske ut grensene mellom matematikk og datavitenskap.

Enorm datakraft

Årets vinnere heter László Lovász og Avi Wigderson.

− De har gitt helt fundamentale bidrag til kryptering, sier Hans Munthe-Kaas til forskning.no. Han har ledet komiteen som har plukket vinnerne.

I likhet med Alan Turing har de to vinnerne jobbet i skjæringspunktet mellom matematikk og informatikk.

Men i Lovász’ og Wigdersons levetid har datamaskinene fått en kraft som Turing neppe hadde sett for seg.

Det betyr for eksempel at hackere kan pløye gjennom et vanvittig antall mulige løsninger for å knekke kodene som beskytter bankkontoen eller e-posten din.

Likevel er den personlige informasjonen din overraskende godt beskyttet fra slike angrep.

Forklaringen ligger i matematikken bak kryptering.

Så lenge universet har eksistert

− Selv om du har superraske datamaskiner, finnes det problemer de ikke kan løse selv om de fikk like lang tid på seg som universet har eksistert, forteller Munthe-Kaas, som til vanlig er professor i matematikk ved Universitetet i Bergen.

Det finnes altså grenser for hvilke problemer som kan løses med en datamaskin. De ble beskrevet av Turing − allerede før den første datamaskinen ble laget.

Datafolkene som lager metoder for å beskytte for eksempel bankkontoen din, bør derfor velge seg et slikt «uløselig» problem i krypteringen.

Knuste kryptering

Men likevel blir koder knekket også i dag. Det viser seg at noen problemer som ekspertene anså som uløselige, ikke var det allikevel.

Den ene Abelprisvinneren, ungarske László Lovász, har blant annet funnet en metode som kan knuse flere kjente krypteringsmetoder.

Metoden kalles LLL-algoritmen.

Den er oppkalt etter Lovász, som er professor ved Eötvös Loránd University i Ungarn, og to andre matematikere som også har etternavn som begynte på L.

Algoritmen gjør at datamaskinen slipper å pløye gjennom alle mulige løsninger.

László Lovász

  • Lovász er født i Ungarn i 1948. På gymnaset i Budapest fikk han spesialiserte matematikktimer sammen med andre begavede elever. Han studerte matematikk ved Eötvös Loránd University og fikk sin doktorgrad der bare 22 år gammel.
  • Lovász har vært tilknyttet flere ungarske universiteter og har vært gjesteforsker ved universiteter i flere land. I 1993 ble han utnevnt som professor ved Yale University, USA. I 1999 begynte han å jobbe som forsker i Microsoft. Fra 2006 har han vært tilbake ved Eötvös Loránd University, der han er professor.
  • Lovász har gjort viktige bidrag innen fagfelt som kombinatorikk og grafteori og løst flere matematiske gåter.

Kilde: Det Norske Videnskaps-Akademi

Nye metoder opp fra asken

Istedenfor kan den på elegant vis forenkle et komplisert problem. Da er plutselig ikke datakraft en like stor begrensning lenger.

− Man fikk et verktøy for å angripe mange kjente kryptosystemer på, forteller Munthe-Kaas.

Men opp fra asken kom nye verktøy som kan bli ekstra viktige i fremtiden.

Disse nye krypteringsmetodene, basert på metoden til Abelprisvinneren, har nemlig en stor fordel.

De kan, ifølge Munthe-Kaas, ikke knekkes av kvantedatamaskiner.

Kvantedatamaskiner

Kvantedatamaskiner har på papiret ikke de samme begrensingene som datamaskinene vi bruker i dag. Altså følger de ikke Turing sine teorier lenger.

Så vidt vi vet, finnes ikke slike maskiner enda. Google kunngjorde riktignok at de har laget en slik maskin, men så trakk de studien tilbake.

En av de vanligste måtene å kryptere på i dag er å bruke primtall.

Mange av disse systemene kan knekkes av en kvantedatamaskin.

Men ved hjelp av Lovász sin metode, kan disse kodespråkene erstattes.

− Det viser seg at noen kryptosystemer ikke kan knekkes av en kvantedatamaskin og alle er basert på LLL-algoritmen, forteller Munthe-Kaas.

Kunnskapsløse bevis

Et annet viktig bidrag til kryptering, er fra den andre Abelprisvinneren. Avi Wigderson ble født i Israel og er professor ved Princeton, USA.

Metoden hans kalles kunnskapsløse bevis – «zero-knowledge proofs» på engelsk − og gjør det mulig å bevise noe uten å avsløre innholdet i beviset.

Det blir som å overbevise mottageren om at du har en viss informasjon, uten å vise den frem, forklarer Munthe-Kaas.

Denne metoden kan være nyttig i flere sammenhenger. Men kanskje mest interessant, er det som har med kryptovalutaer å gjøre.

− Metoden er grunnlaget for blokkjedeteknologi for å hemmeligholde informasjon om kryptovalutaer, stadfester komitelederen.

Avi Wigderson

  • Wigderson er født i Israel i 1956. Han studerte datavitenskap ved Technion – Israeli Institute of Technology og tok doktorgrad i datakompleksitet ved Princeton, USA.
  • Han ble professor ved Hebrew University i Jerusalem i 1991. I 1999 dro han tilbake til Princeton og Institute for Advanced Study, hvor han har vært siden.
  • Wigderson er kjent for sin evne til å se forbindelser mellom tilsynelatende ubeslektede områder. Han har gjort viktige bidrag til fagfelt som datakompleksitet og grafteori, og har bygd opp sterke fagmiljøer rundt seg. Den største anvendelsen av forskningen hans er i dag innen kryptering.

Kilde: Det Norske Videnskaps-Akademi

Åpnet godteskuff med mattenøtter

Begge Abelprisvinnerne har bidratt med mye annet innen feltene matematikk og datavitenskap. Et interessant eksempel kommer fra Widgerson.

Sammen med flere kollegaer har han åpnet en godteskuff med mattenøtter som andre matematikere kan prøve å løse.

Forskerne viste nemlig følgende:

Hvis et matematisk problem kan løses ved hjelp av tilfeldighet, kan det også løses på tradisjonelt vis.

Altså litt som at hvis du kan kaste kron og mynt for å bestemme hvilken vei du skal gå i hvert kryss − og klarer å havne på riktig sted − så finnes det en annen løsning.

En løsning hvor du ikke trenger å bruke et tilfeldig myntkast.

Finne store primtall

For eksempel inspirerte denne oppdagelsen en gruppe indiske matematikere, forteller Munthe-Kaas.

De har klart å finne en ny algoritme som kan sjekke om et stort tall er et primtall. Du vet disse tallene som bare kan deles på 1 eller seg selv. Det største primtallet vi har funnet i dag krever 4000 A4-sider hvis vi skulle skrevet ned alle sifrene.

Slike metoder fantes også før, men de brukte tilfeldige sprang hit og dit som en del av beregningen.

− Som et resultat av Widgersons bevis skjønte man at det måtte finnes en algoritme, forklarer Munthe-Kaas.

De indiske matematikerne fant altså en rask oppskrift for å finne disse primtallene på den tradisjonelle måten. På fagspråket kalles det en deterministisk algoritme.

Ny æra av matematikken

Målet med årets Abelpris er å løfte frem fagfeltet vinnerne representerer, som har røtter tilbake til blant andre Alan Turing, forteller Munthe-Kaas.

− Vi er inni ny æra av matematikken hvor datamaskiner og beregninger står helt sentralt. Det er spennende.

− Denne prisen er for å feire og hylle samarbeidet med datavitenskap og matematikk og hvordan de to feltene har inspirert hverandre begge veier, erklærer komitelederen.

László Lovász og Avi Wigderson var de beste kandidatene innen dette fagfeltet, konkluderte Abelkomiteen.

Saken er oppdatert 19/3-21 kl 14:15

Abelprisen

  • Abelpris deles ut av Det Norske Videnskaps-Akademi (DNVA) for fremragende matematisk arbeid.
  • Prisen er på 7,5 millioner norske kroner og ble for første gang delt ut i 2003.
  • DNVA har nedsatt en Abelkomité av fem matematikere som vurderer nominerte kandidater og anbefaler en eller flere verdige vinnere av Abelprisen.

Kilde: Det Norske Videnskaps-Akademi

Powered by Labrador CMS