Crypto
圣石匕首
sage直接运行脚本就有了
import gmpy2
beta=0.37
delta=0.01
n=round((1-2*beta-2*delta)/((1-beta)^2-2*delta-beta),6)
e= 3668637434348843171145584606519031375027610199908169273169275927238735031431533260375377791001464799116453803408104076615710166171199990283470548282669948353598733020244755959461974603778630346457439345913209321194112256348302765254052193562603687450740346132207444615610078198488883539133291840346099727880587092122957231085658576850601488737629051252914095889313671875244094452330062619943781809984690384476868543570724769198985172300665613239047649089399919032152539462701309393130614829962670866062380816370571057536421400102100259975636785825540933280194583888638501981649650640939392658268133881679239293596283
N= 9748523098652101859947730585916490335896800943242955095820326993765071194474558998322598145898741779502734772138283011560029368500998354183150180904846368209977332058847768859238711047784703104535311583123388923571789764758869419482184613566672922481672444028753365755071127320541645016370072493604532087980626825687519083734367691341907014061379844209864141989961751681235215504772582878202048494707090104738899927036896915997556102574747166491969027546256022019959716418675672979328622656831990050058120299353807110233202113906317969377201045402271911946244076903611612303290556012512559696538977841061277173754331
c= 5374936627659221745209010619827617207565185520404653329184605916859755641352457088986635357806048863755173540232471505333583684733535121482637476692432365062808450583470788320547816186936317927449796090525477205337038591439577855884910604383190932340306435201976465543731935147881754136301375206828970248293731391543905441514528959500307972606931927112031018356411970001312995489429650903529877904694901310020882390008248466887950986326522740278880600110217817950511478637493101027659292006016454642135508207492151610829525082829566392116546434101694921106423469015683277992978077101831969525458693031031468092418427
n=int(n+1)
#print(n)
m=int(n*(1-beta))
X=int(pow(N,delta))
Y=int(pow(N,delta+beta))
Z.<x,y>=ZZ[]
L=Matrix(ZZ,n,n)
f=e*x-y
for i in range(n):
g=list(N^max(0,m-i)*x^(n-1-i)*f^i)
for j in range(len(g)):
L[i,j]=g[j][0]*X^(n-1-j)*Y^j
L=L.LLL()[0]
coeff=[]
for i in range(n):
coeff.append((L[i]//(X^(n-1-i)*Y^i),'x'+'**'+str(n-1-i)+'*y'+'**'+str(i)))
s=''
for i in range(len(coeff)):
s+=str(coeff[i][0])+'*'+coeff[i][1]+'+'
f=eval(s[:-1])
factored_f = f.factor()
first_polynomial = factored_f[0][0]
first_coefficient = first_polynomial.coefficients()[0]
k = first_coefficient + 1
dp = first_polynomial.coefficients()[1]
p=(e*dp-1)//k+1
q=N//p
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,N)
print(bytes.fromhex(hex(m)[2:]))
#b'flag{small_dp_is_not_secure_adhfaiuhaph}'
欧拉欧拉！！
from Crypto.Util.number import *
flag = b'flag{*********}'
m = bytes_to_long(flag)
def get_prime(bits):
while True:
p = getPrime(bits)
x = (1 << bits) - 1 ^ p
for i in range(-10, 11):
if isPrime(x + i):
return p, x + i, i
p, q, i = get_prime(512)
n = p * q
e = 65537
c = pow(m, e, n)
print("c =", c)
print("n =", n)
print("i =", i)
注意一下异或的优先级是最低的，所以x=[(1 << bits) - 1] ^ p，而[(1 << bits) - 1]的结果为全一，这时候对它进行异或就相当于减法。
所以我们直接有两个方程求解两个未知数，z3处理就好了
from z3 import *
from Crypto.Util.number import *
c = 14859652090105683079145454585893160422247900801288656111826569181159038438427898859238993694117308678150258749913747829849091269373672489350727536945889312021893859587868138786640133976196803958879602927438349289325983895357127086714561807181967380062187404628829595784290171905916316214021661729616120643997
n = 18104347461003907895610914021247683508445228187648940019610703551961828343286923443588324205257353157349226965840638901792059481287140055747874675375786201782262247550663098932351593199099796736521757473187142907551498526346132033381442243277945568526912391580431142769526917165011590824127172120180838162091
i = -3
e=65537
s=Solver()
p=Int('p')
q=Int('q')
s.add(p*q==n)
s.add(q==((1<<512)-1)-p+i)
assert str(s.check()) == 'sat'
s=s.model()
p=s[p].as_long()
q=s[q].as_long()
print(long_to_bytes(pow(c,inverse(e,(p-1)*(q-1)),n)))
#b'flag{y0u_really_kn0w_the_phi}'
*俱以我之名
from Crypto.Util.number import *
from gmpy2 import *
import random
def pad(msg, nbits):
pad_length = nbits - len(msg) * 8 - 8
assert pad_length >= 0
pad = random.getrandbits(pad_length).to_bytes((pad_length + 7) // 8, "big")
padded_msg = pad[:len(pad)//2] + b"\x00" + msg + pad[len(pad)//2:]
return padded_msg
def All_in_my_name(p, q):
#开启三技能<俱以我之名>后，维娜立即在周围八格可部署地面召唤“黄金盟誓(Golden_Oath)”;对RSA造成真实伤害。
Golden_Oath = (p-114)*(p-514)*(p+114)*(p+514)*(q-1919)*(q-810)*(q+1919)*(q+810)
x = bytes_to_long(pad(gift, random.randint(bytes_to_long(gift).bit_length(), 512)))
y = inverse(x, Golden_Oath)
return y
flag = b'flag{?????}'
gift = b'?????'
assert gift[:3] == b'end'
p = getPrime(512)
q = getPrime(512)
n = p*q
e = 65537
c = pow(bytes_to_long(flag), e,n)
print(f'n = {n}')
print(f'c = {c}')
print(f'All_in_my_name = {All_in_my_name(p, q)}')
题目、代码里都有明显的提示就是维纳攻击。
根据Golden_Oath的生成，可以知道它的数量级是\(n^4\)，这里我记为G
\[我们有x*y=1\mod G=x*y=1+k*G，跟rsa中生成d的公式很像\\\ 我们发现y也就是All\_in\_my\_name的值很大4094bits，根据rsa中我们利用维纳攻击，可以有\\ 记N=n^4,x*y≈1+k*(n^4)=1+k*N\\ \frac{y}{N}≈\frac{k}{x}\\ 我们可以通过题目中gift含有end这三个字符，遍历连分数进行判断。 \]我到求出Golden_Oath后就卡住了，我想到用方程求解，但我用sage的solve和z3的solve都没求出来。
这下又学到一个求解方程的了，利用sympy库，这下记住了。
from Crypto.Util.number import *
from sympy import symbols, Eq, solve
n = 141425071303405369267688583480971314815032581405819618511016190023245950842423565456025578726768996255928405749476366742320062773129810617755239412667111588691998380868379955660483185372558973059599254495581547016729479937763213364591413126146102483671385285672028642742654014426993054793378204517214486744679
c = 104575090683421063990494118954150936075812576661759942057772865980855195301985579098801745928083817885393369435101522784385677092942324668770336932487623099755265641877712097977929937088259347596039326198580193524065645826424819334664869152049049342316256537440449958526473368110002271943046726966122355888321
All_in_my_name = 217574365691698773158073738993996550494156171844278669077189161825491226238745356969468902038533922854535578070710976002278064001201980326028443347187697136216041235312192490502479015081704814370278142850634739391445817028960623318683701439854891399013393469200033510113406165952272497324443526299141544564964545937461632903355647411273477731555390580525472533399606416576667193890128726061970653201509841276177937053500663438053151477018183074107182442711656306515049473061426018576304621373895497210927151796054531814746265988174146635716820986208719319296233956243559891444122410388128465897348458862921336261068868678669349968117097659195490792407141240846445006330031546721426459458395606505793093432806236790060342049066284307119546018491926250151057087562126580602631912562103705681810139118673506298916800665912859765635644796622382867334481599049728329203920912683317422430015635091565073203588723830512169316991557606976424732212785533550238950903858852917097354055547392337744369560947616517041907362337902584102983344969307971888314998036201926257375424706901999793914432814775462333942995267009264203787170147555384279151485485660683109778282239772043598128219664150933315760352868905799949049880756509591090387073778041
# print(All_in_my_name.bit_length()) # 4094
cf = continued_fraction(All_in_my_name / (n^4))
convers = cf.convergents()
for con in convers:
# possible k, g
pk, pg = con.as_integer_ratio()
if pk == 0:
continue
gift=long_to_bytes(pg)
if b'end' in gift:
Golden_Oath=(pg*All_in_my_name-1)//pk
p, q = symbols('p q')
equation1 = Eq(p * q, n)
equation2 = Eq((p-114)*(p-514)*(p+114)*(p+514)*(q-1919)*(q-810)*(q+1919)*(q+810), Golden_Oath)
solutions = solve((equation1, equation2), (p, q))
p,q=solutions[0]
p,q=int(abs(p)),int(abs(q))
print(long_to_bytes(int(pow(c,inverse_mod(65537,(p-1)*(q-1)),n))))
break
#b'flag{rE@L_d@m@9e_15_7h3_mo5t_au7hEn7ic_dam49E}'