公钥密码体制中,除了 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++ 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#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;
}

结果

1
2
3
4
5
6
7
8
请设置超递增序列长度
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)

1
2
3
4
5
6
7
8
9
10
11
// 说实话感觉一两句讲不清楚，想要了解自行了解吧，这里直接用代码吧😥
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++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#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
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//加密
请输入1选择加密，或者输入2选择解密
1
请设置超递增序列长度
8
请输入明文
10101100
加密后得密文:710
//解密
请输入1选择加密，或者输入2选择解密
2
请设置超递增序列长度
8
请输入密文
710
解密后的明文:10101100

6.总结

背包问题是 NP 完全类问题，至今还没有多项式时间的求解方法。若对所有可能解进行穷举搜索，当 n>100 时,计算是不可能的。然而对大多数基于背包问题的公钥加密体制,已经有有效的攻击方法。1983 年 Shamir 发现了 MH 加密体制的缺陷,即可以从普通的背包向量(公)重构出超递增背包向量(私),从而证明 MH 背包密码是不安全的。自从 MH 被破后，又有许多其他的背包加密体制被提出,但这些体制中的大多数都被用同样的密码分析方法攻破了，少数则采用更高级的分析方法攻破,虽然有极个别的背包变型还没有破解,但人们已不再信赖它们了。另外，大多数背包密码算法不适合数字签名。