[HackTheBox] brevi moduli Walkthrough

はじめに

HackTheBox Challenge Crypto VeryEasy
brevi moduliのWalkthroughです。
自環境へのsageインストールが面倒臭くなり、インストール不要でできる方法をメモしたものです。

Challenge Description

On a cold Halloween night, five adventurers gathered at the entrance of an ancient crypt. The Cryptkeeper appeared from the shadows, his voice a chilling whisper: "Five locks guard the treasure inside. Crack them, and the crypt is yours." One by one, they unlocked the crypt's secrets, but as the final door creaked open, the Cryptkeeper's eerie laughter filled the air. "Beware, for not all who enter leave unchanged."

WalkThrough

サーバソースコード

from Crypto.Util.number import isPrime, getPrime, bytes_to_long
from Crypto.PublicKey import RSA

rounds = 5
e = 65537

for i in range(rounds):
    print('*'*10, f'Round {i+1}/{rounds}', '*'*10)

    pumpkin1 = getPrime(110)
    pumpkin2 = getPrime(110)
    n = pumpkin1 * pumpkin2
    large_pumpkin = RSA.construct((n, e)).exportKey()
    print(f'\n🎃Can you crack this pumpkin🎃?\n{large_pumpkin.decode()}\n')

    assert isPrime(_pmp1 := int(input('enter your first pumpkin = '))), exit()
    assert isPrime(_pmp2 := int(input('enter your second pumpkin = '))), exit()

    if n != _pmp1 * _pmp2:
        print('wrong! bye...')
        exit()

    print()

print(open('flag.txt').read()) 

使用ライブラリ

Crypto.util.number

1. getPrime(N:int, randfunc:callable)
   long Return a random N-bit prime number

   getPrime(N, randfunc=None)
   

2. isPrime(N:long, false_positive_prob:float, randfunc:callable)
   bool Return true if N is prime

   isPrime(N, false_positive_prob=1e-06, randfunc=None)
   

Crypto.PublicKey

• construct() at the module level
  (e.g. Crypto.PublicKey.RSA.construct()). The key will be built from a set of sub-components

  large_pumpkin = RSA.construct((n, e)).exportKey()
  

サーバコード解析

1. pumpkinは110bitの素数を示し、定義した2つの110bitの素数(pumpkin1,pumpkin2)を掛け合わせて、nを定義する。
2. 定義したnと既に定義されているe=65537を用いて、RSA暗号鍵を作成する。
3. ユーザ側にこの暗号鍵の素数を求めさせて、一致すれば正解して次のラウンドに進む。計5回のラウンドを完了すればflag.txtを出力する。

解き方

前準備

サーバにアクセスし、ラウンドを開始する。

$ nc [IP] [PORT]

サーバ出力

********** Round 1/5 **********

🎃Can you crack this pumpkin🎃?
-----BEGIN PUBLIC KEY-----
MDcwDQYJKoZIhvcNAQEBBQADJgAwIwIcBmRSx1TXLdDvlBvt4v8vKjCZrNkeffes
757CowIDAQAB
-----END PUBLIC KEY-----

1. RSA暗号鍵の法(Modulus:n)を求める

サーバ出力された下記部分をコピーして自環境にkey.pemを作成する。

# key.pem
-----BEGIN PUBLIC KEY-----
MDcwDQYJKoZIhvcNAQEBBQADJgAwIwIcBmRSx1TXLdDvlBvt4v8vKjCZrNkeffes
757CowIDAQAB
-----END PUBLIC KEY-----

下記コードにより暗号鍵の法を求める。

# rsa_n.py 
from Crypto.PublicKey import RSA
e=65537
key = RSA.importKey(open('key.pem').read())
n,e=key.n,key.e
print(n,e)

実行して暗号鍵の法を出力する。

$ python3 rsa_n.py
783748737251442703079011873190205882062185270621496635094301155987

2. SageMathツールにより素数を求める

出力された暗号鍵の法を上記サイトに入力する。
素数の求め方は下記

factor(n)

計算結果出力に約30秒ほどかかり、場合によっては計算結果が出力されない場合がある。

出力結果をpumpkin1,pumpkin2に入力して正解であれば次のラウンドに進む。計5回繰り返すとフラグを出力する。

********** Round 1/5 **********
🎃Can you crack this pumpkin🎃?
-----BEGIN PUBLIC KEY-----
MDcwDQYJKoZIhvcNAQEBBQADJgAwIwIcBmRSx1TXLdDvlBvt4v8vKjCZrNkeffes
757CowIDAQAB
-----END PUBLIC KEY-----

enter your first pumpkin = 778757285861374994697077330195249 
enter your second pumpkin = 864382775363666998584057618585107

...

********** Round 5/5 **********
🎃Can you crack this pumpkin🎃?
-----BEGIN PUBLIC KEY-----
MDcwDQYJKoZIhvcNAQEBBQADJgAwIwIcB3EwCV4YEKyz2gJA6JyTO0/rsvo75tJm
jiQikwIDAQAB
-----END PUBLIC KEY-----

enter your first pumpkin = 678697478730944254991538487928321 
enter your second pumpkin = 1154783628660191137400341171916947

HTB{***************}