背包密码
背包密码
前情提要
背包问题
假设一个背包可以承受重量为$S$，现在有n个物品，其重量分别为$a_1$,$a_2$,…$a_n$
问题：哪些物品在最多只能装一次的情况下可以恰好使得背包被装满。
对应关系式：$x_1a_1+x_2a_2+…+x_na_n=S$
其中($x_i\in0,1$)
实际上，我们可以将明文转换成数字，并将其二进制01码从高位到低位依次作$x_i$.
公布$a_i、S$、这样就实现了,利用背包问题来简单加密明文。
此时，若要破解出$x_i$,爆破攻击的时间复杂度是$O(2^n)$，非常困难也非常安全，但没有意义。
因为加密的目的，是让指定的人（同时有公私钥的人）能快速解密，而只有公钥的人则无法快速解密。
如上所述的加密方式，没有这么一种「私钥」能让拥有者快速解出明文$x_i$
超递增序列
为什么要将这个因为直接爆破攻击时间复杂度为$O(2^n)$，非常困难，为此需要找到一个在特殊情况下可以快速求出序列$X$(即$x_i$组成的序列)，即超递增序列。
${r_1,r_2,…,r_n}$是超递增序列，指的是$r_i>=r_1+r_2+r_3+…+r_{i-1}$,就是第$i$个个数大于前面$i-1$个数之和，也就是$r_i>2r_{i-1}$
当明文和超递增序列依次相乘再求和时
$x_1r_1+x_2r_2+…+x_nr_n=S$，$x_i={0,1}$,$a_i>0$
可以通过依次比较$S$与序列中最大元素的大小关系来确定该元素性质。
eg：
$S$>$r_n$则$r_n$一定存在于等式左边，即$x_n$=1
就是因为超递增序列的纯在，即使小于$r_n$的所有都存在于等式左边，它们的和也小于$r_n$,所以$S$若要大于$r_n$，$r_n$就必须存在。
令$S=S-r_n$,然后比较$S$和$r_{n-1}$同理可得$x_{n-1}$
同理可得到序列$X$所有元素。
加密算法流程
Encryption
明文
- 明文字符串转数字
- 明文数字转二进制
- 生成明文序列$x=(x_1,x_2,x_3,…,x_n)$,$x_i\in(0,1)$
私钥
- 生成超递增序列：$r=(r_1,r_2,r_3,…,r_n)$为私钥序列
公钥
- 生成模数$B$,满足$B>\sum_{i=1}^nr_i$,就是$B>2r_n$
- 生成乘数$A$，满足$gcd(A,B)=1$
- 生成公钥序列$M=(M_1,M_2,M_3,…,M_N)$,其中$M_i\equiv Ar_i\pmod B$
密文
生成密文$S=x\cdot M=\sum_{i=1}^nx_iM_i$
已知公布序列$M$,乘数$A$,模数$B$,密文$S$
Decryption
- 计算$A$关于模$B$的逆元$A^{-1}$
- $S’\equiv A^{-1}S\equiv A^{-1}\sum_{i=1}^nx_iAr_i\equiv \sum_{i=1}^nx_ir_i \pmod B$
- 利用超递增序列$r$性质，求解二进制明文->数字->字符串
拥有公、私钥者可以计算出$S’$，然后利用超递增序列$r$轻易求解明文
没有私钥者只能计算出$S’$，缺少序列$r$无法利用超递增序列求解。
只能用$S=x\cdot M=\sum_{i=1}^nx_iM_i$,只要正常选择好乘数$A$、序列$r$，模$B$后的序列$M$各元素$(M\equiv Ar_i \pmod B)$将丧失原大小顺序性质。也就是攻击者还是要克服$O(2^n)$的时间复杂度解决问题。
攻击
参数不当
如果乘数$A$,超递增序列$r$大小选取不当，使得$Ar_i$<$B$,则$Ar_i\pmod B=Ar_i$，导致公钥序列是个很明显的超递增序列
这题的思路还是挺清晰的
背包密码求解
贴合实际：
$S=\sum_{i=0}^{n-1}x_iM_i$
其中$M$为背包的公钥，$S$为密文，记$n=len(M)$,背包密度$d=n/log_2(max(M))$
当密度$d<0.9408$时，可以用LLL，BKZ算法来完成求解
这块杰哥讲的比较细时间也比较新。
lattice1
造格
(n+1)*(n+1)
$\begin{pmatrix} 1 & 0 & \cdots & 0 & M_1 \ 0 & 1 & \cdots & 0 & M_2 \ \vdots & \vdots & \ddots & \vdots & \vdots \ 0 & 0 & \cdots & 1 & M_n \ 0 & 0 & \cdots & 0 & S \end{pmatrix}$
线性关系
$(x_1\ x_2 …\ x_n\ -1)\cdot \begin{pmatrix} 1 & 0 & \cdots & 0 & M_1 \ 0 & 1 & \cdots & 0 & M_2 \ \vdots & \vdots & \ddots & \vdots & \vdots \ 0 & 0 & \cdots & 1 & M_n \ 0 & 0 & \cdots & 0 & S \end{pmatrix}=(x_1,x_2,…,0)$
lattice2
造格
（n+1）*(n+1)
$\begin{pmatrix} 2 & 0 & \cdots & 0 & M_1 \ 0 & 2 & \cdots & 0 & M_2 \ \vdots & \vdots & \ddots & \vdots & \vdots \ 0 & 0 & \cdots & 2 & M_n \ 1 & 1 & \cdots & 1 & S \end{pmatrix}$
$(x_1\ x_2\ …\ x_n\ -1)\cdot \begin{pmatrix} 2 & 0 & \cdots & 0 & M_1 \ 0 & 2 & \cdots & 0 & M_2 \ \vdots & \vdots & \ddots & \vdots & \vdots \ 0 & 0 & \cdots & 2 & M_n \ 1 & 1 & \cdots & 1 & S \end{pmatrix}=(2x_1-1,2x_2-1,…,0)$
带模的背包
$S=\sum_{i=0}^nx_iM_i\pmod p→S=\sum_{i=0}^nx_iM_i-kp$
对应的格为
$(x_1\ x_2\ …\ x_n\ -1\ k)\begin{pmatrix} 2 & 0 & \dots & 0 & 0 & M_1 \ 0 & 2 & \dots & 0 & 0 & M_2 \ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \ 0 & 0 & \dots & 2 & 0 & M_n \ 0 & 0 & \dots & 0 & 1 & S \ 1 & 1 & \dots & 1 & 0 & p \end{pmatrix}=(2x_1-1\ 2x_2-1\ …\ 2x_n-1\ 1\ 0)$
