RSA Kryptering
- Historie, Matematikk og Implementasjon

(c) 2003 Jostein S. Trondal og Magne Rugnes

Innholdsfortegnelse

Innledning
Hva er kryptografi?
Eksempel på kryptografi
Historien bak RSA
Matematikken bak RSA
Kilder
Implementasjon av RSA
Kildekode

Innledning

Denne artikkelen handler hovedsaklig om RSA algoritmen, litt historie, matematikken bak algoritmen og en implementasjon av algoritmen i Java. Det forklares også litt om hva kryptografi egentlig er og hvordan det fungerer i praksis. For å forstå RSA bedre, oppfordres leseren til å teste ut programmene som er vedlagt. Artikkelen leveres som svar på en prosjektoppgave i faget Tallteori høst-semesteret 2003 ved Høgskolen i Agder (Kristiansand) med Trygve Breiteig som faglærer.

Hva er Kryptografi?

Kryptografi går ut på å omforme klartekst til såkalt chiffertekst, en prosess som blir kalt kryptering, og tilbake igjen til klartekst (dekryptering). Målet er å gjøre meldinger uleselige for uvedkommede og kun leselige for de som vet hvordan klarteksten er omformet.

Eksempel på kryptografi

Olav skal holde en overraskelsesfest for Signe som fyller 50 år. Den eneste som gjenstår av forbredelser er å invitere Jon på festen. Desverre er Jon på hytta uten mobildekning, Signe skal besøke Jon, så Olav bestemmer seg for å sende beskjeden som brev med Signe. Problemet er at Signe IKKE må kunne tyde innholdet i brevet.

På forhånd har Olav og og Jon avtalt at bruker en kode der de bytter om på bokstavene i alfabetet på følgende måte:

a=m g=n m=h s=i y=v
b=s h=a n=g t=å z=k
c=r i=e o=f u=ø æ=x
d=p j=w p=d v=l ø=j
e=y k=o q=b w=q å=t
f=z l=c r=u x=æ  

Beskjeden som Olav skal sende, lyder: "du er invitert til overraskelsesfest for signe på vertshuset mandag klokken to. ikke si noe til signe."

Olav krypterer meldingen ved å erstatte bokstavene meddte tilsvarende bokstavene i tabellen over og får den krypterte meldingen som ser slik ut: "pø yu egleåyuå åec flyuumioyciyizyiå zfu iengy dt lyuåiaøiyå hmgpmn ocfooyg åf. eooy ie gfy åec iengy."

Når Jon skal lese meldingen, må han først dekryptere den. Dette gjør han ved å bruke samme tabell som Olav brukte til å kryptere meldingen med, men erstatter de krypterte bokstavene tilbake til de orginale.

Historien bak RSA

Siden kryptografiens opprinnelse og frem til 1970-tallet hadde man et vedvarende problem i alle krypteringssystemer. Problemet består i å utveksle nøkler. Uansett hvor god kryptering man bruker i tradisjonell kryptografi, er man nødt til å utveksle nøkler på en sikker måte før kryptert kommuniksajon kan foregå.

Mot slutten av 1960-tallet ble DES systemet veldig mye brukt (Spesielt i USA) av militæret, banker og større firmaer. Men problemet med nøkkeldistribusjon ble større og større etterhvert som stadig mer informasjon skulle sendes kryptert.

Whitfield Diffie fra New York var veldig opptatt av problemet med nøkkeldistribusjon, men møtte mye motgang. De fleste innen kryptografimiljøet mente det var umulig å lage et system som unngikk distribusjonsproblemet. Diffie søkte etterhvert kontakt med Martin Hellman og Ralph Merkle.

Etter halvannet års forskning kom endelig gjennombruddet, våren 1976. De kom frem til en metode der to parter blir enige om en felles nøkkel ved å utveksle informasjon som ikke er hemmelig. For eksempel over telefonen. Metoden kalles Diffie-Hellman-Merkle nøkkelutveksling og lever i beste velgående den dag i dag.

Dette er kanskje det viktigste gjennombruddet i kryptografiens historie siden Cæsar-metoden. Men metoden har en ulempe som gjør den upraktisk i endel tilfeller. Når to parter skal bruke metoden, bør de helst ha direkte kontakt fordi informasjon må sendes frem og tilbake en gang for å bli enige om en felles nøkkel.

