はじめに
RSAは，公開鍵暗号方式の代表的なアルゴリズムの1つです．このアルゴリズムは，非常に強力なセキュリティを提供するため，現代の通信や暗号化の分野でよく使用されています．しかし，RSAにも弱点があり，それを攻略することができます．この記事では，htb(hack the box)のWeak RSAを攻略していきます．
魔法使いへの道とは
RSA攻略は，ウィザード級ハッカーになるための重要なスキルの1つです．しかし，RSA攻略には，高度な数学的な知識が必要です．例えば，素因数分解問題を解決するためには，数論の知識が必要です．
RSAとは何ですか？
RSAは，公開鍵暗号方式の一種であり，鍵の生成，暗号化，復号に公開鍵と秘密鍵の2つの鍵を使用します．RSAは，非常に大きな数の素因数分解問題を解くことが困難であるという数学的な問題を利用しています．RSAは，1983年にロナルド・リベスト，アディ・シャミア，レナード・アデルマンによって発明されました．
RSAは，公開鍵と秘密鍵を使用して暗号化と復号を行います．公開鍵は，誰でも使用できる鍵であり，秘密鍵は，所有者しか使用できない鍵です．通信者Aが通信者Bにメッセージを送信する場合，AはBの公開鍵を使用してメッセージを暗号化します．Bは自分の秘密鍵を使用してメッセージを復号します．
Weak RSAとは何ですか？
RSAは，非常に大きな素数pとqを使用して暗号化鍵を生成するため，暗号鍵の生成には多大な計算リソースが必要です．しかし，弱い素数を使用することで，暗号化されたメッセージを容易に解読できる可能性があります．このように，弱いRSAを攻略することができます．
RSA攻撃に使用されるツール
RSA攻撃には，いくつかのツールが使用されます．例えば，RsaCtfToolは，暗号化されたメッセージを解読するために使用されるツールの1つです．また，OpenSSL RSAコマンドを使用して，RSA鍵の生成，暗号化，復号を行うこともできます．SageMathは，RSAのような数学的な問題を解決するために使用される数学ソフトウェアの1つです．
Hack The Box
Hack The Boxは，ウェブアプリケーション，ネットワーク，ペネトレーションテストなど，さまざまなセキュリティ関連のチャレンジを提供するプラットフォームです．Hack The Boxを使用して，RSA攻撃の練習を行うことができます．
前回の攻略
前回ではRsaCtfToolを使用して，Weak RSAを攻略する方法を学びました
今回はRSAの暗号化などを理解しながら攻略していきます．
Weak RSAの攻略
RSA暗号の暗号化
RSA暗号で文章M を暗号化するには下記の式で暗号文C を作成します．
C \equiv M^{e} \ ( \ mod \ \ n)e と nは公開鍵です．
ここで，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:
ぜんk内k内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:cd16進数表記なので
Modulus
03303b790fb149da3406d495ab9b9fb8a9e293445e3bd43b18ef2f0521b726ebe8d838ba774bb5240f08f7fbca0a142a1d4a61ea973294e684a8d1a2cdf18a84f2db7099b8e977588b0b891292558caa05cf5df2bc6334c5ee5083a234edfc79a95c478a78e337c723ae8834fb8a9931b74503ffea9e61bf53d8716984ac47837b
Exponent
6117c60448b139451ab5b60b6257a12bda90c0960fad1e007d16d8fa43aa5aaa3850fc240e5414ad2ba1090e8e12d6495bbc73a0cba562504255c73ea3fbd36a8883f831da8d1b9b8133ac2109e20628e80c7e53baba4ce5a14298811e70b4a2313c914a2a3217c02e951aaee4c9eb39a3f080357b533a6cca9517cb2b95bfcdこれをサイトを使って10進数に変換します．
Modulus
573177824579630911668469272712547865443556654086190104722795509756891670023259031275433509121481030331598569379383505928315495462888788593695945321417676298471525243254143375622365552296949413920679290535717172319562064308937342567483690486592868352763021360051776130919666984258847567032959931761686072492923
Exponent
68180928631284147212820507192605734632035524131139938618069575375591806315288775310503696874509130847529572462608728019290710149661300246138036579342079580434777344111245495187927881132138357958744974243365962204835089753987667395511682829391276714359582055290140617797814443530797154040685978229936907206605RSA暗号の解読
暗号文Cを受け取った人が解読するには，秘密鍵である自分しか持っていない（p,q,d)という3つの秘密の数字の組み合わせが必要になります．
ここで，dはp, 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=28064707897434668850640509471577294090270496538072109622258544167653888581330848582140666982973481448008792075646342219560082338772652988896389532152684857dの算出
上記の式を変形する．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暗号の仕組みに踏み込んで見ていきました．久しぶりの式変形などでいろいろと大変でしたがなんとか導くことができました．
次回からも奮っていきたいと思います．
コメント