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

 

Grupper

En mengde G er en gruppe hvis den er et sett av elementer med en binær operator ● som assosierer et element (a●b) med hvert ordnede par (a,b) av elementer i G, slik at de følgende aksiomene oppfylles:

• (A1) Lukkethet: Hvis a og b hører til G, så er (a●b) også i G
• (A2) Assosiativitet: a●(b●c) = (a●b)●c for alle a, b, c i G
• (A3)Identitetselement: Det finnes et element e i G slik at a●e = e●a = a for alle a i G
• (A4) Invers: For hver a i G, finnes det et element a’ i G slik at a●a’ = a’●a = e
• (A5)(For Abelsk gruppe) Kommutativitet: a●b = b●a for alle a, b i G

Sykliske grupper

Potenser er definert innen en gruppe som gjentatte anvendelser av gruppeoperatoren, slik a³ = a●a●a. Vi definerer a⁰ = e som identitetselementet, og a^-n =  (a’)ⁿ , hvor a’ er det inverse elementet av a  innen gruppen. Gruppen G er syklisk hvis ethvert element i G er en potens a^k (k er et heltall) av et bestemt element a ∈ G. Elementet a sies å generere gruppen G, dvs. a er en generator av G. En syklisk gruppe er alltid abelsk, og kan være endelig eller uendelig.

Ringer

En ring R , som kan defineres {R , + , * }, er en mengde elementer med to binære operatorer, kalt addisjon og multiplikasjon, slik at for alle a , b , c i R, er følgende aksiomer oppfylt:

(A1–A5)   R  er en abelsk gruppe med hensyn til addisjon; dvs. R tilfredsstiller aksiomene A1 til A5 (se over). For tilfellet en additiv gruppe, angir vi identitetselementet som 0 og inversen til a  som –a

(M1) Lukkethet under multiplikasjon:
Hvis a og b hører til R , så er ab også i R

(M2) Assosiativitet av multiplikasjon:
a (bc ) =  (ab)c  for alle a , b , c  i R

(M3) Distributive lover:
a (b + c ) = ab + ac  for alle a , b , c  i R        
(a + b )c = ac + bc  for alle a , b , c  i R

En ring er altså en mengde hvor vi kan utføre addisjon, subtraksjon [a – b = a + (-b )], og multiplikasjon uten å forlate mengden.

En ring sies å være kommutativ hvis den tilfredsstiller det følgende tilleggskriteriet:

(M4) Kommutativitet av multiplikasjon:
ab = ba for alle a, b i R

Et integritetsområde (integral domain) er en kommutativ ring som oppfyller de følgende aksiomene:

(M5) Multiplikativ identitet: 
Det finnes et element 1 i R  slik at a1 =  1a = a for alle a i R

(M6) Ingen null-divisorer: 
Hvis a , b  i R  og ab =  0, så er enten a = 0  eller b =  0

Kropper

En kropp F , angitt {F, +,* }, er en mengde elementer med to binære operatorer, kalt addisjon og multiplikasjon, slik at for alle a , b , c i F, er følgende aksiomer oppfylt:

(A1–M6) F er et integritetsområde; dvs.  F tilfredstiller aksiomene A1 til A5 og M1 til M6

(M7) Multiplikativ invers:
For hver a i F, unntatt 0, finnes det et element a^-1  i F slik at aa^-1 =  (a^-1 )a =  1

En kropp er altså en mengde hvor vi kan utføre addisjon, subtraksjon, multiplikasjon og divisjon uten å forlate mengden. Divisjon er definert med følgende regel: a /b = a (b^-1 )

Velkjente eksempler på kropper er de rasjonelle tallene, de reelle tallene, og de komplekse tallene. Bemerk at mengden av alle heltall ikke er en kropp, fordi det ikke finnes en multiplikativ invers for ethvert element.

Endelige kropper kalles også Galois Field på utenlandsk, og i kryptografi er det særlig to spesialtilfeller vi er interessert i; endelige kropper med p elementer (referert til som GF(p)) og endelige kropper med pⁿ elementer (GF(pⁿ)). Det kan vises at ordenen til en endelig kropp må være en potens av et primtall pⁿ hvor n er et positivt heltall.

Den enkleste endelige kroppen er GF(2). I dette tilfellet er addisjon ekvivalent med XOR-operatoren, og multiplikasjon er ekvivalent med den logiske OG-operatoren.

Vi har vist hvordan man kan konstruere en endelig kropp av orden p, hvor p  er et primtall. GF(p) er definert med følgende egenskaper:

1. GF(p) består av p elementer.
2. De binære operatorene + og * er definert over mengden.
   Operasjonene addisjon, subtraksjon, multiplikasjon, og divisjon kan utføres uten å forlate mengden.
   Hvert element av mengden unntatt 0 har en multiplikativ invers.

Vi har vist at elementene i GF(p) er heltallene {0, 1, . . . , p – 1} og at de aritmetiske operatorene er addisjon og multiplikasjon mod p

Polynom-aritmetikk med koeffesienter i Z_p

Hvis hvert distinkte polynom regnes som et element i mengden, er mengden en ring. Når polynom-aritmetikk utføres på polynomer over en kropp, er divisjon mulig – men det betyr ikke at eksakt divisjon er mulig. Hvis vi prøver å foreta polynom-divisjon over en koeffisientmengde som ikke er en kropp, vil vi finne at divisjon ikke alltid er definert. Selv når koeffisentmengden er en kropp vil ikke plynomdivisjon nødvendigvis være eksakt. Hvis vi aksepterer at rester er tillatt, kan vi si at polynomdivisjon er mulig hvis koeffisienten er en kropp.

Polynomdivisjon

Vi kan skrive ethvert polynom på formen:

f(x) = q(x) g(x) + r(x)

r(x) kan tolkes som å være resten; følgelig: r(x) = f(x) mod g(x). Hvis det ikke er noen rest kan vi si at g(x) deler f(x) (g(x) | f(x)). Vi kan si at g(x) er en faktor av f(x), eller at g(x) er en divisor av f(x). Et polynom f(x) over en kropp F kalles irredusibelt hvis og bare hvis f(x) ikke kan representeres som et produkt av to polynomer, begge over F, og begge med grad lavere enn det av f(x). Et irredusibelt polynom kalles også et primsk polynom.

Polynomial GCD

Polynomet c(x) sies å være største felles divisor av a(x) og b(x) hvis følgende holder:

• c(x) deler både a(x) og b(x)
• Enhver divisor av a(x) og b(x) er en divisor av c(x)

En ekvivalent definisjon er:

• gcd[a(x), b(x)] er polynomed av maksimum grad som deler både a(x) og b(x)

Euclids algoritme kan utvides til å finne største felles divisor av to polynomer hvis koeffisienter er elementer i en kropp.

Beregningsmessige betraktninger

Ettersom koeffisienter er 0 eller 1, kan ethvert slikt polynom representers som en bitstreng. Multiplikasjon er shift og XOR, jfr. multiplisering av store tall for hånd. Modulo-reduksjon gjøres ved å gjentatte ganger substituere høyeste potens med rest av irredusibelt polynom (også shift og XOR).

Bruk av en Generator

En generator g av en endelig kropp F av orden q (inneholder q elementer) er et element hvis første q-1 potenser genererer alle elementene av F større enn null. Elementene av F består av 0, g⁰, g¹, . . . ., g^q-2

Tenk deg en kropp F definert av et polynom f(x). Et element b som finnes i F kalles en rot av polynomet hvis f(b) = 0. Det kan vises at en rot g av et irredusibelt polynom er en generator av den endelige kroppen definert på det polynomet.