Sharif University CTF 2016: Crypto 150 Solver

find_p.py

# original file name : find_p.sage
from sage.all import *
import sys

n=0xA4E20DDB854955794E7ABF4AE40051C0FC30488C82AB93B7DD046C1CC094A54334C97E84B523BD3F79331EBEAF5249200D729A483D5B8D944D58DF18D2CA9401B1A1A6CDA8A3AC5C234A501794B76886C426FAC35AD9615ADAB5C94B58C03CCFFA891CE0156CBC14255F019617E40DE9124FBBE70D64CD823DCA870FF76B649320927628250D47DB8DFA9BBCE9964CB3FE3D1B69845BD6FA2E6938DDA1F109E5F4E4170C845B976BBD5121107642FC00606208F9BC83322532739BCFEAF706FB2AF985EBD9769C7FBD50ECBF55566BD44FB241F9FD2DE25069AA8C744F0558514F1E9C8E4297A4D4B25D9F2B7494B466C2E6E2834BA68C5C824215018368B4FB

e = 65537

c = 0x64A3F710E3CB9B114FD112B45AC4845292D0B1FEE1468147E80FABA3CD56B1206F5C59E5D400A7F20C9BCD5B42C7197A0D07FBBA48BFBDA550C5CAFB562BEC1B1CB301D131E13233F2BD1C80EEB48956FF0BC8DB6AE2CD727FB1DAC62822331B15A6044F825D01D81036DA3CC8A3575165E813051036715CDF5F7865676DC2513AAD08C5113DFFDC4E6B13E6FFCA2FAD1AA6986D3ED9F1896C109F641074DA7DBFE62CCAD3CACE4B80332475FE3C9EC4869FCA31EE2860D45959F8583C2AEC7A00FC2FD63DBF6CBEB1C604D60CF780FE028ED0AD65DC74BC5335F96EE7CEDEA292F76B427E5F402BCC609B39302CD4A51F405C6ACF8B8A7569AAD9A9318F060B

test = pow(2, e, n)

pi=0xCDE6FD1CF108066CC548DF9070E102C2C651B885F24F503AAFFE276FEB573110C1E4592A35890D7678AAEEE9F44800FC43F999D5D06B89FCB22E5335A9287BC6D75A3E91E53906D413163D5
const_1 = pi * 2**400
const_2 = const_1 ** 2

def high_bit_known(pbar):
  global n
  beta = 0.5
  epsilon = beta^2/7
  pbits = 1024

  kbits = floor(n.nbits()*(beta^2-epsilon))
  PR.<x> = PolynomialRing(Zmod(n))
  f = x + pbar

  x0 = f.small_roots(X=2^kbits, beta=beta)
  return x0

for x in xrange(1, 4096):
  if x % 0x100 == 0:
    print "[+] %04x..."%x
  kp = (x + 2**12 + 2**13 + 2**14 + 2**15 + 2**16 + 2**17 + 2**18 + 2**19)
  pbar = kp * const_1
  p = high_bit_known(pbar)
  if len(p) > 0:
    print p
    p = ZZ(p[0] + pbar)
    if n % p == 0:
      print "!!!Found!!!"
      print "kp = %d" % kp
      print "p, q  = %d, %d" % (p, n/p)
      sys.exit(0)

solver.py

from scryptos import *

n=0xA4E20DDB854955794E7ABF4AE40051C0FC30488C82AB93B7DD046C1CC094A54334C97E84B523BD3F79331EBEAF5249200D729A483D5B8D944D58DF18D2CA9401B1A1A6CDA8A3AC5C234A501794B76886C426FAC35AD9615ADAB5C94B58C03CCFFA891CE0156CBC14255F019617E40DE9124FBBE70D64CD823DCA870FF76B649320927628250D47DB8DFA9BBCE9964CB3FE3D1B69845BD6FA2E6938DDA1F109E5F4E4170C845B976BBD5121107642FC00606208F9BC83322532739BCFEAF706FB2AF985EBD9769C7FBD50ECBF55566BD44FB241F9FD2DE25069AA8C744F0558514F1E9C8E4297A4D4B25D9F2B7494B466C2E6E2834BA68C5C824215018368B4FB

e = 65537

c = 0x64A3F710E3CB9B114FD112B45AC4845292D0B1FEE1468147E80FABA3CD56B1206F5C59E5D400A7F20C9BCD5B42C7197A0D07FBBA48BFBDA550C5CAFB562BEC1B1CB301D131E13233F2BD1C80EEB48956FF0BC8DB6AE2CD727FB1DAC62822331B15A6044F825D01D81036DA3CC8A3575165E813051036715CDF5F7865676DC2513AAD08C5113DFFDC4E6B13E6FFCA2FAD1AA6986D3ED9F1896C109F641074DA7DBFE62CCAD3CACE4B80332475FE3C9EC4869FCA31EE2860D45959F8583C2AEC7A00FC2FD63DBF6CBEB1C604D60CF780FE028ED0AD65DC74BC5335F96EE7CEDEA292F76B427E5F402BCC609B39302CD4A51F405C6ACF8B8A7569AAD9A9318F060B

test = pow(2, e, n)

pi=0xCDE6FD1CF108066CC548DF9070E102C2C651B885F24F503AAFFE276FEB573110C1E4592A35890D7678AAEEE9F44800FC43F999D5D06B89FCB22E5335A9287BC6D75A3E91E53906D413163D5
const_1 = pi * 2**400
const_2 = const_1 ** 2

p, q  = 144299940222848685214153733110344660304144248927927225494186904499495592842937728938865184611511914233674465357703431948804720019559293726714685845430627084912877192848598444717376108179511822902563959186098293320939635766298482099885173238182915991321932102606591240368970651488289284872552548559190434607447, 144245059483864997316184517203073096336312163518349447278779492969760750146161606776371569522895088103056082865212093431805166968588430946389831338526998726900084424430828957236538023320369476765118148928194401317313951462365588911048597017242401293395926609382786042879520305147467629849523719036035657146109

assert p * q == n

rsa = RSA(e=e, n=n, p=p, q=q)
print repr(rsa)

print hex(rsa.decrypt(c), 2)[2:].decode("hex")

I analysis prime generator. I got prime structure.
generated prime looks like below:

p = k * pi * 2^{400} + t

t is 399-bits random number, pi is Product of all odd prime less than 443(equals to Fixed Parameter!), and k is random(1, 2^12) + 2^12 + 2^13 + 2^14 + 2^15 + 2^16 + 2^17 + 2^18 + 2^19.

What is bruteforceble parameter? Yes, It's k. It has only 2^12-bit randomness.
...and max(t) is 2^399-1. It is less than n^1/4.

So I think to use High-bit known Attack.

for x in xrange(1, 2**12): # bruteforce k (1 -> 2^12)
  k = x + 2^12 + 2^13 + 2^14 + 2^15 + 2^16 + 2^17 + 2^18 + 2^19
  p = High_bit_known([k * pi * 2^400])
  if n % p == 0:
    Bingo!

Flag is e7531f1bb9c95c19e823065d3e6a86b6