2021-鹤城杯-Crypto Writeup

鹤城杯的密码学题目，难度相对较低。但是也挺有意思的，可以学习点小知识。

0x0 easy_Crypto

签到题

公正公正公正诚信文明公正民主公正法治法治诚信民主自由敬业公正友善公正平等平等法治民主平等平等和谐敬业自由诚信平等和谐平等公正法治法治平等平等爱国和谐公正平等敬业公正敬业自由敬业平等自由法治和谐平等文明自由诚信自由平等富强公正敬业平等民主公正诚信和谐公正文明公正爱国自由诚信自由平等文明公正诚信富强自由法治法治平等平等自由平等富强法治诚信和谐

社会主义核心价值观编码，直接解编码就可

flag{IlUqU9O5guX6YiITsRNPiQmbhNRjGuTP}

0x1 A_Crypto

传统密码学题目，应该是个套娃密码

4O595954494Q32515046324757595N534R52415653334357474R4N575955544R4O5N4Q46434S4O59474253464Q5N444R4Q51334557524O5N4S424944473542554O595N44534O324R49565746515532464O49345649564O464R4R494543504N35

使用python的ciphey库进行求解就好

python3 -m ciphey -t "4O595954494Q32515046324757595N534R52415653334357474R4N575955544R4O5N4Q46434S4O59474253464Q5N444R4Q51334557524O5N4S424944473542554O595N44534O324R49565746515532464O49345649564O464R4R494543504N35"

大约2s左右就能抛出flag了

image-20211008200334880

直接求解出传统密码学套娃题目的flag：

flag{W0w_y0u_c4n_rea11y_enc0d1ng!}

0x2 babyrsa

from Crypto.Util.number import getPrime, bytes_to_long
from secret import flag

p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 65537
hint1 = p >> 724
hint2 = q % (2 ** 265)
ct = pow(bytes_to_long(flag), e, n)
print(hint1)
print(hint2)
print(n)
print(ct)

听大佬们说这是一道原题，我也不清楚是在哪里的原题，好像需要简单变化就能得到flag

分析一下题目，题目泄露了p的高位数据，但是只泄露了300位，还不能使用coppersmith攻击，需要至少576位才能使用coppersmith攻击。但是题目给到了另一个因子，因此可以尝试使用另一个因子进行构造来求解。

另一个因子该怎么使用呢？看来需要简单的数学推导了 XD $$ q\ \text{mod}\ 2^{265} \equiv q_0 \ q = q_0 + 2^{265} \times k \ n = q_0\cdot p + 2^{265} \cdot k \cdot p \ n \cdot q_0^{-1} = p + 2^{265} \cdot k \cdot p \cdot q_0^{-1} \ p_0 \equiv n \cdot q_0^{-1}\ \text{mod}\ 2^{265} $$ 根据推导过程可以获取到p的低位p0，然后就可以使用coppersmith攻击进行快乐求解了。求解后可以得到p，然后根据p的数值来获得q的数值。现在得到这两个数值就可以进行RSA的正常求解啦！

EXP:

from Crypto.Util.number import *
import gmpy2

n = 21815431662065695412834116602474344081782093119269423403335882867255834302242945742413692949886248581138784199165404321893594820375775454774521554409598568793217997859258282700084148322905405227238617443766062207618899209593375881728671746850745598576485323702483634599597393910908142659231071532803602701147251570567032402848145462183405098097523810358199597631612616833723150146418889589492395974359466777040500971885443881359700735149623177757865032984744576285054725506299888069904106805731600019058631951255795316571242969336763938805465676269140733371287244624066632153110685509892188900004952700111937292221969
c = 19073695285772829730103928222962723784199491145730661021332365516942301513989932980896145664842527253998170902799883262567366661277268801440634319694884564820420852947935710798269700777126717746701065483129644585829522353341718916661536894041337878440111845645200627940640539279744348235772441988748977191513786620459922039153862250137904894008551515928486867493608757307981955335488977402307933930592035163126858060189156114410872337004784951228340994743202032248681976932591575016798640429231399974090325134545852080425047146251781339862753527319093938929691759486362536986249207187765947926921267520150073408188188

e = 65537
p1 = 1514296530850131082973956029074258536069144071110652176122006763622293335057110441067910479
q0 = 40812438243894343296354573724131194431453023461572200856406939246297219541329623
mod = pow(2,265)
p0 = n*(gmpy2.invert(q0, mod))%mod
pbar=(p1<<724)+p0
PR.<x> = PolynomialRing(Zmod(n))
 
for i in range(32):
    f=pbar+x*mod*32
    f=f.monic()
    pp=f.small_roots(X=2^454,beta=0.4)
    if(pp):
        break
    pbar+=mod
 
p=int(pbar+pp[0]*32*mod)
assert n%p==0

q = n//p

phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m = pow(c, d, n)
flag = long_to_bytes(m)
print(flag)
# b'flag{ef5e1582-8116-4f61-b458-f793dc03f2ff}'

0x3 Crazy_Rsa_Tech

from Crypto.Util.number import *
from Crypto.Util.Padding import *

FLAG = bytes_to_long(pad(b"flag{??????}",64))
def init_key():
    p, q = getPrime(512), getPrime(512)
    n = p*q
    e = 9
    while(GCD((p-1)*(q-1),e)!=1):
        p, q = getPrime(512), getPrime(512)
        n = p*q
    d = inverse(e,(p-1)*(q-1))
    return n,e,d

n_list=list()
c_list=list()
for i in range(9):
    N,e,d=init_key()
    n_list.append(N)
    c=pow(FLAG,e,N)
    c_list.append(pow(FLAG,e,N))
    assert(pow(c,d,N)==FLAG)
