Challenge:


from Crypto.Util.number import *
from os import urandom
from SECRET import d


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).hex()
    return (n,e,enc)

flag = b'redacted'
print(d.bit_length())
for _ in range(T):
    data = flag + urandom(40)
    print(encrypt(data))

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



Solve:

The private key d is small with 465 bits.

The fact that each plaintext is related is actually not so useful. We’ll ignore the ciphertexts given for now,

and recover d just with the n’s and e’s given.

I realised it is also similar to this chall


We can write 10 equations

ei*di-1 == ki*phi

for all ki<d


d = random_prime(2**465)

for _ in range(10):
    p, q = random_prime(2**512), random_prime(2**512)
    n = p*q
    phi = (p-1)*(q-1)
    e = pow(d, -1, phi)

    k = (e*d - 1) // phi
    assert k<d
    assert e*d - 1 == k*phi

    assert phi == n - (p+q) + 1
    assert e*d - 1 == k*(n - (p+q) + 1)
    assert e*d - 1 == k*n - k*(p + q - 1)
    z = k*(p + q - 1) - 1 # ~= 2**465 * 2 * isqrt(n)
    assert k*n - d*e == z


\[k_1 \begin{bmatrix}n_1 \\0\\0\\0\\0\\0\\0\\0\\0\\0 \\ 0 \end{bmatrix} + k_2 \begin{bmatrix}0 \\ n_2 \\0\\0\\0\\0\\0\\0\\0\\0 \\ 0\end{bmatrix} + k_3 \begin{bmatrix}0 \\0\\ n_3 \\0\\0\\0\\0\\0\\0\\0 \\ 0\end{bmatrix} + ... + k_{10} \begin{bmatrix}0 \\0\\0\\0\\0\\0\\0\\0\\0\\ n_{10} \\ 0\end{bmatrix} + d \begin{bmatrix}-e_1 \\ -e_2 \\ -e_3 \\ -e_4 \\ -e_5 \\ -e_6 \\ -e_7 \\ -e_8 \\ -e_9 \\ -e_{10} \\ 1 \end{bmatrix} = \begin{bmatrix}z_1 \\ z_2 \\ z_3 \\ z_4 \\ z_5 \\ z_6 \\ z_7 \\ z_8 \\ z_9 \\ z_{10} \\ d\end{bmatrix}\]



POC (slightly smaller d)

s = 450 # 465
d = random_prime(2**s)
print(f'{d = }')

ns = []
es = []
for _ in range(10):
    p, q = random_prime(2**512), random_prime(2**512)
    n = p*q
    phi = (p-1)*(q-1)
    e = pow(d, -1, phi)
    
    ns.append(n)
    es.append(e)

M = (diagonal_matrix(ns)
     .augment(vector(es))
     .stack(vector([0]*10 + [1]))
     .T
)

W = diagonal_matrix(QQ, [1/(2**s * 2 * isqrt(n))]*10 + [1/(2**s)])
M = (M*W).dense_matrix().LLL()/W

print(M[0][-1])


But, it doesn’t seem to succeed for 465 bits…

The most straightforward fix would be to brute some bits of d.



But let’s try another approach, including a better guess of p+q.

2*isqrt(n) < p+q < 3*isqrt(n) (noting you using getPrime not random_prime, as in the challenge)

Let’s average it out:

b = (2*isqrt(n) + 3*isqrt(n)) // 2

Then once we arrive here:

    assert e*d - 1 == k*n - k*(p + q - 1)

replace p+q with b+x (and for simplicity we can get rid of the -1 too, it can be included in x)

    b = (2*isqrt(n) + 3*isqrt(n)) // 2
    assert e*d - 1 == k*n - k*(p + q - 1)
    x = p + q - 1 - b
    print(ZZ(p+q).nbits(), x.nbits()) # bits we've saved :) 
    assert e*d - 1 == k*n - k*(b + x)
    z = k*x-1
    print(z.nbits())
    assert k*(n - b) - e*d == z


We can also observe z.nbits() is roughly in the range 971-976


