首页 > 其他分享 >BaseCTF2024-week3-Crypto部分题目wp

BaseCTF2024-week3-Crypto部分题目wp

时间:2024-09-09 11:48:45浏览次数:7  
标签:phi pow BaseCTF2024 Crypto flag wp print import

先放一下官方的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()求解,就是时间有点久

factordb.com

之后给了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

相关文章

  • 不可不知的WPF几何图形(Geometry)
    在软件行业,经常会听到一句话“文不如表,表不如图”说明了图形在软件应用中的重要性。同样在WPF开发中,为了程序美观或者业务需要,经常会用到各种个样的图形。今天以一些简单的小例子,简述WPF开发中几何图形(Geometry)相关内容,仅供学习分享使用,如有不足之处,还请指正。 什么是几何图形(G......
  • crypto插件的用法
    文章目录1.概念介绍2.方法与功能2.1基本用法2.2加密算法3.示例代码4.内容总结我们在上一章回中介绍了"FlutterCacheManager组件"相关的内容,本章回中将介绍一个加密工具包.闲话休提,让我们一起TalkFlutter吧。1.概念介绍加密主要是为了保护一些重要数据,我......
  • WPF Generic eventhandler for various event
    publicMainWindow(){InitializeComponent();this.AddHandler(ListBox.SelectionChangedEvent,newSelectionChangedEventHandler(GenericHandler));this.AddHandler(Button.ClickEvent,newRoutedEventHandler(GenericHandler));}......
  • .NET 8 + WPF 企业级工作流系统
    合集-.NET开源工具(11) 1..NET开源快捷的数据库文档查询和生成工具07-312..NET结果与错误处理利器FluentResults08-013..NET+WPF桌面快速启动工具GeekDesk08-194.Gradio.NET支持.NET8简化Web应用开发08-265..NET开源实时监控系统-WatchDog08-276.实用接地......
  • WPF ListBox ListBoxItem Selected background style
    <Windowx:Class="WpfApp340.MainWindow"xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"xmlns:d="http://schemas.microsoft......
  • 【转】[C#][WPF] 旋转的播放按钮
    转自:http://www.dmskin.com运行后播放按钮就会一直旋转,而暂停按钮不动。<Windowx:Class="WPF.Views.MainWindow"xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml&quo......
  • jsp步拿拿鞋城购物系统njwp7
    jsp步拿拿鞋城购物系统njwp7本系统(程序+源码+数据库+调试部署+开发环境)带论文文档1万字以上,文末可获取,系统界面在最后面。系统程序文件列表项目功能商家,用户,商品分类,商品品牌,商品信息,特价商品,用户留言开题报告内容一、项目背景与意义随着电子商务的蓬勃发展,线上......
  • .NET 8 + WPF 企业级工作流系统
    前言推荐一款基于.NET8、WPF、Prism.DryIoc、MVVM设计模式、Blazor以及MySQL数据库构建的企业级工作流系统的WPF客户端框架-AIStudio.Wpf.AClient6.0。项目介绍框架采用了Prism框架来实现MVVM模式,不仅简化了MVVM的典型应用场景,还充分利用了依赖注入(DI)、消息传递以及容......
  • DevExpress WPF中文教程:如何解决排序、过滤遇到的常见问题?(一)
    DevExpressWPF拥有120+个控件和库,将帮助您交付满足甚至超出企业需求的高性能业务应用程序。通过DevExpressWPF能创建有着强大互动功能的XAML基础应用程序,这些应用程序专注于当代客户的需求和构建未来新一代支持触摸的解决方案。无论是Office办公软件的衍伸产品,还是以数据为中心......
  • windows C++ 并行编程-并发和UWP(三)
    控制执行线程Windows运行时使用COM线程模型。在此模型中,根据对象处理其同步的方式,对象被托管在不同的单元中。线程安全对象托管在多线程单元(MTA)中。必须通过单个线程访问的对象托管在单线程单元(STA)中。在具有UI的应用程序中,ASTA(应用程序STA)线程负责发送窗......