文章 - 2024 鹏城杯-crypto 部分wp

babyenc

from Crypto.Util.number import *
import random
from gmpy2 import *
from secret import flag


assert len(flag) == 42
flag1 = flag[:len(flag)//2]
flag2 = flag[len(flag)//2:]
print(flag1.encode())
print(flag2.encode())
m1 = bytes_to_long(flag1.encode())
m2 = bytes_to_long(flag2.encode())

def e_gen(bits):
    e = []
    for _ in range(5):
        e.append(getPrime(bits))
    return e

def enc1(m, e, shift):
    n = next_prime(m << shift)
    tmp = getPrime(256)
    cc = []
    for i in range(len(e)):
        cc.append(int(pow(tmp, e[i], n)))
    return cc

def key_gen(nbits):
    p = getPrime(nbits)
    q = getPrime(nbits)
    return p, q

def enc2(m, p, q, n):
    c = [pow(m, p, n),pow(m, q, n)]
    return c

bits = 6
nbits = 1024
e = e_gen(bits)
shift = 310
c1 = enc1(m1,e,shift)
print("e =",e)
print("c1 =",c1)
p, q = key_gen(nbits)
n = p * q

c2 = enc2(m2, p, q, n)
print("n =",n)
print("c2 =",c2)

'''
e = [43, 37, 53, 61, 59] 
c1 = [304054249108643319766233669970696347228113825299195899223597844657873869914715629219753150469421333712176994329969288126081851180518874300706117, 300569071066351295347178153438463983525013294497692191767264949606466706307039662858235919677939911290402362961043621463108147721176372907055224, 294806502799305839692215402958402593834563343055375943948669528217549597192296955202812118864208602813754722206211899285974414703769561292993531, 255660645085871679396238463457546909716172735210300668843127008526613931533718130479441396195102817055073131304413673178641069323813780056896835, 194084621856364235027333699558487834531380222896709707444060960982448111129722327145131992393643001072221754440877491070115199839112376948773978]
n = 16175064088648626038689748434699435826247716579187475966092822028609536761351820951820375552440329596553448265674841223230257463367834546091974959931391707199002842774795702094681528411058318007858638798643010942408552063479863545047616823056802010158288409527763686086960916160949496083789920012040215745627854092010308869223489833074860062054019221397227691063339148923860987250696934050122115972982286012688955816234717242567815830341836031567275888691320640526306946586793028267588302696611724356566003447616419092371914903382944112125852939011729294400479171568234647164730191643282793224422368321464125847020067
c2 = [12053085469218650692076937068797478047679005585690696222988148891925249697123080938461512785257424651119325211991331622346111396522606463631848519999574540677285771456451798811902760319940781754940936484802949729402283626052963389539032949160905330315285409948932070460455535716223838438994608837585387741418172014634472651248450564788332400265295308803291229281839428962457585593065595521459963501453576128172245723315811398209056633738967993602668795794847967331946516181453804430961308142497659799416125763566765485760600358126127595222197324155943818136202233758771243043559460620477085689770403810190118485243364, 13878717704635179949812987989626985689079485417345626168168664941124566737996226347895779823781042724620099437593856913505609774929187720381745418166924229828643565384137488017127800518133460531729559408120123922005898834268035918798610962941606864727966963354615441094676621013036726097763695675723672289505864372820096404707522755617527884121630784469379311199256277022770033036782130954108210409787680433301426480762532000133464370267551845990395683108170721952672388388178378604502610341465223041534665133155077544973384500983410220955683686526835733853985930134970899200234404716865462481142496209914197674463932]
'''

这段代码实现了一个双阶段加密机制，分别对一个42字节长的flag进行了两次加密。两段加密是完全分开的，所以比较简单。

enc1加密

def e_gen(bits):
    e = []
    for _ in range(5):
        e.append(getPrime(bits))
    return e

这个循环运行5次，每次生成一个长度为5bits位的素数用作加密的指数,放入e列表里。

def enc1(m, e, shift):
    n = next_prime(m << shift)
    tmp = getPrime(256)
    cc = []
    for i in range(len(e)):
        cc.append(int(pow(tmp, e[i], n)))
    return cc

enc1解题思路

我们需要找到一些指数的组合，使得这些组合的指数和相等，从而消掉中间变量 tmp。例如：

n 是通过将 m左移 shift位后找到的下一个素数。

tmp是一个256位的随机素数。

对每个 e[i]，计算 tmp的 e[i]次幂模 n，并将结果存入列表 cc中。

但是tmp和n不变，而flag在n里，我们就只需要把tmp约掉，我们选择两个组合，使得它们的指数和相等。第一个组合是 43+53=37+59。

43+53=37+59
53+53+59=61+61+43

由于 tmp^96mod n是相同，我们可以得到：

其中 k1 是某个整数。这意味着 (c11×c12)−(c13×c14)是 n的倍数。

然后：我们选择另一个组合 53+53+59=61+61+43。

同理我们也能得到(c15^2c11)-(c61^2c43)=k2*n

再将得到的k1n和k2n取最大公约数就得到n了，然后左移310位就能得到flag1了

from Crypto.Util.number import *
import gmpy2
e = [43, 37, 53, 61, 59]
c = [304054249108643319766233669970696347228113825299195899223597844657873869914715629219753150469421333712176994329969288126081851180518874300706117, 300569071066351295347178153438463983525013294497692191767264949606466706307039662858235919677939911290402362961043621463108147721176372907055224, 294806502799305839692215402958402593834563343055375943948669528217549597192296955202812118864208602813754722206211899285974414703769561292993531, 255660645085871679396238463457546909716172735210300668843127008526613931533718130479441396195102817055073131304413673178641069323813780056896835, 194084621856364235027333699558487834531380222896709707444060960982448111129722327145131992393643001072221754440877491070115199839112376948773978]
t1=c[0]*c[2]
t2=c[1]*c[4]
t3=c[2]*c[2]*c[4]
t4=c[3]*c[3]*c[0]

n1=abs(t1-t2)
n2=abs(t3-t4)

n=gmpy2.gcd(n1,n2)
flag1=long_to_bytes(n>>310)
print(flag1)
#b'flag{3e99c26b-efdd-4c'

enc2加密

def key_gen(nbits):
    p = getPrime(nbits)
    q = getPrime(nbits)
    return p, q

def enc2(m, p, q, n):
    c = [pow(m, p, n),pow(m, q, n)]
    return c

看上去就很简单的加密，唯一的突破点就是用pq作为指数。

enc2解题思路

看见pq作为指数很自然地想到费马小定理，我们可以用费马小定理进行变形：

再变形我们可以得到:

又因为n=p*q:

这里的k为任意整数，再将两式相乘：

这样就构造格多项式，然后就只要在sage用small_roots求解就是了

下面的kbits=167，只要你自己生成一下flag，就知道flag2的长度大概为167bits,用来缩小范围。

#sage
from Crypto.Util.number import *
n = 16175064088648626038689748434699435826247716579187475966092822028609536761351820951820375552440329596553448265674841223230257463367834546091974959931391707199002842774795702094681528411058318007858638798643010942408552063479863545047616823056802010158288409527763686086960916160949496083789920012040215745627854092010308869223489833074860062054019221397227691063339148923860987250696934050122115972982286012688955816234717242567815830341836031567275888691320640526306946586793028267588302696611724356566003447616419092371914903382944112125852939011729294400479171568234647164730191643282793224422368321464125847020067
c1=12053085469218650692076937068797478047679005585690696222988148891925249697123080938461512785257424651119325211991331622346111396522606463631848519999574540677285771456451798811902760319940781754940936484802949729402283626052963389539032949160905330315285409948932070460455535716223838438994608837585387741418172014634472651248450564788332400265295308803291229281839428962457585593065595521459963501453576128172245723315811398209056633738967993602668795794847967331946516181453804430961308142497659799416125763566765485760600358126127595222197324155943818136202233758771243043559460620477085689770403810190118485243364
c2=13878717704635179949812987989626985689079485417345626168168664941124566737996226347895779823781042724620099437593856913505609774929187720381745418166924229828643565384137488017127800518133460531729559408120123922005898834268035918798610962941606864727966963354615441094676621013036726097763695675723672289505864372820096404707522755617527884121630784469379311199256277022770033036782130954108210409787680433301426480762532000133464370267551845990395683108170721952672388388178378604502610341465223041534665133155077544973384500983410220955683686526835733853985930134970899200234404716865462481142496209914197674463932

kbits=167
PR.<x> = PolynomialRing(Zmod(n))
f = (c1-x)*(c2-x)
f=f.monic()
x0 = f.small_roots(X=2^kbits)[0]
print(long_to_bytes(int(x0)))
#b'd2-bbe5-1420eaaa3b30}'

最后合一下就是flag

flag{3e99c26b-efdd-4cd2-bbe5-1420eaaa3b30}

babyrsa

from Crypto.Util.number import *
from random import * 
from secret import flag
import os

def pad_flag(flag, bits=1024):
    pad = os.urandom(bits//8 - len(flag))
    return int.from_bytes(flag + pad, "big")

p,q = [getPrime(1024) for _ in "RSA"[1:]] 
a,b = [randint(0, 2**1024) for _ in "RSA"[:-1]] 

n = p * q
e = 0x10001
m = pad_flag(flag)

assert m < n

c = pow(m, e, n)

print(c)
print(n)
print(p + b * q)
print(a * p + q)

# 11850797596095451670524864488046085367812828367468720385501401042627802035427938560866042101544712923470757782908521283827297125349504897418356898752774318846698532487439368216818306352553082800908866174488983776084101115047054799618258909847935672497139557595959270012943240666681053544905262111921321629682394432293381001209674417203517322559283298774214341100975920287314509947562597521988516473281739331823626676843441511662000240327706777269733836703945274332346982187104319993337626265180132608256601473051048047584429295402047392826197446200263357260338332947498385907066370674323324146485465822881995994908925
# 21318014445451076173373282785176305352774631352746325570797607376133429388430074045541507180590869533728841479322829078527002230672051057531691634445544608584952008820389785877589775003311007782211153558201413379523215950193011250189319461422835303446888969202767656215090179505169679429932715040614611462819788222032915253996376941436179412296039698843901058781175173984980266474602529294294210502556931214075073722598225683528873417278644194278806584861250188304944748756498325965302770207316134309941501186831407953950259399116931502886169434888276069750811498361059787371599929532460624327554481179566565183721777
# 4780454330598494796755521994676122817049316484524449315904838558624282970709853419493322324981097593808974378840031638879097938241801612033487018497098140216369858849215655128326752931937595077084912993941304190099338282258345677248403566469008681644014648936628917169410836177868780315684341713654307395687505633335014603359767330561537038768638735748918661640474253502491969012573691915259958624247097465484616897537609020908205710563729989781151998857899164730749018285034659826333237729626543828084565456402192248651439973664388584573568717209037035304656129544659938260424175198672402598017357232325892636389317
# 9819969459625593669601382899520076842920503183309309803192703938113310555315820609668682700395783456748733586303741807720797250273398269491111457242928322099763695038354042594669354762377904219084248848357721789542296806917415858628166620939519882488036571575584114090978113723733730014540463867922496336721404035184980539976055043268531950537390688608145163366927155216880223837210005451630289274909202545128326823263729300705064272989684160839861214962848466991460734691634724996390718260697593087126527364129385260181297994656537605275019190025309958225118922301122440260517901900886521746387796688737094737637604

为了使用LLL算法解决问题，首先需要根据已知条件构建一个合适的格。对于给定的方程组p + b * q和a * p + q，我们可以通过将这些方程转换成向量的形式来构建格。因为要满足hermite定理需要进行调整,然后用LLL解出pq,然后因为取的ab位数可能会有些偏差，需要多试几次，一般就1位相差：

import gmpy2
from Crypto.Util.number import *

c = 11850797596095451670524864488046085367812828367468720385501401042627802035427938560866042101544712923470757782908521283827297125349504897418356898752774318846698532487439368216818306352553082800908866174488983776084101115047054799618258909847935672497139557595959270012943240666681053544905262111921321629682394432293381001209674417203517322559283298774214341100975920287314509947562597521988516473281739331823626676843441511662000240327706777269733836703945274332346982187104319993337626265180132608256601473051048047584429295402047392826197446200263357260338332947498385907066370674323324146485465822881995994908925
n = 21318014445451076173373282785176305352774631352746325570797607376133429388430074045541507180590869533728841479322829078527002230672051057531691634445544608584952008820389785877589775003311007782211153558201413379523215950193011250189319461422835303446888969202767656215090179505169679429932715040614611462819788222032915253996376941436179412296039698843901058781175173984980266474602529294294210502556931214075073722598225683528873417278644194278806584861250188304944748756498325965302770207316134309941501186831407953950259399116931502886169434888276069750811498361059787371599929532460624327554481179566565183721777
h1 = 4780454330598494796755521994676122817049316484524449315904838558624282970709853419493322324981097593808974378840031638879097938241801612033487018497098140216369858849215655128326752931937595077084912993941304190099338282258345677248403566469008681644014648936628917169410836177868780315684341713654307395687505633335014603359767330561537038768638735748918661640474253502491969012573691915259958624247097465484616897537609020908205710563729989781151998857899164730749018285034659826333237729626543828084565456402192248651439973664388584573568717209037035304656129544659938260424175198672402598017357232325892636389317
h2 = 9819969459625593669601382899520076842920503183309309803192703938113310555315820609668682700395783456748733586303741807720797250273398269491111457242928322099763695038354042594669354762377904219084248848357721789542296806917415858628166620939519882488036571575584114090978113723733730014540463867922496336721404035184980539976055043268531950537390688608145163366927155216880223837210005451630289274909202545128326823263729300705064272989684160839861214962848466991460734691634724996390718260697593087126527364129385260181297994656537605275019190025309958225118922301122440260517901900886521746387796688737094737637604


for i in range(4):
    for j in range(4):
        L = Matrix([
        [1,0,0,4*h1<<2048],
        [0,1,0,4*h2<<2048],
        [0,0,2^(1024-2),(h1*i+h2*j-h1*h2)<<2048],
        [0,0,0,n<<2048]])
        p0 = L.LLL()[0]
        p = 4*abs(p0[0])+i
        if is_prime(p) and n%p==0:
            q=n//p
            break

phi_n=(p-1)*(q-1)
d = gmpy2.invert(65537,phi_n)
m = pow(c,d,n)
print(long_to_bytes(int(m)))
# b'flag{3z_r5a_15_r34lly_345y_w1sh_u_c0uld_g3t_f14g}\xcb\xdfr\x1f\xf6E\x04 \x83_U\xe5I\xef\x82\xde\x8a\xe4p\x95R*\x89.1<\xc2\x9d[OU#\x19 \x0f\x0eQ\xe9\xaa\x83\xb1\xfeG8\x99yB`\x04\xec\xa9\x13\x85@\xb1R\x97h\xb4\xfd\xaa]py\xdf\x87\x08\xaf\xf6\xdaf\x0b\x00\xf2\x0c\xc9l8\x03'