Crypto-题目复现

Crypto（部分赛题复现）

一、ECC

题目

from Crypto.Util.number import *
from flag import flag

assert flag.startswith(b'SHCTF{')

m = next_prime(bytes_to_long(flag))
p = getPrime(512)
a,b = getPrime(128),getPrime(128)
E = EllipticCurve(Zmod(p),[a,b])
k = getPrime(256)
A1 = E.random_point()
A2 = A1*k
M = E.lift_x(m)
C = M+A2

print('p = ',p)
print('k = ',k)
print('A1 = ',A1)
print('C = ',C)

分析题目，根据椭圆曲线$y^2=x^3+ax+b(mod p)$,
易得
$y_1^2=x_1^3+ax_1+b(mod p)$
$y_2^2=x_2^3+ax_2+b(mod p)$

因此 $y_1^2-y_2^2=x_1^3-x_2^3+a(x_1-x_2) (mod p)$
可以得到

• $a=((y_1^2-y_2^2)-(x_1^3-x_2^3))*(x_1-x_2)^{-1}(mod p)$

• $b=y_1^2-x_1^3-ax_1$

代码实现如下：

from sage.all import *

p = 9799485259524549113003780400336995829253375211044694607315372450399356814285244762186468904824132005209991983177601498069896166228214442123763065076327679
k = 73771953838487511457389800773038323262861649769228176071578897500004883270121

# 椭圆曲线上的点 A1 的坐标
A1_x = 5945412329827707694132352090606154232045921322662767755331097180167148601629747751274580872108985870208681845078153424348847330421799769770041805208089791
A1_y = 4113102573821904570542216004200810877456931033522276527318388416329888348077285857968081007666714313806776668203284797556825595791189566621228705928598709

# 椭圆曲线上的点 C 的坐标
C_x = 2336301464307188733995312208152021176388718095735565422234047912672553316288080052957448196669174030921526180747767251838308335308474037066343018337141276
C_y = 6868888273736103386336636953449998615833854869329393895956720058438723636197866928342387693671211918574357564701700555086194574821628053750572619551290025

# 计算椭圆曲线的系数 a,b
a = (((A1_y**2 - C_y**2) - (A1_x**3 - C_x**3)) * inverse_mod(A1_x - C_x, p)) % p
b = (A1_y**2 - (A1_x**3 + a * A1_x)) % p

# 椭圆曲线 E
E = EllipticCurve(Zmod(p), [a, b])
# 得到椭圆曲线上的点 A1 和 C
A1 = E(A1_x, A1_y)
C = E(C_x, C_y)

# 计算 M，M 是 C 和 A1 的 k 倍之差
M = C - A1 * k

M_x, M_y = M.xy()
M_x = int(M_x)  # 确保 M_x 是整数
k = 0  