print("n_list:",n_list)
print("c_list:",c_list)

多组加密，而且加密的明文是一致的，直接使用CRT求解，写个CRT的脚本直接求解出flag：

from Crypto.Util.number import *
import gmpy2

n_list= [71189786319102608575263218254922479901008514616376166401353025325668690465852130559783959409002115897148828732231478529655075366072137059589917001875303598680931962384468363842379833044123189276199264340224973914079447846845897807085694711541719515881377391200011269924562049643835131619086349617062034608799, 92503831027754984321994282254005318198418454777812045042619263533423066848097985191386666241913483806726751133691867010696758828674382946375162423033994046273252417389169779506788545647848951018539441971140081528915876529645525880324658212147388232683347292192795975558548712504744297104487514691170935149949, 100993952830138414466948640139083231443558390127247779484027818354177479632421980458019929149817002579508423291678953554090956334137167905685261724759487245658147039684536216616744746196651390112540237050493468689520465897258378216693418610879245129435268327315158194612110422630337395790254881602124839071919, 59138293747457431012165762343997972673625934330232909935732464725128776212729547237438509546925172847581735769773563840639187946741161318153031173864953372796950422229629824699580131369991913883136821374596762214064774480548532035315344368010507644630655604478651898097886873485265848973185431559958627423847, 66827868958054485359731420968595906328820823695638132426084478524423658597714990545142120448668257273436546456116147999073797943388584861050133103137697812149742551913704341990467090049650721713913812069904136198912314243175309387952328961054617877059134151915723594900209641163321839502908705301293546584147, 120940513339890268554625391482989102665030083707530690312336379356969219966820079510946652021721814016286307318930536030308296265425674637215009052078834615196224917417698019787514831973471113022781129000531459800329018133248426080717653298100515701379374786486337920294380753805825328119757649844054966712377, 72186594495190221129349814154999705524005203343018940547856004977368023856950836974465616291478257156860734574686154136925776069045232149725101769594505766718123155028300703627531567850035682448632166309129911061492630709698934310123778699316856399909549674138453085885820110724923723830686564968967391721281, 69105037583161467265649176715175579387938714721653281201847973223975467813529036844308693237404592381480367515044829190066606146105800243199497182114398931410844901178842049915914390117503986044951461783780327749665912369177733246873697481544777183820939967036346862056795919812693669387731294595126647751951, 76194219445824867986050004226602973283400885106636660263597964027139613163638212828932901192009131346530898961165310615466747046710743013409318156266326090650584190382130795884514074647833949281109675170830565650006906028402714868781834693473191228256626654011772428115359653448111208831188721505467497494581]
c_list= [62580922178008480377006528793506649089253164524883696044759651305970802215270721223149734532870729533611357047595181907404222690394917605617029675103788705320032707977225447998111744887898039756375876685711148857676502670812333076878964148863713993853526715855758799502735753454247721711366497722251078739585, 46186240819076690248235492196228128599822002268014359444368898414937734806009161030424589993541799877081745454934484263188270879142125136786221625234555265815513136730416539407710862948861531339065039071959576035606192732936477944770308784472646015244527805057990939765708793705044236665364664490419874206900, 85756449024868529058704599481168414715291172247059370174556127800630896693021701121075838517372920466708826412897794900729896389468152213884232173410022054605870785910461728567377769960823103334874807744107855490558726013068890632637193410610478514663078901021307258078678427928255699031215654693270240640198, 14388767329946097216670270960679686032536707277732968784379505904021622612991917314721678940833050736745004078559116326396233622519356703639737886289595860359630019239654690312132039876082685046329079266785042428947147658321799501605837784127004536996628492065409017175037161261039765340032473048737319069656, 1143736792108232890306863524988028098730927600066491485326214420279375304665896453544100447027809433141790331191324806205845009336228331138326163746853197990596700523328423791764843694671580875538251166864957646807184041817863314204516355683663859246677105132100377322669627893863885482167305919925159944839, 2978800921927631161807562509445310353414810029862911925227583943849942080514132963605492727604495513988707849133045851539412276254555228149742924149242124724864770049898278052042163392380895275970574317984638058768854065506927848951716677514095183559625442889028813635385408810698294574175092159389388091981, 16200944263352278316040095503540249310705602580329203494665614035841657418101517016718103326928336623132935178377208651067093136976383774189554806135146237406248538919915426183225265103769259990252162411307338473817114996409705345401251435268136647166395894099897737607312110866874944619080871831772376466376, 31551601425575677138046998360378916515711528548963089502535903329268089950335615563205720969393649713416910860593823506545030969355111753902391336139384464585775439245735448030993755229554555004154084649002801255396359097917380427525820249562148313977941413268787799534165652742114031759562268691233834820996, 25288164985739570635307839193110091356864302148147148153228604718807817833935053919412276187989509493755136905193728864674684139319708358686431424793278248263545370628718355096523088238513079652226028236137381367215156975121794485995030822902933639803569133458328681148758392333073624280222354763268512333515]
e = 9
def CRT(aList, mList):
    M = 1
    for i in mList:
        M = M * i   
    x = 0
    for i in range(len(mList)):
        Mi = M // mList[i]   
        Mi_inverse = gmpy2.invert(Mi, mList[i]) 
        x += aList[i] * Mi * Mi_inverse 
    x = x % M
    return x
m_e = CRT(c_list, n_list) 
m = gmpy2.iroot(m_e, e)[0] 
flag = long_to_bytes(m)
print(flag)
# b'flag{H0w_Fun_13_HAstads_broadca5t_AtTack!}\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16\x16'

运行脚本就能拿到本道题目的flag了！

flag{H0w_Fun_13_HAstads_broadca5t_AtTack!}