flag가 여러 번 암호화된 다음 파일이 주어집니다.
The file below is given saying that the flag is encrypted several times.
captured_827a1815859149337d928a8a2c88f89f
맨 윗줄에 {N : e : c}라는 설명이 있는데, RSA인 듯합니다.
At the top there is {N : e : c}, and we can assume that it is RSA.
특징을 살펴보면 N이 다 같은 것을 볼 수 있습니다. 이 때 사용할 수 있는 공격은 Common Modulus Attack입니다. (참고: http://diamond.boisestate.edu/~liljanab/ISAS/course_materials/AttacksRSA.pdf)
Looking into the file, we notice that all the N are the same. In this case, we can do Common Modulus Attack. (Reference: http://diamond.boisestate.edu/~liljanab/ISAS/course_materials/AttacksRSA.pdf)
먼저 N, e, C를 파싱하고, 서로소인 \(e_{1}\)과 \(e_{2}\)을 찾습니다.
First we parse N, e, C, then look for \(e_{1}\) and \(e_{2}\), which are relatively primes.
# parsing
s = open('captured_827a1815859149337d928a8a2c88f89f', 'rt').read()[12:] # excluding top {N : e : c}
N=[]
e=[]
C=[]
s=s.replace(' ','')
for i in s.split():
t=map(eval,i.replace(' ','').lstrip('{').rstrip('}').split(':'))
N.append(t[0])
e.append(t[1])
C.append(t[2])
# find relatively prime e1, e2
import itertools, fractions
for i,j in itertools.combinations(e, 2):
if fractions.gcd(i, j)==1: print e.index(i),e.index(j)
결과: 8, 18
Result: 8, 18
따라서 서로소인 \(e_1=e[8]\)과 \(e_2=e[18]\)를 찾았습니다. 그럼 이제 다음 식을 만족하는 \(x, y\)를 찾아야합니다.
So we found \(e_1=e[8]\) and \(e_2=e[18]\). Now we have to find \(x, y\) such that
\[x\times e_1+y\times e_2=1\]
이는 Diophantine 방정식(참고: http://yum3.tistory.com/22)을 이용해서 찾을 수 있습니다. diophantine(e[8], e[18], 1)을 넣으면 \((x,y)=(-3898661337, 407775632)\)가 반환됩니다. 그러면 \(C_{1}^x\times C_{2}^y \mod n\)을 통해 P를 알아낼 수 있습니다. 하지만 \(x\)가 음수이므로 \(C_{1}^{-3898661337}=(C_{1}^{3898661337})^{-1}\)로 바꿔줘야하고, \(C_{1}^{3898661337}\)의 modular 연산의 역원(Multiplicative Inverse)을 구해야합니다.
This can be easily found using Diophantine Equation. Using the function specified here: http://yum3.tistory.com/22, diophantine(e[8], e[18], 1) would result in \((x,y)=(-3898661337, 407775632)\). Then we can easily find the plaintext by \(C_{1}^x\times C_{2}^y \mod n\). However, because \(x\) is negative, we have to consider \(C_{1}^{-3898661337}=(C_{1}^{3898661337})^{-1}\), which is the multiplicative inverse of \(C_{1}^{3898661337}\) in modular operation.
Multiplicative Inverse는 다음과 같은 코드로 구할 수 있습니다.
We can find Multiplicative Inverse using the following code:
def mul_inv(a, n):
if n == 1: return 1
r1, r2 = n, a
t1, t2 = 0, 1
while r2 != 0:
q = r1/r2
r1, r2 = r2, r1%r2
t1, t2 = t2, t1-q*t2
if t1 < 0: t1 += n
return t1
최종 코드는 다음과 같습니다.
The final code is as follows:
def diophantine(a, b, c):
'''returns (x, y) where ax+by=c'''
r1, r2 = a, b
s1, s2 = 1, 0
t1, t2 = 0, 1
while r2!=0:
q = r1/r2
r1, r2 = r2, r1%r2
s1, s2 = s2, s1-q*s2
t1, t2 = t2, t1-q*t2
# gcd: r1
return (c/r1*s1, c/r1*t1)
def mul_inv(a, n):
if n == 1: return 1
r1, r2 = n, a
t1, t2 = 0, 1
while r2 != 0:
q = r1/r2
r1, r2 = r2, r1%r2
t1, t2 = t2, t1-q*t2
if t1 < 0: t1 += n
return t1
x, y = diophantine(e[8], e[18], 1)
print hex((mul_inv(pow(C[8],-x,N[0]),N[0])*pow(C[18],y,N[0]))%N[0])
결과는 '0x666c61675f537472656e6774685f4c6965735f496e5f446966666572656e636573L'이 나오는데, 이를 decode하면 Flag를 얻을 수 있습니다.
It prints '0x666c61675f537472656e6774685f4c6965735f496e5f446966666572656e636573L', and we decode it to get the flag.
Flag: flag_Strength_Lies_In_Differences