Basis

基于子集和问题 - $a_{1}x_{1}+…+a_{n}x_{n}=E;\quad x_{i}\in\{0,1\}.$

Proved to be NP-hard.

但Merkle-Hellman cryptosystem存在trapdoor.

Merkle-Hellman cryptosystem

Key-Generation

有随机超递增序列$w=(w_{1},w_{2},…,w_{n})$，随机数$q>\sum w_{i}$及随机数r (gcd(r, q) = 1)

即定义序列$\beta$中的元素$\beta_{i}\equiv rw_{i}(mod\ q),i\in[1,n]$. 公钥$\beta$，私钥$(w,q,r)$.

Encryption

n-bit明文$\alpha=(\alpha_{1},\alpha_{2},…,\alpha_{n})$. 密文$c=\sum\alpha_{i}\beta_{i}$.

Decryption

$c’\equiv cr^{-1}\equiv \sum\alpha_{i}w_{i}(mod\ q)$.

则由$\sum\alpha_{i}w_{i}<q$及超递增序列w易知，令j从n-1到0，背包当前容量为c时，

(1) $c<w[j]\rightarrow m[j]=0,j—;$

(2) $c\geq w[j]\rightarrow m[j]=1,c-=w[j],j—;$

即可恢复出明文m.

More Version

选取一个permutation $\pi$，在生成的$\beta$序列后，再令$\beta’_{i}=\beta_{\pi(i)}$. 公开序列则为$\beta’$. 持有私钥加入$\pi$.

The Multiple Knapsack Cryptosystem

Key-Generation

私钥 - 六元组$(A,B,E,p,u,v)$，公钥 - 三元组$(F,G,H)$.

其中私钥$A(\{a_i\}),B(\{b_i\}),C(\{c_i\})$满足Condition 1, 2：

Condition 1.

Condition 2.

[Q] - paper里提出的是$a_{1}(2^{n-1}-2^{k-1})(a_{k}-\sum_{i=1}^{k-1}a_{i})$及$b_{1}…$，但decryption原理推导时，个人感觉存在一定问题…故此处与paper不一.

Algorithm (Generate A,B,E)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import *

def GenPriKnapsack(n):
    a1, b1, e1 = getRandomNBitInteger(16), getRandomNBitInteger(16), getRandomNBitInteger(16)
    A, B, E = [a1], [b1], [e1]
    a, b, e = a1, b1, e1
    sum_a, sum_b, sum_e = a, b, e
    tmp = 2 ** (n - 1)
    for i in range(n - 1):
        a = getRandomRange(sum_a // 2, sum_a)
        b = getRandomRange(sum_b // 2, sum_b)
        met = -a * b + sum_a * sum_b + sum_e - (tmp - 2 ** (i + 1)) * (b1 * (a - sum_a) + a1 * (b - sum_b))
        e = met + getRandomRange(2**8, 2**16)
        sum_a += a
        sum_b += b
        sum_e += e
        A.append(a)
        B.append(b)
        E.append(e)
    return A, B, E

由Condition 1我们有$a_{k}b_{k}\leq (\sum_{i=1}^{k-1}a_{i})(\sum_{i=1}^{k-1}b_{i})$，且能由此和Condition 2推出$e_{k}>\sum_{i=1}^{k-1}e_{i}$. (Superincreasing)

Algorithm (Generate p,u,v)

1
2
3
4
5
p = (sum_a * sum_b + sum_e) + getRandomRange(2**8, 2**16)
s = size(p) // 2
u, v = getPrime(s), getPrime(s)
while GCD(u, p) != 1 or GCD(v, p) != 1:
    u, v = getPrime(s), getPrime(s)

Algorithm (Generate F,G,H)

1
2
3
F = [(u * _) % p for _ in A]
G = [(v * _) % p for _ in B]
H = [(u * v * _) % p for _ in E]

Encryption

$M=(m_{1},m_{2},…,m_{n})$，有$C:=(\sum_{i=1}^{n}f_{i}m_{i})(\sum_{i=1}^{n}g_{i}m_{i})+\sum_{i=1}^{n}h_{i}m_{i}$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def encrypt(pubkey, m):
    F, G, H = pubkey
    n = len(F)
    m = [int(_) for _ in bin(bytes_to_long(m))[2:]]
    m = [0] * ((8 - len(m) % 8) % 8) + m
    c = []
    for i in range(0, len(m), n):
        block_m = m[i : i + n]
        if len(block_m) != n:
            padding = [getRandomRange(0, 2) for _ in range(n - len(block_m))]
            block_m += padding
        fm, gm, hm = 0, 0, 0
        for i in range(n):
            fm += F[i] * block_m[i]
            gm += G[i] * block_m[i]
            hm += H[i] * block_m[i]
        block_c = fm * gm + hm
        c.append(hex(block_c)[2:])
    return c

Decryption

$D(C):=u^{-1}v^{-1}C(mod\ p)=(\sum_{i=1}^{n}a_{i}m_{i})(\sum_{i=1}^{n}b_{i}m_{i})+\sum_{i=1}^{n}e_{i}m_{i}$.

由Condition 1. 知，$\sum_{i=1}^{k}a_{i}\leq 2^{k-1}a_{1},\sum_{i=1}^{k}b_{i}\leq 2^{k-1}b_{1}$，有

$\because\sum_{i=1}^{k}a_{i}=2^{k-1}a_{1}-\Delta\quad\therefore\sum_{i=1}^{n}a_{i}\leq 2^{n-1}a_{1}-2^{n-k}\Delta$.

$\therefore\sum_{i=k+1}^{n}a_{i}=\sum_{i=1}^{n}a_{i}-\sum_{i=1}^{k}a_{i}\leq a_{1}(2^{n-1}-2^{k-1})$. 同理$\sum_{i=k+1}^{n}b_{i}\leq b_{1}(2^{n-1}-2^{k-1})$.

又由$(a_{k}-\sum_{i=1}^{k-1}a_{i})\leq 0,(b_{k}-\sum_{i=1}^{k-1}b_{i})\leq 0$及Condition 2. 知，

可知上式为下式的充分条件

又等价为

且在$m_{k}=1$时，有另一显然成立的不等式如下

由(1)(2)有以下解密算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def decrypt(prikey, c):
    A, B, E, u, v, p = prikey
    n = len(A)
    u_inv = inverse(u, p)
    v_inv = inverse(v, p)
    m = ""
    for block_c in c:
        block_m = ""
        Dc = (u_inv * v_inv * int(block_c, 16)) % p
        am, bm, em = 0, 0, 0
        for k in range(n - 1, -1, -1):
            d = (am + A[k]) * (bm + B[k]) + (em + E[k])
            if Dc >= d:
                block_m += "1"
                am += A[k]
                bm += B[k]
                em += E[k]
            else:
                block_m += "0"
        m = m + block_m[::-1]
    return long_to_bytes(int(m, 2))

Code For Test

MKS.py

Attack on the MKS Cryptosystem

由于私钥A，B具有相同的非超递增性质，所以证其一即可，我们令m为一小于n的正整数，定义以下在$N^{m}$上的向量：

由于攻击者仅知公钥F部分，未知私钥A，但有同余关系$f\equiv ua(mod\ p)$，因此给出以下引理：

Lemma 1

令向量$x\in Z^{m}$，若$x\perp f$，则有$x\perp a$或$|x|\geq \frac{p}{|a|}$.

Proof. 有$\equiv 0(mod\ p)$，若假设x不与a正交，则有$||\geq p$（因为$gcd(u,p)=1$），再由柯西不等式可知$P\leq |x||a|$.