算法代表 背包算法 RSA(Rivest, shamir, adleman 椭圆曲线(ECC, Elliptic Curve Cryptography)
背包算法 RSA(Rivest, Shamir, Adleman) 椭圆曲线 ECC, Eilliptic Curve Croptography) 算法代表
2背包问题 背包问题描述:已知一长度为b的背包及长度分别为aa2an的n 个物品。假定这些物品的直径与背包相同,若从这些物品中选出若 千个正好装满这个背包。那么,究竟是那些物品? 即求解 ∑a:x=b 其中a和b都是正整数。 背包问题是著名的mp完备类困难问题,至今没有好的求解方法。 而对2中可能进行搜索,实际上是不可能的
2 背包问题 背包问题描述 已知一长度为b的背包及长度分别为a1,a2,…an的n 个物品 假定这些物品的直径与背包相同 若从这些物品中选出若 干个正好装满这个背包 那么 究竟是那些物品 即求解 n Σ aixi=b i=1 其中 ai和b都是正整数 背包问题是著名的np完备类困难问题 至今没有好的求解方法 而对2n中可能进行搜索 实际上是不可能的
MH背包公钥密码 背包公钥密码: 选取正整数a1a2.an作为公钥,明文位串为m=mm2mn。利 用公钥加密问题c=a1m+a2m2+…+anmn 从明文c求明文m等价于背包问题。 MH背包公钥密码: 其背包系列a1a22是由超递增系列b12b,(b>∑b)经 MH(Merkle-Hellman)变换a= wb, (mod m得到的。虽然a1a2an不 具有超递增性,但可经变换后成为超递增系列求解
MH背包公钥密码 背包公钥密码 选取正整数a1,a2,…an作为公钥 明文位串为m=m1m2…mn 利 用公钥加密问题 c= a1 m1+ a2 m2+… +an mn. 从明文c求明文m等价于背包问题 MH背包公钥密码 i-1 其背包系列a1,a2,…an是由超递增系列b1,b2,…bn , bi> Σ bj) 经 j=1 MH(Merkle-Hellman)变换ak=wbk(mod m)得到的 虽然a1,a2,…an不 具有超递增性 但可经变换后成为超递增系列求解
3 Diffie-Hellman密钥交换算法 Di6和 Hellman在其里程碑意义的文章中,虽然给出了 密码的思想,但是没有给出真正意义上的公钥密码实例,也 没能找出一个真正带陷门的单向函数。然而,他们给出单向 函数的实例,并且基于此提出 Diffie-hellman密钥交换算法。 这个算法是基于有限域中计算离散对数的困难性问题之上: 设F为有限域,g∈F是F的乘法群FF{0}=<g>。并且对 任意正整数x,计算g是容易的;但是已知g和y求x使y=g, 是计算上几乎不可能的。这一问题称为有限域F上的离散对 数问题。公钥密码学中使用最广泛的有限域为素域Fp 对 Diffie-Hellman密钥交换协议描述: Alice和Bob协商 好一个大素数p,和大的整数g,1<gp,p和g无须保密,可 为网络上的所有用户共享
3.Diffie-Hellman密钥交换算法 Diffie 和Hellman在其里程碑意义的文章中 虽然给出了 密码的思想 但是没有给出真正意义上的公钥密码实例 也 没能找出一个真正 带陷门的单向函数 然而 他 们给出单向 函数的实例 并且基于此提出Diffie-Hellman密钥 交换算法 这个算法是 基于有限域中计算离散对数的困难性问题 之 上 设 F为有限域 g F 是 F 的 乘 法 群 F *=F\{0}=<g> 并且 对 任意正整数 x 计算 g x是容易的 但是已知 g 和 y 求 x 使y= g x 是计算上几乎不可能的 这一问题称为有限域 F上的离散 对 数问题 公钥密码学中使用最广泛的有限域 为素域 F P. 对Diffie-Hellman密钥 交 换协议描述 Alice 和Bob协商 好一个大 素 数 p 和大的整数 g 1<g<p p 和 g 无 须保密 可 为网络上的所有用户共享
当 Alice和Bob要进行保密通信时,他们可以按如下步骤来做: 1) Alicei选取大的随机数x,并计算X=gY(mdP) (2Bob选取大的随机数x,并计算X′=gx'modP) 3) Alice将X传送给Bob;Bob将Ⅹ'传送给 Alice (4) Alice计算K=(X^(modP,Bob计算K′=(X)X(modP) 易见,K=K′=gx(modP) 由(4)知, Alice和Bob已获得了相同的秘密值K。双方以K作为 加解密钥以传统对称密钥算法进行保密通信。 注: Diffie-Hellman密钥交换算法拥有美国和加拿大的专利
当Alice和Bob要进行保密通信时 他们可以按如下步骤来做 (1)Alice选取大的随机数x 并计算 X=gx(mod P) (2)Bob选取大的随机数x′ 并计算 X ′ = gx ′(mod P) (3)Alice将X传送给Bob Bob将X ′传送给Alice (4)Alice计算K=(X ′)X(mod P);Bob计算K ′ X) X ′(mod P), 易见 K=K ′ =g xx ′(mod P) 由(4)知 Alice和Bob已获得了相同的秘密值K 双方以K作为 加解密钥以传统对称密钥算法进行保密通信 注 Diffie-Hellman密钥交换算法拥有美国和加拿大的专利