20210929-绿城杯-CryptoSecWriteUp

Posted on Edited on In , Views: Symbols count in article: 3.2k Reading time ≈ 3 mins.

 

warmup加密算法

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

str1 = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'


def decode(cipher_text, a, b, m):
    d = gmpy2.invert(a, m)
    plain_text = ''
    for i in cipher_text:
        if i in str1:
            addr = str1.find(i)
            plain_text += str1[d * (addr - b) % m]
        else:
            plain_text += i
    print(plain_text)


cipher = 'aoxL{XaaHKP_tHgwpc_hN_ToXnnht}'
decode(cipher, 37, 23, 52)

RSA-1

尚师傅拿了二血

如果$n=pq$，且$(p,\ q)=1$
$$
c\equiv m^e\ mod\ n\Leftrightarrow c\equiv m^e\ mod\ p,\ c\equiv m^e\ mod\ q\notag
$$

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

n = 17365231154926348364478276872558492775911760603002394353723603461898405740234715001820111548600914907617003806652492391686710256274156677887101997175692277729648456087534987616743724646598234466094779540729413583826355145277980479040157075453694250572316638348121571218759769533738721506811175866990851972838466307594226293836934116659685215775643285465895317755892754473332034234495795936183610569571016400535362762699517686781602302045048532131426035260878979892169441059467623523060569285570577199236309888155833013721997933960457784653262076135561769838704166810384309655788983073376941843467117256002645962737847
c = 6944967108815437735428941286784119403138319713455732155925055928646536962597672941805831312130689338014913452081296400272862710447207265099750401657828165836013122848656839100854719965188680097375491193249127725599660383746827031803066026497989298856420216250206035068180963797454792151191071433645946245914916732637007117085199442894495667455544517483404006536607121480678688000420422281380539368519807162175099763891988648117937777951069899975260190018995834904541447562718307433906592021226666885638877020304005614450763081337082838608414756162253825697420493509914578546951634127502393647068722995363753321912676
e = 0x10001
p = gcd(n, c)
q = n // p
assert n == p * q
padding = 2021 * 1001 * p
print(long_to_bytes(pow(c, invert(e, (p-1)*(q-1)), n) // padding))

RSA2-PLUS

第二层解个方程就好，第一层主要用到费马分解，分解出来可能是$pq$和$p_1q_1$，或$pq_1$或者$p_1q$，然后设下未知数爆破解方程就好

可以试试，512位的相邻素数之间一般一个差3位数

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
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from Crypto.Util.number import *
from sympy import *
from gmpy2 import invert, iroot
from public import *


# level1
# yafu
pq1 = 79679231796035037354449627487236220201878797729093909877127396750043503300636464774059752126148617367251988043645511172901030621825575172979048675217345099706517900079260617448298874437193769061144201311929792287772928471712053565834702260975126852624433945451405258351557569670978748727663718174543709899747

p1q = n1 // pq1
z = abs(pq1 - p1q)


def brute_force_pq():
    for x in range(2, 1000, 2):
        for y in range(2, 1000, 2):
            delta = (x * y + z) ** 2 + 4 * x * y * p1q
            if delta > 0 and iroot(delta, 2)[1]:
                p = ((-z - x * y) + iroot(delta, 2)[0]) // (2 * x)
                if isPrime(p):
                    q1 = p1q // p
                    p1, q = nextprime(p), prevprime(q1)
                    phi = (p1 - 1) * (q1 - 1) * (p - 1) * (q - 1)
                    return phi


# level2
a = symbols('a')
b = symbols('b')
ans = solve([a * b - p2q2,  a + b - p2_q2], [a, b])[0]
p2, q2 = ans
if n2 != p2 ** 2 * q2 ** 3:
    p2, q2 = q2, p2
assert n2 == p2 ** 2 * q2 ** 3
phi1 = brute_force_pq()
phi2 = int((p2 - 1) * p2 * (q2 - 1) * q2 ** 2)
print(long_to_bytes(pow(c1, invert(e, phi1), n1)).decode(), end='')
print(long_to_bytes(pow(c2, invert(e, phi2), n2)).decode())