《公开密钥密码.ppt》由会员分享,可在线阅读,更多相关《公开密钥密码.ppt(85页珍藏版)》请在三一文库上搜索。
1、密 码 学,公开密钥密码,一、公开密钥密码体制的基本思想,1、传统密码的缺点: 收发双方持有相同密钥,密钥分配困难,网络环境更突出。 不能方便地实现数字签名,商业等应用不方便。,Ke Kd,一、公开密钥密码体制的基本思想,2、公开密钥密码的基本思想: 将密钥 K一分为二,一个专门加密,一个专门解密: Ke Kd 且由Ke 不能计算出 Kd ,于是可将Ke公开,使密钥分配简单。 由于Ke Kd且由Ke 不能计算出 Kd ,所以 Kd 便成为用户的指纹,于是可方便地实现数字签名。,一、公开密钥密码体制的基本思想,3、公开密钥密码的基本条件: E和 D互逆; 基本条件,保密条件 D(E(M)M Ke
2、 Kd且由Ke 不能计算出 Kd ;安全条件 E和 D都高效。 实用条件 E(D(M)M 保真条件 如果满足 可保密,如果满足 可保真,如果4个条件都满足,可同时保密保真。,二、公开密钥密码的基本工作方式,设 M为明文,C为密文,E为公开密钥密码的加密算法,D为解密算法,Ke为公开的加密钥,Kd为保密的解密钥,每个用户都分配一对密钥,而且将所有用户的公开的加密钥Ke存入共享的密钥库PKDB。,二、公开密钥密码的基本工作方式,1、确保数据秘密性:A B 发方: A首先查PKDB,查到B的公开的加密钥KeB 。 A用KeB 加密M得到密文C: C=E(M,KeB) A发C给B。 收方: B接受C。
3、 B用自己的KdB解密,得到明文M=D(C,KdB)。,M,二、公开密钥密码的基本工作方式,1、确保数据秘密性: 安全性分析: 只有B才有KdB ,因此只有B才能解密,所以确保了秘密性。 任何人都可查PKDB得到B的KeB ,所以任何人都可冒充A给B发送数据。不能确保真实性。,二、公开密钥密码的基本工作方式,2、确保数据真实性:A B 发方: A首先用自己的KdA对M解密,得到C=D(M,KdA)。 A发C给B。 收方: B接受C。 B查PKDB查到A的公开的加密钥KeA 。 B用KeA加密C,得到明文M=E(C,KeA)。,M,二、公开密钥密码的基本工作方式,2、确保数据真实性: 安全性分析
4、: 只有A才有KdA ,因此只有A才能解密产生C,所以确保了真实性。 任何人都可查PKDB得到A的KeA,所以任何人都可加密得到明文。不能确保秘密性。,二、公开密钥密码的基本工作方式,3、同时确保数据秘密性和真实性:A B 发方: A首先用自己的KdA对M解密,得到S: S=D(M,KdA) 查PKDB,查到B的公开的加密钥KeB 。 用KeB 加密S得到C: C=E(S,KeB) A发C给B。,M,二、公开密钥密码的基本工作方式,3、同时确保数据秘密性和真实性: 收方: B接受C。 B用自己的KdB解密C,得到S: S=D(C,KdB) B查PKDB查到A的公开的加密钥KeA 。 B用A的公
5、开的加密钥KeA 加密S,得到M: M=E(S,KeA),二、公开密钥密码的基本工作方式,3、同时确保数据秘密性和真实性: 安全性分析: 只有A才有KdA ,因此只有A才能解密产生S,所以确保了真实性。 只有B才有KdB ,因此只有B才能获得明文,所以确保了秘密性。,三、RSA公开密钥密码,1978年美国麻省理工学院的三名密码学者R.L.Rivest,A.Shamir和L.Adleman提出了一种基于大合数因子分解困难性的公开密钥密码,简称为RSA密码。 RSA密码被誉为是一种风格幽雅的公开密钥密码。既可用于加密,又可用于数字签名,安全、易懂。 RSA密码已成为目前应用最广泛的公开密钥密码。,
6、三、RSA公开密钥密码,1、加解密算法 随机地选择两个大素数 p和 q,而且保密; 计算n=pq,将 n公开; 计算(n)=(p-1)(q-1),对(n)保密; 随机地选取一个正整数e, 1e(n)且(e,(n))=1,将 e公开; 根据 ed1 mod (n),求出d,并对d保密; 加密运算:CM e mod n 解密运算:MC d mod n,三、RSA公开密钥密码,2、算法论证 E和D的可逆性 要证明:D(E(M)=M MCd (Me)dMed mod n 因为ed1 mod(n),这说明edt(n)+1,其中t为某整数。所以, Med Mt(n)+1 mod n 。 因此要证明 Med
7、 M mod n ,只需证明 M t(n)+1 M mod n 。,三、RSA公开密钥密码,2、算法论证 E和D的可逆性 在(M,n)1的情况下,根据数论(Euler定理), M t(n) 1 mod n , 于是有, M t(n)+1 M mod n 。,三、RSA公开密钥密码,2、算法论证 E和D的可逆性 在(M,n)1的情况下,分两种情况: 第一种情况:M1,2,3,n-1 因为n=pq,p和q为素数, M1,2,3,n-1,且(M,n)1 。 这说明M必含p或q之一为其因子,而且不能同时包含两者,否则将有Mn,与M1,2,3,n-1矛盾。,三、RSA公开密钥密码,2、算法论证 E和D的
8、可逆性 不妨设Map 。 又因q为素数,且M不包含q,故有(M,q)1, 于是有,M (q) 1 mod q 。 进一步有,M t(p-1)(q) 1 mod q。 因为q是素数,(q)(q-1),所以t(p-1)(q)t(n),所以有 M t(n) 1 mod q。,三、RSA公开密钥密码,2、算法论证 E和D的可逆性 于是,M t(n) bq+1,其中b为某整数。 两边同乘M, M t(n)+1 bqM+M 。 因为Map,故 M t(n)+1 bqap+M =abn+M 。 取模n得, M (n)+1 M mod n 。,三、RSA公开密钥密码,2、算法论证 E和D的可逆性 在(M,n)
9、1的情况下,分两种情况: 第二种情况:M0 当M0时,直接验证,可知命题成立。,三、RSA公开密钥密码,2、算法论证 加密和解密运算的可交换性 D(E(M)=(Me)d =Med =(Md)e =E(D(M) mod n 所以,RSA密码可同时确保数据的秘密性和数据的真实性。 加解密算法的有效性 RSA密码的加解密运算是模幂运算,有比较有效的算法。,三、RSA公开密钥密码,2、算法论证 在计算上由公开密钥不能求出解密钥 小合数的因子分解是容易的,然而大合数的因子分解却是十分困难的。关于大合数的因子分解的时间复杂度下限目前尚没有一般的结果,迄今为止的各种因子分解算法提示人们这一时间下限将不低于O
10、(EXP(lnNlnlnN)1/2)。根据这一结论,只要合数足够大,进行因子分解是相当困难的。,三、RSA公开密钥密码,2、算法论证 在计算上由公开密钥不能求出解密钥 假设截获密文C,从中求出明文M。他知道 MCd mod n , 因为n是公开的,要从C中求出明文M,必须先求出d,而d是保密的。但他知道, ed1 mod (n), e是公开的,要从中求出d,必须先求出(n),而(n)是保密的。,三、RSA公开密钥密码,2、算法论证 在计算上由公开密钥不能求出解密钥 但他又知道, (n)=(p-1)(q-1), 要从中求出(n),必须先求出p和q,而p和q是保密的。但他知道, n=pq, 要从n
11、求出p和q,只有对n进行因子分解。而当n足够大时,这是很困难的。,三、RSA公开密钥密码,2、算法论证 在计算上由公开密钥不能求出解密钥 只要能对n进行因子分解,便可攻破RSA密码。由此可以得出,破译RSA密码的困难性对n因子分解的困难性。目前尚不能证明两者是否能确切相等,因为不能确知除了对n进行因子分解的方法外,是否还有别的更简捷的破译方法。 目前只有Rabin密码具有: 破译Rabin密码的困难性=对n因子分解的困难性。,3、 RSA密码的实现 1)参数选择 为了确保RSA密码的安全,必须认真选择密码参数: p和q要足够大; 一般应用:p和q应 512 b 重要应用:p和q应 1024 b
12、 p和q应为强素数 文献指出,只要(p-1)、(p+1)、(q-1)、(q+1)四个数之一只有小的素因子,n就容易分解。 p和q的差要大;,三、RSA公开密钥密码,三、RSA公开密钥密码,3、 RSA密码的实现 1)参数选择 (p-1)和(q-1)的最大公因子要小。 如果( p-1)和(q-1)的最大公因子太大,则易受迭代加密攻击。 e的选择 随机且含1多就安全,但加密速度慢。于是,有的学者建议取e216+165537 d的选择 d不能太小,要足够大 不要许多用户共用一个模 n;易受共模攻击,三、RSA公开密钥密码,3、 RSA密码的实现 2)大素数的产生 概率产生 目前最常用的概率性算法是M
13、iller检验算法。Miller检验算法已经成为美国的国家标准。 确定性产生 确定性测试 确定性构造,三、RSA公开密钥密码,3、 RSA密码的实现 3)大素数的运算 快速乘方算法 反复平方乘算法: 设e的二进制表示为 eek-1 2k-1 + ek-2 2k-2 +.,+ e1 21 + e0 则 Me = (Mek-1)2 Mek-2)2Me1)2 Me0 mod n 设e为k位二进制数,w(e)为e的二进制系数中为1的个数,则最多只需要计算w(e) -1次平方和w(e)次数的模乘。从而大大简化了计算。,三、RSA公开密钥密码,3、 RSA密码的实现 3)大素数的运算 快速模乘算法 反复平
14、方乘算法解决了快速乘方取模的问题,仍未解决快速模乘的问题; Montgomery算法是一种快速模乘的好算法; 将以上两种算法结合成为实现RSA密码的有效方法。 硬件协处理器是提高运算效率的有效方法。,三、RSA公开密钥密码,3、 RSA密码的实现 3)大素数的运算 Montgomery算法的思路: 要计算 Y=AB mod n ,因为n很大,取模运算困难,采取一个小的模 R,回避大模的计算。 利用空间换时间,多用存储空间换取快速。 缺点:不能直接计算出 Y=AB mod n ,只能计算出中间值 ABR-1 mod n ,因此还需要预处理和调整运算。一次性计算Y=AB mod n并不划算。 适合
15、:RSA等密码中多次的模乘计算。,三、RSA公开密钥密码,4、对RSA公开密钥密码的主要攻击 穷举攻击:穷举所有可能的私钥 数学攻击: 因式分解攻击 参数的选取不当造成的攻击 选择密文攻击 共模攻击 小指数攻击 计时攻击,RSA公钥加密的攻击因子分解,因子分解攻击RSA的途径包括 分解n为p,q 直接确定(n), 而不确定p,q 直接确定d,而不确定(n) 可以证明,从e和n确定(n)或者d的算法至少和因子分解一样费时。因此,将因子分解的困难性作为评价RSA安全性的基准。,RSA公钥加密的攻击选择密文攻击,RSA在选择密文攻击面前很脆弱。一般攻击者是将某一信息作一下伪装( Blind),让拥有
16、私钥的实体签署。然后,经过计算就可得到它所想要的信息。,RSA公钥加密的攻击共模攻击,共模攻击:指通信系统中使用相同的n,且存在两个用户的公钥e1和e2是互质的,则可以由这两个用户对同一条明文的不同加密结果,恢复出原始明文 攻击方法: 设c1me1(mod n) c2 me2 (mod n) 攻击者知道e1, e2, n, c1, c2 因为e1和e2互质,故用Euclidean算法能找到r和s,使得te1+se2=1 (注意是相等) 则c1tc2s=m (mod n) 不能用同一个n来生成密钥,RSA公钥加密的攻击小指数攻击,Wiener在1990年指出,当dn1/4时,从e和n可以很容易求
17、出密钥d,RSA公钥加密的攻击计时攻击,思想:利用指数中某一位为0或者为1时,硬件加密速度不同,四、ELGamal公钥密码,1、基本情况: ELGamal密码是除了RSA密码之外最有代表性的公开密钥密码。 RSA密码建立在大合数分解的困难性之上。 ELGamal密码建立在离散对数的困难性之上。,所谓离散对数,就是给定正整数x,y,n,求出正整数k(如果存在的话),使yxk(mod n)。,四、ELGamal公钥密码,2、离散对数问题: 设p为素数,则模p的剩余构成有限域: Fp=0,1,2, ,p-1 Fp 的非零元构成循环群Fp* Fp* =1,2, ,p-1 =,2,3,p-1, 则称为F
18、p*的生成元或模 p 的本原元。 求的摸幂运算为: y =x mod p,1xp-1,四、ELGamal公钥密码,2、离散对数问题: 求对数 X 的运算为 x=logy,1xp-1 由于上述运算是定义在模p有限域上的,所以称为离散对数运算。 从x计算y是容易的。可是从y计算x就困难得多,利用目前最好的算法,对于小心选择的p将至少需用O(p )次以上的运算,只要p足够大,求解离散对数问题是相当困难的。,四、 ELGamal公钥密码,3、算法 准备:随机地选择一个大素数p,且要求p-1有大素数因子。再选择一个模p的本原元。将p和公开。 密钥生成 用户随机地选择一个整数d作为自己的秘密的解密钥,2d
19、p-2 。 计算y=d mod p,取y为自己的公开的加密钥。 由公开钥y 计算秘密钥d,必须求解离散对数,而这是极困难的。,四、 ELGamal公钥密码, 加密 将明文消息M(0Mp-1)加密成密文的过程如下: 随机地选取一个整数k,2kp-2。 计算: U y k mod p; C1k mod p; C2UM mod p; 取 C(C1 ,C2)作为的密文。,四、 ELGamal公钥密码, 解密 将密文(C1 ,C2)解密的过程如下: 计算VC1 d mod p; 计算MC2 V -1 mod p。,四、 ELGamal公钥密码,解密的可还原性可证明如下: C2 V-1 mod p (UM
20、)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密码是安全的。 为了安全p应为150位以上的十进制数,而且p-1应有大素因子。 为了安全加密和签名所使用的k必须是一次性的。 d和k都不能太小。,四、 ELGamal公钥密码,4、安全性 如果 k不是一次性的,时间长了就
21、可能被攻击着获得。又因y是公开密钥,攻击者自然知道。于是攻击者就可以根据Uy k mod p计算出U,进而利用Euclid算法求出U1。又因为攻击者可以获得密文C2,于是可根据式C2UM mod p通过计算U1C2得到明文M。 设用同一个k加密两个不同的明文M和M,相应的密文为(C1 ,C2)和(C1,C2)。因为C2C2 MM,如果攻击者知道M,则很容易求出M。,四、 ELGamal公钥密码,5、ELGamal密码的应用 由于ELGamal密码的安全性得到世界公认,所以得到广泛的应用。著名的美国数字签名标准DSS,采用了ELGamal密码的一种变形。 为了适应不同的应用,人们在应用中总结出1
22、8种不同的ELGamal密码的变形。,四、 ELGamal公钥密码,5、 ELGamal密码的应用 加解密速度快 由于实际应用时ELGamal密码运算的素数p比RSA要小,所以ELGamal密码的加解密速度比RSA稍快。 随机数源 由ELGamal密码的解密钥d和随机数k都应是高质量的随机数。因此,应用ELGamal密码需要一个好的随机数源,也就是说能够快速地产生高质量的随机数。 大素数的选择 为了ELGamal密码的安全,p应为150位(十进制数)以上的大素数,而且p-1应有大素因子。,五、椭圆曲线密码,1、椭圆曲线密码的一般情况 受ELGamal密码启发,在其它离散对数问题难解的群中,同样
23、可以构成ELGamal密码。于是人们开始寻找其它离散问题难解的群。 研究发现,有限域GF(p)上的椭圆曲线的解点构成交换群,而且离散对数问题是难解的。于是可在此群上建立ELGamal密码,并称为椭圆曲线密码。,五、椭圆曲线密码,1、椭圆曲线密码的一般情况 椭圆曲线密码已成为除RSA密码之外呼声最高的公钥密码之一。 它密钥短、签名短,软件实现规模小、硬件实现电路省电。 普遍认为,160位长的椭圆曲线密码的安全性相当于1024位的RSA密码,而且运算速度也较快。,五、椭圆曲线密码,1、椭圆曲线密码的一般情况 一些国际标准化组织已把椭圆曲线密码作为新的信息安全标准。如,IEEE P1363/D4,A
24、NSI F9.62,ANSI F9.63等标准,分别规范了椭圆曲线密码在Internet协议安全、电子商务、Web服务器、空间通信、移动通信、智能卡等方面的应用。,五、椭圆曲线密码,2、椭圆曲线 设p是大于3的素数,且4a3+27b2 0 mod p ,称 y2 =x3 +ax+b ,a,bGF(p) 为GF(p)上的椭圆曲线。 由椭圆曲线可得到一个同余方程: y2 =x3 +ax+b mod p 其解为一个二元组,x,yGF(p),将此二元组描画到椭圆曲线上便为一个点,于是又称其为解点。,五、椭圆曲线密码,2、椭圆曲线 为了利用解点构成交换群,需要引进一个O元素,并定义如下的加法运算: 定义
25、单位元 引进一个无穷点O(,),简记为0,作为0元素。 O(,)O(,)000 。 并定义对于所有的解点P(x ,y), P(x ,y)+OO+ P(x ,y)P(x ,y)。,五、椭圆曲线密码,2、椭圆曲线 定义逆元素 设P(x1 ,y1)和Q(x2 ,y2)是解点,如果x1=x2 且y1=-y2 ,则 P(x1 ,y1)Q(x2 ,y2)0 。 这说明任何解点R(x ,y)的逆就是 R(x ,-y)。 注意:规定无穷远点的逆就是其自己。 O(,)-O(,),五、椭圆曲线密码,2、椭圆曲线 定义加法 设P(x1,y1)Q(x2,y2),且P和Q不互逆 ,则 P(x1 ,y1)Q(x2 ,y2
26、)R(x3 ,y3) 。其中 x3 = 2 - x1 -x2 , y3 = (x1 x3)- y1 , =(y2 -y1 )/(x2 - x1 )。,五、椭圆曲线密码,2、椭圆曲线 定义加法 当P (x1 ,y1) = Q(x2,y2)时 P(x1 ,y1) Q(x2,y2) 2 P(x1 ,y1) R(x3 ,y3)。 其中 x3 = 2 - 2x1 , y3 =(x1 x3)- y1 , =(3x12 + a)/(2 y1)。,五、椭圆曲线密码,2、椭圆曲线 作集合E=全体解点,无穷点O 。 可以验证,如上定义的集合E和加法运算构成加法交换群。 复习:群的定义 G是一个非空集,定义了一种运
27、算,且运算是自封闭的; 运算满足结合律; G中有单位元; G中的元素都有逆元;,五、椭圆曲线密码,3、椭圆曲线解点加法运算的几何意义: 设P(x1 ,y1)和Q(x2 ,y2)是椭圆曲线的两个点,则连接P(x1 ,y1)和Q(x2 ,y2)的直线与椭圆曲线的另一交点关于横轴的对称点即为P(x1 ,y1)+Q(x2 ,y2)点。,五、椭圆曲线密码,3、椭圆曲线解点加法运算的几何意义:,x,y,0,P,Q,P+Q,五、椭圆曲线密码,4、举例: 取p=11,椭圆曲线y2=x3 +x+6 。由于p较小,使GF(p)也较小,故可以利用穷举的方法根据y2=x3 +x+6 mod 11求出所有解点。 复习:
28、平方剩余 设p为素数,如果存在一个正整数x,使得 x2=a mod p, 则称 a是模p的平方剩余。,五、椭圆曲线密码,x x3+x+6 mod 11 是否模11平方剩余 y 0 6 No 1 8 No 2 5 Yes 4,7 3 3 Yes 5,6 4 8 No 5 4 Yes 2,9 6 8 No 7 4 Yes 2,9 8 9 Yes 3,8 9 7 No 10 4 Yes 2,9,五、椭圆曲线密码,根据表可知全部解点集为: (2,4),(2,7),(3,5),(3,6),(5,2), (5,9),(7,2),(7,9),(8,3),(8,8), (10,2),(10,9)。 再加上无穷
29、远点O,共13的点构成一个加法交换群。 由于群的元素个数为13,而13为素数,所以此群是循环群,而且任何一个非O元素都是生成元。,五、椭圆曲线密码,由于是加法群,n个元素G相加,G+G+.+G nG 。我们取G (2,7)为生成元,具体计算加法表如下: 2G=(2,7)+(2,7)=(5,2) 因为=(322+1)(27)-1 mod 11 =23-1 mod 11=24 mod 11=8 。于是,x3 =82-22 mod 11=5 ,y3 =8(2-5)-7 mod 11=2。,五、椭圆曲线密码,G (2,7), 2G (5,2), 3G (8,3), 4G (10,2), 5G (3,6
30、), 6G (7,9), 7G (7,2), 8G (3,5), 9G (10,9),10G (8,8), 11G (5,9), 12G (2,4), 13G O( , )。,五、椭圆曲线密码,除了GF(p)上的椭圆曲线,外还有定义在GF(2m)上的椭圆曲线。这两种椭圆曲线都可以构成安全的椭圆曲线密码。 在上例中,由于p较小,使GF(p)也较小,故可以利用穷举的方法求出所有解点。但是,对于一般情况要确切计算椭圆曲线解点数N的准确值比较困难。 N满足以下不等式 P+1-2P 1/2NP+1+2P 1/2 。,五、椭圆曲线密码,5、椭圆曲线密码 ELGamal密码建立在有限域GF(p)的乘法群的离
31、散对数问题的困难性之上。而椭圆曲线密码建立在椭圆曲线群的离散对数问题的困难性之上。两者的主要区别是其离散对数问题所依赖的群不同。因此两者有许多相似之处。,五、椭圆曲线密码,5、椭圆曲线密码 椭圆曲线群上的离散对数问题 在上例中椭圆曲线上的解点所构成的交换群恰好是循环群,但是一般并不一定。于是我们希望从中找出一个循环子群E1 。可以证明当循环子群E1 的阶n是足够大的素数时,这个循环子群中的离散对数问题是困难的。,五、椭圆曲线密码,5、椭圆曲线密码 椭圆曲线群上的离散对数问题 设P和Q是椭圆曲线上的两个解点,t 为一正整数,且1tn。对于给定的P和t,计算tPQ是容易的。但若已知P和Q点,要计算
32、出t则是极困难的。这便是椭圆曲线群上的离散对数问题,简记为ECDLP(Elliptic Curve Discrete Logarithm Problem)。,五、椭圆曲线密码,5、椭圆曲线密码 椭圆曲线群上的离散对数问题 除了几类特殊的椭圆曲线外,对于一般ECDLP目前尚没有找到有效的求解方法。于是可以在这个循环子群E1中建立任何基于离散对数困难性的密码,并称这个密码为椭圆曲线密码。,五、椭圆曲线密码,椭圆曲线密码 T= p为大于3素数,p确定了有限域GF(p); 元素a,bGF(p),a和b确定了椭圆曲线; G为循环子群E1的生成元点,n为素数且为生成元G的阶,G和n确定了循环子群E1; h
33、=|E|/n,并称为余因子,h将交换群E和循环子群联系起来。,五、椭圆曲线密码,椭圆曲线密码 密钥: 用户的私钥定义为一个随机数d, d1,2,n-1。 用户的公开钥定义为Q点, Q=dG 。,五、椭圆曲线密码,椭圆曲线密码 设d为用户私钥,Q为公钥,将Q存入PKDB。 设要加密的明文数据为M,将M划分为一些较小的数据块,M=m1 ,m2 , ,mt,其中0mi n 。,五、椭圆曲线密码,椭圆曲线密码 加密过程:A把M加密发给B A查PKDB,查到B的公开密钥QB 。 A选择一个随机数k,且k1,2,n-1。 A计算点X1(x1 ,y1)=kG 。 A计算点X2(x2 ,y2)=kQB ,如果
34、分量x2=O,则转。 A计算密文 C = mi x2 mod n 。 A发送加密数据(X1,C)给B。,五、椭圆曲线密码,椭圆曲线密码 解密过程: 用户B用自己的私钥dB 求出点X2 : dBX1 = dB(kG) = k(dB G) = k QB = X2(x2 ,y2) 对C解密,得到明文mi =C x2 1 mod n 。,五、椭圆曲线密码,椭圆曲线密码 椭圆曲线密码的实现 由于椭圆曲线密码所依据的数学基础比较复杂,从而使得其具体实现也比较困难。 难点: 安全椭圆曲线的产生; 倍点运算。,六、公钥密码的理论模型,1、单向函数 设函数 y=f(x),如果满足以下两个条件,则称为单向函数:
35、如果对于给定的 x,要计算出 y很容易; 而对于给定的 y,要计算出 x很难。 2、单向函数的应用 安全HASH函数 操作系统口令,六、公钥密码的理论模型,3、利用单向函数构造密码 用正变换作加密,加密效率高; 用逆变换作解密,安全,敌手不可破译; 但是加密后不能还原。,六、公钥密码的理论模型,4、单向陷门函数 设函数 y=f(x),且 f 具有陷门,如果满足以下两个条件,则称为单向陷门函数: 如果对于给定的 x,要计算出 y很容易; 而对于给定的 y,如果不掌握陷门要计算出 x很难,而如果掌握陷门要计算出 x就很容易。,六、公钥密码的理论模型,5、单向陷门函数的应用 用正变换作加密,加密效率
36、高; 用逆变换作解密,安全; 把陷门信息作为密钥,且只分配给合法用户。确保合法用户能够方便地解密,而非法用户不能破译。,六、公钥密码的理论模型,6、单向函数的研究现状 理论上:不能证明单向函数一定存在; 实际上:只要函数的单向性足够工程应用就行; 实际上已找到的单向性足够的函数有: 合数的因子分解问题 大素数的乘积容易计算( pq n),而大合数的因子分解困难( n pq)。 有限域上的离散对数问题 有限域上大素数的幂乘容易计算( ab c),而对数计算困难( log a c b)。,公钥密码方案的实际应用,实现速度 通常用于交换对称算法的加密密钥 数字签名算法,公钥密码安全性分析,穷举攻击:可使用长密钥来对抗 由公钥来计算私钥:目前为止,虽然对特定公钥算法,均未证明该方法不可行。但公钥仍广泛使用,对称加密 VS 公钥加密,公钥加密 VS 公钥签名,公钥加密:可以提供保密性,但不能提供认证性。因为任何人都可以用A的公钥对消息进行加密,并发送给A。 公钥签名:可以提供认证性,但不能提供保密性。因为签名的验证过程中消息必须为明文的形式。 要同时实现加密和认证,可以同时使用加密和签名(一般为:先签名,后加密),1、公开密钥密码体制的基本思想是什么? 2、公开密钥密码体制的基本工作方式有哪些?并进行简单的描述。,