# 爆破，直到找到合适的 k
while True:
    # 计算 M_x + k，并转换为字节
    flag = (M_x + k).to_bytes((M_x + k).bit_length() // 8 + 1, byteorder='big')
    if flag[-1] == b'}'[0]:
        print(flag)
        break
    k += 1 

最后得出flag

b'SHCTF{fo1und_adm1n_1st112}'

二、Worde

题目

import gmpy2
from Crypto.Util.number import *
from enc import flag

m = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
n = p*q
e = getPrime(200)
d = gmpy2.invert(e,(p-1)*(q-1))
dp = d % (p-1)
c = pow(m,e,n)

print(f"n = {n}")
print(f"c = {c}")
print(f"e = {e}")
print(f"dp = {dp}")
'''
n = 109107602100083925434534585854846831236367603422316141347264137431302883470878923089749415207692012162155876778433717629342677316345731989945596067366116672567736273807718413809647914537764235761542424897238828392953295052578070312924153469401927457894377311164918422725712644346523111884028669119193975313887
c = 12365023456688645580386013142401018678669277172751038338862050435558830037797597611468398293100628165715843800273910908523113026689604063358765532741066964819435916168186673401044725950148852461706560086575130200892491873160148840462376185674368155136548141795152470696307075032455110914362528191482417145054
e = 1110502004037199148392049197465263263258201603154804199229233
dp = 3275908895382252717938319219921393159589684865527587914026986407331495145759978971843598067552610402795251010991143945338216738101191449912695396060306987
'''

分析

$d_p=d mod(p-1)$

$ed=1 mod(p-1)(q-1)$

$m^{ed_p} modn=m^{ed mod(p-1)}modn=m^{edmod(p-1)}modp$

所以$ m^{ed_p}modn=m^{1+k(p-1)}modp$

由费马小定理得

$m^{1+k(p-1)}=mmodp$

$m^{ed_p}modn=mmodp$

即$m^{ed_p}modn-m=0modp$

又因为 $n=p*q$

所以，

$p=gcd(m^{ed_p}modn-m,n)$

$q=n/p$

由于p，q的值不会随m的值的变化而变化，因此先取一个简单的m值算出p，q

这里取m=3,具体代码如下：

import gmpy2
from Crypto.Util.number import long_to_bytes

n = 109107602100083925434534585854846831236367603422316141347264137431302883470878923089749415207692012162155876778433717629342677316345731989945596067366116672567736273807718413809647914537764235761542424897238828392953295052578070312924153469401927457894377311164918422725712644346523111884028669119193975313887
c = 12365023456688645580386013142401018678669277172751038338862050435558830037797597611468398293100628165715843800273910908523113026689604063358765532741066964819435916168186673401044725950148852461706560086575130200892491873160148840462376185674368155136548141795152470696307075032455110914362528191482417145054
e = 1110502004037199148392049197465263263258201603154804199229233
dp = 3275908895382252717938319219921393159589684865527587914026986407331495145759978971843598067552610402795251010991143945338216738101191449912695396060306987

p=gmpy2.gcd(pow(3,e*dp,n)-3,n)
q=n // p
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)

m=pow(c,d,n)
print(long_to_bytes(m))

得出flag：

SHCTF{W0RD_E_You_Dian_d4_39ac80}

三、魔鬼的步伐

题目

from Crypto.Util.number import *
from random import choice
from enc import flag

m = bytes_to_long(flag)
def get_primes(limit):
    primes = []
    is_prime = [True] * (limit + 1)
    for num in range(2, limit + 1):
        if is_prime[num]:
            primes.append(num)
            for multiple in range(num * num, limit + 1, num):
                is_prime[multiple] = False
    return primes

def get_Prime(bits):
    while True:
        n = 2
        while n.bit_length() < bits:
            n *= choice(primes)
        if isPrime(n + 1):
            return n + 1

e = 65537
primes = get_primes(e)
p = get_Prime(512)
q = get_Prime(512)
n = p*q
c = pow(m,e,n)
print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")
'''
n = 4186638789266977215701176406902225153580897798738374778190546920953456120773405529907877295436545488469674635531209549868315266718331642076467662180105755639770292506252529987461772914357288415820521682440518534463618953638844660234376343358577530665662965586577666423222977193832113032528182580888600345392172267
e = 65537
c = 1101497471412301437262774092373565647672283526174670758698538912172368368818345084954023566146183938314237997217377433629432867021863253208574722128961878717486680977557664225793339730281222164389006116794870197114163633751309928211749128540642890687695741098247036592774972659188774127813915341533193950474979408
'''

由题目暗示和题目代码可以看出，p-1 是光滑数

$p-1=p_1p_2…p_n(p_i<=B)$

所以$p-1|B!$

即$B!=k(p-1)$

由费马小定理得：$a^{k(p-1)}=1modp$

$=>a^{B!}=1modp$

可以得知$p=gcd(a^{B!}-1,n)$

代码如下：

import gmpy2
from Crypto.Util.number import long_to_bytes

n = 4186638789266977215701176406902225153580897798738374778190546920953456120773405529907877295436545488469674635531209549868315266718331642076467662180105755639770292506252529987461772914357288415820521682440518534463618953638844660234376343358577530665662965586577666423222977193832113032528182580888600345392172267
e = 65537
c = 1101497471412301437262774092373565647672283526174670758698538912172368368818345084954023566146183938314237997217377433629432867021863253208574722128961878717486680977557664225793339730281222164389006116794870197114163633751309928211749128540642890687695741098247036592774972659188774127813915341533193950474979408

