hack the box ~魔法使いへの道~ (その10) 【Walkthrough】Weak RSA II

htb

はじめに

ホワイトハッカーを目指したエンジニアの活動記録です.
セキュリティ関連の知識ゼロですが,奮闘していきます.

前回の記事はこちら,Find The Easy Passを攻略しました*1

hack the box ~魔法使いへの道~ (その8) 【Walkthrough】Find The Easy Pass
ホワイトハッカーを目指したエンジニアの活動記録です. セキュリティ関連の知識ゼロですが,奮闘していきます. 今回はBeginner TrackのFind The Easy Passをこちらの記事*1を参考に攻略していきたいと思います.

今回はBeginner TrackのWeak RSAをRSAの仕組みに踏み込んでこちらの記事*2を参考に攻略していきたいと思います.

file

RSA暗号の暗号化

RSA暗号で文章M を暗号化するには下記の式で暗号文C を作成します*3

C \equiv M^{e} \ ( \ mod \ \ n)

enは公開鍵です.

ここで,Weak RSAの値を確認してみます.
Modulusがn,Exponentがeに該当します.

┌──(maki㉿kali)-[~/Downloads/Weak RSA/RsaCtfTool-master/RsaCtfTool-master]
└─$ openssl rsa -pubin -inform PEM -text -noout < key.pub
RSA Public-Key: (1026 bit)
Modulus:
    03:30:3b:79:0f:b1:49:da:34:06:d4:95:ab:9b:9f:
    b8:a9:e2:93:44:5e:3b:d4:3b:18:ef:2f:05:21:b7:
    26:eb:e8:d8:38:ba:77:4b:b5:24:0f:08:f7:fb:ca:
    0a:14:2a:1d:4a:61:ea:97:32:94:e6:84:a8:d1:a2:
    cd:f1:8a:84:f2:db:70:99:b8:e9:77:58:8b:0b:89:
    12:92:55:8c:aa:05:cf:5d:f2:bc:63:34:c5:ee:50:
    83:a2:34:ed:fc:79:a9:5c:47:8a:78:e3:37:c7:23:
    ae:88:34:fb:8a:99:31:b7:45:03:ff:ea:9e:61:bf:
    53:d8:71:69:84:ac:47:83:7b
Exponent:
    61:17:c6:04:48:b1:39:45:1a:b5:b6:0b:62:57:a1:
    2b:da:90:c0:96:0f:ad:1e:00:7d:16:d8:fa:43:aa:
    5a:aa:38:50:fc:24:0e:54:14:ad:2b:a1:09:0e:8e:
    12:d6:49:5b:bc:73:a0:cb:a5:62:50:42:55:c7:3e:
    a3:fb:d3:6a:88:83:f8:31:da:8d:1b:9b:81:33:ac:
    21:09:e2:06:28:e8:0c:7e:53:ba:ba:4c:e5:a1:42:
    98:81:1e:70:b4:a2:31:3c:91:4a:2a:32:17:c0:2e:
    95:1a:ae:e4:c9:eb:39:a3:f0:80:35:7b:53:3a:6c:
    ca:95:17:cb:2b:95:bf:cd

16進数表記なので

Modulus
03303b790fb149da3406d495ab9b9fb8a9e293445e3bd43b18ef2f0521b726ebe8d838ba774bb5240f08f7fbca0a142a1d4a61ea973294e684a8d1a2cdf18a84f2db7099b8e977588b0b891292558caa05cf5df2bc6334c5ee5083a234edfc79a95c478a78e337c723ae8834fb8a9931b74503ffea9e61bf53d8716984ac47837b

Exponent
6117c60448b139451ab5b60b6257a12bda90c0960fad1e007d16d8fa43aa5aaa3850fc240e5414ad2ba1090e8e12d6495bbc73a0cba562504255c73ea3fbd36a8883f831da8d1b9b8133ac2109e20628e80c7e53baba4ce5a14298811e70b4a2313c914a2a3217c02e951aaee4c9eb39a3f080357b533a6cca9517cb2b95bfcd

これをサイト*4を使って10進数に変換します.

Modulus
573177824579630911668469272712547865443556654086190104722795509756891670023259031275433509121481030331598569379383505928315495462888788593695945321417676298471525243254143375622365552296949413920679290535717172319562064308937342567483690486592868352763021360051776130919666984258847567032959931761686072492923

Exponent
68180928631284147212820507192605734632035524131139938618069575375591806315288775310503696874509130847529572462608728019290710149661300246138036579342079580434777344111245495187927881132138357958744974243365962204835089753987667395511682829391276714359582055290140617797814443530797154040685978229936907206605

RSA暗号の解読

暗号文Cを受け取った人が解読するには,秘密鍵である自分しか持っていない(p,q,d)という3つの秘密の数字の組み合わせが必要になります.
ここで、dp, q(それぞれ素数)と,公開鍵dに対して,以下の条件が成り立つようになっています.

e \cdot d \equiv 1 \ ( \ mod \ \ (p-1)(q-1))

