🔑

【HackTheBox Crypto Challenge】Brainy's Cipher Writeup

2023/07/31に公開

Security

About This Challenge

challenge description

Brainy likes playing around with esoteric programming. 
He also likes math and has therefore encrypted his very secure password with a popular encryption algorithm. 
Claiming that his password cannot be retrieved now, he has sent the ciphertext to some of his friends. 
Can you prove to Brainy that his password can actually be recovered?

難解プログラミング言語（esoteric programming）が好きなBrainyが自分の暗号化したパスワードを友達に送った、そのパスワードを復号してみよう、みたいなことが書いてあります。

提供されたのはこのbrainy.txtだけです。

brainy.txt

++++++++++[>+>+++>+++++++>++++++++++<<<<-]>>>>+++++++++++++++++++++++.-----------.<------------.---.++.---------.+.++.-.++.+.-----.++..++++.--.++++.+..-------.+.+++.---.+.+++++.-------.+.---.+++++++.+.-------..+++.-.+++++.-------.++.+++++.-----.+++++..-----.--.++++++++.-------.--.++++.+++.---.++..+++.------.+++.--.-..++++++.-.----..+++++.------.++++++.---.---.--.+++.++++.-------.+++++..-.++..-------.++++++.---.++..+++.----.++++.-------.++++++++..----.+++.+.------.--.-.++.-.+++++.--..--.++++.-.++++.---.------.+++++.++.+.---.+++.---.----.++++.--.+++.-----.+++++.+.---.--.+++++++.---.---...---.+.++++++++.----.++++.-----.++.--.-.--.++.-.-.+++++.--..+++++.-------.-.++++.++.-----.++++++.--------.+++.+++.-.+++.----.----.++++++.----.++++++.-------.-----.>+.<++++++++++++++.---------.+.++++++.--------.++.+++++++.--------.+++++++.----.+.----.+++...----.++++..++.----..+++.+++.-----.++++.--.++..-------.+++.++++.--.---.--.++++++..-----..+++++++.-------.+++++++.--------..++++++.++.--..++.----.+++.++.------.++++.+.-..+.+.-------.++++++.-.---.---.-.++++++++..-----.---.++.+.++..-.--.+++.++++.--..------.++++++++.-------.+++++++..---.+.++..---.----.+.++++++..-.-.-----.--.++++.--.+++++++.----.++++.-----.-.+.++.+..+..--.-.---.+++++.--.--.++++++.--------.++.---.+++++++..----.---.+++++++++.-...-------.++++++++.-------.++.-.+++++.----.-.+++++.---.----.+++++.++.-----.---.+++++++.++.---------...++.+++++++.------.+++++.-------.++++.-----.+++++.----.-----.>-------------.++++++++++++.<++++++++++++++.-----..-.----.++++++.-..-----.++.++++++.--.----..--.++.-.++++++++.------.+..--.+++++++.------.---.++++++.----.++++++.-.++.------.++++...--.---.+++++++.--------.++++++++.----..+.----.+..---.++++++++.+.---.-.---.--.++++++++.-----.+++++.----.+.+++.------.--..+++++++++.-.---.++.----.++++.-.------.+++++.--.++.+++.-----.++.++.--..----.-.+++++++.+.----.---.+++++.+++.---.-----.+++++.------.++++++.-.----..++.+++.--.---.++.++++++.--------..+++++.+++.---.-----.++.++++++.---.+++.-.-------.++.+++.-.---.+++.---.+.++.-----.+++++++.---.--.-..++++.++.-------.++++.+.--.++++..+.+.-.---.-.--.+.+++++.--.+++.------..--.++++++++.-.------.++++.+++.-----.+.----.-----.>------------.+++++++++++++.<++++++++++++++.-.---------.++++++..++.+.--.----.-.--.+++.---.++++++++..-----.+.--.--.++++++.+++.----.---.+.++.++++.------.++++++..--.----.++++..---.+++.----.--..++++++++.-.-----..---.+++++++++.---------.++++++.----.+++++.-.--.---.++++++.+.+.---------.++++++.----.++++.+++.-----.+++.--.+++.----.+++.------.++++++.----.++++++.---..------.+++++++.----.++.+.+.++.-..-------.++++++.-------.++++.---.++++.+++.-----.++++++..----.-.+++++..---.---.-..+.--.+++.---.++++.++.---.-.+++++.-..-------.++..+++.++++.----.---.++.+++++.--------.++++.+.------..+++++.---.++++++.-.------.+++.++.--.---.++.+++.-----.+++++.---.+.--.-.+++++++.+.-------.--.+++++.-----..+++++.++.---.+++++.-.--.-.----.-----.>--------------.<++++++++++++++.----.----.--.+++++++.+.--------.++++++++.--..+..---.---.+++++..++.--.++.--.+.------.+++++++.-----.+++++.---.++.++.----.++.----.++.-----.+++..+++++.-----.--.+++...++.----.++++++.--------.+++++++++.--------.+.++++.+.----..++++++.-------.++..++++.--------.++++++.-.-----.++.++++.++.---.-----.++.-.+.++++.++.---.--.-.++++.-..----..+++++++.-----.++++++.---.----.--.+++++.+.--.+++++.----.++++.---.--.+.++.++.--.+.------.+.-.+++.--.---.++.--.++++++++.------.--.+++++.-.-.++++++.------.++++++.------..+++.++.------..++++.-.++..-----.++++++.--------.++.+++++.--.-----.++++++++..-.-----.+++++++.------.+++.------.++.++.-.-.+++.----.+.+++++++.---.+.++..-----.++++.--------.+++++..-.+++++..---.-.-----.++.--.+++++++++.--------.+++++.+++.----.--.+++.--..++.---.++.++++.---.-.++++.--------.+++++..------.+++++++.++.-------.+++.--..++.+.---.++++++.---------.++.+++++.--.++.++.--------.+++++++.-.---.-.++.----.+++++++.--------.++++++.------.+++++++.---.+++.--.++++.---.---..-..++.++.-.-.---.++++++..--.+++.+.----.++++.---------..++.+.+++++.---.-.+.----.+++++++.--.---.--.+..-.-.++++++.--.++++.-.+.-----.+.+++.+.----.++.++..--------.++.+++++++.--------.+++++.+..-----.--.+.++++++.--.----.+.++++++.--------.++++++++.------.--.++++++...+.-------.+++++++++.-----.+.+.----.+++.-----.++++++.+.+.--------.+++.+++++.-------.+.+++++++.--.-------.++++++++.-.------.>++++++++++++++++++++++++++.

