RSA

RSA er en krypteringsalgoritme basert på offentlig nøkkel (en.: public key).


== Drift ==
For å bruke RSA-algoritmen må den gjennom tre steg; generering av nøkkeltall, kryptering og dekryptering.


=== Generering av nøkkeltall ===
Mottaker finner fram to primtall som 
  
    
      
        p
      
    
    {\displaystyle p}
   og 
  
    
      
        q
      
    
    {\displaystyle q}
   og regner ut 
  
    
      
        n
        =
        p
        ⋅
        q
      
    
    {\displaystyle n=p\cdot q}
   og 
  
    
      
        b
        =
        (
        p
        −
        1
        )
        ⋅
        (
        q
        −
        1
        )
      
    
    {\displaystyle b=(p-1)\cdot (q-1)}
  . For at dette skal bli tilstrekkelig sikkert må man velge to store primtall (over noen 100 siffer i hver).
Nå velger mottaker et tall 
  
    
      
        e
      
    
    {\displaystyle e}
   slik at 
  
    
      
        s
        f
        d
        (
        e
        ,
        b
        )
        =
        1
      
    
    {\displaystyle sfd(e,b)=1}
  
Tallene 
  
    
      
        n
      
    
    {\displaystyle n}
   og 
  
    
      
        e
      
    
    {\displaystyle e}
   kan nå offentliggjøres for at sender kan begynne kryptering. Dette er den offentlige nøkkelen (en.: public key).
Kongruensen 
  
    
      
        e
        d
        ≡
        1
        
          
          (
          mod
          
          b
          )
        
      
    
    {\displaystyle ed\equiv 1{\pmod {b}}}
   regnes nå ut, og det minste positive tallet velges til det hemmelige tallet 
  
    
      
        d
      
    
    {\displaystyle d}
  . (
  
    
      
        d
      
    
    {\displaystyle d}
  = hemmelig dekrypteringsnøkkel).


=== Kryptering ===
Meldingen som skal sendes gjøres om til tall. La 
  
    
      
        M
      
    
    {\displaystyle M}
   være ett av tallene.
Vi finner nå det minste positive tallet for 
  
    
      
        N
      
    
    {\displaystyle N}
  , slik at 
  
    
      
        N
        ≡
        
          M
          
            e
          
        
        
          
          (
          mod
          
          n
          )
        
      
    
    {\displaystyle N\equiv M^{e}{\pmod {n}}}
  . Resten ved divisjonen 
  
    
      
        
          M
          
            e
          
        
        :
        n
      
    
    {\displaystyle M^{e}:n}
   er altså den hemmelige meldingen.
Nå kan avsender sende 
  
    
      
        N
      
    
    {\displaystyle N}
   til mottaker.


=== Dekryptering ===
I dekrypteringsprosessen er 
  
    
      
        M
      
    
    {\displaystyle M}
   det minste positive tallet i 
  
    
      
        M
        ≡
        
          N
          
            d
          
        
        
          
          (
          mod
          
          n
          )
        
      
    
    {\displaystyle M\equiv N^{d}{\pmod {n}}}
  . Ved å finne resten av 
  
    
      
        
          N
          
            d
          
        
        :
        n
      
    
    {\displaystyle N^{d}:n}
   kan man finne meldingen, 
  
    
      
        M
      
    
    {\displaystyle M}
  .


=== Eksempel ===


==== Generering av nøkkeltall ====
Vi velger to primtall som 
  
    
      
        p
      
    
    {\displaystyle p}
   og 
  
    
      
        q
      
    
    {\displaystyle q}
  . 

  
    
      
        p
        =
        5
      
    
    {\displaystyle p=5}
   og 
  
    
      
        q
        =
        7
      
    
    {\displaystyle q=7}
  

Vi finner n og b.

  
    
      
        n
        =
        p
        ⋅
        q
        =
        5
        ⋅
        7
        =
        35
      
    
    {\displaystyle n=p\cdot q=5\cdot 7=35}
  
  
    
      
        b
        =
        (
        p
        −
        1
        )
        (
        q
        −
        1
        )
        =
        (
        5
        −
        1
        )
        (
        7
        −
        1
        )
        =
        4
        ⋅
        6
        =
        24
      
    
    {\displaystyle b=(p-1)(q-1)=(5-1)(7-1)=4\cdot 6=24}
  

Nå må vi finne en verdi for 
  
    
      
        e
      
    
    {\displaystyle e}
   slik at 
  
    
      
        s
        f
        d
        (
        e
        ,
        b
        )
        =
        1
      
    
    {\displaystyle sfd(e,b)=1}
  .
Vi faktoriserer 
  
    
      
        b
      
    
    {\displaystyle b}
  .
  
    
      
        24
        =
        2
        ⋅
        2
        ⋅
        2
        ⋅
        3
      
    
    {\displaystyle 24=2\cdot 2\cdot 2\cdot 3}
   
