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

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.

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

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 ≤ 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.

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 ≤ p-2 og som er gjensidig prim med p-1.  For eksempel 8599.
  2. Første del av signaturen finnes ved å beregne rk 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 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 v2h(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).

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

Foreslå endringer i tekst

Foreslå bilder til artikkelen

Kommentarer

Har du spørsmål om artikkelen? Skriv her, så får du svar fra fagansvarlig eller redaktør.

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