RSA で、これまでと違ってとりあえず形式的には正しそうなパラメータが付与された。鍵も2048ビットあった。

実は素数のどちらかが小さくて素因数分解できるのでは、と思って奇数で割り続けるプログラムを走らせたところ、予想通りすぐに素因数分解が完了した。

というわけで、あとはその結果をもとに Wikipedia とかを見ながら暗号化解除。

   
#!/usr/bin/python
 
N=0xee290c7a603fc23300eb3f0e5868d056b7deb1af33b5112a6da1edc9612c5eeb4ab07d838a3b4397d8e6b6844065d98543a977ed40ccd8f57ac5bc2daee2dec301aac508f9befc27fae4a2665e82f13b1ddd17d3a0c85740bed8d53eeda665a5fc1bed35fbbcedd4279d04aa747ac1f996f724b14f0228366aeae34305152e1f430221f9594497686c9f49021d833144962c2a53dbb47bdbfd19785ad8da6e7b59be24d34ed201384d3b0f34267df4ba8b53f0f4481f9bd2e26c4a3e95cd1a47f806a1f16b86a9fc5e8a0756898f63f5c9144f51b401ba0dd5ad58fb0e97ebac9a41dc3fb4a378707f7210e64c131bca19bd54e39bbfa0d7a0e7c89d955b1c9f
e=0x10001
c=0x3dbf00a02f924a70f44bdd69e73c46241e9f036bfa49a0c92659d8eb0fe47e42068eaf156a9b3ee81651bc0576a91ffed48610c158dc8d2fb1719c7242704f0d965f8798304925a322c121904b91e5fc5eb3dc960b03eb8635be53b995217d4c317126e0ec6e9a9acfd5d915265634a22a612de962cfaa2e0443b78bdf841ff901423ef765e3d98b38bcce114fede1f13e223b9bd8155e913c8670d8b85b1f3bcb99353053cdb4aef1bf16fa74fd81e42325209c0953a694636c0ce0a19949f343dc229b2b7d80c3c43ebe80e89cbe3a3f7c867fd7cee06943886b0718a4a3584c9d9f9a66c9de29fda7cfee30ad3db061981855555eeac01940b1924eb4c301
 
# 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
 
def decrypt_rsa(N, e, d, cipher):
    c_powers = [cipher]
    cur_power = 1
 
    while cur_power <= d:
        tmp = c_powers[len(c_powers) - 1]
        c_powers.append((tmp * tmp) % N)
        cur_power *= 2
 
    cur_power = 1
    cur_pos = 0
    ans = 1
 
    while cur_power <= d: if d & cur_power > 0:
            ans *=  c_powers[cur_pos]
            ans %= N
        cur_pos += 1
        cur_power *= 2
 
    return ans
 
 
#i = 3
i = 57970027
 
while True:
    if N%i==0:
        p=i
        q=N/p
        break
 
    i+=2
 
d = euclidean(e, (p-1)*(q-1))
 
ans = decrypt_rsa(N, e, d, c)
 
ans_array = []
while ans:
    ans_array.append(chr(ans % 256))
    ans /= 256
 
ans_array.reverse()
 
print ''.join(ans_array)