现代密码与学第七讲：公钥密码学2 .ppt

* * * * * * * 96=5*19+1 = 96-19*5=1 =5^{-1}=-19 mod 96 = 5^[-1]=77 mod 96 * * * A=kn+t, 所以A (mod n)=t,又因为;t=k1*p+t1, 所以 A (mod n) (mod p)=t1;另一方面A=kn+t=k*p*q+k1*p+t1, so A (mod p )=t1；从而， A (mod n) (mod p)= A (mod p) * * * * * * （3）成立是因为t是使上式成立的最小的值 假设攻击者是一个解密系统的合法用户，但是他不应该偷看密文C（例如密级比较高的文档），如果他使用解密系统解密C，访问控制和审计系统会记录他的违规操作。为了隐蔽，他把C伪装一下，然后解密，对于系统来说，r足够随机的话，只能看到攻击者解密了一个随机文档，很难和C联系起来，但是攻击者却可以通过去伪得到明文 * K泄露，则由y和C2可以解出M 攻击者若已知k，可以计算y^k,然后用C2/y^k就得到明文； 若是k重复使用，则C2/C2’=M/M’,知道其中的一个明文，另一个可求。 X *97+Y*75=1 97=75+22 = 22=97-75 75=3*22+9 = 9=75-3*22=75-3*(97-75) =4*75-3*97 22=2*9+4 =4=22-2*9 =(97-75)-2*(4*75-3*97)=7*97 -9*75 9=2*4+1 =1=9-2*4=(4*75-3*97)-2*(7*97-9*75)=-17*97+22*75 * * * * * * * * Ax+b=y Y^2=x^3+cx+d * * * * * * * * 椭圆曲线密码体制ECC（elliptic curve cryptography）被IEEE公钥密码标准P1363采用. 椭圆曲线并非椭圆，一般来讲，椭圆曲线的曲线方程是以下形式的三次方程： y2+axy+by=x3+cx2+dx+e 其中a，b，c，d，e是满足某些简单条件的实数. 定义中包括一个称为无穷点的元素，记为O. 椭圆曲线密码体制 * 椭圆曲线的两个例子 椭圆曲线密码体制 * 椭圆曲线关于x轴对称, 定义椭圆曲线上的加法律（加法法则）如下： ① O为加法单位元，即对椭圆曲线上任一点P，有P+O=P. ② 设Q和R是椭圆曲线上x坐标不同的两点，Q+R的定义如下： 画一条通过Q、R的直线与椭圆曲线交于P1（这一交点是唯一的，除非所做的直线是Q点或R点的切线，由Q+R+P1=O得Q+R=-P1. 椭圆曲线密码体制 * ③ 点Q的倍数定义如下： 在Q点做椭圆曲线的一条切线，设切线与椭圆曲线交于点S，定义2Q=Q+Q=-S。类似地可定义3Q=Q+Q+Q+，…，等. ④设P1=(x,y)是椭圆曲线上的一点（如图所示），它的加法逆元定义为P2=-P1=(x, -y). 以上定义的加法具有一般数域加法运算的一般性质，如交换律、结合律等. 椭圆曲线密码体制 这是因为P1、P2的连线延长到无穷远时，得到椭圆曲线上的 另一点O，即椭圆曲线上的3点P1、P2，O共线，P1+P2+O=O， P1+P2=O，所以P2=-P1. 由O+O=O，还可得O=-O. * 密码学中通常采用有限域上的椭圆曲线，它指曲线方程定义式中，所有系数都是某一有限域GF(p)中的元素（其中p为一大素数）. 其中最为常用的是 y2≡x3+ax+b(mod p) (a,b∈GF(p), 4a3+27b2(mod p)≠0) 定义的曲线. 椭圆曲线密码体制 * 例： p=23，a=b=1，4a3+27b2(mod 23)≡8≠0 方程为y2≡x3+x+1. 椭圆曲线密码体制 其图形是连续曲线, 我们只考虑曲线在第一象限中的整数点 椭圆曲线密码体制 设Ep(a,b)表示上面方程所定义的椭圆曲线上的点集{(x,y)|0≤xp,0≤yp，且x,y均为整数}并上无穷远点O. Ep(a,b)由以下方式计算： ① 对每一x(0≤xp且x为整数），计算x3+ax+b(mod p). ② 决定①中求得的值在模p下是否有平方根，如果没有，则曲线上没有与这一x相对应的点；如果有，则求出两个平方根（y=0 时只有一个平方根）. * 本例中E23(1,1)由下表给出（表中不包含O）. 椭圆曲线密码体制 * Ep(a,b)上的加法定义 设P，Q∈Ep(a,b)，则 ① P+O=P. ② 如果P=(x,y)，那么(x, y)+(x, -y)=O，即 (x, -y)是P的加法逆元，表示为-P. 由Ep(a,b)的产生方式知，-P也是Ep(a,b)中的点，如上例，P=(13,7)∈E23(1,1)，