哪些网站做面试题,江门网站制作公司,网站改版降权,wordpress如何改字体大小7.2、子集求和问题与背包密码系统
一、数学描述
1.1、第一种描述
20 世纪 70 年代末#xff0c;默克尔和赫尔曼首次尝试将密码系统建立在一个 NP-完全问题上。他们使用了以下数学问题的一个版本#xff0c;该问题是对经典knapsack问题的概括。 子集和问题 假设你有一个正…7.2、子集求和问题与背包密码系统
一、数学描述
1.1、第一种描述
20 世纪 70 年代末默克尔和赫尔曼首次尝试将密码系统建立在一个 NP-完全问题上。他们使用了以下数学问题的一个版本该问题是对经典knapsack问题的概括。 子集和问题 假设你有一个正整数列表 ( M 1 , M 2 … M n ) 和另一个整数 s 找到列表中元素的一个子集其和是 s ( 你可以假设至少有一个这样的子集 ) 。 子集和问题 \\ 假设你有一个正整数列表(M_{1},M_{2}…M_{n})和另一个整数s\\ 找到列表中元素的一个子集其和是s(你可以假设至少有一个这样的子集)。 子集和问题假设你有一个正整数列表(M1,M2…Mn)和另一个整数s找到列表中元素的一个子集其和是s(你可以假设至少有一个这样的子集)。
1.2、另一种描述
这是描述子集和问题的另一种方式。
正整数列表 M ( M 1 , M 2 , . . . , M n ) M(M_{1},M_{2},...,M_{n}) M(M1,M2,...,Mn)是公开的。Bob选择一个秘密二进制向量 x ⃗ ( x 1 , x 2 , . . . , x n ) \vec{x}(x_{1},x_{2},...,x_{n}) x (x1,x2,...,xn)即每个 x i x_{i} xi可以是0或1。Bob计算总和 S ∑ i 1 n x i M i S\sum_{i1}^{n}x_{i}M_{i} S∑i1nxiMi并将 S 发送给Alice。
子集和问题要求Alice找到原始向量 x ⃗ \vec{x} x 或另一个二进制向量给出相同的和。请注意向量 x ⃗ \vec{x} x 告诉了Alice要将哪些 M i M_{i} Mi 包括在 S 中因为只有当 x i 1 x_{i}1 xi1 时所有的 M i M_{i} Mi 才在总和 S 中。因此指定二进制向量 x ⃗ \vec{x} x 等于指定 M 的一个子集。
很明显Alice可以通过检查所有长度为n的 2 n 2^{n} 2n个二进制向量来找到 x ⃗ \vec{x} x 。一个简单的碰撞算法允许Alice将指数减半。
二、可以减半的简单碰撞算法
命题 7.3. 设 M ( M 1 , M 2 , . . . , M n ) M(M_{1},M_{2},...,M_{n}) M(M1,M2,...,Mn)设 (M,S) 是一个子集问题。对于所有整数集 I 和 J满足以下条件: I ⊂ { i : 1 ≤ i ≤ 1 2 n } a n d J ⊂ { j : 1 2 n j ≤ n } I \subset \{i:1\le i\le \frac{1}{2}n \} \qquad and \qquad J\subset \{j:\frac{1}{2}n j\le n\} I⊂{i:1≤i≤21n}andJ⊂{j:21nj≤n} 计算并列出这些值 A I ∑ i ∈ I M i a n d B J S − ∑ j ∈ J M j A_{I}\sum_{i \in I}^{}M_{i} \qquad and \qquad B_{J}S-\sum_{j \in J}^{}M_{j} AIi∈I∑MiandBJS−j∈J∑Mj 然后这些列包含一对满足 A I 0 B J 0 A_{I_{0}}B_{J_{0}} AI0BJ0的集合 I 0 I_{0} I0和 J 0 J_{0} J0这些集合 I 0 I_{0} I0和 J 0 J_{0} J0给出了子集和问题的一个解 S ∑ i ∈ I 0 M i ∑ j ∈ J 0 M j S\sum_{i \in I_{0}}^{}M_{i}\sum_{j \in J_{0}}^{}M_{j} Si∈I0∑Mij∈J0∑Mj 每个列表中的条目数不超过 2 n / 2 2^{n/2} 2n/2因此算法的运行时间为 O ( 2 n / 2 ϵ ) O(2^{n/2\epsilon }) O(2n/2ϵ)其中 ϵ \epsilon ϵ是一个小值用于对列表进行排序和比较。类似于算法分析中的分治思想将一个整体问题分成两个子问题通过不停的分割并通过解决子问题一层层递归往上从而解决整体大问题
证据。只需注意如果 x ⃗ \vec{x} x 是二元向量 x ⃗ \vec{x} x 给出了给定子集和问题的解那么我们可以把解写成 ∑ 1 ≤ i ≤ 1 2 n x i M i S − ∑ 1 2 n ≤ i ≤ n x i M i \sum_{1 \le i \le \frac{1}{2}n}^{}x_{i}M_{i}S- \sum_{\frac{1}{2}n \le i \le n}^{}x_{i}M_{i} 1≤i≤21n∑xiMiS−21n≤i≤n∑xiMi
子集I和J的个数是 O ( 2 n / 2 ) O(2^{n/2}) O(2n/2)因为它们是n/2阶集合的子集。
三、背包问题应用于密码系统
3.1、密码思想
如果n很大那么一般来说它是很难解决一个随机实例的子集问题。然而假设Alice掌握了一些关于 M 的秘密知识或陷阱门信息使她能够保证解 x 是唯一的并且能够轻松地找到 x。这样Alice就能把子集和问题当作公钥密码系统来使用。Bob的明文是向量 x他的加密信息是总和 S ∑ x i M i S\sum x_{i}M_{i} S∑xiMi只有Alice才能通过 S 的知识轻松恢复 x。
但是Alice能用什么鬼鬼祟祟的把戏来确保她能解决这个特定的子集和问题而别人却不能?一种可能是使用一个非常容易解决的子集问题但以某种方式将这个简单的解决方案隐藏起来不让其他人知道。
3.2、密码系统前提
定义。一个递增整数序列是一个正整数列表 r ( r 1 , r 2 , . . . , r n ) r(r_{1},r_{2},...,r_{n}) r(r1,r2,...,rn)其属性是 r i 1 ≥ 2 r i 对所有 1 ≤ i ≤ n − 1 r_{i1}\ge 2r_{i} \qquad 对所有 \qquad 1\le i \le n-1 ri1≥2ri对所有1≤i≤n−1 引理7.4。设 r ( r 1 , r 2 , . . . , r n ) r(r_{1},r_{2},...,r_{n}) r(r1,r2,...,rn)是一个超递增序列。有 r k r k − 1 . . . r 2 r 1 对于所有 2 ≤ k ≤ n r_{k}r_{k-1}...r_{2}r_{1} \qquad 对于所有2 \le k \le n rkrk−1...r2r1对于所有2≤k≤n 证据。我们用k的归纳法给出了一个证明。当k 2时我们有 r 2 ≥ 2 r 1 r 1 r_{2}\ge 2r_{1}r_{1} r2≥2r1r1这就开始了归纳法。现在假设这个引理在2≤k n的情况下是成立的。然后首先使用超递增性然后是归纳假设我们发现 r k 1 ≥ 2 r k r k r k r k ( r k − 1 . . . r 2 r 1 ) r_{k1} \ge 2r_{k}r_{k}r_{k}r_{k}(r_{k-1}...r_{2}r_{1}) rk1≥2rkrkrkrk(rk−1...r2r1) 这表明引理对于k 1也是成立的。
如果 M 中的整数构成一个超递增序列则子集和问题非常容易求解。 求解方法如下
证明。假设 M 是一个超递增序列意味着 M i 1 ≥ 2 M i M_{i1} \ge 2M_{i} Mi1≥2Mi。我们已知存在一个解为了区别于算法产生的向量x我们称其为实际解y。因此我们假设y·M S我们需要证明x y。
我们用向下归纳法证明当1≤k≤n时 x k y k x_{k}y_{k} xkyk。我们的归纳假设是对于所有 k i ≤ nxi yi我们需要证明 xk yk。(注意我们允许 k n在这种情况下我们的归纳假设是空的。假设的意思是当我们执行从 i n 到 i k 1 的算法时每个阶段都有 xi yi。所以在i k执行循环之前S的值被简化为
现在考虑当我们执行循环i k时会发生什么。有两种可能:
(请注意在情况2中我们利用 引理 7.4 推导出 M k − 1 . . . M 1 M_{k-1}...M_{1} Mk−1...M1 严格小于 Mk。在这两种情况下我们都得到 xk yk这就完成了 x y 的证明。此外它还表明解是唯一的因为我们已经证明任何解都与算法的输出一致而算法的本质是对任何给定的输入 S 返回唯一的向量 x。
3.3、背包密码系统
Merkle和Hellman提出了一个基于超增长子集和问题的公钥密码系统该问题用同余来伪装。为了创建公钥/私钥对Alice从一个超递增序列 r ( r 1 , r 2 , . . . , r n ) r(r_{1},r_{2},...,r_{n}) r(r1,r2,...,rn)开始。她还选择了满足以下条件的两个大秘密整数 A 和 B B 2 r n a n d g c d ( A , B ) 1 B2r_{n} \qquad and \qquad gcd(A,B)1 B2rnandgcd(A,B)1 Alice创建了一个新的序列M它不是通过设置来超增的 M i ≡ A r i ( m o d B ) w i t h 0 ≤ M i ≤ B M_{i} \equiv Ar_{i} \pmod{B} \qquad with \qquad 0 \le M_{i} \le B Mi≡Ari(modB)with0≤Mi≤B 序列M是Alice的公钥。
为了加密一条消息Bob选择一个纯文本x它是一个二进制向量计算后将密文发送给Alice: S x ⋅ M ∑ i 1 n x i M i Sx\cdot M\sum_{i1}^{n}x_{i}M_{i} Sx⋅Mi1∑nxiMi Alice通过第一次计算解密S S ′ ≡ A − 1 S ( m o d B ) w i t h 0 ≤ S ′ B S^{} \equiv A^{-1}S \pmod B \qquad with0 \le S^{}B S′≡A−1S(modB)with0≤S′B 然后Alice利用超递增序列 r 和命题 7.5 中描述的快速算法求解 S ′ S^{} S′的子集和问题。
解密之所以有效是因为 S ′ S^{} S′等于: S ′ ≡ A − 1 S ≡ A − 1 ∑ i 1 n x i M i ≡ A − 1 ∑ i 1 n x i A r i ≡ ∑ i 1 n x i r i ( m o d B ) S^{} \equiv A^{-1}S \equiv A^{-1}\sum_{i1}^{n}x_{i}M_{i} \equiv A^{-1}\sum_{i1}^{n}x_{i}Ar_{i} \equiv \sum_{i1}^{n}x_{i}r_{i} \pmod B S′≡A−1S≡A−1i1∑nxiMi≡A−1i1∑nxiAri≡i1∑nxiri(modB) 假设 B 2 r n B 2r_{n} B2rn引理7.4告诉Alice: ∑ i 1 n x i r i ≤ ∑ i 1 n r i 2 r n B \sum_{i1}^{n}x_{i}r_{i} \le \sum_{i1}^{n}r_{i}2r_{n}B i1∑nxiri≤i1∑nri2rnB 所以通过在0到B - 1的范围内选择 S ′ S^{} S′她确保了她得到了一个完全相等的 S ′ ∑ i 1 n x i r i S^{}\sum_{i1}^{n}x_{i}r_{i} S′∑i1nxiri而不仅仅是一个全等。
下表总结了Merkle-Hellman密码系统。
基于伪装子集和问题的密码系统被称为子集和密码系统或背包密码系统。其一般思路是从秘密超增序列开始使用秘密模线性运算对其进行伪装然后将伪装序列作为公钥公布。最初的梅克尔和赫尔曼系统建议对 Ar (mod B) 的条目进行秘密排列作为额外的安全保护层。后来的版本由许多人提出涉及多个不同模量的多重乘法和还原。有关背包密码系统的精彩概览请参阅 Odlyzko 的文章。
注释 7.8. 关于背包系统必须考虑的一个重要问题是获得理想的安全等级所需的各种参数的大小。有 2 n 2^{n} 2n 个二进制向量 x ( x 1 , x 2 , . . . , x n ) x(x_{1},x_{2},...,x_{n}) x(x1,x2,...,xn)我们在命题 7.3 中已经看到有一种碰撞算法因此有可能在 O ( 2 n / 2 ) O(2^{n/2}) O(2n/2)次操作中破解背包密码系统。因此为了获得 2 k 2^{k} 2k数量级的安全性必须使 n 2k例如 2 80 2^{80} 280的安全性要求 n 160。不过尽管这提供了对抗碰撞攻击的安全性但并不排除存在其他更有效的攻击正如我们将在第 7.14.2 节中看到的这些攻击确实存在。(另见注释 7.10。
注释 7.9. 假设我们已经选定了 n 的值那么其他参数必须多大呢事实证明如果 r1 太小就很容易受到攻击因此我们必须坚持 r1 2n。序列的超递增性质意味着 r n 2 r n − 1 4 r n − 2 . . . 2 n r 1 2 2 n r_{n}2r_{n-1}4r_{n-2}...2^{n}r_{1}2^{2n} rn2rn−14rn−2...2nr122n 那么 B 2 r n 2 2 n 1 B2r_{n}2^{2n1} B2rn22n1因此我们发现公钥中的条目 Mi 和密文 S 满足以下条件: M i O ( 2 2 n ) a n d S O ( 2 2 n ) M_{i}O(2^{2n}) \qquad and \qquad SO(2^{2n}) MiO(22n)andSO(22n) 因此公钥M是一个由n个整数组成的列表每个整数大约2n位长而明文x包含n位信息密文大约2n位长。请注意消息扩展比例是2比1。
备注 7.10. 已知解决随机选择子集和问题的最佳算法是碰撞算法的各种版本如命题 7.3。不幸的是随机选择子集和问题没有陷阱门因此不能用来创建密码系统。而事实证明使用伪装的超增子集和问题可以得到其他更有效的算法。沙米尔、奥德利兹科、拉加里亚斯等人最早的此类攻击使用了各种特别的方法但在 1985 年著名的 LLL2 格还原论文[77]发表后人们逐渐发现基于密码系统的窍门有一个根本性的弱点。粗略地说如果 n 小于 300 左右那么格还原就能让攻击者在令人不安的短时间内从密文 S 中恢复出明文 x。因此一个安全的系统需要 n 300在这种情况下私钥长度大于 2 n 2 2n^{2} 2n2 180000 比特≈176 kB。这是如此之大以至于使安全的背包系统不切实际。
四、在格密码系统下的背包问题
现在我们简要介绍一下Eva如何用向量重新表述子集和问题。假设她想把 S 写成集合 M ( m 1 , . . . , m n ) M(m_{1},...,m_{n}) M(m1,...,mn)的子集和。她的第一步是形成矩阵: 相关的向量是矩阵(7.4)的行我们将其标记为:
就像在第 7.1 节末尾描述的二维示例中一样Eva关注的是 v1,…, vn1 的所有整数线性组合的集合: L a 1 v 1 a 2 v 2 . . . a n v n : a 1 , a 2 , . . . , a n 1 ∈ Z L{a_{1}v_{1}a_{2}v_{2}...a_{n}v_{n}:a_{1},a_{2},...,a_{n1} \in Z} La1v1a2v2...anvn:a1,a2,...,an1∈Z 集合L是格的另一个例子。
现在假设 x (x1,…,xn) 是给定子集和问题的解。那么格 L 包含向量: t ∑ i 1 n x i v i − v n 1 ( 2 x 1 − 1 , 2 x 2 − 1 , . . . , 2 x n − 1 , 0 ) t\sum_{i1}^{n}x_{i}v_{i}-v_{n1}(2x_{1}-1,2x_{2}-1,...,2x_{n}-1,0) ti1∑nxivi−vn1(2x1−1,2x2−1,...,2xn−1,0) 其中t的最后一个坐标是0因为 S x 1 m 1 . . . x n m n Sx_{1}m_{1}...x_{n}m_{n} Sx1m1...xnmn
现在我们来看看问题的关键所在。由于 xi 都是 0 或 1 2 x i − 1 2x_{i}-1 2xi−1的值都是±1所以向量 t 很短 ∥ t ∥ n \parallel t \parallel \sqrt{n} ∥t∥n 。另一方面我们已经看到 m i O ( 2 2 n ) m_{i}O(2^{2n}) miO(22n) S O ( 2 2 n ) SO(2^{2n}) SO(22n)所以生成 L 的向量长度都是 ∥ v i ∥ O ( 2 2 n ) \parallel v_{i} \parallel O(2^{2n}) ∥vi∥O(22n)。因此除了 t 之外L 不可能包含任何长度小于 n \sqrt{n} n 的非零向量。如果我们假设Eva知道一种能够在格中找到小的非零向量的算法那么她就能够找到 t从而恢复明文 x。
在格中寻找短向量的算法称为格还原算法。其中最有名的是我们前面提到的 LLL 算法及其变体如 LLL-BKZ。本章的其余部分将专门描述格、基于格的密码系统、LLL 算法以及 LLL 的密码应用。关于背包密码系统的更详细分析见第 7.14.2 节另见例 7.33。
五、我的一些疑问
在3.2节的证明中得到了关系 S k ∑ i 1 k y i M i 其中 k i ≤ n S_{k}\sum_{i1}^{k}y_{i}M_{i} \qquad 其中ki \le n Ski1∑kyiMi其中ki≤n 进而可以得到 S k ∑ i 1 k y i M i y k M k ∑ i 1 k − 1 y i M i 其中 k i ≤ n S_{k}\sum_{i1}^{k}y_{i}M_{i}y_{k}M_{k}\sum_{i1}^{k-1}y_{i}M_{i} \qquad 其中ki \le n Ski1∑kyiMiykMki1∑k−1yiMi其中ki≤n 所以当 y k 1 y_{k}1 yk1时由于 y i y_{i} yi不总是为1或0可以得到 S k ≥ M k S_{k} \ge M_{k} Sk≥Mk
疑问但是为什么从以上的推论在可以得到 x k 1 x_{k}1 xk1?
对于 y k 0 y_{k}0 yk0时同样中间能够理解 S k ≤ M k − 1 . . . M 1 M k S_{k} \le M_{k-1}...M_{1}M_{k} Sk≤Mk−1...M1Mk但为什么可以推断出 x k 0 x_{k}0 xk0
