密码学 第8章 公钥密码.ppt

《密码学 第8章 公钥密码.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、第8章公钥密码数论简介公钥密码体制的基本概念RSA算法背包密码体制Rabin密码体制椭圆曲线密码体制数论简介回顾欧拉函数的求值公式：1970=1×1066+904,gcd(1066,904)1066=1×904+162,gcd(904,162)904=5×162+94,gcd(162,94)162=1×94+68,gcd(94,68)94=1×68+26,gcd(68,26)68=2×26+16,gcd(26,16)26=1×16+10,gcd(16,10)16=1×10+6,gcd(10,6)10=1×6+4,gcd(6,4

2、)6=1×4+2,gcd(4,2)4=2×2+0,gcd(2,0)因此gcd(1970,1066)=2。例:求gcd(1970,1066)。求乘法逆元如果gcd(a,b)=1，则b在moda下有乘法逆元（不妨设b

3、算法ExtendedEuclid(f,d)中，X3等于前一轮循环中的Y3，Y3等于前一轮循环中的X3-QY3，由于Q是Y3除X3的商，因此Y3是前一轮循环中的Y3除X3的余数，即X3modY3，可见ExtendedEuclid(f,d)中的X3、Y3与Euclid(f,d)中的X、Y作用相同，因此可正确产生gcd(f,d)。如果gcd(f,d)=1，则在最后一轮循环中Y3=0，X3=1，因此在前一轮循环中Y3=1。因为fY1+dY2=Y3成立，即fY1+dY2=1，所以dY2=1+(-Y1)×f，dY2≡1modf，即Y2≡d

4、-1modf。例：求gcd(7,5)。例：求gcd(17,283)。公钥密码体制的基本概念公钥体制加密的框图其中d是中间结果，d的终值即为所求结果。c在这里的作用是表示指数的部分结果，其终值即为指数m，c对计算结果无任何贡献，算法中完全可将之去掉。椭圆曲线的两个例子