Now the improved solver is very effective:

from Crypto.Util.number import *

s = 465
d = getPrime(s)
print(f'{d = }')

ns = []
es = []
for _ in range(10):
    p, q = getPrime(512), getPrime(512)
    n = p*q
    assert 2*isqrt(n) < p+q < 3*isqrt(n)
    phi = (p-1)*(q-1)
    e = pow(d, -1, phi)
    
    ns.append(n)
    es.append(e)

    k = (e*d - 1) // phi
    assert k<d
    assert e*d - 1 == k*phi

    assert phi == n - (p+q) + 1
    assert e*d - 1 == k*(n - (p+q) + 1)
    assert e*d - 1 == k*n - k*(p + q - 1)

    b = (2*isqrt(n) + 3*isqrt(n)) // 2
    assert e*d - 1 == k*n - k*(p + q - 1)
    x = p + q - 1 - b
    #print(ZZ(p+q).nbits(), x.nbits()) # bits we've saved :) 
    assert e*d - 1 == k*n - k*(b + x)
    z = k*x-1
    print(z.nbits())
    assert k*(n - b) - e*d == z

M = (diagonal_matrix([n - ((2*isqrt(n) + 3*isqrt(n)) // 2) for n in ns])
     .augment(vector(es))
     .stack(vector([0]*10 + [1]))
     .T
)
for zbits in range(970, 980):
    print(f'{zbits = }')
    W = diagonal_matrix(QQ, [1/(2**zbits) for n in ns] + [1/(2**s)])
    M = (M*W).dense_matrix().LLL()/W
    print(M[0][-1])


And time to finally use it on the challenge data:

from Crypto.Util.number import *

c = 0x1e4433543ad3eab1d5a5490e33ee98c34785945c7b69dd0fd0a371c28e5ff45f6627ad0559d9837fd6439367543ff5670f4df4fd36cbee75950db62e51811f98e3f34db66b07196a5dfbd9867952d8e6d67c43becf086087181e5f78582e98945e5c8c08d754b998ef01e836729f9620cdcd2cc8aae9cb4bf3d8e4beec3ca8fd
ns = [61608417975397048843788515638593839325111098880518441270527767841153782846066445099077365303960932518098100778959123136871039627996767023258612684873083420234538156646585282154245553305607644427220207313162116929585370583379703086997585339296145409828300576290109728682441066135201997295424597733433471586151, 52084595054768217522676979342755393306305099169414947960508049057119329537162079071100773540172780699842974838973453517862170568297372572652378982794735495836797191260523386985555538123219596180065060457770169661533302156160201909218943628670173938802399175928847179180982290051008255643478089280887936398779, 121675354261226402523384817752122501670754379029920951567545832861118347020889141951034949457467042630795199347469665294677977729959566390358589470405088739543312116123816666440234661644847943610733959265939955886506334607329368744886743083353218982597246897307234102346047327550059519916639261619453107169923, 70820434096887624688036248070441718528107270792728727307197623356369639890276828895683705436125317302252834211775910545775001651922925694194466935425170969939539346172633115232030274859268960310846965871663926227518137713901150141826470260092611613639370170779217268337906342955347156686598981918675591938393, 82396665631738285668995082087133930047188890932442133336046256534530991902128696466596278088102928917626464109384091264437455382690583003229076491363732222934817133536320704449557698925700841043105303694696203472531025908797520768019280257689521302427077849286757365739653728248123114986191011560571298134089, 64885222129962661919689742957615146346855998523264787345799887210230045803423356080820154546050540728264000944692170729880161760807788699983366314269171423680987673788784023826885067996007133127166699735414920427997399513922777341273346196540175237091469555617281522541592407225697228219483666768990986901207, 130307595686638523389042871138355252466828093625912424932382409748014813151912412889866698513547588105179569464359905871041351306187955332098310075195714887141180801001191398677311128761953690562878908997464309620384635922453765468745206262477334243233099872249671186622159533482223573972729351847574480258349, 65386448419573832864151040666988491321490532636782967162806795276671017479566436411594017000387653366263378617189553041765586083217125727980734225153709370447270596363822524978426540069479632490507360491377612488876553715272119578498102854909764339676652952568021321118127618560269626549257296451954041925283, 131618812326147470215836136712095159211663684841466199972335887950664101678748935713203393931245541362772506324940879455504378545672259298894346211770983161798960234145317156224604949365110464634198678301644727985645228605590810190481288852412139519629077007437022950591320600450976104529132138396249413028099, 99041226655569332839951771030354960649881033648844611842019981984694036670092050113949713459076512100815903654289240773362239468428010238444408944822516190193861719380849620966232652503444079295871086550223067647300451354087943235559953597249075277760677450645744584993036921709483731953822197438848939991653]
es = [60032368056605168202792776655067640210910930719068898740685488293392455428589220656480049668823171895161714617099267690524276842795335016835073541061601545456195765907623303970146386500563913899580929779870429659650425339185233299118860275385880359287380867251468679962048998842668813298548390941601249105855, 15937444970326662770243305998311639639802081677519521519037892156989918335411343952028567001158781869582357356721336548356177945486289103616332672857562241745733313956089488246637981047367689313876169403573606972534488436195086998111247112950511965259280728899941655052549135516189815880662766290132607874671, 1958149621008109700386193021020256359555810444022322757777842537494487439895477039590251808463946583928481366538370998263830913239177109491659797444270949612728937519312683847609162235917948298810271512469482956117395111528004250206351805086758526770795159863075378020975086922955262230095667701740508170151, 6264211827826908864953215815104077572906230669747226774603059704547415338199956437981145121700015020477626176620200121575740530313039227764537541481272011717745292622796843631960318813842515397395192806936521180850750841260559451018598913158548097304919304754876270597286947644956943158352022152801127867879, 77541341309162852568860774868359137598587882474829780783306540898574011860779494674673722444562346968736216806881154962981695851598965376893425170303668270087989094501452417979429678869102952038600630142304872749698942475289176861137563927160985001506014089253274664444041660282426708388957971134224538326179, 47625666889348051674457306461777570860477708163951567694477110559722255361844497439523737482859577232793119885759760321686098657292699849459852343686370029321619072315457562131610624443702007471950020751311592439673932509558946203816066868221203483167079506399876187240483994566182748627389022243608934595071, 15517881429792452627724339825487038872077384939873021432131971858090290889497162855962736652640866521963165312583164013911162455865793567436833813352448640307756786561236246631146444590597902995591016928432988304077340670079503467394770901559567924809126517090243024890436892801283564005789256977822007581731, 62417639911670877600600895776941278119707067464948560335387709799367122896567813566638216057171867961437006927011778910808189676129022776796728833211435603542364704330783289218396426543693678813151580911213239650850603907199690825764030369692366216968117035006819175280930722880390482701178418013436415892711, 14318453997383587408499979509282945054981178882287936277795320451723285671391694914929520724692059461777785480850364952738183846512279857119933447174333240691522012746191524101263192457454032837995702952840654708026147079321112397181981380295129696518148352311994008219805602114421675331461920408832158576071, 45917328654051873455626365238806652384056265616606200025887647202756379007355041189714541493038574645714670682101129613041399879280497291675656671383417575172090283625761438606371062142083212903854592596935358334738253893062615061401134834123551055465985828525720791523020773994634134135284036947641526947783]

M = (diagonal_matrix([n - ((2*isqrt(n) + 3*isqrt(n)) // 2) for n in ns])
     .augment(vector(es))
     .stack(vector([0]*10 + [1]))
     .T
)
zbits = 977
W = diagonal_matrix(QQ, [1/(2**zbits) for n in ns] + [1/(2**465)])
M = (M*W).dense_matrix().LLL()/W
d = abs(M[0][-1])
flag = pow(c, d, ns[0])
print(long_to_bytes(int(flag)))
# hitcon{recover_everything_by_amazing_LLL_algorithm!!}