[Dream Hack - Crypto] RSA-wiener

Wiener 공격

위너(Wiener)의 공격은 RSA 암호화 방식에서 발생하는 취약성을 이용한 공격 기법 중 하나이다. RSA는 공개키 암호화 알고리즘으로 널리 사용되며, 큰 소수인 두 개의 소수를 기반을 한다. 하지만 위너의 공격은 특정 조건이 충족될 때, RSA의 개인키를 복구하는 데 사용될 수 있다.

위너의 공격은 다음과 같은 전제 조건을 필요로 한다:

1. 소수 p와 q가 n = p x q로부터 계산되었을 때, p와 q의 크기가 너무 작아 n을 계산하는 데 상당한 비용이 들지 않는 경우.
2. e가 매우 큰 경우. 보통 RSA에서는 공개 지수 e로 작은 소수, 주로 3 또는 65537(2^16 + 1)을 사용합니다. 하지만 e가 매우 큰 경우에는 위너의 공격이 적용될 수 있다.

위 조건을 충족하는 경우, 위너의 공격은 다음과 같이 진행된다:

1. n과 e를 알고 있는 상황에서, RSA의 개인키 d를 구하기 위해 d의 근사치인 d' = 1/e mod (euler_phi(n))를 계산한다. 여기서 euler_phi(n)=(p-1)(q-1) 은 n의 오일러 피 함수이다.
2. d'의 분수 표현을 이용하여 d'를 d = (k x euler_phi(n)+1)/e 형태로 한다. 이때, k는 양의 정수이다.
3. 위의 식을 만족하는 k 값을 찾아내기 위해 연속된 k 값들을 시도하면서 d가 정수가 되는지 확인한다. 이 때, d가 정수가 되는 k 값을 찾게 되면, 해당 k 값으로부터 개인키 d를 계산할 수 있다.

 

풀이 방법

우리는 N, e, 암호화된 Flag를 가지고 있다.

N = 237513265686025789186562608732400008100581870458434017952788114554225756652162413702306473956172406315118900180084859436965775540087331299252158189935099309726131944473377703166550089276072127708850460299073570538050902891628197488607150799868080449908160852741234270848472245085906293581136277333188361835161
e = 187224198358976786579749067995497890905799822947128651088251530361387419780131539700347226362649795586438751501544451473659148049507814353125472665954342709257182749776947194758327083239358991106508477303866175029695125086636425667367941964361682844471490598884007406957886946810963902666192471332550759161305
Flag = 24981254080909219230265206235193414028780554719956568981014479247148185251168118446607184006846379494138286369937332491801314184196030148052351232512282822191418093014429056913869049243299733179602660079651535369672864881677595298490260859831553321356068082173796345881132554132547112018880976416128995190760

직접 풀이 과정을 작성하여 풀어보려고 했지만 숫자가 너무 커서 계속 메모리 오류가 발생하였다. 그래서 툴을 사용하여서 풀었다.

$ git clone <https://github.com/zweisamkeit/RSHack.git>
$ cd RSHack
$ pip install -r requirements.txt
$ python rshack.py

 

 

비밀키 구하기

요구하는 포멧대로 -n {modulus 값} -e {exponent 값} 을 넣어주면 비밀키가 나온다.

 

복호화 하기