密码学04－公钥密码课件

《密码学04－公钥密码课件》由会员分享，可在线阅读，更多相关《密码学04－公钥密码课件（90页珍藏版）》请在金锄头文库上搜索。

1、本科生学位课：现代密码学,第四章 公钥密码,主讲教师：董庆宽 研究方向：密码学与信息安全 Email ：,2/88,4.1 密码学中常用数学知识 4.2 公钥密码体制的基本概念 4.3 RSA算法 4.4 背包体制 4.5 Rabin体制 4.6 NTRU公钥密码系统 4.7 椭圆曲线密码体制 4.8 基于身份的密码体制,本章提要,3/88,4.1 密码学中的常用数学知识,群、环、域、素数 模运算 费尔马定理 ap-1=1 mod p ，p是素数 欧拉函数 (n)：小于n的且与n互素的正整数个数 a(n)=1 mod n 素性检验 1.爱拉托斯散筛法(Eratosthenes) 依次删去小于

2、素数的倍数 2. Miller-Rabin概率检测法 3.AKS,欧几里得算法、扩展欧几里德算法 求最大公约数和乘法的逆元 中国剩余定理 求一次同余方程组的解 离散对数，本原根 平方剩余 计算复杂性,4/88,4.2 公钥密码体制的基本概念,公钥密码体制的出现在密码学史上是一个最大的而且是惟一真正的革命。为密码学发展提供了新的理论和技术基础 公钥密码算法基本工具不再是代换和置换，而是数学函数 以非对称的形式使用两个密钥，两个密钥的使用对保密性、密钥分配、认证等都有着深刻的意义。 公钥密码体制的概念是在解决单钥密码体制中最难解决的两个问题时提出的，即密钥分配和数字签字,5/88,对称密码算法的缺

3、陷 密钥分配问题： 通信双方加密通信前要通过秘密的安全信道协商加密密钥，这种安全信道可能很难实现；对这个信道安全性的要求比正常传送消息信道的安全性要高 密钥管理问题： 在多用户网络中，任何两个用户之间都需要有共享的秘密钥，n个用户需要Cn2=n(n-1)/2个密钥，n=5000时，Cn2=12,497,500，系统开销非常大 没有签名功能： 当主体A收到主体B的电子文挡时，无法向第三方证明此电子文档确实来源于B， 传统单钥加密算法无法实现抗抵赖的需求,6/88,公钥密码的主要作用 公钥加密 用于加密任何消息，象分组密码一样使用 任何人可以用公钥加密消息，私钥的拥有者可以解密消息 数字签名 (D

4、igital Signature) 用于生成对某消息的数字签名 私钥的拥有者生成数字签名，任何人可以用公钥验证签名 签名时可将公钥加密算法逆用来实现，也可单独设计公钥签名算法 基于公钥的密钥分配(Key Distribution) 用于交换秘密信息，常用于协商对称加密算法的密钥 可采用公钥加密的算法实现密钥分配 也可使用单独设计的密钥交换算法，如DH密钥交换协议实现密钥分配 其它应用： 零知识证明，公平抛币等等，（用于各种目的的认证）,7/88,公钥密码的发展概况 1976年Diffie和Hellman在其“密码学新方向”一文中提出公钥密码： W.Diffie and M.E.Hellman,

5、 “New Directions in Cryptography”, IEEE Transaction on Information Theory, V.IT-22.No.6, Nov 1976：644-654 1978年Merkle和Hellman基于背包问题提出了首个公钥密码体制，但两年后被破译 1978年Rivest，Shamir & Adleman基于大数分解的困难性提出了RSA公钥算法，成为迄今为止最为成熟和完善的公钥密码体制 1985年出现了基于求解离散对数困难性的公钥密码算法DLP 90年代逐步出现椭圆曲线(ECC)等其他公钥算法 当前的公钥密码算法主要是基于大数分解困难性和离散

