tips

gmpy2のインストールに失敗した．

gmpy2は，GMPのPython用のラッパーである．
GMPは，非常に大きな数を計算するのに役に立つライブラリである．
gmpy2を使えば，百桁以上の整数に対しても√の計算を行ったりすることができる．

pipでインストールしようとしたらエラーが出た．

$ pip install gmpy2
(...)
    In file included from src/gmpy2.c:426:
    src/gmpy.h:252:12: fatal error: 'mpfr.h' file not found
    #  include "mpfr.h"
               ^~~~~~~~
    1 error generated.
    error: command 'clang' failed with exit status 1
    
    ----------------------------------------
(...)

どうやら依存関係にあるライブラリが足りないらしい．
このサイトを参考に以下を実行．

brew install mpfr mpc libmpc
pip install gmpy2

正常にインストールすることができた．

CpawCTF

Q29.[Crypto] Common World

どうやらRSA暗号を解く問題らしいが，現実的な時間で解けないから今でも使われているのでは．．．
と，どうしていいかわからず，調べた．

公開鍵暗号 RSA - Common Modulus Attack, 秘密鍵からの素因数分解

限定的な状況であればこれを解く方法はいくつかあるらしく，本問はその1つに該当する．
Common Modulus Attackが適用できる条件は以下の通り．

ある平文に対して公開鍵(e1, n), (e2, n)と暗号文c1, c2が渡されている．
e1とe2は互いに素である．

この復号方法を実装している例を発見したので，利用させてもらった．

また，今回のフラグには意味があるらしく，暗号数字 1から5で検索したらポリュビオスの暗号表というものを見つけた．
1から5までの数字の組で1つのアルファベットを表す．

Pythonでこれを解いてみる．

import sys

TABLE = {
    '1': {'1': 'A', '2': 'B', '3': 'C', '4': 'D', '5': 'E'},
    '2': {'1': 'F', '2': 'G', '3': 'H', '4': '(I,J)', '5': 'K'},
    '3': {'1': 'L', '2': 'M', '3': 'N', '4': 'O', '5': 'P'},
    '4': {'1': 'Q', '2': 'R', '3': 'S', '4': 'T', '5': 'U'},
    '5': {'1': 'V', '2': 'W', '3': 'X', '4': 'Y', '5': 'Z'},
}


def conv_polybius(text):
    ret = ''
    for i in range(0, len(text), 2):
       ret += TABLE[text[i]][text[i+1]]
    return ret


if __name__ == '__main__':
    text = sys.argv[1]
    ans = conv_polybius(text)
    print(ans)

これで2019年4月27日現在で掲載されているすべての問題を解き終えた．
CpawCTF2もあるので，次はこちらに挑戦する．