Export page to Open Document format View page as slide show

Tietoturva

Matematiikkaa

  • Monet kryptografiset primitiivit perustuvat matematiikkaan.
    • Jotta ymmärtää menetelmien toiminnan on tunnettava perusteet taustalla.
    • Dataa käsitellään numeroarvoina binäärien sijaan.
      • Binäärinen data käsitellään positiivisina kokonaislukuina
  • Tiedon manipulointi toteutetaan matemaattisilla funktioilla.
    • esim. Salattutieto = f(selkoteksti)

Lukuteorian perusteet

  • Lukuteoria käsittelee kokonaislukujen erilaisia ominaisuuksia
  • Jaollisuus ja jakojäännös
    • div fuktio palauttaa kokonaislukuosan jako-operaatiosta, mod funktio palauttaa jakojäännöksen.
      • \frac{5}{2}=2\frac{1}{2} \mapsto 5 div 2 = 2 , 5 mod 2 = 1
    • Jos b mod a = 0, niin a on b:llä jaollinen eli a on b:n tekijä
      • tällöin on olemassa kokonaisluku k niin b =a*k
      • merkitään a \mid b
  • Modulus operaatiota käytetään jotta tulokset pysyvät halutulla alueella.
    • f(x)=g(x) mod 4 varmistaa että funktion f(x) tulos on korkeintaan 2 bittiä pitkä
      • Lopputulokseen lisätään tarvittaessa nollia eteen, jotta funktion lopputulos on aina saman suuruinen

Lukuteoria: alkuluvut

  • Luku p (>0) on alkuluku jos se on jaollinen vain itsellään ja 1:llä
    • Alkulukuja tarvitaan mm. epäsymmetrisessä salauksessa
  • Numero joka ei ole alkuluku on jaollinenluku (yhdistetty luku, composite number)
    • Jaollisialukuja voidaan esittää aina alkulukujen tulona.
    • Jaollisen luvun tekijöiden etsimistä kutsutaan tekijöihin jaoksi (factorization)
    • Luku voidaan jakaa tekijöihin vain yhdellä tavalla.
      • 54=2*27=2*3*9=2*3*3*3 = 2*3^{3}

Suhteellinen alkuluku (relatively prime, coprime)

  • Kaksinumero ovat suhteellisesti alkulukuja jos heidän suurin yhteinen tekijä (syt, greatest common divisor) on yksi.
    • syt (p,q) = 1 { gcd (p,q) = 1 }
  • Suurin yhteinen tekijä
    • Suurin kokonaisluku joka on tekijä sekä a:lle että b:lle
    • Jos p on alkuluku ja p>q niin gcd(p,q)=1

∗ p ja q ovat suhteellisesti alkulukuja toisilleen.

  • Voidaan ratkaista euklideaan algoritmilla

Euklideaan algoritmi

  • Euclidean algorithm
    • syt (a,b) (tai gcd (a,b) )
    • Olkoon a=q*b+r , jossa a>b, q=a\: div\: b and r=a\: mod\: b
    • Toista kaava: b=q'*r+r' , jossa q'=b\: div\: r and r'=b\: mod\: r
    • Kun r'=0. niin r kaavassa on a:n ja b:n suurin yhteinen tekijä.

Laajennettu Euklideaan algoritmi

  • Kokonaisluvuille a ja b on olemassa kokonaisluvut s ja t niin että a*s+b*t=syt(a,b)
    • Näitä arvoja tarvitaan esimerkiksi modulus jakolaskuissa
    • s ja t voidaan löytää käyttäen laajennettua Euklideaan algoritmia (extended euclidean algorithm)
  • as+bt=gcd(a,b)
    • Jaetaan a b:llä → a=q_{1}b+r_{1}ja jatketaan Euklideaan algoritmilla kasvattaen q:n ja r:n indeksejä kierroksittain
    • Muodostetaan sarjat s_{0}=0,s_{1}=1,s_{j}=-q_{j-1}s_{j-1}+s_{j-2} ja t_{0}=1,t_{1}=0,t_{j}=-q_{j-1}t_{j-1}+t_{j-2}
      • Sarjojen alut ovat toisilleen käänteiset.
    • Etsityt s ja t ovat arvot joilla on sama indeksi kuin viimeisellä q:lla.
    • Viimeiset arvot jotka s:lle ja t:lle voidaan laskea ovat a:n ja b:n arvot jaettuna niiden suurimmalla yhteisellä tekijällä.
    • Algoritmia käytetään usein kongruenssien löytämiseen.

