2023江苏省领航杯

记录部分2023江苏省领航杯——Crypto的题目

题目来源于师傅分享,归类可能有问题,题目应该也是不全的,如果有误请师傅们见谅。

高职组–决赛

wp

回文

1
=QfzEDO4YDNlBzN4gzN0YGM1QzYyUGZ3QDZzgDM7V2Sn52bI52Q=

=去掉,密文翻转再base64解密

CnHongKe{083d47de2c450f478870e468813}

RSA2

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
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

def GCRT(mi, ai):
assert (isinstance(mi, list) and isinstance(ai, list))
curm, cura = mi[0], ai[0]
for (m, a) in zip(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)

def genkey():
p = getPrime(pbit)
q = getPrime(qbit)
assert(gcd(p-1,(q-1)//2) != 1 and q >= int(pow(p*q,qbit//nbit)))
n = p*q
while 1:
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
print pow(flag,e,n)
#7903942109284616971177039757063852086984176476936099228234294937286044560458869922921692962367056335407203285911162833729143727236259599183118544731181209893499971239166798975272362502847869401536913310597050934868114362409772188138668288760287305966467890063175096408668396691058313701210130473560756912616590509776003076415730640467731466851294845080825312579944440742910769345079740436037310725065646739277834041891837233390010487460412084089630786396822488869754420904734966722826157548254882580507819654527378643632759059506306290252851428488883937359516531613654502801727220504711666666550673928496325962262842

首先观察d的产生方式,而且p,q相差很大,想到了Unbalanced RSA with Small CRT-Exponent Attack

这里讲了公私钥的产生方式,有个疑惑的点是论文里说了$p-1$和$\frac{q-1}{2}$must be coprime(互素),但是题目附件中

怎会是这样?

网上找了个脚本RSA | Lazzaro (lazzzaro.github.io)

适用于$q(小的那个因子) < N^{0.382}$,这里$\frac{qbit}{nbit}= \frac{658}{2048}\approx0.32$

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
#sage
N=
e=

n = 12 # 或n=5
beta = 0.32 # beta = 0.3212890625
delta = 0.02 # delta = 0.0244140625

X = int(N ** delta*(n+1)/2)
Y = int(N ** (delta + beta)*(n+1)/2)

def C(a,b):
ret=1
for i in range(b):
ret*=(a-i)
ret/=(b-i)
return ret
def get_Matrix(n,m):
MM=[[0 for __ in range(n)] for _ in range(n)]
for j in range(n):
pN=max(0,m-j)
for i in range(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 in range(n):
f+=x**(n-i-1) * y**i * (L[i] // pow(X,n-i-1) // pow(Y,i))#将x,y参数化

print(f.factor())

参数beta:$\beta = \frac{qbit}{nbit} \approx 0.32$

参数delta:$\delta = \frac{dp_bit}{nbit}=\frac{50}{2048} \approx 0.02 $

参数n:n为格子的维度,大佬用下面的式子计算出n,对于本题来说,求得的n=3.408695

但是实际用脚本的过程中,发现n=4并不能得到想要的结果,n=5可能是一个最低值

1
2
3
4
5
beta = 
delta =
n = round((1-2*beta-2*delta)/((1-beta)^2-2*delta-beta),6)
m = (1-beta)*n
print(m,n)

结果得到:

1
...(603601239605461619719962824215850028370828276194986402520006784945171666555162381560306067089554862768237542295127706223128204911327713581268000464342787657534895446276895456449104343518846054862311913534953258511*x + 1115967702502739*y)

从后往前, 第一个是dp,第二个是k

然后利用这两个式子求p

exp:

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

dp =
k =
n =
e =
c =

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}

根据$ed_p + k(p-1) = 1 \longrightarrow p = \frac{ed_p - 1}{k} + 1$

!!!但是,这题不知道为什么k要加上1

总之,理解不太透彻,只能当脚本小子了

RSA3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from Crypto.Util.number import *
from secret import flag
m = bytes_to_long(flag)
p1, q1 = getPrime(512), getPrime(512)
n1 = p1*q1
e = 65537

p2, q2 = getPrime(512), getPrime(512)
n2 = p2*q2

print(f'n1 = {n1}')
print(f'n2 = {n2}')
print(f'c1 = {pow(m,e,n2)}')
print(f'c2 = {pow(n1-m,e,n2)}')

# n1 = 52579135273678950581073020233998071974221658902576724000130040488018033110534210901239397446395736563148970863970460542205225993317478251099451639165369081820130823165642873594136020122857712288395352930384057524510346112486008850200845915783772351449146183974239444691330777565342525218070680067550270554767
# n2 = 68210568831848267339414957973218186686176324296418282565773310695862151827108036984694027795077376921170907068110296451176263520249799154781062517066423984526868547296781709439425857993705489037768605485740968600877866332458671029054092942851472208033494968784822459369206497698469167909174346042658361616469
# c1 = 42941712708129054668823891960764339394032538100909746015733801598044118605733969558717842106784388091495719003761324737091667431446354282990525549196642753967283958283202592037329821712755519455155110675327321252333824912095517427885925854391047828862338332559137577789387455868761466777370476884779752953853
# c2 = 62704043252861638895370674827559804184650708692227789532879941590038911799857232898692335429773480889624046167792573885125945511356456073688435911975161053231589019934427151230924004944847291434167067905803180207183209888082275583120633408232749119300200555327883719466349164062163459300518993952046873724005

e太大了,对于Franklin攻击来说要跑很久,在其他师傅的指引下,了解了half-gcd

参考:HALF-GCD算法的阐述_half gcd_Entropy Increaser的博客-CSDN博客

多项式 gcd 的正确姿势:Half-GCD 算法 - whx1003 - 博客园 (cnblogs.com)

脚本来源:rkm0959_implements/Half_GCD/code.sage at main · rkm0959/rkm0959_implements (github.com)

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

def HGCD(a, b):
if 2 * b.degree() <= a.degree() or a.degree() == 1:
return 1, 0, 0, 1
m = a.degree() // 2
a_top, a_bot = a.quo_rem(x^m)
b_top, b_bot = b.quo_rem(x^m)
R00, R01, R10, R11 = HGCD(a_top, b_top)
c = R00 * a + R01 * b
d = R10 * a + R11 * b
q, e = c.quo_rem(d)
d_top, d_bot = d.quo_rem(x^(m // 2))
e_top, e_bot = e.quo_rem(x^(m // 2))
S00, S01, S10, S11 = HGCD(d_top, e_top)
RET00 = S01 * R00 + (S00 - q * S01) * R10
RET01 = S01 * R01 + (S00 - q * S01) * R11
RET10 = S11 * R00 + (S10 - q * S11) * R10
RET11 = S11 * R01 + (S10 - q * S11) * R11
return RET00, RET01, RET10, RET11

def GCD(a, b):
print(a.degree(), b.degree())
q, r = a.quo_rem(b)
if r == 0:
return b
R00, R01, R10, R11 = HGCD(a, b)
c = R00 * a + R01 * b
d = R10 * a + R11 * b
if d == 0:
return c.monic()
q, r = c.quo_rem(d)
if r == 0:
return d
return GCD(d, r)

sys.setrecursionlimit(500000)

e = 65537
n1 =
n2 =
c1 =
c2 =
R.<x> = PolynomialRing(Zmod(n2))
f = x^e - c1
g = (n1 - x)^e - c2

res = GCD(f,g)

m = -res.monic().coefficients()[0]
print(m)
flag = long_to_bytes(int(m))
print(flag)
#CnHongKe{Fr4nkl1n_R31ter_4nd_gcD}

GCD(f,g)返回$ax -bM$,$a,b$代表任意数字

monic()使得上式变为$x-M$,再提取$M$

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
from Crypto.Util.number import *
from os import *
from secret import flag

assert len(flag) <= 35

m = bytes_to_long(flag)
t = getPrime(32)
p = getPrime(512)
q = getPrime(512)
n = p * q
hint = ((t+q)**4+(t+q)**3+(t+q)**2+(t+q)+2023) % n

r = 11779674470989201650533406519886591289516202072957618550910646323186300227953911

c = pow(t,m,r)

print(c)
print(n)
print(hint)

# 6580860405834148836110773014414875358234621644983930335529135801623195480368832
# 139415227833650606627481949032630333904915784502498383402775795770352459104117035911044614539656661779065034631025979910419387363425628162982061251276669112098757186870838748231794731153245273066810769109396532311364451556967782895742561287251234088360088678874714586399626016737310602036235187097500522638791
# 43691909620514553907337084747877613125770180914725560231672822190047048268654323014909857087117101555550872581680976037673609645072816688179430921113411189775681186282652913102207473404267361338845128228750191128828347979058211793191911795538917687509092140331114867217314732225741963090158157118956958361667

$hint \equiv (t+q)^4+(t+q)^3+(t+q)^2+(t+q) + 2023 \mod n$

展开后发现$hint \equiv t^4 + t^3 + t^2 + t + 2023 + 很多q\mod n$

在Coppersmith下模n,会把q全部模完,所以可以直接求出$t$

1
2
3
4
5
6
7
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$

所以$m = m’ + k\times \phi(r)$

发现m一直出不来

因为$\phi(r)=r-1$有很多因子,$\phi(r)$可能不是$t$模$r$的阶,遍历所有因子,发现存在使得$t^a \equiv 1 \mod r$的因子,经检验得$a=\frac{r-1}{2}$和$a=\frac{r-1}{17}$

所以$t$模$r$的阶为$\frac{r-1}{34}$,记为$\phi’(r)$

这个$\phi’(r)$也满足$t^{\phi’(r)} \equiv 1 \mod r$

尝试$m = m’ + k\times \phi’(r)$,$k$的大小在22bit左右

接着就是爆破k

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

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):
if pow(t,(r-1)//i[0],r) == 1:
order.append(i[0])

# print(order)
# [2, 17]
phi = (r - 1) // 34
for k in range(2^22):
temp = m + k*phi
flag = long_to_bytes(temp)
try:
if len(flag.decode()) <= 35:
print(flag)
break
except:
continue
# CnHongKe{cp_smith_with_pollard_p-1}

复赛

asr

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

def genprime():
while True:
r = getRandomNBitInteger(64)
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
if isPrime(p) and isPrime(q):
return p, q
def enc(flag, n):
m = bytes_to_long(flag)
return pow(m, 31387, n)



p, q = genprime()
n = p * q
c = enc(flag, n)
print(n)
print(c)

$\because p = r^6+8r^4-41r^3+14r^2-116r+31387$

$q = r^5 -9r^4 + 17r^3 - 311r^2-16r +14029$

$\therefore n = r^{11} - 9r^{10} + 25r^9 - 424r^8 + 503r^7 + 10602r^6 + 45292r^5 - 175921r^4 - 5758r^3 - 9563095r^2 - 2129556r + 440328223$

把$n$开11次方,得到的$r’$会略大于或者略小于$r$

爆破一下

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

n = 73553176031506251642448229714220151174734540964434813056145000616720019024269982417494553771890010861489245572362590935764438928110836109730139595790550323300572059713433794357690270439325805603980903813396260703
c = 6035303231100318215656164353047198868742763055193754611914191674005776329646395050293747516587004104241717689072827492745628156828285466831779549229513115371571798719567117034735830671759951028004405762435531685
e = 31387

r = gmpy2.iroot(n,11)[0]
for i in range(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!!!}'

结果发现,只需要$r+1$就行了

脚本来源:2023 江苏领航杯 (qq.com)

ezrsa

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 *              
from gmpy2 import invert
#from secret import flag,e
e=11299
flag="CnHongKe{xxxxx}"

def enc(key, p):
e, n = key
cipher = [pow(ord(char), e, n) for char in p]
return cipher
def dec(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)

assert(e < 20000)
print("Public key:")
print(pubkey[1])
cipher = (enc(pubkey, flag))

print("Encrypted flag:")
print(cipher)

"""
n = 72247494519029483967034760366376786853061601103300157813759661775953565912596351092287547406601293830981872918918938736057259213906558022493243888210973589378711150746378675386713286364059548872717761789465830532496818860955952848759604076974545518597370294034234115061042965941759696027120414108241913315823
c = [23086568633766027889700149282556028601873588133389538577048220777519629053893020835596785887647597774272630671514043075789089166339490664485821551265008072526985961605709337174865785620861795518368806256695564549352791382917399957127324333828822855864895189216581775972150143373812919138450624070271563605781, 61424780590998716668669522879005833894226611068988736111090847848564952203683192799647992306556603909310758923465682857752771528865725336620979965796403804180726836508128298963907214867637490978049881021200499605597084724400813056262536028860369819412653602159130062278358850923752212354694875260742761085298, 48972347185727309580275811398968322398732292284718613286033964656750569533816676490768122129969818200823106363038086076716848785261859085349544695714346759435389253954398744742706972731080540025437559712419376172012608552755595256980994587437212314607911439680754158685958213442852345610886117149808132016667, 61900034054386621130587335874165191153789670659043111868368913383427388843553828977951515166753531254554889530123861241679942156133394477844988559568261609121966239636746106844585498882352452796587012169345091313195906669668187972481122815780919799898784783071380231308771760678158462462371463688337980966056, 61424780590998716668669522879005833894226611068988736111090847848564952203683192799647992306556603909310758923465682857752771528865725336620979965796403804180726836508128298963907214867637490978049881021200499605597084724400813056262536028860369819412653602159130062278358850923752212354694875260742761085298, 9450415868171579852265098054119152648200942770623210086786809222084784959844945630371248180007508011953947300816820109987312423346559505226253550792399518771112488858163511513111841198409634670818742944088825363946933893952656072580401498319136121912520261916028145167846733858193149171599064970439268199783, 10035734578627344969947375235594072983851319696847209997368331158831147669149961069031833471519627366504594153020437204571060611428623914456969214997923532068856482468179965518854707629794312716955250557912419773434419097161023559262564458848063915219346903480654597328232422644596377103117825829328614075690, 5651041338136387965270707005514495599960051787842260459297309665876049923224924292148523058126335232362070965833156272480917510429785778533039914573874120321092901286353688478193761623313802721160582545556066963078690764669931722358118104123077318311422846797054759255064946480668759913078778113387444436772, 14271259146328702790695772784067429851163342737347538777950741762508946650827944617931146968866218980425939274541815935964077603794848153188731356254177631333208035026728310408767228380734867744475231330055609453484352384922899766458129175972076865172633564831188088602907146780176603278159798710852150155253, 62406194652765011605245085350409728452067228284594736543030951188813141827047471129688563874017873401654027493958313799538667190622125421268982329762449606129199279688989354341511243792985075002044026442461088633434402762089223231979549393979184803396697173744411798858018768084174805247172995100258785744206, 63709385155465577684045832627013714734477675077145869296144855691101040965871249828804609100346204070983371062590273336734564969020068052618256509773408613924173909751351554561064586129837540954337160904415625404892669592986127801019807989827319368290273765648256480872195493742292667971088647173453059033806, 48977318868316177241868377840886234518379318740788414464335149639789241373564334219732049732484152649864293157598629604567238775720288389168177046142209467079549232009426147052416900999957014084019576693027561825654624690272350264451017869825303585254430358271190141844081570800201723992346171314406386674943, 48977318868316177241868377840886234518379318740788414464335149639789241373564334219732049732484152649864293157598629604567238775720288389168177046142209467079549232009426147052416900999957014084019576693027561825654624690272350264451017869825303585254430358271190141844081570800201723992346171314406386674943, 565104133813638796527070700551449559996005178784226045,
9297309665876049923224924292148523058126335232362070965833156272480917510429785778533039914573874120321092901286353688478193761623313802721160582545556066963078690764669931722358118104123077318311422846797054759255064946480668759913078778113387444436772, 3956140276099962408524811644378665260926195324627931125735919417604617330787900581903522720016806707086965650313838135840992580442876605474811383818108244966337270671303251812771008272858935652243561913687651063565007930291142413707811828393424201379693530423289355865533076364121921469892110296393354892615, 64940238786056387401400208343541494710106569145648776253264921960848871998112873944735053044143142466740886274718484463159497520574083206269832189589919893550520334911490391957266450195041949757369417242568602992393025242097901450113737739057611554182495438506865992404354942119595468005771945393932589768474, 64940238786056387401400208343541494710106569145648776253264921960848871998112873944735053044143142466740886274718484463159497520574083206269832189589919893550520334911490391957266450195041949757369417242568602992393025242097901450113737739057611554182495438506865992404354942119595468005771945393932589768474, 26352444581944643830963227423429946980811236174292159142870560906116668786800921081108266494217634934060542948019867625299869944900083383044563948756655507024025376518773098977036898176798319228360435941463124583821154981070698271384027340432620539761424919238056654209894138660851835259359180413998571510866, 40143952866342512113851528831224840428508359508863486720333430314639020044892359484055175960350878532212164045297142804890441825145732613460997839927190176844605217276182528040788352071676527553305037569493706223713078036314819975031692707790811142576347096406283580538840499698900522007082050790381461432333, 3956140276099962408524811644378665260926195324627931125735919417604617330787900581903522720016806707086965650313838135840992580442876605474811383818108244966337270671303251812771008272858935652243561913687651063565007930291142413707811828393424201379693530423289355865533076364121921469892110296393354892615, 64940238786056387401400208343541494710106569145648776253264921960848871998112873944735053044143142466740886274718484463159497520574083206269832189589919893550520334911490391957266450195041949757369417242568602992393025242097901450113737739057611554182495438506865992404354942119595468005771945393932589768474, 63709385155465577684045832627013714734477675077145869296144855691101040965871249828804609100346204070983371062590273336734564969020068052618256509773408613924173909751351554561064586129837540954337160904415625404892669592986127801019807989827319368290273765648256480872195493742292667971088647173453059033806, 48888685774691755361314428123012470903274435407919121739086146641066936108772671897622273617773466901370666579985825990735116909193505734002962914749300893402294987407241465624548368394059300582991374404299605248595530416820237532082552535859877438232561386581747696852665114096889765422722443550622873560905, 48888685774691755361314428123012470903274435407919121739086146641066936108772671897622273617773466901370666579985825990735116909193505734002962914749300893402294987407241465624548368394059300582991374404299605248595530416820237532082552535859877438232561386581747696852665114096889765422722443550622873560905, 38583572018907364214647900005166742548285199585572254326541125387795789224923544225334386246655335740938100752554849888600258201438026409196139322439518308323982209353504064739859448757230608480631399883893401220790226127149746215151900805996489931009866529965548635227695192170717058032494324346363053930619, 64940238786056387401400208343541494710106569145648776253264921960848871998112873944735053044143142466740886274718484463159497520574083206269832189589919893550520334911490391957266450195041949757369417242568602992393025242097901450113737739057611554182495438506865992404354942119595468005771945393932589768474, 39561402760999624085248116443786652609261953246279311257359194176046173307879005819035227200168067070869656503,
13838135840992580442876605474811383818108244966337270671303251812771008272858935652243561913687651063565007930291142413707811828393424201379693530423289355865533076364121921469892110296393354892615, 64940238786056387401400208343541494710106569145648776253264921960848871998112873944735053044143142466740886274718484463159497520574083206269832189589919893550520334911490391957266450195041949757369417242568602992393025242097901450113737739057611554182495438506865992404354942119595468005771945393932589768474, 48977318868316177241868377840886234518379318740788414464335149639789241373564334219732049732484152649864293157598629604567238775720288389168177046142209467079549232009426147052416900999957014084019576693027561825654624690272350264451017869825303585254430358271190141844081570800201723992346171314406386674943, 5651041338136387965270707005514495599960051787842260459297309665876049923224924292148523058126335232362070965833156272480917510429785778533039914573874120321092901286353688478193761623313802721160582545556066963078690764669931722358118104123077318311422846797054759255064946480668759913078778113387444436772, 48977318868316177241868377840886234518379318740788414464335149639789241373564334219732049732484152649864293157598629604567238775720288389168177046142209467079549232009426147052416900999957014084019576693027561825654624690272350264451017869825303585254430358271190141844081570800201723992346171314406386674943, 63709385155465577684045832627013714734477675077145869296144855691101040965871249828804609100346204070983371062590273336734564969020068052618256509773408613924173909751351554561064586129837540954337160904415625404892669592986127801019807989827319368290273765648256480872195493742292667971088647173453059033806, 21643731734484252696109953515687478013118937715056061520976924340371395968660338303624558633862679263768843575243426341986847599097591917653435606042602095144570247241757302533523905744626606836773661026140082883368820615972739914083417816255913686820936373857254933361629603081613492930030281179652207492149, 48888685774691755361314428123012470903274435407919121739086146641066936108772671897622273617773466901370666579985825990735116909193505734002962914749300893402294987407241465624548368394059300582991374404299605248595530416820237532082552535859877438232561386581747696852665114096889765422722443550622873560905, 64940238786056387401400208343541494710106569145648776253264921960848871998112873944735053044143142466740886274718484463159497520574083206269832189589919893550520334911490391957266450195041949757369417242568602992393025242097901450113737739057611554182495438506865992404354942119595468005771945393932589768474, 40143952866342512113851528831224840428508359508863486720333430314639020044892359484055175960350878532212164045297142804890441825145732613460997839927190176844605217276182528040788352071676527553305037569493706223713078036314819975031692707790811142576347096406283580538840499698900522007082050790381461432333, 40143952866342512113851528831224840428508359508863486720333430314639020044892359484055175960350878532212164045297142804890441825145732613460997839927190176844605217276182528040788352071676527553305037569493706223713078036314819975031692707790811142576347096406283580538840499698900522007082050790381461432333, 63709385155465577684045832627013714734477675077145869296144855691101040965871249828804609100346204070983371062590273336734564969020068052618256509773408613924173909751351554561064586129837540954337160904415625404892669592986127801019807989827319368290273765648256480872195493742292667971088647173453059033806, 63709385155465577684045832627013714734477675077145869296144855691101040965871249828804609100346204070983371062590273336734564969020068052618256509773408613924173909751351554561064586129837540954337160904415625404892669592986127801019807989827319368290273765648256480872195493742292667971088647173453059033806, 395614027609996240852481164437866526092619532462793112573591941760461733078790058190352272001680670708696565031383813584099258044287660547481138381810824496633727067,
1303251812771008272858935652243561913687651063565007930291142413707811828393424201379693530423289355865533076364121921469892110296393354892615, 48977318868316177241868377840886234518379318740788414464335149639789241373564334219732049732484152649864293157598629604567238775720288389168177046142209467079549232009426147052416900999957014084019576693027561825654624690272350264451017869825303585254430358271190141844081570800201723992346171314406386674943, 20593313344992264722474643208232460904729585942331327945281307002575544045487870568637031063784433406096326172788745559326479291854636106027597680333110098010128235038952685620360851399518780967171732233524825381055879695801401425059095441692301391956163400460584139637380367489591078077440142620116997434358]
"""

爆破就行了

这个$e$是不是不应该给出来的,出题人失误了吧,按理说应该通过第一个字母C,来得到$e$

exp:

1
2
3
4
5
6
7
8
9
10
e = 11299
n =
c = [...]
flag = ''
for j in range(len(c)):
for i in range(32,128):
if pow(i,e,n) == c[j]:
flag += chr(i)
print(flag)
#CnHongKe{a8cc755d375811f55cec82153388c}

prng

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 secret import flag
import random

def base(n, l):
bb = []
while n > 0:
n, r = divmod(n, l)
bb.append(r)
return ''.join(str(d) for d in bb[::-1])

def prng(secret):
seed = base(secret, 5)
seed = [int(i) for i in list(seed)]
length = len(seed)
R = [[ random.randint(0,4) for _ in range(length)] for _ in range(length*2)]
S = []
for r in R:
s = 0
for index in range(length):
s += (r[index] * seed[index]) % 5
s %= 5
S.append(s)
return R, S

m = bytes_to_long(flag)
R, S = prng(m)

with open('output.txt', 'w') as f:
f.write(f'R = {R}\nS = {S}')

divmod(n,l)返回(n // l,n % l)

base(n,l)就是把n,写成l进制

分析代码知道

$S_1 = (R_{1,1}\times seed_1 \mod 5) + …+(R_{1,n} \times seed_n \mod 5)$

$\dots$

$S_n = (R_{n,1}\times seed_1 \mod 5) + …+(R_{n,n} \times seed_n \mod 5)$

$S_{n+1} = (R_{n+1,1}\times seed_1 \mod 5) + …+(R_{n+1,n} \times seed_n \mod 5)$

$\dots$

$S_{2n} = (R_{2n,1}\times seed_1 \mod 5) + …+(R_{2n,n} \times seed_n \mod 5)$

上面代码自己生成数据

GF(5)下解这个矩阵方程

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#sage
from Crypto.Util.number import *

R = [[] , ... , []]
S = []

r = Matrix(GF(5),R)
s = vector(GF(5),S)
seed = r.solve_right(s)
m = list(seed)
flag = ""
# flag="".join(map(str,m))

for i in m:
flag += str(i)

flag = long_to_bytes(int(flag,5))
print(flag)
# CnHongKe{l1ne4r_prng_1s_d4ngr0s~~!d9uxdj9223}

感谢这位师傅提供的数据

2023 江苏领航杯 misc密码wp_零上安全的博客-CSDN博客

prng加强版

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
from Crypto.Util.number import *
from secret import flag
import random

def base(n, l):
bb = []
while n > 0:
n, r = divmod(n, l)
bb.append(r)
return ''.join(str(d) for d in bb[::-1])

def prng(secret):

seed = base(secret, 5)
seed = [int(i) for i in list(seed)]
length = len(seed)
R = [[ random.randint(0,4) for _ in range(length)] for _ in range(length**2)]
S = []
for r in R:
s = 0
for index in range(length):
s += (r[index] + seed[index]) % 5
s %= 2
S.append(s)
return R, S

m = bytes_to_long(flag)
R, S = prng(m)

with open('output.txt', 'w') as f:
f.write(f'R = {R}\nS = {S}')

R是一个$length^2 \times length$的矩阵,记$n = length$

根据加密过程有下式
$$
S_i = \sum_{j=1}^{n}(R_{ij} + seed_j \mod 5) \mod 2
$$

1
2
3
4
5
0:(1,0,0,0,0)
1:(0,1,0,0,0)
2:(0,0,1,0,0)
3:(0,0,0,1,0)
4:(0,0,0,0,1)

这样做的目的是为了把这个先模5再模2的没有办法解的线性方程组变化到一个可以解的形式。

所以穷举$R_{i,j}$和$seed_j$的值,因为渲染问题,用$a$代表$R_{i,j}$,$b$代表$seed_j$,中间的值代表$(R_{i,j}+seed_j \mod 5) \mod 2$的值,我们可以得到下面这个表:

a\b 0 1 2 3 4
0 0 1 0 1 0
1 1 0 1 0 0
2 0 1 0 0 1
3 1 0 0 1 0
4 0 0 1 0 1

为什么可以把加法变乘法

举个例子,根据$S_i = \sum_{j=1}^{n}(R_{ij} + seed_j \mod 5) \mod 2$

假设$1 = (2 + 1 \mod 5) + (3 + 4 \mod 5) + (0 + 2 \mod 5) \mod 2$

对应上表$a = 2,b=1$,$a=3,b=4$,$a=0,b=2$的真值相加

所以我们可以把$S_i = \sum_{j=1}^{n}(R_{ij} + seed_j \mod 5) \mod 2$

转化为$S_i = \sum_{j=1}^{n}{r_{ij} \times m_j} \mod 2$,($r_{ij}$,$m_j$分别表示$R_{ij},seed_j$编码后的形式)

如何写成矩阵表达

对于上述$1 = (2 + 1 \mod 5) + (3 + 4 \mod 5) + (0 + 2 \mod 5) \mod 2$

取$a = 2$那一行的值作为编码形式$(0,1,0,0,1)$,$b = 1$取一开始讲的那个编码形式$(0,1,0,0,0)$

于是有

如何求解

因为已知$S_i$和$R_{i,j}$

随便取一个$S = 0 = (1 \times m_1) + (3 \times m_2) + (2 \times m_3) \mod 2$

即转化成

推广到一般形式即为:$S_i = \sum_{j=1}^{n}(R_{ij} + seed_j \mod 5) \mod 2$,最终转化为:$S_i = (\sum_{i=1}^{n^2}r_{ij} \times m_j) \mod 2$

我们有$n^2$组$R_{i,j}$和$S_i$,足够求解$5n$个未知量

构造这样的矩阵:

值得注意的是,在矩阵求解的过程中,有可能会出现编码范围以外的值

1
2
3
4
5
0:(1,0,0,0,0)
1:(0,1,0,0,0)
2:(0,0,1,0,0)
3:(0,0,0,1,0)
4:(0,0,0,0,1)

比如(1,1,1,1,0),说明编码不是一对一的,而是一对二的。

比如4就对应了(1,1,1,1,0)(0,0,0,0,1)

网上找了篇大佬的博客有讲解:Crypto CTF 2023 WriteUps | 廢文集中區 (maple3142.net)

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

with open('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 in range(5 * n):
a = []
B.append(S[i])
for j in range(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 in range(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}

参考文章

[CryptoCTF] CryptoCTF 2023 tough分类 团队解题writeup - 知乎 (zhihu.com)

Crypto趣题-其他 | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz)

bd

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 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)


print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")
print(f"hint1 = {hint1}")
print(f"hint2 = {hint2}")

"""
n = 73337798113265277242402875272164983073482378701520700321577706460042584510776095519204866950129951930143711572581533177043149866218358557626070702546982947219557280493881836314492046745063916644418320245218549690820002504737756133747743286301499039227014032044403571945455215839074583290324966069724343874361
e = 42681919079074901709680276679968298324860328305878264036188155781983964226653746568102282190906458519960811259171162918944726137301701132135900454469634110653076655027353831375989861927565774719655974876907429954299669710134188543166679161864800926130527741511760447090995444554722545165685959110788876766283
c = 35616516401097721876690503261383371143934066789806504179229622323608172352486702183654617788750099596415052166506074598646146147151595929618406796332682042252530491640781065608144381326123387506000855818316664510273026302748073274714692374375426255513608075674924804166600192903250052744024508330641045908599
hint1 = 740477612377832718425
hint2 = 767891335159501447918
"""

利用上高位的boneh_durfee攻击

参考一篇论文367.pdf (iacr.org)

他们实验时的脚本:Codes of the manuscript—Practical Attacks on Small Private Exponent RSA—New Records and New Insi - Pastebin.com

论文提到:

对于1024bit的模,当$m=7,t=3$的时候,至少需要27位p的高位,才能成功

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
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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
import time
time.clock = time.time

debug = True

strict = False

helpful_only = True
dimension_min = 7 # 如果晶格达到该尺寸,则停止移除
# 显示有用矢量的统计数据
def helpful_vectors(BB, modulus):
nothelpful = 0
for ii in range(BB.dimensions()[0]):
if BB[ii,ii] >= modulus:
nothelpful += 1

print (nothelpful, "/", BB.dimensions()[0], " vectors are not helpful")

# 显示带有 0 和 X 的矩阵
def matrix_overview(BB, bound):
for ii in range(BB.dimensions()[0]):
a = ('%02d ' % ii)
for jj in range(BB.dimensions()[1]):
a += '0' if BB[ii,jj] == 0 else 'X'
if BB.dimensions()[0] < 60:
a += ' '
if BB[ii, ii] >= bound:
a += '~'
#print (a)

# 尝试删除无用的向量
# 从当前 = n-1(最后一个向量)开始
def remove_unhelpful(BB, monomials, bound, current):
# 我们从当前 = n-1(最后一个向量)开始
if current == -1 or BB.dimensions()[0] <= dimension_min:
return BB

# 开始从后面检查
for ii in range(current, -1, -1):
# 如果它没有用
if BB[ii, ii] >= bound:
affected_vectors = 0
affected_vector_index = 0
# 让我们检查它是否影响其他向量
for jj in range(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 in range(affected_vector_index + 1, BB.dimensions()[0]):
# 如果它影响哪怕一个向量
# 我们放弃这个
if BB[kk, affected_vector_index] != 0:
affected_deeper = False
# 如果没有其他向量受到影响,则将其删除,并且
# 这个有用的向量不够有用
#与我们无用的相比
if affected_deeper and abs(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`
"""
def boneh_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 in range(mm + 1):
for ii in range(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 not in monomials: # 如果单项不在单项中
monomials.append(monomial)
monomials.sort()

# y-移位
for jj in range(1, tt + 1):
for kk in range(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 in range(1, tt + 1):
for kk in range(floor(mm/tt) * jj, mm + 1):
monomials.append(u^kk * y^jj)

# 构造格 B
nn = len(monomials)
BB = Matrix(ZZ, nn)
for ii in range(nn):
BB[ii, 0] = gg[ii](0, 0, 0)
for jj in range(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")
return 0,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 in range(nn - 1):
for pol2_idx in range(pol1_idx + 1, nn):

# 对于i and j, 构造两个多项式

PR.<w,z> = PolynomialRing(ZZ)
pol1 = pol2 = 0
for jj in range(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

if not found_polynomials:
print ("no independant vectors could be found. This should very rarely happen...")
return 0, 0

rr = rr(q, q)

# solutions
soly = rr.roots()

if len(soly) == 0:
print ("Your prediction (delta) is too small")
return 0, 0

soly = soly[0][0]
ss = pol1(q, soly)
solx = ss.roots()[0][0]
return solx, soly

def example():
############################################
# 随机生成数据
##########################################
#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 in range(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 in range(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 ===")
if False:
print ("x:", solx)
print ("y:", soly)

d_sol = int(pol(solx, soly) / e)
ss=ss+1

print ("=== solution found ===")
print ("p的高比特为:",l)
print ("q的高比特为:",qM)
print ("d=",d_sol)

if debug:
print("=== %s seconds ===" % (time.time() - start_time))
#break
print("ss=",ss)
#end=time.process_time
end=time.clock()
print('Running time: %s Seconds'%(end-start))
if __name__ == "__main__":
example()

题目给出了p的高70位,所以exp中把s由27改为了70

d=783087701705468761679148299766995936398557044101882919430819055852416479930185217204358163

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

n =
d =
c =

m = pow(c,d,n)
print(long_to_bytes(m))
#CnHongKe{Y0u_m4d3_n3w_rec0rd!!!1113dsd2et}

另外一种解法参考:2023 江苏领航杯 misc密码wp_零上安全的博客-CSDN博客

写在最后

星盟安全团队纳新!

欢迎师傅们加群(346014666)学习、讨论!

-------------已经到底啦!-------------