hgame2025-week1 crypto

hgame week1

sieve

题目代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#sage
from Crypto.Util.number import bytes_to_long
from sympy import nextprime

FLAG = b'hgame{xxxxxxxxxxxxxxxxxxxxxx}'
m = bytes_to_long(FLAG)

def trick(k):
    if k > 1:
        mul = prod(range(1,k)) 
        if k - mul % k - 1 == 0:
            return euler_phi(k) + trick(k-1) + 1
        else:
            return euler_phi(k) + trick(k-1)
    else:
        return 1

e = 65537
p = q = nextprime(trick(e^2//6)<<128)
n = p * q
enc = pow(m,e,n)
print(f'{enc=}')
#enc=2449294097474714136530140099784592732766444481665278038069484466665506153967851063209402336025065476172617376546

$k - mul (mod k) - 1 == 0$ 这里其实是判断k是否是素数

根据威尔逊定理:如果p是一个奇素数或P=2，那么有

$(p-1)!=-1(mod p)$

证明:

设x和它的逆元x-1 如果他们相等则有
$x^2=1 mod p—>(x-1)(x+1)=0mod p$

这是x只能等于p-1或1

p=2时候，显然成立

p是奇素数时：
mul=1*2…*(p-2)*(p-1)

p-1=-1(mod p)

并且对应A=0,1,2..,(p-1)是一个完全的剩余系

从这个完全剩余系里面排除0,1,p-1。得到B=2,3,…,p-2

在B内有偶数个元素，并且都与p互素，并且每两个互逆的元素配对那么

则有 m=2*3*…p-2,m =1 mod p

则$(p-1)!=-1(mod p)$

所以这个递归方程最后返回的trick(e^2//6)=1到p-1所有数的欧拉函数+p以内素数的个数，如果直接强制爆破世界复杂度过高，所以这里我们利用筛法来做。 我自己搞得筛法效率太低了了要一个小时，这里我们分析官方的代码。

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
#include <iostream>
#include <vector>
#include <boost/multiprecision/cpp_int.hpp>

using namespace std;
using namespace boost::multiprecision;

// 使用筛选法计算欧拉函数
void sieve_euler_phi(cpp_int n, vector<cpp_int>& phi) {
    phi.resize(static_cast<std::size_t>(n + 1));

    for (cpp_int i = 0; i <= n; ++i) {
        phi[static_cast<std::size_t>(i)] = i;
    }

    for (cpp_int i = 2; i <= n; ++i) {

        if (phi[static_cast<std::size_t>(i)] == i) { // i是质数
            for (cpp_int j = i; j <= n; j += i) {
                phi[static_cast<std::size_t>(j)] = phi[static_cast<std::size_t>(j)] * (i - 1) / i;
            }
        }
        
        if (i % 100000000 == 0) { // 每计算100000个数输出一次进度

            cout << "Sieved up to " << i.str() << endl;
        }
    }
}

int main() {
    cpp_int n = 715849728; 
    vector<cpp_int> phi;

    sieve_euler_phi(n, phi);

    cpp_int result = 0;
    for (cpp_int i = 1; i <= n; ++i) {
        result += phi[static_cast<std::size_t>(i)];
        if (phi[static_cast<std::size_t>(i)] == i - 1) { // i是质数
            result += 1;
        }
    }

    cout << "Calculated trick(" << n.str() << "): " << result.str() << endl;

    return 0;
}
  • 更简洁的方法我们分开来看,利用了杜教筛
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from sympy import *
from gmpy2 import invert
from Crypto.Util.number import long_to_bytes
e = 65537
n=(e * e) // 6
cache=None
if cache is None:
    cache={}
if n in cache:
    print(cache[n])
if n<1:
    print(n,'=0')
pre_max=min(n,10**6)
print(pre_max)
phi =list(range(pre_max+1))

for p in range(2,pre_max+1):
    if phi[p]==p:
        for m in range(p,pre_max+1,p):
            phi[m] -= phi[m] // p#这里是用于辅助计算，处理小于10**6位时的情况

筛法

这里用到的不算普通的欧拉筛选，而是利用了杜教筛

杜教筛

适用于数论中的积性函数（欧拉函数便是一种积性函数）

  • 积性函数、

若gcd(m,n)=1

f(m*n)=f(m)*f(n)，具体的杜教筛复现文章不多解释，我也不是很会Io的这些(我太菜了)

  • 利用证明（还需要了解，繁反演卷积这些，内容太多了，我也不算很会。就知道怎么用吧

这里贴一篇相关文章杜教筛 - pengym - 博客园

我们便可以得出我们要求的n以内的所有欧拉函数的和$S(n)=n(n+1)/2-\sum^n_{k=2}S([n/k])$

题目代码:

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

def sum_euler_phi(n, cache=None):
    if cache is None:
        cache = {}
    if n in cache:
        return cache[n]
    if n < 1:
        return 0
    # 预处理小范围的欧拉函数
    pre_max = min(n, 10**6)
    phi = list(range(pre_max + 1))
    for p in range(2, pre_max + 1):
        if phi[p] == p:  # p是素数
            for multiple in range(p, pre_max + 1, p):
                phi[multiple] -= phi[multiple] // p
    # 计算前缀和
    s_phi = [0] * (pre_max + 1)
    for i in range(1, pre_max + 1):
        s_phi[i] = s_phi[i - 1] + phi[i]
    # 分块递归处理大范围
    def helper(n):
        a=[]
        if n <= pre_max:
            return s_phi[n]
        res = n * (n + 1) // 2
        k = 2
        while k <= n:
            m = n // k
            next_k = n//m  + 1
            res -= (next_k - k) * helper(m)
            k = next_k

        return res
    result = helper(n)
    cache[n] = result
    return result

e = 65537
k = (e * e) // 6
sum_phi = sum_euler_phi(k)
prime_count = primepi(k)
trick_value = sum_phi + prime_count

shifted_value = trick_value << 128
p = nextprime(shifted_value)
n = p * p  # 因为 p = q
phi = p * (p - 1)
d = invert(e, phi)
enc = 2449294097474714136530140099784592732766444481665278038069484466665506153967851063209402336025065476172617376546
m = pow(enc, d, n)
print(long_to_bytes(m).decode())

superrsa

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
from Crypto.Util.number import *
import random
from sympy import prime
 
FLAG=b'hgame{xxxxxxxxxxxxxxxxxx}'
e=0x10001
 
def primorial(num):
    result = 1
    for i in range(1, num + 1):
        result *= prime(i)  #取前num个素数相乘
    return result
M=primorial(random.choice([39,71,126]))  #39
 
def gen_key():
    while True:
        k = getPrime(random.randint(20,40))
        a = getPrime(random.randint(20,60))
        p = k * M + pow(e, a, M)
        if isPrime(p):
            return p
 
p,q=gen_key(),gen_key()
n=p*q
m=bytes_to_long(FLAG)
enc=pow(m,e,n)

print(f'{n=}')
print(f'{enc=}')
 
"""
n=787190064146025392337631797277972559696758830083248285626115725258876808514690830730702705056550628756290183000265129340257928314614351263713241
enc=365164788284364079752299551355267634718233656769290285760796137651769990253028664857272749598268110892426683253579840758552222893644373690398408
"""

这是一道roca的板子题，原理不太理解，套模板吧

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
133
134
135
136
#p,q=k*M+(65537**a %M)
 
# Hardcoded parameters for efficiency
# Found using params.py
param = \
{
  512: {
    "n": 39,
    "a_max": 62,
    "k_max": 37,
    "M": 0x924cba6ae99dfa084537facc54948df0c23da044d8cabe0edd75bc6,
    "M_prime": 0x1b3e6c9433a7735fa5fc479ffe4027e13bea,
    "m": 5,
    "t": 6,
    "c_a": 0x80000
  }
}
 
# https://github.com/mimoo/RSA-and-LLL-attacks/blob/master/coppersmith.sage
def coppersmith_howgrave_univariate(pol, N, beta, mm, tt, XX):
    """
    Coppersmith revisited by Howgrave-Graham
    finds a solution if:
    * b|N, b >= N^beta , 0 < beta <= 1
    * |x| < XX
    """
    #
    # init
    #
    dd = pol.degree()
    nn = dd * mm + tt
 
    #
    # checks
    #
    if not 0 < beta <= 1 :
        raise ValueError("beta should belongs in (0, 1]")
 
    if not pol.is_monic():
        raise ArithmeticError("Polynomial must be monic.")
 
 
    #
    # Coppersmith revisited algo for univariate
    #
 
    # change ring of pol and x
    polZ = pol.change_ring(ZZ)
    x = polZ.parent().gen()
 
    # compute polynomials
    gg = []
    for ii in range(mm):
        for jj in range(dd):
            gg.append((x * XX)**jj * N**(mm - ii) * polZ(x * XX)**ii)
    for ii in range(tt):
        gg.append((x * XX)**ii * polZ(x * XX)**mm)
 
    # construct lattice B
    BB = Matrix(ZZ, nn)
 
    for ii in range(nn):
        for jj in range(ii+1):
            BB[ii, jj] = gg[ii][jj]
 
    # LLL
    BB = BB.LLL(early_red=True, use_siegel=True)
 
    # transform shortest vector in polynomial
    new_pol = 0
    for ii in range(nn):
        new_pol += x**ii * BB[0, ii] / XX**ii
 
    # factor polynomial
    potential_roots = new_pol.roots()
 
    return [i[0] for i in potential_roots]
 
# Top level of the attack, feeds the queue for the workers
def roca(N):
 
  # Key is not always of perfect size, infer from size
  keylength = int(log(N, 2))
  if keylength < 1000 :
    keylength = 512
  elif  keylength < 2000 :
    keylength = 1024
  elif keylength < 4000 :
    keylength = 2048
  else:
    keylength = 4096
 
  # bruteforce
  M_prime = param[keylength]['M_prime']
  c_prime = discrete_log(N, Mod(65537, M_prime))
  ord_prime = Zmod(M_prime)(65537).multiplicative_order()
  top = (c_prime + ord_prime)/2
  beta = 0.5
  mm = param[keylength]['m']
  tt = param[keylength]['t']
 
  XX = int((2*pow(N, beta)) / M_prime)
 
  # Bruteforce until p, q are found
  a_prime = floor(c_prime/2)
  while a_prime < top:
 
      # Construct polynomial
      m_inv = int(inverse_mod(M_prime, N))
      k_tmp = int(pow(65537, a_prime, M_prime))
      known_part_pol = int(k_tmp * m_inv)
      F = PolynomialRing(Zmod(N), implementation='NTL', names=('x',))
      (x,) = F._first_ngens(1)
      pol = x + known_part_pol
 
      # Get roots of polynomial using coppersmith
      roots = coppersmith_howgrave_univariate(pol, N, beta, mm, tt, XX)
 
      # Check if roots are p, q
      for root in roots:
        factor1 = k_tmp + abs(root) * M_prime
        if mod(N, factor1) == 0:
          factor2 = N // factor1
          return int(factor1), int(factor2)
      a_prime += 1
 
 
 
N=787190064146025392337631797277972559696758830083248285626115725258876808514690830730702705056550628756290183000265129340257928314614351263713241
print ("[+] Factoring %i" % N)
 
factor1, factor2 = roca(N)
 
print ("[+] Found factors of N:")
print ("[+] p =" , factor1)
print ("[+] q =" , factor2)

ez_bag

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
import copy
from Crypto.Util.number import getPrime
from paramiko.util import bit_length

L=[]
list = []
bag = []
p=getPrime(16)
for i in range(1):
    t = p
    a=[getPrime(20) for _ in range(16)]
    b=0
    for j in a:
        temp=t%2
        b+=temp*j
        t=t>>1
    A=copy.deepcopy(a)
    list.append(a)
    L.append(A)
    L[i].append(b)

    bag.append(b)
print(bin(p))
print(p)
print(f'list={list}')
print(f'S={bag}')
print(f'L={L}')
print(bin(p))
# 这里是我用来生成（多维）子集和的python代码

简单的多维子集和，当时还卡了挺久的不过确实学到很多

[文章 - 子集和问题的两种解决方式 - 先知社区]，赛后我写了一篇文章有很清楚的讲解，还有解题代码

GHctf–rsa feirema

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
from Crypto.Util.number import getPrime, bytes_to_long
from secret import f

flag = b'NSSCTF{test_flag}'
p = getPrime(512)
q = getPrime(512)
n = p*q

m = bytes_to_long(flag)
e = 65537
c = pow(m,e,n)

R.<x> = ZZ[]
f = R(str(f))

w = pow(2,f(p),n)


print(f'{n = }\n')
print(f'{e = }\n')
print(f'{c = }\n')
print(f'{f = }\n')
print(f'{w = }\n')


'''
n = 101780569941880865465631942473186578520071435753163950944409148606282910806650879176280021512435190682009749926285674412651435782567149633130455645157688819845748439487113261739503325065997835517112163014056297017874761742768297646567397770742374004940360061700285170103292360590891188591132054903101398360047
e = 65537
c = 77538275949900942020886849496162539665323546686749270705418870515132296087721218282974435210763225488530925782158331269160555819622551413648073293857866671421886753377970220838141826468831099375757481041897142546760492813343115244448184595644585857978116766199800311200819967057790401213156560742779242511746
f = 2*x^332 - x^331 + x^329 + 3*x^328 - x^327 - 3*x^325 + x^323 - 3*x^322 - x^321 - 3*x^320 + x^319 + 2*x^318 - 4*x^317 - 3*x^315 - 2*x^314 + x^313 + x^312 + 2*x^311 + 2*x^309 + 2*x^308 + 5*x^307 + 2*x^306 + 3*x^305 + 5*x^304 + 4*x^303 + x^302 - x^301 - x^300 - 2*x^299 - 2*x^298 + x^297 + 3*x^296 - x^295 - 4*x^292 - x^290 + 4*x^289 - x^287 - 3*x^286 + x^285 - 2*x^284 + x^283 - x^282 - 2*x^281 + x^280 - 2*x^279 + x^278 + 2*x^277 - 3*x^276 - x^275 - 4*x^274 - 3*x^273 - 5*x^272 - 2*x^271 - 3*x^270 + 2*x^269 + 2*x^268 - x^267 - 2*x^266 + x^265 + x^264 - 3*x^262 - 3*x^259 + 2*x^258 - x^257 + 2*x^256 + 2*x^255 - x^254 - 2*x^253 - x^252 + 2*x^251 - x^250 + x^249 + 2*x^247 + 2*x^246 + 2*x^245 - 2*x^244 - 3*x^243 + 2*x^242 - 3*x^241 - x^240 - 3*x^239 - x^236 - 3*x^235 - 2*x^234 - x^233 - 2*x^232 - x^231 - 3*x^230 - 2*x^229 - 4*x^228 - 2*x^227 - 3*x^226 + 2*x^225 + x^224 - x^223 - 2*x^221 + 3*x^219 - x^217 - 2*x^216 + x^215 + 2*x^213 - x^212 + 3*x^211 + x^210 + 4*x^209 + x^208 - x^206 - x^205 - x^204 + 2*x^203 - 3*x^202 + 2*x^199 - x^198 + 2*x^196 - 2*x^195 + 3*x^194 + 3*x^193 - x^192 + 4*x^191 + 2*x^189 + x^186 - x^185 - x^184 + 3*x^183 + x^182 + 2*x^181 - 2*x^180 + x^177 + x^175 - x^173 + 3*x^172 + x^170 + x^169 - x^167 - 2*x^166 - x^165 - 4*x^164 - 2*x^163 + 2*x^162 + 4*x^161 - 2*x^160 - 3*x^159 - 2*x^158 - 2*x^157 + x^156 - x^155 + 3*x^154 - 4*x^153 + x^151 + 2*x^150 + x^149 - x^148 + 2*x^147 + 3*x^146 + 2*x^145 - 4*x^144 - 4*x^143 + x^142 - 2*x^140 - 2*x^139 + 2*x^138 + 3*x^137 + 3*x^136 + 3*x^135 + x^134 - x^133 + 2*x^132 + 3*x^130 - 3*x^129 - 2*x^128 - x^127 - 2*x^126 + x^125 + x^124 - 2*x^123 + x^122 - x^121 + 3*x^120 - x^119 - 2*x^118 - x^117 - x^116 - 2*x^115 + 2*x^114 + 2*x^113 - 3*x^112 - x^111 - 4*x^110 + x^109 + x^108 + x^106 - 4*x^105 + x^104 - x^103 - x^101 + x^100 - 2*x^99 + x^98 - x^97 + 3*x^96 + 3*x^94 - x^93 - x^92 + x^91 - 2*x^90 + x^89 - x^88 + x^87 - x^86 + x^85 + x^84 - x^83 + x^79 - 3*x^78 - 2*x^77 + x^74 + 3*x^73 - x^72 - 3*x^71 - 2*x^70 + x^69 - 3*x^66 + x^65 + x^64 - 4*x^62 - x^61 + x^60 - x^59 + 3*x^58 - x^57 - x^54 + 3*x^53 + x^51 - 3*x^50 - x^49 + 2*x^47 - x^46 - x^44 + x^43 - x^42 - 4*x^41 - 3*x^39 - x^37 - x^36 - 3*x^35 + x^34 + x^33 - 2*x^32 + 2*x^31 - x^30 + 2*x^29 - 2*x^28 - 2*x^27 - x^24 + x^22 - 5*x^21 + 3*x^20 + 2*x^19 - x^18 + 2*x^17 + x^16 - 2*x^15 - 2*x^14 + x^13 + x^12 + 2*x^11 - 3*x^10 + 3*x^9 + 2*x^8 - 4*x^6 - 2*x^5 - 4*x^4 + x^3 - x^2 - 1
w = 32824596080441735190523997982799829197530203904568086251690542244969244071312854874746142497647579310192994177896837383837384405062036521829088599595750902976191010000575697075792720479387771945760107268598283406893094243282498381006464103080551366587157561686900620059394693185990788592220509670478190685244
'''
  • 解题代码
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
from Crypto.Util.number import long_to_bytes
from sage.all import *

n = 101780569941880865465631942473186578520071435753163950944409148606282910806650879176280021512435190682009749926285674412651435782567149633130455645157688819845748439487113261739503325065997835517112163014056297017874761742768297646567397770742374004940360061700285170103292360590891188591132054903101398360047
e = 65537
c = 77538275949900942020886849496162539665323546686749270705418870515132296087721218282974435210763225488530925782158331269160555819622551413648073293857866671421886753377970220838141826468831099375757481041897142546760492813343115244448184595644585857978116766199800311200819967057790401213156560742779242511746
w = 32824596080441735190523997982799829197530203904568086251690542244969244071312854874746142497647579310192994177896837383837384405062036521829088599595750902976191010000575697075792720479387771945760107268598283406893094243282498381006464103080551366587157561686900620059394693185990788592220509670478190685244

# 定义多项式并计算f(1)
R.<x> = ZZ[]
f = 2*x^332 - x^331 + x^329 + 3*x^328 - x^327 - 3*x^325 + x^323 - 3*x^322 - x^321 - 3*x^320 + x^319 + 2*x^318 - 4*x^317 - 3*x^315 - 2*x^314 + x^313 + x^312 + 2*x^311 + 2*x^309 + 2*x^308 + 5*x^307 + 2*x^306 + 3*x^305 + 5*x^304 + 4*x^303 + x^302 - x^301 - x^300 - 2*x^299 - 2*x^298 + x^297 + 3*x^296 - x^295 - 4*x^292 - x^290 + 4*x^289 - x^287 - 3*x^286 + x^285 - 2*x^284 + x^283 - x^282 - 2*x^281 + x^280 - 2*x^279 + x^278 + 2*x^277 - 3*x^276 - x^275 - 4*x^274 - 3*x^273 - 5*x^272 - 2*x^271 - 3*x^270 + 2*x^269 + 2*x^268 - x^267 - 2*x^266 + x^265 + x^264 - 3*x^262 - 3*x^259 + 2*x^258 - x^257 + 2*x^256 + 2*x^255 - x^254 - 2*x^253 - x^252 + 2*x^251 - x^250 + x^249 + 2*x^247 + 2*x^246 + 2*x^245 - 2*x^244 - 3*x^243 + 2*x^242 - 3*x^241 - x^240 - 3*x^239 - x^236 - 3*x^235 - 2*x^234 - x^233 - 2*x^232 - x^231 - 3*x^230 - 2*x^229 - 4*x^228 - 2*x^227 - 3*x^226 + 2*x^225 + x^224 - x^223 - 2*x^221 + 3*x^219 - x^217 - 2*x^216 + x^215 + 2*x^213 - x^212 + 3*x^211 + x^210 + 4*x^209 + x^208 - x^206 - x^205 - x^204 + 2*x^203 - 3*x^202 + 2*x^199 - x^198 + 2*x^196 - 2*x^195 + 3*x^194 + 3*x^193 - x^192 + 4*x^191 + 2*x^189 + x^186 - x^185 - x^184 + 3*x^183 + x^182 + 2*x^181 - 2*x^180 + x^177 + x^175 - x^173 + 3*x^172 + x^170 + x^169 - x^167 - 2*x^166 - x^165 - 4*x^164 - 2*x^163 + 2*x^162 + 4*x^161 - 2*x^160 - 3*x^159 - 2*x^158 - 2*x^157 + x^156 - x^155 + 3*x^154 - 4*x^153 + x^151 + 2*x^150 + x^149 - x^148 + 2*x^147 + 3*x^146 + 2*x^145 - 4*x^144 - 4*x^143 + x^142 - 2*x^140 - 2*x^139 + 2*x^138 + 3*x^137 + 3*x^136 + 3*x^135 + x^134 - x^133 + 2*x^132 + 3*x^130 - 3*x^129 - 2*x^128 - x^127 - 2*x^126 + x^125 + x^124 - 2*x^123 + x^122 - x^121 + 3*x^120 - x^119 - 2*x^118 - x^117 - x^116 - 2*x^115 + 2*x^114 + 2*x^113 - 3*x^112 - x^111 - 4*x^110 + x^109 + x^108 + x^106 - 4*x^105 + x^104 - x^103 - x^101 + x^100 - 2*x^99 + x^98 - x^97 + 3*x^96 + 3*x^94 - x^93 - x^92 + x^91 - 2*x^90 + x^89 - x^88 + x^87 - x^86 + x^85 + x^84 - x^83 + x^79 - 3*x^78 - 2*x^77 + x^74 + 3*x^73 - x^72 - 3*x^71 - 2*x^70 + x^69 - 3*x^66 + x^65 + x^64 - 4*x^62 - x^61 + x^60 - x^59 + 3*x^58 - x^57 - x^54 + 3*x^53 + x^51 - 3*x^50 - x^49 + 2*x^47 - x^46 - x^44 + x^43 - x^42 - 4*x^41 - 3*x^39 - x^37 - x^36 - 3*x^35 + x^34 + x^33 - 2*x^32 + 2*x^31 - x^30 + 2*x^29 - 2*x^28 - 2*x^27 - x^24 + x^22 - 5*x^21 + 3*x^20 + 2*x^19 - x^18 + 2*x^17 + x^16 - 2*x^15 - 2*x^14 + x^13 + x^12 + 2*x^11 - 3*x^10 + 3*x^9 + 2*x^8 - 4*x^6 - 2*x^5 - 4*x^4 + x^3 - x^2 - 1

k = f(1)  
print(f"计算得到的k值: {k}")

# 计算2^k mod n（处理负指数）
if k >= 0:
    result = pow(2, k, n)
else:
    inv_2 = inverse_mod(2, n) 
    result = pow(inv_2, -k, n)

p = gcd(w - result, n)
q = n // p

# 计算私钥并解密
phi = (p - 1) * (q - 1)
d = inverse_mod(e, phi)
m = pow(c, d, n)
flag = long_to_bytes(int(m))

print(f"分解得到的素数p: {p}")
print(f"分解得到的素数q: {q}")
print(f"解密后的Flag: {flag.decode()}")

原理, $p^k≡p≡1mod(p-1)$ –> $ f(p)≡f(1) mod(p-1)$

则有$2^{f(p)}≡2^{f(1)}modp $明显 $2^{f(p)}-2^{f(1)}=result$能被p整除，且n=p*q所以 p=gcd(result,n)

python > crypto
#crypto #python #ctf
hgame2025-week1 crypto
http://example.com/2025/03/05/hgame week1/
Beitragsautor
fox
Veröffentlicht am
March 5, 2025
Urheberrechtshinweis