Really Secure Algorithm (ångstromCTF 2019)

2019-04-25 Comments crypto

解説

really_secure_algorithm.txt の内容は以下の通り。

p = 8337989838551614633430029371803892077156162494012474856684174381868510024755832450406936717727195184311114937042673575494843631977970586746618123352329889
q = 7755060911995462151580541927524289685569492828780752345560845093073545403776129013139174889414744570087561926915046519199304042166351530778365529171009493
e = 65537
c = 7022848098469230958320047471938217952907600532361296142412318653611729265921488278588086423574875352145477376594391159805651080223698576708934993951618464460109422377329972737876060167903857613763294932326619266281725900497427458047861973153012506595691389361443123047595975834017549312356282859235890330349

RSA 暗号の p, q が与えられている問題なので、すぐに解ける。

過去に同じような問題をやったことがあったので、その時のコードを流用。

import Crypto.PubKey.RSA
import Crypto.Number.ModArithmetic
import Crypto.Number.Serialize

import Data.Text
import Data.Text.Encoding

solve :: Integer -> Integer -> Integer -> Integer -> Text
solve p q e c = toDisplay $ expSafe c d n
  where
    n = p * q
    d = case generateWith (p,q) 0 e of
      Nothing -> error "generateWith error"
      Just (_pubKey, privateKey) -> private_d privateKey

toDisplay :: Integer -> Text
toDisplay = decodeUtf8 . i2osp

試してみます。

> p = 8337989838551614633430029371803892077156162494012474856684174381868510024755832450406936717727195184311114937042673575494843631977970586746618123352329889
> q = 7755060911995462151580541927524289685569492828780752345560845093073545403776129013139174889414744570087561926915046519199304042166351530778365529171009493
> e = 65537
> c = 7022848098469230958320047471938217952907600532361296142412318653611729265921488278588086423574875352145477376594391159805651080223698576708934993951618464460109422377329972737876060167903857613763294932326619266281725900497427458047861973153012506595691389361443123047595975834017549312356282859235890330349
> solve p q e c
"actf{really_securent_algorithm}"

フラグ

actf{really_securent_algorithm}

#CTF #ångstromCTF 2019