Ch公钥密码体制.ppt

网络与信息安全 Ch04 公钥密码体制 传统密码系统有两个特点： 加密和解密时所使用的密钥是相同的或者类似的，从加密钥可以很容易地推导出解密钥，反之亦然，因此我们常称传统密码系统为单钥密码系统或对称钥密码系统。 在一个密码系统中，我们不能假定加密算法和解密算法是必威体育官网网址的，因此密钥必须必威体育官网网址。然而发送信息的通道往往是不可靠的，所以在传统密码系统中，必须用不同于发送信息的另一个信道来发送密钥。 《密码学的新方向》 1976年，美国学者Diffie和Hellman为解决密钥的分发与管理问题发表了著名论文《密码学的新方向》New Direction in Cryptography，提出一种密钥交换协议，允许在不安全的媒体上通过通讯双方交换信息，安全地传送秘密密钥，并提出了建立“公开密钥密码体制”(Public Key)的新概念。 这篇文章中提出的公钥密码的思想：若每一个用户A有一个加密密钥ka，不同于解秘密钥ka’，加密密钥ka公开，ka’必威体育官网网址，当然要求ka的公开不至于影响ka’的安全。若B要向A必威体育官网网址送去明文m，可查A的公开密钥ka，若用ka加密得密文c，A收到c后，用只有A自己才掌握的解密密钥ka’对x进行解密得到m。 当时他们还没有实现这种体制的具体算法。 1976年，W. Diffie和N.E.Hellman发表的著名论文“密码学的新方向”，奠定了公钥密码的基础。公钥密码系统提出了一系列新颖的概念和思想，开创了密码学的新时代，其特点是： 加密钥和解密钥本质是不同的，知道其中一个，不存在一个有效地推导出另一个密钥的算法，所以公钥密码系统常又被称为双钥密码系统或非对称密码系统； 不需要分发密钥的额外信道，我们可以公开加密钥，这样无损于整个系统的必威体育官网网址性，需要必威体育官网网址的仅仅是解密钥。 公钥密码系统还带来认证性的好处。 单向函数 单向函数：计算F(m, K)＝c 容易，但由 c 计算 m 不容易。 在密码学中最常用的单向函数有两类， 一是公开密钥密码中使用的单向陷门函数、 二是消息摘要中使用的单向散列函数。 公钥密码体制(加密)概念 公钥密码（加密）+认证 数论知识简介 互素：若最大公因子gcd(a,b)=1，则整数a和b互素。 定义：若a?x mod n =1，则称a与x对于模n互为逆元。 用欧几里得Euclid算法求乘法逆元 若a和n互素，则a在模n下有逆元。 欧拉函数 欧拉Euler函数：φ(n)=与n互素的、小于n的正整数的个数，n1。例： φ(3)= φ(4) =2，φ(5)=4，φ(7) =6 数论知识简介 模运算性质：同余 模运算满足自反性、对称性、传递性； a=a mod n； 若a=b mod n，则b=a mod n； 若a=b mod n，b=c mod n，则a=c mod n 若a mod n=b mod n，则(a-b)mod n=0； [(a mod n) +(b mod n)]mod n=(a + b) mod n； - - ； * * ； 例：152 mod 12 =(3*3) mod 12=9 数论知识简介 若n是素数，则φ(n)=n-1 若n=p*q，p、q是素数，则φ(n)=(p-1)*(q-1) 例： φ(21)= φ(3*7)=2*6=12 费马Fermat定理 数论知识简介 欧拉Euler定理：a φ(n) mod n =1 推论：若a与n互素，则a与a φ(n)-1 互为逆元。 例：a=4，n=7， φ(7)=6， a φ(7)-1 =45=1024 所以，4和1024在模7下互为逆元。 验证：4x1024 mod7 =1 例如： m=3, n=10; ф(10)=4 mф(n)=34=81 ; 81 mod 10 = 1 即 81≡ 1 mod 10 34+1 = 243 ≡ 3 mod 10 高次幂剩余的运算 高次幂剩余的运算 例：gcd(98,44)=? 98=44*2+10 44=10*4+4 10=4*2+2 4=2*2+0 余数为0，则有最大公约数，且为2； 欧几里得算法求逆元 用扩展欧几里得算法计算 若a和n互素，则a在模n下有逆元，记做a-1。 定义：若a?x mod n =1，则称a与x对于模n互为逆元。 用欧几里得Euclid算法求乘法逆元，即存在两个整数