EIGamal 密码体制描述

1.简单介绍

1.EIGamal密码是除了RSA密码之外最有代表性的公开密钥密码

2.EIGamal建立在离散对数的困难问题之上

2.密钥产生

（1）选择一个素数p，以及小于p的两个随机数 g 和 x 

（2）计算

（3）以（y,g,p)作为公开钥，x作为私钥

3.加密运算

（1）对于明文消息M，随机选择一个与 p-1 互素的整数 k计算  p， p

（2）密文就为C=(C1,C2)

4.解密计算

 

5.正确性证明

 

6.EIGamal 密码体制安全性

EIGamal建立在离散对数的困难问题之上，举个例子：p是一个大素数

求c=2^q mod p很简单，可以用快速幂很快解出来，但是已知c的话，要你求在当前计算力的情况下，时间复杂度一般在O()，当 q 比较大的时候，要求出q就特别麻烦。