RSA Textbook

3kCTF 2020
Cryptography
ac01010
July 26th, 2020
RSA


Howgrave-Graham and Seifert's Attack

RSA Textbook

496 points, 10 solves


This challenge gave you three public RSA keys, all of which shared a common modulus. The private exponents were extremely small, and was therefore vulnerable to Howgrave-Graham and Seifert's Attack. The private key is no larger than 815/2048 bits, which is approximately 0.39795. Since this is greater than 0.400, as shown in the table on page 17 in this paper, we can conclude that we will be able to recover the private keys d.

This sage script implements the attack, and was modified from code found here in a previous CTF writeup by defund:

n = 12170190688004538444277411858659743698858881698522002560104158646993985233366286537140023919311475138247627293483294012428391264973961998717641256731743650816966630823200651379840685959607068295100050560483372204779059185916233606668058455492543750789590662887744463330804561435647720395428571207395720326720079784739378979190536116850099548129878814526898868252532680831715727722854511143304480680172052813141124420045611849828057723775363105949126828405455366200106404262310675794659470280643495090398585218024841176044368628727517113941678716688564185680961627362553111203039001198980515164358280669308454156335407
e1 = 3608925965574376523567945341556278002516414013521504911184984382205274952167864225371696017993914370497201512168776166664088733042670271646970202280312387281923684119807730941123751515160638485698825644259362763695807647636424870261387602647920252532625627698043754500477196359587280636895393200790995388403075695605752313259071472848947759665811971017441614507395695166977173983209874826569262567456954762013063380865150534725774724048932079149474773099227628235894219595993039786915437293792843467687437824528953466687440976745496029400371187996064849843219741352701174026683144995955926404403452468786948428940027
e2 = 2705742985834249419593731294742640629063082486092845443539270908653438835415907814640922583157596954837534793829979420920198220583127130141172579878212440120192417321752335684151522579530049628576946957043579231780623871429784888205786958275264941043957214384797910571377927751881376467152335343819159923905777819744174333126671522426796324838179520524018483919571215970759256674475827355541411323954244780923617745270386685895731319052600788632072228874066127098381849641952288244849313571762646260481179154523761739298818111645172710767353435965052896552293260158397774508443428719331456374349726714924857674679205
e3 = 3035365189985498586303047048784147960258852204370735950376858958412525602591256013408704341559429814208409740880540723564047453268194004007025515302654689487102249859432374152268384575758806644375008555596328108954751739613261097357911851867276625220692495609283168900124098676799207897772849526250849182230188000946516269730320060104809776594584791996622731993896557212016228453224349936398794285686351250712690093264997448606619172537355077652043467103166971300884698914802166607190765845078412359425449726466096602648615851255067426028168676632944926874766408639251537680297862420982004104687562994618386282503979
c = 8428440225372437159697731953040047552034760946696949785472254831497076019605441760668381296291759447497600405504562269104549915534101891117092326606340168399884372637000427767246446007973335837452013998684912761764510307152056346432612919127031634162077989869360717849451315550957073076040273291239841901635055739913150280146317663383345358421035311465389299247093408775682992619258004736599439564552486105106585061374815530581898589428950106020942797612406757368312750240904783591854877330620611395246954169095417676892061171148418509328414536101813085141351870212082214659362996288288403303642365539978759986883582
a = 815/2048

M = matrix([
    [1, -n,   0,   n^2,   0,      0,      0,     -n^3],
    [0, e1, -e1, -e1*n, -e1,      0,   e1*n,   e1*n^2],
    [0,  0,  e2, -e2*n,   0,   e2*n,      0,   e2*n^2],
    [0,  0,   0, e1*e2,   0, -e1*e2, -e1*e2, -e1*e2*n],
    [0,  0,   0,     0,  e3,  -e3*n,  -e3*n,   e3*n^2],
    [0,  0,   0,     0,   0,  e1*e3,      0, -e1*e3*n],
    [0,  0,   0,     0,   0,      0,  e2*e3, -e2*e3*n],
    [0,  0,   0,     0,   0,      0,      0, e1*e2*e3],
])

D = diagonal_matrix(ZZ, map(round, [
    n^(3/2),
    n^(1),
    n^(a+3/2),
    n^(1/2),
    n^(a+3/2),
    n^(a+1),
    n^(a+1),
    1
]))
L = M*D
B = L.LLL()
small = L.solve_left(B[0])
print(gcd([small[i] for i in (1,3,5,7)]))
print(gcd([small[i] for i in (2,3,6,7)]))
print(gcd([small[i] for i in (4,5,6,7)]))

After recovering d, we can trivially recover the plaintext: 3k{hOwGr4v3_gr4h4m_and_s31F3rt_4re_C00l}AAAAAAAAAAAAAAAAAAAA

Flag: 3k{hOwGr4v3_gr4h4m_and_s31F3rt_4re_C00l}