[RSA] Franklin-Reiter Related Message Attack

이 공격은 평문을 이용한 2개의 암호문이 동일한 공개 키를 이용한 경우 사용 가능하다.

 

구하고자 하는 평문을 $m$라고 하자.

그리고 암호화에 사용된 평문은 다음과 같다.

$$m_1 = am + b,\ m_2 = cm + d$$

따라서 암호문은 다음과 같다.

$$c_1 \equiv m_1^e\ mod\ N,\ c_2 \equiv m_2^e\ mod\ N$$

이 식을 x에 관한 식으로 나타내자.

$$(ax + b)^e - c_1 \equiv 0\ mod\ N,\ (cx + d)^e - c_2 \equiv\ 0\ mod\ N$$

x에 대한 각 식을 함수로 정의할 수 있다.

$$f(x) = (ax + b)^e - c_1 \in \mathbb Z_N[x] \\ g(x) = (cx + d)^e - c_2 \in \mathbb Z_N[x]$$

이때 $f(m) = g(m) = 0$을 만족하므로 $gcd(f(x),\ g(x)) = x - m$을 만족한다.

이 공격은 일반적으로 $O(e^2)$ 정도의 시간이 걸린다고 한다.

때문에 $e = 3$을 이용해 예제를 만들었다.

 

prob.py

from Crypto.Util.number import *

secrets = b'KCTF{REDACTED}'
assert len(secrets) == 94

bits = 1024

p, q = getStrongPrime(bits), getStrongPrime(bits)
N = p * q

m1 = bytes_to_long(b'Mr.Prof said ' + secrets)
m2 = bytes_to_long(secrets + b' haha, you can not get my secrets!!')

c1 = pow(m1, 3, N)
c2 = pow(m2, 3, N)

print(f'N = {N}')
print(f'c1 = {c1}')
print(f'c2 = {c2}')

전체 플래그의 길이는 94이며 $m_1,\ m_2$가 $m$을 이용해 생성됐다.

bytes_to_long은 각 문자의 아스키코드에 바이트상 위치를 곱한 값을 합산한다.

AB는 65가 오른쪽에서 2번째 자리에 있기 때문에 $(2^8)^1 = 256$을 곱하고, 66이 가장 오른쪽에 있으므로 $(2^8)^0 = 1$을 곱한다.

이 값들을 더하면 16706이다.

이를 이용하면 $m_1$과 $m_2$를 m을 이용한 일차식으로 나타낼 수 있다.

따라서 위의 공격이 가능하다.

 

$f_1 = (ax + b)^3 - c_1$에서 a는 $m_1$의 secret의 계수이므로 1이다.

b는 'Mr.Prof said '의 아스키코드값에 $(2^8)^{94}$를 곱한 값이다. (len(secrets) = 94)

마찬가지로 $f_2 = (cx + d)^3 - c_2$에서 c는 $m_2$의 secret의 계수이다.

$s_2$ = ' haha, you can not get my secrets!!' 라면 $c = (2^8)^{len(s_2)}$이다.

d는 $s_2$이다.

이제 $f_1,\ f_2$의 gcd를 구하면 일차식을 얻을 수 있다.

그 일차식의 상수항이 곧 secret이다.

 

dec.py

from Crypto.Util.number import *
from sage.all import *

def polynomial_gcd(a, b):
    while b:
        a, b = b, a % b
    return a.monic()

N = 24244041804501162472564647370374270184531393746804288319280726459577632071606268430625121813419270340494764299041651072790971720341895797867480117054248459787125854934127635796290393145983747850260472975424206043146043177689264338466989081316851167841149550741908759663407424116592429173185689930996908873082451785565041720251026788898787986922071605425908190132168620253452796712207603687562294178520498263526131777871973542767746348754975032523521822460836859762015309398237678745979226559606779640640136616992632954257870136890463540827354040667727395546845222094413686226660922361995359218832619736202569656151163
c1 = 5451103720974006771894842643062444162747092701406953019400400167899151527354382947898173402210926600427632950011293371579854290004969282086968213211616813495239908753980028299283087799714937160911173516392058875985646231199273931029177156204347005173648267167122980071830348891172383752374397050902778508982129212144875678699067429229893999332690739687293917998168692212510684135852798970565580117664917857024871233803950984230845884440660219919717880496458347660727217484269825824916349169511206017766173652876772782031048341768217582013975462438373142913161843472975488909714599771571155464597411711377003937873322
c2 = 17538096874773134657758720366290263080724779807090670045051490425928458504424885639035110123425985705743783665036204743916913981864638617416453892357744338886134659719553301344222846711332872308013985800681802604902995461825300330435502930784273152365324306881741468538903744597656458457038498520629935231808871045416999915279543303908483776744246654465972773220728584943561682148255466477872645626082991415536992159939930892532470072821607330535655128712605561772748181705160994117125075978732110703981704326513604296504464972666806646399639705203468751001197527039921336577147049296909653524061344018099670014065074

P = PolynomialRing(Zmod(N), "x")
x = P.gen()
flag_len = 94

s1, s2 = b'Mr.Prof said ', b' haha, you can not get my secrets!!'

a = 1
b = bytes_to_long(s1) * 256**flag_len
c = 256 ** len(s2)
d = bytes_to_long(s2)

f1 = (a * x + b) ** 3 - c1
f2 = (c * x + d) ** 3 - c2

flag = -polynomial_gcd(f1, f2)
print(long_to_bytes(int(flag[0])).decode())