ElGamal

ElGamal er et asymmetrisk kryptosystem som hovedsakelig anvendes til å lage en digital signatur på datasett som representerer et dokument på et digitalt format.

Faktaboks

Etymologi

Oppkalt etter den egyptiske matematikeren Taher ElGamal som presenterte chifferet i 1985.

Anvendelse i digitale signaturer

ElGamal er en variant av Diffie-Hellman problemet og sikkerheten er derfor basert på antagelsen om at det for alle praktiske formål er umulig å beregne logaritmer i den multiplikative gruppen Z*p.

Generering av en signatur forutsetter at det finnes et digitalt konsentrat i form av en hakkeverdi av dokumentet som skal signeres. Signaturen består i en kryptering av hakkeverdien av dokumentet med den private nøkkelen.

Hva man faktisk kan konkludere fra en beregning som viser at en signatur er gyldig avhenger av hvilke antagelser man velger å legge til grunn. Dette er diskutert i artikkelen om digitale signaturer.

Virkemåte med eksempel

De tre naturlige trinnene er først å generere et nøkkelpar, deretter å signere et dokukent, for så til sist å verifisere signaturen.

Generering av nøkler

Et nøkkelpar genereres i tre trinn:
  1. Man velger et primtall p og en generator α av den sykliske kroppen Z*p. For eksempel p=16189 og α=2.
  2. Det velges en privat nøkkel a, 1 ≤ a ≤ p-2. For eksempel 1234.
  3. Til slutt beregnes y = αa mod p. I tråd med eksemplet blir det y=21234 mod 16189 = 2507.

Den offentlige nøkkelen er de tre tallene (p=16189, α=2, y=2507) mens den private nøkkelen som nevnt er a=1234. Alle som skal verifisere den digitale signaturen må skaffe seg kjennskap til den offentlige nøkkelen fra en pålitelig åpen kilde.

Signering

For at et dokument skal kunne signeres må det først genereres et en hakkeverdi av dokumentet. Vi kaller dokumentet som skal signeres m og hakkeverdien h(m). Som eksempel setter vi h(m) = 2463.

Signering skjer i fire trinn.

  1. Det velges et tilfeldig tall k, 1 ≤ k ≤ p-2 og som er gjensidig prim med p-1. For eksempel 8599.
  2. Første del av signaturen finnes ved å beregne r=αk mod p. I tråd med eksemplet blir det 28599 mod 16189 = 10298.
  3. k-1 mod (p-1) beregnes. Dette gjøres for eksempel med den utvidede evklidske algoritme. I eksempelet er 8599-1 mod (16189-1) = 8671.
  4. Andre del av signaturen finnes ved å beregne s = k-1 (h(m) – ar) mod (p-1) hvor h(m) er hakkeverdien av meldingen som beskrevet over. I eksempelet blir det 8671 * (2463-(1234*10298)) mod 16188 = 14125.

Signaturen på m er paret (r, s) eller (10298, 14125).

Verifisering av signatur

Verifisering av en signatur (r,s) på dokumentet m skjer i fire trinn:

  1. Den offentlige nøkkelen skaffes til veie fra en åpen sikker kilde. I eksempelet er den offentlige nøkkelen som nevnt (p=16189, α=2, y=2507).
  2. Hakkeverdien av m genereres med samme metode som da signaturen ble generert. I eksempelet er h(m) = 2463.
  3. Man beregner v1=yrrs mod p. I eksemplet er v1=250710298 * 1029814125 mod 16189 = 11752.
  4. Beregn v2=αh(m) mod p. I eksempelet v2=22463 mod 16189 = 11752.

Signaturen er gyldig dersom v1=v2. I eksempelet er begge 11752.

Både det å generere en signatur og å verifisere den krever manipulasjon av svært store tall. Primtallet p=16189 i eksempelet over er kun 14 bit (fem siffer) langt. I reelle anvendelser brukes primtall på minst tusen bit (300 siffer).

Det anbefales det at p i nøkkelen er minst tusen bit mens k er minst 160 bit (2013).

Les mer i Store norske leksikon

Kommentarer

Kommentarer til artikkelen blir synlig for alle. Ikke skriv inn sensitive opplysninger, for eksempel helseopplysninger. Fagansvarlig eller redaktør svarer når de kan. Det kan ta tid før du får svar.

Du må være logget inn for å kommentere.

eller registrer deg

Fagansvarlig for Kryptografi

Harald Øverby
Professor, Handelshøyskolen BI