6、对数困难性来构造的，椭圆曲线上也可构造这类体制，相同密钥长度下其安全性更高 参考资料：公钥密码学等,8/88,4.2.1 公钥密码体制的原理,公钥密码算法的最大特点是采用两个相关密钥将加密和解密能力分开 一个密钥是公开的，称为公开密钥，简称公开钥，用于加密、验证签名，可以被任何人知道 另一个密钥是为用户专用，因而是保密的，只能被消息的接收者或签名者知道，称为秘密密钥，简称秘密钥，用于解密、产生签名 因此公钥密码体制也称为双钥密码体制 算法有以下重要特性： 已知密码算法和加密密钥，求解密密钥在计算上是不可行的 因此加密和签名的验证者不能解密和生成签名,9/88,公钥体制的加密过程 密钥的产生：要

7、求接收消息的端系统，产生一对用来加密和解密的密钥PKB和SKB，如图中的接收者B，其中PKB是公开钥，SKB是秘密钥。因此，公钥可以发布给其他人 公开钥的分发：端系统B将加密密钥(PKB)予以公开。另一密钥则被保密(SKB) 加密：A要想向B发送消息m，则使用B的公开钥加密m，表示为c=EPKBm其中c是密文，E是加密算法 解密：B收到密文c后，用自己的秘密钥SKB解密，即m=DSKBc，其中D是解密算法。因为只有B知道SKB，所以其他人都无法对c解密。,10/88,公钥体制的认证过程 公钥加密算法不仅能用于加、解密，还能用于对发方A发送的消息m提供认证 用户A用自己的秘密钥SKA对m加密，表

8、示为c=ESKAm 将c发往B。B用A的公开钥PKA对c解密，表示为m=DPKAc 因为从m得到c是经过A的秘密钥SKA加密，只有A才能做到。因此c可当做A对m的数字签字。 任何人只要得不到A的秘密钥SKA就不能篡改m，所以以上过程获得了对消息来源和消息完整性的认证。,11/88,认证符： 通过单向压缩函数解决长文件的签字(hash) 用户数目很多时，单纯加解密的认证方法需要很大的存储空间 因为每个文件都必须以明文形式存储以方便实际使用，同时还必须存储每个文件被加密后的密文形式即数字签字，以便在有争议时用来认证文件的来源和内容 改进的方法是减小文件的数字签字的大小，即先将文件经过一个函数压缩成

9、长度较小的比特串，得到的比特串称为认证符,12/88,认证符具有这样一个性质： 如果保持认证符的值不变而修改文件，在计算上是不可行的 签名过程中，往往用发送者的秘密钥对认证符加密，加密后的结果为原文件的数字签字。 (详见第7章),13/88,公钥体制同时提供加密和认证的过程 认证过程中，由于消息是由用户自己的秘密钥加密的，所以消息不能被他人篡改，但却能被他人窃听。这是因为任何人都能用用户的公开钥对消息解密。为了同时提供认证功能和保密性，可使用双重加、解密 先签名后加密：发方首先用自己的秘密钥SKA对消息m加密，用于提供数字签字。再用收方的公开钥PKB第2次加密，表示为c=EPKBESKAm 先

10、解密再验证：解密过程为m=DPKADSKBc 即收方先用自己的秘密钥，再用发方的公开钥对收到的密文两次解密。 如果先加密后签名是不安全的，别人可以先将签名去掉，再签上自己的签名，从而实现了篡改。,14/88,4.2.2 公钥密码算法应满足的要求,公钥密码算法应满足以下要求 收方B产生密钥对（公开钥PKB和秘密钥SKB）在计算上是容易的。由私钥及其他密码信息容易计算出公开密钥(P问题) 发方A用收方的公开钥对消息m加密以产生密文c，即c=EPKBm在计算上是容易的 收方B用自己的秘密钥对c解密，即m=DSKBc在计算上是容易的 敌手由B的公开钥PKB求秘密钥SKB在计算上是不可行的 敌手由密文c

11、和B的公开钥PKB恢复明文m在计算上是不可行的 加、解密次序可换，即EPKBDSKB(m)=DSKBEPKB (m) 其中最后一条虽然非常有用，但不是对所有的算法都作要求。在构建盲签字等算法时需要类似要求 以上要求的本质之处在于要求一个陷门单向函数。,15/88,单向函数 是两个集合X、Y之间的一个映射，使得Y中每一元素y都有惟一的一个原像xX，且由x易于计算它的像y，由y计算它的原像x是不可行的 “易于计算”是指函数值能在其输入长度的多项式时间内求出，即如果输入长n比特，则求函数值的计算时间是na 的某个倍数，其中a是一固定的常数 这时称求函数值的算法属于多项式类P，否则就是不可行的，例如，

