Day 10 背包公鑰加密法

15th鐵人賽

廖紳勛

2023-09-24 09:34:46

170 瀏覽

分享至

背包問題

其問題如下：
給定n個數字 $W_1, \dots, W_n$ 以及一個指定的和S，是否存在一些由0和1組成的a，使得 $S = a_1W_1 + \dots + a_nW_n$

舉例來說，n=8，給定85, 13, 9, 7, 47, 27, 99, 86，S=172，則a=(1, 1, 0, 0, 1, 1, 0, 0)可以滿足其要求

在不對給定的數字多做假設的情況下，這種一般類型的背包問題是NP完備

也就是隨便給n個數字，要決定是否某些數字的和等於某個數字，沒有人能找到在多項式時間內完成的方法
可以看得出來要驗證a是否滿足要求很容易，但要能找到滿足要求的a相當困難

特殊情況

不過，在某些很特殊的情況下，解開背包問題是相當容易的

假設給定的數字為3, 6, 11, 25, 46, 95, 200, 411
其初始給定的數字為遞增，且每個數字要比前面數字總和來得大(例如：6比3大，11比3+6大...)
這種情況稱為超級遞增背包(superincreasning Knapsack)

可以透過以下函數檢查：

def check_superincreasing(W):
    Ws = W.cumsum()
    
    Ws = np.insert(Ws[:-1], 0, 0)

    if (Ws < W).all():
        return True
    else: return False
    
check_superincreasing(np.array([3, 6, 11, 25, 46, 95, 200, 411]))

假設指定的和S=309，以下示範如何在多項式時間找出a：

因為S<411 ==> a8 = 0
因為S>200 ，a7不可能為0，否則剩餘的數字和小於200，不足S ==> a7 = 1，令S=S-200=109
由於S>95，同理a6 = 1，S = S-95 = 14
由於S<46 ==> a5=0
S<25 ==> a4 = 0
S>11 ==> a3 = 1，S = S-11 = 3
S < 6 ==> a2 = 0
S = 3 ==> a1 = 1
整個過程可以在n步就完成，得出a=(1,0,1,0,0,1,1,0)

def superincreasing(S, W):
    if not check_superincreasing(W):
        return ValueError('W not superincreasing')
    else:
        a = np.zeros(len(W))
        for i in range(len(W)):
            if S >= W[-i-1]:
                a[-i-1] = 1
                S -= W[-i-1]
        if S != 0:
            return 'a does not exist'
        return a

superincreasing(309, np.array([3, 6, 11, 25, 46, 95, 200, 411]))

背包加密

有了以上的知識，終於可以進入背包加密的主要演算法：

Bob先隨機地產生一個超級遞增背包W
並隨機地選擇一個比這個超級背包總和還要大的數q
以及一個比q還要小且互質的數r

這三個東西(W,q,r)就是Bob自己要收好的私鑰

將W內的所有數字乘以r除以q，所得到的餘數就是公鑰

舉個實際的例子：

Bob先隨機地生成超級遞增背包W = (114, 117, 238, 471, 944, 1891, 3777, 7553)

此背包總和為15105

隨機地選擇比15105大的整數q = 21888，同時也隨機找一個與q互質數字r = 20555

接著Bob將W內的東西都乘以r除以q取餘數，得到一般背包(1254, 19143, 11066, 6909, 11152, 18305, 21387, 331)

def transform_super2ordinary(q, r, W):
    if np.gcd(q,r)!=1:
        return ValueError('q,r must be coprime')
    if not check_superincreasing(W):
        return ValueError('W not superincreasing')
    if q < W.sum():
        return ValueError('q must be bigger')
    else:
        return (W * r) % q

q = 21888
r = 20555
W = np.array([114,  117,  238,  471,  944, 1891, 3777, 7553])
transform_super2ordinary(q, r, W)

一般人只能看到(1254, 19143, 11066, 6909, 11152, 18305, 21387, 331)，完全不知道q, r, W的值