先放一下官方的wp(我这里只放我出的题):
https://j0zr0js7k7j.feishu.cn/wiki/XN3BwnHrZihQ3ZkhEyocb5EJnUd
没有n啊
from Crypto.Util.number import *
import gmpy2
flag=b'BaseCTF{}'
m=bytes_to_long(flag)
p=getPrime(512)
q=getPrime(512)
n=p*q
e=65537
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
c=pow(m,e,n)
x=pow(n,e,c)
print("c =",c)
print("e =",e)
print("d =",d)
print("x =",x)
'''
c = 52453423663797600504896811946820841317615798875871627840172711423749946998217916744135290476795328543876098295227017753117609268701786914053599060330837226980969490439739651088710549890669593587642238827462108900683237797139569260570711611781514337884756698142193277516649805710242748531658979160170193283558
e = 65537
d = 54297831548863701092644190086258072883163378307246681513317422545902442650340916001357605211715836911877651782099787873046987096258918495734824011752504203578982947618784736181975847356304742402103468329660346526185908618978851982007496096394151821403282347897417590596861323293706611997134962231129075032641
x = 40635864473997460751766935373772107585133301579524000836637683731949939348171187931595274511243052505604832873086269554842194695737052043633079044688826020656068356561856848814530947955429343483847291398607359454851926470168457852479044154798114087493843073091985855839008222762224952503563764527380033064437
'''
\[n=c+a\\
x=n^e\quad mod(c)\\
二项式定理:x=a^e\quad mod(c)\\
e*d_c=1\quad mod(\phi(c))\\
x^{d_c}=a^{e*d_c}=a\quad mod(c)
\]\(\phi(c)\)可以通过网站在线分解
也可以直接利用sage中euler_phi()求解,就是时间有点久
之后给了d就正常解了
from Crypto.Util.number import *
import gmpy2
c = 52453423663797600504896811946820841317615798875871627840172711423749946998217916744135290476795328543876098295227017753117609268701786914053599060330837226980969490439739651088710549890669593587642238827462108900683237797139569260570711611781514337884756698142193277516649805710242748531658979160170193283558
e = 65537
d = 54297831548863701092644190086258072883163378307246681513317422545902442650340916001357605211715836911877651782099787873046987096258918495734824011752504203578982947618784736181975847356304742402103468329660346526185908618978851982007496096394151821403282347897417590596861323293706611997134962231129075032641
x = 40635864473997460751766935373772107585133301579524000836637683731949939348171187931595274511243052505604832873086269554842194695737052043633079044688826020656068356561856848814530947955429343483847291398607359454851926470168457852479044154798114087493843073091985855839008222762224952503563764527380033064437
phic=(2-1)*(3-1)*(73-1)*(3967-1)*(6373-1)*(95592293-1)*(216465863-1)*(4744823012787277141-1)*(48245998253859255581546561942142167304434549996919484957120717763726325509833409296170471619434291990255044694414983821250538266717293535917534918221352198192885071310932646412147737114561229291373456448363184353049796801297876664512630305475226391199481032049429-1)
#phic=euler_phi(c)
dc=gmpy2.invert(e,phic)
a=pow(x,dc,c)
print(long_to_bytes(pow(c,d,a+c)))
exgcd
from Crypto.Util.number import *
flag=b'BaseCTF{}'
m=bytes_to_long(flag)
p=getPrime(1024)
q=getPrime(1024)
n=p*q
e1=3747
e2=2991
c1=pow(m,e1,n)
c2=pow(m,e2,n)
print("n =",n)
print("e1 =",e1)
print("e2 =",e2)
print("c1 =",c1)
print("c2 =",c2)
"""
n = 27855350163093443890983002241607629119744539643165776358993469078731521668677421483556132628708836721737685936980427467856642738196111748018522018598646125626995613169001111504706363742194664774823604738939411512861441742683157275818500991834651769368178320088982759626122029956515159435424882855075032400667120376075618896752694718491438251810609878021717559466498493103257912108879328270813061231904227056671621363669388496383136964549879459562004569059185078204867346250733489663015417879915436157806942021693920206071715538430633494012923651469196048546309592946901609803631751035364478773126967010589504275776307
e1 = 3747
e2 = 2991
c1 = 24426579024062518665031958216110619832653602343205488454298659533869220501923184793828421371206493659949730138867555889074137026401207985428160803910695088081370233571905915349589146504374710444468715701305061060934519410886010929009297226496448218819742287990364436349188987723637449590579092391100714056589967894609950537021838172987840638735592599678186555961654312442380755963257875487240962193060914793587712733601168204859917001269928487633954556221987632934190217367502677285906521385169669644977192556145782303526375491484736352799180747403161343130663661867413380222714012960607473395828938694285120527085083
c2 = 6932145147126610816836065944280934160173362059462927112752295077225965836502881335565881607385328990881865436690904056577675885697508058289570333933837515526915707121125766720407153139160751343352211421901876051228566093038929625042619250168565502734932197817082848506826847112949495527533238122893297049985517280574646627011986403578166952789317461581409161873814203023736604394085875778774834314777046086921852377348590998381648241629124408514875110073073851913857329679268519229436092660959841766848676678740851087184214283196544821779336090434587905158006710112461778939184327386306992082433561460542130441825293
"""
共模攻击,但$$e_1和e_2不互素$$
\[c_1=m^{e1}\mod n\\ c_2=m^{e2}\mod n\\ 通过扩展欧几里得计算:s_1*e_1+s_2*e_2=s\\ c_1^{s_1}*c_2^{s_2}=m^{s_1*e_1+s_2*e_2}=m^s \]最后得到的是\(m^{gcd(e1,e2)}\),最后开个根即可
from Crypto.Util.number import *
from gmpy2 import *
n = 27855350163093443890983002241607629119744539643165776358993469078731521668677421483556132628708836721737685936980427467856642738196111748018522018598646125626995613169001111504706363742194664774823604738939411512861441742683157275818500991834651769368178320088982759626122029956515159435424882855075032400667120376075618896752694718491438251810609878021717559466498493103257912108879328270813061231904227056671621363669388496383136964549879459562004569059185078204867346250733489663015417879915436157806942021693920206071715538430633494012923651469196048546309592946901609803631751035364478773126967010589504275776307
e1 = 3747
e2 = 2991
c1 = 24426579024062518665031958216110619832653602343205488454298659533869220501923184793828421371206493659949730138867555889074137026401207985428160803910695088081370233571905915349589146504374710444468715701305061060934519410886010929009297226496448218819742287990364436349188987723637449590579092391100714056589967894609950537021838172987840638735592599678186555961654312442380755963257875487240962193060914793587712733601168204859917001269928487633954556221987632934190217367502677285906521385169669644977192556145782303526375491484736352799180747403161343130663661867413380222714012960607473395828938694285120527085083
c2 = 6932145147126610816836065944280934160173362059462927112752295077225965836502881335565881607385328990881865436690904056577675885697508058289570333933837515526915707121125766720407153139160751343352211421901876051228566093038929625042619250168565502734932197817082848506826847112949495527533238122893297049985517280574646627011986403578166952789317461581409161873814203023736604394085875778774834314777046086921852377348590998381648241629124408514875110073073851913857329679268519229436092660959841766848676678740851087184214283196544821779336090434587905158006710112461778939184327386306992082433561460542130441825293
s,s1,s2=gcdext(e1,e2)
m=(pow(c1,s1,n)*pow(c2,s2,n))%n
print(long_to_bytes(iroot(m,s)[0]))
#b'BaseCTF{feb7e1ae-a8f7-4fc4-8d6d-945a45cc3f6d}'
wiener?
from Crypto.Util.number import *
import decimal
flag=b"BaseCTF{}"
m = bytes_to_long(flag)
p = getPrime(1024)
q = getPrime(1024)
n=p*q
e=65537
c=pow(m,e,n)
print("e =",e)
print("c =",c)
decimal.getcontext().prec = 648
P=decimal.Decimal(p)
Q=decimal.Decimal(q)
leak=decimal.Decimal((3*P*Q-1)/(3*Q*Q))
print("leak =",leak)
"""
e = 65537
c = 11032748573623426359632659657114807044712138586316710250985606809252700461490504487308849626514319062562557448839550994242999334882617031487618174168038491566640081840111747765753878087564318833273878755416584962921669911444225959335274753391800995531023212276838665202257007640354237043291129197348884914956663597240094662207929658519596987351984403258345205873566463643624175318315064440456858013874962784792564480286904620663695194689839431808082976248378509181327101557380978849545906691903896662095520288964101796965095129861467059775556110616007889846240936219381379219605528051627402300580239311202137582442057
leak = 0.829374344780877053838760251345359097311540811993463349625630085472892814959843248358036249898871908548743719153319438638517170060651237635838827482534816419091949205584951292517303330452910012749674475329235689229498752425379611083979518257734473992186831474208400813283887045691145481237726578827559198828469462343342343287720369159899636816373592067698883361360269728719786071024354151682314608072902347335691012713629816579496252896260869382806838857194293618332286500427694077400072428506897829689703872985954772105672992293334668485358785863779749153981721900135318166811250762946069962348114491411585418993494561587403918162681937152503739843
"""
直接摘抄的wiener攻击的思想,连分数定理:
\[\left|a-\frac{c}{d}\right|<\frac{1}{2*d^2}\\ 可得\frac{c}{d}就是a的一个连分数近似 \](至于定理证明我也不会,不好意思喵)
推导:
\[leak=\frac{3*P*Q-1}{3*Q*Q}\\ leak=\frac{P}{Q}-\frac{1}{3*Q^2}\\ \left|leak-\frac{P}{Q}\right|=\frac{1}{3*Q^2}<\frac{1}{2*Q^2}\\ 之后计算leak的连分数,即可得到p和q \]e = 65537
c = 11032748573623426359632659657114807044712138586316710250985606809252700461490504487308849626514319062562557448839550994242999334882617031487618174168038491566640081840111747765753878087564318833273878755416584962921669911444225959335274753391800995531023212276838665202257007640354237043291129197348884914956663597240094662207929658519596987351984403258345205873566463643624175318315064440456858013874962784792564480286904620663695194689839431808082976248378509181327101557380978849545906691903896662095520288964101796965095129861467059775556110616007889846240936219381379219605528051627402300580239311202137582442057
leak = 0.829374344780877053838760251345359097311540811993463349625630085472892814959843248358036249898871908548743719153319438638517170060651237635838827482534816419091949205584951292517303330452910012749674475329235689229498752425379611083979518257734473992186831474208400813283887045691145481237726578827559198828469462343342343287720369159899636816373592067698883361360269728719786071024354151682314608072902347335691012713629816579496252896260869382806838857194293618332286500427694077400072428506897829689703872985954772105672992293334668485358785863779749153981721900135318166811250762946069962348114491411585418993494561587403918162681937152503739843
from Crypto.Util.number import *
cf = continued_fraction(leak)
convers = cf.convergents()
for pkd in convers:
# possible k, d
pp, pq = pkd.as_integer_ratio()
pp=int(pp)
if pp.bit_length()==1024 and isPrime(pp):
flag=long_to_bytes(int(pow(c,inverse(e,pp-1),pp)))
if b'Base' in flag:
print(flag)
break
#b'BaseCTF{9431ee53-5d5c-4b0b-956f-1eafff6c9e87}'
没有n啊_pro
前言:
在之前西瓜杯的比赛中我出一次这个题,然后在前几天sigenzhe师傅在我博客低下说了另一种不用给x的解法,所以我重新生成了一下数据搬了过来,感谢sigenzhe师傅。
当时博客里的sigenzhe师傅的原话:
《给你d又怎样》 这道题可以不要 hint 也能做出来。
n为256位,那phi(n)的位数在256、255、254这个区间内。有了e和d,ed=k * phi(n) + 1 。且 k < e 可以通过爆破k的方法 得到几十个可能的 phi(n) 。而且最重要是 phi(n)的位数小于256,是可以分解的,phi(n) = (p-1) * (q-1) ,那我们通过组合phi(n)的因子,就有可以得到(p-1) 。
最终检测退出的条件是,因子组合排列相乘,只要位数是128 且 + 1后是素数即可。
from Crypto.Util.number import *
import gmpy2
flag=b'BaseCTF{}'
m=bytes_to_long(flag)
p=getPrime(128)
q=getPrime(128)
n=p*q
e=65537
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
assert d<phi
c=pow(m,e,n)
print("c =",c)
print("e =",e)
print("d =",d)
\[已知:e*d\equiv1\mod\phi(n)\\
那么e*d=1+k*\phi(n),k*\phi(n)=e*d-1\\
为了方便想我还给了一个条件d<\phi(n)\\
可以得到k<e,我们通过遍历e的范围即可得到多个k_i\phi(n)\\
\phi(n)的范围可以推测为256\\
之后可以求解\phi(n)的全分解,对全分解进行排列组合即可得到
\]当然也可以直接对e*d-1进行分解然后排列组合,但好像耗时比较长
#sage
from Crypto.Util.number import *
import itertools
c = 78919950899709764543039048006935881842075789773495004639436106636461009323420
e = 65537
d = 13002488326322253055272696035053386340217207134816593767440035447757509399233
p_bits=128
q_bits=128
def get_phi(e, d):
k_phi = e*d -1
result = []
for k in range(e,2,-1):
if k_phi % k == 0:
tmp = k_phi // k
if int(tmp).bit_length()==p_bits+q_bits:
result.append(tmp)
return result
def main():
phi_list = get_phi(e,d) #获得可能的phi_n列表
count = len(phi_list)
print(f'一共有{count}个可能的phi')
count = 0
for phi in phi_list:
count += 1
print(f'{count} 正在尝试爆破 {phi}')
factors = factor(phi) # 分解phi_n得到质因子列表
result = []
for i in factors:
num, times = int(i[0]), i[1]
result += [num] * times
if len(factors)>1:
s = set()
for r in range(1, len(result) + 1):
combination = list(itertools.combinations(result, r))
for i in combination:
s.add(i)
ans=[]
for i in s:
tmp=1
for j in i:
tmp=tmp*j
ans.append(tmp)
for num in ans:
if int(num+1).bit_length()==p_bits and is_prime(num+1):
p = num+1
q = phi // num + 1
if is_prime(q):
n = p * q
flag=long_to_bytes(int(pow(c,d,n)))
if b'BaseCTF' in flag:
print(flag)
return
if __name__ == '__main__':
main()
#b'BaseCTF{3e226a94-babb27696416}'
标签:phi,pow,BaseCTF2024,Crypto,flag,wp,print,import
From: https://www.cnblogs.com/naby/p/18404271