上記の条件を満たす「d」と,公開鍵の「n」を以下の式に沿って計算すると,暗号文Cを解読し元の文章M'を複合することができます.

M' \equiv C^d \ ( \ mod \ \ n)

p,qの算出

こちらのサイト*5を使って因数を算出します.

p=20423438101489158688419303567277343858734758547418158024698288475832952556286241362315755217906372987360487170945062468605428809604025093949866146482515539

q=28064707897434668850640509471577294090270496538072109622258544167653888581330848582140666982973481448008792075646342219560082338772652988896389532152684857

dの算出

上記の式を変形する.modの定義からe \cdot d -1(p-1)(q-1)で割り切れるとみなせるので

e \cdot d -1 = (p-1)(q-1)x

ここでxは適当な任意の数である.

移項して

 1 = e \cdot d + (-(p-1)(q-1))x

このようになる.

ここで,下記のようなプログラムを作成し

print("----- calc d -----")

p=20423438101489158688419303567277343858734758547418158024698288475832952556286241362315755217906372987360487170945062468605428809604025093949866146482515539
print("p")
print(p)

q=28064707897434668850640509471577294090270496538072109622258544167653888581330848582140666982973481448008792075646342219560082338772652988896389532152684857
print("q")
print(q)

e=68180928631284147212820507192605734632035524131139938618069575375591806315288775310503696874509130847529572462608728019290710149661300246138036579342079580434777344111245495187927881132138357958744974243365962204835089753987667395511682829391276714359582055290140617797814443530797154040685978229936907206605
print("e")
print(e)

d = xgcd(e, (p-1) * (q-1))
print("d")
print(d)

このプログラムを実行して解く.

┌──(maki㉿kali)-[~/Downloads/Weak RSA/RsaCtfTool-master/RsaCtfTool-master]
└─$ sage
┌────────────────────────────────────────────────────────────────────┐
│ SageMath version 9.5, Release Date: 2022-01-30                     │
│ Using Python 3.10.4. Type "help()" for help.                       │
└────────────────────────────────────────────────────────────────────┘

sage: load ("calc.sage")
----- calc d -----
p
20423438101489158688419303567277343858734758547418158024698288475832952556286241362315755217906372987360487170945062468605428809604025093949866146482515539
q
28064707897434668850640509471577294090270496538072109622258544167653888581330848582140666982973481448008792075646342219560082338772652988896389532152684857
e
68180928631284147212820507192605734632035524131139938618069575375591806315288775310503696874509130847529572462608728019290710149661300246138036579342079580434777344111245495187927881132138357958744974243365962204835089753987667395511682829391276714359582055290140617797814443530797154040685978229936907206605
d
(1, 44217944188473654528518593968293401521897205851340809945591908757815783834933, -5259834501007605609644411402251788782440829565443302749773174465275676170713)
sage: 

これにより,

 1 = e \cdot 442179... + (-(p-1)(q-1))\cdot(-525983...)

となるので

d=44217944188473654528518593968293401521897205851340809945591908757815783834933

と分かる.

M'の算出

下記のようなプログラムを作成し

#!/usr/bin/env python3 

d=44217944188473654528518593968293401521897205851340809945591908757815783834933

p=20423438101489158688419303567277343858734758547418158024698288475832952556286241362315755217906372987360487170945062468605428809604025093949866146482515539

q=28064707897434668850640509471577294090270496538072109622258544167653888581330848582140666982973481448008792075646342219560082338772652988896389532152684857

n = p*q

with open("flag.enc", "rb") as f:
    flag = f.read()

flag = int.from_bytes(flag, byteorder="big")
flag = pow(flag, d, n)

print("flag-hex=")
print(flag)

numBytes = len(hex(flag)[2:]) // 2 + 1
flag = flag.to_bytes(numBytes, byteorder="big").decode('utf-8', errors='ignore')

print("flag=")
print(flag)

このプログラムを実行して解く.

┌──(maki㉿kali)-[~/Downloads/Weak RSA/RsaCtfTool-master/RsaCtfTool-master]
└─$ python flag_calc.py
flag-hex=
1497194306832430076266314478305730170974165912795150306640063107539292495904192020114449824357438113183764256783752233913408135242464239912689425668318419718061442061010640167802145162377597484106658670422900749326253337728846324798012274989739031662527650589811318528908253458824763561374522387177140349821
flag=
!ϲo@gX{Dn(Dx".,-)!6WQ+L~J9{_SDYCߚ▒4LU
                                     p/AHTB{s1mpl************}

おわりに

前回か既存のツールを使用して簡単に解析しましたが,今回はRSA暗号の仕組みに踏み込んで見ていきました.久しぶりの式変形などでいろいろと大変でしたがなんとか導くことができました.
次回からも奮っていきたいと思います.

参考サイト

1 :hack the box ~魔法使いへの道~ (その9) 【Walkthrough】Weak RSA
2 :Hack The Box: Weak RSA
3 :わかった気になれる『サマーウォーズ』の暗号 「RSA暗号」を解説
4 :2進数、8進数、10進数、16進数相互変換ツール
*5 :factordb

コメント

タイトルとURLをコピーしました