ElGamal¶
Keutamaan¶
- Sulitnya menghitung algoritma diskrit
- Masalah logaritma diskrit:
- jika \(p\) adalah bilangan prima dan \(g\) & \(y\) adalah sembarang bilangan bulat. Carilah \(x\) sedemikian sehingga \(g^x \equiv y (\bmod p)\)
Properti¶
- bil.prima \(p\)
- bil.acak \(g\) (\(g<p\))
- bil.acak \(x\) (\(x<p\)) (kc.privat)
- \(y = g^x \bmod p\) (kc.publik)
- plaintext \(m\)
- ciphertext \(a\) & \(b\)
Algoritma pembangkitan kunci¶
- pilih sembarang bil.prima \(p\), dapat dishare diantara anggota
- pilih sembarang \(g\) & \(x\), g < p, 1 <= x <= p-2
- hitung \(y = g^x \bmod p\)
hasil :
- kc.publik: tripel(y,g,p)
- kc.privat: pasangan(x,p)
Algoritma Enkripsi¶
- susun plaintext menjadi blok-blok, [0,p-1]
- pilih bilangan acak \(k\), 1 <= k <= p-2
- setiap blok \(m\) dienkripsi dengan rumus
\[
\begin{align}
a &= g^k \bmod p \\
b &= (y^k)m \bmod p
\end{align}
\]
pasangan \(a\) & \(b\) adalah ciphertext utk blok \(m\), jadi ukuran ciphertext 2x ukuran plaintextnya
Algoritma Dekripsi¶
- gunakan kc.privat \(x\) utk menghitung
- \((a^x)^{-1} = a^{p-1-x} \bmod p\)
- hitung plaintext m dengan persamaan:
\[
\begin{align}
m &= \frac{b}{a^x} \bmod p \\
&= b((a^x)^{-1}) \bmod p
\end{align}
\]
Contoh¶
a. pembangkitan kunci (oleh alice)
misal :
\[
\begin{align}
p &= 2357\\
g &= 2\\
x &= 1751\\
\end{align}
\]
hitung:
\[
\begin{align}
y & = g^x \bmod p \\
& = 2^{1751} \bmod 2357 \\
& = 1185
\end{align}
\]
hasil:
- kc.publik: (y=1185, g=2, p=2357)
- kc.privat: (x=1751, p=2357)
b. enkripsi (oleh bob)
misal :
\(m = 2035\) (nilai \(m\) masih berada [0, 2357-1])
bob memilih bilangan acak \(k = 1520\) (nilai \(k\) masih berada [0, 2357-1])
bob menghitung :
\[
\begin{align}
a &= g^k \bmod p \\
&= 2^{1520} \bmod 2357 \\
&= 1430
\end{align}
\]
\[
\begin{align}
b &= (y^k)m \bmod p \\
&= (1185^{1520})2035 \bmod 2357 \\
&= 697
\end{align}
\]
jadi ciphertext yg dihasilkan adalah (1430, 697)
bob mengirim ke alice
c. dekripsi (oleh alice)
\[
\begin{align}
\frac{1}{a^x} &= (a^x)^{-1} \\
&= a^{p-1-x} \bmod p \\
&= 1430^{2357-1-1751} \bmod 2357\\
&= 872
\end{align}
\]
\[
\begin{align}
m &= \frac{b}{a^x} \bmod p\\
&= b((a^x)^{-1}) \bmod p\\
&= 697 \cdot 872 \bmod 2357\\
&= 2035
\end{align}
\]