はじめに

セキュリティキャンプ全国大会2021に参加しました。応募するにあたって応募課題なるものを提出する必要があり、特に集中コースの応募課題はクソむずいです。

本記事は私が応募したL-1 暗号解読チャレンジゼミの応募課題晒しです。どこかの誰かへ、参考になればと思います。

Schmidt-Samoa暗号について解説し、実装してください。

Schmidt-Samoa暗号の鍵生成、暗号化、復号のアルゴリズムは以下の通りです[1][2]。

鍵生成：
$$N=p^2q$$
$$d=N^{-1}\mod lcm(p-1,,q-1)$$

暗号化：
$$c=m^N\mod N$$

復号：
$$m=c^d\mod pq$$

これらを踏まえて実装します。言語はPython3.7を使用しました。

schmidt_samoa.py

from Crypto.Util.number import *

class schmidt_samoa:
    def __init__(self, bits): # 初期化（鍵生成）
        self.gen_new_key(bits)

    def gen_new_key(self, bits): # 鍵生成
        self.p = getStrongPrime(bits)
        self.q = getStrongPrime(bits)
        self.N = self.p**2 * self.q
        lcm_pq = self.LCM(self.p - 1, self.q - 1)
        self.d = inverse(self.N, lcm_pq)

    def LCM(self, a, b): # a, bの最小公倍数を計算
        return (a * b) // GCD(a, b)

    def encryption(self, m): # 暗号化
        m = bytes_to_long(m.encode("utf-8"))
        c = pow(m, self.N, self.N)
        return c

    def decryption(self, c): # 復号
        m = pow(c, self.d, self.p * self.q)
        m = long_to_bytes(m).decode("utf-8")
        return m


r = schmidt_samoa(1024) # 1024bitの鍵を生成
m = "Hello_Schmidt_Samoa_cryptography!!!"
cipher = r.encryption(m)
print("cipher :", cipher)

plane = r.decryption(cipher)
print("plane :", plane)

実行結果。

> python schmidt_samoa.py
cipher : 1376063264612298996776091836628703269271250797234474235435697802430446781952502800054633078632211205553714558952453349108245389024596211197751243017755249894805382728917909375420445451460023812537921098929046213627594059215559945744268903509339910563700385438423906603276275225473215185200284630990924588542421008833183463938588203524823750543508913224999337754115421808186392869353325964185002164215666080307545339468428627884681290443051649798043145546674187757616807086967301629974829085160811468750032651709901388862160954531501527806445231146619780032842353915397218508648752993824032810840262501700162274577847189378539791861203839898966966783956375077270006873005607090273390364202214626585906996691648956560482380857300139332633165656479185416000685283517523558071756394444665697948476843177286966097542016243653571598207886985921927295227418025753845216547484337853080369848168437084847439894291939233433188062997459
plane : Hello_Schmidt_Samoa_cryptography!!!

正しく復号できることが確認できました。

Schmidt-Samoa暗号という暗号には、暗号として"役に立たない"レベルの瑕疵が存在します。もしもこれに気づけた場合は、それについて解説してください。

暗号化アルゴリズムにおいて、$m^N$を計算していることがわかります。同じ素因数分解の難しさを暗号強度としているRSA暗号の場合、指数は0x10001=65537なので、暗号化が遅くなると考察できます。

実際にSchmidt-Samoa暗号とRSA暗号の速度を比較してみます。暗号化の指数計算の速度を比較したいので、時間に大きな影響があると考えられる巨大素数の生成と復号の実行時間は含めませんでした。

time_comp.py

from Crypto.Util.number import *
from time import perf_counter as time

class Schmidt_Samoa: # Schmidt-Samoa暗号
    def __init__(self, bits):
        self.gen_new_key(bits)

    def gen_new_key(self, bits):
        self.p = getStrongPrime(bits)
        self.q = getStrongPrime(bits)
        self.N = self.p**2 * self.q
        lcm_pq = self.LCM(self.p - 1, self.q - 1)
        self.d = inverse(self.N, lcm_pq)

    def LCM(self, a, b):
        return (a * b) // GCD(a, b)

    def encryption(self, m):
        m = bytes_to_long(m.encode("utf-8"))
        c = pow(m, self.N, self.N)
        return c

    def decryption(self, c):
        m = pow(c, self.d, self.p * self.q) # ここの指数計算が遅いと考えられる
        m = long_to_bytes(m).decode("utf-8")
        return m

