第十八届全国大学生信息安全竞赛暨第二届“长城杯” 密码WP

目前只有rasnd。fffffhash和lwewl要等一会

两个挑战

挑战一

$2^{11}$范围不是很大，可以爆破

那么我们有

$$(h_1 + 0x114)\cdot x_2 = x_1\cdot x_2\cdot p + x_2\cdot y_1\cdot q……① \\ (h_2 + 0x514)\cdot x_1 = x_2\cdot x_1\cdot p + x_1\cdot y_2\cdot q……②$$

①-②消元，只剩下$k\cdot q$

那么我们直接gcd()就可以得到q，接下来解RSA就行

from Crypto.Util.number import *
from pwn import *
from gmpy2 import *
import z3
from tqdm import *

n1 = 20098804536137619219686514167309396726748047486138910660783535397072336204543045296884414562669111355333649108073375784636854579127942452121723680253831687708659766918425077956960994410741580546791725051659704746522938196374093593625388255396856475109838541981938015078179639960951848655328587493252406061729335213121321614521762036759202902762638514676779823608948654699717242467789086616522847752837640764480951716926780998917185375172248801605625123163814120595817962632782558697588241842199880217961531159240908728202565168790837691247687704894622148010542055832895419733531942029960945822049736766710371186302817
c1 = 8635112706223755800262342570315586161298886846752609390941872966563808647340996222201689136085302316040668677484788593544820261175892561090213779421412404116635422412628642892245021797990969582874280656927535755922625892036157584162301335294097018827117277296999321677774653427181345854682766458393158305789160886756187221173335618036761149976577369027542445139779375166921973611612878793248626726005179659426782768576634952246842686717213435494830983494345920417864988588415851098698794791392670251454690465275525993785337125444502111406199468384988690143368528619781081660567052575769553955901884836702026839976200
hint1 =1448977614028423852146158631545257456863006753639133561131248140443997809862210211021228958719161440432760611567514203043059796208662094154012736889980349151093965972535034854176799623111132016341059145970621676197581506026499574131404405061636673659343344534401830495226538785326920904691599271089707422828145929450951741500738896876333341314
hint2 =6202436602208234144092035513220755605104154285721120659338124413593119793091141418187013041325965181367008841210268852693364626641399688500086075018760157893624663839341437140102780579600071623869516768209534094912445522678719383928731732666322301284110106734364999829220811325500230050138384727199838267936974361992666377317835917013391114163733377312484752384078306330298175580985377149429952124778444502445193031984207078185432101919485229535913849088202489151


h1 = hint1 + 0x114
h2 = hint2 + 0x514
for i in trange(1, 2**11):
    for j in range(1, 2**11):
        q1 = gcd(h1*i - h2*j, n1)
        if q1 != 1 and n1%q1 == 0:
            p1 = n1//q1
            phi1 = (p1-1)*(q1-1)
            d1 = inverse(e, phi1)
            m1 = pow(c1, d1, n1)
            try:
                print(long_to_bytes(m1).decode())
            except:
                continue

挑战二

已知

hint3

$$h_3 \equiv (514\cdot p-114\cdot q)^{n-p-q} \mod n$$

指数是n的欧拉函数展开减一

那么有

$$h_3 \equiv (514\cdot p-114\cdot q)^{\phi(n)-1} \mod n$$

欧拉定理，化简

$$h_3 \equiv (514\cdot p-114\cdot q)^{-1} \mod n$$

即

$$514\cdot p-114\cdot q \equiv {h_3}^{-1} \mod n$$

与$n = p\cdot q$联立，得到p，q

正常解RSA就能得到后半段flag

代码

from Crypto.Util.number import *
from pwn import *
from gmpy2 import *
import z3
n2 = 24002351273497161501305634432811557466164677979345282116491706458612038185773444678026683306815751595121359957389198822886323480682756988195588622833343259480329599776985583086874884410556671287702997032180506681331256603922224800542858120115645781467596929968424448393028893494279024518804060798667189602396351214100576676354600751445188041054429280612844725383504450696395827057889879000401300314618843818953500705785458740217345226082391054153637393901325311447131642793855422591937445369668752194230310739713949359192552839511537547475444948059347140771869551107605052095788242065374735183530861807068967925855431
c2 =7686254010914623979797443426125742550547977374444922695663838384960344471430291158459757742100723865301136211194543502499809917757042214457192851341262989816117347736066656082804418656338951438863996807374966659704001433427469039345923491054483535922002301867775850232151739846156655083628123194500496625183733378121552855327404803324805300540542256503223899764098261336993796331572987300411582324739484741370917053581159506500270508660955738498955293182048608847708600321447147761158233014901968284840333920456068543029582684695527088414692540235821302105123067862401820139183214026059541678895844438892340678634381
hint3 = 619584097417928068119384792483642969119149359681377940533683968849011572529997373790271862721152897782813793799240151873165650177683985990116362580375141260275486691837398884926430666522833128298134296921959337029109612221022571547206486445766121834780086400919304845226661083747536388649435912822521715514375210408852684206378500599100367831933159067406496322488337502324396561405550450182624884462224289128720320111770282917622239931764320474583909191076339298869696809816460539187982935347425122310442321953492186319005187910422095662949184442893339474499518491050975348535596874374056565037212046773015618663013

x = invert(hint3, n2)
p2 = z3.Int("p2")
q2 = z3.Int("q2")
s = z3.Solver()
s.add(514*p2 - 114*q2 == x)
s.add(p2*q2 == n2)
if s.check() == z3.sat:
    m = s.model()
    p = m[p2].as_long()
    q = m[q2].as_long()
    phi2 = (p-1)*(q-1)
    d2 = inverse(e, phi2)
    m = pow(c2, d2, n2)
    print(long_to_bytes(m).decode())