El Gamal Attack

Alice memilih prima p dan basis s, dimana 2 £ s £ p-2. kemudian memilih privat a, dimana 2 £ a £ p-2, dan menghitung a = s^a (mod p). Publik Alice adalah (p,s,a).

Jika Alice ingin menandatangani M Î {0,1,…,p-1}, ia memilih kunci session acak k, dengan 1 £ k £ p-2 dan gcd(k, p-1) = 1. Alice menggunakan k untuk menghitung :

r = s^k (mod p) dan t = k^-1 (M – ra) (mod (p-1))

Bob menerima (M,r,t) dari Alice dan memeriksa apakah 1 £ r £ p-1. Jika tidak, maka tanda tangan tersebut ditolak. Jika benar, Bob menghitung v = s^M (mod p) dan w = a^r . r^t (mod p). Jika v = w (mod p), maka tanda tangan valid.

Cara kerja elgamal adalah sebagi berikut :

Alice membuat tanda tangan (M,r,t). Kemudian v = w (mod p), dimana

v = s^M (mod p) dan w = a^r . r^t (mod p)

yang memenuhi

w = a^r . r^t (mod p) = (s^a)^r (s^k)^t (mod p)

= s^ra . s^{kk’(M – ra)} (mod p)

= s ^M (mod p)

= v (mod p)

Jika penyerang Trudy mampu mengitung logaritma diskrit dengan efisien, ia dapat memperoleh nilai a (privat Alice) dari a. Untuk memalsukan tanda tangan Alice, Trudy perlu menemukan nilai r dan t sehingga s ^M = a^r . r^t.

Metode serangan terhadap elgamal

Jika Trudy dapat menebak k dari tanda tangan (M, r, t), maka ia dapat menghitung ra = M – kt (mod (p-1)) sehingga dapat juga menghitung kunci rahasia a (privat Alice).

Alice pasti menggunakan kunci session yang berbeda untuk setiap pesan yang ditandatangani, anggap Alice menggunakan k untuk M dan M’ , dimana M ¹ M’ . Lalu Trudy dapat menghitung t – t’ = k^-1 (M – M’) (mod (p-1)), dengan begitu dapat diperoleh k, karena

k = (M – M’)(t-t’)^-1 (mod (p-1))

dengan begitu maka Trudy dapat memperoleh nilai a dari k.

Trudy dapat membuat suatu pesan M dengan tanda tangan yang valid (M,r,t). Pertama Trudy memilih b dan c, dimana gcd(c,p-1) = 1. Lalu menetapkan r = s^ba^c (mod p) dan menghitung nilai t = -rc^-1 (mod (p-1)). Terakhir, M = -rbc^-1 (mod (p-1)) sehingga mendapatkan tanda tanan yang valid untuk pesan (M,r,t) karena

a^r . r^t (mod p) = (s^a)^r . (s^bac)^-rc’ (mod p)

= (s^ar) . (s^b s^ac)^-rc’ (mod p)

= (s^ar)(s^-brc’)(s^-ar) (mod p)

= s^-rbc’ (mod p)

= s^M (mod p)