第讲_公钥密码体制.ppt

第4讲　公钥密码体制 主讲：谢昕 课程主要内容 §3　背包公钥密码体制 　设超递增背包序列为｛1,2,5,9,20,41,83,164｝，用MH背包算法进行加解密。 §3　背包公钥密码体制 离散数学 由LaGrange内插法 例如：(3,5)门限体制。选S=13, p=17, h(x)=2x2+10x+13 选x=1,2,3,4,5，5个秘密份额 S1=h(1)=(2+10+13) mod17=8 S2=h(2)=(8+20+13) mod17=7 S3=h(3)=(18+30+13) mod17=10 S4=h(4)=(32+40+13) mod17=0 S5=h(5)=(50+50+13) mod17=11 §6　补充----秘密共享密码体制 离散数学 从任意三个秘密份额可重构多项式h(x)。 如给定S1，S2，S3，则有 §6　补充----秘密共享密码体制 离散数学 (t，n)门限体制的特点： （1）在参与者集P中成员总数不超过p的前提下，可以增加新成员，即计算新的秘密份额不会改变已有的秘密份额。 （2）通过选用常数项不变的另一个t-1次多项式，可将某个成员的秘密份额作废。 （3）可以根据成员重要性不同分给不等个数的秘密份额，实现分级方案。 §6　补充----秘密共享密码体制 此为封面页，需列出课程编码、课程名称和课程开发室名称。 要求：每个子课程（6位编码的课程）要求做一个这样的胶片，胶片文件命名为“课程编码 课程名称.ppt”。 此页胶片仅在授课时使用，胶片＋注释中不使用。 封面页按产品分为4个，各产品使用自己的封面，把其他封面直接删除即可。 此页为了让学员和老师对课程安排有一个大致的了解。 此页列出本课程的主要培训标题，列出每章的名称即可。如果章下面的节不多，在此页可以一并列出。 此页胶片仅在授课时使用，胶片＋注释中有专门的目录和标题，不需要重复使用该页面。 离散数学 §4　 ElGamal密码体制 ElGamal公钥体制的描述： 1）选取一个足够大的素数p，使求解离散对数问题在Zp上是困难的； 2）在Zp*上选择一个本原元g； 3）随机选取整数k（0≤x≤p-2），并计算y=gk(mod p); 密钥生成的准备： 离散数学 解密：Bob计算 Dk(y1,y2)=y2(y1k)-1(mod p)= m(gk)r(grk)-1=m §4　 ElGamal密码体制 加密：Alice 取一个秘密随机数r∈ Zp-1，对明文m加密 　　 Ek(m,r)=(y1,y2) 　　其中， y1=gr(mod p)　　y2=m*yr(mod p) 公钥为：{ p,g,y } 私钥为：{ k ｝ 离散数学 §4　 ElGamal密码体制 举例：设p=2579,如果选取g=2,k=765,则 1 ） y=gk(mod p)= 2765(mod 2579)= 949 ； 2）设A要发送的消息m=1299,则A选择随机数r=853并计算 　y1=g853(mod 2579)=435；　　及 y2=1299*949853(mod 2579)=2396。 3）A发送密文y=(435,2399)给B； 4）B收到后计算m=2399*(435765)-1(mod 2579)=1299. 离散数学 椭圆曲线上的公钥密码体制的优点：速度快、安全性高、密钥短、灵活性好。 同等安全下的密钥长度： RSA:512 1024 2048 21000 ECC:106 160 211 600 §5　椭圆曲线密码体制（ECC） Elliptic Curve Cryptosystem 离散数学 (1) 无穷远元素（无穷远点，无穷远直线） 平面上任意两相异直线的位置关系有相交和平行两种。 引入无穷远点，使两种不同关系统一。 AB⊥L1， L2∥L1，直线AP由AB起绕A点依逆时针方向转动， P为AP与L1的交点。 Q=∠BAP→? /2 AP → L2 L2 L1 P∞ B A P Q §5　椭圆曲线密码体制（ECC） 离散数学 可设想L1上有一点P∞，它为L2和L1的交点，称之为无穷远点。 直线L1上的无穷远点只能有一个。 (过A点只有一条平行于L1的直线L2，两直线的交点只有一个) 结论： 1、平面上一组相互平行的直线，有公共的无穷远点。 （为与无穷远点相区别，把原来平面上的点叫做平常点） 2、平面上任何相交的两直线L1,L2有不同的无穷远点。 (原因：否则L1和L2有公共的无穷远点P∞，则过两相异点A和P ∞有相异两直线，与公理相矛盾) 3、全体无穷远点构成一条无穷