Kryptografi og nettverkssikkerhet (Kapittel 2: Tallteori)

Dagens tekst er hentet fra kapittel 2 i Cryptography and Network Security.

Ber på forhånd om unnskylding til eventuelle matematikere som leser bloggen for misbruk av “norske” matematiske termer…

Dette kapittelet er ment å gi et grunnlag i tallteori som senere vil være nyttig for å forstå algoritmer som blir presentert.

Delbarhet

Vi sier at b deler a hvis a = mb, der a, b, og m er heltall. b deler a hvis det ikke er noen rest når man dividerer.  b | a er notasjonen som brukes. Hvis b | a sier vi at b er en divisor av a.

Noen egenskaper ved delbarhet:

  • Hvis a | 1, så a = ±1
  • Hvis a | b og b | a, så a = ±b
  • Enhver b ≠ 0 deler 0
  • Hvis a | b og b | c, så a | c
  • Hvis b | g og b | h, så b | (mg + nh) for vilkårlige heltall m and n

Gitt et vilkårlig positivt heltall n og et vilkårlig ikke-negativt heltall a, hvis vi deler a med n får vi en heltallskvotient q og en heltallsrest r som oppfyller følgende sammenheng:

  a = qn + r             0 ≤ r < n; q = [a/n]

Største felles divisor (GCD)

Den største felles divisor av a og b er det største heltallet som deler både a og b. Vi kan bruke notasjonen gcd(a,b). Vi definerer også gcd(0,0) = 0. Et positivt heltall c sies å være gcd av a og b hvis:

  • c er en divisor av a og b
  • Enhver divisor av a og b er også en divisor av c

En ekvivalent definisjon er:
gcd(a,b) = max[k, slik at k | a og k | b]

Modulær Aritmetikk

Hvis a er et heltall, og n er et positivt heltall, definerer vi a mod n til å være resten når a deles med n; heltallet n kalles modulus. Følgelig, for ethvert heltall a:

   a =  qn +  r   0 ≤ r < n;  q = [a/ n]

    a = [a/ n] *  n + ( a mod n)

To heltall a og b sies å være kongruent modulo n hvis (a mod n) = (b mod n). Dette skrives a ≡ b (mod n). Bemerk at hvis a ≡ 0(mod n), så har vi at n | a

Kongruenser har følgende egenskaper:

  1. a ≡ b (mod n) hvis n | (a – b)
  2. a ≡ b (mod n) impliserer at b ≡ a (mod n)
  3. a ≡ b (mod n) og b ≡ c (mod n) impliserer at a ≡ c (mod n)

For å demonstrere det første punktet, hvis n | (a – b), så er (a – b) = kn for en eller annen k; vi kan skrive a = b + kn. Følgelig, (a mod n) = (rest når b + kn divideres med n) = (rest når b divideres med n) = (b mod n).

Modulær aritmetikk har følgende egenskaper:

  1. [(a mod n) + (b mod n)] mod n = (a + b) mod n
  2. [(a mod n) – (b mod n)] mod n = (a – b) mod n
  3. [(a mod n) * (b mod n)] mod n = (a * b) mod n

Vi kan demonstrere den første egenskapen:

Definer (a mod n) = ra og (b mod n) = rb. Vi kan da skrive a = ra + jn for et eller annet heltall j og b = rb + kn for et eller annet heltall k. Deretter:

(a + b) mod n = (ra + jn + rb + kn) mod n
= (ra + rb + (k + j)n) mod n
= (ra + rb) mod n
= [(a mod n) + (b mod n)] mod n

Ettersom vi krever at GCD er positiv, gcd(a,b) = gcd(a,-b) = gcd(-a,b) = gcd(-a,-b). Generelt, gcd(a,b) = gcd(| a |, | b |). Dessuten, ettersom alle heltall (unntatt 0) deler 0, har vi at gcd(a,0) = | a |. Vi har sagt at to heltall a og b er relativt primsk hvis deres eneste felles positive heltallsfaktor er 1; dette er ekvivalent med å si at a og b er relativt primsk hvis gcd(a,b) = 1.

Vi kan finne additive og multiplikative inverser modulo 8. Den additive inversen -w for et heltall w er gitt ved w+(-w) ≡ 0 (mod 8); for multiplikasjon har vi w*w-1 ≡ 1 (mod 8). Av dette ser vi at det ikke finnes multiplikative inverser for alle tall modulo 8.