class RSA: # RSA暗号
    def __init__(self, bits):
        self.gen_new_key(bits)

    def gen_new_key(self, bits):
        self.p = getStrongPrime(bits)
        self.q = getStrongPrime(bits)
        self.N = self.p * self.q
        self.e = 65537
        phi = (self.p - 1) * (self.q - 1)
        self.d = inverse(self.e, phi)

    def encryption(self, m):
        m = bytes_to_long(m.encode("utf-8"))
        c = pow(m, self.e, self.N)
        return c

    def decryption(self, c):
        m = pow(c, self.d, self.N)
        m = long_to_bytes(m).decode("utf-8")
        return m


bits = 1024
m = "Hello_Schmidt_Samoa_cryptography!!!"
count = 1000 # 指数計算を行う回数

r1 = Schmidt_Samoa(bits)
cipher = r1.encryption(m)
plane = r1.decryption(cipher)
assert plane == m # 念のため正しく復号できることを確認
t0 = time()
for i in range(count):
    cipher = r1.encryption(m) # 暗号化

print("Schmidt-Samoa :", time() - t0, "[s]")

r2 = RSA(bits)
cipher = r2.encryption(m)
plane = r2.decryption(cipher)
assert plane == m # 念のため正しく復号できることを確認
t0 = time()
for i in range(count):
    cipher = r2.encryption(m) # 暗号化

print("RSA :", time() - t0, "[s]")

実行結果

> python time_comp.py
Schmidt-Samoa : 88.8674412 [s]
RSA : 0.16095640000000344 [s]

実行結果より、Schmidt-Samoa暗号はRSA暗号と比べて暗号化に500倍以上時間がかかるとわかりました。

あなたの好きな公開鍵暗号を一つ取り上げ、解説し、実装してください。

ナップザック暗号が大好きなので、それについて実装・解説を行います。
ナップザック暗号の鍵生成、暗号化、復号のアルゴリズムは以下の通りです。
鍵生成：
bit長$n$の平文を暗号化するために、超増加数列$A$を定義します。
超増加数列とは、各項がそれ以前の項の総和よりも大きい数列のことです。
$$A=(a_1, a_2, ..., a_n)$$
さらに$q> \sum_{i=1}^{n}a_i$を満たす秘密鍵$q$と、$q$と互いに素な秘密鍵$p$を定義します。
以上の値より、公開鍵$β$を以下の式で生成します。

$$β=(β_1, β_2, ..., β_n)$$
$$β_i=p・A_i \mod q$$

暗号化：
平文$m$のbit長を$n$とし、暗号化をするうえで$m$を2進数で表します。すなわち$m_i$は平文の第$i$bitであることを表します。

$$m=m_1 | m_2 | ... | m_n$$

ただし$|$はbitを繋げる演算とします。

そして、以下の式より暗号文$c$を計算します。

c=\sum_{i=1}^{n}β_i・m_i

復号：
まず以下の式より$c'$を計算します。
$$c'=c・p^{-1} \mod q$$

ここで$c'$は超増加数列$A$の部分和であるので、$A$が超増加であることを利用すれば$O(n)$で部分和問題を解くことができます。部分和問題を解くことで得られた0, 1で表現されるベクトル（$A$と$m$の内積が$c'$となるような$m$）が平文ベクトルとなります[3]。

knapsack.py

from Crypto.Util.number import *
from random import getrandbits


