HackCTF - Cryptography - RSA

하아...... 2일걸렸다 2일... 알고리즘을 찾기 힘들어서.. 의심되어서 흑흑

 

p = 9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483

q = 11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407

e = 65537

c = 83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034

 

이런식으로 주면 pq이용해서 n 구하고 d구하고 하면 된다.

 

일단 주어진 p,q를 이용하여 리눅스에서 rsatool.py에

./rsatoo.py -p 9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483 -q 11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407

해주면 n과 d가 나온다.

 

그리고 나서 윈도우로 돌아와서 pycharm에

def gcd(a, b):
 if a == 0: return b
 return gcd(b%a, a)

def egcd(a, b):
 if a == 0:
  return (b, 0, 1)
 g, y, x = egcd(b%a,a)
 return (g, x - (b//a) * y, y)

def inv(a, m):
 g, x, y = egcd(a, m)
 if g != 1:
  raise Exception('No modular inverse')
 return x%m

n = 0xa328797b9e7373250a36df6e4ea02f5f5f44dc923b83a098a218a78254a07134463f608fb3db095d580c8cb95e0b7644a68942d60a6f6a22604f08045a852613ab7a3c884d2000ec5c0cc5a209c81a3b19011cdcc74ce85ce0764a1ce4ebf3ea9b9a2e056f882dbe64e2a891c6bd3ea19a3e6c6d30a512936e64975b7e55e28d
p = 0xb8388266a62fb2a156da2c39368df596f76a656f625e02850446192dd6ed72f9ece160fc348b7b0742334f5298df94cc3ffbc106a42b1003a1effa0911c0a8b3
q = 0xe2bb0710f41a958cfe94636d0402876983eff9fa1f873bc69665e21abe111c8817c60653ac2aeef84376d67c75dbca7f9c57217b8a38da9b6f502024816867bf
e = 0x10001
d = inv(e,(p-1)*(q-1))
c= 0x767e17d22b50bcca982d1b09432365d6db9e417a03eef72899e6a05cb7a8bb4cc0b158fbdc463adba96d9b4acfd43cd75c80da6e87749a8482a65b5dffcec573c63924c62903ad802fe6e60905ae3c02cb9e916c01e651de914663f76267ed23895add9915ec171966841ad7b6d9d943a2bd023c3af9f96893705e98613f739a
m=pow(c,d,n)

print(m)

 

알게된 점이라면 d를 구하는 식과 m을 구할떄 pow를 쓰는데 c,d,n으로 하면 마지막 n이 %n의 역할을 하는데 기본 %n보다 훨씬 더 좋은 효율로 계산을 해서 속도도 빠르다는 것이다.

 

flag는 딴거없이 출력값인 10진수 숫자만 넣어주면 된다.

flag : 5577446633554466577768879988