#!/usr/bin/env python
# coding: utf-8

# # HITCON CTF 2019 Quals - Not So Hard RSA (crypto)

# The challenge consists of the following short code:
# 
# ```py
# from Crypto.Util.number import *
# from secrets import *
# 
# T = 10
# def encrypt(data):
#     num = bytes_to_long(data)
#     p = getPrime(512)
#     q = getPrime(512)
#     n = p*q
#     assert num < n
#     phi = (p-1)*(q-1)
#     e = inverse(d,phi)
#     a = pow(num,e,n)
#     enc = long_to_bytes(a).encode('hex')
#     return (n,e,enc)
# 
# flag = open('flag').read()
# print d.bit_length()
# for _ in xrange(T):
#     data = flag + urandom(40)
#     print encrypt(data)
# ```
# 
# We are given 10 different RSA moduli and encryptions of the flag under each of them. The only relation between them is the common private exponent $d$. From the output file we can see that it has 465 bits, i.e. it is very short (compared to 1024 bits - size of $n$). Consider the exponents equations of the RSA, with approximate bit size of elements noted (recall that $0 \le k_i < min(e_i, d)$):
# 
# $$
# \underbrace{e_i}_\text{1024 bits} \underbrace{d}_\text{465 bits} - 1
# =
# k_i \phi(n_i) = \underbrace{k_i}_\text{465 bits}(\underbrace{n_i}_\text{1024 bits}\underbrace{-p_i-q_i+1}_\text{512 bits})
# .
# $$
# 
# $$
# \underbrace{k_in_i}_\text{1489 bits} - \underbrace{e_i d+1}_\text{1489 bits} = \underbrace{k_i(p_i+q_i-1)}_\text{977 bits}.
# $$
# 

# How much freedom do the unknowns have? Let's assume we fix $d$ arbitrarily. Then 465-bit freedom of $k$ would allow to get roughly $1489-465=1024$-bit value on the left. However, we know that it has only 977 bits (we consider it as an error/noise term). Therefore, we obtain a 47-bit costraint on $d$ from each equation. From 10 equations we can expect to recover all 465 bits of $d$!
# 
# This is just an intuition behind the sizes of the numbers, we also have to efficiently satisfy the constraints. Luckily, LLL works great with such linear equations.
# 
# Consider the following lattice (spanned by rows):
# 
# $$
# \Lambda =
# \begin{array}{c c}
#     \begin{array}{c}
#       d \\ k_1 \\ \vdots \\ k_{10}
#     \end{array}\hspace{-1em}
#     &
#     \left(
#       \begin{array}{@{} c c c c c c c @{}}
#         -e_1 & \cdots & -e_{10} & 1   & 0 & \cdots & 0 \\
#         1 & \cdots & 0 & 0          & 1 & \cdots & 0 \\
#         \vdots & \ddots  & \vdots & \vdots & \vdots & \ddots & \vdots \\
#         0 & \cdots & 1 & 0          & 0 & \cdots & 1 \\
#       \end{array}
#     \right) \\
#      & \begin{array} {@{} c c c c c c c @{}}
#         \hspace{0.7cm}v_1 & \cdots & v_{10} & \hspace{0.35cm}d & k_1 & \cdots & k_{10} 
#       \end{array} \\
# \end{array}.
# $$

# Note that all $e_i$ are in the same row since they correspond to terms with $e_id$ and $d$ is the same for all equations. Whereas all $k_i$ are different and each has its own row.
# 
# Consider the correct $k_i$ and $d$ and consider the linear combination descibed at the left side of the matrix. The corresponding vector in the lattice is equal to
# $$
# (v_1, \dots, v_{10}, d, k_1, \dots, k_{10}),
# $$
# where $v_i = k_in_i-e_id$ is the small ("noise") 977-bit value. As a result, we obtain that the solution we look for correspond to the short vector in the lattice: all $v_i$, $d$ and all $k_i$ must be small. Note that $d$ and $k$ should be 465-bit values, while $v$ can be much larger: 977 bits. To encode this information, we scale the '$d$' and '$k_i$' columns by $2^{512}$ before applying LLL and scale back afterwards.

