2

I'm trying to implement a basic example of El Gamal in python 2.7. There's some bug in the decryption which I'm unable to solve.

It's the decryption step should be: e^-d * c mod p

Any help appreciated.

from __future__ import division
from random import SystemRandom

cryptogen = SystemRandom()

# find a prime
p = 809

# random g
g = 256

# private key d from {1..,p-2}
d = 68

# public key part
k = (g ** d) % p


## k_rpiv d
## k_pub: p, g, k


# message
m = 100
# r is any real number
r = 89
# encryption
e = (g ** r) % p
# cipher
c = (k ** r * m) % p

# decryption
s = (e ** d) % p
dec = (1/s * c) % p
print(m, e, c, dec)

output:
(100, 468L, 494L, 1.7642857142857142)

see duplicate for the solution or in short here (please also see the comments wrt computational efficiency)

# decryption
# find inverse of e ** d under p
# p is prime, so any number a \in Z_p^* is coprime with p
# => Eulers Theorem: a^(p-1) \equiv 1 (mod p)
# and inverse of a is given by a^(p-2) (mod p)
dec = ((e ** d) ** (p - 2) * c) % p
Martin
  • 91
  • 1
  • 11
  • As you can see `dec` is a float and not an int. That's because `1/s` is not meant as addition, but rather as the modular inverse of `s`. – Artjom B. Apr 10 '16 at 15:35
  • 1
    Also, you might want to use the three-argument version of `pow()`, because `(g ** r) % p` is incredibly inefficient. The modular exponentiation needs to be a single combined algorithm in order to prevent generating an incredibly large number `g ** r` and only then applying the modulo operation. – Artjom B. Apr 10 '16 at 15:37
  • thanks, this helped a lot. edited the message with reference to the linked post – Martin Apr 10 '16 at 18:56

0 Answers0