Python：ElGamal

brief introduction

Baidu Encyclopedia portal
Based on Duffy - Asymmetric encryption algorithm of Herman key exchange
EIGamal The public key cryptosystem is based on the intractability of the problem between discrete logarithms in a finite field . It is based on the principle that ： It is difficult to solve the discrete logarithm , The inverse operation can be effectively calculated by square multiplication . In the corresponding group G in , An exponential function is a one-way function .

Algorithm

explain

• import explain ： In the import, I added my own Prime correlation function , You can add or overwrite by yourself
• Input ： Decimal integer （ In the code is mb, namely B In plain text ）, Replace... With the comment section
• Output ： Two parts ： The encryption part outputs the encrypted decimal ciphertext pair , Decryption part outputs decrypted decimal plaintext （ lazy , Disassemble the code by yourself
• other ： Automatically generate safe prime numbers p（ Speed depends on luck , Twoorthree seconds faster , There is no upper limit ）、 Primordial root g、 random number a、g Of a Power , prime number p、 Primordial root g、g Of a Power as public key , random number a For private key , Both public and private key pairs are receivers A Of
• technological process ： The system generates relevant parameters ,B In plain text mb Encrypted into （c1,c2） And send it to A;A Use the private key after receiving a Decrypt output plaintext ma（, Finally, compare the correctness of the plaintext , This is definitely not the normal step ）.

Code

Operation error reporting 、 Please see the instructions for timeout

import prime
import random
import math
p=prime.safe_length(150)
g=prime.safe_root(p)
a=random.randint(2, p)
ga=pow(g,a,p)
print(' Public key ：('+str(p)+',\n'+str(g)+',\n'+str(ga)+')')
#print(' Private key ：'+str(a))
mb=prime.length(149)#int(input('m:'))
print('\nB\'s input:\n'+str(mb))
k=random.randint(1, p-1)
while math.gcd(p-1, k)!=1:
k=random.randint(1, p-1)
c1=pow(g, k,p)
c2=((mb%p)*pow(ga,k,p))%p
print('\ncyphertext：('+str(c1)+',\n'+str(c2)+')')
v=pow(c1,a,p)
ma=(c2*prime.modinv(v,p))%p
print('\nA\'s output:\n'+str(ma))
print(ma==mb)# Plaintext comparison