# In[34]:


from __future__ import print_function, division
from sage.all import *
from Crypto.Util.number import *
from sock import Sock
class Stop(Exception): _render_traceback_ = lambda self: None


# In[35]:


# chall
data = [
(61608417975397048843788515638593839325111098880518441270527767841153782846066445099077365303960932518098100778959123136871039627996767023258612684873083420234538156646585282154245553305607644427220207313162116929585370583379703086997585339296145409828300576290109728682441066135201997295424597733433471586151L, 60032368056605168202792776655067640210910930719068898740685488293392455428589220656480049668823171895161714617099267690524276842795335016835073541061601545456195765907623303970146386500563913899580929779870429659650425339185233299118860275385880359287380867251468679962048998842668813298548390941601249105855L, '1e4433543ad3eab1d5a5490e33ee98c34785945c7b69dd0fd0a371c28e5ff45f6627ad0559d9837fd6439367543ff5670f4df4fd36cbee75950db62e51811f98e3f34db66b07196a5dfbd9867952d8e6d67c43becf086087181e5f78582e98945e5c8c08d754b998ef01e836729f9620cdcd2cc8aae9cb4bf3d8e4beec3ca8fd'),
(52084595054768217522676979342755393306305099169414947960508049057119329537162079071100773540172780699842974838973453517862170568297372572652378982794735495836797191260523386985555538123219596180065060457770169661533302156160201909218943628670173938802399175928847179180982290051008255643478089280887936398779L, 15937444970326662770243305998311639639802081677519521519037892156989918335411343952028567001158781869582357356721336548356177945486289103616332672857562241745733313956089488246637981047367689313876169403573606972534488436195086998111247112950511965259280728899941655052549135516189815880662766290132607874671L, '15dbeced76ab710b84982e67a839846cfe38cfccce4dacc585df0e38d695e1c84eac7281d8c83b3c6eebfae7c27d91496b19de120374d08cbccc251a464c2f7bb10fb9d1c1f13b78f1fbfe0ce37d01350978dcb192c92db43560a9cd81481aa2e2d41a8c5b3c67d3e3ae4be50ddf37a5a0193da6f4befe71d5348bd7820f1b0a'),
(121675354261226402523384817752122501670754379029920951567545832861118347020889141951034949457467042630795199347469665294677977729959566390358589470405088739543312116123816666440234661644847943610733959265939955886506334607329368744886743083353218982597246897307234102346047327550059519916639261619453107169923L, 1958149621008109700386193021020256359555810444022322757777842537494487439895477039590251808463946583928481366538370998263830913239177109491659797444270949612728937519312683847609162235917948298810271512469482956117395111528004250206351805086758526770795159863075378020975086922955262230095667701740508170151L, '5b445089b4578b115b0293cc1922f5fdb784701fd533eec7ec9bd7fdad995baefb051b9793ff3dadc24ff8d5b52c89f9565f65409c58506c7e79dd787f8e388f019497461fa3db0eac5284d398f9e6a1b81c59ba74677cc01c38ddd6461df029e1179f3ee63ccce20f3090835b7bd7b4de25c38ccddf2ec622cd41fafb49d68f'),
(70820434096887624688036248070441718528107270792728727307197623356369639890276828895683705436125317302252834211775910545775001651922925694194466935425170969939539346172633115232030274859268960310846965871663926227518137713901150141826470260092611613639370170779217268337906342955347156686598981918675591938393L, 6264211827826908864953215815104077572906230669747226774603059704547415338199956437981145121700015020477626176620200121575740530313039227764537541481272011717745292622796843631960318813842515397395192806936521180850750841260559451018598913158548097304919304754876270597286947644956943158352022152801127867879L, '4f56516d8e197a8fd6ed76433a836635dd5ad1247be9ccbb5a88ea940f5746221b4bb5b60ef925019a11d36fbe8f1d948e9afb4305937d7e017148b8ba324682d60ed6fb7f3de80031432023bbef81a96d0c1bd26c3a728bc6fdebbd48bf86b93325584c1a1386e26374c9747754b858a01b73996cea8fe4edd2a8130504e63e'),
(82396665631738285668995082087133930047188890932442133336046256534530991902128696466596278088102928917626464109384091264437455382690583003229076491363732222934817133536320704449557698925700841043105303694696203472531025908797520768019280257689521302427077849286757365739653728248123114986191011560571298134089L, 77541341309162852568860774868359137598587882474829780783306540898574011860779494674673722444562346968736216806881154962981695851598965376893425170303668270087989094501452417979429678869102952038600630142304872749698942475289176861137563927160985001506014089253274664444041660282426708388957971134224538326179L, '6b35dffadd327c0999efc909a3c1d1482c6a286808801095eec5ea88224467881b4081c1aef02c273cc5dc4d3505dc50fcf4ce60052b6a5a9dc005faad4709fbcca254c6fc1c552d51c8e15fbd8fc404b0136758e1ba57f6c04b1049e303a43ae60c1eb0b671289f6689d1cd104c407549c1bcfc081a28a3f3324a1611e81555'),
(64885222129962661919689742957615146346855998523264787345799887210230045803423356080820154546050540728264000944692170729880161760807788699983366314269171423680987673788784023826885067996007133127166699735414920427997399513922777341273346196540175237091469555617281522541592407225697228219483666768990986901207L, 47625666889348051674457306461777570860477708163951567694477110559722255361844497439523737482859577232793119885759760321686098657292699849459852343686370029321619072315457562131610624443702007471950020751311592439673932509558946203816066868221203483167079506399876187240483994566182748627389022243608934595071L, '0f79419a86361d668ced50fbcfa521c5117f7b2f72c3cc248dba4b2b1c9e7dc3a32fa500f5167a0360aeefcb8daa973bc67b0537d641617c2d96d98ee27179de1644b480c120b2d14054db032b42af33b23f8182f72cc8e752d6f89d556800f637bc492bd8eb2fb294eee61bc3c55677066b6962c4d2a1f1896703d446d903f3'),
(130307595686638523389042871138355252466828093625912424932382409748014813151912412889866698513547588105179569464359905871041351306187955332098310075195714887141180801001191398677311128761953690562878908997464309620384635922453765468745206262477334243233099872249671186622159533482223573972729351847574480258349L, 15517881429792452627724339825487038872077384939873021432131971858090290889497162855962736652640866521963165312583164013911162455865793567436833813352448640307756786561236246631146444590597902995591016928432988304077340670079503467394770901559567924809126517090243024890436892801283564005789256977822007581731L, '69a8e0bb49427f3465c9f3a41a22e047bd348c886cdb07264a321f8b890bb48cd7a878e43c1eb4b2f496dafb50677b3eea032c8f7f2ee59695398c56cc3b183bb6e2f1ab2d5d633461a6592ca0c98c0f2dae4100d6aaaf0d1166bdd46beb68b07d9c9cf6c5a92ef7db019dc065b3a8300ca25b50cba51a3294d954c178bf3770'),
(65386448419573832864151040666988491321490532636782967162806795276671017479566436411594017000387653366263378617189553041765586083217125727980734225153709370447270596363822524978426540069479632490507360491377612488876553715272119578498102854909764339676652952568021321118127618560269626549257296451954041925283L, 62417639911670877600600895776941278119707067464948560335387709799367122896567813566638216057171867961437006927011778910808189676129022776796728833211435603542364704330783289218396426543693678813151580911213239650850603907199690825764030369692366216968117035006819175280930722880390482701178418013436415892711L, '2231e71788fe0fec78ada4f24a58bbaa5b1a0fb48dc94b18bf7409637dbcfd8e2755d80b5e4b309e20a69474a6e2eb245e40c1b3f81c6151dbf7e6871e90a9616a32f4a8443d30bfaaff5d711be39bc8f38c13234af9fd867f508b8a6b097a49fb07a1392ec08c38f0939620cf644ec6631f7566b6bc7a1f1d01a9c736eceda4'),
(131618812326147470215836136712095159211663684841466199972335887950664101678748935713203393931245541362772506324940879455504378545672259298894346211770983161798960234145317156224604949365110464634198678301644727985645228605590810190481288852412139519629077007437022950591320600450976104529132138396249413028099L, 14318453997383587408499979509282945054981178882287936277795320451723285671391694914929520724692059461777785480850364952738183846512279857119933447174333240691522012746191524101263192457454032837995702952840654708026147079321112397181981380295129696518148352311994008219805602114421675331461920408832158576071L, '71a370974f020d338071e2b0480f38f2d5b488252f5eb206636d6dcd3c93ea586a507c29d2e611a9a8d5d0f849b913116b37e69345d6eae71cf87cdb6b74e75bccdb374c372562777a727f07e4272a5ff17b451d582074b565879453d028c5e9b91cb67ae923f0f09492e508422e65c1daada0564d91a9feec094af77ab190fa'),
(99041226655569332839951771030354960649881033648844611842019981984694036670092050113949713459076512100815903654289240773362239468428010238444408944822516190193861719380849620966232652503444079295871086550223067647300451354087943235559953597249075277760677450645744584993036921709483731953822197438848939991653L, 45917328654051873455626365238806652384056265616606200025887647202756379007355041189714541493038574645714670682101129613041399879280497291675656671383417575172090283625761438606371062142083212903854592596935358334738253893062615061401134834123551055465985828525720791523020773994634134135284036947641526947783L, '336e810e66eeac255f1714b290187773de92ec044b654a4cc0eef2070e9d8d86fa37d424b2e4b71fd135e634034e06dbc31e77bd13d470aa5d3e5dcc5e689b565178a4a445d4560f5569967315a0bbe163ef83063429ec8d1fbba1a8dbd9e30a2a67e17793f8b19e7b184c3b989dadc85b7f060e3daefb66ff803c98bda8862f'),
]
T = len(data)        


