先在此感谢Kicky_Mu的博客，保留了很多赛事的题面，让我的学习方便了很多

我玩青水的

题面：

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

m = bytes_to_long(flag)
e = 2
p = getPrime(512)
c = pow(m, e, p)

print(f"p = {p}")
print(f"c = {c}")

'''
p = 7709388356791362098686964537734555579863438117190798798028727762878684782880904322549856912344789781854618283939002621383390230228555920884200579836394161
c = 5573755468949553624452023926839820294500672937008992680281196534187840615851844091682946567434189657243627735469507175898662317628420037437385814152733456
'''

分析：

e = 2，二次剩余，

我最开始的想法是二次剩余的特殊的情况，但是测试发现p%4!=3，所以pass

然后也想到了rabin加密，但是发现p无法分解，所以pass

最后，直接解有限域下的多项式方程即可

exp:

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

p = 7709388356791362098686964537734555579863438117190798798028727762878684782880904322549856912344789781854618283939002621383390230228555920884200579836394161
c = 5573755468949553624452023926839820294500672937008992680281196534187840615851844091682946567434189657243627735469507175898662317628420037437385814152733456
e = 2

PR.<x> = PolynomialRing(Zmod(p))
f = x^2 - c
f = f.monic()
res = f.roots()
for m in res:
    print(long_to_bytes(int(m[0])))

Hard_ECC

题面:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from flag import flag

A = [0,
     3,
     0,
     973467756888603754244984534697613606855346504624,
     864199516181393560796053875706729531134503137794]
p = 992366950031561379255380016673152446250935173367
ec = EllipticCurve(GF(p), [A[0], A[1], A[2], A[3], A[4]])
T = ec.random_point()
secret = int.from_bytes(flag, 'little')
Q = T * secret
print(T, Q)
# (295622334572794306408950267006569138184895225554 : 739097242015870070426694048559637981600496920065 : 1)
# (282367703408904350779510132139045982196580800466 : 411950462764902930006129702137150443195710071159 : 1)

分析:

构造了一个椭圆曲线，进行了一次曲线的标量乘法，ECDLP秒了

主要注意这个secret是小端序，所以最后的结果要倒置

exp:

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 *
from gmpy2 import *

A = [0,
3,
0,
973467756888603754244984534697613606855346504624,
864199516181393560796053875706729531134503137794]
p = 992366950031561379255380016673152446250935173367
E = EllipticCurve(GF(p), [A[0], A[1], A[2], A[3], A[4]])

T = (295622334572794306408950267006569138184895225554 , 739097242015870070426694048559637981600496920065 )
Q = (282367703408904350779510132139045982196580800466 , 411950462764902930006129702137150443195710071159 )

T = E(T)
Q = E(Q)

secret = T.discrete_log(Q)

print(long_to_bytes(secret)[::-1])

OEIS2

题面:

1
2
3
4
5
6
from hashlib import *
upper = 2**28 + 5
res = 1
for i in range(1, upper + 1):
    res *= i
flag = 'Beginctf{' + sha256(str(sum([int(i) for i in str(res)])).encode()).hexdigest() + '}'

分析:

主要就是要算个upper的阶乘，用sage里的**factorial()**即可

exp:

1
2
3
4
5
6
7
8
9
from hashlib import *

number = factorial(2**28+5)

t = sum(int(d) for d in str(number))
print(t)

flag = 'Beginctf{' + sha256(str(t).encode()).hexdigest() + '}'
print(flag)

fake_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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 from Crypto.Util.number import *
from secret import flag

def fakeN_list():
    puzzle_list = []

    for i in range(15):
        r = getPrime(32)
        puzzle_list.append(r)

    p = getPrime(32)
    q = getPrime(32)
    com = p*q

    puzzle_list.append(com)

    return puzzle_list

def encrypt(m,e,fake_n_list):

    fake_n = 1
    for i in range(len(fake_n_list)):
        fake_n *= fake_n_list[i]

    really_n = 1
    for i in range(len(fake_n_list)-1):
        really_n *= fake_n_list[i]

    c = pow(m,e,really_n)

    print("c =",c)
    print("fake_n =",fake_n)

