宣传一波 更好的阅读体验 👉 个人blog
公钥密码体制中,除了 RSA、EIGamal 和圆曲线加密体制以外,还有很多其他公钥密码算法,但由于各种原因它们的应用都不如上述算法广泛,本篇将对一些其他重要公钥密码算法,MH 背包公钥加密体制的原理作简要的介绍。
看到背包很熟悉?有关系,但不多如有。(温馨提示:如果忘记背包请随时复习我们最经典的背包九讲😋)
1.MH 背包公钥加密体制介绍
背包公钥加密体制是由 Ralph Merkle 和 Martin Hellman 于 1978 年首提出的,它是第一个公钥加密算法,其安全性基于背包难题。尽管这个算法后来发现是不安全的,但是由于它实现了如何将 NP 完全问题用于设计公钥密码算法,所以其设计思想很值得借鉴和研究。
背包问题描述起来很简单:给定一堆物品,每个重量不同,能否将这些物品中的几件放入一个背包中使之等于一个给定的重量?数学描述为:给定一个正整数集$A=(a_1,a_2,\ldots ,a_n)$(称为背包向量),已知S
是A
的某子集合A'
中元素的和。求A'
或者求一个n
元的0、1
向量$X=(x_1,x_2,\ldots,x_n)$使得:
$$ \sum_{i=1}^{n}{x_ia_i} = S $$
Merkle 和 Hellman 提出的背包公加密体制(简称 MH 背包密码)是利用超递增序列的背包问题来实现的(简称超递增背包问题)。所谓超递增序列,是指这个序列的每一项都大于它之前所有项之和,即对于任意j>1
,有:
$$ a_j > \sum_{i = 1}^{j - 1}{a_i} $$
例如,(1,3,6,13,27,52)
就是一个超递增序列。超递增背包问题的解很容易找到,用 S
与A
的最后一项$a_n$,比较,如果 $S< a_n$,则它不在背包中令$x_n=0$;如果 $S>a_n$,则它在背包中,令$x_n = 1$,并令$ S=S-a_n$。进而考查序列下一个最大的数$ a_n-1$,重复到最后一个数比较结束如果总重量减为零,那么有一个解,否则无解。而一般背包问题是困难的,它目前没有多项式时间的算法。求解若使用穷搜法,则最坏情况下需遍历$ 2^n$个子集合, n
较大时,非常困难。MH 背包公钥加密体制利用了超递增序列作为私钥,公钥则是有相同解的一般背包向量。
2.密钥生成算法
令 A={$a_1,a_2,\ldots,a_n$}是一个超递增整数序列,取素数 $p、b,p> \sum_{i = 1}^{n}{a_i},1 \leq b \leq p-1$,计算$t_i\equiv ba_i(mod p),1 \leq i \leq n$。则公钥为$t=(t_1,t_2,\ldots,t_n)$和p
,私钥为A
和b
。
C++ 代码
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 100010;
int len; // 设置超递增序列长度(随便)
int A[N];//私钥
int b;//私钥
int p;//公钥
int t[N];//公钥
int sum;//A[N]前len项和
int primes[N];
int cnt;
bool st[N];
void get_primes(){ //线性筛法得质数
int n = N;
for(int i=2;i<=n;i++){
if(!st[i]) primes[cnt++]=i;
for(int j=0;primes[j]<=n/i;j++){
st[primes[j]*i]=true;
if(i%primes[j]==0) break;
}
}
}
void init_A() // 初始化超递增序列,随便写的,满足调价即可
{
A[0] = 1;
sum += A[0];
for(int i = 1; i < len; i ++ )
{
A[i] = sum + 1;
sum += A[i];
}
}
int main()
{
cout << "请设置超递增序列长度" << endl;
cin >> len;
init_A();
get_primes();
for(int i = 0; i < cnt; i ++ )
{
if(primes[i] > sum)
{
p = primes[i];
b = primes[i - 1];
break;
}
}
cout << "公钥集合" << endl;
cout << "t:" ;
for(int i = 0; i < len; i ++ ) cout << (b * A[i]) % p << " ";
cout << endl;
cout << "p:" << p << endl;
cout << "私钥集合" << endl;
cout << "A:";
for(int i = 0; i < len; i ++ ) cout << A[i] << " ";
cout << endl << "b:" << b << endl;
return 0;
}
结果
请设置超递增序列长度
8
公钥集合
t:251 245 233 209 161 65 130 3
p:257
私钥集合
A:1 2 4 8 16 32 64 128
b:251
3.加解密算法(肥肠简单)
加密算法:设明文块二进制表示为 $m=m_1m_2\ldots m_n$,则使用加密算法$c \equiv \sum_{i = 1}^{n}{t_im_i}(mod p)$,计算出密文 c,发送给接收方。
解密算法:通过公式$S\equiv b^{-1}c(mod p)$计算得到 S,对超递增序列$A=(a_1,a_2,\ldots,a_n)$及整数 S 利用超递增背包问题求解算法恢复出明文$m_1m_2\ldots m_n$。
求逆元!!!!
这里只介绍快速幂求逆元,如若需要知道快速幂,点击直达
前提
费马小定理:若 p 是质数,整数 b 不是 p 的倍数,则 b^(p−1)≡1(modp).
我们可以将式子变形:b⋅b^p−2≡1(modp),所以 binv=b^p−2
当 n 为质数时,可以用快速幂求逆元:
a / b ≡ a _ x (mod n)
两边同乘 b 可得 a ≡ a _ b _ x (mod n)
即 1 ≡ b _ x (mod n)
同 b * x ≡ 1 (mod n)
由费马小定理可知,当 n 为质数时
b ^ (n - 1) ≡ 1 (mod n)
拆一个 b 出来可得 b * b ^ (n - 2) ≡ 1 (mod n)
故当 n 为质数时,b 的乘法逆元 x = b ^ (n - 2)
当 n 不是质数时,可以用扩展欧几里得算法求逆元:
a 有逆元的充要条件是 a 与 p 互质,所以 gcd(a, p) = 1
假设 a 的逆元为 x,那么有 a * x ≡ 1 (mod p)
等价:ax + py = 1
exgcd(a, p, x, y)
// 说实话感觉一两句讲不清楚,想要了解自行了解吧,这里直接用代码吧😥
LL qmi(int a, int b, int p) // 快速幂求逆元
{
LL res = 1;
while(b){
if(b & 1) res = res * a % p;
a = (LL)a * a % p;
b >>= 1;
}
return res;
}
4.样例
已知A=(1,3,7,13,26,65,119,267)
是超递增序列,作为私钥,求解一个公钥,并利用这个公私钥对对明文 10101100
实现加解密。
解:
由于1+3+7+13+26+65+119+267=501
取 p=523,b=467,得$b^{-1}\equiv 28mod 532$。
则:
$$ t_1 \equiv 467 \times 1 \equiv 467(mod 523) \\ $$
$$ t_2 \equiv 467 \times 3 \equiv 355(mod 523) \\ $$
$$ t_3 \equiv 467 \times 7 \equiv 131(mod 523) \\ $$
$$ t_4 \equiv 467 \times 13 \equiv 318(mod 523) \\ $$
$$ t_5 \equiv 467 \times 26 \equiv 113(mod 523) \\ $$
$$ t_6 \equiv 467 \times 65 \equiv 21(mod 523) \\ $$
$$ t_7 \equiv 467 \times 119 \equiv 135(mod 523) \\ $$
$$ t_8 \equiv 467 \times 215 \equiv 215(mod 523) \\ $$
可得,A
和b
为私钥,与之对应的公钥:(467,355,131,318,113,21,135,215)和 p。
对于明文 10101100 加密得密文:
$$ t_1+t_3+t_5+t_6=467+131+113+21=732 $$
接收方收到密文 732 后计算:
$$ 732\times 28=20496\equiv 99(mod 523) $$
解超递增序列背包问题:
$$ m_1+3m_2+7m_3+13m_4+26m_5+65m_6+119m_7+267m_8=99(mod 523) $$
得到$m_1=m_3=m_5=m_6 = 1,m_2=m_4=m_7=m_8=0$,即得明文:10101100。
5.C++代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <sstream>
using namespace std;
const int N = 100010;
typedef long long LL;
int len; // 设置超递增序列长度(随便)
int A[N];//私钥
int b;//私钥
int p;//公钥
int t[N];//公钥
int sum;//A[N]前len项和
int primes[N];
int cnt;
bool st[N];
string clear_text; //明文
string secret_text; //密文
bool byt[N]; // 用于辅助找到明文二进制
int res;//选择加密还是解密
void get_primes(){ //线性筛法得质数
int n = N;
for(int i=2;i<=n;i++){
if(!st[i]) primes[cnt++]=i;
for(int j=0;primes[j]<=n/i;j++){
st[primes[j]*i]=true;
if(i%primes[j]==0) break;
}
}
}
void init() // 初始化获取私钥和公钥(上面有注释这里就不详细给了)
{
A[0] = 1;
sum += A[0];
for(int i = 1; i < len; i ++ )
{
A[i] = sum + 1;
sum += A[i];
}
for(int i = 0; i < cnt; i ++ )
{
if(primes[i] > sum)
{
p = primes[i];
b = primes[i - 1];
break;
}
}
for(int i = 0; i < len; i ++ ) t[i] = (b * A[i]) % p;
}
int qmi(int a, int b, int p) // 快速幂求逆元
{
LL res = 1;
while(b)
{
if(b & 1) res = res * a % p;
b >>= 1;
a = (LL) a * a % p;
}
return res;
}
void dfs(int u, int s)
{
if(u >= len)
{
int all = 0;
for(int i = 0; i < len; i ++ )
{
all += byt[i] * A[i];
}
if(all == s)
{
for(int i = 0; i < len; i ++ )
{
if(byt[i]) clear_text += '1';
else clear_text += '0';
}
}
return;
}
byt[u] = 0;
dfs(u + 1, s);
byt[u] = 1;
dfs(u + 1, s);
}
void encrypt(string s)
{
int c = 0;//密文c
for(int i = 0; i < s.size(); i ++ )
{
if(s[i] == '1')
{
c += t[i];
}
}
secret_text = to_string(c);
cout << "加密后得密文:" << secret_text << endl;
}
void encode(string str)
{
int c;
std::istringstream ss(str);
ss >> c;
int down = qmi(b, p - 2, p); // b得逆元
int s = down * c % p;
// 能力不够,应该能用DP,但是俺不会,只会最简单得dfs😋
dfs(0, s); // dfs遍历00000000-11111111
cout << "解密后的明文:" << clear_text << endl;
}
int main()
{
cout << "请输入1选择加密,或者输入2选择解密" << endl;
cin >> res;
cout << "请设置超递增序列长度" << endl;
cin >> len;
get_primes();
init();
if(res == 1)
{
cout << "请输入明文" << endl;
cin >> clear_text;
encrypt(clear_text);
}
else if(res == 2)
{
cout << "请输入密文" << endl;
cin >> secret_text;
encode(secret_text);
}
return 0;
}
结果:
//加密
请输入1选择加密,或者输入2选择解密
1
请设置超递增序列长度
8
请输入明文
10101100
加密后得密文:710
//解密
请输入1选择加密,或者输入2选择解密
2
请设置超递增序列长度
8
请输入密文
710
解密后的明文:10101100
6.总结
背包问题是 NP 完全类问题,至今还没有多项式时间的求解方法。若对所有可能解进行穷举搜索,当 n>100 时,计算是不可能的。然而对大多数基于背包问题的公钥加密体制,已经有有效的攻击方法。1983 年 Shamir 发现了 MH 加密体制的缺陷,即可以从普通的背包向量(公)重构出超递增背包向量(私),从而证明 MH 背包密码是不安全的。自从 MH 被破后,又有许多其他的背包加密体制被提出,但这些体制中的大多数都被用同样的密码分析方法攻破了,少数则采用更高级的分析方法攻破,虽然有极个别的背包变型还没有破解,但人们已不再信赖它们了。另外,大多数背包密码算法不适合数字签名。