a = 2
k = 2
while True:
    a = pow(a, k, n)
    p = gmpy2.gcd(a-1, n)
    if p != 1 and p != n:
        q = n // p
        print("p=",p)
        print("q=",q)
        break
    k += 1

phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,n)
m=long_to_bytes(m)
print(m)

得到flag如下：

SHCTF{1Rlc7iOn_is_THE_d3vils_5TeP_G3}

四、小鲨鱼的方程

题目

from Cryptodome.Util.number import *
from random import *
from gmpy2 import *
import uuid
flag1='ISCTF{'+str(uuid.uuid4())+'}'

m1=bytes_to_long(flag1.encode())
def get_p():
    BITS = 256
    bits = 777
    oder = 4
    a = randint(1 << bits, 1 << bits + 1)   #a是777位随机数
    p=getPrime(BITS)      #p是256位素数
    p1 = p**oder+a        #p1=p*4+a
    return p,p1
p,p1=get_p()
s=getPrime(1024)
q=getPrime(512)
n=p*q**4
e=65537
c1=pow(s,e,n)     #求s
#d=invert(e,(p-1)(q**4-q**3))
#s=pow(c1,d,n)
c=pow(s**3+1,m1,s**5)
print("c1=",c1)
print("c =",c)
print("n =",n)
print("p1 =",p1)

'''
c1= 671390498592586008552998377599101093977542184109077889081448730480869018650843045119891777468161631085086340705902115332025675787789530562679603254577287153918966364523848382506106179394235772395029788721306186952016420794804145631124905952103136061076643266886961178241381892015555099638200222249447194504082451341122502519637821695210573997670753981061458264118355417889153180841281073262935937836447460470926729282834006229571453935760593644658459098721652426154970766417292435960463905367868753821950303919781798234432998272038029063155193184039985018137026245365188171178677898869374676546799536208952198558258306460302868688355653022725288744014143221560882404431652751343944983442109327
c = 8641190030376811670503537177719719233418166235794962118828671236836174132083208517733734760455990850156371205118391537919769888760384574011411232571257192285256730733174399297826587479261381970232162702657952399683882650083181048279650913795429823628186888540572704055008102853692060360140858142686334722286525699998854566609078547487420929457446776757558492454916447188774943818970599916514467335772992690805247630814156710861067503956707301402347944233660194395192354000788262111000900574820275786269075882923600474781645848712157460135387134196156906258218217831988828360827613420801773911833194097791649069743116686685667300622630909231822986237104627385544169938138006242341269672868611269202418482629393372933567053272565557137741441902377611003983050084491513897727856173625922194300103448148829004025229567101761111396110940066254801762424343522707712480796358754008120503317686600144600226149617189681233392693738216138797012278242152852923361635415564580582002132107424154426980566696622448291815571736676562214017436
n = 1076246859437269645898003764327104347852443049519429833372038915264009774423737482018987571807662568251485615769880354898666799006772572239466617428164721157850526408878346223839884319846641438292436373441749602341461361190584638190903978829024853974880636148520803145113551453821058269641304504880310836801494499720662704717315748614372503735165114899680682056477494953525794354656896362929510309669119173103242509398650608116835276076364248473952717811633756784397347121601006659623317417388283638159905288128181587304367489096254611610975352096229116491567502061775862811850081040850421151385474249060884479729988512713640536139010928836126719149031115182144744359297169350288886555784650111
p1 = 145356063641618996012874664536921616978986640263438210169671010403677822239343590475177543891188656103067696467174379510912427160232486984044862545338401652910975162942038201716552753723984593267892098222213049269335313670049037479410635628460505327693176152061750827570561482918795206276991967169087371403553
''' 

解答

p,q容易得到，之后按正常的RSA步骤求出s，之后就是利用s求m

$\because c=pow(s^3+1,m,s^5)$

$即c=(s^3+1)^mmods^5$