Diffie kom etterhvert med en ny idé som kunne løse dette problemet. Ideén gikk ut på å lage et nytt krypteringssystem som tok i bruk såkalte asymmetriske nøkler. Tradisjonelt har man brukt den samme nøkkelen for både kryptering og dekryptering (Symmetrisk nøkkel).

Diffie's idé gikk ut på å ha et system med én nøkkel til kryptering (offentlig nøkkel) og en annen nøkkel til dekryptering (privat nøkkel). Den offentlig nøkkelen gjøres kjent til almenheten og den private holdes hemmelig. Meldinger som krypteres med den offentlige nøkkelen kan bare dekrypteres med den private nøkkelen.

Idéen var en helt ny og revolusjonerende måte å tenke på. Men Diffie hadde ikke laget et slikt system, og det var slett ikke sikkert at det var mulig å få til i praksis.

I april 1977 kom nok et gjennombrudd i kryptografiens historie. Tre forskere på M.I.T., Ronald Rivest, Adi Shamir og Leonard Adleman ble kjent med Diffie's idé om asymmetriske nøkler og samarbeidet om problemet. Etter et års intens prøving og feiling kom de endelig frem til RSA systemet slik vi kjenner det i dag.

Matematikken bak RSA

Generering av nøkkelpar:

1) Først genererer vi en offentlig nøkkel. Man finner to store primtall, p og q. For enkelhets skyld kan vi velge p=13 og q=11.

2) Sett N=p*q. I dette tilfellet er N=143.

3) Velg et tall e som ikke har felles faktorer med (p-1)*(q-1). F.eks. e=7.

4) Tallparet N og e utgjør nå den offentlige nøkkelen.

5) Den private nøkkelen d regnes ut ved å løse kongruensen e*d=1(mod (p-1)*(q-1)). I vårt tilfelle får vi 7*d=1(mod 120) som gir d=103.

Kryptering av melding:

Vi starter med en melding M som skal krypteres. For enkelhets skyld velger vi bare et tall som skal krypteres, og setter M=89. Den krypterte meldingen C regnes ut slik: C=M^e (mod N). I vårt tilfelle har vi C=89^7 (mod 143)=67.

Dekryptering av melding:

For å finne M på grunnlag av C og den private nøkkelen d bruker man følgende formel: M=C^d (mod N), som i vårt tilfelle blir M=67^103 (mod 143)=89.

Hvor store bør p og q være?
Enkelt sagt kan vi si at jo større de er, so sikrere er RSA systemet. Ulempen med store p og q er at krypteringen er mer ressurskrevende. I RSA Laboratories' FAQ anbefales det at nøkkelstørrelsen er i størrelsesordenen 1024 bits for normalt bruk, opp til 2048 bits for ekstrem sikkerhet. 1024 bits tilsvarer en N på ca. 310 siffer. (2048 bits tilsvarer ca. 500 siffer i N).

p og q bør ha omtrent like mange siffer. Dette gjør N vanskligere å faktorisere enn hvis det ene primtallet er mye mindre enn det andre.

For få år siden, var det vanlig å generere såkalte "strong prime numbers" for bruk i nøkkelgenereringen. Etter at den såkalte "elliptic curve factoring algorithm" ble brukt i faktoriseringen, er disse spesielle primtallene mer eller mindre gått av moten.

Kilder

www.rsasecurity.com/rsalabs/faq
"The Art of Computer Programming, vol.2", Donald E. Knuth
"The Code Book", Simon Singh
"Bak tallene, Innføring i tallteori", Trygve Breiteig

Implementasjon av RSA

For å implementere RSA systemet, behøver man ikke mye kode. Formlene er få og simple, men for å forstå dem, kreves det kunnskap om modulær aritmetikk.

Vi har valgt å implementere systemet i Java. Vi har laget forskjellige programmer for å generere nøkkelpar, kryptere, dekryptere og tilslutt et program som prøver å knekke systemet ved å faktorisere tallet iden offentlige nøkkelen.

Vi har lagt vekt på at koden skal være enkel å forstå (av programmerere) fremfor å optimalisere den til det ugjenkjennelige. For mer informasjon om det tekniske ved implementeringen, se kommentarer i koden.

Implementasjonen kan lastes ned her: RSAimplementasjon.zip

Kildekode

Oversikt over filene som brukes i implementasjonen

