公钥密码学的各种技术及功能 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) ◼ 背包算法