baby RSA

Description

Category: Crypto

Source: AceBear Security Contest 2019

Points: 831

Author: Jisoon Park(js00n.park)

Description:

Let's warm-up

link

Write-up

문제 설정은 매우 간단하다. n, e, c와 함께 (p + q)²⁰¹⁹ mod n, (p + 2019)^q mod n의 값이 주어진다. (각각 a, b라고 해두자)

여기서 private exponent를 찾아서 c를 복호화 하면 되는 문제이다.

[...]

p = getPrime(512)
q = getPrime(512)
n = p*q
e = 65537

c = pow(m, e, n)

print(n)
# 13299187269178832408213486199795357[...]

print(c)
# 51298575439582965784709335152059190[...]

print(pow(p+q, 2019, n))
# 11662295269650372444446581690681292[...]

print(pow(p+2019, q, n))
# 46935581819524717607675319301313485[...]

우선 (p + 2019)^q mod n = b을 살펴보자. q승을 한다는데서 페르마의 소정리를 이용할 생각을 쉽게 해볼 수 있다.

• (p + 2019)^q mod n = (p + 2019)^{(q - 1) + 1} mod n mod q = p + 2019 mod q = b mod q
• p = b - 2019 (mod q)

다음으로 (p + q)²⁰¹⁹ mod n = a을 풀어보자.

(a + c)^b mod c = a^b mod c 인 것을 활용하면 된다. (증명은 b가 0, 1일때는 자명하고, 2일때 부터는 귀납법을 이용하면 된다.)

• (p + q)²⁰¹⁹ mod n = p²⁰¹⁹ mod n mod q = (b - 2019)²⁰¹⁹ mod q = a mod q
• (b - 2019)²⁰¹⁹ - a = 0 (mod q)

그러므로, (b - 2019)²⁰¹⁹ - a는 q의 배수이다. n 또한 q의 배수이니, 두 수의 GCD를 구하면 q의 값을 알 수 있다.

이제 순서대로 p, phi(n), d, m을 구하면 flag를 얻을 수 있다. (code)

Flag : AceBear{1_Hop3_1t_w4s_n0t_t00_34sy_f0r_U}