Rating: 0

謎の行列みたいなのがおいてある。そのままではどうしようもないので、とりあえず matrix encryption とかで検索すると、 Hill Cipher が出てきて問題名とも合致。というわけで Hill Cipher の Wikipedia の記事を見ながら解く。

mod Nでの逆行列の計算に戸惑うが、ウェブ検索した結果見つけた動画(https://www.youtube.com/watch?v=LhBovzm4Ajs )では、普通の逆行列に近い処理をしていた。普通の逆行列は numpy なるツールで計算できそうなので、確認しながら最終的には以下のようなコードに。
    
#!/usr/bin/python
 
import numpy
 
alphabet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ123456789_{}"
N = len(alphabet)
 
matrix = [[54, 53, 28, 20, 54, 15, 12, 7],
          [32, 14, 24, 5, 63, 12, 50, 52],
          [63, 59, 40, 18, 55, 33, 17, 3],
          [63, 34, 5, 4, 56, 10, 53, 16],
          [35, 43, 45, 53, 12, 42, 35, 37],
          [20, 59, 42, 10, 46, 56, 12, 61],
          [26, 39, 27, 59, 44, 54, 23, 56],
          [32, 31, 56, 47, 31, 2, 29, 41]]
 
ciphertext = "7Nv7}dI9hD9qGmP}CR_5wJDdkj4CKxd45rko1cj51DpHPnNDb__EXDotSRCP8ZCQ"
 
# cf: http://arc360.info/algo/privatekey.html
def euclidean(x, y):
    x1 = 1
    y1 = 0
    z1 = x
    x2 = 0
    y2 = 1
    z2 = y
 
    while z2 != 1:
        q = (z1 - (z1 % z2)) / z2
        x1 = x1 - q * x2
        y1 = y1 - q * y2
        z1 = z1 - q * z2
 
        x1, y1, z1, x2, y2, z2 = x2, y2, z2, x1, y1, z1
 
    while x2 < 0:
        x2 += y
     
    return x2
 
alphabet_to_number = {}
 
for i in range(0, len(alphabet)):
    alphabet_to_number[alphabet[i]] = i
 
# https://www.youtube.com/watch?v=LhBovzm4Ajs
det = numpy.around(numpy.linalg.det(matrix)).astype(numpy.int64)
inv = numpy.around(det * numpy.linalg.inv(matrix)).astype(numpy.int64)
 
mul = euclidean(det, N)
inv = mul * inv
 
for i in range(0, len(inv)):
    for j in range(0, len(inv[i])):
        inv[i][j] = inv[i][j] % N
 
ans = ''
 
for j in range(0, 8):
    cipherarray = []
    for i in range(0, len(inv)):
        cipherarray.append(alphabet_to_number[ciphertext[j * len(inv) + i]])
    plain = numpy.dot(inv, cipherarray)
 
    for i in range(0, len(plain)):
        ans += alphabet % N]
 
print ans