赛前

忙着复习(真bushi)，已经好几天没看crtpto了，进到nc之前还有点心虚。当我看到HvAng和Chimedal两个人一脸奸笑的时候就知道今天注定是非常逆天的了。

比赛开始了，留给小嘟嘟的时间不多了

进到题目里面一看，第一道不会，第二道还好，别的队陆陆续续开始有血了之后也是着手去做了。题目代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
from Crypto.Util.number import getPrime, bytes_to_long
from random import randint
import os

FLAG = os.getenv("FLAG").encode()
flag1 = FLAG[:15]
flag2 = FLAG[15:]

def crypto1():
    p = getPrime(1024)
    q = getPrime(1024)
    n = p * q
    e = 0x10001
    x1=randint(0,2**11)
    y1=randint(0,2**114)
    x2=randint(0,2**11)
    y2=randint(0,2**514)
    hint1=x1*p+y1*q-0x114
    hint2=x2*p+y2*q-0x514
    c = pow(bytes_to_long(flag1), e, n)
    print(n)
    print(c)
    print(hint1)
    print(hint2)


def crypto2():
    p = getPrime(1024)
    q = getPrime(1024)
    n = p * q
    e = 0x10001
    hint = pow(514*p - 114*q, n - p - q, n)
    c = pow(bytes_to_long(flag2),e,n)
    print(n)
    print(c)
    print(hint)
print("==================================================================")
crypto1()
print("==================================================================")
crypto2()
print("==================================================================")

刚开始看到flag有两部分的时候心态已经有点炸了，不过后面慢慢来也还好。

第一段冒险

这里的第一部分和之前的baby hint有点像，都是消去$p$,$q$之一，然后通过找与n的最大公约数不为一来找出另一个，只是这里的$x1$,$x2$是$(1,2048)$之间的数(应该没人傻到会去爆$y1$,$y2$吧)，那我们就用循环爆破出来就好，前半段flag的解题代码如下：

因为爆破的范围不算小，所以这里最好用gmpy2，爆破速度快一点 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
from Crypto.Util.number import*
#from math import gcd,sqrt
import gmpy2
from sympy import*

n = 30674147396610873860748717436320422168594984214597599383319886490718343137981647780032376011894648687988405724217382468391038980611364804249696330989432637193105449958399506831005111394416829797239955259476396309361216816465963705507153731318658231268616304885509337285257448898210894053853030696558503652640558764303071448067987410849515760242159506503426509835919722880835791784126949301193575970351312758142076213296051325654549660219208147325615445787578851251471400879571544162336087458525542025587186608394552914495841859285886557962614424797900647977098026581586926835327594098301555751986906882696857797050661
c = 8195695187254564481795657384087776400175811992598303085484593249053430277389200107699003406474935857713331820598275253685397212364011647074041441296008843099350122506192809243287174141744508170969545484734448764531534331315063847650389026891727114264717043420840329263134861352895070810594258844450504967681529448646489393064983590430126786730459677014802857768995782966056740903589272084602924087077033487049634993679900691857123250790695558353360705703882224481161800730192633852640453067850372667772248404149825889306761331290543416854128951186556515064772507857333967185985375537495335510639545083245930671021680
hint1 = 2733908067777653182251758492136741191186960145113951207115332394641726176482209349578179092456445177211725677004424930838217588015475745744005863621292629974121344847365532172890315918061409228537574516774927215531062116227864303088998853646292639525208555734683561021775756629197547043067716787781249597386972878883939702140960605830126032201
hint2 = 8975626311591360400877813622590946412583479831806130560872173891350740882009156391063722654750334924661340049267488727314680998581595508784216811960154173139856194456490770328374214470055600524147851803252311424435587700108735178605423587803297523101535441492923763243768724192181874665824191206388916445024210443510688945824841398474440641430061076018219163265275163485244959247336620307386804443090094555937763788112006760695994261330161621912586951926622371577
e = 0x10001

hint1 += 0x114
hint2 += 0x514

