Crypt 200: Decrypt it(Easy)

ctpm として SECCON 2014 オンライン予選(en) に出ました。25位でした。

上記事の Decrypt it(Easy) を途中から一緒にやりつつ後を引き継いだのに、アホなミス('A')で取りこぼしたので、終了後に解き直したスクリプトを覚え書きとして残す。

なお、「Sage - Open-Source Mathematical Software System」を使っている。

#! /usr/bin/python
# -*- encoding: utf-8 -*-

from sage.all import *

def decode(target):
  if len(str(target)) % 2 == 0:
    print str(hex(target)).decode('hex')

for n,b,c in ([0xb8ae199365,0xffeee,0x8d5051562b],
    [0xb86e78c811, 0xfffee, 0x5ffa0ac1a2], [0x7bd4071e55, 0xfefef, 0x6008ddf867]):
  p,q = map( lambda x : x[0], factor(n) )

  for x in range(p):
    if (x*x + b*x - c) % p == 0:
      x_p = x
      #break
  for x in range(q):
    if (x*x + b*x - c) % q == 0:
      x_q = x
      #break

  decode( crt(x_p, x_q, p,q) )
  decode( crt(p-b-x_p, x_q, p,q) )
  decode( crt(p-b-x_p, q-b-x_q, p,q) )
  decode( crt(x_p, q-b-x_q, p,q) )
  print "-" * 16

実行結果は以下の通り

# sage -python solver.py
SECCO
aNｳq
    eh(
W_V"ｧ
----------------
2_5
N{Ra_
V
if
  ----------------
b1_N}
U4
｢
%・2
----------------

Rabin暗号は単射じゃないので一意ではない。意味ある文字は SECCON{Ra_b1_N} ですね。