# 背包加密¶

Warning

The current page still doesn't have a translation for this language.

You can read it through Google Translate.

Besides, you can also help to translate it: Contributing.

## 背包问题¶

x_1a_1+x_2a_2+,...,+x_na_n=W

a_i>\sum_{k=1}^{i-1}a_k

## Merkle–Hellman¶

### 公私钥生成¶

#### 生成公钥¶

m>\sum_{i=1}^{i=n}a_i

gcd(w,m)=1

b_i \equiv w a_i \bmod m

### 加解密¶

#### 加密¶

\sum_{i=1}^{i=n}b_iv_i \bmod m

#### 解密¶

\sum_{i=1}^{i=n}w^{-1}b_iv_i \bmod m=\sum_{i=1}^{i=n}a_iv_i \bmod m

b_i \equiv w a_i \bmod m

### 例子¶

secret = 'CENSORED'
msg_bit = bin(int(secret.encode('hex'), 16))[2:]


keyPair = makeKey(len(msg_bit))


def makeKey(n):
privKey = [random.randint(1, 4**n)]
s = privKey[0]
for i in range(1, n):
privKey.append(random.randint(s + 1, 4**(n + i)))
s += privKey[i]
q = random.randint(privKey[n-1] + 1, 2*privKey[n-1])
r = random.randint(1, q)
while gmpy2.gcd(r, q) != 1:
r = random.randint(1, q)
pubKey = [ r*w % q for w in privKey ]
return privKey, q, r, pubKey


def encrypt(msg, pubKey):
msg_bit = msg
n = len(pubKey)
cipher = 0
i = 0
for bit in msg_bit:
cipher += int(bit)*pubKey[i]
i += 1
return bin(cipher)[2:]


import binascii
# open the public key and strip the spaces so we have a decent array
fileKey = open("pub.Key", 'rb')
pubKey = fileKey.read().replace(' ', '').replace('L', '').strip('[]').split(',')
nbit = len(pubKey)
# open the encoded message
fileEnc = open("enc.txt", 'rb')
encoded = fileEnc.read().replace('L', '')
print "start"
# create a large matrix of 0's (dimensions are public key length +1)
A = Matrix(ZZ, nbit + 1, nbit + 1)
# fill in the identity matrix
for i in xrange(nbit):
A[i, i] = 1
# replace the bottom row with your public key
for i in xrange(nbit):
A[i, nbit] = pubKey[i]
# last element is the encoded message
A[nbit, nbit] = -int(encoded)

res = A.LLL()
for i in range(0, nbit + 1):
# print solution
M = res.row(i).list()
flag = True
for m in M:
if m != 0 and m != 1:
flag = False
break
if flag:
print i, M
M = ''.join(str(j) for j in M)
# remove the last bit
M = M[:-1]
M = hex(int(M, 2))[2:-1]
print M


295 [1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0]
415349535f3962643364356664323432323638326331393536383830366130373036316365
>>> import binascii
>>> binascii.unhexlify('415349535f3962643364356664323432323638326331393536383830366130373036316365')
'ASIS_9bd3d5fd2422682c19568806a07061ce'


flag 是 ASIS_9bd3d5fd2422682c19568806a07061ce

### 题目¶

• 2017 国赛 classic