Lukuteoria: Modulaari algebra

  • “Kello matematiikkaa”: 5 hours after 9 it is 2 o'clock
    • 9+5\equiv2\:(mod\:12) or 9+5\equiv_{12}2
  • Kongruentti (yhteneväisyys, congruent) (\equiv) : a\equiv b\:(mod\: n) a on kongruentti b mod n
    • eli a=b+kn ,jossa k on mikä tahansa kokonaisluku
    • Ekvivalenssi: x on ekvivalentti y:lle : x\equiv_{n}y , jos (x\: mod\: n)=(y\: mod\: n)\Longrightarrow x\equiv_{n}y jos (x-y)=k*n millä tahansa k:lla
    • Kongruenssi toimii yleensä kuten yhtäsuuruus (=)

Kongruenssin ominaisuuksia

  • Associativity
    [a+(b+c)]\: mod\: n=[(a+b)+c]\: mod\: n
    [a*(b*c)\: mod\: n]=[(a*b)*c]\: mod\: n
  • Commutativity (a+b)\: mod\: n=(b+a)\: mod\: n
    (a*b)\: mod\: n=(b*a)\: mod\: n
  • Distributivity a*(b+c)]\: mod\: n=[(a*b)+(a*c)]\: mod\: n
  • Existence of identities (a+0)\: mod\: n=a\: mod\: n=a\:\,\,\,\, if\,\: a<n
    (a*1)\: mod\: n=a\: mod\: n=a\:\,;\, if\,\: a<n
  • Reducibility (a+b)\: mod\: n=((a\: mod\: n)+(b\: mod\: n))\: mod\: n
    (a*b)\: mod\: n=((a\: mod\: n)*(b\: mod\: n))\: mod\: n
  • Existence of inverse a+(-a)\! mod\: n=0
    a*(a^{-1})\: mod\: n=1\:\,\, iff\: a\neq0
  • addition, multiplication and subraction of modulus works normally
    • if a\equiv_{n}b and c\equiv_{n}d then
      a+c\equiv_{n}b+d\rightarrow a\equiv_{n}b+d-c
      a-c\equiv_{n}b-d
      a*c\equiv_{n}b*d

Jakolasku modulus n

  • a voi olla jakaja mod n jos gcd(a,n) = 1
    • 2x\equiv_{5}4\rightarrow x\equiv2(Jako voidaan tehdä koska gcd (2,5)=1)
  • Murtoluvut voidaan käsitellä käänteislukuna modulossa
    a^{-1}=\frac{1}{a}
    joten \frac{a}{b}\, mod\, n on sama kuin \frac{a}{b}\, mod\, n
  • jako jos gcd(a,n) > 1
    • Yritetään ratkaista x yhtälöstä a*x\equiv_{n}b ja gcd (a,n) =d, d >1
    • jos d ei jaa b:tä, niin ratkaisua ei ole olemassa!
    • jos d\mid b voit yrittää muokata kaavaa (\frac{a}{d})*x\equiv\frac{b}{d}\, mod\,\frac{n}{d} , ratkaise uusi kaava saadaksesi x
    • ratkaisut x:lle ovat x_{0},x_{0}+\frac{n}{d},x_{0}2*(\frac{n}{d})

