from Crypto.Util.number import* import random from gmpy2 import gcd ,invert import os,random from functools import reduce flag = 'flag{*****}' nbit = 2048 pbit = 658 qbit = nbit-pbit
defGCRT(mi, ai): assert (isinstance(mi, list) andisinstance(ai, list)) curm, cura = mi[0], ai[0] for (m, a) inzip(mi[1:], ai[1:]): d = gcd(curm, m) c = a - cura assert (c % d == 0) K = c / d * invert(curm / d, m / d) cura += curm * K curm = curm * m / d return (cura % curm, curm)
defgenkey(): p = getPrime(pbit) q = getPrime(qbit) assert(gcd(p-1,(q-1)//2) != 1and q >= int(pow(p*q,qbit//nbit))) n = p*q while1: dp,dq = random.getrandbits(50), getPrime(50) d = GCRT([p-1,q-1],[dp,dq])[0] if(gcd(d, (p-1)*(q-1)) == 1): break e = invert(d,(p-1) * (q-1)) return n,e
n,e= genkey()
flag = flag + os.urandom(40)
flag = bytes_to_long(flag) assert(flag<n) print n #24520888125100345615044288264230762903878924272518571342713995342063192899124989891699091460914318368533612522321639660343147487234147817765379565866063142022911783047710228071012334390251457138278189863078398353697056081286846816500611712981402958876560909958985941278622099006464269427107124576069124593580390423932176305639686809675964840679026457045269910781753881177055233058940084858058581167930068081780478893848660425039669034700316924547379360271738374641525963541506226468912132334624110432284070298157810487695608530792082901545749959813831607311669250447276755584806773237811351439714525063949561215550447 print e #11548167381567878954504039302995879760887384446160403678508673015926195316468675715911159300590761428446214638046840120602736300464514722774979925843178572277878822181099753174300465194145931556418080206026501299370963578262848611390583954955739032904548821443452579845787053497638128869038124506082956880448426261524733275521093477566421849134936014202472024600125629690903426235360356780817248587939756911284609010060687156927329496321413981116298392504514093379768896049697560475240887866765045884356249775891064190431436570827123388038801414013274666867432944085999838452709199063561463786334483612953109675470299 printpow(flag,e,n) #7903942109284616971177039757063852086984176476936099228234294937286044560458869922921692962367056335407203285911162833729143727236259599183118544731181209893499971239166798975272362502847869401536913310597050934868114362409772188138668288760287305966467890063175096408668396691058313701210130473560756912616590509776003076415730640467731466851294845080825312579944440742910769345079740436037310725065646739277834041891837233390010487460412084089630786396822488869754420904734966722826157548254882580507819654527378643632759059506306290252851428488883937359516531613654502801727220504711666666550673928496325962262842
X = int(N ** delta*(n+1)/2) Y = int(N ** (delta + beta)*(n+1)/2)
defC(a,b): ret=1 for i inrange(b): ret*=(a-i) ret/=(b-i) return ret defget_Matrix(n,m): MM=[[0for __ inrange(n)] for _ inrange(n)] for j inrange(n): pN=max(0,m-j) for i inrange(j+1): MM[j][i]=pow(N,pN)*pow(X,n-i-1)*pow(Y,i)*pow(e,j-i)*C(j,i)*pow(-1,i) MM=Matrix(ZZ,MM) return MM
M=get_Matrix(n,n//2+1) L=M.LLL()[0]
x,y = var('x'),var('y') f=0 for i inrange(n): f+=x**(n-i-1) * y**i * (L[i] // pow(X,n-i-1) // pow(Y,i))#将x,y参数化
k = k + 1 p = (e * dp - 1) // k + 1 print(int(p).bit_length()) q = n // p print(int(q).bit_length()) d = gmpy2.invert(e,(p-1)*(q-1)) m = pow(c,d,n) print(long_to_bytes(int(m))) #CnHongKe{1b35037a-a472-4e9c-bdba-768f7e84dd0e}
hint = 43691909620514553907337084747877613125770180914725560231672822190047048268654323014909857087117101555550872581680976037673609645072816688179430921113411189775681186282652913102207473404267361338845128228750191128828347979058211793191911795538917687509092140331114867217314732225741963090158157118956958361667 n = 139415227833650606627481949032630333904915784502498383402775795770352459104117035911044614539656661779065034631025979910419387363425628162982061251276669112098757186870838748231794731153245273066810769109396532311364451556967782895742561287251234088360088678874714586399626016737310602036235187097500522638791 R.<x> = PolynomialRing(Zmod(n)) f = x^4 + x^3 + x^2 + x + 2023 - hint res = f.small_roots(X=2^32,beta=0.4) print(res) # res = [4000655279]
$\therefore t = 4000655279$
$\because c\equiv t^m \mod r$
注意到$ len(flag) \le 35 \therefore m \le 2^{280}$,但是r.bit_length()只有263
通过$c \equiv t^m \mod r$求出的m是缺失后的m(这个$m$只有257bit)。
$c \equiv t ^{m} \mod r \longrightarrow c \equiv (c \times 1)\mod r \longrightarrow c \equiv t ^{m’} \times t^{\phi(r)} \mod r$
c = 6580860405834148836110773014414875358234621644983930335529135801623195480368832 n = 139415227833650606627481949032630333904915784502498383402775795770352459104117035911044614539656661779065034631025979910419387363425628162982061251276669112098757186870838748231794731153245273066810769109396532311364451556967782895742561287251234088360088678874714586399626016737310602036235187097500522638791 hint = 43691909620514553907337084747877613125770180914725560231672822190047048268654323014909857087117101555550872581680976037673609645072816688179430921113411189775681186282652913102207473404267361338845128228750191128828347979058211793191911795538917687509092140331114867217314732225741963090158157118956958361667 r = 11779674470989201650533406519886591289516202072957618550910646323186300227953911
R.<x> = PolynomialRing(Zmod(n))
f = x^4 + x^3 + x^2 + x + 2023 - hint res = f.small_roots(X=2^32,beta=0.4) # print(res) t = res[0] # print(t)
t = 4000655279 m = discrete_log(mod(c,r),mod(t,r)) print(int(m).bit_length())
order = [] for i in factor(r-1): ifpow(t,(r-1)//i[0],r) == 1: order.append(i[0])
# print(order) # [2, 17] phi = (r - 1) // 34 for k inrange(2^22): temp = m + k*phi flag = long_to_bytes(temp) try: iflen(flag.decode()) <= 35: print(flag) break except: continue # CnHongKe{cp_smith_with_pollard_p-1}
n = 73553176031506251642448229714220151174734540964434813056145000616720019024269982417494553771890010861489245572362590935764438928110836109730139595790550323300572059713433794357690270439325805603980903813396260703 c = 6035303231100318215656164353047198868742763055193754611914191674005776329646395050293747516587004104241717689072827492745628156828285466831779549229513115371571798719567117034735830671759951028004405762435531685 e = 31387
r = gmpy2.iroot(n,11)[0] for i inrange(100000): p = r**6 + 8*r**4 - 41*r**3 + 14*r**2 - 116*r + 31387 q = r**5 - 9*r**4 + 17*r**3 - 311*r**2 - 16*r + 14029 r = r+1 if isPrime(p) and isPrime(q) and n==p*q: print(p) q = n // p d = gmpy2.invert(e,(p-1)*(q-1)) m = pow(c,d,n) print(long_to_bytes(m)) break # b'CnHongKe{m0re_fuN_RSA!!!}'
from Crypto.Util.number import * from gmpy2 import invert #from secret import flag,e e=11299 flag="CnHongKe{xxxxx}" defenc(key, p): e, n = key cipher = [pow(ord(char), e, n) for char in p] return cipher defdec(pk, c): key, n = pk plain = [chr(pow(char, key, n)) for char in c] return''.join(plain) p = getPrime(512) q = getPrime(512) n = p*q pubkey = (e,n)
e = 11299 n = c = [...] flag = '' for j inrange(len(c)): for i inrange(32,128): ifpow(i,e,n) == c[j]: flag += chr(i) print(flag) #CnHongKe{a8cc755d375811f55cec82153388c}
from Crypto.Util.number import * from secret import flag import random defbase(n, l): bb = [] while n > 0: n, r = divmod(n, l) bb.append(r) return''.join(str(d) for d in bb[::-1]) defprng(secret): seed = base(secret, 5) seed = [int(i) for i inlist(seed)] length = len(seed) R = [[ random.randint(0,4) for _ inrange(length)] for _ inrange(length*2)] S = [] for r in R: s = 0 for index inrange(length): s += (r[index] * seed[index]) % 5 s %= 5 S.append(s) return R, S m = bytes_to_long(flag) R, S = prng(m)
withopen('output.txt', 'w') as f: f.write(f'R = {R}\nS = {S}')
from Crypto.Util.number import * from secret import flag import random
defbase(n, l): bb = [] while n > 0: n, r = divmod(n, l) bb.append(r) return''.join(str(d) for d in bb[::-1])
defprng(secret):
seed = base(secret, 5) seed = [int(i) for i inlist(seed)] length = len(seed) R = [[ random.randint(0,4) for _ inrange(length)] for _ inrange(length**2)] S = [] for r in R: s = 0 for index inrange(length): s += (r[index] + seed[index]) % 5 s %= 2 S.append(s) return R, S
m = bytes_to_long(flag) R, S = prng(m)
withopen('output.txt', 'w') as f: f.write(f'R = {R}\nS = {S}')
withopen('output.txt') as f: s = f.read().splitlines()
R = eval(s[0][4:]) S = eval(s[1][4:])
n = len(R[0])
A = [] B = [] for i inrange(5 * n): a = [] B.append(S[i]) for j inrange(n): if (R[i][j] == 0): a.extend([0, 1, 0, 1 ,0]) elif (R[i][j] == 1): a.extend([1, 0, 1, 0, 0]) elif (R[i][j] == 2): a.extend([0, 1, 0, 0, 1]) elif (R[i][j] == 3): a.extend([1, 0, 0, 1, 0]) elif (R[i][j] == 4): a.extend([0, 0, 1, 0, 1]) A.append(a)
A = matrix(GF(2), A) B = vector(GF(2), B) x = A.solve_right(B) inv = { (1,0,0,0,0): 0, (0,1,0,0,0): 1, (0,0,1,0,0): 2, (0,0,0,1,0): 3, (0,0,0,0,1): 4, }
m = "" for i inrange(n): thing = tuple(x[i*5:(i + 1)*5]) if thing in inv: m += str(inv[thing]) else: thing2 = tuple(1 - x for x in thing) m += str(inv[thing2]) print(m) flag = long_to_bytes(int(m,5)) print(flag) #CnHongKe{179bdc38ea135c35f1f973c039a422a7}
from Crypto.Util.number import * from secret import flag
p = getPrime(512) q = getPrime(512) n = p * q d = getPrime(299) e = inverse(d,(p-1)*(q-1)) m = bytes_to_long(flag) c = pow(m,e,n) hint1 = p >> (512-70) hint2 = q >> (512-70)
import time time.clock = time.time debug = True strict = False helpful_only = True dimension_min = 7# 如果晶格达到该尺寸,则停止移除 # 显示有用矢量的统计数据 defhelpful_vectors(BB, modulus): nothelpful = 0 for ii inrange(BB.dimensions()[0]): if BB[ii,ii] >= modulus: nothelpful += 1 print (nothelpful, "/", BB.dimensions()[0], " vectors are not helpful")
# 显示带有 0 和 X 的矩阵 defmatrix_overview(BB, bound): for ii inrange(BB.dimensions()[0]): a = ('%02d ' % ii) for jj inrange(BB.dimensions()[1]): a += '0'if BB[ii,jj] == 0else'X' if BB.dimensions()[0] < 60: a += ' ' if BB[ii, ii] >= bound: a += '~' #print (a)
# 尝试删除无用的向量 # 从当前 = n-1(最后一个向量)开始 defremove_unhelpful(BB, monomials, bound, current): # 我们从当前 = n-1(最后一个向量)开始 if current == -1or BB.dimensions()[0] <= dimension_min: return BB # 开始从后面检查 for ii inrange(current, -1, -1): # 如果它没有用 if BB[ii, ii] >= bound: affected_vectors = 0 affected_vector_index = 0 # 让我们检查它是否影响其他向量 for jj inrange(ii + 1, BB.dimensions()[0]): # 如果另一个向量受到影响: # 我们增加计数 if BB[jj, ii] != 0: affected_vectors += 1 affected_vector_index = jj # 等级:0 # 如果没有其他载体最终受到影响 # 我们删除它 if affected_vectors == 0: #print ("* removing unhelpful vector", ii) BB = BB.delete_columns([ii]) BB = BB.delete_rows([ii]) monomials.pop(ii) BB = remove_unhelpful(BB, monomials, bound, ii-1) return BB # 等级:1 #如果只有一个受到影响,我们会检查 # 如果它正在影响别的向量 elif affected_vectors == 1: affected_deeper = True for kk inrange(affected_vector_index + 1, BB.dimensions()[0]): # 如果它影响哪怕一个向量 # 我们放弃这个 if BB[kk, affected_vector_index] != 0: affected_deeper = False # 如果没有其他向量受到影响,则将其删除,并且 # 这个有用的向量不够有用 #与我们无用的相比 if affected_deeper andabs(bound - BB[affected_vector_index, affected_vector_index]) < abs(bound - BB[ii, ii]): #print ("* removing unhelpful vectors", ii, "and", affected_vector_index) BB = BB.delete_columns([affected_vector_index, ii]) BB = BB.delete_rows([affected_vector_index, ii]) monomials.pop(affected_vector_index) monomials.pop(ii) BB = remove_unhelpful(BB, monomials, bound, ii-1) return BB # nothing happened return BB """ Returns: * 0,0 if it fails * -1,-1 如果 "strict=true",并且行列式不受约束 * x0,y0 the solutions of `pol` """ defboneh_durfee(pol, modulus, mm, tt, XX, YY): """ Boneh and Durfee revisited by Herrmann and May 在以下情况下找到解决方案: * d < N^delta * |x|< e^delta * |y|< e^0.5 每当 delta < 1 - sqrt(2)/2 ~ 0.292 """ # substitution (Herrman and May) PR.<u, x, y> = PolynomialRing(ZZ) #多项式环 Q = PR.quotient(x*y + 1 - u) # u = xy + 1 polZ = Q(pol).lift() UU = XX*YY + 1 # x-移位 gg = [] for kk inrange(mm + 1): for ii inrange(mm - kk + 1): xshift = x^ii * modulus^(mm - kk) * polZ(u, x, y)^kk gg.append(xshift) gg.sort() # 单项式 x 移位列表 monomials = [] for polynomial in gg: for monomial in polynomial.monomials(): #对于多项式中的单项式。单项式(): if monomial notin monomials: # 如果单项不在单项中 monomials.append(monomial) monomials.sort() # y-移位 for jj inrange(1, tt + 1): for kk inrange(floor(mm/tt) * jj, mm + 1): yshift = y^jj * polZ(u, x, y)^kk * modulus^(mm - kk) yshift = Q(yshift).lift() gg.append(yshift) # substitution # 单项式 y 移位列表 for jj inrange(1, tt + 1): for kk inrange(floor(mm/tt) * jj, mm + 1): monomials.append(u^kk * y^jj) # 构造格 B nn = len(monomials) BB = Matrix(ZZ, nn) for ii inrange(nn): BB[ii, 0] = gg[ii](0, 0, 0) for jj inrange(1, ii + 1): if monomials[jj] in gg[ii].monomials(): BB[ii, jj] = gg[ii].monomial_coefficient(monomials[jj]) * monomials[jj](UU,XX,YY) #约化格的原型 if helpful_only: # #自动删除 BB = remove_unhelpful(BB, monomials, modulus^mm, nn-1) # 重置维度 nn = BB.dimensions()[0] if nn == 0: print ("failure") return0,0 # 检查向量是否有帮助 if debug: helpful_vectors(BB, modulus^mm) # 检查行列式是否正确界定 det = BB.det() bound = modulus^(mm*nn) if det >= bound: print ("We do not have det < bound. Solutions might not be found.") print ("Try with highers m and t.") if debug: diff = (log(det) - log(bound)) / log(2) print ("size det(L) - size e^(m*n) = ", floor(diff)) if strict: return -1, -1 else: print ("det(L) < e^(m*n) (good! If a solution exists < N^delta, it will be found)") # display the lattice basis if debug: matrix_overview(BB, modulus^mm) # LLL if debug: print ("optimizing basis of the lattice via LLL, this can take a long time") #BB = BB.BKZ(block_size=25) BB = BB.LLL() if debug: print ("LLL is done!") # 替换向量 i 和 j ->多项式 1 和 2 if debug: print ("在格中寻找线性无关向量") found_polynomials = False for pol1_idx inrange(nn - 1): for pol2_idx inrange(pol1_idx + 1, nn): # 对于i and j, 构造两个多项式 PR.<w,z> = PolynomialRing(ZZ) pol1 = pol2 = 0 for jj inrange(nn): pol1 += monomials[jj](w*z+1,w,z) * BB[pol1_idx, jj] / monomials[jj](UU,XX,YY) pol2 += monomials[jj](w*z+1,w,z) * BB[pol2_idx, jj] / monomials[jj](UU,XX,YY) # 结果 PR.<q> = PolynomialRing(ZZ) rr = pol1.resultant(pol2) if rr.is_zero() or rr.monomials() == [1]: continue else: print ("found them, using vectors", pol1_idx, "and", pol2_idx) found_polynomials = True break if found_polynomials: break ifnot found_polynomials: print ("no independant vectors could be found. This should very rarely happen...") return0, 0 rr = rr(q, q) # solutions soly = rr.roots() iflen(soly) == 0: print ("Your prediction (delta) is too small") return0, 0 soly = soly[0][0] ss = pol1(q, soly) solx = ss.roots()[0][0] return solx, soly defexample(): ############################################ # 随机生成数据 ########################################## #start_time =time.perf_counter start =time.clock() size=512 length_N = 2*size; ss=0 s=70; M=1# the number of experiments delta = 299/1024 # p = random_prime(2^512,2^511) for i inrange(M): # p = random_prime(2^size,None,2^(size-1)) # q = random_prime(2^size,None,2^(size-1)) # if(p<q): # temp=p # p=q # q=temp N = e = c = hint1 = # p高位 hint2 = # q高位 # print ("p真实高",s,"比特:", int(p/2^(512-s))) # print ("q真实高",s,"比特:", int(q/2^(512-s))) # N = p*q; # 解密指数d的指数( 最大0.292) m = 7# 格大小(越大越好/越慢) t = round(((1-2*delta) * m)) # 来自 Herrmann 和 May 的优化 X = floor(N^delta) # Y = floor(N^(1/2)/2^s) # 如果 p、 q 大小相同,则正确 for l inrange(int(hint1),int(hint1)+1): print('\n\n\n l=',l) pM=l; p0=pM*2^(size-s)+2^(size-s)-1; q0=N/p0; qM=int(q0/2^(size-s)) A = N + 1-pM*2^(size-s)-qM*2^(size-s); #A = N+1 P.<x,y> = PolynomialRing(ZZ) pol = 1 + x * (A + y) #构建的方程 # Checking bounds #if debug: #print ("=== 核对数据 ===") #print ("* delta:", delta) #print ("* delta < 0.292", delta < 0.292) #print ("* size of e:", ceil(log(e)/log(2))) # e的bit数 # print ("* size of N:", len(bin(N))) # N的bit数 #print ("* size of N:", ceil(log(N)/log(2))) # N的bit数 #print ("* m:", m, ", t:", t) # boneh_durfee if debug: ##print ("=== running algorithm ===") start_time = time.time() solx, soly = boneh_durfee(pol, e, m, t, X, Y) if solx > 0: #print ("=== solution found ===") ifFalse: print ("x:", solx) print ("y:", soly) d_sol = int(pol(solx, soly) / e) ss=ss+1