Generator.java - Dette programmet genererer et RSA nøkkelpar med valgfri størrelse. Den offentlige nøkkelen blir skrevet til filen "offentlig-N.txt" og "offentlig-e.txt". Den private nøkkelen blir skrevet til "privat.txt".

privat.txt - Inneholder den private nøkkelen (kalles "d" i koden)

offentlig-e.txt - Inneholder den offentlige eksponenten (kalles "e" i koden)

offentlig-N.txt - Inneholder produktet av primtallene p og q (kalles "N" i koden)

Krypter.java - Leser tallet i "M.txt", samt den offentlige nøkkelen, krypterer og skriver det krypterte tallet til "C.txt".

M.txt - Denne tekstfilen inneholder tallet som skal krypteres, og må lages manuelt. Tallet må være mindre enn den offentlige nøkkelen.

C.txt - Inneholder det krypterte tallet som blir laget av "Krypter.java".

Dekrypter.java - Leser tallet i "C.txt", samt den private nøkkelen, dekrypterer og skriver det dekrypterte tallet til "M.txt".

Verktoy.java - Dette er en klasse som inneholder diverse metoder som brukes av de andre programmene.

Knekk.java - Dette programmet prøver å finne den private nøkkelen på grunnlag av den offentlige nøkkelen ved å faktorisere N ved hjelp av Fermat's metode og skriver resultatet til "knekk-privat.txt".

knekk-privat.txt - Inneholder den private nøkkelen (kalles "d" i koden)

Generator.java

import java.math.BigInteger;

  public class Generator {
    public static void main(String[] args) {
      long p=0, q=0, N, phi, e, d;
      int bits=4, pbits, qbits;

      try {
        bits = new Integer(args[0]).intValue();
        if(bits<5 || bits>63) throw (new Exception());
      } catch (Exception ex) {
        feil();
      }

      pbits = bits/2;
      qbits = bits-pbits;

      java.util.Random r = new java.util.Random();

      while (p<3) p = BigInteger.probablePrime(pbits, r).longValue();
      System.out.print("lager "+pbits+" bits p = "+p+"\n");

      while (q<3) q = BigInteger.probablePrime(qbits, r).longValue();
      System.out.print("lager "+qbits+" bits q = "+q+"\n");

      N = p*q;
      System.out.print("N = p * q = "+p+" * "+q+" = "+N+"\n");
      Verktoy.skriv(N, "offentlig-N.txt");

      phi = (p-1)*(q-1);
      System.out.print("phi = (p-1)*(q-1) = "+(p-1)+" * "+(q-1)+" = "+phi+"\n");

      e = Verktoy.finnE(phi);
      System.out.print("velger en e (innbyrdisk primisk med phi) = "+e+"\n");
      Verktoy.skriv(e, "offentlig-e.txt");

      d = Verktoy.finnD(e, phi);
      System.out.print("finner d ved å løse kongruensen e*d=1(mod phi); d = "+d+"\n");
      Verktoy.skriv(d, "privat.txt");
    }

    private static void feil() {
      System.out.println("java Generator <antall_bits_i_N>");
      System.out.println("Antall bits i nøkkel må være minst 5, maks 63");
      System.exit(1);
    }
  }

Krypter.java

  class Krypter {
    public static void main(String[] args){
      long M, N, e, C;

      M = Verktoy.les("M.txt");
      System.out.println("M = "+M);

      N = Verktoy.les("offentlig-N.txt");
      System.out.println("N = "+N);
      if(N <= M) {
        System.out.println("Feil: For stor M i forhold til N.");
        System.exit(1);
      }

      e = Verktoy.les("offentlig-e.txt");
      System.out.println("e = "+e);

      C = Verktoy.modPow(M, e, N);
      System.out.println("krypterer M; C = M^e (mod N) = "+M+"^"+e+" (mod "+N+") = "+C);
      Verktoy.skriv(C, "C.txt");
    }
  }

Dekrypter.java

  class Dekrypter {
    public static void main(String[] args){
      long C, d, N, M;

      C = Verktoy.les("C.txt");
      System.out.println("C = "+C);

      d = Verktoy.les("privat.txt");
      System.out.println("d = "+d);

      N = Verktoy.les("offentlig-N.txt");
      System.out.println("N = "+N);

      M = Verktoy.modPow(C, d, N);
      System.out.println("dekrypterer C; M = C^d (mod N) = "+C+"^"+d+" (mod "+N+") = "+M);
      Verktoy.skriv(M, "M.txt");
    }
  }

