W'Blog

Wbuildings的自勉小屋

0%

第一届帕鲁杯-CTF挑战赛

发表于 分类于 Valine：
本文字数： 26k 阅读时长 ≈ 23 分钟

草树知春不久归，百般红紫斗芳菲。

玛卡巴卡能有什么坏心思呢

题目

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
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
encoding_rules = {
    'a': '玛卡巴卡轰',
    'b': '阿巴雅卡轰',
    'c': '伊卡阿卡噢轰',
    'd': '哈姆达姆阿卡嗙轰',
    'e': '咿呀呦轰',
    'f': '玛卡雅卡轰',
    'g': '伊卡阿卡轰',
    'h': '咿呀巴卡轰',
    'i': '达姆阿卡嗙轰',
    'j': '玛卡巴卡玛卡巴卡轰',
    'k': '玛卡巴卡玛卡巴卡玛卡巴卡轰',
    'l': '玛卡巴卡玛卡巴卡玛卡巴卡玛卡巴卡轰',
    'm': '阿巴雅卡阿巴雅卡轰',
    'n': '阿巴雅卡阿巴雅卡阿巴雅卡轰',
    'o': '阿巴雅卡阿巴雅卡阿巴雅卡阿巴雅卡轰',
    'p': '伊卡阿卡噢伊卡阿卡噢轰',
    'q': '伊卡阿卡噢伊卡阿卡噢伊卡阿卡噢轰',
    'r': '伊卡阿卡噢伊卡阿卡噢伊卡阿卡噢伊卡阿卡噢轰',
    's': '哈姆达姆阿卡嗙哈姆达姆阿卡嗙轰',
    't': '哈姆达姆阿卡嗙哈姆达姆阿卡嗙哈姆达姆阿卡嗙轰',
    'u': '哈姆达姆阿卡嗙哈姆达姆阿卡嗙哈姆达姆阿卡嗙哈姆达姆阿卡嗙轰',
    'v': '咿呀呦咿呀呦轰',
    'w': '咿呀呦咿呀呦咿呀呦轰',
    'x': '咿呀呦咿呀呦咿呀呦咿呀呦轰',
    'y': '咿呀呦咿呀呦咿呀呦咿呀呦咿呀呦轰',
    'z': '玛卡雅卡玛卡雅卡轰',
    'A': '玛卡雅卡玛卡雅卡玛卡雅卡轰',
    'B': '玛卡雅卡玛卡雅卡玛卡雅卡玛卡雅卡轰',
    'C': '伊卡阿卡伊卡阿卡轰',
    'D': '伊卡阿卡伊卡阿卡伊卡阿卡轰',
    'E': '伊卡阿卡伊卡阿卡伊卡阿卡伊卡阿卡轰',
    'F': '咿呀巴卡咿呀巴卡轰',
    'G': '咿呀巴卡咿呀巴卡咿呀巴卡轰',
    'H': '咿呀巴卡咿呀巴卡咿呀巴卡咿呀巴卡轰',
    'I': '咿呀巴卡咿呀巴卡咿呀巴卡咿呀巴卡咿呀巴卡轰',
    'J': '达姆阿卡嗙达姆阿卡嗙轰',
    'K': '达姆阿卡嗙达姆阿卡嗙达姆阿卡嗙轰',
    'L': '达姆阿卡嗙达姆阿卡嗙达姆阿卡嗙达姆阿卡嗙轰',
    'M': '达姆阿卡嗙达姆阿卡嗙达姆阿卡嗙达姆阿卡嗙达姆阿卡嗙轰',
    'N': '巴卡巴卡轰',
    'O': '巴卡巴卡巴卡巴卡轰',
    'P': '巴卡巴卡巴卡巴卡巴卡巴卡轰',
    'Q': '巴卡巴卡巴卡巴卡巴卡巴卡巴卡巴卡轰',
    'R': '巴卡巴卡巴卡巴卡巴卡巴卡巴卡巴卡巴卡巴卡轰',
    'S': '呀呦轰',
    'T': '呀呦呀呦轰',
    'U': '呀呦呀呦呀呦轰',
    'V': '呀呦呀呦呀呦呀呦轰',
    'W': '呀呦呀呦呀呦呀呦呀呦轰',
    'X': '达姆阿卡轰',
    'Y': '达姆阿卡达姆阿卡轰',
    'Z': '达姆阿卡达姆阿卡达姆阿卡轰',
    '0': '达姆阿卡达姆阿卡达姆阿卡达姆阿卡轰',
    '1': '达姆阿卡达姆阿卡达姆阿卡达姆阿卡达姆阿卡轰',
    '2': '玛巴轰',
    '3': '玛巴玛巴轰',
    '4': '玛巴玛巴玛巴轰',
    '5': '玛巴玛巴玛巴玛巴轰',
    '6': '巴卡玛巴轰',
    '7': '巴卡玛巴巴卡玛巴轰',
    '8': '巴卡玛巴巴卡玛巴巴卡玛巴轰',
    '9': '巴卡玛巴巴卡玛巴巴卡玛巴巴卡玛巴轰',
    '=': '妈个巴子轰',
    '/': '妈个巴卡轰',
    '+': '妈个巴达轰',

}