Nå velger vi et tall for 
  
    
      
        e
      
    
    {\displaystyle e}
  . Vi kan velge 
  
    
      
        e
        =
        11
      
    
    {\displaystyle e=11}
   siden 
  
    
      
        11
      
    
    {\displaystyle 11}
   ikke finnes i 
  
    
      
        24
      
    
    {\displaystyle 24}
  
Vi ser at 
  
    
      
        s
        f
        d
        (
        11
        ,
        24
        )
        =
        1
      
    
    {\displaystyle sfd(11,24)=1}
  

Vi offentliggjør nøklene n og e, (e = encryption key)

  
    
      
        n
        =
        35
      
    
    {\displaystyle n=35}
   og 
  
    
      
        e
        =
        11
      
    
    {\displaystyle e=11}
  

Nå må vi lage det hemmelige tallet 
  
    
      
        d
      
    
    {\displaystyle d}
  .

  
    
      
        e
        d
        ≡
        1
        
          
          (
          mod
          
          b
          )
        
      
    
    {\displaystyle ed\equiv 1{\pmod {b}}}
  
  
    
      
        11
        d
        ≡
        1
        
          
          (
          mod
          
          24
          )
        
      
    
    {\displaystyle 11d\equiv 1{\pmod {24}}}
  
  
    
      
        11
        d
        ≡
        1
        +
        5
        ⋅
        24
        
          
          (
          mod
          
          24
          )
        
      
    
    {\displaystyle 11d\equiv 1+5\cdot 24{\pmod {24}}}
  
  
    
      
        11
        d
        ≡
        121
        
          
          (
          mod
          
          24
          )
        
      
    
    {\displaystyle 11d\equiv 121{\pmod {24}}}
  
  
    
      
        11
        d
        ≡
        11
        ⋅
        11
        
          
          (
          mod
          
          24
          )
        
      
    
    {\displaystyle 11d\equiv 11\cdot 11{\pmod {24}}}
  
  
    
      
        d
        ≡
        11
        
          
          (
          mod
          
          24
          )
        
      
    
    {\displaystyle d\equiv 11{\pmod {24}}}
  

Det hemmelige tallet er dermed 
  
    
      
        d
        =
        11
      
    
    {\displaystyle d=11}
   (d=decryption key)

OBS: 
  
    
      
        e
      
    
    {\displaystyle e}
   og 
  
    
      
        d
      
    
    {\displaystyle d}
   er ikke alltid like. Det er bare en tilfeldighet at de er like i dette eksemplet.


==== Kryptering ====
Vi mottar de offentlige nøklene 
  
    
      
        e
      
    
    {\displaystyle e}
   og 
  
    
      
        n
      
    
    {\displaystyle n}
  

  
    
      
        e
        =
        11
      
    
    {\displaystyle e=11}
   og 
  
    
      
        n
        =
        35
      
    
    {\displaystyle n=35}
  

Meldingen 
  
    
      
        M
        =
        8
      
    
    {\displaystyle M=8}
   ønskes å bli sendt, men den må krypteres først.
For å finne 
  
    
      
        N
      
    
    {\displaystyle N}
  , den krypterte meldingen, gjør vi slik:

  
    
      
        N
        ≡
        
          M
          
            e
          
        
        
          
          (
          mod
          
          n
          )
        
      
    
    {\displaystyle N\equiv M^{e}{\pmod {n}}}
  
  
    
      
        N
        ≡
        
          8
          
            11
          
        
        
          
          (
          mod
          
          35
          )
        
      
    
    {\displaystyle N\equiv 8^{11}{\pmod {35}}}
  
  
    
      
        N
        ≡
        8589934592
        
          
          (
          mod
          
          35
          )
        
      
    
    {\displaystyle N\equiv 8589934592{\pmod {35}}}
  
  
    
      
        N
        ≡
        8589934592
        −
        245426702
        ⋅
        35
        
          
          (
          mod
          
          35
          )
        
      
    
    {\displaystyle N\equiv 8589934592-245426702\cdot 35{\pmod {35}}}
  
  
    
      
        N
        ≡
        22
        
          
          (
          mod
          
          35
          )
        
      
    
    {\displaystyle N\equiv 22{\pmod {35}}}
  

Den hemmelige meldingen er 
  
    
      
        N
        =
        22
      
    
    {\displaystyle N=22}
  


==== Dekryptering ====
Vi mottar den krypterte meldingen 
  
    
      
        N
      
    
    {\displaystyle N}
  .

  
    
      
        N
        =
        22
      
    
    {\displaystyle N=22}
  

