素因数分解

[picoCTF][Cryptography][Very Smooth]

Writeup

• 素因数分解のサイトでは、素因数分解できなかった。
  参考サイトの説明を元に、コードを作成。

Pollard's ρ-1 algorithm

import math

N = 0xb03ea698ce2b51fb00e11e6fbaf1e5373dc5b0c70eb2b14a36d21e8667be8774eee51f6050a10237f6b24f21204fc8013681e7ed72ed051188f3274aae8f1de0d39389b514c196fa82c98a270bfabefd044da8c687b0e114ebbde82536c0709ac5ad81bfe0077e9d9b798ad5abecee52767e68f8060c45936521fd93893102eb1676f2ff41324a7a6b3dff2e830538e06d25934e9f14bf6b40ab5674fe648e314bf06f84282f5ef52bc1401de3a42eb66e64bcdadd2674348e5bdb7016feda44d719af387a948ad81cbaed10213dd930fc7bc7677d8c4cdab0645d0ff15e6ad6ca37135942c3be08f23e7be0992c8b3370dcdc31045e086d823107fb2e443dc9
exp = 1
base = 2

while True:
    base = pow(base, exp, N)
    p = math.gcd(base-1, N)
    if 1 < p < N:
        break
    else:
        exp += 1

print("p =", p)
print("q =", N//p)

• コードを実行
  素因数分解に成功。
  

• 与えられたコードを確認
  math.lcmを使用している。
  

• 必要なライブラリをインストール

pip install pycryptodome

• デコードするコードを作成

dec.py

import math
from Crypto.Util.number import *

c = 0xa913a96e215b5aa79c702d27fa375c73d06787639c4131fb32877cafefaa8faf70e15f6a17ef2a9a6f5310b157cb287b740e77cb5385081d1853a9104bc16357b259fa2d146bd87398d4ef6f1c078289812952c67792cf9cd745049aeb9d4ab4dff2825a9c0b3381f19b2a67164f9d4de33c25f98bc2f224feb5507b531e1a1c7be5ed2d8ddd01f3fae37245e8cf99c75a21848993d445e1d6d69d555a3e6cc8055704fdde88df9084bda3ea65a9384fa64bf8df4d88946449526320c15d4d2d871638070489adf3f8c95caffeab40b0d137a9319be20cdf6ebbaf037f62093d9bd33edd4ffd7e1929b9ab06252956fd85250a0515ef2b4e035017be5702cdd3
e = 65537
p = 166778678181685622576528273627655558408416154535903271612099666211650718813574353644982679332718906416639262976090347767411961612927781793104151632976133030663080503056699508483393432483211221435369665266139037807475222869716828564531056095553338227197069928344760597134918054695465937470622255206477029220627
q = 133403359244090432282498741122238666960102072347999139399194192684930601046915449960642287092839790447663496118648044185489682661151904512440107598783041356688524538695035027282386056258524355032597865645378353170572838674473248880702185307449067157154593351616151961260356975594350933975792987875901590674739

phi = math.lcm(p-1, q-1)
# eを-1乗して、phiのmod（余り）を計算
d = pow(e, -1, phi)
# 暗号文をd乗して、nのmod（余り）を計算
P = pow(c, d, p*q)

print(long_to_bytes(P).decode())

• コードを実行し、デコードに成功
  

• 以上です。

参考サイト