htb (その10) Weak RSA II 【Walkthrough】 ~魔道~

魔法使いへの道

はじめに

RSAは，公開鍵暗号方式の代表的なアルゴリズムの1つです．このアルゴリズムは，非常に強力なセキュリティを提供するため，現代の通信や暗号化の分野でよく使用されています．しかし，RSAにも弱点があり，それを攻略することができます．この記事では，htb(hack the box)のWeak RSAを攻略していきます．

魔法使いへの道とは

http://hamaruki.xmagix.com/the-road-to-wizard-hacker/

RSA攻略は，ウィザード級ハッカーになるための重要なスキルの1つです．しかし，RSA攻略には，高度な数学的な知識が必要です．例えば，素因数分解問題を解決するためには，数論の知識が必要です．

RSAとは何ですか？

RSAは，公開鍵暗号方式の一種であり，鍵の生成，暗号化，復号に公開鍵と秘密鍵の2つの鍵を使用します．RSAは，非常に大きな数の素因数分解問題を解くことが困難であるという数学的な問題を利用しています．RSAは，1983年にロナルド・リベスト，アディ・シャミア，レナード・アデルマンによって発明されました．

RSAは，公開鍵と秘密鍵を使用して暗号化と復号を行います．公開鍵は，誰でも使用できる鍵であり，秘密鍵は，所有者しか使用できない鍵です．通信者Aが通信者Bにメッセージを送信する場合，AはBの公開鍵を使用してメッセージを暗号化します．Bは自分の秘密鍵を使用してメッセージを復号します．

http://hamaruki.xmagix.com/what-is-rsa-beginners-can-understand/

Weak RSAとは何ですか？

RSAは，非常に大きな素数pとqを使用して暗号化鍵を生成するため，暗号鍵の生成には多大な計算リソースが必要です．しかし，弱い素数を使用することで，暗号化されたメッセージを容易に解読できる可能性があります．このように，弱いRSAを攻略することができます．

http://hamaruki.xmagix.com/what-is-weak-rsa/

RSA攻撃に使用されるツール

RSA攻撃には，いくつかのツールが使用されます．例えば，RsaCtfToolは，暗号化されたメッセージを解読するために使用されるツールの1つです．また，OpenSSL RSAコマンドを使用して，RSA鍵の生成，暗号化，復号を行うこともできます．SageMathは，RSAのような数学的な問題を解決するために使用される数学ソフトウェアの1つです．

http://hamaruki.xmagix.com/what-is-rsa-ctf-tool/

Hack The Box

Hack The Boxは，ウェブアプリケーション，ネットワーク，ペネトレーションテストなど，さまざまなセキュリティ関連のチャレンジを提供するプラットフォームです．Hack The Boxを使用して，RSA攻撃の練習を行うことができます．

前回の攻略

前回ではRsaCtfToolを使用して，Weak RSAを攻略する方法を学びました

http://hamaruki.xmagix.com/hack-the-box-walkthrough-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:cd

16進数表記なので

Modulus
03303b790fb149da3406d495ab9b9fb8a9e293445e3bd43b18ef2f0521b726ebe8d838ba774bb5240f08f7fbca0a142a1d4a61ea973294e684a8d1a2cdf18a84f2db7099b8e977588b0b891292558caa05cf5df2bc6334c5ee5083a234edfc79a95c478a78e337c723ae8834fb8a9931b74503ffea9e61bf53d8716984ac47837b

Exponent
6117c60448b139451ab5b60b6257a12bda90c0960fad1e007d16d8fa43aa5aaa3850fc240e5414ad2ba1090e8e12d6495bbc73a0cba562504255c73ea3fbd36a8883f831da8d1b9b8133ac2109e20628e80c7e53baba4ce5a14298811e70b4a2313c914a2a3217c02e951aaee4c9eb39a3f080357b533a6cca9517cb2b95bfcd

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

https://hogehoge.tk/tool/number.html

Modulus
573177824579630911668469272712547865443556654086190104722795509756891670023259031275433509121481030331598569379383505928315495462888788593695945321417676298471525243254143375622365552296949413920679290535717172319562064308937342567483690486592868352763021360051776130919666984258847567032959931761686072492923

Exponent
68180928631284147212820507192605734632035524131139938618069575375591806315288775310503696874509130847529572462608728019290710149661300246138036579342079580434777344111245495187927881132138357958744974243365962204835089753987667395511682829391276714359582055290140617797814443530797154040685978229936907206605

RSA暗号の解読

暗号文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=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暗号の仕組みに踏み込んで見ていきました．久しぶりの式変形などでいろいろと大変でしたがなんとか導くことができました．
次回からも奮っていきたいと思います．

FAQs

  • Q1. RSAはどのような暗号方式ですか？
    A1. RSAは、非常に強力な公開鍵暗号方式であり、暗号化と復号のために異なる鍵を使用します。RSAは、非常に大きな素数を使用して鍵を生成するため、暗号化されたメッセージを解読することは非常に困難です。
  • Q2. RSA攻撃に必要なスキルは何ですか？
    A2. RSA攻撃には、高度な数学的な知識が必要です。素因数分解問題を解決するためには、数論の知識が必要です。また、暗号化されたメッセージを解読するためには、コンピュータサイエンスの知識が必要です。
  • Q3. RSA攻撃を行うために必要なツールは何ですか？
    A3. RSA攻撃には、いくつかのツールが使用されます。例えば、RsaCtfTool、OpenSSL RSAコマンド、SageMathなどがあります。
  • Q4. RSA攻撃を防ぐためには、どのような方法がありますか？
    A4. RSA攻撃を防ぐためには、強力な鍵を使用することが重要です。また、安全なランダム数生成器を使用し、鍵生成時には十分な長さの素数を使用することも重要です。
  • Q5. RSA攻撃は、どのような場面で使用されることがありますか？
    A5. RSA攻撃は、セキュリティのテストやペネトレーションテストなど、セキュリティ関連の分野で使用されることがあります。また、不正アクセスや盗聴などの犯罪行為にも使用される可能性があります。

コメント

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