Dual RSA

本文主要介绍ACTF2023中的MidRSA一题。

首先介绍一下什么是 Dual RSA 和 Common private exponent RSA。

Dual RSA

对偶 RSA 是指对于一副公钥 $e$ 和 $d$ 满足：

$ed=k_1(N_1-p_1-q_1+1)+1\\ ed=k_2(N_2-p_2-q_2+1)+1$

其中 $p_1,q_1,p_2,q_2$是素数，且 $N_1=p_1q_1,N_2=p_2q_2$。

Common private exponent RSA

作为 Dual RSA的变种，Common private exponent RSA 指的是 $r$ 副RSA参数其私钥大小是相同的。即：

$e_1d=1+k_1(N_1-p_1-q_1+1)\\e_2d=1+k_2(N_2-p_2-q_2+1)\\\cdots\\e_rd=1+k_r(N_r-p_r-q_r+1)$

ACTF2023 MidRSA

题目要我们解一个 $r=3$ 的Common private exponent RSA，且 $e$ 也是相同的。

我一开始的思路是构造下面的格子：

$L = \begin{bmatrix} 2^{\frac{l_N}{2}} & e &e &e\\0&-n_1&0&0\\0&0&-n_2&0\\0&0&0&-n_3 \end{bmatrix}$

那么 $v=(d, k_1,k_2,k_3),v\cdot L=(d\cdot 2^{\frac{l_N}{2}},t_1, t_2, t_3)$，其中 $l_N$ 是 $N$ 的比特数，$t_i=1+k_i(-p-q+1)$。可以看出 $t$ 的比特数接近 $l_d+\frac{l_N}{2}$。

在这题 $l_d=576,l_N=1536$。要用LLL得到 $v$ 必须满足高斯启发式，可近似视为 $|\det(L)|^{\frac14}>||(d\cdot 2^{\frac{l_N}{2}},t_1, t_2, t_3)||$，即

$\frac{\frac{l_N}2+3l_N}{4}>l_t+1=l_d+\frac{l_N}2+1$

在这题里面不等式为 $1344>1345$，刚好卡在了界上，所以需要把界再提高一点。

进一步优化

我问了大佬dbt的做法，大致是爆破私钥 $d$ 的低位，以提高格子的行列式大小。但格子的造法十分巧妙，而且也容易推广到其他问题里面，所以在这里记录这一方法。

首先记 $d=2^sd_h+d_l$，表示$d_l$表示 $d$ 的后 $s$ 位，$d_h$ 表示高位。那么按下面的方式造格子：

$L=\begin{bmatrix}2^se &2^se &2^se &2^\rho&\\-n_1&&&&\\&-n_2&&&\\&&-n_3&&\\ed_l&ed_l&ed_l&&2^{l_t} \end{bmatrix}$

可以验证 $v=(d_h, k_1,k_2,k_3,1),v\cdot L=(t_1, t_2, t_3,2^\rho d_h,2^{l_t})$，$l_t=l_d+\frac{l_N}2$。

注意到 $|\det(L)|=2^{\rho+l_t}n_1n_2n_3$，那么高斯启发式可以近似成：

$\frac{(\frac{l_N}2+s)+3l_N+l_t}5>l_t$

等价于 $s>0$。但在本题 $s$ 要取到 14 以上才能求解出目标向量。

其实也可以这样构造格：

$L=\begin{bmatrix}2^\rho&2^se &2^se &2^se \\&-n_1&&&\\&&-n_2&&\\&&&-n_3&\\&ed_l&ed_l&ed_l&2^{l_t} \end{bmatrix}$

exp:

from tqdm import tqdm
from Crypto.Util.number import long_to_bytes