# print(encoding_rules.values())
# print(encoding_rules.keys())
values = ['玛卡巴卡轰', '阿巴雅卡轰', '伊卡阿卡噢轰', '哈姆达姆阿卡嗙轰', '咿呀呦轰', '玛卡雅卡轰', '伊卡阿卡轰', '咿呀巴卡轰', '达姆阿卡嗙轰', '玛卡巴卡玛卡巴卡轰', '玛卡巴卡玛卡巴卡玛卡巴卡轰', '玛卡巴卡玛卡巴卡玛卡巴卡玛卡巴卡轰', '阿巴雅卡阿巴雅卡轰', '阿巴雅卡阿巴雅卡阿巴雅卡轰', '阿巴雅卡阿巴雅卡阿巴雅卡阿巴雅卡轰', '伊卡阿卡噢伊卡阿卡噢轰', '伊卡阿卡噢伊卡阿卡噢伊卡阿卡噢轰', '伊卡阿卡噢伊卡阿卡噢伊卡阿卡噢伊卡阿卡噢轰', '哈姆达姆阿卡嗙哈姆达姆阿卡嗙轰', '哈姆达姆阿卡嗙哈姆达姆阿卡嗙哈姆达姆阿卡嗙轰', '哈姆达姆阿卡嗙哈姆达姆阿卡嗙哈姆达姆阿卡嗙哈姆达姆阿卡嗙轰', '咿呀呦咿呀呦轰', '咿呀呦咿呀呦咿呀呦轰', '咿呀呦咿呀呦咿呀呦咿呀呦轰', '咿呀呦咿呀呦咿呀呦咿呀呦咿呀呦轰', '玛卡雅卡玛卡雅卡轰', '玛卡雅卡玛卡雅卡玛卡雅卡轰', '玛卡雅卡玛卡雅卡玛卡雅卡玛卡雅卡轰', '伊卡阿卡伊卡阿卡轰', '伊卡阿卡伊卡阿卡伊卡阿卡轰', '伊卡阿卡伊卡阿卡伊卡阿卡伊卡阿卡轰', '咿呀巴卡咿呀巴卡轰', '咿呀巴卡咿呀巴卡咿呀巴卡轰', '咿呀巴卡咿呀巴卡咿呀巴卡咿呀巴卡轰', '咿呀巴卡咿呀巴卡咿呀巴卡咿呀巴卡咿呀巴卡轰', '达姆阿卡嗙达姆阿卡嗙轰', '达姆阿卡嗙达姆阿卡嗙达姆阿卡嗙轰', '达姆阿卡嗙达姆阿卡嗙达姆阿卡嗙达姆阿卡嗙轰', '达姆阿卡嗙达姆阿卡嗙达姆阿卡嗙达姆阿卡嗙达姆阿卡嗙轰', '巴卡巴卡轰', '巴卡巴卡巴卡巴卡轰', '巴卡巴卡巴卡巴卡巴卡巴卡轰', '巴卡巴卡巴卡巴卡巴卡巴卡巴卡巴卡轰', '巴卡巴卡巴卡巴卡巴卡巴卡巴卡巴卡巴卡巴卡轰', '呀呦轰', '呀呦呀呦轰', '呀呦呀呦呀呦轰', '呀呦呀呦呀呦呀呦轰', '呀呦呀呦呀呦呀呦呀呦轰', '达姆阿卡轰', '达姆阿卡达姆阿卡轰', '达姆阿卡达姆阿卡达姆阿卡轰', '达姆阿卡达姆阿卡达姆阿卡达姆阿卡轰', '达姆阿卡达姆阿卡达姆阿卡达姆阿卡达姆阿卡轰', '玛巴轰', '玛巴玛巴轰', '玛巴玛巴玛巴轰', '玛巴玛巴玛巴玛巴轰', '巴卡玛巴轰', '巴卡玛巴巴卡玛巴轰', '巴卡玛巴巴卡玛巴巴卡玛巴轰', '巴卡玛巴巴卡玛巴巴卡玛巴巴卡玛巴轰', '妈个巴子轰', '妈个巴卡轰', '妈个巴达轰']
keys = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '=', '/', '+']