Fra tidligere kjenner vi den hemmelige nøkkelen 
  
    
      
        d
      
    
    {\displaystyle d}
   og den offentlige nøkkelen 
  
    
      
        n
      
    
    {\displaystyle n}
  

  
    
      
        d
        =
        11
      
    
    {\displaystyle d=11}
   og 
  
    
      
        n
        =
        35
      
    
    {\displaystyle n=35}
  

Vi ser at det er en sammenheng mellom 
  
    
      
        N
      
    
    {\displaystyle N}
  , 
  
    
      
        d
      
    
    {\displaystyle d}
   og 
  
    
      
        n
      
    
    {\displaystyle n}
   slik at vi kan finne 
  
    
      
        M
      
    
    {\displaystyle M}
  .

  
    
      
        M
        ≡
        
          N
          
            d
          
        
        
          
          (
          mod
          
          n
          )
        
      
    
    {\displaystyle M\equiv N^{d}{\pmod {n}}}
  

  
    
      
        M
        ≡
        
          22
          
            11
          
        
        
          
          (
          mod
          
          35
          )
        
      
    
    {\displaystyle M\equiv 22^{11}{\pmod {35}}}
  

For å få lettere tall å regne med så bruker vi litt kreativ regning. Vi ser på eksponenter av 22 som er lavere enn 11.

  
    
      
        
          22
          
            1
          
        
        =
        22
        ≡
        22
        
          
          (
          mod
          
          35
          )
        
      
    
    {\displaystyle 22^{1}=22\equiv 22{\pmod {35}}}
  
  
    
      
        
          22
          
            2
          
        
        =
        484
        ≡
        29
        
          
          (
          mod
          
          35
          )
        
      
    
    {\displaystyle 22^{2}=484\equiv 29{\pmod {35}}}
  
  
    
      
        
          22
          
            4
          
        
        =
        (
        
          22
          
            2
          
        
        
          )
          
            2
          
        
        ≡
        
          29
          
            2
          
        
        ≡
        841
        ≡
        1
        
          
          (
          mod
          
          35
          )
        
      
    
    {\displaystyle 22^{4}=(22^{2})^{2}\equiv 29^{2}\equiv 841\equiv 1{\pmod {35}}}
  
  
    
      
        
          22
          
            8
          
        
        =
        (
        
          22
          
            4
          
        
        
          )
          
            2
          
        
        ≡
        
          1
          
            2
          
        
        ≡
        1
        
          
          (
          mod
          
          35
          )
        
      
    
    {\displaystyle 22^{8}=(22^{4})^{2}\equiv 1^{2}\equiv 1{\pmod {35}}}
  

Vi ser at 
  
    
      
        11
        =
        1
        +
        2
        +
        8
      
    
    {\displaystyle 11=1+2+8}
  

  
    
      
        
          22
          
            1
          
        
        ⋅
        
          22
          
            2
          
        
        ⋅
        
          22
          
            8
          
        
        ≡
        22
        ⋅
        29
        ⋅
        1
        
          
          (
          mod
          
          35
          )
        
      
    
    {\displaystyle 22^{1}\cdot 22^{2}\cdot 22^{8}\equiv 22\cdot 29\cdot 1{\pmod {35}}}
  
  
    
      
        
          22
          
            1
            +
            2
            +
            8
          
        
        ≡
        638
        
          
          (
          mod
          
          35
          )
        
      
    
    {\displaystyle 22^{1+2+8}\equiv 638{\pmod {35}}}
  
  
    
      
        
          22
          
            11
          
        
        ≡
        638
        −
        18
        ⋅
        35
        
          
          (
          mod
          
          35
          )
        
      
    
    {\displaystyle 22^{11}\equiv 638-18\cdot 35{\pmod {35}}}
  
  
    
      
        
          22
          
            11
          
        
        ≡
        8
        
          
          (
          mod
          
          35
          )
        
      
    
    {\displaystyle 22^{11}\equiv 8{\pmod {35}}}
  

Vi har nå funnet den krypterte meldingen

  
    
      
        M
        =
        8
      
    
    {\displaystyle M=8}
  


== Historie ==
Algoritmen ble først beskrevet i 1977 av Ron Rivest, Adi Shamir og Leonard Adleman ved MIT; de tre bokstavene RSA er initialene i etternavnene deres i samme rekkefølge som de fremkommer på artikkelen deres.Den Britiske matematikeren Clifford Cocks beskrev et lignende system i et internt dokument for den britiske etterretningstjenesten GCHQ. Hans oppdagelse ble ikke offentliggjort før i 1997, grunnet top-secret klassifisering av arbeidet.
MIT fikk et patent på "Cryptographic communications system and method" som benyttet algoritmen i 1983. Patentet ville vært gyldig til 2003, men ble offentliggjort av RSA 21. september 2000.


== Referanser ==