举例说明（公私钥对生成) {1,3,7,13,26,65,119,267是超递增序列，是私有密钥。 1+3+7+13+26+65+119+267=501 取p=523和u=467,可得V=28。 通过uv=13076=1mod523可验证。然后，计算： a1=467*1≡467m0d523 a2=467*3≡355m0d523 a3=467*7≡131m0d523 a4=467*13≡318m0d523 a5=467*26≡113m0d523 a6=467*65≡21m0d523 a7=467*119=135m0d523ag=467*267=215m0d523 (467,355,131,318,113,21,135,215}是背包序列，是公开密钥。 18 CNR@HEU http://machunguang.hrbeu.edu.cn
举例说明（公私钥对生成） {,,, , , , , } 1,3,7,13,26,65,119,267 }是超递增序列，是私有密钥 。 1+3+7+13+26+65+119+267=501 取p=523 和u=467，可得v=28 。 通过 uv=13076 ≡1 mod 523 可验证。然后，计算： a1=467*1 ≡467 mod 523 a 2=467*3 ≡355 mod 523 a 3 =467*7 ≡131 mod 523 a 131 mod 523 a 4 =467*13 ≡318 mod 523 318 mod 523 a 5=467*26 ≡113 mod 523 a 6=467*65 ≡21 mod 523 a 7=467*119 ≡135 mod 523 a 8=467*267 ≡215 mod 523 {467 355 131 318 113 21 135 215}是背包序列 是公开密钥 18 {467,355,131,318,113,21,135,215}是背包序列 ，是公开密钥
举例说明（加解密） 设明文m=10101100 加密过程： a+ag+a5+a6=467+131+113+21=732(密文) 解密解密： 接受方收到密文732后，乘以v=28,再取模523，即得： 732*28=20496=99m0d532 解超递增序列背包问题： m1+3m2+7m3+13m4+26m5+65m6+119m7+267mg=99 m1=3=5=m6=1,m247g=0 即得明文10101100 19 CNR@HEU http://machunguang.hrbeu.edu.cn
举例说明(加解密) 设明文m=10101100 加密过程： a1+a3+a5+a6=467+131+113+21 467+131+113+21 732 = （密文） 解密解密： 接受方收到密文732后，乘以v=28，再取模523，即得： 732*28=20496=99 mod 532 解超递增序列背包问题： m1+3m2+7m3+13m4+26m5+65m6+119m7+267m8=99 m1=m3=m5=m6=1, m2=m4=m7=m8=0 19 即得明文10101100
安全性分析 。背包问题是NP问题，至今还没有有效的求解方法。若对2n种 所有可能进行穷举搜索，当很大时在实际上是不可能的。 以n=100为例：2100=1.27*1030 以每秒搜索107种方案的超高速电子计算机进行穷举，一 年只能完成3.2*1014次，所以共要： 1.27*1030/3.2*1014=4*1015年 。事实上，墨科-赫尔曼变换将超递增序列的特性隐蔽性不够，已 被证明大多数基于背包问题的公钥密码是不安全的，现很少在 使用，但它的思想是值得借鉴的。关于对背包问题的攻击，感 兴趣的同学请参见相关文献。 20 CNR@HEU http://machunguang.hrbeu.edu.cn
安全性分析 背包问题是NP问题 至今还没有有效的求解方法 若对 2 背包问题是NP问题，至今还没有有效的求解方法。若对 2n 种 所有可能进行穷举搜索， 所有可能进行穷举搜索， 当n很大时在实际上是不可能的。 以 n=100 为例： 100 30 2100=1.27*1030 以每秒搜索107种方案的超高速电子计算机进行穷举，一 年只能完成3.2*1014次，所以共要： 1.27*1030 / 3.2*1014 = 4*1015年 事实上，墨科-赫尔曼变换将超递增序列的特性隐蔽性不够，已 被证明大多数基于背包问题的公钥密码是 被证明大多数基于背包问题的公钥密码是不安全的，现很少在 使用，但它的思想是值得借鉴的。关于对背包问题的攻击，感 兴趣的同学请参见相关文献 20
背包密码小结 o 背包密码算法是第一个公开密钥算法，但大多数不适合数字 签名。 。背包算法的安全性源于背包问题，它是一个P问题（随着背 包中物品数目的增多而计算量呈指数增长)。尽管这个算法 是不安全的，但由于它证明了如何将NP问题用于公钥密码体 制，是值得研究的。 自从方案被破译后，又有许多其他的背包变型被提出，但 这些背包中的大多数都被用同样的密码分析方法攻破，少数 则采用更高级的分析方法，虽然有极个别的背包变型还没有 破解，但人们已不再信赖它们了。 21 CNR@HEU http://machunguang.hrbeu.edu.cn
背包密码小结 背包密码算法是 背包密码算法是第 个公开密钥算法 一个公开密钥算法，但大多数不适合 但大多数不适合数字 签名。 背包算法的安全性源于 背包算法的安全性源于背包问题，它是 个一 NP问题(随着背 包中物品数目的增多而计算量呈指数增长)。尽管这个算法 。尽管这个算法 是不安全的，但由于它证明了 但由于它证明了如何将NP问题用于公钥密码体 问题用于公钥密码体 制，是值得研究的。 自从MH方案被破译后，又有许多其他的背包变型被提出，但 方案被破译后，又有许多其他的背包变型被提出，但 这些背包中的大多数都被用同样的密码分析方法攻破，少数 则采用更高级的分析方法，虽然有极个别的背包变型还没有 破解，但人们已不再信赖它们了。 21
RSA公钥密码的简介 在Diffiez和Iellman提出公钥密码体制的设想后两年， 先后有Merkle和Iellman.提出了MH背包公钥密码，Rivest、 Shamir、Adleman联合提出的简称为RSA公钥密码系统。RSA 虽稍后于H背包公钥系统，但它到目前为止应用最广的一种 公钥密码。RSA的理论基础是数论的欧拉定理，它的安全性 (陷门是将大整数分成素因子乘机) 依赖于大整数的素因子分解的困难性。 CNR@HEU http://machunguang.hrbeu.edu.cn
RSA公钥密码的简介 公钥密码的简介 在Diffie和Hellman Hellman提出公钥密码体制的设想后两年， 提出公钥密码体制的设想后两年， 先后有Merkle和Hellman提出了MH背包公钥密码， 背包公钥密码，Rivest、 Shamir、Adleman Adleman联合提出的简称为 联合提出的简称为RSA公钥密码系统。 公钥密码系统。RSA 虽稍后于MH背包公钥系统，但它到目前为止应用最广的 种 但它到目前为止应用最广的 一 种 公钥密码 。RSA的理论基础是数论的 的理论基础是数论的欧拉定理，它的安全性 依赖于大整数的素因子分解的困难性。 22 （陷门是将大整数分成素因子乘机）