PlaidCTF 2015 Strength (crypto110) writeup

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)
Copy

결과: 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
Copy

최종 코드는 다음과 같습니다.

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])
Copy

결과는 '0x666c61675f537472656e6774685f4c6965735f496e5f446966666572656e636573L'이 나오는데, 이를 decode하면 Flag를 얻을 수 있습니다.

It prints '0x666c61675f537472656e6774685f4c6965735f496e5f446966666572656e636573L', and we decode it to get the flag.

Flag: flag_Strength_Lies_In_Differences