寒假练习
sieve
题目：
#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
这道题应用了威尔逊定理，当t是素数是有：
可以知道trick函数就是：
若k是素数时，那么加上素数本身
若k不是素数时，那么加上k的欧拉函数
就可以直接写一个暴力的遍历，大概32线程得算半个小时
exp：
from Crypto.Util.number import *
from tqdm import trange
from multiprocessing import Pool
from sympy import nextprime
e = 65537
def attack(range):
sum = 0
low = range[0]
up = range[1]
for i in trange (low,up):
if isPrime(i) == 1:
sum += i
else:
sum +=euler_phi(i)
return sum
ranges = [(i,i + 22370304) for i in range(0,(e^2)//6,22370304)]
with Pool(32) as pool:
r = list(pool.imap(attack,ranges))
# s = [152112632221601, 456337891708778, 760563153385075, 1064788432900908, 1369013679480153, 1673238964967408, 1977464210577528, 2281689470925397, 2585914718885781, 2890140015070371, 3194365320284588, 3498590502229128, 3802815803774237, 4107041057080815, 4411266356492306, 4715491596737003, 5019716821093504, 5323942127871198, 5628167370304753, 5932392679368064, 6236617965137888, 6540843088821975, 6845068453853532, 7149293658737784, 7453519081442678, 7757744246853267, 8061969464637097, 8366194743436508, 8670419969136315, 8974645350621916, 9278870487356522, 9583095916072177]
sum = 0
s = [152112632221601, 456337891708778, 760563153385075, 1064788432900908, 1369013679480153, 1673238964967408, 1977464210577528, 2281689470925397, 2585914718885781, 2890140015070371, 3194365320284588, 3498590502229128, 3802815803774237, 4107041057080815, 4411266356492306, 4715491596737003, 5019716821093504, 5323942127871198, 5628167370304753, 5932392679368064, 6236617965137888, 6540843088821975, 6845068453853532, 7149293658737784, 7453519081442678, 7757744246853267, 8061969464637097, 8366194743436508, 8670419969136315, 8974645350621916, 9278870487356522, 9583095916072177]
for i in s:
sum += i
print(sum)
# 155763335231466255
e = 65537
print(155763335231466255+euler_phi((e^2)//6)) #记得加上e^2//6的欧拉函数
p = q = nextprime((155763335447735055)<<128)
n = p * q
phi = (p-1)*q
d = inverse(e,phi)
m = pow(2449294097474714136530140099784592732766444481665278038069484466665506153967851063209402336025065476172617376546,d,n)
print(long_to_bytes(m))
# hgame{sieve_is_n0t_that_HArd}
赛后看到一种快速求解欧拉函数和的方法，在这里记录一下先
#sage
from sympy import nextprime
from sympy.ntheory import primepi
def sum_euler_phi(n):
if n == 0:
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)
s_phi[0] = 0
for i in range(1, pre_max + 1):
s_phi[i] = s_phi[i-1] + phi[i]
# 分块递归计算大范围
cache = {}
def helper(n):
if n in cache:
return cache[n]
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
cache[n] = res
return res
return helper(n)
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 = q = nextprime(shifted_value)
print(f"Calculated trick({k}) = {trick_value}")
print(f"p = q = {p}")
ezBag
题目：
from Crypto.Util.number import *
import random
from Crypto.Cipher import AES
import hashlib
from Crypto.Util.Padding import pad
from secrets import flag
list = []
bag = []
p=random.getrandbits(64)
assert len(bin(p)[2:])==64
for i in range(4):
t = p
a=[getPrime(32) for _ in range(64)]
b=0
for i in a:
temp=t%2
b+=temp*i
t=t>>1
list.append(a)
bag.append(b)
print(f'list={list}')
print(f'bag={bag}')
key = hashlib.sha256(str(p).encode()).digest()
cipher = AES.new(key, AES.MODE_ECB)
flag = pad(flag,16)
ciphertext = cipher.encrypt(flag)
print(f"ciphertext={ciphertext}")
"""
list=[[2826962231, 3385780583, 3492076631, 3387360133, 2955228863, 2289302839, 2243420737, 4129435549, 4249730059, 3553886213, 3506411549, 3658342997, 3701237861, 4279828309, 2791229339, 4234587439, 3870221273, 2989000187, 2638446521, 3589355327, 3480013811, 3581260537, 2347978027, 3160283047, 2416622491, 2349924443, 3505689469, 2641360481, 3832581799, 2977968451, 4014818999, 3989322037, 4129732829, 2339590901, 2342044303, 3001936603, 2280479471, 3957883273, 3883572877, 3337404269, 2665725899, 3705443933, 2588458577, 4003429009, 2251498177, 2781146657, 2654566039, 2426941147, 2266273523, 3210546259, 4225393481, 2304357101, 2707182253, 2552285221, 2337482071, 3096745679, 2391352387, 2437693507, 3004289807, 3857153537, 3278380013, 3953239151, 3486836107, 4053147071], [2241199309, 3658417261, 3032816659, 3069112363, 4279647403, 3244237531, 2683855087, 2980525657, 3519354793, 3290544091, 2939387147, 3669562427, 2985644621, 2961261073, 2403815549, 3737348917, 2672190887, 2363609431, 3342906361, 3298900981, 3874372373, 4287595129, 2154181787, 3475235893, 2223142793, 2871366073, 3443274743, 3162062369, 2260958543, 3814269959, 2429223151, 3363270901, 2623150861, 2424081661, 2533866931, 4087230569, 2937330469, 3846105271, 3805499729, 4188683131, 2804029297, 2707569353, 4099160981, 3491097719, 3917272979, 2888646377, 3277908071, 2892072971, 2817846821, 2453222423, 3023690689, 3533440091, 3737441353, 3941979749, 2903000761, 3845768239, 2986446259, 3630291517, 3494430073, 2199813137, 2199875113, 3794307871, 2249222681, 2797072793], [4263404657, 3176466407, 3364259291, 4201329877, 3092993861, 2771210963, 3662055773, 3124386037, 2719229677, 3049601453, 2441740487, 3404893109, 3327463897, 3742132553, 2833749769, 2661740833, 3676735241, 2612560213, 3863890813, 3792138377, 3317100499, 2967600989, 2256580343, 2471417173, 2855972923, 2335151887, 3942865523, 2521523309, 3183574087, 2956241693, 2969535607, 2867142053, 2792698229, 3058509043, 3359416111, 3375802039, 2859136043, 3453019013, 3817650721, 2357302273, 3522135839, 2997389687, 3344465713, 2223415097, 2327459153, 3383532121, 3960285331, 3287780827, 4227379109, 3679756219, 2501304959, 4184540251, 3918238627, 3253307467, 3543627671, 3975361669, 3910013423, 3283337633, 2796578957, 2724872291, 2876476727, 4095420767, 3011805113, 2620098961], [2844773681, 3852689429, 4187117513, 3608448149, 2782221329, 4100198897, 3705084667, 2753126641, 3477472717, 3202664393, 3422548799, 3078632299, 3685474021, 3707208223, 2626532549, 3444664807, 4207188437, 3422586733, 2573008943, 2992551343, 3465105079, 4260210347, 3108329821, 3488033819, 4092543859, 4184505881, 3742701763, 3957436129, 4275123371, 3307261673, 2871806527, 3307283633, 2813167853, 2319911773, 3454612333, 4199830417, 3309047869, 2506520867, 3260706133, 2969837513, 4056392609, 3819612583, 3520501211, 2949984967, 4234928149, 2690359687, 3052841873, 4196264491, 3493099081, 3774594497, 4283835373, 2753384371, 2215041107, 4054564757, 4074850229, 2936529709, 2399732833, 3078232933, 2922467927, 3832061581, 3871240591, 3526620683, 2304071411, 3679560821]]
bag=[123342809734, 118191282440, 119799979406, 128273451872]
ciphertext=b'\x1d6\xcc}\x07\xfa7G\xbd\x01\xf0P4^Q"\x85\x9f\xac\x98\x8f#\xb2\x12\xf4+\x05`\x80\x1a\xfa !\x9b\xa5\xc7g\xa8b\x89\x93\x1e\xedz\xd2M;\xa2'
"""
造格：
使用BKZ规约出更精确的数，发现最后一组数只有-1和0两种数，应该就是需要的那组向量了
from Crypto.Cipher import AES
import hashlib
list=[[2826962231, 3385780583, 3492076631, 3387360133, 2955228863, 2289302839, 2243420737, 4129435549, 4249730059, 3553886213, 3506411549, 3658342997, 3701237861, 4279828309, 2791229339, 4234587439, 3870221273, 2989000187, 2638446521, 3589355327, 3480013811, 3581260537, 2347978027, 3160283047, 2416622491, 2349924443, 3505689469, 2641360481, 3832581799, 2977968451, 4014818999, 3989322037, 4129732829, 2339590901, 2342044303, 3001936603, 2280479471, 3957883273, 3883572877, 3337404269, 2665725899, 3705443933, 2588458577, 4003429009, 2251498177, 2781146657, 2654566039, 2426941147, 2266273523, 3210546259, 4225393481, 2304357101, 2707182253, 2552285221, 2337482071, 3096745679, 2391352387, 2437693507, 3004289807, 3857153537, 3278380013, 3953239151, 3486836107, 4053147071], [2241199309, 3658417261, 3032816659, 3069112363, 4279647403, 3244237531, 2683855087, 2980525657, 3519354793, 3290544091, 2939387147, 3669562427, 2985644621, 2961261073, 2403815549, 3737348917, 2672190887, 2363609431, 3342906361, 3298900981, 3874372373, 4287595129, 2154181787, 3475235893, 2223142793, 2871366073, 3443274743, 3162062369, 2260958543, 3814269959, 2429223151, 3363270901, 2623150861, 2424081661, 2533866931, 4087230569, 2937330469, 3846105271, 3805499729, 4188683131, 2804029297, 2707569353, 4099160981, 3491097719, 3917272979, 2888646377, 3277908071, 2892072971, 2817846821, 2453222423, 3023690689, 3533440091, 3737441353, 3941979749, 2903000761, 3845768239, 2986446259, 3630291517, 3494430073, 2199813137, 2199875113, 3794307871, 2249222681, 2797072793], [4263404657, 3176466407, 3364259291, 4201329877, 3092993861, 2771210963, 3662055773, 3124386037, 2719229677, 3049601453, 2441740487, 3404893109, 3327463897, 3742132553, 2833749769, 2661740833, 3676735241, 2612560213, 3863890813, 3792138377, 3317100499, 2967600989, 2256580343, 2471417173, 2855972923, 2335151887, 3942865523, 2521523309, 3183574087, 2956241693, 2969535607, 2867142053, 2792698229, 3058509043, 3359416111, 3375802039, 2859136043, 3453019013, 3817650721, 2357302273, 3522135839, 2997389687, 3344465713, 2223415097, 2327459153, 3383532121, 3960285331, 3287780827, 4227379109, 3679756219, 2501304959, 4184540251, 3918238627, 3253307467, 3543627671, 3975361669, 3910013423, 3283337633, 2796578957, 2724872291, 2876476727, 4095420767, 3011805113, 2620098961], [2844773681, 3852689429, 4187117513, 3608448149, 2782221329, 4100198897, 3705084667, 2753126641, 3477472717, 3202664393, 3422548799, 3078632299, 3685474021, 3707208223, 2626532549, 3444664807, 4207188437, 3422586733, 2573008943, 2992551343, 3465105079, 4260210347, 3108329821, 3488033819, 4092543859, 4184505881, 3742701763, 3957436129, 4275123371, 3307261673, 2871806527, 3307283633, 2813167853, 2319911773, 3454612333, 4199830417, 3309047869, 2506520867, 3260706133, 2969837513, 4056392609, 3819612583, 3520501211, 2949984967, 4234928149, 2690359687, 3052841873, 4196264491, 3493099081, 3774594497, 4283835373, 2753384371, 2215041107, 4054564757, 4074850229, 2936529709, 2399732833, 3078232933, 2922467927, 3832061581, 3871240591, 3526620683, 2304071411, 3679560821]]
bag=[123342809734, 118191282440, 119799979406, 128273451872]
ciphertext=b'\x1d6\xcc}\x07\xfa7G\xbd\x01\xf0P4^Q"\x85\x9f\xac\x98\x8f#\xb2\x12\xf4+\x05`\x80\x1a\xfa !\x9b\xa5\xc7g\xa8b\x89\x93\x1e\xedz\xd2M;\xa2'
L=Matrix(ZZ,65,68)
for i in range(64):
L[i,i]=1
L[i,-1]=list[0][i]
L[i,-2]=list[1][i]
L[i,-3]=list[2][i]
L[i,-4]=list[3][i]
L[-1,:]=0
L[-1,-1]=bag[0]
L[-1,-2]=bag[1]
L[-1,-3]=bag[2]
L[-1,-4]=bag[3]
x=L.BKZ()
p = ''
tmp = x[-1][:-4][::-1]
for j in tmp:
if abs(j) == 1:
p += '1'
else:
p += '0'
p = int(p, 2)
print(p)
# 17739748707559623655
key = hashlib.sha256(str(p).encode()).digest()
cipher = AES.new(key, AES.MODE_ECB)
flag = cipher.decrypt(ciphertext)
print(flag)
# hgame{A_S1mple_Modul@r_Subset_Sum_Problem}
suprimeRSA
题目：
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)
return result
M=primorial(random.choice([39,71,126]))
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参考GKCTF2020_Crypto
脚本：GitHub - FlorianPicca/ROCA: A Sage implementation of the ROCA attack
exp：
from tqdm import tqdm
def solve(M, n, a, m):
# I need to import it in the function otherwise multiprocessing doesn't find it in its context
base = int(65537)
# the known part of p: 65537^a * M^-1 (mod N)
known = int(pow(base, a, M) * inverse_mod(M, n))
# Create the polynom f(x)
F = PolynomialRing(Zmod(n), implementation='NTL', names=('x',))
(x,) = F._first_ngens(1)
pol = x + known
beta = 0.1
t = m+1
# Upper bound for the small root x0
XX = floor(2 * n**0.5 / M)
# Find a small root (x0 = k) using Coppersmith's algorithm
roots = coppersmith_howgrave_univariate(pol, n, beta, m, t, XX)
# There will be no roots for an incorrect guess of a.
for k in roots:
# reconstruct p from the recovered k
p = int(k*M + pow(base, a, M))
if n%p == 0:
return p, n//p
def coppersmith_howgrave_univariate(pol, modulus, beta, mm, tt, XX):
"""
Taken from https://github.com/mimoo/RSA-and-LLL-attacks/blob/master/coppersmith.sage
Coppersmith revisited by Howgrave-Graham
finds a solution if:
* b|modulus, b >= modulus^beta , 0 < beta <= 1
* |x| < XX
More tunable than sage's builtin coppersmith method, pol.small_roots()
"""
#
# 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.")
#
# calculate bounds and display them
#
"""
* we want to find g(x) such that ||g(xX)|| <= b^m / sqrt(n)
* we know LLL will give us a short vector v such that:
||v|| <= 2^((n - 1)/4) * det(L)^(1/n)
* we will use that vector as a coefficient vector for our g(x)
* so we want to satisfy:
2^((n - 1)/4) * det(L)^(1/n) < N^(beta*m) / sqrt(n)
so we can obtain ||v|| < N^(beta*m) / sqrt(n) <= b^m / sqrt(n)
(it's important to use N because we might not know b)
"""
#
# 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 * modulus ** (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]
BB = BB.LLL()
# 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()
# test roots
roots = []
for root in potential_roots:
if root[0].is_integer():
result = polZ(ZZ(root[0]))
if gcd(modulus, result) >= modulus ** beta:
roots.append(ZZ(root[0]))
return roots
def roca(n):
keySize = len(bin(n)[2:])
if keySize <= 960:
M_prime = 0x1b3e6c9433a7735fa5fc479ffe4027e13bea
m = 5
elif 992 <= keySize <= 1952:
M_prime = 0x24683144f41188c2b1d6a217f81f12888e4e6513c43f3f60e72af8bd9728807483425d1e
m = 4
print("Have you several days/months to spend on this ?")
elif 1984 <= keySize <= 3936:
M_prime = 0x16928dc3e47b44daf289a60e80e1fc6bd7648d7ef60d1890f3e0a9455efe0abdb7a748131413cebd2e36a76a355c1b664be462e115ac330f9c13344f8f3d1034a02c23396e6
m = 7
print("You'll change computer before this scripts ends...")
elif 3968 <= keySize <= 4096:
print("Just no.")
return None
else:
print("Invalid key size: {}".format(keySize))
return None
a3 = Zmod(M_prime)(n).log(65537)
order = Zmod(M_prime)(65537).multiplicative_order()
inf = a3 // 2
sup = (a3 + order) // 2
# Search 10 000 values at a time, using multiprocess
# too big chunks is slower, too small chunks also
chunk_size = 10000
for inf_a in tqdm(range(inf, sup, chunk_size)):
# create an array with the parameter for the solve function
inputs = [((M_prime, n, a, m), {}) for a in range(inf_a, inf_a+chunk_size)]
# the sage builtin multiprocessing stuff
from sage.parallel.multiprocessing_sage import parallel_iter
from multiprocessing import cpu_count
for k, val in parallel_iter(cpu_count(), solve, inputs):
if val:
p = val[0]
q = val[1]
print("found factorization:\np={}\nq={}".format(p, q))
return val
if __name__ == "__main__":
# Normal values
#p = 88311034938730298582578660387891056695070863074513276159180199367175300923113
#q = 122706669547814628745942441166902931145718723658826773278715872626636030375109
#a = 551658, interval = [475706, 1076306]
# won't find if beta=0.5
# p = 80688738291820833650844741016523373313635060001251156496219948915457811770063
# q = 69288134094572876629045028069371975574660226148748274586674507084213286357069
# #a = 176170, interval = [171312, 771912]
# n = p*q
n = 787190064146025392337631797277972559696758830083248285626115725258876808514690830730702705056550628756290183000265129340257928314614351263713241
# For the test values chosen, a is quite close to the minimal value so the search is not too long
roca(n)
# p=954455861490902893457047257515590051179337979243488068132318878264162627
# q=824752716083066619280674937934149242011126804999047155998788143116757683
from Crypto.Util.number import *
p=954455861490902893457047257515590051179337979243488068132318878264162627
q=824752716083066619280674937934149242011126804999047155998788143116757683
c = 365164788284364079752299551355267634718233656769290285760796137651769990253028664857272749598268110892426683253579840758552222893644373690398408
phi = (p-1)*(q-1)
d = inverse(65537,phi)
print(long_to_bytes(pow(c,d,p*q)))
# hgame{ROCA_ROCK_and_ROll!}