ex:
w =2, -w=6: 2+6 ≡ 0 (mod 8)
w=5, w-1=5: 5*5 = 25 ≡ 1 (mod 8)

Euklids algoritme

Euklids algoritme er en prosedyre for å finne største felles divisor til to positive heltall, den er en av de fundamentale teknikkene i tallteori. To heltall er som kjent relativt primsk dersom deres eneste felles heltallsfaktor er 1.

euclid(a,b)
if (b==0) then return a;
else return euclid(b, a mod b);

Primtall

Primtall er et sentralt begrep i tallteori. Primtall har kun 1 og seg selv som divisorer, og de kan følgelig ikke skrives som et produkt av andre tall. Ethvert heltall a > 1 kan faktoriseres på en unik måte som a = p1a1 * p2a2 * . . . * ptat, hvor p1 < p2 < . . .  < pt  er primtall, og hvor hver ai er et positivt heltall. Dette er kjent som det fundamentale teoremet i aritmetikk.

Fermats teorem

Fermats teorem sier at hvis p er et primtall og a er et positivt heltall som ikke kan deles av p så har vi ap-1 ≡ 1 (mod p). Alternativt kan vi si: Hvis p er et primtall og a er et positivt heltall, så har vi ap ≡ a (mod p).

Eulers Teorem

Eulers Totient-funksjon φ(n) gir antallet heltall mindre enn n som er relativt primsk med n.

Eulers teorem sier at for enhver a og n som er relativt primsk:

aφ(n) ≡  1(mod n)

En alternativ form er:

aφ(n)+1 ≡ a(mod n)

Miller-Rabin Algoritmen

Miller-Rabin-algoritmen brukes for å teste om et stort tall er et primtall. Algoritmen er som følger:

TEST (n)

  • Finn heltall k, q, med k > 0, q odde, slik at (n – 1)=2kq ;
  • Velg et tilfeldig heltall a, 1 < a < n – 1 ;
  • if aq mod n = 1 then return (“inconclusive”) ;
  • for j = 0 to k – 1 do
    • if (a2jq mod n = n – 1) then return (“inconclusive”) ;
  • return (“composite”) ;

Determinisk Primalitets Algoritme

Fram til 2002 var det ingen kjent metode for effektivt å bevise at et veldig stort tall var et primtall; alle algoritmene som var i bruk ga et probabilistisk resultat. I 2002 utviklet Agrawal, Kayal, og Saxena en algoritme (AKS-algoritmen) som effektivt avgjør om et gitt stort tall er et primtall. Den later ikke til å være like effektiv som Miller-Rabin algoritmen, men til gjengjeld er den altså deterministisk.

Det kinesiske restteoremet – Chinese Remainder Theorem (CRT)

Antatt å ha bliltt oppdaget av den kinesiske matematikeren Sun Tsu (også kjent Sun Tzu eller Sun Zi) rundt the 3. århundre (må ikke forveksles med general Sun Zi (Sun Tzu) som skrev “Kunsten å krige” rundt 700 år tidligere). Dette regnes som en av de mest nyttige resultatene i tallteori. CRT sier at det er mulig å rekonstruere heltall i et bestemt intervall modulo et sett av parvise prime moduli. Det kan formuleres på flere måter, og gir oss en måte å manipulere (potensielt veldig store) tall modulo M ved hjelp av tupler av mindre tall; dette kan være nyttig der hvor M består av 150 siffer eller mer. Imidlertid er det nødvendig å kunne faktorisere M på forhånd.

Hvis vi tar 10 som et eksempel, er de parvis prime faktorene 2 og 5. Gitt at vi har et siffer x hvor x mod 2 = 0 og x mod 5 = 3. Dette gir en unik løsning x = 8.

Logaritmer

Definisjonen på den briggske logaritmen til x (som vi pleide skrive log(x)) er “hva må i opphøye 10 med for å få x?” For en logaritme med vilkårlig base x har vi:

y = xlogx(y)

Flere egenskaper ved logaritmer:

logx(1) = 0

logx(x)= 1

logx(yz) = logx(y) + logx(z)

logx(yr) = r × logx(y)

Diskrete logaritmer

b ≡ ai(mod p), hvor 0 ≤ i ≤ (p-1)

Denne eksponenten i kalles den diskrete logaritmen av tallet b for basen a (mod p).