2024XCTF4/1-5/1

签到题

题目：

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 *
from tqdm import *
import gmpy2
flag=b'XYCTF{uuid}'
flag=bytes_to_long(flag)  #将字节串 flag 转换为大整数
leak=bin(int(flag))   #转换为二进制字符串的形式
while 1:       # 末位补0到514
    leak += "0"
    if len(leak) == 514:    
        break

def swap_bits(input_str):   #交换列表中对应位置的元素
    input_list = list(input_str[2:])
    length = len(input_list)

    for i in range(length // 2):
        temp = input_list[i]
        input_list[i] = input_list[length - 1 - i]
        input_list[length - 1 - i] = temp

    return ''.join(input_list)

input_str = leak
result = swap_bits(input_str)
a=result

def custom_add(input_str):
    input_list = list(input_str)
    length = len(input_list)
    
    for i in range(length):
        input_list[i] = str((int(input_list[i]) + i + 1) % 10)

    result = ''.join(input_list)
    return result


input_str = a
result = custom_add(input_str)
b=result
print(b)
#12345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567891134567789013445789912234667900123557889112356678911245568891223457790013345689901245667890234457799023355788001334678891124566790113445778902335578800133556899112346778011245567991223557880012355788902234677900124557889023355788001245568991133566790013445688912234577900124457889112456679001245578801233467789112355779912234577990233556780113

根据上面的加密方式倒推出解密的函数即可

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
from Crypto.Util.number import *

def custom_sub(input_str):
    input_list = list(input_str)
    length = len(input_list)

    for i in range(length):
        input_list[i] = str((int(input_list[i]) + 10 - i - 1) % 10)

    result = ''.join(input_list)
    return result

def reverse_swap_bits(input_str):
    input_list = list(input_str)
    length = len(input_list)

    for i in range(length // 2):
        temp = input_list[i]
        input_list[i] = input_list[length - 1 - i]
        input_list[length - 1 - i] = temp

    return ''.join(input_list)

encrypted_flag = "12345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567891134567789013445789912234667900123557889112356678911245568891223457790013345689901245667890234457799023355788001334678891124566790113445778902335578800133556899112346778011245567991223557880012355788902234677900124557889023355788001245568991133566790013445688912234577900124457889112456679001245578801233467789112355779912234577990233556780113" 

# 第一步：解除自定义加法
step1 = custom_sub(encrypted_flag)

# 第二步：逆向位交换
step2 = reverse_swap_bits(step1)

print(step2)
print(int(step2,2))
x="1011000010110010100001101010100010001100111101101100011001110010011001000110100001100100011001100110101011001100010110101100011011000110110001000110100001011010011010001100110011000010110010100101101011000010011011100111001001110010010110101100101001110000011100001100001001101000011001001100100001100010011010000110010001101110011000001111101"
print(long_to_bytes(int(x,2)))

#10110000101100101000011010101000100011001111011011000110011100100110010001101000011001000110011001101010110011000101101011000110110001101100010001101000010110100110100011001100110000101100101001011010110000100110111001110010011100100101101011001010011100000111000011000010011010000110010011001000011000100110100001100100011011100110000011111010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
# 9254392036983367729993565657642756163106647020423020921597044715242734027281359079743634890921671710476305652413203664281624325410548175719951158501965824
# b'XYCTF{c924235f-ccb4-4fae-a799-e88a42d14270}'

happy_to_solve1

题目： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import *
import sympy
from secrets import flag

def get_happy_prime():
    p = getPrime(512)
    q = sympy.nextprime(p ^ ((1 << 512) - 1))  
    return p, q

m = bytes_to_long(flag)
p, q = get_happy_prime()
n = p * q
e = 65537
print(n)
print(pow(m, e, n))
# n=24852206647750545040640868093921252282805229864862413863025873203291042799096787789288461426555716785288286492530194901130042940279109598071958012303179823645151637759103558737126271435636657767272703908384802528366090871653024192321398785017073393201385586868836278447340624427705360349350604325533927890879
# c=14767985399473111932544176852718061186100743117407141435994374261886396781040934632110608219482140465671269958180849886097491653105939368395716596413352563005027867546585191103214650790884720729601171517615620202183534021987618146862260558624458833387692782722514796407503120297235224234298891794056695442287

参考这里： alt text alt text alt text

改一下上面的代码即可 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import *
import gmpy2
import sympy
n = 24852206647750545040640868093921252282805229864862413863025873203291042799096787789288461426555716785288286492530194901130042940279109598071958012303179823645151637759103558737126271435636657767272703908384802528366090871653024192321398785017073393201385586868836278447340624427705360349350604325533927890879
c = 14767985399473111932544176852718061186100743117407141435994374261886396781040934632110608219482140465671269958180849886097491653105939368395716596413352563005027867546585191103214650790884720729601171517615620202183534021987618146862260558624458833387692782722514796407503120297235224234298891794056695442287
e = 65537
p=(gmpy2.iroot(pow(2,1024)-4*n,2)[0]+pow(2,512))//2
p=int(p)
while(1):
    p=sympy.nextprime(p)
    if(n%p==0):
        print(p)
        break
q=n//p
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,n)
flag=long_to_bytes(int(m))
print(flag)
# b'XYCTF{3f22f4efe3bbbc71bbcc999a0a622a1a23303cdc}'

熊博士

题目:

CBXGU{ORF_BV_NVR_BLF_CRZL_QQ}

搜索发现是一种特定的加密方式

alt text 
1
xyctf{liu_ye_mei_you_xiao_jj}

happy_to_solve2

题目： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import random
from Crypto.Util.number import *
from secrets import flag

def get_happy_prime():
    while 1:
        p = int("".join([random.choice("123") for _ in range(512)]))
        q = int("".join([random.choice("567") for _ in range(512)]))
        if isPrime(p) and isPrime(q):
            return (p,q)

m = bytes_to_long(flag)
p ,q= get_happy_prime()
n = p * q
e = 65537
print(n)
print(pow(m, e, n))
# 697906506747097082736076931509594586899561519277373830451275402914416296858960649459482027106166486723487162428522597262774248272216088755005277069446993003521270487750989061229071167729138628583207229945902389632065500739730301375338674342457656803764567184544685006193130563116558641331897204457729877920989968662546183628637193220770495938729301979912328865798266631957128761871326655572836258178871966196973138373358029531478246243442559418904559585334351259080578222274926069834941166567112522869638854253933559832822899069320370733424453856240903784235604251466010104012061821038897933884352804297256364409157501116832788696434711523621632436970698827611375698724661553712549209133526623456888111161142213830821361143023186927163314212097199831985368310770663850851571934739809387798422381702174820982531508641022827776262236373967579266271031713520262606203067411268482553539580686495739014567368858613520107678565628269250835478345171330669316220473129104495659093134763261751546990704365966783697780787341963138501
# 153383826085102296581238539677668696644156148059026868813759015106139131297135097831661048493079405226972222492151356105759235749502324303047037349410709021152255315429280760639113724345836532087970918453353723090554450581657930847674930226113840172368662838756446364482977092478979838209396761279326533419699056209983721842484996150025403009644653678928025861445324715419893797015875541525590135843027312322236085581571452084477262582966972702577136904385741443870527205640874446616413917231260133364227248928492574610248881137364204914001412269740461851747883355414968499272944590071623223603501698004227753335552646715567802825755799597955409228004284739743749531270833084850113574712041224896044525292591264637452797151098802604186311724597450780520140413704697374209653369969451501627583467893160412780732575085846467289134920886789952338174193202234175299652687560232593212131693456966318670843605238958724126368185289703563591477049105538528244632434869965333722691837462591128379816582723367039674028619947057144546
本题参考常乐村驾校队伍的wp

用pq ≡ 10 mod 10^i DFS 搜寻

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
43
44
45
import gmpy2
from itertools import product
from Crypto.Util.number import long_to_bytes
n =
697906506747097082736076931509594586899561519277373830451275402914416296858960649459482027106166
486723487162428522597262774248272216088755005277069446993003521270487750989061229071167729138628
583207229945902389632065500739730301375338674342457656803764567184544685006193130563116558641331
897204457729877920989968662546183628637193220770495938729301979912328865798266631957128761871326
655572836258178871966196973138373358029531478246243442559418904559585334351259080578222274926069
834941166567112522869638854253933559832822899069320370733424453856240903784235604251466010104012061821038897933884352804297256364409157501116832788696434711523621632436970698827611375698724661
553712549209133526623456888111161142213830821361143023186927163314212097199831985368310770663850
851571934739809387798422381702174820982531508641022827776262236373967579266271031713520262606203067411268482553539580686495739014567368858613520107678565628269250835478345171330669316220473129
104495659093134763261751546990704365966783697780787341963138501
c =
153383826085102296581238539677668696644156148059026868813759015106139131297135097831661048493079
405226972222492151356105759235749502324303047037349410709021152255315429280760639113724345836532087970918453353723090554450581657930847674930226113840172368662838756446364482977092478979838209
396761279326533419699056209983721842484996150025403009644653678928025861445324715419893797015875
541525590135843027312322236085581571452084477262582966972702577136904385741443870527205640874446
616413917231260133364227248928492574610248881137364204914001412269740461851747883355414968499272
944590071623223603501698004227753335552646715567802825755799597955409228004284739743749531270833084850113574712041224896044525292591264637452797151098802604186311724597450780520140413704697374
209653369969451501627583467893160412780732575085846467289134920886789952338174193202234175299652
687560232593212131693456966318670843605238958724126368185289703563591477049105538528244632434869
965333722691837462591128379816582723367039674028619947057144546
e = 65537
def base10(ss):
r = 0
for x in ss[: -1]:
r = r * 10 + x
return r
def dfs(ps, qs, mod):
if base10(ps) * base10(qs) = n:
yield base10(ps), base10(qs)
return
for pp, qq in product((1, 2, 3), (5, 6, 7)):
p = base10(ps + [pp])
q = base10(qs + [qq])
if p * q % mod = n % mod:
yield from dfs(ps + [pp], qs + [qq], mod * 10)
p, q = next(dfs([], [], 1))
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))
"""
XYCTF{7f4b2241951976ce5ef6df44503209059997e5085d1bc21f6bef4d9effb29fd0}

factor1

题目： 

1
2
3
4
5
6
7
8
9
10
11
12
13
import gmpy2
import hashlib
from Crypto.Util.number import *

p = getPrime(512)
q = getPrime(512)
d = getPrime(512)
e = gmpy2.invert(d, (p**3 - 1) * (q**3 - 1))
flag = "XYCTF{" + hashlib.md5(str(p + q).encode()).hexdigest() + "}"
print(e)
print(p * q)
# 172005065945326769176157335849432320425605083524943730546805772515111751580759726759492349719668775270727323745284785341119685198468883978645793770975366048506237371435027612758232099414404389043740306443065413069994232238075194102578269859784981454218948784071599231415554297361219709787507633404217550013282713899284609273532223781487419770338416653260109238572639243087280632577902857385265070736208291583497988891353312351322545840742380550393294960815728021248513046077985900158814037534487146730483099151396746751774427787635287611736111679074330407715700153025952858666841328055071403960165321273972935204988906850585454805923440635864200149694398767776539993952528995717480620593326867245714074205285828967234591508039849777840636255379730281105670496110061909219669860172557450779495125345533232776767292561378244884362014224844319802810586344516400297830227894063759083198761120293919537342405893653545157892446163
# 99075185389443078008327214328328747792385153883836599753096971412377366865826254033534293886034828804219037466246175526347014045811852531994537520303063113985486063022444972761276531422538694915030159420989401280012025249129111871649831185047820236417385693285461420040134313833571949090757635806658958193793
alt text alt text https://www.cnblogs.com/futihuanhuan/p/18126544

e = gmpy2.invert(d, (p3 - 1) * (q3 - 1))

ed=1 mol (p3-1)(q3-1)

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
43
import gmpy2
import libnum
from Crypto.Util.number import long_to_bytes

def transform(x, y):  # 使用辗转相处将分数 x/y 转为连分数的形式
    res = []
    while y:
        res.append(x // y)
        x, y = y, x % y
    return res

def continued_fraction(sub_res):
    numerator, denominator = 1, 0
    for i in sub_res[::-1]:  # 从sublist的后面往前循环
        denominator, numerator = numerator, i * numerator + denominator
    return denominator, numerator  # 得到渐进分数的分母和分子，并返回

# 求解每个渐进分数
def sub_fraction(x, y):
    res = transform(x, y)
    res = list(map(continued_fraction, (res[0:i] for i in range(1, len(res)))))  # 将连分数的结果逐一截取以求渐进分数
    return res

def get_pq(a, b, c):  # 由p+q和pq的值通过维达定理来求解p和q
    par = gmpy2.isqrt(b * b - 4 * a * c)  # 由上述可得，开根号一定是整数，因为有解
    x1, x2 = (-b + par) // (2 * a), (-b - par) // (2 * a)
    return x1, x2

def wienerAttack(e, n):
    for (d, k) in sub_fraction(e, pow(n,3)):  # 用一个for循环来注意试探e/n的连续函数的渐进分数，直到找到一个满足条件的渐进分数
        if k == 0:  # 可能会出现连分数的第一个为0的情况，排除
            continue
        if (e * d - 1) % k != 0:  # ed=1 (mod φ(n)) 因此如果找到了d的话，(ed-1)会整除φ(n),也就是存在k使得(e*d-1)//k=φ(n)
            continue
        phi = (e * d - 1) // k  # 这个结果就是 φ(n)
        print(phi)

e = 172005065945326769176157335849432320425605083524943730546805772515111751580759726759492349719668775270727323745284785341119685198468883978645793770975366048506237371435027612758232099414404389043740306443065413069994232238075194102578269859784981454218948784071599231415554297361219709787507633404217550013282713899284609273532223781487419770338416653260109238572639243087280632577902857385265070736208291583497988891353312351322545840742380550393294960815728021248513046077985900158814037534487146730483099151396746751774427787635287611736111679074330407715700153025952858666841328055071403960165321273972935204988906850585454805923440635864200149694398767776539993952528995717480620593326867245714074205285828967234591508039849777840636255379730281105670496110061909219669860172557450779495125345533232776767292561378244884362014224844319802810586344516400297830227894063759083198761120293919537342405893653545157892446163
n = 99075185389443078008327214328328747792385153883836599753096971412377366865826254033534293886034828804219037466246175526347014045811852531994537520303063113985486063022444972761276531422538694915030159420989401280012025249129111871649831185047820236417385693285461420040134313833571949090757635806658958193793
d = wienerAttack(e, n)

# 得到了phi的值（有四个，这里选择了最后一个才行）
phi=972511355325113364052631731298241810108224336674853638392467496531221801463760422905081649486798893513235333261259026447362914449581968126150102058615785246984679107185088051540510676300698365173661664885922445984655201183939191294572815083110772280365015589954234618105130449050794187936653858911777331129374894613360180493778922390477471639230901499329286970066470938409172561402078020835704490763798033121327637376099345951393869066421256289755264836484293517455899841236893445058111156336783915080237891217097045326088433225353906745033086359517592587665091898519726306522216078946862525938605393095583476688928534868739031136603910653270126346663043777160589940969589929595662661998764846989622496897301967409430643458710968400436993966533764128546870219134569546167184537791250407432987498639475713973006971493363603598769092342912760402244358599858957999731973699418392072577594301810589012112435730728238977588777556
1
p+q=19967005847503923034507166918794965506267503428119552203292911361615132318903414819134103287113608735292986181147786515878575262609755277623932397581187246
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from sympy import symbols, Eq, solve 

# 定义符号变量
x= symbols('x')

# 已知的值
phi = 972511355325113364052631731298241810108224336674853638392467496531221801463760422905081649486798893513235333261259026447362914449581968126150102058615785246984679107185088051540510676300698365173661664885922445984655201183939191294572815083110772280365015589954234618105130449050794187936653858911777331129374894613360180493778922390477471639230901499329286970066470938409172561402078020835704490763798033121327637376099345951393869066421256289755264836484293517455899841236893445058111156336783915080237891217097045326088433225353906745033086359517592587665091898519726306522216078946862525938605393095583476688928534868739031136603910653270126346663043777160589940969589929595662661998764846989622496897301967409430643458710968400436993966533764128546870219134569546167184537791250407432987498639475713973006971493363603598769092342912760402244358599858957999731973699418392072577594301810589012112435730728238977588777556

n = 99075185389443078008327214328328747792385153883836599753096971412377366865826254033534293886034828804219037466246175526347014045811852531994537520303063113985486063022444972761276531422538694915030159420989401280012025249129111871649831185047820236417385693285461420040134313833571949090757635806658958193793

# 定义方程    
equation = Eq(n ** 3 - x ** 3 + 3 * n * x + 1, phi)

# 解方程
solutions = solve(equation, x)

print("x", solutions)
# x [19967005847503923034507166918794965506267503428119552203292911361615132318903414819134103287113608735292986181147786515878575262609755277623932397581187246, -9983502923751961517253583459397482753133751714059776101646455680807566159451707409567051643556804367646493090573893257939287631304877638811966198790593623 - 771456569821584922256693369902764016239372722068394853403923361178938709770043333485345978614898773234557340570790401703783946838483311130240494535029156*sqrt(3)*I, -9983502923751961517253583459397482753133751714059776101646455680807566159451707409567051643556804367646493090573893257939287631304877638811966198790593623 + 771456569821584922256693369902764016239372722068394853403923361178938709770043333485345978614898773234557340570790401703783946838483311130240494535029156*sqrt(3)*I]

import hashlib
x=19967005847503923034507166918794965506267503428119552203292911361615132318903414819134103287113608735292986181147786515878575262609755277623932397581187246
flag = "XYCTF{" + hashlib.md5(str(x).encode()).hexdigest() + "}"
print(flag)

factor3

加密代码： 

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
43
44
45
46
47
from Crypto.Util.number import *
import random
flag = b'XYCTF{*****}'
m = bytes_to_long(flag)
def gainPrime():
while True:
x = random.getrandbits(256)
y = random.getrandbits(256)
if y % 2 == 0:
continue
p = x ** 3 + 3 * y ** 3
if p.bit_length() == 768 and p % 2 == 1 and isPrime(p):
return p
p, q = gainPrime(), gainPrime()
N = p * q
phi = (p ** 2 + p + 1) * (q ** 2 + q + 1)
d = getPrime(320)
e = inverse(d, phi)
c = d**2^m
print(f"N: {N}")
print(f"e: {e}")
print(f"c: {c}")
N:
913125842482770239379848062277162627509794409924607555622246822717218133091223291889541294440266178282194506242444509803611492259403578922020590
849630191477864719052980160940803309686069818208833547621252544423652489
179493083138385424424384165228024273745733240109761707533778691158938848
158094054261174692601673435971526522219273943464877956131040249169850420
336023942653021547841666224446678539579529590840999008107782784268926145
671962239929431694391039559247
e:
494518390582436635999115147756676313570637682518235195828939117782099618
734167908630788943568232122157772909140885391963441876427590731524706959
546524212914108888799081844320513851526790475333924396837458796755678072
486028072639014677580265244176441153444956871730684233063789931539669072
735599696830757690822185323538738397827461580678488181113667710378657058
297572328491762536595872579603698945272140918157163640403488075948987156
585480146162739943419183496337465468187233821931312507662218106713861638
334075899266373256620752680354704533272722692596941861606161634082613228
896420520465402725359166156632884432690715903666803067996854084671477445
131853993177110154928274312496230096270510089973592664248613332000290545
537840595645944390047611474888693558676781309912289044962293014118087259
307560444929227407113819165713213046898243995956550944640168932947118400
215917515277554126694376415569909534496134700668701465649939
c:
445093133736946148210694599254213355758596289403050506511087038911256532
987550295276218237292611703737321050951657095848360656627436984055113238
1128665744266165792377925899683228751870742727716
解密参考：列向量队

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
import itertools
def small_roots(f, bounds, m=1, d=None):#多元copper
if not d:
d = f.degree()
R = f.base_ring()
N = R.cardinality()
f /= f.coefficients().pop(0)
f = f.change_ring(ZZ)
G = Sequence([], f.parent())
for i in range(m + 1):
base = N ^ (m - i) * f ^ i
for shifts in itertools.product(range(d),
repeat=f.nvariables()):
g = base * prod(map(power, f.variables(), shifts))
G.append(g)
B, monomials = G.coefficient_matrix()
monomials = vector(monomials)
factors = [monomial(*bounds) for monomial in monomials]
for i, factor in enumerate(factors):
B.rescale_col(i, factor)
B = B.dense_matrix().LLL()
B = B.change_ring(QQ)
for i, factor in enumerate(factors):
B.rescale_col(i, 1 / factor)
H = Sequence([], f.parent().change_ring(QQ))
for h in filter(None, B * monomials):
H.append(h)
I = H.ideal()
if I.dimension() == -1:
H.pop()
elif I.dimension() == 0:
roots = []
for root in I.variety(ring=ZZ):
root = tuple(R(root[var]) for var in f.variables())
roots.append(root)
return roots
return []
from Crypto.Util.number import long_to_bytes
n =
913125842482770239379848062277162627509794409924607555622246822717218133091223291889541294440266178282194506242444509803611492259403578922020590
849630191477864719052980160940803309686069818208833547621252544423652489
179493083138385424424384165228024273745733240109761707533778691158938848
158094054261174692601673435971526522219273943464877956131040249169850420
336023942653021547841666224446678539579529590840999008107782784268926145
671962239929431694391039559247
e =
494518390582436635999115147756676313570637682518235195828939117782099618
734167908630788943568232122157772909140885391963441876427590731524706959
546524212914108888799081844320513851526790475333924396837458796755678072
486028072639014677580265244176441153444956871730684233063789931539669072
735599696830757690822185323538738397827461580678488181113667710378657058
297572328491762536595872579603698945272140918157163640403488075948987156
585480146162739943419183496337465468187233821931312507662218106713861638
334075899266373256620752680354704533272722692596941861606161634082613228
896420520465402725359166156632884432690715903666803067996854084671477445
131853993177110154928274312496230096270510089973592664248613332000290545
537840595645944390047611474888693558676781309912289044962293014118087259
307560444929227407113819165713213046898243995956550944640168932947118400
215917515277554126694376415569909534496134700668701465649939
P = PolynomialRing(Zmod(e), "k,s")
k, s = P.gens()
f = 1 + k * (n ^ 2 + (n + 1) * (s + 1) + s ^ 2 - 2 * n)
k, s = small_roots(f, (2 ** 320, 2 ** 768), m=3, d=4)[0] # take ~1min
k, s = ZZ(k), ZZ(s)
print(k)
print(s)
'''
125125730665737365965460573948581759569571720243814978163777784963537129
2306024253248630690054410
192542022902257858340613955458155183565501196469577365750108215823363337
683394973722208794410902290438994342045520906008135423459729237892362733
695782276383497516564289875792818430615786451024154774031397254880170824
9946480791494352
'''
#求出k和s之后，直接可以求出d了
from sympy import solve, symbols
from gmpy2 import invert
from Crypto.Util.number import long_to_bytes, isPrime, bytes_to_long,
getPrime
'''
p_q =
192542022902257858340613955458155183565501196469577365750108215823363337
683394973722208794410902290438994342045520906008135423459729237892362733
695782276383497516564289875792818430615786451024154774031397254880170824
9946480791494352
n =
913125842482770239379848062277162627509794409924607555622246822717218133
091223291889541294440266178282194506242444509803611492259403578922020590
849630191477864719052980160940803309686069818208833547621252544423652489
179493083138385424424384165228024273745733240109761707533778691158938848
158094054261174692601673435971526522219273943464877956131040249169850420
336023942653021547841666224446678539579529590840999008107782784268926145
671962239929431694391039559247
p, q = symbols('p q')
res = solve([p + q - p_q, p * q - n], [p, q])
print(res)
'''
e =
494518390582436635999115147756676313570637682518235195828939117782099618
734167908630788943568232122157772909140885391963441876427590731524706959
546524212914108888799081844320513851526790475333924396837458796755678072
486028072639014677580265244176441153444956871730684233063789931539669072
735599696830757690822185323538738397827461580678488181113667710378657058
297572328491762536595872579603698945272140918157163640403488075948987156
585480146162739943419183496337465468187233821931312507662218106713861638
334075899266373256620752680354704533272722692596941861606161634082613228
896420520465402725359166156632884432690715903666803067996854084671477445
131853993177110154928274312496230096270510089973592664248613332000290545
537840595645944390047611474888693558676781309912289044962293014118087259
307560444929227407113819165713213046898243995956550944640168932947118400
215917515277554126694376415569909534496134700668701465649939
p =
845727542734252771097508620366884787581346823455578404917525769041539439
746914530374958818236462967773717478357930648479282951655380705183747821
800053493097745787392338644671787997907165214166274630065657567039034950
440073852768399
q =
107969268628832581230863093421466704807366514124019525258355638919209393
708703520684712912587255993661622594209727841160207128294191167373987951
515776927073722937825056011325639630825069929607527311024831498176267329
9506406938725953
phi = (p ** 2 + p + 1) * (q ** 2 + q + 1)
d = invert(e, phi)
c =
445093133736946148210694599254213355758596289403050506511087038911256532
987550295276218237292611703737321050951657095848360656627436984055113238
1128665744266165792377925899683228751870742727716
happy_to_solve2
加密代码：
m = c ^ (d ** 2)
print(long_to_bytes(m))
#b'XYCTF{I_love_to_read_the_crypto_paper_and_try_to_ak_them}'

babyRSMAX

alt text 题目： 

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
from Crypto.Util.number import *
from gmpy2 import *
from random import choice

flag = b'XYCTF{******}'
e = '?'
def getBabyPrime(nbits):
    while True:
        p = 1
        while p.bit_length() <= nbits:
            p *= choice(sieve_base)
        
        if isPrime(p+1):
            return p+1

p = getBabyPrime(512)
q = getBabyPrime(512)
n = p*q
gift1 = (pow(p,e,n)-pow(q,e,n)) % n
gift2 = pow(p+q,e,n)

t = 65537
x = bytes_to_long(e)
y = pow(x, t, n)

m = bytes_to_long(flag)
c = powmod(m, e, n)

print(f'n = {n}')
print(f'gift1 = {gift1}')
print(f'gift2 = {gift2}')
print(f'c = {c}')
print(f'y = {y}')

'''
n = 39332423872740210783246069030855946244104982381157166843977599780233911183158560901377359925435092326653303964261550158658551518626014048783435245471536959844874036516931542444719549997971482644905523459407775392702211086149279473784796202020281909706723380472571862792003687423791576530085747716706475220532321
gift1 = 4549402444746338327349007235818187793950285105091726167573552412678416759694660166956782755631447271662108564084382098562999950228708300902201571583419116299932264478381197034402338481872937576172197202519770782458343606060544694608852844228400457232100904217062914047342663534138668490328400022651816597367310
gift2 = 111061215998959709920736448050860427855012026815376672067601244053580566359594802604251992986382187891022583247997994146019970445247509119719411310760491983876636264003942870756402328634092146799825005835867245563420135253048223898334460067523975023732153230791136870324302259127159852763634051238811969161011462
c = 16938927825234407267026017561045490265698491840814929432152839745035946118743714566623315033802681009017695526374397370343984360997903165842591414203197184946588470355728984912522040744691974819630118163976259246941579063687857994193309554129816268931672391946592680578681270693589911021465752454315629283033043
y = 1813650001270967709841306491297716908969425248888510985109381881270362755031385564927869313112540534780853966341044526856705589020295048473305762088786992446350060024881117741041260391405962817182674421715239197211274668450947666394594121764333794138308442124114744892164155894256326961605137479286082964520217
'''
本题参考了常乐村驾校队伍的wp

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 *
from gmpy2 import *
from random import choice
n =
393324238727402107832460690308559462441049823811571668439775997802339111831585609013773599254350
923266533039642615501586585515186260140487834352454715369598448740365169315424447195499979714826
449055234594077753927022110861492794737847962020202819097067233804725718627920036874237915765300
85747716706475220532321
g1 =
454940244474633832734900723581818779395028510509172616757355241267841675969466016695678275563144
727166210856408438209856299995022870830090220157158341911629993226447838119703440233848187293757
617219720251977078245834360606054469460885284422840045723210090421706291404734266353413866849032
8400022651816597367310
g2 =
111061215998959709920736448050860427855012026815376672067601244053580566359594802604251992986382
187891022583247997994146019970445247509119719411310760491983876636264003942870756402328634092146
799825005835867245563420135253048223898334460067523975023732153230791136870324302259127159852763
634051238811969161011462
c =
169389278252344072670260175610454902656984918408149294321528397450359461187437145666233150338026
810090176955263743973703439843609979031658425914142031971849465884703557289849125220407446919748
196301181639762592469415790636878579941933095541298162689316723919465926805786812706935899110214
65752454315629283033043
y =
181365000127096770984130649129771690896942524888851098510938188127036275503138556492786931311254053478085396634104452685670558902029504847330576208878699244635006002488111774104126039140596281
718267442171523919721127466845094766639459412176433379413830844212411474489216415589425632696160
5137479286082964520217
pe = ((g1+g2)/ 2)%n
qe = ((g2-g1)/ 2)%n
p = gmpy2.gcd(pe,n)
q = gmpy2.gcd(qe,n)
print(p,q)
print(p*q= n)
phi=(p-1)*(q-1)
t = 65537
x = pow(y,gmpy2.invert(t,phi),n)
e = x
print(long_to_bytes(e))
e = 4096
phi = phi/ 4
d_ = gmpy2.invert(e,phi)
#print(d)
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
43
44
45
46
47
48
49
50
51
52
53
54
55
def multiplication(x1,y1,x2,y2,w,p):
x=(x1*x2+y1*y2*w)%p
y=(x1*y2+x2*y1)%p
return x,y
# 获取w,使得w = -1 mod p, w是复数元的平方
def get_w(c,p):
a=randint(1,p)
w=pow(a, 2) - c
while pow(w,(p - 1)/ 2,p)! p-1:
a=randint(1,p)
w=pow(a,2)-c
return w,a
def Cipolla_algorithm(c,p):
    #主体部分
    w,a=get_w(c,p)
    power=(p+1)/ 2
    x1=a
    y1=1
    x=1
    y=0
    while(power! 0):
        if(power! (p+1)/ 2):
            x1,y1=multiplication(x1,y1,x1,y1,w,p)
        if(power & 1):
            x,y=multiplication(x,y,x1,y1,w,p)
        power> 1
    return x
cn =
pow(c,4*1534022146892150554839736212812313821410100326022914405108745499241300613161518580076912
4140840468748
23035337005158475621433705623268639417140515158078335142054666787229183797173181186377993649280,
n)
cp = cn%p
Cipolla_algorithm(cn,p)%p
166353789373057352195268573847472134983952212264580315606750168640904529917560511398152614100259
694276272602506054433757749654828608600573448732931745676174
sage: Cipolla_algorithm(cn,p)%p
132092561537869160993667319333430266730451609506565594486832556247939179580442437134355292265094
6388889883899419614130483678902025
sage: Cipolla_algorithm(cn,p)%p
166353789373057352195268573847472134983952212264580315606750168640904529917560511398152614100259
694276272602506054433757749654828608600573448732931745676174
sage:
Cipolla_algorithm(166353789373057352195268573847472134983952212264580315606750168640904529917560
511398152614100259694276272602506054433757749654828608600573448732931745676174,p)%p
0
sage:
Cipolla_algorithm(132092561537869160993667319333430266730451609506565594486832556247939179580442
4371343552922650946388889883899419614130483678902025,p)%p
36344540379246669047243921781711114415694316462518391812884210045
sage:
Cipolla_algorithm(132092561537869160993667319333430266730451609506565594486832556247939179580442
4371343552922650946388889883899419614130483678902025,p)%p
166353789373057352195268575168397750362643822201253508941052835945420624983216456266478176543306
949701450304802363434626984929302798183530544471602540368154
1
2
3
4
#长度较短的通常会是flag，尝试l2b
print(long_to_bytes(36344540379246669047243921781711114415694316462518391812884210045))
"""
b'XYCTF{Rabin_is_so_biggggg!}'
CTF
2024XCTF4/1-5/1
http://jrhu0048.github.io/2024/04/12/ctf/2024xctf4-1-5-1/
作者
JR.HU
发布于
2024年4月12日
更新于
2024年10月14日
许可协议