소스코드 분석

• 암호화 파이썬 코드

   from Crypto.Util.number import bytes_to_long, getPrime
  import random
  
  flag = open("flag.txt").read().encode()
  flag = bytes_to_long(flag)
  n = 1
  while n.bit_length()<4096:
      i = random.randint(10,16)
      reps = random.randint(2,5)
      p = getPrime(i)
      if n%p !=0:
          n*=p**reps
  e = 65537
  encryptedFlag = pow(flag, e, n)
  
  print(f"n = {n}")
  print(f"e = {e}")
  print(f"flag = {encryptedFlag}")
  

  • 평문 준비
  • 약한 다중-소수 구하기
  • 공개 지수 설정 (65537 → 전형적인 rsa 지수)
  • 암호문 계산 (pow)

• 주어진 n, e, encryptedFlag

  n = 84957339878841249042661992015318775914153057891067549723671982778975957526984361748735670333426792012519248099265537115315835602057882318543112781196438953840653279029957533208045448649312183873062132255928109150470090982541502003013666939934181416473581073990221728448342533549843710383544743220364127453679761909368982493089369740815066106196444062558446312836612656666434089655206650558129894180991572670565328419648196602807190683488653617068325238542193033423978598565191919683033996144778397817249870630736098769732268174866389943010980427234356604782502318622853423388492983406635687647680770869588481426436811952986075832678887752706507835771052708232550208582584262345437818916577580806059662945066377375408508814381061305598911972399165132279018674832071994673661875185328115121586302490349253912699566783660070599552395205352917554104371784905394477629626963439266490743240318198729049054547013391348516066097465180775402810975266096525722415778248668765855332776864126033830969325570615444114396786906102536716873598804164196155179833683285635189223166238933318740720918827120989416013091102543382987278707392961157272937695585450287755023671116911370689655292160336521776501052329465384315585357461493649222793172462113102463
  e = 65537
  flag = 45146787828557679140423580221442956925310977371109091853462843177826294442352634580160310989152235297235514141658881390908592470683795245870619319983451904537192781823855678086088663405872526980084960008183831288044960349605168173490367894375757787452024287989993362954206286853190401541606518731317814018817491109177360761859453002792899864984488524864028766239497641048919565458281765487932324396702580026094746189401141448947513512730220423629277692258527951902039531739842965067285622196418171785466236294324572986853688947727117303227689578683403160426800470263102483582737614730930657875098843867256713854784720793138228809768453579721222271047690131897888999884098995408016105397663714102200568327066068146128637742779637777800612639149916508879936573438036837445673606364763612971401591822166427703422764153960398983100036398400304771376839125152709954274549463602659761299411215766075895177151923436509501196662786766042103493713861194722614436307437016043581292216432028543923347478884441934980948114759937955940408027377458938151172837554432746134399838012547867483350557859826433321810794053681726512471838143910118068486851496148663526948219071671481909824342580081675074372829356225227848676981201731545407466857723499918017
  

풀이

• 아래 파이썬 스크립트는 주어진 n, e, encryptedFlag 값을 이용해 소인수분해로부터 모듈러스의 오일러 토션트(φ), 비밀지수 d를 구하고, 이를 통해 원문 플래그를 복호화

  #!/usr/bin/env python3
  from Crypto.Util.number import inverse, long_to_bytes
  from sympy import factorint
  
  # 1) 암호문 파라미터: 실제 값으로 바꿔주세요.
  n = 84957339878841249042661992015318775914153057891067549723671982778975957526984361748735670333426792012519248099265537115315835602057882318543112781196438953840653279029957533208045448649312183873062132255928109150470090982541502003013666939934181416473581073990221728448342533549843710383544743220364127453679761909368982493089369740815066106196444062558446312836612656666434089655206650558129894180991572670565328419648196602807190683488653617068325238542193033423978598565191919683033996144778397817249870630736098769732268174866389943010980427234356604782502318622853423388492983406635687647680770869588481426436811952986075832678887752706507835771052708232550208582584262345437818916577580806059662945066377375408508814381061305598911972399165132279018674832071994673661875185328115121586302490349253912699566783660070599552395205352917554104371784905394477629626963439266490743240318198729049054547013391348516066097465180775402810975266096525722415778248668765855332776864126033830969325570615444114396786906102536716873598804164196155179833683285635189223166238933318740720918827120989416013091102543382987278707392961157272937695585450287755023671116911370689655292160336521776501052329465384315585357461493649222793172462113102463         # n = ...
  e = 65537                 # e = ...
  cipher = 45146787828557679140423580221442956925310977371109091853462843177826294442352634580160310989152235297235514141658881390908592470683795245870619319983451904537192781823855678086088663405872526980084960008183831288044960349605168173490367894375757787452024287989993362954206286853190401541606518731317814018817491109177360761859453002792899864984488524864028766239497641048919565458281765487932324396702580026094746189401141448947513512730220423629277692258527951902039531739842965067285622196418171785466236294324572986853688947727117303227689578683403160426800470263102483582737614730930657875098843867256713854784720793138228809768453579721222271047690131897888999884098995408016105397663714102200568327066068146128637742779637777800612639149916508879936573438036837445673606364763612971401591822166427703422764153960398983100036398400304771376839125152709954274549463602659761299411215766075895177151923436509501196662786766042103493713861194722614436307437016043581292216432028543923347478884441934980948114759937955940408027377458938151172837554432746134399838012547867483350557859826433321810794053681726512471838143910118068486851496148663526948219071671481909824342580081675074372829356225227848676981201731545407466857723499918017  # flag (= encryptedFlag)
  
  # 2) n 소인수분해
  factors = factorint(n)
  print("factors: ",factors)
  # factors는 {p1: r1, p2: r2, ...} 형태의 dict
  
  # 3) φ(n) 계산
  phi = 1
  for p, r in factors.items():
      # p^r 에 대한 φ = p^(r-1)*(p-1)
      phi *= (p**(r-1)) * (p-1)
  
  # 4) 비밀지수 d 계산
  d = inverse(e, phi)
  print("d: ",d)
  
  # 5) 복호화
  m = pow(cipher, d, n)
  flag_bytes = long_to_bytes(m)
  
  print("Recovered flag:", flag_bytes)
  

  • 작업 순서
    1. sympy.factorint()로 n을 소인수분해.
    2. 각 소인수 p^r마다 \phi 값을 누적: p^{r-1}(p-1).
    3. Crypto.Util.number.inverse()로 d = e^{-1} \bmod \phi 계산.
    4. pow(cipher, d, n)로 복호화한 정수를 바이트로 변환.

• 코드 실행

  

• flag

  • byuctf{3ulers_ph1_function_15_v3ry_us3ful_4nd_th15_I5_a_l0ng_fl4g}