これはBrainfuckのコードですね。確かにesolangと言えばこれですよね、、？
https://ja.wikipedia.org/wiki/Brainfuck

Investigation

何も読めないので、オンラインのInterpreterを入れて実行してみます。https://www.dcode.fr/brainfuck-language
こんな情報が入っていました。

実行結果

p:7901324502264899236349230781143813838831920474669364339844939631481665770635584819958931021644265960578585153616742963330195946431321644921572803658406281,
q:12802918451444044622583757703752066118180068668479378778928741088302355425977192996799623998720429594346778865275391307730988819243843851683079000293815051,
dp:5540655028622021934429306287937775291955623308965208384582009857376053583575510784169616065113641391169613969813652523507421157045377898542386933198269451,
dq:9066897320308834206952359399737747311983309062764178906269475847173966073567988170415839954996322314157438770225952491560052871464136163421892050057498651,
c:62078086677416686867183857957350338314446280912673392448065026850212685326551183962056495964579782325302082054393933682265772802750887293602432512967994805549965020916953644635965916607925335639027579187435180607475963322465417758959002385451863122106487834784688029167720175128082066670945625067803812970871

p、qがあるので、暗号化の仕組みはRSAですね。
また、dp、dpがあるので、これはChinese Remainder Theorem （CRT、中国剰余定理）を使ったRSAっぽいです。最後のcは暗号化されたパスワードでしょう。

復号に使う情報は揃っているので、コードを書いていきます。

RSA with Chinese Remainder Theorem

なぜCRTを使うのか

通常のRSAの復号は、 $M \equiv C^d\ mod\ n$ で計算しますが、秘密鍵 $d$ が大きいのでこの計算がそれなりに重いです。CRTを使うと復号の計算量を下げることができます。
一言でいうと、RSAの復号を高速化するための手法です。

数式

あまり詳しくないけどCRTを使ったRSAの復号を数式で書いてみます。 $M$ は平文、 $C$ は暗号文の意味です。

まずは計算に使う $d_p$ と $d_q$ を計算します。 $p$ と $q$ はRSA公開鍵の生成に使う素数です。

d_p \equiv d\ mod\ (p-1)\\ d_q \equiv d\ mod\ (q-1)

次は暗号文 $C$ をこうやって $m_1$ と $m_2$ にします。

m_1 \equiv C^{d_p}\ mod\ p\\ m_2 \equiv C^{d_q}\ mod\ q

復号の時に使うcoefficientも計算します。なんか本のnotationがバラバラなので、 $u$ と $v$ にします。

u \equiv q^{-1}\ mod\ p\\ v \equiv p^{-1}\ mod\ q

$m_1$ と $m_2$ を次の計算で平文 $M$ に復号できます。 $n=pq$ です。

M \equiv (q \cdot u \cdot m_1 + p \cdot v \cdot m_2)\ mod\ n

数式はこの教科書の内容を参考にしています（7.5.2 Fast Decryption with the Chinese Remainder Theorem）。https://www.crypto-textbook.com/

コード

復号のコードです。

solution.py

p=7901324502264899236349230781143813838831920474669364339844939631481665770635584819958931021644265960578585153616742963330195946431321644921572803658406281
q=12802918451444044622583757703752066118180068668479378778928741088302355425977192996799623998720429594346778865275391307730988819243843851683079000293815051
dp=5540655028622021934429306287937775291955623308965208384582009857376053583575510784169616065113641391169613969813652523507421157045377898542386933198269451
dq=9066897320308834206952359399737747311983309062764178906269475847173966073567988170415839954996322314157438770225952491560052871464136163421892050057498651
c=62078086677416686867183857957350338314446280912673392448065026850212685326551183962056495964579782325302082054393933682265772802750887293602432512967994805549965020916953644635965916607925335639027579187435180607475963322465417758959002385451863122106487834784688029167720175128082066670945625067803812970871


m1 = pow(c, dp, p)
m2 = pow(c, dq, q)

u = pow(q, -1, p)
v = pow(p, -1, q)

M = (q*u*m1 + p*v*m2 ) % (p*q)

# remove 0x
bytes.fromhex(hex(M)[2:])

出力にフラグがありました！

実行結果

ch1nxxxxxxxxxxxxxxxxxxxxx_9792

memo

cryptographyはこれで勉強していました。

このコースの内容を把握できればhtbのcrypto challengeだいたい解ける気がします。9年前の動画ですが、教授の説明がわかりやすし、話し方も面白くておすすめです。