3-3-公钥密码学和RSA.ppt

密码学与数学 “没有公钥密码的研究就没有近代密码学。” 而在密码学的发展过程中，数学中许多分支如数论、概率统计、近世代数、信息论、椭圆曲线理论、算法复杂性理论、自动机理论、编码理论等都可以在其中找到各自的位置。 卢开澄 编著《计算机密码学——计算机网络中的数据保密与安全》 3.4 公钥密码学和RSA算法 公钥密码学思想(回顾) 经典公钥加密算法：RSA算法 数论 一、公钥密码学思想1、公钥密码学的提出——密码学的重要进步 “New Directions in Cryptography” Whitfield Diffie，Hellman 1976 提出了公钥密码算法的概念和思路 提出了鉴别和签名问题 提出了D-H密钥协商协议 2、公钥密码算法的思路 对称算法的缺陷 为事先协商密钥，需另外的安全信道或KDC 密钥管理量庞大、复杂 不能满足签名的需求 非对称算法 密钥对 K ＝（Kd，Ke），Kd即私钥 Ke即公钥 (用于加密的是公钥) 加密：E（P，Ke）＝ C 解密：D（C，Kd）＝ P 要求知道公开密钥也无法计算出秘密密钥 Ke Kd 理论上能够实现，实际计算量大，实现比较困难 3、公钥密码算法的实现 非对称体制则基于某些数学特性 利用公钥对明文进行计算 利用私钥对密文计算后可恢复得到明文 虽然公钥公开，但由它推导私钥即使理论可能，但计算困难 使用公钥密码学通信 Alice和Bob选用一个公开密钥密码系统 Bob将他的公开密钥传送给Alice Alice用Bob的公开密钥加密她的消息，然后传送给Bob Bob用他的私人密钥解密Alice的消息。 4、公钥算法建立 构造一种算法，实现明文到密文的转换过程中可以有一对关键信息。 每个用户生成密钥对(Ke、Kd) Ke或Kd是一个或几个数(大数) 符合计算特性的数，而不象对称算法的密钥 secret key是随机比特 Ke需要公开(公钥： public key ，encrypt key ) Kd得自己秘密保留(私钥：private key， decrypt key,) 6、公钥算法加密 加密（如果有人要给该用户发送消息P） 先获得该用户的公开钥Ke 加密 C = E（P，Ke）或写成 C = EKe（P） 传输 解密 D（C，Kd）＝P 除非拥有Kd，否则不能解开 算法实现 1977年，R, S, A Ron Rivest /~rivest/ Adi Shamir http://www.wisdom.weizmann.ac.il/~shamir/ Len Adleman /dept/molecular-science/ 二、数论知识 素数 模运算 定理 1、数 每一个自然数都有正因数(因数又称约数)例如： 1有一个正因数；2，3，5都有两个正因数，即1和其本身；4有三个正因数：1，2，4；可见，自然数的正因数，有多有少。除了1以外，每个自然数都至少有两个正因数。 把只有“1和其本身”两个正因数的自然数称为质数(又称素数)； 把正因数多于两个的自然数称为合数； 全体自然数分成三类：1、质数、合数 最小的质数是2，质数有很多应用性好的计算性质 2、素数性质 两个数互素，即最大公因子是1，记为gcd(*,*) = 1 求最大公因子 gcd(a,b)的算法有：欧几里德Euclid辗转相除法；stein算法 素数和谁都互素，除了他的倍数 任一个数总可以写成一系列素数的乘积，而且写法唯一 a＝p1a1 × p2a2 × p3a3 × …… × ptat 36=2×2×3×3=22×32 3、模运算 即求余运算（C语言中的运算符％） m mod n＝a 0≤an, 且有k使m＝kn＋a 同余关系：x mod n＝y mod n ＝ a 记做：x≡y mod n，称：x，y同余 则： x=k1*n+a；y=k2*n+a 所以：两数同余也说明两数相差n的倍数 计算：59≡？mod 7 模运算性质 a＋b mod n ＝ (a mod n＋b mod n) mod n a－b mod n ＝ (a mod n－b mod n) mod n a×b mod n ＝ (a mod n×b mod n) mod n 其他性质 交换律 结合律 分配律 4、定理 1）Fermat费尔马小定理： 若p是素数；a不是p的倍数，则 ap ≡ a mod p 即 2）欧拉函数Φ(n)：定义为小于n且与n互素的正整数个数。 n为素数时，Φ(n)=n-1 n＝p×q，若p、q都是素数，则： Φ(n) =Φ(p×q)=φ(p)φ(q) ＝(p-1)(q-1) 即： 素数的欧拉函数值为该数本身减1 两个素数的积的欧拉函数结果是这两个数各自的欧拉函