由二项式定理得：

$(s^3+1)^m=C_m^0s^{3m}1^0+C_m^1s^{3(m-1)}1^1…+C_m^{m-1}s^31^{m-1}+C_m^ms^01^m$

$\therefore (s^3+1)^m=C_m^0s^{3m}+C_m^1s^{3(m-1)}…+C_m^{m-1}s^3+C_m^ms^0$

因为m必定大于2

$\therefore s^3$前面的数必定是s^5的倍数，可以直接约掉

$\therefore (s^3+1)^m=ms^3+1mods^5$

$\therefore c=ms^3+1mods^5$

$\because 由于flag的长度可知m<s^2(2048bits)$

$\therefore c=ms^3+1$

$\therefore m=(c-1)/(s^3)$

代码实现如下：

from Crypto.Util.number import long_to_bytes
import gmpy2

c1= 671390498592586008552998377599101093977542184109077889081448730480869018650843045119891777468161631085086340705902115332025675787789530562679603254577287153918966364523848382506106179394235772395029788721306186952016420794804145631124905952103136061076643266886961178241381892015555099638200222249447194504082451341122502519637821695210573997670753981061458264118355417889153180841281073262935937836447460470926729282834006229571453935760593644658459098721652426154970766417292435960463905367868753821950303919781798234432998272038029063155193184039985018137026245365188171178677898869374676546799536208952198558258306460302868688355653022725288744014143221560882404431652751343944983442109327
c = 8641190030376811670503537177719719233418166235794962118828671236836174132083208517733734760455990850156371205118391537919769888760384574011411232571257192285256730733174399297826587479261381970232162702657952399683882650083181048279650913795429823628186888540572704055008102853692060360140858142686334722286525699998854566609078547487420929457446776757558492454916447188774943818970599916514467335772992690805247630814156710861067503956707301402347944233660194395192354000788262111000900574820275786269075882923600474781645848712157460135387134196156906258218217831988828360827613420801773911833194097791649069743116686685667300622630909231822986237104627385544169938138006242341269672868611269202418482629393372933567053272565557137741441902377611003983050084491513897727856173625922194300103448148829004025229567101761111396110940066254801762424343522707712480796358754008120503317686600144600226149617189681233392693738216138797012278242152852923361635415564580582002132107424154426980566696622448291815571736676562214017436
n = 1076246859437269645898003764327104347852443049519429833372038915264009774423737482018987571807662568251485615769880354898666799006772572239466617428164721157850526408878346223839884319846641438292436373441749602341461361190584638190903978829024853974880636148520803145113551453821058269641304504880310836801494499720662704717315748614372503735165114899680682056477494953525794354656896362929510309669119173103242509398650608116835276076364248473952717811633756784397347121601006659623317417388283638159905288128181587304367489096254611610975352096229116491567502061775862811850081040850421151385474249060884479729988512713640536139010928836126719149031115182144744359297169350288886555784650111
p1 = 145356063641618996012874664536921616978986640263438210169671010403677822239343590475177543891188656103067696467174379510912427160232486984044862545338401652910975162942038201716552753723984593267892098222213049269335313670049037479410635628460505327693176152061750827570561482918795206276991967169087371403553
e = 65537

p_tmp=gmpy2.iroot(p1,4)[0]
while True:    #暴力破解p和q
    q_tmp=n // p_tmp
    if n==q_tmp*p_tmp:
        p=p_tmp
        q=gmpy2.iroot(q_tmp,4)[0]
        break
    p_tmp-=1

phi=(p-1)*(q**4-q**3)   #欧拉函数
d=gmpy2.invert(e,phi)
s=pow(c1,d,n)
#print(s)
m=(c-1)//(s**3)
ans=long_to_bytes(m)
print(ans)

运行得到flag

b'ISCTF{8e0ff2de-cd65-497f-a755-815154bb5b1f}'

五、蓝鲨的费马

题目：

import libnum
import gmpy2
from Crypto.Util.number import *

flag=b'ISCTF{********}'
m=bytes_to_long(flag)