c = '玛卡巴卡玛卡巴卡轰达姆阿卡嗙轰阿巴雅卡阿巴雅卡阿巴雅卡轰达姆阿卡嗙轰哈姆达姆阿卡嗙哈姆达姆阿卡嗙哈姆达姆阿卡嗙轰玛卡巴卡轰达姆阿卡嗙轰阿巴雅卡阿巴雅卡轰咿呀呦轰达姆阿卡嗙轰
'

c_list = []
for i in c.split('轰'):
	c_list.append(i+'轰')

m = ''
for i in c_list[:-1]:
	if i in values:
		index = values.index(i)
		m+=keys[index]
print(m)

c = '玛巴轰达姆阿卡达姆阿卡达姆阿卡达姆阿卡轰玛巴轰玛巴玛巴玛巴轰达姆阿卡嗙轰哈姆达姆阿卡嗙哈姆达姆阿卡嗙轰伊卡阿卡噢伊卡阿卡噢轰玛卡巴卡轰哈姆达姆阿卡嗙哈姆达姆阿卡嗙轰哈姆达姆阿卡嗙哈姆达姆阿卡嗙轰咿呀呦咿呀呦咿呀呦轰阿巴雅卡阿巴雅卡阿巴雅卡阿巴雅卡轰伊卡阿卡噢伊卡阿卡噢伊卡阿卡噢伊卡阿卡噢轰哈姆达姆阿卡嗙轰'

c_list = []
for i in c.split('轰'):
	c_list.append(i+'轰')

m = ''
for i in c_list[:-1]:
	if i in values:
		index = values.index(i)
		m+=keys[index]
print(m)

# flag{jinitaimei}
# 2024ispassword

01110

题目

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
from Crypto.Util.number import getPrime, getRandomRange, bytes_to_long
from random import randrange
from flag import flag

p = getPrime(512)
q = getPrime(512)
n = p * (q**2)
e = 65537



