第十一章 公钥密码学基础 2021/2/21 计算机算法设计与分析
2021/2/21 计算机算法设计与分析 1 第十一章 公钥密码学基础
密码、加密与解密 ■密码是通信双方按约定的法则进行信息 特殊变换的一种重要保密手段 ■依照法则变明文为密文,称为加密变换; ■依照法则变密文为明文,称为解密变换 ■早期密码学仅对文字或数码进行加、解 密变换。现代密码学还可以对语音、图 像、数据等都可实施加、解密变换 2021/22 计算机算法设计与分析 2
2021/2/21 计算机算法设计与分析 2 密码、加密与解密 ◼ 密码是通信双方按约定的法则进行信息 特殊变换的一种重要保密手段。 ◼ 依照法则变明文为密文，称为加密变换； ◼ 依照法则变密文为明文，称为解密变换。 ◼ 早期密码学仅对文字或数码进行加、解 密变换。现代密码学还可以对语音、图 像、数据等都可实施加、解密变换
密码体制 ■进行明密变换的法则,称为密码体制。 ■密码体制可以分为四种基本类型: ■错乱:按照规定方式改变明文符号的位置 ■代替:用一个或多个代替表来代替明文符号; 密本:用预先编定的字母或数字密码组来代替 明文中一定的词组单词等; 加乱:用有限元素组成的一串序列作为乱数, 按规定的算法,同明文序列相结合变成密文 这四种体制,既可单独使用,也可混合使用。 2021/22 计算机算法设计与分析 3
2021/2/21 计算机算法设计与分析 3 密码体制 ◼ 进行明密变换的法则，称为密码体制。 ◼ 密码体制可以分为四种基本类型： ◼ 错乱：按照规定方式改变明文符号的位置； ◼ 代替：用一个或多个代替表来代替明文符号； ◼ 密本：用预先编定的字母或数字密码组来代替 明文中一定的词组单词等； ◼ 加乱：用有限元素组成的一串序列作为乱数， 按规定的算法，同明文序列相结合变成密文。 ◼ 这四种体制，既可单独使用，也可混合使用
密钥和公钥密码的思想 ■1976年美国斯坦福大学的De和 Hellman 提出了公钥密码的思想 ■为密码系统分别设计一个加密密钥kc和 个解密密钥kd 把kc公开,而把kd保密,同时kc的公开 不会影响kd的安全。这样 加密的过程为:c=E(m), ■解密的过程为:m=D(c) 2021/221 计算机算法设计与分析
2021/2/21 计算机算法设计与分析 4 密钥和公钥密码的思想 ◼ 1976年美国斯坦福大学的Diffle和Hellman 提出了公钥密码的思想： ◼ W.Diffie and M.E.Hellman: ◼ “New Directrions in Cryptography”, ◼ IEEE Transaction on Information Theory, V.IT-22.No.6, Nov 1976, PP.644-654 ◼ 为密码系统分别设计一个加密密钥kc和 一个解密密钥kd。 ◼ 把kc公开，而把kd保密，同时kc的公开 不会影响kd的安全。这样： ◼ 加密的过程为：c = Ekc(m)， ◼ 解密的过程为：m = Dkd(c)
秘钥与公钥 ■密码学分为秘钥密码学和公钥密码学 ■秘钥密码学在加密和解密所使用的密钥 是相同的,又称为对称密码学。 ■公钥密码学加密和解密所使用的密钥是 不相同的,且前者(签字密钥)公开而后者 (验证密钥)保密,又称为非对称密码学。 2021/221 计算机算法设计与分析 5
2021/2/21 计算机算法设计与分析 5 秘钥与公钥 ◼ 密码学分为秘钥密码学和公钥密码学。 ◼ 秘钥密码学在加密和解密所使用的密钥 是相同的，又称为对称密码学。 ◼ 公钥密码学加密和解密所使用的密钥是 不相同的，且前者(签字密钥)公开而后者 (验证密钥)保密，又称为非对称密码学
公钥密码学的各种技术及功能 1、保密通信 2、数字签名 3、秘密共享 4、认证功能 2021/221 计算机算法设计与分析 6
2021/2/21 计算机算法设计与分析 6 公钥密码学的各种技术及功能 ◼ 1、保密通信 ◼ 2、数字签名 ◼ 3、秘密共享 ◼ 4、认证功能
单向函数 ■加密的过程和解密的过程分别为: c=E(m)和m=D(c) ■显然D是E的逆函数,即D=E-1 ■设x)是En上的一个变换,En={0,1,…,n-1}, f(x)是单向的,若由x计算y=f(x)是容易的,即 P问题,而由y计算出x是困难的,即NPC问题 ■因此,公钥密码学的思想就是让加密函数是 个单向函数。加密容易解密难! 2021/22 计算机算法设计与分析
2021/2/21 计算机算法设计与分析 7 单向函数 ◼ 加密的过程和解密的过程分别为： c = E (m)和m = D(c) ◼ 显然D是E的逆函数，即D = E–1 。 ◼ 设f(x) 是En上的一个变换，En={0, 1, …, n–1}， f(x)是单向的，若由x计算y = f(x)是容易的，即 P问题，而由y计算出x是困难的，即NPC问题。 ◼ 因此，公钥密码学的思想就是让加密函数是一 个单向函数。加密容易解密难！
单向陷门函数 ■加密容易解密难。要难住别人,却不要难住自 己。怎么办? ■f(x)说是单向陷门函数,如果有陷门信息K, 当K未知时,fx)是单向的,当K已知时,由y 计算出x是容易的。 ■公约密码学的思想就是将加密函数设计为一个 单向陷门函数,而把陷门信息K作为解密密码 ■解密密码K是保密的。有了解密密码,就很容 易解密,而不知道解密密码,就很难解密 2021/221 计算机算法设计与分析
2021/2/21 计算机算法设计与分析 8 单向陷门函数 ◼ 加密容易解密难。要难住别人，却不要难住自 己。怎么办？ ◼ f(x) 说是单向陷门函数，如果有陷门信息K， 当K未知时，f(x)是单向的，当K已知时，由y 计算出x是容易的。 ◼ 公约密码学的思想就是将加密函数设计为一个 单向陷门函数，而把陷门信息K作为解密密码。 ◼ 解密密码K是保密的。有了解密密码，就很容 易解密，而不知道解密密码，就很难解密
单向陷门函数 ■例如:取两个不相等的质数p和q,令n=pq 取函数f(x)= Xk mod n,且(k,φ(n)=1,其中d(n) 是n的欧拉函数(即(n)=(p-1)*(q-1),则fx) 是一个单向函数。 如果有d使得kd≡1(modφ(n),已知d,由y计 算出x是容易的,因为y≡x(modn)。d就是它 的陷门信息。如果我们不知道φ(n),而仅知道k, 要想求出d是很困难的,这是一个NPC问题 所以fx)还是一个单向陷门函数 2021/22 计算机算法设计与分析 9
2021/2/21 计算机算法设计与分析 9 单向陷门函数 ◼ 例如：取两个不相等的质数p和q，令n = pq， 取函数f(x) = xk mod n，且(k, ф(n))=1，其中ф(n) 是n的欧拉函数(即ф(n)=(p – 1)*(q – 1))，则f(x) 是一个单向函数。 ◼ 如果有d使得kd ≡ 1(mod ф(n))，已知d，由y计 算出x是容易的，因为y d ≡ x (mod n)。d就是它 的陷门信息。如果我们不知道ф(n)，而仅知道k， 要想求出d是很困难的，这是一个NPC问题。 所以f(x)还是一个单向陷门函数
代表算法 RSA(Rivest, Shamir, Adleman) 椭圆曲线(ECC) Elliptic Curve Cryptography) ■背包算法 2021/221 计算机算法设计与分析 10
2021/2/21 计算机算法设计与分析 10 代表算法 ◼ RSA(Rivest, Shamir, Adleman) ◼ 椭圆曲线(ECC) (Eilliptic Curve Croptography) ◼ 背包算法