p=libnum.generate_prime(1024)
q=libnum.generate_prime(1024)
n=p*q
e=0x10001
c=pow(m,e,n)
d=inverse(e,(p-1)*(q-1))
leak = (d+(pow(p,q,n)+pow(q,p,n)))%n

print("c=", c)
print("n=", n)
print("leak=", leak)

"""
c= 8989289659072309605793417141528767265266446236550650613514493589798432446586991233583435051268377555448062724563967695425657559568596372723980081067589103919296476501677424322525079257328042851349095575718347302884996529329066703597604694781627113384086536158793653551546025090807063130353950841148535682974762381044510423210397947080397718080033363000599995100765708244828566873128882878164321817156170983773105693537799111546309755235573342169431295776881832991533489235535981382958295960435126843833532716436804949502318851112378495533302256759494573250596802016112398817816155228378089079806308296705261876583997
n= 13424018200035368603483071894166480724482952594135293395398366121467209427078817227870501294732149372214083432516059795712917132804111155585926502759533393295089100965059106772393520277313184519450478832376508528256865861027444446718552169503579478134286009893965458507369983396982525906466073384013443851551139147777507283791250268462136554061959016630318688169168797939873600493494258467352326974238472394214986505312411729432927489878418792288365594455065912126527908319239444514857325441614280498882524432151918146061570116187524918358453036228204087993064505391742062288050068745930452767100091519798860487150247
leak= 9192002086528025412361053058922669469031188193149143635074798633855112230489479254740324032262690315813650428270911079121913869290893574897752990491429582640499542165616254566396564016734157323265631446079744216458719690853526969359930225042993006404843355356540487296896949431969541367144841985153231095140361069256753593550199420993461786814074270171257117410848796614931926182811404655619662690700351986753661502438299236428991412206196135090756862851230228396476709412020941670878645924203989895008014836619321109848938770269989596541278600166088022166386213646074764712810133558692545401032391239330088256431881
"""

分析：

$\because 已知leak=(d+p^qmodn+q^pmodn)modn$

$令x=p^qmodn,则有x=p^q+kn,即x=p^q+k(p*q)$