if __name__ == '__main__':
    m = bytes_to_long(flag)
    e = 65537
    fake_n_list = fakeN_list()
    encrypt(m,e,fake_n_list)

'''
c = 6451324417011540096371899193595274967584961629958072589442231753539333785715373417620914700292158431998640787575661170945478654203892533418902
fake_n = 178981104694777551556050210788105224912858808489844293395656882292972328450647023459180992923023126555636398409062602947287270007964052060975137318172446309766581
'''

分析：

fake_n_list：15个32bit的素数和一个n

fake_n是由这十六个因子乘积得到的，really_n则是前15个素数乘积得到的

直接用sage内置的factor得到所有因子，注意此时得到的因子是15个素数和p,q,一共17个

可以用itertools库中的combinations生成所有可能的组合，爆破一下就行

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

c = 6451324417011540096371899193595274967584961629958072589442231753539333785715373417620914700292158431998640787575661170945478654203892533418902
fake_n = 178981104694777551556050210788105224912858808489844293395656882292972328450647023459180992923023126555636398409062602947287270007964052060975137318172446309766581
e = 65537

primes = []
for i in factor(fake_n):
    primes.append(i[0])
print(primes)

for prime in combinations(primes, len(primes)-2):
    n = 1
    for p in prime:
        n *= p
    phi = 1
    for p in prime:
        phi *= (p-1)
    d = invert(e, phi)
    m = pow(c, d, n)
    try:
        print(long_to_bytes(m).decode())
    except:
        pass

begin_rsa

题面:

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
from Crypto.Util.number import *
from gmpy2 import *
from secret import flag
m = bytes_to_long(flag)

while True:
    e = 65537
    p1 = getPrime(512)
    q1 = getPrime(512)
    n1 = p1 * q1
    p1_xor_q1_low = (p1 ^ q1) & ((1 << 402) - 1)
    if p1_xor_q1_low >= 10**121 and p1_xor_q1_low <= 10**122 - 1:
        p2 = next_prime(p1_xor_q1_low)
        q2 = int(str(p2)[61:] + str(p2)[:61])
        n2 = p2 * q2
        if isPrime(p2) and isPrime(q2):
            delta = p2 - p1_xor_q1_low
            c = pow(m, e, n1)
            print(f"delta = {delta}")
            print(f"n1 = {n1}")
            print(f"n2 = {n2}")
            print(f"c = {c}")
            break

'''
delta = 61
n1 = 150838784531830142890659431841610000561921043629625618437510373123377520444955469509903631548754842609295975005302780725591929018884805452687677684641162979092069629817740554095750189248769936750051172301891394503776919559958638203717583333429953061416588208428893436430392654983424277005324307321992921302331
n2 = 102603788692700558034198259394482879736866145355211103067657972779629890324418113112441175321034955422723378003769267804892308121194871227786783930178021669484220789624643889449429959522560822967157677629720685465873700893389751397027159036419
c = 100199300622156732994823007073822662584719346985430234367094043002848132740563819931486477742264272832060136969084318984512567787814048659200236334994498141562184235841854521058494238451300610422156322926341430748222140189349893444976932184031798101999886029853099171189139509539715437105818418407563733036131
'''

分析:

题目生成两个素数p~1~,q~1~，并计算了 它们异或结果的低402位并记作p1_xor_q1_low，并判断了此值的十进制范围

取此值的next_prime为p2，并将p2的十进制前半段和后半段交换得到q2

  • 我们要先求出p2,q2得到p1_xor_q1_low，再求出p1,q1

  • 由前后半段交换我们可以记为：
    $$
    p_2\ =\ 10^{61}*a\ +\ b\
    q_2\ =\ 10^{61}*b\ +\ a
    $$

  • 然后就有：
    $$
    n_2\ =\ (10^{61}*a+b)(10^{61}b+a)\
    \
    n_2\ =\ 10^{122}ab+10^{61}(a^2+b^2)+a    b
    $$

    1
    2
    3
    4
    5
    6
    7
    8
    9
             a   b
        *    b   a
    -----------------
            abh abl
        aah aal
        bbh bbl
    abh abl
     
    n[:60] n[60:121] ... n[-61:]

    可以发现n2的十进制低61位就是ab的低61位，高61位就是ab的高61位

    考虑到有一位的进数影响，因此需要爆破一下

  • 有了ab后就可以得到a^2^+b^2^，自然就可以解出a和b了，那么也就有了p1_xor_q1_low

  • 最后，剪枝＋coppersmith

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

