[HouseplantCTF] Returning Stolen Archives - 암호학 / RSA

 

RSA 암호학 문제

 

항상 풀면서 느끼는거지만 RSA 문제는 R S A 로 3행시를 지어서 제목으로 만드는것 같다.

 

문제 파일로 intercepted.txt 파일과 returningstolenarchives.py 파일 두개가 주어진다.

 

반응형

 

RSA는 지금까지도 아주 많이 사용하는 공개키 알고리즘의 이름이다.

 

개발자인 Rivest, Shamir, Adleman 세명의 이름 앞글자를 따서 RSA 라고 이름을 붙혔다.

 

엄청나게 큰 숫자일수록 소인수분해가 어렵다는것에 착안해서 설계되었다.

 

RSA의 원리는 아래와 같다.

 

1. 두 소수 p, q를 준비한다.

2. p-1, q-1과 각각 서로소(1외에는 공약수가 없는 수)인 정수 e를 준비한다.

3. ed를 (p-1)(q-1)으로 나눈 나머지가 1의 되도록 하는 d를 구한다.(d는 개인키로 공개하지 않는다)

4. n=pq를 계산한 후 n과 e를 공개한다.(이 둘이 공개키)

 

이 알고리즘을 이용해서 공개키-개인키 쌍을 만들고

 

공개키로 암호화했다면 개인키로만 풀 수 있고, 개인키로 암호화했다면 공개키로만 풀 수 있는 그런 알고리즘이다.

 

이제 주어진 파일을 살펴보자.

 

n = 54749648884874001108038301329774150258791219273879249601123423751292261798269586163458351220727718910448330440812899799 
e = 65537
ct = [52052531108833646741308670070505961165002560985048445381912028939564989677616205955826911335832917245744890104862186090,24922951057478302364724559167904980705887738247412638765127966502743153757232333552037075100099370197070290632101808468,31333127727137796897042309238173536507191002247724391776525004646835609286736822503824661004274731843794662964916495223,37689731986801363765434552977964842847326744893755747412237221863834417045591676371189948428149435230583786704331100191,10128169466676555996026197991703355150176544836970137898778443834308512822737963589912865084777642915684970180060271437,31333127727137796897042309238173536507191002247724391776525004646835609286736822503824661004274731843794662964916495223,32812400903438770915197382692214538476619741855721568752778494391450400789199013823710431516615200277044713539798778715,48025916179002039543667066543229077043664743885236966440148037177519549014220494347050632249422811334833955153322952673,52052531108833646741308670070505961165002560985048445381912028939564989677616205955826911335832917245744890104862186090,32361547617137901317806379693272240413733790836009458796321421127203474492226452174262060699920809988522470389903614273,4363489969092225528080759459787310678757906094535883427177575648271159671231893743333971538008898236171319923600913595,47547012183185969621160796219188218632479553350320144243910899620916340486530260137942078177950196822162601265598970316,32361547617137901317806379693272240413733790836009458796321421127203474492226452174262060699920809988522470389903614273,33230176060697422282963041481787429356625466151312645509735017885677065049255922834285581184333929676004385794200287512,32315367490632724156951918599011490591675821430702993102310587414983799536144448443422803347161835581835150218650491476,6693321814134847191589970230119476337298868688019145564978701711983917711748098646193404262988591606678067236821423683,32710099976003111674253316918478650203401654878438242131530874012644296546811017566357720665458366371664393857312271236,49634925172985572829440801211650861229901370508351528081966542823154634901317953867012392769315424444802884795745057309,50837960186490992399835102776517955354761635070927126755411572132063618791417763562399134862015458682285563340315570436]

 

intercepted.txt 파일을 열어보면,

 

n, e, ct 값이 적혀있다.

 

여기서 n과 e가 공개키이고, ct가 ciphertext 암호문을 의미한다.

 

ct 값은 자세히 보면 배열 형태로 저장되어 있는걸 볼 수 있다.

 

암호문이 하나가 아니라 여러개 인듯 하다.

 

p = [redacted]
q = [redacted]
e = 65537
flag = "[redacted]"

def encrypt(n, e, plaintext):
  print("encrypting with " + str(n) + str(e))
  encrypted = []
  for char in plaintext:
    cipher = (ord(char) ** int(e)) % int(n)
    encrypted.append(cipher)
  return(encrypted)

n = p * q
ct = encrypt(n, e, flag)
print(ct)

 

다음으로 returningstolenarchives.py 파일의 내용은 위와 같다.

 

