、 ELGamal公钥密码 (2)加密 将明丈消息M(0≤M≤p-1)加密成密文的过程如 下 ①随机地选取一个整数k,2≤k≤p-2 ②计算:U= yk mod p; C=ak mod p; C2=UM mod p; ③取C=(C1,C2)作为的密文
二、 ELGamal ELGamal公钥密码 ⑵ 加密 • 将明文消息M（0≤M≤p-1)加密成密文的过程如 加密成密文的过程如 下： ①随机地选取一个整数k，2≤k≤p-2。 ②计算： U ＝y k mod p； C1＝αk mod p； C2＝UM mod p； ③取 C＝（C1 ，C2）作为的密文
、 ELGamal公钥密码 ()解密 将密文(C1,C2)解密的过程如下 ①计算V=C14m0odp; ②计算M=C2V-1modp
二、 ELGamal ELGamal公钥密码 ⑶ 解密 • 将密文（C1 ，C2）解密的过程如下： 解密的过程如下： ①计算V＝C1d mod p； ②计算M＝C2 V -1 mod p
、 ELGamal公钥密码 解密的可还原性可证明如下: C2V-I mod p=(UM)V-I mod p =UM(C1 d)-I mod p -UM((ak)d)-I mod p -UM((a d)k)-l mod p =UM((y)k)-I mod p =UM (U)-I mod p =M mod p
二、 ELGamal ELGamal公钥密码 • 解密的可还原性可证明如下： C2 V-1 mod p ＝(UM)V-1 mod p ＝UM（C1 d）-1 mod p ＝UM（（αk）d）-1 mod p ＝UM（（αd）k）-1 mod p ＝UM（（y）k）-1 mod p ＝UM（U）-1 mod p ＝M mod p
、 ELGamal公钥密码 4)安全性 由于 ELGamal密码的安全性建立在GF(p)离散 对数的雅性之上,而目前尚无求解GF(p)离 散对数的有数算法,所以在p足够大时 ELGamal 密码是安全的。 为了安全应为150位以上的十进制数,而且p1 应有大素因子。 。为了安全加和签名所使用的k必须是一次性的 d和k都不能太小
二、 ELGamal ELGamal公钥密码 ⑷ 安全性 • 由于ELGamal ELGamal密码的安全性建立在 密码的安全性建立在GF（p）离散 对数的困难性之上 对数的困难性之上，而目前尚无求解 而目前尚无求解GF（p）离 散对数的有效算法 散对数的有效算法，所以在p足够大时ELGamal ELGamal 密码是安全的。 • 为了安全p应为150位以上的十进制数 位以上的十进制数，而且p-1 应有大素因子。 • 为了安全加密和签名所使用的k必须是一次性的 必须是一次性的。 • d和k都不能太小
、 ELGamal公钥密码 ()安全性 如果k不是一次性的,时间长了就可能被击 着获得。又因是公开密钥,政击者自然知道。 是项击者就可以根据U=ykm0dp计算出U 进而利用EC1id算法求出U1。又因为攻击者可 以获得密文C2,于是可根据式2=Mm0dp通 过计算C2得到明文M 设用同一个k加密两个不同的明文M和M,相应 的密文为(G1,C2)和(C',C2)。因为 C2=M/M,如果功击者知道M,则很容易 求出M
二、 ELGamal ELGamal公钥密码 ⑷ 安全性 • 如果 k不是一次性的，时间长了就可能被攻击 时间长了就可能被攻击 着获得。又因y是公开密钥，攻击者自然知道 攻击者自然知道。 于是攻击者就可以根据 于是攻击者就可以根据U＝y k mod p计算出U， 进而利用Euclid算法求出U－1。又因为攻击者可 又因为攻击者可 以获得密文C2，于是可根据式C2＝UM mod p通 过计算U－1 C2得到明文M。 • 设用同一个k加密两个不同的明文 加密两个不同的明文M和M’，相应 的密文为（ C1 ， C2）和（ C1’， C2’）。因为 C2∕C2’＝ M∕M’，如果攻击者知道 如果攻击者知道M，则很容易 求出M’