class knapsack:
    def __init__(self, bits):
        self.gen_new_key(bits)
    
    def gen_new_key(self, bits):
        self.A = []
        a, b = 0, 0
        for _ in range(bits): # 超増加数列Aを生成
            a += getrandbits(32) + b
            b += a # 変数bにこれまでの数列の総和を代入しAが超増加になるようにする
            self.A.append(a)
            
        # 互いに素になるように素数で秘密鍵を定義
        self.q = getPrime(1024)
        self.p = getPrime(1024)
        
        assert self.q > sum(self.A) # 法qを上回ってないか確認

        self.pub_key = [a * self.p % self.q for a in self.A] # 公開鍵を生成
        f = open("pub_key.py", "w")
        f.write("pub_key = " + str(self.pub_key) + "\n")
        f.close()

    def encryption(self, m):
        m = bytes_to_long(m.encode("utf-8"))
        m = bin(m)[2:]
        length = len(m)
        cipher = sum([int(m[i]) * self.pub_key[i] for i in range(length)]) # 平文と秘密鍵のベクトルから暗号文（ベクトル内積）を計算
        f = open("cipher.py", "w")
        f.write("cipher = " + str(cipher) + "\n")
        f.close()
        return cipher

    def decryption(self, c):
        c = c * inverse(self.p, self.q) % self.q
        m = ""
        for a in self.A[::-1]: # Aが超増加数列であることを利用し復号
            if a <= c:
                c -= a
                m += "1"
            else:
                m += "0"
        m = long_to_bytes(int(m[::-1], base=2)).decode("utf-8")
        return m


plane = "The knapsack cipher can be attacked with the LLL algorithm!!!"
length = bytes_to_long(plane.encode("utf-8")).bit_length()
print("bit length :", length)

r = knapsack(length) # 鍵長は平文のbit長分必要なのでlength分生成

cipher = r.encryption(plane)
print("cipher :", cipher)

plane = r.decryption(cipher)
print("plane :", plane)

実行結果。

> python knapsack.py
bit length : 487
cipher : 11352597607209369490497843269170920195594315198775071694734111805080902716615039558095951911905951556161294824966450105422699569698806231013649249477629741314041736304225361294268741932980544030676052772057738667664381860232845821085021940208598932796473010766331791054990709539245836884563561877575600091082569
plane : The knapsack cipher can be attacked with the LLL algorithm!!!

正しく復号できることが確認できました。

前問で取り上げた暗号は応募時点で「安全」ですか？解読手法があればそれを一つ解説し、安全ならばその理由を解説してください。

ナップザック暗号の安全性については密度というものが重要になってきます。密度$d$は以下の式で計算できます。

d=\frac{n}{\log_2 max(pub\_key)}

ここで$d$が$d≤0.9408$を満たすとき、低密度攻撃（CLOS法）を用いて平文を解読できます[4]。基底Mを

とおき、Mが貼る格子をLLLアルゴリズムで攻撃すれば適当なiにおいてM[i][0]が0でそれ以外が1か-1のベクトルが得られそれが平文となります。

以降攻撃スクリプト。

attack.sage

from Crypto.Util.number import *
from math import log2
from pub_key import pub_key
from cipher import cipher


def create_matrix(pub, c): # 基底Mを生成
    N = len(pub)
    m_id = matrix.identity(N) * 2
    m = matrix(ZZ, 1, N + 1, pub[:] + [-c])
    B = m_id.augment(matrix(ZZ, N, 1, [-1] * N))
    m = m.stack(B)
    return m

def shortest_vector(matrix): # 最短経路（m[i][0]が0でそれ以外が-1, 1のベクトル）を検索
    for i in matrix.columns():
        if not(i[0]) and all([(j == -1 or j == 1) for j in i[1:]]):
            return i


d = len(pub_key) / log2(max(pub_key)) # 密度dを計算
print("d =", d)

M = create_matrix(pub_key, cipher) # 基底を張る
LLL_M = M.transpose().LLL().transpose() # LLLアルゴリズムで殴る
V = shortest_vector(LLL_M) # 最短経路を検索

# 最短経路のベクトルVは-1, 1で表されるので-1を0で置換し復号する
plane = "".join(list(map(str, V)))
plane = plane.replace("0", "")
plane = plane.replace("-1", "0")

print("plane :", long_to_bytes(int(plane, base=2)))

実行結果。

> sage attack.sage
d = 0.4759199847945804
plane : The knapsack cipher can be attacked with the LLL algorithm!!!

正しく復号できることができました。

参考文献