Verktoy.java

  import java.io.*;
  import java.math.BigInteger;

  class Verktoy {

    // gcd finner største felles faktor av u og v
    // ved hjelp av Euklid's algoritme
    static long gcd(long u, long v) {
      long temp;
      while (v != 0) {
        temp = u % v;
        u = v;
        v = temp;
      }
      return u;
    }

    // Finner e på grunnlag av phi.
    // e må være innbyrdes primisk med phi
    public static long finnE(long phi){
      long sff=0, e=2;
      while (sff != 1){
        e++;
        sff = gcd(e, phi);
      }
      return e;
    }

    // Finner d (den private nøkkelen) på grunnlag av
    // e og phi ved å løse kongruensen e*d=1(mod phi)
    public static long finnD(long e, long phi) {
      long u1=1, u2=0, u3=phi, v1=0, v2=1, v3=e;
      long q, d, t1, t2, t3, uu, vv;
      while (v3 != 0) {
        q = u3/v3;
        t1 = u1-q*v1;
        t2 = u2-q*v2;
        t3 = u3-q*v3;
        u1=v1;  u2=v2;  u3=v3;
        v1=t1;  v2=t2;  v3=t3;
      }
      uu = u1;
      vv = u2;
      if (vv < 0) d = vv+phi;
      else d = vv;
      return d;
    }

    // Regner ut a opphøyd i x modulus m
    public static long modPow(long a, long x, long m){
      BigInteger A = new BigInteger(new Long(a).toString());
      BigInteger X = new BigInteger(new Long(x).toString());
      BigInteger M = new BigInteger(new Long(m).toString());
      return A.modPow(X,M).longValue();
    }

    // Skriver et tall til en angitt tekstfil
    public static void skriv(long tall, String filnavn){
      try{
        System.out.println("skriver til "+filnavn);
        FileWriter tekstFilSkriver = new FileWriter(filnavn, false);
        PrintWriter tekstSkriver = new PrintWriter(tekstFilSkriver);
        tekstSkriver.print(tall);
        tekstSkriver.close();
      }
      catch (IOException unntak) {
        System.out.print("error: Feil ved skriving til fil! " + unntak);
      }
    }

    // Leser et tall fra en angitt tekstfil
    public static long les(String filnavn){
      String tallStreng;
      tallStreng="-1";
      try{
        System.out.println("leser fra "+filnavn);
        FileReader tekstFilLeser = new FileReader(filnavn);
        BufferedReader tekstLeser = new BufferedReader(tekstFilLeser);
        tallStreng = tekstLeser.readLine();
      }
      catch (IOException unntak) {
        System.out.print("error: Feil ved lesing av fil! " + unntak);
      }
      return new Long(tallStreng).longValue();
    }
  }

Knekk.java

class Knekk {
    public static void main(String[] args) {
      long N = Verktoy.les("offentlig-N.txt");
      System.out.println("N = "+N);
      long e = Verktoy.les("offentlig-e.txt");
      System.out.println("e = "+e);
      System.out.print("faktoriserer N...");
      long p = faktoriser(N);
      long q = N/p;
      System.out.println("ferdig! N = " + p + " * " + q);
      long phi = (p-1)*(q-1);
      System.out.println("phi = "+phi);
      long d = Verktoy.finnD(e, phi);
      System.out.println("d = "+d);
      Verktoy.skriv(d, "knekk-privat.txt");
    }

    // Returnerer den største faktoren i N
    // mindre eller lik kvadratroten av N.
    // Algoritmen er hentet fra Donald Knuth,
    // The Art of Computer Programming, vol.2.
    static long faktoriser(long N) {
      long sqrtN, x, y, r;

      if (N<3 || N%2 == 0)
        throw new ArithmeticException("N<2 eller ikke oddetall");

      sqrtN = (long)Math.sqrt(N);
      x = 2*sqrtN + 1;
      y = 1;
      r = sqrtN*sqrtN - N;

      while (r!=0) {
        r += x;
        x += 2;
        while (r>0) {
          r -= y;
          y += 2;
        }
      }
      return (x-y)/2;
      // N = ((x-y)/2)*((x+y-2)/2),
      // og (x-y)/2 er den største faktoren
      // av N mindre eller lik sqrt(N)
    }
  }