λ nc misc.2019.chall.actf.co 19600 Welcome to the AlphaBeta interpreter! The flag is at the start of memory. You get one line: > cccCISccccCIScccCIYxSGSHaaCLgDLihhhDLDLgggDLTTGaaCLSGccbbbCLDLgggDLjggggDLSHDLTTGaaaCL Hello World!
なんかでた。理解を深めるため、命令を短くする。wikipedia の内容によるうと
L outputs a character to the screen
ということなので、最初に出現する L 以降を削除してみる。
λ nc misc.2019.chall.actf.co 19600 Welcome to the AlphaBeta interpreter! The flag is at the start of memory. You get one line: > cccCISccccCIScccCIYxSGSHaaCL H
予想通り、1文字だけ出力された。また、文字より数値を出力させた方がデバッグしやすいので
M outputs a number to the screen
の通り M を使う。また、レジスタ1,2は a, g でインクリメンタルできるらしい。
a adds 1 to register 1 g adds 1 to register 2
λ nc misc.2019.chall.actf.co 19600 Welcome to the AlphaBeta interpreter! The flag is at the start of memory. You get one line: > aM 0
λ nc misc.2019.chall.actf.co 19600 Welcome to the AlphaBeta interpreter! The flag is at the start of memory. You get one line: > gM 0⏎
全然変わらない。ということはレジスタ3が怪しい。
C sets register 3 to the value of register 1 D sets register 3 to the value of register 2
レジスタ3に値をセットするためには C か D を使えば良さそう。
λ nc misc.2019.chall.actf.co 19600 Welcome to the AlphaBeta interpreter! The flag is at the start of memory. You get one line: > aCM 1
G sets register 1 to the memory at the memory pointer S adds 1 to the register
が使えそうだとわかる。またフラグはメモリの先頭から始まっているらしいので
λ nc misc.2019.chall.actf.co 19600 Welcome to the AlphaBeta interpreter! The flag is at the start of memory. You get one line: > GCM 97
λ nc misc.2019.chall.actf.co 19600 Welcome to the AlphaBeta interpreter! The flag is at the start of memory. You get one line: > GCL a
λ nc misc.2019.chall.actf.co 19600 Welcome to the AlphaBeta interpreter! The flag is at the start of memory. You get one line: > GCLSGCL ac
解けそう。最後に適当に繰り返して終わり。
λ nc misc.2019.chall.actf.co 19600 Welcome to the AlphaBeta interpreter! The flag is at the start of memory. You get one line: > GCLSGCLSGCLSGCLSGCLSGCLSGCLSGCLSGCLSGCLSGCLSGCLSGCLSGCLSGCLSGCLSGCLSGCLSGCLSGCLSGCLSGCLSGCLSGCLSGCLSGCLSGCLSGCL actf{esolangs_sure_are_fun!}
λ curl https://controlyou.2019.chall.actf.co/ | grep actf % Total % Received % Xferd Average Speed Time Time Time Current Dload Upload Total Spent Left Speed 100 991 100 991 0 0 1256 0 --:--:-- --:--:-- --:--:-- 1257 if (flag.value === "actf{control_u_so_we_can't_control_you}") {
The first line of a PDF file shall be a header consisting of the 5 characters %PDF- followed by a version number of the form 1.N, where N is a digit between 0 and 7
λ qpdf --qdf blank_paper.pdf out.pdf WARNING: blank_paper.pdf: can't find PDF header qpdf: operation succeeded with warnings; resulting file may have some problems
p = 8337989838551614633430029371803892077156162494012474856684174381868510024755832450406936717727195184311114937042673575494843631977970586746618123352329889 q = 7755060911995462151580541927524289685569492828780752345560845093073545403776129013139174889414744570087561926915046519199304042166351530778365529171009493 e = 65537 c = 7022848098469230958320047471938217952907600532361296142412318653611729265921488278588086423574875352145477376594391159805651080223698576708934993951618464460109422377329972737876060167903857613763294932326619266281725900497427458047861973153012506595691389361443123047595975834017549312356282859235890330349
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}"
Wikipedia によると定義は以下の通り。E と D はそれぞれ Encryption と Decryption の頭文字。
$$
\begin{aligned}
E(x) & = (ax + b) \bmod m \\
D(x) & = a^{-1} (x-b) \bmod m
\end{aligned}
$$
それぞれの変数は以下の通り
変数名
意味
m
出現する文字の種類数 (アルファベットなら 26, 平仮名なら50, etc)
a
暗号化の鍵1, ただし a と m が互いに素 (最大公約数が1) になるように a を選ぶ
b
暗号化の鍵2
x
数値に変換した平文, 0 ~ m-1 のどれかと対応する
ここで \( a^{-1} \)は modular multiplicative inverse of a modulo m であり、以下の等式を満たす。
$$
\begin{aligned}
1 = a a^{-1} \bmod m
\end{aligned}
$$
ちゃんと復号できることの証明
法則名
等式
Identity
\( (a \bmod m) \bmod m = a \bmod m \)
Distributive
\( a+b \bmod m = ((a \bmod m) + (b \bmod m)) \bmod m \)
Distributive
\( ab \bmod m = ((a \bmod m) (b \bmod m)) \bmod m \)
証明
$$
\begin{aligned}
D(E(x)) & = a^{-1} (E(x) - b) \bmod m \\
& = a^{-1} (((ax + b) \bmod m) - b) \bmod m \\
& = ((a^{-1} \bmod m) ((((ax + b) \bmod m) - b) \bmod m)) \bmod m \\
& = ((a^{-1} \bmod m) (( (((ax + b) \bmod m) \bmod m) + (-b) \bmod m) \bmod m)) \bmod m \\
& = ((a^{-1} \bmod m) (( ((ax + b) \bmod m) + (-b) \bmod m) \bmod m)) \bmod m \\
& = ((a^{-1} \bmod m) (( ax + b - b) \bmod m)) \bmod m \\
& = ((a^{-1} \bmod m) (ax \bmod m)) \bmod m \\
& = a^{-1}ax \bmod m \\
& = (a^{-1}a \bmod m) (x \bmod m) \bmod m \\
& = (x \bmod m) \bmod m \\
& = x \bmod m \\
& = x
\end{aligned}
$$
シーザー暗号との関係
\(a=1\)の時はシーザー暗号になります。
具体例
具体例として大文字のアルファベット26文字を考えます。(m=26)
そのため、アルファベットと数の対応表は以下の通り。
平文 | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z —-| x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25
decryption :: Key -> Char -> Char decryption (a,b) c | c `elem` ['A'..'Z'] = substD e | otherwise = c where e = fromIntegral invA * (x-b) `mod` m m = 26 x = substE c (invA, _y, _v) = gcde (toInteger a) (toInteger m)
\(a=3, b=23\) の時に THE FLAG IS DIFF3RENTFROMTH3AFFINECIPH3R ってなってますね。大文字と小文字の両方に対応できるように改良します。
decryption :: Key -> Char -> Char decryption (a,b) c | c `elem` ['A'..'Z'] || c `elem` ['a'..'z'] = substD base e | otherwise = c where e = fromIntegral invA * (x-b) `mod` m m = 26 x = substE c (invA, _y, _v) = gcde (toInteger a) (toInteger m) base = if isUpper c then 'A'else 'a'
substE :: Char -> Int substE c = fromEnum c - fromEnum base where base = if isUpper c then 'A'else 'a'
substD :: Char -> Int-> Char substD base i = toEnum (i + fromEnum base)
crack :: Int -> String -> IO () crack a crypted = forM_ [0..25] $ \i -> do putStr $ show i <> ": " putStrLn $ map (decryption (a, i)) crypted
> map (decryption (3,23)) "Csj mexp vz gvmM3wjkCMwnHCs3XmMvkjDvQs3w" "The flag is difF3renTFroMTh3AfFineCiPh3r"
$ nc 13.234.130.76 7002 bash: cannot set terminal process group (1): Not a tty bash: no job control in this shell bash-4.4$ ls ls bash: LS: command not found bash-4.4$ pwd pwd bash: PWD: command not found
一瞬、CAPSLOCK がバグったのかと思ったけど、そうではなくこれが問題だった。
入力した文字が全て大文字として解釈されるため、コマンドが何も実行できないという感じ。
ちょっと調べたら ${v,,} で小文字にできることがわかったので、あとは簡単だった。
bash-4.4$ l="ls /" bash-4.4$ ${l,,} ${l,,} bin etc jail media opt root sbin sys usr dev home lib mnt proc run srv tmp var
bash-4.4$ l="bash"; ${l,,} l="bash"; ${l,,} bash: cannot set terminal process group (1): Not a tty bash: no job control in this shell bash: /root/.bashrc: Permission denied