$\therefore xmodq=(p^q+k(p*q)modq=p^qmodq$

$\therefore x*p^{-1}=p^{q-1}modq$

$\because q是素数$

$\therefore 由费马小定理得p^{q-1}=x*p^{-1}=1modq$

$\therefore x=pmodq,即p^qmodn=pmodp$

$同理，得q^pmodn=q$

$\therefore d=leak-(pmodq+qmodp)modn$

$\because n是2047bit，leak是2043bit，p+q在1024bit左右$

$\therefore d最有可能直接等于leak-(p+q)$

$\because p+q=n+1-(p-1)(q-1)$

且d是e关于mod(p-1)(q-1)的逆

$\therefore d=leak-n-1$

之后直接简单的RSA解密就行

代码如下：

from Crypto.Util.number import long_to_bytes

c= 8989289659072309605793417141528767265266446236550650613514493589798432446586991233583435051268377555448062724563967695425657559568596372723980081067589103919296476501677424322525079257328042851349095575718347302884996529329066703597604694781627113384086536158793653551546025090807063130353950841148535682974762381044510423210397947080397718080033363000599995100765708244828566873128882878164321817156170983773105693537799111546309755235573342169431295776881832991533489235535981382958295960435126843833532716436804949502318851112378495533302256759494573250596802016112398817816155228378089079806308296705261876583997
n= 13424018200035368603483071894166480724482952594135293395398366121467209427078817227870501294732149372214083432516059795712917132804111155585926502759533393295089100965059106772393520277313184519450478832376508528256865861027444446718552169503579478134286009893965458507369983396982525906466073384013443851551139147777507283791250268462136554061959016630318688169168797939873600493494258467352326974238472394214986505312411729432927489878418792288365594455065912126527908319239444514857325441614280498882524432151918146061570116187524918358453036228204087993064505391742062288050068745930452767100091519798860487150247
leak= 9192002086528025412361053058922669469031188193149143635074798633855112230489479254740324032262690315813650428270911079121913869290893574897752990491429582640499542165616254566396564016734157323265631446079744216458719690853526969359930225042993006404843355356540487296896949431969541367144841985153231095140361069256753593550199420993461786814074270171257117410848796614931926182811404655619662690700351986753661502438299236428991412206196135090756862851230228396476709412020941670878645924203989895008014836619321109848938770269989596541278600166088022166386213646074764712810133558692545401032391239330088256431881
e=0x10001

d=leak-n-1
m=pow(c,d,n)
print(long_to_bytes(m))

运行得到flag:

b'ISCTF{u_got_it}'

六、Schmidt-Samoa（RSA）

题目：

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

flag = b'D0g3xGC{****************}'

def gen_key(p, q):
    public_key = p*p*q        
    e = public_key        
    n = p*q
    phi_n = (p-1)*(q-1)
    private_key = inverse(e,phi_n)
    return public_key,private_key,e

p = getPrime(512)
q = getPrime(512)

N,d,e = gen_key(p,q)

c = gmpy2.powmod(bytes_to_long(flag),e,N)

print(N)
print(d)
print(c)
'''
n = 539403894871945779827202174061302970341082455928364137444962844359039924160163196863639732747261316352083923762760392277536591121706270680734175544093484423564223679628430671167864783270170316881238613070741410367403388936640139281272357761773388084534717028640788227350254140821128908338938211038299089224967666902522698905762169859839320277939509727532793553875254243396522340305880944219886874086251872580220405893975158782585205038779055706441633392356197489
d = 58169755386408729394668831947856757060407423126014928705447058468355548861569452522734305188388017764321018770435192767746145932739423507387500606563617116764196418533748380893094448060562081543927295828007016873588530479985728135015510171217414380395169021607415979109815455365309760152218352878885075237009
c = 82363935080688828403687816407414245190197520763274791336321809938555352729292372511750720874636733170318783864904860402219217916275532026726988967173244517058861515301795651235356589935260088896862597321759820481288634232602161279508285376396160040216717452399727353343286840178630019331762024227868572613111538565515895048015318352044475799556833174329418774012639769680007774968870455333386419199820213165698948819857171366903857477182306178673924861370469175
'''

分析：

（本题考查Schmidt-Samoa密码系统）

分析题目，可以知道，本题的关键在于求出$p\times q$。

设a为一个较小的正整数，则$a^{N \times d}\equiv a^{k \times (p-1)(q-1)}\equiv amodp\times q$

$\therefore a^{N\times d}-a\equiv 0modp\times q$

$\therefore a^{N\times d}-a=k\times p\times q$

$\because N=p \times p\times q$

$\therefore p\times q=gcd(a^{N\times d}-a,N)$,为了方便将取a=2

接着进行简单的RSA解密就行

代码如下：

from Crypto.Util.number import long_to_bytes
n = 539403894871945779827202174061302970341082455928364137444962844359039924160163196863639732747261316352083923762760392277536591121706270680734175544093484423564223679628430671167864783270170316881238613070741410367403388936640139281272357761773388084534717028640788227350254140821128908338938211038299089224967666902522698905762169859839320277939509727532793553875254243396522340305880944219886874086251872580220405893975158782585205038779055706441633392356197489
d = 58169755386408729394668831947856757060407423126014928705447058468355548861569452522734305188388017764321018770435192767746145932739423507387500606563617116764196418533748380893094448060562081543927295828007016873588530479985728135015510171217414380395169021607415979109815455365309760152218352878885075237009
c = 82363935080688828403687816407414245190197520763274791336321809938555352729292372511750720874636733170318783864904860402219217916275532026726988967173244517058861515301795651235356589935260088896862597321759820481288634232602161279508285376396160040216717452399727353343286840178630019331762024227868572613111538565515895048015318352044475799556833174329418774012639769680007774968870455333386419199820213165698948819857171366903857477182306178673924861370469175

pq=gcd(pow(2,n*d,n)-2,n)
m=pow(c,d,pq)
print(long_to_bytes(m))

运行得到flag：

b'D0g3xGC{W1sh_Y0u_Go0d_L@ucK-111}'