c = 598823083137858565473505718525815255620672892612784824187302545127574115000325539999824374357957135208478070797113625659118825530731575573239221853507638809719397849963861367352055486212696958923800593172417262351719477530809870735637329898331854130533160020420263724619225174940214193740379571953951059401685115164634005411478583529751890781498407518739069969017597521632392997743956791839564573371955246955738575593780508817401390102856295102225132502636316844
e = 334726528702628887205076146544909357751287869200972341824248480332256143541098971600873722567713812425364296038771650383962046800505086167635487091757206238206029361844181642521606953049529231154613145553220809927001722518303114599682529196697410089598230645579658906203453435640824934159645602447676974027474924465177723434855318446073578465621382859962701578350462059764095163424218813852195709023435581237538699769359084386399099644884006684995755938605201771
n1 = 621786427956510577894657745225233425730501124908354697121702414978035232119311662357181409283130180887720760732555757426221953950475736078765267856308595870951635246720750862259255389006679454647170476427262240270915881126875224574474706572728931213060252787326765271752969318854360970801540289807965575654629288558728966771231501959974533484678236051025940684114262451777094234017210230731492336480895879764397821363102224085859281971513276968559080593778873231
n2 = 335133378611627373902246132362791381335635839627660359611198202073307340179794138179041524058800936207811546752188713855950891460382258433727589232119735602364790267515558352318957355100518427499530387075144776790492766973547088838586041648900788325902589777445641895775357091753360428198189998860317775077739054298868885308909495601041757108114540069950359802851809227248145281594107487276003206931533768902437356652676341735882783415106786497390475670647453821
n3 = 220290953009399899705676642623181513318918775662713704923101352853965768389363281894663344270979715555659079125651553079702318700200824118622766698792556506368153467944348604006011828780474050012010677204862020009069971864222175380878120025727369117819196954091417740367068284457817961773989542151049465711430065838517386380261817772422927774945414543880659243592749932727798690742051285364898081188510009069286094647222933710799481899960520270189522155672272451
nbits = 0x600
dbits = 0x240
s = 14
rho = 2**(nbits // 2 + s)
r = 2**(nbits // 2 + dbits)
for d_l in tqdm(range(2**(s-1), 2**s)):
    B = matrix([[e*2**s, e*2**s, e*2**s, rho, 0], [-n1, 0, 0, 0, 0], [0, -n2, 0, 0, 0], [0, 0, -n3, 0, 0], [e*d_l, e*d_l, e*d_l, 0, r]])
    # Q = diagonal_matrix([1, 1, 1, rho, r])
    # B = B * Q
    C = B.LLL()
    
    if C[0][-1] == r:
        v = C[0] * B**-1
        if v[0] > 0:
            d = int(v[0]) * 2**s + d_l 
            m = long_to_bytes(int(pow(c, d, n1)))
            if b'ACTF' in m:
                print(m)

Coppersmith 做法

这题我的构造格的做法卡在了界上，于是换了用Coppersmith的方法做了出来。

注意到：

$\begin{aligned} ed &=1+k_1\phi(n_1)=1+k_1n_1-k_1(p_1+q_1-1)\\&= 1+a\phi(n_2)=1+an_2-a(p_2+q_2-1)\\&=1+d^′\phi(n_3)=1+d^′n_3-d^′(p_3+q_3-1)\end{aligned}$

设 $w=d,x=(p_1+q_1-1),y=(p_2+q_2-1),z=(p_3+q_3-1)$，有如下模方程组：

$\begin{aligned}f_1 &= e*w + x - 1\equiv0(mod\;n_1)\\f_2 &= e*w + y - 1\equiv0(mod\;n_2)\\f_3 &= e*w + z - 1\equiv0(mod\;n_3)\end{aligned}$

CRT之后进行多元Coppersmith：

from Crypto.Util.number import *
import itertools

def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()

    if isinstance(f, Polynomial):
        x, = polygens(f.base_ring(), f.variable_name(), 1)
        f = f(x)

    R = f.base_ring()
    N = R.cardinality()
    
    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)

    G = Sequence([], f.parent())
    for i in range(m+1):
        base = N^(m-i) * f^i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)
    # print(G[-1])
    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)

    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)

    print(B.dimensions())
    B = B.dense_matrix().LLL()

    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1/factor)

    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B*monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            print(I)
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots

    return []