for a1 in range(1,2050):
    for a2 in range(1,2050):
        s1 = a1 * hint1
        s2 = a2 * hint2
        s3 = s2 - s1
        if(gmpy2.gcd(n,s3) != 1):
            qk = gmpy2.gcd(s3,n)
            break
pk = n // qk
phi = (pk-1)*(qk-1)
d = gmpy2.invert(e,phi)
m = gmpy2.powmod(c,d,n)
print(long_to_bytes(m))
#flag{734031da-4ade-

数据都是用linux的nc指令拿的

第二段冒险

注意到hint的运算中的$n-p-q$,其实就是$\phi(n)-1$,这就直接唤醒小嘟嘟尘封已久的记忆了——欧拉定理

欧拉定理：

设$ g=514 p-114 q $,那么有

即

两边同乘一个$g$,结合欧拉定理就得到

这里显然

至此，得到了该方程式

其中$g,n$已知，那么$p,q$就出来了，flag也就到手了，第二段解题代码如下：

现场因为对python解方程的函数使用不熟，浪费了很多时间(doge)，答案出来了还在不知道干啥，以为报错了 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
n = 12770611655818096647161782302078911333402831101183375872586198854848220448902568834282421862645550844927614718201781341905970424057298968077901453982255439123888662774842955774665812608475846447473879462841501625817098757408500167138659569109524726427566725125791538416173273023725471135692369118540084274964512850990806942609672470726910641262246271759386750125592065172773743394229753579355873486810529287241178062010144061253781598267199117007008995254498460595096336810955851991065383403655978931677906866087173910303765621506105333892254039208954381940156952865955944097141600535033220040433166800567094811537517
c = 11197331143585043545825006413021247200305045882150099471913804902448923074493954775043503469396608916282625546383950939477297667811909173627114102582059966186497848776161992258943269172765386959106303699462854776521451456686004187084374484899020017230931620253018853482944970887258198037818769485277661280959485534299205582469400683269680903475157416869331117131195545537967292467883735059791714017991784961291843402124163148368660096247083760298126873491143048367758927854560236627832354374142834138748808850127148740442303475426779663311277408789727125138894367831884009707596867462145036901706844761823563089338593
hint = 6793772318786619236460964974348973739231132253067622104641409349249473675153731718266918681463902848571664337867896528949538541537727923468274198624232900873948658575539747395048826224363049154531150342748839559926117271918245409069267822965433059664438469316298739362160068579421372767808059924216014758085287815123474907771108831098393549558875279424646958765101737835928533332430634126142940879616574240927210224645216553136929470895047777809172301666713621538711631942805059015383529625798788828399150286290559277590396107876575810080182506579094197001273883807980136049751735250338997179826118742675300296973593
e = 0x10001

g = inverse(hint,n)

# qk = symbols('qk')
# print(solve(114*(qk**2)+g*qk-514*n))
qk = 118314642415069683994380790593703097422841687480302802662342361729292152747498108411165694071673562669203146478195826741733429297921082944677156569841642642673963735218531873932109766498541716720407275771649688508360947786744548026318907104422575844642459559714445593077631008593470289183698859053266846359033
pk = n // qk
phi = (pk-1)*(qk-1)
d = inverse(e,phi)
m = pow(c,d,n)
print(long_to_bytes(m))
#4ea4-85e6-79c7eb106344}

两段flag合在一起#flag{734031da-4ade-4ea4-85e6-79c7eb106344}便是最终flag

特别鸣谢

还是得特别感谢HvAng的，找到了第一段冒险的高度相似题目，不过不看也差不多能想到思路，四舍五入一下，他也没什么鸟用。至于Chimedal,更没什么鸟用，午饭还不请客，搞的两点了才简单的吃了点快食，朕的龙体要是出了什么问题，Chimedal第一个斩了，然后朕从国库里掏钱给他的那个学妹治治眼睛。

我是被逼地改了博客（嘤嘤嘤