RSA 암호 알고리즘에서 핵심이라고 할 수 있는 두 소수(p, q)는 의도적으로 가려져있는 생태고,

 

정답인 flag 역시 [redacted] 로 가려진 상태이다.

 

기존에 나왔던 RSA 문제들은 RsaCtfTool 이라는 도구를 이용해 풀었는데

(https://hackingstudypad.tistory.com/126)

 

이번엔 다른 방법으로 풀어보고자 한다.

 

 

문제 설명을 다시한번 읽어보자.

 

여기서 one at a time 이라는 문장이 힌트일 것이라 생각하고 접근했다.

 

문제에서 주어진 암호문 ct가 배열 형태로 되어있는걸로 보아 한 번에 한 글자씩 암호화 시킨게 아닐까?

 

생각하고 접근해봤다.

 

만약 Hello 라는 단어가 있으면 H, e, l, l, o 를 각각 암호화 시켜서 길이가 5인 배열은 만드는 방법인 것이다.

 

n = 54749648884874001108038301329774150258791219273879249601123423751292261798269586163458351220727718910448330440812899799
e = 65537
ct = [52052531108833646741308670070505961165002560985048445381912028939564989677616205955826911335832917245744890104862186090,24922951057478302364724559167904980705887738247412638765127966502743153757232333552037075100099370197070290632101808468,31333127727137796897042309238173536507191002247724391776525004646835609286736822503824661004274731843794662964916495223,37689731986801363765434552977964842847326744893755747412237221863834417045591676371189948428149435230583786704331100191,10128169466676555996026197991703355150176544836970137898778443834308512822737963589912865084777642915684970180060271437,31333127727137796897042309238173536507191002247724391776525004646835609286736822503824661004274731843794662964916495223,32812400903438770915197382692214538476619741855721568752778494391450400789199013823710431516615200277044713539798778715,48025916179002039543667066543229077043664743885236966440148037177519549014220494347050632249422811334833955153322952673,52052531108833646741308670070505961165002560985048445381912028939564989677616205955826911335832917245744890104862186090,32361547617137901317806379693272240413733790836009458796321421127203474492226452174262060699920809988522470389903614273,4363489969092225528080759459787310678757906094535883427177575648271159671231893743333971538008898236171319923600913595,47547012183185969621160796219188218632479553350320144243910899620916340486530260137942078177950196822162601265598970316,32361547617137901317806379693272240413733790836009458796321421127203474492226452174262060699920809988522470389903614273,33230176060697422282963041481787429356625466151312645509735017885677065049255922834285581184333929676004385794200287512,32315367490632724156951918599011490591675821430702993102310587414983799536144448443422803347161835581835150218650491476,6693321814134847191589970230119476337298868688019145564978701711983917711748098646193404262988591606678067236821423683,32710099976003111674253316918478650203401654878438242131530874012644296546811017566357720665458366371664393857312271236,49634925172985572829440801211650861229901370508351528081966542823154634901317953867012392769315424444802884795745057309,50837960186490992399835102776517955354761635070927126755411572132063618791417763562399134862015458682285563340315570436]

strings_for_flag = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890_{}!@#$"

def encrypt(n, e, plaintext):
  encrypted = ''
  for char in plaintext:
    cipher = (ord(char) ** int(e)) % int(n)
    encrypted = str(cipher)
  return(encrypted)

def decrypt():
  flag = ''
  for i in range(len(ct)):
    compare = str(ct[i])
    for j in range(len(strings_for_flag)):
      enc = str(encrypt(n, e, strings_for_flag[j]))
      if compare == enc:
        flag += strings_for_flag[j]
        break
  print(flag)

decrypt()

 

문제에저 주어진 returningstolenarchives.py 코드를 이용해서 문제풀이 코드를 작성했다.

 

바뀐점이 있다면

 

p, q, e, flag 가 선언되어있던 부분을

 

txt파일로 주어진 n, e, ct 값으로 바꿔주고

 

strings_for_flag 변수를 선언해서 플래그에 들어갈 수 있는 문자들을 넣어줬다.

 

encrypt() 함수는 거의 그대로 둔 상태로

 

decrypt() 함수를 새로 작성했는데

 

strings_for_flag 변수에서 한글자씩(a, b, c ... 순서로) 가져와서 

 

주어진 n, e 값과 encrypt 함수로 RSA 암호문을 만든 뒤,

 

만들어진 암호문과 ct 배열에 있는 암호문이 똑같은걸 찾아내는 방식이다.

 

쉽게 생각하면 그냥 Brute force 한것이다.

 

 

코드를 실행시키면 해독된 평문을 찾을 수 있다.