# Note that $v_i$ are typically a bit smaller, and we can reduce them by approximating $p+q$ by $2\sqrt{n}$. Therefore, we should scale the $d$ and $k_i$ columns by a bit smaller numbers. This is important, since the information amount that we obtain is quite tight. In fact, when scaling by $2^{512}$, the resulting basis does not contain the desired result. However, it should still be available in small linear combinations of short vectors, or e.g., by guessing a few bits of $d$ first.
# 
# Luckily, scaling by $2^{505}$ works well and we find the correct $d$ in 10-th element of the smallest basis vector.

# In[37]:


m = matrix(ZZ, T+1, 2*T+1)

i = 0
m[0,T] = 1
for ni, ei, ci in data:
    m[0,i] = -ei
    # approximate p+q as 2sqrt(n), reduce a bit size of the noise
    m[1+i,i] = (ni - 2*int(sqrt(ni)))
    m[1+i,T+1+i] = 1
    i += 1
    
Cd = 2**505
Ck = 2**506
for i in range(T):
    m.set_column(i, m.column(i))
    m.set_column(T+1+i, m.column(T+1+i) * Cd)
m.set_column(T, m.column(T) * Ck)

ml = m.LLL()

for i in range(T):
    ml.set_column(i, ml.column(i))
    ml.set_column(T+1+i, ml.column(T+1+i) / Cd)
ml.set_column(T, ml.column(T) / Ck)    

print("Bit sizes:")
print([len(ZZ(v).bits()) for v in ml[0][:T]])
print([len(ZZ(v).bits()) for v in ml[0][T:T+1]])
print([len(ZZ(v).bits()) for v in ml[0][T+1:]])

n, e, ct = data[0]

for irow, row in enumerate(ml):
    d = int(abs(row[T]))
    if pow(2, e*d, n) == 2:
        print("found d", "row", irow, ":", "d =", d)
        ct = int(ct, 16)
        flag = pow(ct, d, n)
        print(`long_to_bytes(flag)`)
        break