第三讲公钥密码体制.pptVIP

公钥密码学 公钥密码学 概述 常用的数学知识 公钥密码体制的基本概念 RSA算法 几种有代表性的公钥密码体制 公钥密码学 概述 为什么需要公钥密码/非对称密码？ 对称密码体制的特点 对称密码体制存在哪些问题？ 公钥密码学 概述 优点:效率高、算法简单、计算开销小，适合加密大量数据。 缺点:密钥分配问题 若N个人相互必威体育官网网址通信，每人必须拥有（N-1）个私钥，N很大时，需要保存的私钥很多。 可信中心分发：共需要发N*(N-1)/2个私钥 N =1000时, 999 *1000/2 = 499500 双方事先约定：用户之间自己秘密会面（第一次远距离通信如何办？） 如何向第三方证明确实是由发送方传递来的消息？ 公钥密码学 概述 公开密钥技术:又称为非对称密钥技术，与对称密钥技术不同，它需要使用一对密钥来分别完成加密和解密的操作。其中一个公开发布，称为公开密钥 ( Public-Key );另外一个由用户自己秘密保存，称为私有密钥( Private-Key )。发送方用公开密钥去加密，信息接受者则用私有密钥去解密。 公钥密码学 概述 公钥密码学 概述 1976，W. Diffie, M. E. Hellman “New Directions in Cryptography”，提出非对称密码算法的思想。 是密码学发展史上的革命 在那个时代，是对密码学的一个全新理解 公钥密码学 概述 在“New Directions in Cryptography”中，Diffie和Hellman描述了几个可能用来实现公钥密码的数学变换，他们称之为单向陷门函数。 单向陷门函数是有一个陷门的一类特殊单向函数。它首先是一个单向函数，在一个方向上易于计算而反方向却难于计算。但是，如果知道那个秘密陷门，则也能很容易在另一个方向计算这个函数。即已知x，易于计算f（x），而已知f（x），却难于计算x。然而，一旦给出f（x）和一些秘密信息y，就很容易计算x。在公开密钥密码中，计算f（x）相当于加密，陷门y相当于私有密钥，而利用陷门y求f（x）中的x则相当于解密。 单向陷门函数的概念使得公钥密码系统称为可能。 公钥密码学 概述 公钥密码体制永远不能提供无条件的安全性。 这是因为能截取到密文y的敌手能够利用公开的加密规则ek依次加密每一个明文，直到找到满足y=ek(x)的x为止。所以我们研究的是公钥体制的计算安全性。 常用的数学知识 常用的数学知识 常用的数学知识 常用的数学知识 常用的数学知识 常用的数学知识 常用的数学知识 常用的数学知识 常用的数学知识 常用的数学知识 常用的数学知识 常用的数学知识 常用的数学知识 4.1.5 素性检测 爱拉托斯散（Eratosthenes）筛法 Miller-Rabin概率素性检测 引理：如果p为大于2的素数，则方程x2≡1 mod p的解只有和x≡1和x≡-1 引理的逆命题：若方程x2≡1 mod p有唯一解x不为1或-1，p不是素数 常用的数学知识 For循环结束,有d≡an-1 mod n.由费尔玛定理,若n为素数,d为1.所以d≠1，则d不是素数 n-1≡-1 mod n,所以x ≠1和x ≠n-1指x2≡1 mod n 有非±1的根,n不是素数 该算法对s个不同的a，重复调用，如果每次都返回true，则n是素数的概率大于等于1-2-s 常用的数学知识 4.1.6 欧几里得算法 欧几里得（Euclid）算法是数论中的一个基本技术，是求两个正整数的最大公因子的简化过程。而推广的Euclid算法不仅可求两个正整数的最大公因子，而且当两个正整数互素时，还可求出其中一个数关于另一个数的乘法逆元。 基于以下基本结论： 性质: 对任意非负整数a和正整数b,有 gcd(a,b)=gcd(b,a mod b) 常用的数学知识 证明： a=kb+r≡r mod b?a mod b=a-kb 设d|a,d|b, 所以d|kb. 由d|a和d|kb，得d|(a mod b) 故d是b和a mod b的公因子。 a,b以及b,a mod b公因子集合相同，故最大公因子也相同 例:gcd(55,22)=gcd(22,11)=gcd(11,0)=11 常用的数学知识 Euclid(f,d) fd 1. X?f;Y?d; 2. If Y=0 then return X=gcd(f,d) 3. R=X mod Y 4. X=Y; 5. Y=R 6. Goto 2 常用的数学知识 例4.2 求gcd(1970, 1066)。 1970=1×1066+904, gcd(1066, 904) 1066=1×904+162, gcd(904, 162) 904=5×162+94, gcd(162, 94) 1