e = 334726528702628887205076146544909357751287869200972341824248480332256143541098971600873722567713812425364296038771650383962046800505086167635487091757206238206029361844181642521606953049529231154613145553220809927001722518303114599682529196697410089598230645579658906203453435640824934159645602447676974027474924465177723434855318446073578465621382859962701578350462059764095163424218813852195709023435581237538699769359084386399099644884006684995755938605201771
n1 = 621786427956510577894657745225233425730501124908354697121702414978035232119311662357181409283130180887720760732555757426221953950475736078765267856308595870951635246720750862259255389006679454647170476427262240270915881126875224574474706572728931213060252787326765271752969318854360970801540289807965575654629288558728966771231501959974533484678236051025940684114262451777094234017210230731492336480895879764397821363102224085859281971513276968559080593778873231
n2 = 335133378611627373902246132362791381335635839627660359611198202073307340179794138179041524058800936207811546752188713855950891460382258433727589232119735602364790267515558352318957355100518427499530387075144776790492766973547088838586041648900788325902589777445641895775357091753360428198189998860317775077739054298868885308909495601041757108114540069950359802851809227248145281594107487276003206931533768902437356652676341735882783415106786497390475670647453821
n3 = 220290953009399899705676642623181513318918775662713704923101352853965768389363281894663344270979715555659079125651553079702318700200824118622766698792556506368153467944348604006011828780474050012010677204862020009069971864222175380878120025727369117819196954091417740367068284457817961773989542151049465711430065838517386380261817772422927774945414543880659243592749932727798690742051285364898081188510009069286094647222933710799481899960520270189522155672272451

R.<w, x, y, z> = PolynomialRing(ZZ)
f1 = e*w + x - 1
f2 = e*w + y - 1
f3 = e*w + z - 1
F = crt([f1, f2, f3], [n1, n2, n3])
F = F.change_ring(Zmod(n1*n2*n3))

small_roots(F, [2**576, 2**1344, 2**1344, 2**1344], m=1, d=2)

但这样依然没法求解。不过Copper后的多变量方程组经过测试，在代入正确数据后，是 $N$ 的-5到5的倍数，$N=n_1n_2n_3$。

所以在每个多项式的常数项加一个 $k_iN$ ，$k_i\in [-5,5]$，使其成为等式，再求解它们的仿射簇。

