My knapsack has a hole in it
Cipher text: 11b90d6311b90ff90ce610c4123b10c40ce60dfa123610610ce60d450d000ce61061106110c4098515340d4512361534098509270e5d09850e58123610c9
Public key: {99, 1235, 865, 990, 5, 1443, 895, 1477}
The flag is slightly off format.
問題文などを見た感じナップザック暗号だろうか。しかしCLOSに突っ込んでも答えが出なかった
明らかに怪しいことにpublic keyがめちゃくちゃ小さい。ナップザック暗号ではn bitの平文を暗号化するためにn要素の数列を必要とするので、この場合だと8bitの値しか暗号化できないことになる。もし0b11111111を暗号化してもこのcipher textにはならないんじゃないか
鍵が8bitということで1文字ずつ同じ鍵で暗号化したんじゃないかと思った。それで暗号化したやつを前から連結した、みたいな。ちょっとやってみる。
from Crypto.Util.number import *
def knapsack_encrpt(pub_key, m):
bits = "{:08b}".format(m)
c = 0
for i, k in enumerate(pub_key):
if bits[i] == '1':
c += k
return long_to_bytes(c)
key = [99, 1235, 865, 990, 5, 1443, 895, 1477]
cipher = long_to_bytes(0x11b90d6311b90ff90ce610c4123b10c40ce60dfa123610610ce60d450d000ce61061106110c4098515340d4512361534098509270e5d09850e58123610c9)
flag = ''
while len(cipher) > 0:
for i in range(0, 256):
c = knapsack_encrpt(key, i)
if cipher.startswith(c):
flag += chr(i)
cipher = cipher[len(c):]
break
print(flag)
最初これでやってうまく行かなかったんだけど、ナップザック暗号では上のbitから暗号化しても下のbitから暗号化しても原理的には暗号化されるし、それに合わせて復号すればよいということを思い出したのでそっちも試してみたら通った
from Crypto.Util.number import *
def knapsack_encrpt(pub_key, m):
bits = "{:08b}".format(m)[::-1]
c = 0
for i, k in enumerate(pub_key):
if bits[i] == '1':
c += k
return long_to_bytes(c)
key = [99, 1235, 865, 990, 5, 1443, 895, 1477]
cipher = long_to_bytes(0x11b90d6311b90ff90ce610c4123b10c40ce60dfa123610610ce60d450d000ce61061106110c4098515340d4512361534098509270e5d09850e58123610c9)
flag = ''
while len(cipher) > 0:
for i in range(0, 256):
c = knapsack_encrpt(key, i)
if cipher.startswith(c):
flag += chr(i)
cipher = cipher[len(c):]
break
print(flag)
