ElGamal - Applying Multiple Public Key Operations[ElGamal Home][Home]
With the ElGamal method, we can modify the core method so that we can apply the public key multiple times, but only require a single decryption.
|
Outline
With ElGamal encryption, initially Bob creates his public key by selecting a \(g\) value and a prime number (\(p\)) and then selecting a private key (\(x\)). He then computes \(Y\) which is:
\(Y=g^x \pmod p\)
His public key is \((Y, g, p)\) and he will send this to Alice. Alice then creates a message (\(M\)) and selects a random value \(k\). She then computes \(a\) and \(b\):
\(a=g^k \pmod p\)
\(b=Y^k.M \pmod p\)
Bob then receives these and decrypts with:
\(M=\frac{b}{a^x} \pmod p\)
his works because \(\frac{b}{a^x} \pmod p = \frac{Y^k M}{ {(g^k)}^x } \pmod p = \frac{{(g^x)}^k M}{ {(g^k)}^x } \pmod p = = \frac{g^{xk} M} { g^{xk} } \pmod p = M \)
To encrypt a first time gives:
\(a_1=g^{r_1} \pmod p\)
\(b_1=y^{r_1} M \pmod p\)
Now, a second node can also encrypt with:>
\(a_2=g^{r_2}.a_1 \pmod p\)
\(b_2=y^{r_2}.b_1 \pmod p\)
Then we get:
\(a_2=g^{r_1} \times g^{r_2} = g^{r_1+r_2} \pmod p\)
and then:
\(b_2=Y^{r_1} M \times Y^{r_2} = Y^{r_1+r_2} M \pmod p\)
\(M=\frac{b_2}{{a_2}^x} = \frac{Y^{r_1+r_2} M}{({g^{(r_1+r_2)})}^x} = \frac{Y^{r_1+r_2} M}{g^{(r_1+r_2)x}} = \frac{Y^{r_1+r_2} M} {({g^{x})}^{(r_1+r_2)} } = \frac{Y^{(r_1+r_2)} M} { Y^{(r_1+r_2)} } = M \pmod p \)
and so we can keep encrypting, but were a single end decryption process can then decrypt the answer.
The method is defined here:
Coding
The coding is here:
from Crypto.Util.number import * from Crypto import Random import Crypto import libnum import sys from random import randint bits=60 M=10 if (len(sys.argv)>1): M=int(sys.argv[1]) if (len(sys.argv)>2): bits=int(sys.argv[2]) p = Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes) g=2 while (libnum.gcd(g,p-1)!=1): g= randint(0, p-1) x= randint(0, p-1) Y = pow(g,x,p) r1= randint(0, p-1) a1=pow(g,r1,p) b1=M*pow(Y,r1,p) r2= randint(0, p-1) a2=a1*pow(g,r2,p) b2=b1*pow(Y,r2,p) inva2=(libnum.invmod(pow(a2,x,p), p)) D=(b2*inva2) % p print (f"\nMessage: {M}") print(f"Private key: {x}\n") print(f"Public key: Y={Y}, g={g}, p={p}") print("\nFirst encryption with public key") print (f"r1={r1}") print (f"a1={a1}, b1={b1}") print("\nSecond encryption with public key") print (f"r2={r2}") print (f"a2={a2}, b2={b2}") print (f"\nDecryption: {D}")
A sample run for a 60-bit prime:
Message: 100 Private key: 566978574 Public key: Y=961395614, g=170525161, p=1050538903 First encryption with public key r1=677070483 a1=738208265, b1=44866996600 Second encryption with public key r2=471419309 a2=583326956299816040, b2=34613145153018062800 Decryption: 100
and for a 128-bit prime number:
Message: 100 Private key: 89887965341135116555733795073163255435 Public key: Y=55888327493993809117780774188431279713, g=147144674388860281434120081928238595609, p=203362193851142298737330591157118402967 First encryption with public key r1=196947301721004985726424338825560774490 a1=181628457164849980062788089903492054097, b1=525107515064769686327988284903683764500 Second encryption with public key r2=121234576440545925336597806576653894809 a2=354188913374653092319474631532779738976283187784047039994003302836107166718, b2=41604381415523449018454465178793659935073496504290083232037981801309255049000 Decryption: 100