BabyEncryption

Hack The Box BabyEncryption 문제를 풀어 봅시다.

---

CHALLENGE DESCRIPTION

You are after an organised crime group which is responsible for the illegal weapon market in your country. As a secret agent, you have infiltrated the group enough to be included in meetings with clients. During the last negotiation, you found one of the confidential messages for the customer. It contains crucial information about the delivery. Do you think you can decrypt it?

---

Source File

chall.py 파일이 보이며 아래와 같은 코드가 있다.

1. MSG를 encryption() 함수의 인자로 전달한다.
2. encryption()함수는 msg 1글자씩 받아와서 ((123 * char + 18) %256)계산을하고 ct배열에 append 한다.
3. bytes(ct)를 리턴한다.

import string
from secret import MSG

def encryption(msg):
    ct = []
    for char in msg:
        ct.append((123 * char + 18) % 256)
    return bytes(ct)

ct = encryption(MSG)
f = open('./msg.enc','w')
f.write(ct.hex())
f.close()

그래서 나온 결과가 아래와 같다.

6e0a9372ec49a3f6930ed8723f9df6f6720ed8d89dc4937222ec7214d89d1e0e352ce0aa6ec82bf622227bb70e7fb7352249b7d893c493d8539dec8fb7935d490e7f9d22ec89b7a322ec8fd80e7f8921

Solve

제일 먼저 암호화 하는 코드를 봅시다. 인풋값에 123을 곱한 뒤 18을 더하고 256으로 나눈 나머지 값을 배열에 저장합니다.

(123 * char + 18) % 256)

잘 풀어 보면 아래와 같이 됩니다.
((123 * char) + 18) mod 256 

이는 추후에 -18 계산하면 되니 식에서 없애면
(123*char) mod 256로 나타낼수 있습니다.

즉 우리는 (123 * char) mod 256의 역원을 알면 해당 문제를 쉽게 풀 수 있습니다. (123 * char) mod 256의 역원을 구해봅시다.

def test():
    for i in range(0,255):
        a = (123 * i) % 256
        if(a == 1):
            print("[!] find inverse ",i)

test() # [!] find inverse  179

역원을 구했으니 179 우리는 암호를 해독할 수 있습니다.

def decryption(enc):
    ct = []
    for char in enc:
        char = char - 18
        char = char * 179
        char = char % 256
        ct.append(char)       
    return bytes(ct)


with open('msg.enc') as f:
    enc = bytes.fromhex(f.read())
    
flag = decryption(enc)
print(flag)

다음과 같은 FLAG를 획득할 수 있습니다. b'Th3 nucl34r w1ll 4rr1v3 0n fr1d4y.\nHTB{l00k_47_y0u_r3v3rs1ng_3qu4710n5_c0ngr475}'

모듈러 공식

해당 문제푸는데 사용했던 모듈러 공식입니다.
A mod C의 모듈러 역수는 A * B mod C = 1

후기

오랜만에 보는 모듈러 연산이 나와서 매우 당황했다. 모듈로 연산 다까먹어서….. 기억이 안나 푸는데 오래 걸렸다.. 오열ㅜ