Käänteisluku modulossa

  • a:n käänteisluku on luku joka kerrottaessa a:lla on 1
    • a^{-1}*a=1\Longrightarrow a*b\: mod\: m=1\Rightarrow a^{-1}mod\: m=b
    • Esim: 13^{-1}mod\:55=17\Rightarrow13*17\: mod\:55=1
  • Käänteisluvun löytäminen modulossa
    • a^{-1}\equiv s\:(mod\: n)\rightarrow\frac{1}{a}\equiv s\:(mod\: n)joten gcd(a,n) täytyy olla 1 (a on jakaja)
    • koska a^{-1}*a=1\rightarrow a^{-1}*a\equiv1\, mod\, n jos merkitään a^{-1}=s voidaan sanoa että on olemassa arvo t niin että as+nt=1,
    • Laajennetulla euclideaan algoritmin avulla voidaan ratkaista arvo s edellisestä kaavasta
  • Esimerkki: 13^{-1}mod\:55\rightarrow13*s+55*t=1\\55=4*13+3q_{1}=4 \\13=4*3+1q_{2}=4\\3=3*1+0q_{3}=3
    • Viimeisen osamäärän indeksi on 3
    • satjat s:lle ovat: s_{0}=0,s_{1}=1,s_{2}=-4_{q1}1_{s1}+0_{so}=-4,s_{3}=-4_{q2}-4_{s2}+1=17
    • s_{3}=17 Joten käänteisluku 13 mod (55) :lle on 17
    • sarjat t:lle olisivat: t_{0}=1,t_{1}=0,t_{2}=-4_{q1}0_{t1}+1_{to}=1,t_{3}=-4_{q2}1_{t2}+0_{t1}=-4
    • tuloksena 13*17+55(-4)=1 –> gcd (13,17) = 1

Exponenttiin korotus moduluksilla

  • Eksponenttiin korotus voidaan jakaa useaam kertolaskuun ja käyttää kertolasku sääntöjä.
    • Esimkeriksi: 3^{5}mod\,5=(3^{3}*3^{2})\, mod\,5
      • 3\, mod\,5=3
      • 3^{2}mod\,5=9\, mod\,5=4
      • 3^{3}mod\,5=(3^{2}mod\,5*3\, mod\,5)\, mod\,5=4*3\, mod\,5=12\, mod\,5=2
      • 3^{5}mod\,5\,=(3^{2}mod\,5*3^{3}mod\,5)\, mod\,5\,=4*2\, mod\,5=3
    • Ei tarvitse käsitellä lukuja jotka ovat suurempia kuin n^{2},
      • Kryptografiassa nostetaan suuria lukuja potenssiin.
      • Menetelmän avulla säästyy muistia ja laskenta nopeutuu.

Kiinalainen jakojäännös teoreema

  • Chinese remainder theorem
  • for x\equiv a_{1}mod\, n_{1},x\equiv a_{2}mod\, n_{2} ,x\equiv a_{3}mod\, n_{3}x\equiv a_{k}mod\,, with gcd(n_{i},n_{j})=1when i\neq j There is a common unique solution for x in [0, n-1], where n=n_{1}*n_{2}*...*n_{k}
    • the moduluses n are pairwise relatively prime
  • Simple example: x\equiv4\, mod\,7,x\equiv1\, mod\,6
    • x=7k+4 use this as value of x for x\equiv1\, mod\,6
    • 7k+4\equiv1\, mod\,6\rightarrow7k\equiv-3\, mod\,6
      • 7mod\,6=1\rightarrow k\equiv3\, mod\,6\rightarrow k=6s+3
    • use value of k to first equation
      • x=7*(6s+3)+4=42s+25 \rightarrow x\equiv25\, mod\,42e.g. x=25,67,109…
      • 6*7=42

Eulerin totient function

  • Eulerin totient funktio, \phi(n) funktio (Euler's \phi -function, totient function, Euler's totient function)
    • Palauttaa lukumäärän n:ää pienemmistä luvuista, jotka ovat suhteellisesti alkulukuja n:n kanssa eli lukujen määrän joiden suurin yhteinen tekijä n:n kanssa on 1.
    • \phi(10)=4 → 1,3,7,9 (2,4,6 ja 8:lla on suurin yhteinen tekijä 10 kanssa 2 sekä gcd(5,10)=5)
    • Alkuluvulle p: \phi(p)=p-1
    • Lisäksi:\phi(pq)=(p-1)(q-1) jos p ja q ovat alkulukuja
      • 10=5*2 (jaetaan 10 tekijöihin) joten p=5 and q= 2
        \phi(10)=\phi(5*2)=(5-1)(2-1)=4
    • \phi(p^{r})=(1-\frac{1}{p})p^{r}
      • \phi(3^{2})=(1-\frac{1}{3})*9=\frac{2}{3}*9=6 (1,2,4,5,7,8)
    • Yleisesti: \phi(n)=n\prod_{p\mid n}(1-\frac{1}{p}) , jossa p on uniikki alkuluku joka on n:n tekijä
      • Esim: 1000=2^{3}*5^{3}\rightarrow\phi(1000)=1000(1-\frac{1}{2})(1-\frac{1}{5})=40

