ElGamal? allekirjoittajana (2-A)

Toisin kuin RSA, ElGamalin? salausalgoritmi ei ole salauksen ja purun suhteen vaihdannainen (kommutatiivinen), mutta sitä vastaava allekirjoitusalgoritmi on silti hyvin samanlainen kuin salausalgoritmi. (Sen esittelyssä? on DH-algoritmia mukailevia symboleita. Seuraavassa siirrytään kirjallisuudessa yleisemmin käytettäviin symboleihin; esim. yksityisen satunnaisen y:n tilalla on k ja y esiintyy uudessa merkityksessä.)

Lähtökohtana ovat suuri alkuluku p (diskreetti log modulo p vaikea), julkinen satunnaisluku g (primitiivinen juuri mod p) sekä yksityinen satunnaisluku x. Luvut p ja g voivat olla yhteisiä usealle käyttäjälle; p:n pituus on verrattavissa RSA-moduulin pituuteen (esim. vähintään 768 bittiä). Lasketaan y = gx (mod p) ja julkiseksi avaimeksi otetaan kolmikko (y,g,p). Yksityinen avain on x.

Viestin (tai tiivisteen) m allekirjoittaminen:

  • valitaan salassa pidettävä satunnaisluku k, syt(k,p-1)=1
  • lasketaan a = gk (mod p)
  • ratkaistaan sellainen luku b että m = xa + kb (mod p-1). Tämä voidaan tehdä laskemalla b = k-1(m-xa) (mod p-1). Tässä k:n käänteisluku mod p-1 on eo. syt-ehdon takia olemassa.
  • allekirjoitus on (a,b) (joka on kaksi kertaa viestin mittainen)

Allekirjoituksen todentaminen, kun on annettu viesti m ja sen väitetty allekirjoitus (a,b): tarkistetaan, toteutuuko ya ab(mod p) = gm(mod p).

Modifioimalla yhtälöä m = xa + kb (mod p-1) saadaan aikaan variaatioita. Seuraavassa esimerkiksi on +:n tilalla -, mutta eroa on hieman muutakin.

DSA, Digital Signature Algorithm, on DSS-standardin? käyttämä algoritmi, joka muistuttaa ElGamalin? allekirjoitusta, mutta parametrien valinta tehdään Schnorrin periaatteiden mukaan (1991, -93, -96; DSS on FIPS-186-2 vuodelta 2000, alkuperäinen 1993)

  1. Valitse 160-bittinen alkuluku q.
  2. Valitse sellainen 512-1024 -bittinen alkuluku p, että (p-1)/q menee tasan.
  3. Valitse satunnainen h ja laske g = h(p-1)/q mod p. (Jos tulos olisi = 1, valitse uudestaan)
  4. Valitse satunnainen x ja laske y = gx mod p.
  5. Julkinen avain on nelikko (p, q, g, y).

Tiivistetyn viestin m allekirjoittaminen:

  • Valitse salassa pidettävä satunnaisluku k, 0<k<q.
  • Laske a = ( gk mod p ) mod q, ts. redusoidaan ensin p:n suhteen ja sitten vielä q:n suhteen. Näitä a-lukuja on voitu laskea etukäteen.
  • Laske b = k-1(m+xa) mod q. Viestin tultua ajankohtaiseksi tarvitsee operoida vain 160-bittisillä luvuilla.
  • Allekirjoitus on (a,b). Yhteensä vain 320 bittiä.

Allekirjoituksen todentaminen: annettu viesti m ja sen väitetty allekirjoitus (a,b), jossa 0<a,b<q. Tarkistetaan, toteutuuko (gu yv mod p) mod q = a, missä u = mb-1 mod q ja v = ab-1 mod q.

-- JukkaKoskinen?

SivuTiedotLaajennettu edit

Vaativuus Perus
Valmius Valmisteilla
Tyyppi Ydin
Luokitus Uhkat
Mitä Luottamuksellisuus
Miltä Ihmisetön uhka
Missä Organisaatio
Kuka Tite-ammattilainen
Milloin Ennakolta
Miksi Hyvä tapa
Print version |  PDF  | History: r2 < r1 | 
Topic revision: r2 - 26 Sep 2010 - 11:10:19 - MarkoHelenius
 

TUTWiki

Copyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TUTWiki? Send feedback