超递增背包
文章目录
0x1 算法简述
明文：abc -> 01100001 01100010 1100011
现构造私钥，生成一个超递增序列：2, 4, 9, 16, 35, 70, 134, 270
从私钥构造公钥，计算路线如下：
设x为私钥序列元素，y为公钥序列的元素，n、m为两个正整数，m大于私钥序列元素之和，n与m互质，对应有：$ y = x \times n \bmod m $
这里取m=557，n=13，所以计算出公钥序列：26, 52, 117, 208, 455, 353, 71, 168
加密：根据明文二进制串对公钥进行求和，0代表未选中，1代表选中，于是得到密文序列：
52+117+168，52+117+71，52+117+71+168，即337, 240, 408
解密：计算n关于m的逆元k，x为密文元素，有 $y=x \times k \bmod m$，利用y值和私钥序列进行解密，y就是私钥序列对应明文二进制串为1的所有元素的和。过程如下：
先解出k=300，然后 解出包含y的序列为：283，147，417
然后从私钥倒序查找，若私钥元素小于y，则该元素位置置1，y减去该元素继续倒序查找，很容易得出明文。
|
|
0x2 C++实现
待填坑，我就是懒狗