[数信杯 2024]trick chen_xing的WriteUp

两个挑战分别对应$flag$的前半部分与后半部分。

• 对于前半部分，相对于正常的$RSA$而言，多余的信息量是my_sum(p, q)的输出。

1. 函数内部是一个类似于扩展欧几里得算法的形式，而$\frac{p\ast (p-1)}{2}$又是一个三角数，my_sum(p, q)的输出其实就是${\sum }_{k=1}^{q-1}\lfloor \frac{kp}{q}\rfloor$由$gcd(p,q)=1$，数集$\{kp(\mathrm{mod}q):k=1,\cdots ,q-1\}$是$\{1,2,\cdots ,q-1\}$的一个排列。已知公式$\lfloor \frac{kp}{q}\rfloor =\frac{kp-(kp\mathrm{mod}q)}{q}$，所以my_sum(p,q)的输出为$\frac{p{\sum }_{k=1}^{q-1}k-{\sum }_{k=1}^{q-1}(kp(\mathrm{mod}q))}{q}=\frac{p\cdot \frac{q(q-1)}{2}-{\sum }_{r=1}^{q-1}r}{q}$，由于$kp(\mathrm{mod}q)$遍历$\{1,2,\cdots ,q-1\}$，所以，my_sum输出$\frac{\frac{pq(q-1)}{2}-\frac{q(q-1)}{2}}{q}=\frac{(p-1)\ast (q-1)}{2}$。
2. 几何方式理解一下，考虑从远点$O(0,0)$到点$A(p,0)$和$B(0,q)$的矩形（不含边界）。举行内部的整点有$(p-1)(q-1)$个，画一条从$O$到$P(p,q)$的直线$L:y=\frac{q}{p}x$（因为斜率为$\frac{q}{p}$且$gcd(p,q)=1$，这条直线除了点$O$不经过其他整点），而函数意义在该直线的上方/下方的存在的整点的个数，由于互素保证了分割的对称性（分割线上不存在其它整点），因此结果为$\frac{(p-1)(q-1)}{2}$

• 后半部分则是assert isPrime(e) and isPrime(e + 2) ans isPeime(e + 4)得到e=3的信息，此后就是正常的共模攻击，打一个扩展欧几里得算法就可以了。

from Crypto.Util.number import long_to_bytes

def egcd(a, b):
    x0, x1, y0, y1 = 1, 0, 0, 1
    while b:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

n1 =  22383505276728850137663455393633079686429238084408197797583598736760650003679916079650214682155847316076882725141374570460302120855096764538513229862795954147385108308900387069345779449915103629739531828669308609441662300053335686176325098105502184367217993677434252119478443682025354702266792166833784426453473827860172898402795550688610803859067811964931720104933533009885427642851084316565899573561455532590544434854937254255247776951478445378589747901688556058168321108741071828667007173309988355887026701162038060926192564221402875319027966998238769416711177531710785248139168620803548356938612241925380932722399
c1 =  1875398879251872719868560355474242782099823316126827285930474891901277579939760214035965660611635384718229823179041813298873206611283777203743667296506779512722783498577223248836597765063738710749848584774655051102678241594592558007326479725436015975654991768707911096986479210248598327791663633518053344744802610403121077377183221698216942452214704851555128817663013206210786245462794073787939188187310712986483732138020871433643195026191781442811424627811943780027182774192751752696323773367738469182341814291728285268560078864055278903890022779469276094336870186451714400643212890505086008116445776789803714054907
s =  11191752638364425068831727696816539843214619042204098898791799368380325001839958039825107341077923658038441362570687285230151060427548382269256614931397977073692554154450193534672889724957551814869765914334654304720831150026667843088162549052751092183608996838717126059739221841012677351133396083416892213226585669994317200050481169069680885500843210173755018864594875542790353631179885963409919776486038376299550585483719635362703712132567116865982352527948168359492173006364155730215536286166608846636096515412786566634124854053845424324140256891074367122913731031405668717883454810908906437441661786414144891345700
n =  74756662778639436562975999330825359536823289573050471468080861637518231366096792233276979250912851132414972772183499047007690364398808857720990298542543868595743284766520494638065061281311051858351451376628785343090755545582058510677441863939290967915943438156799259309049707455111457719863806587428279966913
c2 =  64621564085446025460866271759165566020214396004425177207823794891920404777580879190969580025066850950809371591382009507114472330028747960284692087131597290543485701418187494780905960234921865134547461595039127664304406560958535606724859673641460627603499570374549012252315820754504800780212190700219217569262
c3 =  27639843852370792448968858748200299412010418689028931967221527924245149194537914958726591682560452552544925542728165476332055988130978672645320390031855755873730679978008696737722666072210193829081412559508020694493801760998905958871041371292406719376419203098956321684168036111911615688064341797998359095922

# part1
m1 = pow(c1, pow(65537, -1, 2 * s), n1)
flag1 = long_to_bytes(m1)

# part2
e = 3
e1 = pow((e + 2), 2023)
e2 = pow((e + 4), 2023)
d, x, y = egcd(e1, e2)
m2 = pow(c2, x, n) * pow(c3, y, n) % n
flag2 = long_to_bytes(m2)

print(flag1 + flag2)
# flag{c4efd5020cb49b9d3257ffa0fbccc0ae}
​
            
AI代码解释