e = 65537
delta = 61
n1 = 150838784531830142890659431841610000561921043629625618437510373123377520444955469509903631548754842609295975005302780725591929018884805452687677684641162979092069629817740554095750189248769936750051172301891394503776919559958638203717583333429953061416588208428893436430392654983424277005324307321992921302331
n2 = 102603788692700558034198259394482879736866145355211103067657972779629890324418113112441175321034955422723378003769267804892308121194871227786783930178021669484220789624643889449429959522560822967157677629720685465873700893389751397027159036419
c = 100199300622156732994823007073822662584719346985430234367094043002848132740563819931486477742264272832060136969084318984512567787814048659200236334994498141562184235841854521058494238451300610422156322926341430748222140189349893444976932184031798101999886029853099171189139509539715437105818418407563733036131

#part1 get p2
carrylist = [""] + [str(i) for i in range(10)]
for i in carrylist:
    try:
        ab = int(str(n2//10^(122+61)) + i + str(n2%10^61))
        a2_b2 = (n2 - ab*(10^122+1))//10^61
        temp = iroot((a2_b2 + 2*ab),2)[1]
        if(temp == True):
            aplusb = iroot(a2_b2 + 2*ab,2)[0]
            aminusb = iroot(a2_b2 - 2*ab,2)[0]
            a = (aplusb + aminusb) // 2
            b = aplusb - a
            p2 = a*10^61+b
            q2 = n2 // p2
            print(p2-delta)
            print(q2-delta)
    except:
        pass

leak = 10046182803426524264884288617724249912105444610090073402734131021321139584526984358095762482718044064584704548733703637802
#leak = 10213211395845269843580957624827180440645847045487337036378631004618280342652426488428861772424991210544461009007340273352


#part2 dfs and copper
leakbits = 402
a1 = bin(leak)[2:].zfill(leakbits)[::-1]
def find(p,q):
    l = len(p)
    mask = 2^l
    if(int(p,2)*int(q,2) % mask != n1 % mask):
        return

    if(l == leakbits):
        pp = int(p,2)
        PR.<x> = PolynomialRing(Zmod(n1))
        f = (2^leakbits)*x + pp
        f = f.monic()
        res = f.small_roots(X=2^(512-leakbits), beta=0.5)
        if(res):
            try:
                ph = int(res[0])
                p = (2^leakbits)*ph + pp
                q = n1 // p
                d = inverse(e,(p-1)*(q-1))
                print(long_to_bytes(int(pow(c,d,n1))))
            except:
                pass
                    
    else:
        if(a1[l] == "1"):
            find("1"+p,"0"+q)
            find("0"+p,"1"+q)
        else:
            find("0"+p,"0"+q)
            find("1"+p,"1"+q)

tempp = "1"
tempq = "1"
find(tempp,tempq)

PAD

题面：

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
import random, math

from Crypto.Util.number import *
from flag import flag
flag=flag[:64]
assert len(flag) == 64

class RSA():
    def __init__(self, m: int):
        self.p, self.q, self.e, self.m = getPrime(512), getPrime(512), getRandomRange(1,8), m
        self.n = self.p * self.q
    def Publickey(self):
        return (self.n, self.e,self.c)
    def Encrypt(self):
        pad = PAD(m=self.m, e=0)
        pad.PAD()
        self.c = (pad.e,pow(pad.M, self.e, self.n))
class PAD():
    def __init__(self, m: int, e):
        self.e, self.m, self.mbits = e, m, m.bit_length()
        if e == 0:
            self.e = getRandomRange(2, 7)
    def PAD(self):
        self.M = pow(self.e, self.mbits) + pow(self.m, self.e)
GIFT = bytes_to_long(flag)
with open("GIFT.txt", "w") as f:
    for i in range(40):
        rsa = RSA(m=GIFT)
        rsa.Encrypt()
        f.write(str(rsa.Publickey()) + "\n")

同时给了一个附件GIFT.txt

分析：

$$
c\ =\ (e_2^{mbits}+m^{e_2})^{e_1}\ mod\ n
$$

其中mbits约等于512，考虑一般是不到的，我们取511

1<= e~1~ <=8，2<=e~2~<=8

但是直接去解并不容易，考虑可不可以找一组简单的数据直接解

在txt文件中找到了一组很好算的数据==>e~1~ = 1，e~2~ = 2
$$
c\ =\ (2^{511}+m^{2})\ mod\ n
$$
直接做差开方即可

exp:

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

with open(r"GIFT.txt","r") as f:
    for i in range(40):
        temp = eval(f.readline())
        if(temp[1]==1 and temp[2][0]==2):
            n = temp[0]
            e1 = temp[1]
            e2 = temp[2][0]
            c = temp[2][1]
            
c = c - 2**512
m = iroot(c,2)[0]
print(long_to_bytes(m))

PAD_revenge

题面：

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 *
from flag import flag

assert len(flag) == 64

class RSA():
    def __init__(self, m: int):
        self.p, self.q, self.e, self.m = getPrime(256), getPrime(256), getRandomRange(1,9), m
        self.n = self.p * self.q
    def Publickey(self):
        return (self.n, self.e,self.c)
    def Encrypt(self):
        pad = PAD(m=self.m, e=0)
        pad.PAD()
        self.c = (pad.e,pow(pad.M, self.e, self.n))
class PAD():
    def __init__(self, m: int, e):
        self.e, self.m, self.mbits = e, m, m.bit_length()
        if e == 0:
            self.e = getRandomRange(1, 9)
    def PAD(self):
        self.M = pow(self.e, self.mbits) + pow(self.m, self.e)
GIFT = bytes_to_long(flag)

with open("GIFT.txt", "w") as f:
    for i in range(100):
        rsa = RSA(m=GIFT)
        rsa.Encrypt()
        data=rsa.Publickey()
        if data[1]*data[2][0]<=2:
            continue
        f.write(str(data) + "\n")

附件GIFT.txt

分析:

其实最重要的区别就是n_bits = 512变小了，以及e1*e2 >2

那么对于
$$
(e_2^{mbits}+m^{e_2})^{e_1}\ >\ n
$$
所以不能像PAD一样解，但可以从txt文件中找到多组(e1，e2)相等的数据，直接

中国剩余定理，启动!!!

exp:

这里找(e1,e2) = (3,3)的来解，解出结果后开三次方根即可

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

n = []
c = []
with open(r"GIFT.txt","r") as f:
    for i in range(100):
        temp = eval(f.readline())
        if(temp[1]==3 and temp[2][0]==3):
            n.append(temp[0])
            c.append(temp[2][1] - 3**511)
x = crt(n,c)[0]
m = iroot(x,3)[0]
print(long_to_bytes(m))

baph

题面：

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
from base64 import b64encode
from Crypto.Util.number import *
from string import ascii_letters
from flag import flag

ls = ascii_letters + '!,.? {}' + '01232456789'
assert all([i in ls for i in flag])
ba = b64encode(flag.encode())
baph, key = '', ''

for b in ba.decode():
	if b.islower():
		baph += b.upper()
		key += '0'
	else:
		baph += b.lower()
		key += '1'

baph = baph.encode()
key = long_to_bytes(int(key, 2))
enc = b''
for i in range(len(baph)):
	enc += long_to_bytes(baph[i] ^ key[i % len(key)])

f = open('flag.enc', 'wb')
f.write(enc)
f.close()

#enc = 'f72e1c66945c11828c1c9b61ce2e221eaa181dae8a49e279cf2d2966871c20a1bb1c977bf71b367eac1833bca749d81bce041c78ad5d09d4b45dcc67c90b3666975d11bca749c067cf2a2667941c27aab463d463f450367eaa2230aea75dc816'

分析：(以后见)

参考：https://www.cnblogs.com/mumuhhh/p/18011785