while True:
    z = randrange(1, n)
    if all(pow(z, (x - 1) // 2, x) == x - 1 for x in (p, q)):
        break


def encrypt_bit(m, n, z):
    secret = getRandomRange(1, n - 1)
    return (pow(secret, 2, n) * pow(z, m, n)) % n

m = int(bin(bytes_to_long(flag))[2:])
c = []
while m:
    bit = m % 10
    c.append(encrypt_bit(bit, n, z))
    m //= 10

print("n=", n)
print("gift1=", pow((p + q), e, n))
print("gift2=", pow((p - q), e, n))
print("z=", z)
print("c=", c)

题解

1
2
3
4
while m:
    bit = m % 10
    c.append(encrypt_bit(bit, n, z))
    m //= 10

就是取最后一位

一眼 jacobi ，可能读取密文时间还花的长些

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 long_to_bytes
import gmpy2

n= 390643660915400759356028673149168279560687093035302974183909784119138903637101610150171466601442693220550718178154721365461636077209566533154335718201358899342358662848545345180263124134588375803369006010468316238614932369094974862842683683363587543473163915923045398254122306762084945489324575516415794686273949909352344088141474136179402651003388916093283318052977257982248730053350207666237541564674407802737159850168950514444047006592253696165165211262564161

plaintext = ''
# with open('output.txt') as f:
# 	print(f.readline().replace(',','\n').strip())

with open('output.txt') as f:
	for line in f:
		cipher = int(line)
		if gmpy2.jacobi(cipher,n) == -1:
			plaintext = '1' +plaintext
		else:
			plaintext = '0'+plaintext
print(long_to_bytes(int(plaintext,2)))

# paluctf{1_4m_th3_b0td_1n_t3st_1n_th3_r0w}

Crypto-签到

题解

n 拿去 factordb 看一下

1
2
3
4
5
6
7
8
9
10
11
import libnum

c= 45269461971515000289671772521188766694700728330128646249215013733085930489882068894332856604506536779801062614812326540395959294654223820007708665902047037358747925250870477703104363139985136565458136270800159390392019520313661164825471977721337242625432765885411745639743648296844838846507684596123618659487
p= 10946776553446440448007472617874712600557780823301066821996423559118196781424700584311983708005541979031881165443127688807109548778070835220727302118913733
e= 65537
n= 119831916911084729466317342717897978036542634518996731609377229053903313866116046924267456495022800951614061986741670058681616050263086729645721769942581237701087728947844081291145401821897421158626638131690590482798935123793612486710503488708248251831913677302987861470596167886864957248328925817207895995289

d = libnum.invmod(e,(p-1)*p)
print(libnum.n2s(pow(c,d,n)))

# flag{8ede5e35-dae8-43fd-a333-855e70c59a55}

gcccd

题目

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
python
from Crypto.Util.number import getStrongPrime, GCD, bytes_to_long
import os
from flag import flag

def long_to_bytes(long_int, block_size=None):
    """Convert a long integer to bytes, optionally right-justified to a given block size."""
    bytes_data = long_int.to_bytes((long_int.bit_length() + 7) // 8, 'big')
    return bytes_data if not block_size else bytes_data.rjust(block_size, b'\x00')

def gen_keys(bits=512, e=5331):
    """Generate RSA modulus n and public exponent e such that GCD((p-1)*(q-1), e) == 1."""
    while True:
        p, q = getStrongPrime(bits), getStrongPrime(bits)
        n = p * q
        if GCD((p-1) * (q-1), e) == 1:
            return n, e

def pad(m, n):
    """Pad the message m for RSA encryption under modulus n using PKCS#1 type 1."""
    mb, nb = long_to_bytes(m), long_to_bytes(n)
    assert len(mb) <= len(nb) - 11
    padding = os.urandom(len(nb) - len(mb) - 3).replace(b'\x01', b'')
    return bytes_to_long(b'\x00\x01' + padding + b'\x00' + mb)

def encrypt(m, e, n):
    """Encrypt message m with RSA public key (e, n)."""
    return pow(m, e, n)

n, e = gen_keys()
m = pad(bytes_to_long(flag), n)
c1, c2 = encrypt(m, e, n), encrypt(m // 2, e, n)

print(f"n = {n}\ne = {e}\nc1 = {c1}\nc2 = {c2}")

# n = 128134155200900363557361770121648236747559663738591418041443861545561451885335858854359771414605640612993903005548718875328893717909535447866152704351924465716196738696788273375424835753379386427253243854791810104120869379525507986270383750499650286106684249027984675067236382543612917882024145261815608895379
# e = 5331
# c1 = 60668946079423190709851484247433853783238381043211713258950336572392573192737047470465310272448083514859509629066647300714425946282732774440406261265802652068183263460022257056016974572472905555413226634497579807277440653563498768557112618320828785438180460624890479311538368514262550081582173264168580537990
# c2 = 43064371535146610786202813736674368618250034274768737857627872777051745883780468417199551751374395264039179171708712686651485125338422911633961121202567788447108712022481564453759980969777219700870458940189456782517037780321026907310930696608923940135664565796997158295530735831680955376342697203313901005151

题解

关键点在这

1
c1, c2 = encrypt(m, e, n), encrypt(m // 2, e, n)

通过题目名gcccd联想到 Franklin-Reiter或者half gcd

1
assert c1 != (c2 * pow(2, e, n)) % n

看这个数的奇偶性，

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
# Franklin-Reiter

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

n = 128134155200900363557361770121648236747559663738591418041443861545561451885335858854359771414605640612993903005548718875328893717909535447866152704351924465716196738696788273375424835753379386427253243854791810104120869379525507986270383750499650286106684249027984675067236382543612917882024145261815608895379
e = 5331
c1 = 60668946079423190709851484247433853783238381043211713258950336572392573192737047470465310272448083514859509629066647300714425946282732774440406261265802652068183263460022257056016974572472905555413226634497579807277440653563498768557112618320828785438180460624890479311538368514262550081582173264168580537990
c2 = 43064371535146610786202813736674368618250034274768737857627872777051745883780468417199551751374395264039179171708712686651485125338422911633961121202567788447108712022481564453759980969777219700870458940189456782517037780321026907310930696608923940135664565796997158295530735831680955376342697203313901005151

assert c1 != (c2 * pow(2, e, n)) % n

inv = libnum.invmod(2,n)
def attack():
    PR.<x>=PolynomialRing(Zmod(n) )
    g1 = (x) ^ e - c1
    g2 = (inv*(x-1)) ^ e - c2
    
    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic()
    return -gcd(g1, g2)[0]

m = attack()
print(long_to_bytes(int(m)))

# flag{6a096839-3ccb-46b4-9eb0-841ca85c0f63}

江枫渔火对愁眠

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Crypto.Util.number import *
flag = b'paluctf{******************}'
p = getPrime(512)
q = getPrime(512)
m = bytes_to_long(flag)
n = p * q
e = 0x10001
c = pow(m, e, n)
leak1 = p & q
leak2 = p | q
print(n)
print(leak1)
print(leak2)
print(c)
# 116117067844956812459549519789301338092862193317140117457423221066709482979351921356314593636327834899992321545232613626111009441254302384449742843180876494341637589103640217194070886174972452908589438599697165869525189266606983974250478298162924187424655566019487631330678770727392051485223152309309085945253
# 8605081049583982438298440507920076587069196185463800658188799677857096281403951362058424551032224336538547998962815392172493849395335237855201439663804417
# 13407373154151815187508645556332614349998109820361387104317659096666170318961881115942116046384020162789239054091769561534320831478500568385569270082820389
# 77391898018025866504652357285886871686506090492775075964856060726697268476460193878086905273672532025686191143120456958000415501059102146339274402932542049355257662649758904431953601814453558068056853653214769669690930883469679763807974430229116956128100328073573783801082618261383412539474900566590518020658

题解

又见到这题了

上次我甚至在某群的群文件里看见了这题 p⊕q

1
if (pp & qq) % (2 ** l) == leak1 % (2 ** l) and pp * qq % (2 ** l) == N % (2 ** l) and (pp | qq) % (2 ** l) == leak2 % (2 ** l) :

改一下判断语句就好

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
import sys
import gmpy2
import libnum

sys.setrecursionlimit(3000)

leak1 = 8605081049583982438298440507920076587069196185463800658188799677857096281403951362058424551032224336538547998962815392172493849395335237855201439663804417
leak2 = 13407373154151815187508645556332614349998109820361387104317659096666170318961881115942116046384020162789239054091769561534320831478500568385569270082820389
N = 116117067844956812459549519789301338092862193317140117457423221066709482979351921356314593636327834899992321545232613626111009441254302384449742843180876494341637589103640217194070886174972452908589438599697165869525189266606983974250478298162924187424655566019487631330678770727392051485223152309309085945253
c = 77391898018025866504652357285886871686506090492775075964856060726697268476460193878086905273672532025686191143120456958000415501059102146339274402932542049355257662649758904431953601814453558068056853653214769669690930883469679763807974430229116956128100328073573783801082618261383412539474900566590518020658

def findp(p, q):
    if len(p) == 1024:
        pp = int(p, 2)
        if N % pp == 0:
            print("p = ", pp)
            print("q = ", N // pp)

    else:
        l = len(p)
        pp = int(p, 2)
        qq = int(q, 2)
        if (pp & qq) % (2 ** l) == leak1 % (2 ** l) and pp * qq % (2 ** l) == N % (2 ** l) and (pp | qq) % (2 ** l) == leak2 % (2 ** l) :
            findp('1' + p, '1' + q)
            findp('1' + p, '0' + q)
            findp('0' + p, '1' + q)
            findp('0' + p, '0' + q)

findp('1', '1')

p =  8765698777357218895930455433534622474349736018036786722894513584283441223303812128653973162721831346202633677284766954990094900299096944074318482652846369
q =  13246755426378578729876630630718068462717569987788401039611945190239825377062020349346567434694413153125153375769817998716719780574738862166452227093778437
e = 65537
phi = (p - 1) * (q - 1)

d = libnum.invmod(e, phi)
m = pow(c, d, N)
print(libnum.n2s(m))

# paluctf{&&&|||&&&|||&&&&&&&&&&&&|||||||||}

两元钱的铜匠

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from secret import flag
from Crypto.Util.number import *
m = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
n = p*q
c = pow(m, 65537, n)
N = getPrime(1024)
leak = (pow(9999, 66666)*p + pow(66666, 9999)*q) % N
print(f'n={n}')
print(f'c={c}')
print(f'N={N}')
print(f'leak={leak}')
"""
n=80916351132285136921336714166859402248518125673421944066690210363157948681543515675261790287954711843082802283188843248579293238274583917836325545166981149125711216316112644776403584036920878846575128588844980283888602402513345309524782526525838503856925567762860026353261868959895401646623045981393058164201
c=22730301930220955810132397809406485504430998883284247476890744759811759301470013143686059878014087921084402703884898661685430889812034497050189574640139435761526983415169973791743915648508955725713703906140316772231235038110678219688469930378177132307304731532134005576976892978381999976676034083329527911241
N=175887339574643371942360396913019735118423928391339797751049049816862344090324438786194807609356902331228801731590496587951642499325571035835790931895483345540104575533781585131558026624618308795381874809845454092562340943276838942273890971498308617974682097511232721650227206585474404895053411892392799799403
leak=161177488484579680503127298320874823539858895081858980450427298120182550612626953405092823674668208591844284619026441298155371399651438065337570099147890081125477609238234662000811899869636390550619251741676887565983189442613760093303841954633720778312454175652907352477365434215186845209831284593041581382419
"""

题解

1
leak = (pow(9999, 66666)*p + pow(66666, 9999)*q) % N

两个未知数？不，两边乘以p，就是一个未知数了，模数下的一元二次方程，可解

$leakp=9999^{66666}p^2+66666^{9999}*n \bmod N$

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import libnum

n=80916351132285136921336714166859402248518125673421944066690210363157948681543515675261790287954711843082802283188843248579293238274583917836325545166981149125711216316112644776403584036920878846575128588844980283888602402513345309524782526525838503856925567762860026353261868959895401646623045981393058164201
c=22730301930220955810132397809406485504430998883284247476890744759811759301470013143686059878014087921084402703884898661685430889812034497050189574640139435761526983415169973791743915648508955725713703906140316772231235038110678219688469930378177132307304731532134005576976892978381999976676034083329527911241
N=175887339574643371942360396913019735118423928391339797751049049816862344090324438786194807609356902331228801731590496587951642499325571035835790931895483345540104575533781585131558026624618308795381874809845454092562340943276838942273890971498308617974682097511232721650227206585474404895053411892392799799403
leak=161177488484579680503127298320874823539858895081858980450427298120182550612626953405092823674668208591844284619026441298155371399651438065337570099147890081125477609238234662000811899869636390550619251741676887565983189442613760093303841954633720778312454175652907352477365434215186845209831284593041581382419
e = 65537

PR.<p> = PolynomialRing(Zmod(N))
f = 9999^66666 *p^2 + 66666^9999 *n  - leak*p

p = f.monic().roots()
p = p[1][0]
q = n//p

phi = (p-1)*(q-1)
d = libnum.invmod(e,int(phi))
m = pow(c,d,n)
print(libnum.n2s(int(m)))

# paluctf{6699669966996699669966996699}

peeeq

题目

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


def check(m, p, q):
    if m == 0: return True
    if m >= p and check(m-p, p, q) : return True
    if m >= q and check(m-q, p, q) : return True
    return False

flag = b"paluctf{***********************}"

p = getPrime(1024)
q = getPrime(1024)
e = getPrime(17)
n = p*q


leak = 20650913970072868759959272239604024297420806808659110564312051736808778949599012338389873196411652566474168134639876252857623310159737758732845898956842366935678501021994729279299799994075598575657211550223683499328614158165787416177094173112167115888930719187253398687736037116845083325669521670262760600243895871953940839864925909273175442587377607028910874730344252804963645659770898616148180806608083557249713184454706023876544328444568520666837841566163924062054001534893538655581481021600384148478571641075265311650046699619525464106135807483192890198614434965478741402348088647355476402189540171838712520668315
pinv_e = gmpy2.invert(p, q)*e
qinv_e = gmpy2.invert(q, p)*e
m = bytes_to_long(flag)
c = pow(m, e, n)
print(c)
print(pinv_e)
print(qinv_e)
m = 0
while True:
    assert m <= leak or check(m, p, q)
    m += 1
# 14656499683788461319601710088831412892194505254418064899761498679297764485273476341077222358310031603834624959088854557947176472443021560072783573052603773463734827298069959304747376040480522193600487999140388188743055733577433643210327070027972481119823973316743393323273128561824747871183252082782459568278265418266528855123687868624734106855360408027492126167597948385055908257193701028960507382053300960017612431744000472268868103779169759349652561826935960615964589526055579319224213399173783902104833907847546751649110661705034653912439791460180154034041113546810232929706136321281991114377628823527206109309013
# 12474140378771043865022148848078136936465079800066130234618983104385642778672967864991495110508733111980066517889153671507701349679185396054215439179349403857665966245686661757089470553109534987101888628107055364941617805783362125836104920292552457095662777743387917809524955960583091720618281570118299619677634759
# 1647206449953560407401595632741127506095799998014240087894866808907042944168674423038307995055460808040825182837354682801054048594394389801771888111156812819183105159993880849157459496014737241461466870906700457127028184554416373467332704931423207098246831148428600375416541264997943693621557486559170922000282251

题解

e的话，两数gcd然后factordb一下找到17 bit 的数就是

目光看到代码：

1
2
3
4
5
6
7
8
9
10
def check(m, p, q):
    if m == 0: return True
    if m >= p and check(m-p, p, q) : return True
    if m >= q and check(m-q, p, q) : return True
    return False
    
m = 0
while True:
    assert m <= leak or check(m, p, q)
    m += 1

经典Frobenius coin problem

已知 正整数 a,b 互素，存在非负整数 x，y，使得 N = ax+by ，则称 N 是可表示的，否则称 N 是不可表示的，结论有二：

1）不可表示的最大整数为 ab-a-b ;

2）不可表示的非负整数的个数为：$\frac{1}{2}(a-1)(b-1)$ ;

【群内问答】Frobenius Coin Problem & Frobenius Number (sohu.com)

此题中 leak 就为 不可表示的最大整数

所以 phi = leak + 1

知道这个题目就基本解决了

$pp^{-1} = 1 \bmod q$

$qq^{-1}= 1 \bmod p$

所以 $pp^{-1}-1 = k_1q$ ，$qq^{-1} -1 = k_2p$

相乘最后得到 $(p^{-1}q^{-1}-k_1k_2)n = pp^{-1}+qq^{-1}-1$

根据位数判断，$n = pp^{-1}+qq^{-1}-1$

exp:

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
import libnum

leak = 20650913970072868759959272239604024297420806808659110564312051736808778949599012338389873196411652566474168134639876252857623310159737758732845898956842366935678501021994729279299799994075598575657211550223683499328614158165787416177094173112167115888930719187253398687736037116845083325669521670262760600243895871953940839864925909273175442587377607028910874730344252804963645659770898616148180806608083557249713184454706023876544328444568520666837841566163924062054001534893538655581481021600384148478571641075265311650046699619525464106135807483192890198614434965478741402348088647355476402189540171838712520668315
c = 14656499683788461319601710088831412892194505254418064899761498679297764485273476341077222358310031603834624959088854557947176472443021560072783573052603773463734827298069959304747376040480522193600487999140388188743055733577433643210327070027972481119823973316743393323273128561824747871183252082782459568278265418266528855123687868624734106855360408027492126167597948385055908257193701028960507382053300960017612431744000472268868103779169759349652561826935960615964589526055579319224213399173783902104833907847546751649110661705034653912439791460180154034041113546810232929706136321281991114377628823527206109309013
pinv_e = 12474140378771043865022148848078136936465079800066130234618983104385642778672967864991495110508733111980066517889153671507701349679185396054215439179349403857665966245686661757089470553109534987101888628107055364941617805783362125836104920292552457095662777743387917809524955960583091720618281570118299619677634759
qinv_e = 1647206449953560407401595632741127506095799998014240087894866808907042944168674423038307995055460808040825182837354682801054048594394389801771888111156812819183105159993880849157459496014737241461466870906700457127028184554416373467332704931423207098246831148428600375416541264997943693621557486559170922000282251

# e = libnum.gcd(pinv_e,qinv_e)  # 307689 = 3 * 102563   
e = 102563
phi = leak + 1

pinv = pinv_e // e
qinv = qinv_e // e

# var("p q")
# f1 = p*pinv + q*qinv - 1 == p*q
# f2 = (p-1)*(q-1) == phi
# res = solve([f1,f2],[p,q])
# print(res)

p = 151832619619952089992267716058068444251307600220706203871589765844990819175654042917774490787590849720202969240992246624166668570786235406779778934647681250166384828094778797880304323848041273713831052602978130708287523575488166230706021974231380611512371425017998262828486267505916086636495016213117818476079
q = 136011049679334940861511595857042329781653809853866436171389745534855895446196665892885140663304371230055953209984856118200410958041858815679721863717912611066674050454954534686280510303474769670492647228370259394337403855556056590338482704020086450814990436480639792318856245688841995452742464887239898730723
n = p*q
d = libnum.invmod(e,phi)
m = pow(c,d,n)
print(libnum.n2s(int(m)))

# paluctf{51b98a17-6843-4e3b-b06c-3cd956bc944c}

lcccg

题目

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
python
import secrets
from Crypto.Util.number import bytes_to_long

flag = b'paluctf{***********}'
class LCG:
    def __init__(self):
        self.x = secrets.randbits(64)
        self.a = 2
        self.m = secrets.randbits(64)

        while self.m % 2 == 0:
            self.m = secrets.randbits(64)

        print("m =", self.m)
    
    def next(self):
        self.x = (self.x * self.a) % self.m
        return self.x

lcg = LCG()

assert b"paluctf" in flag
f = bytes_to_long(flag)

l = f.bit_length()
print("length =", l)

r = 0
for i in range(l + 50):
    r += (lcg.next() & 1) << i

print("cipher =", r ^ f)
# m = 7870528503754256659
# length = 311
# cipher = 3255815260238431584829132773479447408817850185229659648404208268001256903206776002292220185602856730646093869

题解

-------------　　　　本文结束　　感谢阅读　　　　-------------