Python 2.7 で El Gamal の基本的な例を実装しようとしています。復号化には、解決できないバグがあります。
復号化の手順は次のとおりです: e^-d * c mod p
どんな助けでも感謝します。
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)
ソリューションの複製を参照するか、ここで簡単に説明します（計算効率に関するコメントも参照してください）
# 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