我把C++代码放在GitHub上了 GitHub地址：https://github.com/xxxuxonezero/password
**
**
要生成一个超递增序列privatekey，模数modnumber,乘数mulnumber,mulnumber关于modnumber的逆元inversemul,以及背包序列publickey。 先生成一组数据，它们是超递增的，即满足第i个数字比前i-1个数字加起来的和还大。随机生成一个模数，满足它既是素数（为了能够用费马定理求出乘数的逆元），又比超递增序列所有数加起来的和还大，随机生成一个乘数，满足其与模数互质。 利用费马定理求逆元：inversemul=mulnumber^(modnumber-2)%modnumber； 关于逆元（数论）： 与倒数差不多，不过逆元不一定为1/a 若a*b%p=1,则称b是a关于p的逆元 如何生成公钥？ publickey[i]=privatekey[i]*mulnumber%modnumber
**
**
本来想把加密和解密分成两个文件的，但是文件重定向读取字符串的时候，空格没办法读，我就干脆把加密和加密放一起了。 加密： 把数据转换成二进制序列ai,secretWord=ai*publickey[i]; 于是就得到了密文 解密： 通过逆元求得cw=(secretWord * inversemul)%modnumber 用cw，配合私钥得到二进制序列，从而求得明文。 while（cw) { if(cw>=privatekey[i]） stack.push(1); cw-=privatekey[i]; else stack.push(0); }
一个例子： 超递增序列为{1，2，4，8，16，32，64，128} 模数为347，乘数为39，逆元=39^34547=89 背包序列为{39， 78， 156， 312，277 ，207 ，67 ，134} 加密字符‘abc’,得到的密文为 368，301，435 （密文=∑bit_b[i]*publibkey[i]) 通过逆元求得cw=(secretWord * inversemul)%modnumber 得到{134，70，198} 以w=134为例: 134>128 {1} 6>4 {1,0,0,0,0,1} 2>=2 {1,1,0,0,0,0,1} w=0
于是得到的明文为97