12、函数的输入是n比特，如果求函数值所用的时间是2n的某个倍数，则认为求函数值是不可行的,16/88,易于计算和不可行两个概念与计算复杂性理论中复杂度的概念极为相似，然而又存在着本质的区别 在复杂性理论中，算法的复杂度是以算法在最坏情况或平均情况时的复杂度来度量的。这时可能对某些情况很容易求解，复杂度很低 而在此所说的两个概念是指算法在几乎所有情况下的情形,17/88,陷门单向函数 称一个函数是陷门单向函数，是指该函数是易于计算的，但求它的逆是不可行的，除非再已知某些附加信息。当附加信息给定后，求逆可在多项式时间完成 总结为： 陷门单向函数是一族可逆函数fk，满足 当k和X已知时，Y=fk(X)易

13、于计算 当k和Y已知时，X=fk-1(Y)易于计算 当Y已知但k未知时，X=fk-1(Y)计算上是不可行的 研究公钥密码算法就是要找出合适的陷门单向函数,18/88,4.2.3 对公钥密码体制的攻击,以下讨论的攻击是指对所有公钥密码体制都有效的平凡的攻击 涉及到公钥算法所基于的困难问题的安全性和参数空间大小的安全性 第一种平凡的攻击：（穷搜索攻击与密钥长度） 如果密钥太短，公钥密码体制也易受到穷搜索攻击 然而又由于公钥密码体制所使用的可逆函数的计算复杂性与密钥长度常常不是呈线性关系，而是增大得更快。所以密钥长度太大又会使得加解密运算太慢而不实用 因此公钥密码体制目前主要用于密钥管理和数字签字。

14、即处理短消息如密钥和hash值,19/88,第二种平凡的攻击 是寻找从公开钥计算秘密钥的方法 目前为止，对常用公钥算法还都未能够证明这种攻击是不可行的 第三种平凡的攻击：(可能字攻击) 仅适用于对公钥密码算法的攻击 例如对56比特的DES密钥用公钥密码算法加密后发送，敌手用算法的公开钥对所有可能的密钥加密后与截获的密文相比较 如果一样，则相应的明文即DES密钥就被找出。因此不管公钥算法的密钥多长，攻击的本质是对56比特DES密钥的穷搜索攻击 抵抗方法是在欲发送的明文消息后添加一些随机比特 不同的公钥密码算法在设计和实现中的密码协议是影响安全性的主要方面，不同算法的攻击不同。 公钥的安全性是指计

15、算上的安全性,20/88,4.3 RSA算法,1978年由R.Rivest, A.Shamir和L.Adleman提出的一种用数论构造的、也是迄今为止理论上最为成熟完善的公钥密码体制，已得到广泛的应用 R L Rivest, A Shamir, L Adleman, “On Digital Signatures and Public Key Cryptosystems“, Communications of the ACM, vol 21 no 2, pp120-126, Feb 1978 它既可用于加密、又可用于数字签字。 RSA算法的安全性是基于数论中大整数分解的困难性(但可能达不到大数分

16、解的困难强度),21/88,4.3.1 算法描述,1密钥的产生 选两个保密的大素数p和q 计算n=pq，(n)=(p-1)(q-1)，其中(n)是n的欧拉函数值 选一整数e，满足1e (n)，且gcd(n),e)=1 计算d，满足de1 mod (n)，即d是e在模(n)下的乘法逆元，因e与(n)互素，模(n)的乘法逆元一定存在 以e,n为公开钥,d,p,q为秘密钥 秘密钥也可记为d，或d, n，如果是系统负责产生密钥，则用户可能不知道p,q,22/88,2加密 加密时首先将明文比特串分组，使得每个分组对应的十进制数小于n，即分组长度小于log2n。 然后对每个明文分组m，作加密运算： cme mod n 3解密 对密文分组的解密运算为： mcd mod n,23/88,RSA算法中解密过程的正确性证明 证明： 由cme mod n，可