加解密的实现过程 消息m=mm2.mn是n位0,1二进制串 加密过程： c=am1+a2m2+…+anmn c是消息m的密文 解密过程： 利用超递增序列{b}求vc的解，可得消息m。 这是因为vc=vam1+va2m2+.+V anmn =bim+b2m2+...+bnmn uv=1 (mod p)ak=u bk (mod p)by=vak (mod p)(k=1,...,n) CNR@HEU http://machunguang.hrbeu.edu.cn
加解密的实现过程 消息m=m 1 m 2 … m n 是 n 位 0 ， 1 二进制串 加密过程： c=a 1 m1 + a 2 m2 + … + a n m n c 是消息 m 的密文 解密过程： 利用超递增序列{ bi } 求 vc 的解 ，可得消息 m 。 (这是因为 vc =va 1 m 1 + va 2 m 2 + … +v a n m n = b 1 m1 + b 2 m2 + … + b n mn ) uv ≡1 (mod p) a k ≡u b k (mod p) b k ≡va k (mod p) (k =1,…,n) 17 uv 1 (mod p) a k u b k (mod p) b k va k (mod p) (k 1,…,n)
举例说明（公私钥对生成) {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