from Crypto.Util.number import *
c = 598823083137858565473505718525815255620672892612784824187302545127574115000325539999824374357957135208478070797113625659118825530731575573239221853507638809719397849963861367352055486212696958923800593172417262351719477530809870735637329898331854130533160020420263724619225174940214193740379571953951059401685115164634005411478583529751890781498407518739069969017597521632392997743956791839564573371955246955738575593780508817401390102856295102225132502636316844
e = 334726528702628887205076146544909357751287869200972341824248480332256143541098971600873722567713812425364296038771650383962046800505086167635487091757206238206029361844181642521606953049529231154613145553220809927001722518303114599682529196697410089598230645579658906203453435640824934159645602447676974027474924465177723434855318446073578465621382859962701578350462059764095163424218813852195709023435581237538699769359084386399099644884006684995755938605201771
n1 = 621786427956510577894657745225233425730501124908354697121702414978035232119311662357181409283130180887720760732555757426221953950475736078765267856308595870951635246720750862259255389006679454647170476427262240270915881126875224574474706572728931213060252787326765271752969318854360970801540289807965575654629288558728966771231501959974533484678236051025940684114262451777094234017210230731492336480895879764397821363102224085859281971513276968559080593778873231
n2 = 335133378611627373902246132362791381335635839627660359611198202073307340179794138179041524058800936207811546752188713855950891460382258433727589232119735602364790267515558352318957355100518427499530387075144776790492766973547088838586041648900788325902589777445641895775357091753360428198189998860317775077739054298868885308909495601041757108114540069950359802851809227248145281594107487276003206931533768902437356652676341735882783415106786497390475670647453821
n3 = 220290953009399899705676642623181513318918775662713704923101352853965768389363281894663344270979715555659079125651553079702318700200824118622766698792556506368153467944348604006011828780474050012010677204862020009069971864222175380878120025727369117819196954091417740367068284457817961773989542151049465711430065838517386380261817772422927774945414543880659243592749932727798690742051285364898081188510009069286094647222933710799481899960520270189522155672272451
R.<w, x, y, z> = PolynomialRing(ZZ)
res = [445184803042669258060501460666337065409748819565700522985480758464046142444356649661305417601429666089483499518658000235917600544658554505463388554580690771682386525288891628152604328872416827563568043257678021919666327728258909578837878678563263832310846277377335086723097361018253701939607601480600951184350983551299218494982593878862185307778337502648118262875928845114898381254148087445691471055526775257675877756717088114821176127228518164430065621416985678645388005987014332996337092826605164140469164061094908684896407008632891241704352270448574646732437102833489647211223052624179469917953153283093781986140763523242638722776107965111049008032349335332529760730478646863872950926642380702861512866177287389235423235536178751221481798050568757026144811984440814692322629488673907641939773082978464341911491902202267459437729975405680400047292582854013292083957407337287683473773286096263542259203254015144363522498287771864347999918633214618854623567785647212494428902754698020059014857503041921489767478569881128012286980346153234547099052220270216978586327151130121220172440364917302193129335757102546834823350735911769005775186309250706911293562609321330089975923910087245969383190954689866182797457903*w + 226479721041660818883188767515818343215196565270957094909659915583803447887777463558344500679035662454367401516691383780364003620594481885123412763694449012247499474218458417197061284799083900855694333937979864088123490264870114564164070998136867268028843613462197392431523556017063796473666617951999600184286080696400550191976245171501192201569115438415276763064860932387028927994589182882761250991649186794598180348581580308789096989374032325410980406305435150677504069511101450303036004837937156295602086487135213653967356401522414816537538896169987859734798381341776385784759162201729818410039021136964910453569524510402186549245171021355000192947329417534122001345245787418814001325050527269080008259482862262041781126919218431771325144858011937811752612488658005426042992622604021240557202634144013619711845720613495497869032149895374341522183536726464649688024000052968673923741161672908959886885161237055657866122498132300762138587267335173999105657266997365020865217899668*x - 187475363490695410093541673915587736696173934440183887684556719006996516853631119047797283187253205221306379838970509884923520558839666758279229175652358231812295080881430820801257442963557748278888082518460629077308396947697734677771279846415700792485878301861783733516672709470865902206751251339773772959383201851161664672335804831576639491525720110321552904635926781217560129986324207716424684621013908178057770164682089883706013176884067436331340800448272130360766319789201024388832076974493482828404981355870739035626533345852540670306571745121363793913082407758387470298294863818198449840919983747724583137866217628955073630556195621735784409521673514661711482607001177901272488127300681536163113211477567375952623711004479488426427308698053674054985364184063551533276346289666996235817035241432989751480645586558377798620351721440019539604328641262389859541105677691159884175407251421153924420581636210664360965161153553850186163384892845092881372764556468458559899392557982*y - 22622013374672870622129116216509893688901329833755615202298761219672102420574921135049252695678282868581495872661805510212597630977163581768088332430176373421544478058085164430963815722424347692081677184834587805287322221149376228330698643633004436162167671720233494993792004028586071295878698098512635778605650501928678817087035325888677552611103729731845744851996796366532049074906759280382835368896756741737416581521888968454794675822206074083810474020024996723858811975425385002095933807178893473110117220609486831004177325418910515926419184665475827727855080396925848975639805690710478018171836485845457382125502408998779101156560657039107870469221051569391513199962502062438130405843201376568711355710992204823017287889962358261373663187140696585951223584956903708087954547641614691358454089709589152011741572601040600393027293443170836586593320525673565570721249032096338580669054055181728441808543812685830939063830665854233104292041464318592112684528060456970511098871166*z - 16382344176292538167517977383720712830121300997017592022804435357134828613571423375497964796104174364479525805059068385227885430777651545076095255611914407013659915278942431964840026113101804884724574234684647205527771096023003658062092508088162039380797639880180163921058842517611822971036668513713191446297228343310206702553405014035875157432291598361878113576937354802936748933358215885953731001738521874802993602377601456628289136667758814995829131837138023592878937746475040912107994056264779994086987910654987787336645730250963630304547966383148238093860893186463066510824492692820890550947200903394869933577804472448333817532414742580107912956434851303019005538282107455103382791906644356348183692294302681266140128024776585083524172972817567170816024719637550184678691785295410313381713303001434716219458561454077098855653135012183965331261574938401224576197073329712451167664856196573307024494981213705465961897513912596342870910333025762525620208182468449490454726470520, 284134380199453153452313564118634762266305010076882480586495407448627019469189780790636048505259611924218159727700278435266524517531370239695621100241394530391107051806716446821740495388104894089733967713006446541245690143068670393693642277966728760674477203531973638072485516426602560918428730297488011950845924596241470908359114909354888481131555800673237470833507610250335671354741216435530635819178021614455949921363157150825114563541266511829618425670026387832972595931018581581787130201519511014543802825455922224288251102146438683660433672276047733341002996119431644014964588205635307071466255223838968105573857283039347412680687894693048045835387381074614085241418811009607687834017976379519063769559966000176269959477238875869836899713160443750567416958181140120979996124134460171403201056804057336607130170523490142086656772602354215432113782242247911776077253840210236815599155307748347170906979097359194571422797970311750035888234353286058040568891443507585646567861940665396735494538576880116441332971890906888500012826015145114909551032935130773181139475576822866526097787777298270527509957429867021800482325853314993546899405121450976300867250768236357255108197574155493656208245768574133847072431*w + 59007148790516044238083459094487702202681784924100812899405159432953281217328788297507429997762105954184813760693557843608072035195197400449020018437693133401708884393154518692505872571604500716247872343365146902343537814440861538120971184023796808507062455986494766266011183104135932501591885976579382269245787840772416881899893279387505583674796164663271766613621738053052935407018873330141045332064098121052026322242833881820876161063360252449643039424529101391799193931479925516401095004658739700607699911012926845407320288306049159739725755794105078473589560498660372465034957303141701162879705133485546668766425531768910382612478505849253776570152699401547234746171430619059069797502561987954753774466056515970883140028271417513001240586289308492406140942846842505472111524366886765250228237079872211497380026063361030551309464728330761172991714026291046968441682310903574969104684414705828318453784056941097781705796434316130657652579176645895583318600315749061268366746917*x + 42900228349060996011429258420311551217813242734661265969484327450654266278099279906839538118951872737041629262185031847517366913759605410804237090330956385951945660922942892954696708058950229135811315288781568154743447917215502212897429687386914950981759856588973878856677006064697416836865252718925132887963707018365934638091396647516925314261811987995889885855301096778082610018959652947676357399212256546324468496383458479628954467519446091006064708892767447706563088492746799500175530841181716588042017964777370082560396042251925369586263053773480939625841199364394585760064443539809646993324177619865020156271775858434604158244802508177745411631245652222246427090964424575860047781193174210099229750507558807398046298571116176016855372780322632137145646418216120432662051539512614349346890290999106645948042371044257545474240728747368312971824802791864198222544059593603803491963002465317484192120828739521633611419107907289012055394426665229807560314870288259525885959585550*y + 407933476742648296781157784217775669927420088988838987394788702697594680454274649879393832272892057183159381671218502206372414734507847526899326941164320092754315438755484115368241194452180847063938834267771371636138134691170489143600728095051774808056079559321725505527348937495065060460567585032353219865725013150535156900870677159570534017920631751371257418636970332672334953257213771548629576860630127531610270525174018809357700314075551491120872355149665317124637606685841019015593185582599578897239207838101035384144571108958958353613909126655476739268525751375575469791985513481005242230661304382340830330148996489618646028577356809901641009420731298403888818951775544399719385294559551958950498180847126331111863770299992885143514185567432174830684859019354167456176559586312529965505877495495829912584682938558194437516112881907991505234353927323632125355786428176745783630550452678121386973732944500573984793837720059565311150359523562529977611990131423887855558368733359*z - 509840853882225337030670501732574923347915116647601066263678189581202227949702718083740800389606035874385824694097091897497853683462650338152584049932969612107969984071581527015443775082735576915998021899918086693225120422826852894619128966462486567544901871897194150650037126663898409799024723727857735022934508009673508420861967086474964915857239904030419071105893167503470498683192297826446979591906482198986765343800311170807530942658357834576580103466961866222999889110067744032169811428440035185888925713891332312112287439516932882939897936223062757367956511238630428017084914323956590386865187135691397155187197879822160569434637823928640197622129650027682480788911399594638502873255288157004481705820741654480793208899380478673370798934044115460236646380417130394310722650192031080102996023574808770030105335665813013541663075383690579379170444141787370546772170081253162091618139558144699484307557297036716186962624401170453863406529404405680755623602027896442712695065826, -577207792437065823346595354994801229525491674108004057708913057963106403239568724750334085475474981919065753558287636654346559297915856549919482997227033134573710649182344470914036614392994943275041482578362800185543579664168615404688595665754461315645521450426290075193098715288888398247017770958849601526521213654828861103691962299798274613679079965168709262436699043416473222701235743906585550753098322149513851447858125245288373083955945210855334157093149391564125207792672919584393067761887212819841183652602674339376811853665206287013624216641235045236736227792504598890817543813969686887701143842733119625519741478953624825025160049343856503979274554727356458781242275993840811853155871708798084801568564027638630766896706824523761613050421150888862493389311799246246217759111169088132984337599968396130183604490970968872996156690335553025148099370468846172988535729600345252866254292323669950555261788459757173582922162073408830744017732980142131097091769408841837970219846467077185419162794503108315718876061334329454440178632916972773922723791925888968358469790806127171783877700958985097189939405299457668563594722447862462826242403451719910028045687577075100569282181283984006075361735383619258151374*w + 216439773618546757679569036488044719847743902612008965794966625537585013201744761526753652408493281882283329183499528970374469264462454322900695277869211515261150304198711925976570359280880290183160130212808198304291601587846632813340130570030522669279186313404485023839376474433334983866431010927744364179865406074898052116051713226548254285685275869128151593631612198311119385683521226168812205819053883885025109077330096517366354355815425113338332499694419517490599899726184880155269772691119377556267148400006934255271868369640563440169680911662041594382642114553229618323302455270197445046371977446293277965995578234869250349710313927442062719484090219303139901690203365108967838609173932348637552831227815614322301414736722858834063765609822353190137756295761799770433576846701302582533823512058592528043712664586674675365203505905358004967198988576867766838098404664394555780765339730316954790660993508311333667603390364117472900201607443444826779248799170311082005146311650*x - 139266632266166038168820552368321975673215593943851418982076191346201185933182528575873257510295991353890777334633737223468950878784184706090666949070056691274007703189558632648275092989241670767174568395337524024252240202542040336376731007399416351817934876217488582960143980229437171076397888334549809733664420790049365593937189162489651836627399836605619173605403873975201479363718547425911988893341070944650161022137255308302800661923675557123023661537185930108265291891907389172727292162233596007129186992386818204988681677922357244866940679937302780844492025505247728860966033124070916591500030541167980386695240933926223844445152843183063027260426464661439851970482016052637005335696075829571450021051926730952709967037148543677841849822158156103508864730855422476544366690576937792590964104317267877557463417692309349190251199486244709638728070938230567976594317374672348156717419210432092512477018669833747660017385563513074919884042867399139171772500604195092145137281937*y - 38484447898657430152546830647676528306029966494318454553049687977297891154372840395076297162669100054845116419787885803412666508543020020626985651770176240846363145281127843391589075686269535307373765099797104767498680388924340980867745746358080870787161500243617077116385700813044127485160849084485483492482219219156181300308235965365199073758250006168271507142165118951173505513949742453247707003460331946935950847295367943942149340256315045392943947535697020161134854366818895636928245680370491277373202435665148889021799754559546393838628351387143962769762579482512368329694387991909399197970553189191239311468937113114038019164931591358979258690166575730141828951261126530168353435531545204089757439312801689264484528603456156952689361997091283879827694703170799994317547910503543997649874811980060380877611021695805940678643055491850686878021311292167192518131855626373873160998721987480775478447430308176159856829559064611324059522261606320396296817001846462488993770653431*z - 38688693453723289358201653472046215868498342173839092259840746214085936114189392555804097735528190473547435429077905943492851877135249596183042677028978583140779455728025449936706190605369084108611796717673569512540680996380251496095653816273025446674089936943379363762846793390853685304872273508709070953718766065692505221806288098693403375299626026354260912884043205384744400805852936289652509922252480993438997207897473265121404353635434510822364890621536567221199753467458595345614234848515290271764758971954967161261386937158659801464111880337594850768387509565469521132642034154217129256901393715934058267831400187828988486100229492900020433533497178911558220768460222526162479837946311314976345370863087194105106919096118158203532553790572913206801196861735577299571662245620820792292984595761264269608638225198559385496309250927262608450449606346470006343372231663348334463049198532404086799736544530301426150756445735993073920795302969725291310659296719653500866238376282, -296897148223608102853967633699177508033340522337261842572893982981825475705067333030586537418988020458801811673283586797574466327881515407370308091721222519044380330733815379361112515352098930453810543246136518537428496480695555085931054874084510890704163195008025898309958428985274571903731428975184245157056728878724565063418538910061636022647314693134340114299299162273766261929132791368451849987961402212407399369379280808358086156434870387488207540888552847391435032889052036589118445463827897117313491379924919473008241022091450278861670865788265786390689606469076902313793023527900310314095152418130034839432547258433873896558684166230439793124663182339896299504439854310647246849506980871080175408749469001073687317296599999558374756795447526645763285515663349276757325349409424371282518631175177890366755789081214478411699757862631386373975538737228717488213901148210448504969316713473830368817214666648522464821106583390808332639354457135172639288040929614309790763084587859326897667346654638108345992249468603953979805606996074310740799345217445259673644728155426877293106502347602398910803098723808751803914442905303063476707530332857039252713947890313242681306576998443053011499127433496376419826945*w + 409417967932965954946849706960892826855661592393819534117435579000239531597101848877876776024075836063550324995149322696100039634212114862100289091077095005688527698478792229037818201298858639203520931498166450626989723399505042888411576241516502651301437581499870660667281865159870216641434479412827799870280068504097604184059942842703141227181174984027644704182336415253130970408205938853892625123746417493917735085529266330700034396989932553394520467716844961610504732650619829986483297333629159473121264822228298658575967899791562286497824978483649333164949549039914995348920485417656371680315330395089633797266631102146546080386683072649889337311770842211050327079795011723874651450542264566282031537650907590635216283939645762359332469133948170902008044186887372209503462334056781262669195080383176771778183987856831168595695253673143929973280509094409425913750011003494447610751889362206348480053884553482813787455834593984294583832131137400166144928380242513390766725766822*x + 686619589057611758421148786098360121849241418048284085433776928506123962993339013498872747668086426477808022843522303856357410598213618397123396250456436433473609124661793489501030676298732644625201288607303779868901949249854063015764030243100286577750483580523424887077014793319116133456163961411310132398796245059944671090287154792932606391148767191035359405978714672726495727302569214735045608553140903970022296904318130935274449188304459353772842426554393461987919580694763919731330550345468304198023062307902769396452845485053603061005930787632601464457740693865192906429426061575882993650102863373850335855133325557103132647532562812324641135303414263267674574133807461870013233659052597558069438997959397996185204597638668217634669852163189726018919776541851841746194937573519285238421428358670064966437489993574401978557232708849136304796809650558794266149072727448054368699046805119411494335130663907679003632575181017932020326162004987191471582017551987443061909905936056*y - 288023635681573379604061524997346358596239113696312654228313143554145558821423088902357529437412887628036763937953722874782241351655994045705607412797093603298744376719596799726161464092383520531344188778839502683266371087557470313404153352915236528302163895086218191402766224764005901294246061256733456534969240042694869946969305951159980731868527220660017226904545970574992254707498351346580756933658044374654969256688332557577755695151477740508599441169705384789414174579218101764900929496400713610350791331555751077384985109779100091889921144787194989882030165012208865153559230155326416463546293902790640295007629366329027807654887693809349346335003733735809139729639423970655895080391703127682224936079473504052192649149082409207712132103618094311274634220499528658822141999128413935353767085696011085109787574559477481163969142534594375025559038601448618845531863663471674035475136341226384146743337167356055901908975964821590508690096345564441120085685488533192235960079105*z - 808013921309004333763936968061906590108663896745790965322899363952217935769017773474391994254749374913321583900717903677675208880769739213518077928736437835863392446420988918812687413505207763297378031326630727812625301561801635590771453131701552700749757266937077356341530433714980448803352379567404475734107073521347405327377791684475766886461414954402986883256505117404634443003276802242357476743229277089285062733159064708396727890142914166658763453101533038809010138766165647952912918182696750060793535798575316977643828275066065255613834621329055807740660077892899036624787316838212948866871899866149329357392327292920650920264358191165181126280181371742915761483963049623231990029203158996669245599530832082768228232429231570786290189193519802609653186508239685296876257908447652565736856353357230653105886406871755665988958819987685859744531121051755073217290874788077142274323558140391458668441211293805761518122039647094724401304039779027196606860246741423260440671623773]

N = n1*n2*n3

for i in range(-2, 3):
    for j in range(-3, 4):
        for l in range(-4, 5):
            for k in range(-5, 6):
                H = Sequence([res[0]+i*N, res[1]+j*N, res[2]+l*N, res[3]+k*N], R.change_ring(QQ))
                I = H.ideal()
                ans = list(I.variety(ring=ZZ)[0].values())
                if all(i > 0 for i in ans):
                    m = long_to_bytes(int(pow(c, ans[-1], n1)))
                    if b'ACTF' in m:
                        print(m)
                        print(ans[-1])