ナップザック暗号 - crypto-writeup-public

解ける暗号。超増加列を用いた場合に部分和問題が簡単に解けることを利用して復号を行い、超増加列を鍵とすると簡単に解けてしまうため、各 $w_i$ を $w_i * r \mod q$ と変換して一般の数列にすることで暗号化鍵からの復号を妨げている。

暗号文は一つの数値に、秘密鍵や公開鍵は数列になる。nbitの平文を暗号化するためにn要素の数列が必要

鍵生成

超増加列 $w = w_1, w_2, ..., w_n、$ を作る。超増加列は $\sum_{i=1}^{n}{w_i} < w_{n+1}$ となっている、つまり、それまでの総和より大きい数からなる数列らしい。
$\sum_i w_i < q$ である $q$ と $gcd(q, r) = 1$ の $r$ を選ぶ。 $q$ を素数にすれば $r$ は適当に選べる
(( $w_1, w_2, ..., w_n$ ), q, r)が秘密鍵
$\beta_i = r*w_i \mod q$ として( $\beta_1, \beta_2, ..., \beta_n$ )が公開鍵

暗号化

nビットの平文mをビット単位で分割して( $m_1, m_2, ..., m_n$ )とする
暗号文C = $\sum_{i=1}^n{m_i\beta_i}$

復号

$s \equiv r^{-1} \mod q$ なるsを用意して、 C' = CSとする。
C' = $\sum_i {m_i\beta_ir^{-1}} = \sum_i {m_irw_ir^{-1}} \equiv \sum_i {m_iw_i} \mod q$
$m_i$ は0, 1なので、以下の手順で大きい方から順番に平文を復元できる
C'と $w_i$ を比較して $C' > w_i$ なら $m_i=1$ 、 $C' < w_i$ なら $m_i = 0$ である。
$C' > w_i$ なら $C' \leftarrow C' - w_i$

攻撃

CLOS法が今の所一番強そう。よくわかってないが↓のsageスクリプトに突っ込む

https://kimiyuki.net/writeup/ctf/2015/plaidctf-2015-lazy/

b = 
c = 

# check the density
n = len(b)
d = float(n / log(max(b), 2))
assert(d < 0.9048)

# low-density attack, CLOS method
# prepare a basis
MULTIPLIER = 100
B = matrix(ZZ, n + 1, n + 1)
B.set_block(0, 0, MULTIPLIER * matrix(n, 1, b))
B.set_block(n, 0, MULTIPLIER * matrix([-c]))
B.set_block(0, 1, 2 * identity_matrix(n))
B.set_block(n, 1, matrix([-1] * n))

# LLL algorithm
for x in B.LLL():
    print(x)
    if x[0] == 0 and all((x_i in [-1, +1]) for x_i in x[1:]):
        print('x={}'.format(x))

        # decode x
        m = 0
        for x_i in reversed(x[1:]):
            m *= 2
            m += int(x_i == +1)
        print('m={}'.format(m))