I recently got this cryptic message in the mail:

`9429 263 6992 2243 715 6992 4650 7924 237 5486 6204 6239 6204 237 494 6239 1794 7167 715 5149 6239 3801 3750 6239 1242 13481 7774 3401`

Along with these clues:

1. Nooo! This great tennis player recently retired, and was accused of doping. His first name sounds cool.
2. And I heard this person received a large grant of land in California, something named "Rancho San Antonio"? His last name sounds cool.
3. I've heard wikipedia is a great resource. How can I research them more?
4. hmm... this is interesting. his birth day and birth year are both pRime! what Should i do with thAt?

Sounds like gibberish to me. Hopefully you can figure it out though!
Plain Text
복사

# 분석

자 위에 문구를 해석해서 보면 뭔가 암호문을 받았고 아래의 메시지가 힌트라는 것 이다.

1. 아니! 이 훌륭한 테니스 선수는 얼마 전 은퇴했고 도핑 혐의를 받았습니다. 그의 이름은 멋진 것 같습니다.
2. 그리고 이 사람이 캘리포니아에서 "랜초 샌 안토니오(RSA)"라는 이름의 땅을 많이 받았다고 들었습니다. 그의 성은 멋진 것 같습니다.
3. 위키피디아가 좋은 자료라고 들었습니다. 어떻게 더 조사할 수 있을까요?
4. 음... 흥미롭네요. 그의 생일과 출생 연도가 모두 최고(pRime)입니다! 어떻게 해야 할까요?
Plain Text
복사

일단 메시지에서 pRime과 “Rancho San Antonio”에서 앞 글자만 RSA로 대문자로 표시했기 때문에 소수 관련 RSA 암·복호화 관련 문제로 생각할 수 있다.

여기서 정석적인 풀이는 위키피디아에서 검색을 해서 은퇴하고 도핑 혐의를 받은 테니스 선수의 성을 찾고

"Rancho San Antonio"의 땅을 받은 사람의 이름을 찾아

이름과 성을 합쳐 이성을 만들어 해당 사람의 출생 연도를 뽑아 RSA복호화 키에 사용하면 된다고 예상할 수 있는데 이게 정석적인 풀이지만 문득 든 생각이 있었다.

위키 피디아에 올라올 정도면 기원후 사람이다.

1000년 이후의 사람일 것이다.

2000년 이전의 사람일 것이다.

생년월일이 소수라면 0~2000년도와 1~12월 1~31일까지의 경우의수가 나오는데 이는 그렇게 많은 경우의 수가 아니다

3번의 경우의 수에서 소수가 나오는 경우의 수를 계산하면 이 역시 매우 제한적이다.

1~5번까지의 생각을 통해서 그냥 소수를 순서대로 넣어보면서 해당 메시지를 복호화한다면 복구되지 않을까라고 생각했다.

그냥 이건 웃겨서 보다가 웃겨서ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

# get_prime Code

def solution(n):
    is_prime = [True for x in range(n+1)]
    p = 2
    while (p * p < n):
        if is_prime[p]:
            for i in range(p * p, n + 1, p):
                is_prime[i] = False
        p += 1
    prime_numbers = [p for p in range(2, n + 1) if is_prime[p]]
    
    return prime_numbers

primes = solution(2000)
with open('year_primes.txt','w')as f:
    for i in primes:
        f.write(str(i)+"\n")

primes = solution(31)
with open('day_primes.txt','w')as f:
    for i in primes:
        f.write(str(i)+"\n")
Python
복사

일단 위 코드로 소수를 먼저 구해줬다

# Payload

def extended_gcd(a, b):
    """확장 유클리드 알고리즘을 사용하여 gcd(a, b)와 베주 항등식의 계수를 찾습니다."""
    if a == 0:
        return b, 0, 1
    else:
        gcd, x1, y1 = extended_gcd(b % a, a)
        x = y1 - (b // a) * x1
        y = x1
        return gcd, x, y

def find_d(e, phi_n):
    """확장 유클리드 알고리즘을 사용하여 개인키 지수 d를 계산합니다. d는 e의 모듈러 φ(n)에 대한 역원입니다."""
    gcd, x, y = extended_gcd(e, phi_n)
    if x < 0:
        x += phi_n  # 모듈러 역원이 음수일 경우 양수로 변환
    return x

with open('day_primes.txt','r')as f:
    day_keys = [int(i.strip()) for i in f.readlines()]

with open('year_primes.txt','r')as f:
    year_keys = [int(i.strip()) for i in f.readlines()]

for e in range(1000):
    for year in year_keys:
        # RSA 복호화에 필요한 값들
        for day in day_keys:
            p = year           # 예제 소수 p
            q = day           # 예제 소수 q
            ciphertext = [
                9429, 263, 6992, 2243, 715, 6992, 4650, 7924, 237, 5486, 
                6204, 6239, 6204, 237, 494, 6239, 1794, 7167, 715, 5149, 
                6239, 3801, 3750, 6239, 1242, 13481, 7774, 3401
            ]


            # # RSA 모듈러스 N과 오일러 피 함수 phi 계산
            N = p * q
            phi = (p - 1) * (q - 1)

            # # 개인키 d 계산 (e와 phi의 모듈로 곱셈 역원)
            d = find_d(e, phi)

            # # RSA 복호화: 평문 m = ciphertext^d mod N
            plaintext = list()
            for i in range(len(ciphertext)):
                plaintext.append(pow(ciphertext[i], d, N))
            
            if plaintext[0] != ord('b'):
                continue
            try:
                _ = ''.join([chr(i) for i in plaintext])
                print("복호화된 메시지({}, {}, {}): ".format(p,q,e), _)
            except:
                print("복호화된 메시지({}, {}, {}): ".format(p,q,e), "Non Printable")
Python
복사

RSA에서 p, q는 대충 맞출 수 있지만 e를 알아낼 수 없기 때문에 e는 0~1000까지 범위로 잡고 python3 main.py > 1.txt로 코드를 실행한다.

vscode로 Ctrl + F를 눌러 검색 기능을 이용해 Flag를 찾아준다.

# Flag

bronco{wh4t_th3_f0ck_1s_RSA}
Plain Text
복사