第5章[第3部分]公钥密码及Rabin密码及椭圆曲线密码.ppt

椭圆曲线密码体制概述 椭圆曲线举例 加法运算 加法运算 密码学中用的椭圆曲线 椭圆曲线上点的产生 加法定义 加法定义 加法举例－不同点相加 以E23(1,1)为例，设P=(3,10)，Q=(9,7)，计算P+Q 加法举例－同点相加 求2P， P=(3,10) DH体制 DH体制 DH体制举例 ECC举例 网络工程学院? 第5章 公钥密码体制（3） 　　对RSA密码体制，n被分解成功，该体制便被破译，即破译RSA的难度不超过大整数的分解，但不能证明破译RSA和分解大整数是等价的。 　　Rabin密码体制已被证明对该体制的破译与分解大整数是等价的，它有两个特点： 1、它不是以一一对应的单向陷门函数为基础，对同一密文，可能有两个以上对应的明文 2、破译该体制与分解大整数是等价的 概述 密码体制（1） 1、密钥产生 随机选择两个大素数p, q，满足p≡ q≡ 3 mod 4,即这两个素数形式为4k+3；计算n=p*q。 以n作为公钥，p, q作为密钥 2、加密 c ≡ m2modn m是明文分组，c是对应的密文分组 密码体制（2） 3、解密 　　解密即为求解x2 ≡ c ≡ m2modn，由中国剩余定理知该方程等价于解方程组 　　　　　　x2 ≡cmodp x2 ≡cmodq 由于p≡ q≡ 3 mod 4，下面将看到，方程组的解可容易求出，其中每个方程都有两个解，即 x≡m mod p, x≡-mmod p x≡m mod q, x≡-m mod q 经过组合可得到4个同余方程组： x≡-m mod q x≡-m mod q x≡m mod q x≡m mod q x≡-mmod p x≡m mod p x≡-mmod p x≡m mod p 由中国剩余定理可解出每一方程组的解，共有4个，即每一密文对应的明文不惟一。为了有效确定明文，可在m中加入某些双方商定的信息，如日期、发送者的ID等。 解密 p≡q≡3 mod 4，下面将看到，方程组的解可容易求出： 一个结论：对x2 ≡cmodp，c是modp的平方剩余的充要条件是c(p-1)/2≡1modp 简单推导：x2 ≡cmodp　＝＞x(p-1) ≡c(p-1)/2modp 因为c是modp的平方剩余，故c不能被p 整除，所以x也不能被p 整除 由Fermat定理可知x(p-1) ≡1modp, 故c(p-1)/2≡1modp 解方程组 p≡q≡3 mod 4，可得：p+1=4k，即(p+1)/4是一个整数。 则(c(p+1)/4)2≡ (c(p+1)/2≡ c(p-1)/2*c≡cmodp 故(c(p+1)/4和p-(c(p+1)/4是方程x2 ≡cmodp的两个根。同理，故(c(q+1)/4和q-(c(q+1)/4是方程x2 ≡cmodq的两个根 解方程组 例：p=11, q=23, 则n=253 公钥为253，私钥为(11,23) 取m’=6=110,重复后两位，则加密的明文为m=11010,m为十进制的26。 1．加密：c=m2modn=262mod 253=676mod 253=170,加密的密文即为170。 2．解密：设x2=170 mod 253 密码体制例 由中国剩余定理，其等价于 x2=170 mod 11=5 mod 11 x2=170 mod 23=9 mod 23 ?由公式知： x= c(p+1)/4=53mod 11 =±4 x= c(p+1)/4=56mod 23=±3 ?其等价于 x≡4 mod 11 x≡-4mod 11 x≡4mod11 x≡-4mod 11 x≡3 mod 23 x≡3 mod 23 x≡-3 mod 23 x≡-3 mod 23 ?其解依次为26, 95,158, 227 密码体制例 例：实体A选择素数p=277,q=331，计算n=pq=91687，A的公钥是n=91687，A的私钥是(p=277, q=331)。 假设在加密之前需要复制原信息的后6位，为加密10位信息，B复制的后6位得到16位信息m=1001111001111001，用十进制数字表示为m=40569。B计算得c=m2 mod n=405692mod 91687=62111并发送给A。 为解密c，A计算c mod n的四个平方根： m1=69654 m2=22033 m3=40569 m4=51118 二进制表示为： m1=10001000000010110 m2=101011000010001 m3=1001111001111001 　 m4=1100011110101110 密码体制例 为保证RSA算法的安全性