Fermat:n pieni teoreeman ja eulerin teoreema

  • Fermat Little Theorem: a^{p-1}\: mod\: p=1 Kun p on alkuluku eikä a ole p:n tekijä
    muistetaan aiemmasta että: a^{p}\: mod\: p=a jako a:lla antaa: a^{p-1}\: mod\: p=1
  • Eulerin teoreema : a^{\phi(p)}\equiv_{p}1 jos gcd (a,p) = 1 eli a ja p eivät jaa toisiaan
    • jos p on alkuluku niin \phi(p)=p-1
      • Nämä yhdistämällä huomaamme että EUlerin teoreema on Fermat:n teoreeman yleistys
      • a^{\phi(p)}\equiv_{p}1 alkuluvulle a^{p-1}\equiv_{p}

Fermat:n hyödyntäminen käänteisluvun mod p löytämisessä

  • x on a:n käänteisluku mod p jos: ax\: mod\: p=1
  • Fermat sanoo a^{p-1}\: mod\: p=1 joten ax\: mod\: p=a^{p-1}mod\: p
  • Jaetaan molemmat puolet a:lla
    \rightarrow x=a^{p-2}\: mod\: p

Fermat hyödyntäminen suuriin potensseihin nostossa mod n

  • Esimerkiksi: laske 2^{3434309}mod\,101

    \rightarrow2^{3434309}\equiv_{101}(2^{100})^{34343}*2^{09}
  • Fermat:n teoreemasta saamme \rightarrow2^{100}mod\,101=1joten 1^{34343}*2^{9}\equiv_{101}2^{9}\rightarrow512\equiv_{101}=7
  • mod n:llä toimiessa yritä siis saada \phi(n) exponentiksi, helpottaaksesi laskemista

Diskreetit logaritmit

  • Diskreetin logaritmin ongelma on löytää i, niin että g^{i}\equiv_{p}b
    • Tämä on vaikeampi ongelma kuin saman suuruisen kokonaisluvun tekijöihin jako.
  • jos g^{i}\equiv_{p}b voidaan sanoa että i on b:n indeksi mod p
    Voidaan myös kirjoittaa i=ind_{g,p}(b)
    • Indekseillä laskeminen tapahtuu samoin kuin logaritmeilla, siksi indeksejä kutsutaan diskreeteiksi logaritmeiksi
      • ind\:(x*y)=ind\:(x)+ind\:(y)
      • ind\:(x^{k})=k*ind\:(x)
  • Jotkut epäsymmetriset salausmenetelmät perustuvat diskreetteihin logaritmeihin

Primitiivijuuri (Primitive root)

  • f(x)=g^{x}mod\: p, jossa p on alkuluku ja g sen primitiivijuuri
  • g on p:n primitiivijuuri jos g,g^{2},g^{3},\ldots g^{p-1}\:(mod\: p) tuottaa kaikki arvot välillä 1\ldots(p-1)
  • jos mikään potenssi i joka on pienempi kuin \phi(p) ei tuota g^{i}\equiv_{p}1 on g p:n primitiivijuuri
  • Primitiivi juuri alkuluvlle p voidaan laskea etsimällä tekijät \phi(p) ja nostamalla potentiaalinen primitiivijuuri kaikkiin potensseihin (mod p). Tulos ei saa olla 1 paitsi arvolle p-1.
    • onko 5 primitiivi juuri mod (17) ?
Last modified: 2013/07/01 14:42