首页 > 其他分享 >CTF-CRYPTO(2)

CTF-CRYPTO(2)

时间:2025-01-12 22:55:37浏览次数:1  
标签:CRYPTO yG xG CTF mod bsgs equiv

CTF-CRYPTO

椭圆加密

4.BSGS(小步大步法)

[HITCTF 2021 ]

task.py

#Elliptic Curve: y^2 = x^3 + 7 mod N which is secp256k1
N = 2**256-2**32-2**9-2**8-2**7-2**6-2**4-1
E = EllipticCurve(GF(N), [0, 7])
xG = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
yG = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
G = (xG,yG)
n = [secret0,secret1,secret2]
#flag = "HITCTF2021{"+''.join([hex(i) for i in n])
for i in n:
    assert i<1048575
    print(i*G)
cipher0 = (76950424233905085841024245566087362444302867365333079406072251240614685819574 , 85411751544372518735487392020328074286181156955764536032224435533596344295845)
cipher1 = (42965775717446397624794967106656352716523975639425128723916600655527177888618 , 32441185377964242317381212165164045554672930373070033784896067179784273837186)
cipher2 = (26540437977825986616280918476305280126789402372613847626897144336866973077426 , 1098483412130402123611878473773066229139054475941277138170271010492372383833)
assert n[0]*G == cipher0
assert n[1]*G == cipher1
assert n[2]*G == cipher2
#Find n and recover the flag. Good luck!

这题的有N比较小,而且有多个点,所以我们才用bsgs

设求解

\[a^x \equiv b\mod p \]

\[a^{im+j}\equiv b\ mod \ p \]

\[a^j\equiv b*a^{-im}\ mod\ p \]

\[a^j\equiv b*(a^{(-m)i}) \ mod\ p \]

只要找到一组i,j使得最后一个式子成立就行

通过枚举j,递推出a^j mod p的乘法逆元 枚举i,递推出所有等式右边,每得到一个值后,从hash表中查找该值,如果存在,取出其对应的j,x=im+j,就是要的值

具体操作详见

https://oi.men.ci/bsgs-notes/

EXP

from sage.groups.generic import bsgs

N = 2**256-2**32-2**9-2**8-2**7-2**6-2**4-1
E = EllipticCurve(GF(N), [0, 7])
xG = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
yG = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
G = E([xG,yG])

cipher0 = E([76950424233905085841024245566087362444302867365333079406072251240614685819574 , 85411751544372518735487392020328074286181156955764536032224435533596344295845])
cipher1 = E([42965775717446397624794967106656352716523975639425128723916600655527177888618 , 32441185377964242317381212165164045554672930373070033784896067179784273837186])
cipher2 = E([26540437977825986616280918476305280126789402372613847626897144336866973077426 , 1098483412130402123611878473773066229139054475941277138170271010492372383833])

m1 = bsgs(G,cipher0,(1,1000000),operation='+')
m2 = bsgs(G,cipher1,(1,1000000),operation='+')
m3 = bsgs(G,cipher2,(1,1000000),operation='+')
print(m1,m2,m3)
n = [m1,m2,m3]
flag = "NSSCTF{" + ''.join([hex(i)[2:] for i in n])+"}"
print(flag)

标签:CRYPTO,yG,xG,CTF,mod,bsgs,equiv
From: https://www.cnblogs.com/ink599/p/18667534

相关文章

  • get_started_3dsctf_2016 1
    gets造成栈溢出,返回地址填入getflag函数打开看getflag函数,它功能是打开flag文件读取并输出。如果我们的exp传入两个参数a1,a2还不够,因为程序若是不正常退出是没有回显的。(本题没有开启标准输入输出,输入输出会在缓冲区呆着,而exit执行后会将缓冲区输出,即输出flag)在functions里搜......
  • [DASCTF X 0psu3十一月挑战赛|越艰巨·越狂热]single_php复现
    [DASCTFX0psu3十一月挑战赛|越艰巨·越狂热]single_php复现进题如上传参highlight_file,拿到源码<!DOCTYPEhtml><html><head><style>img{max-width:200px;max-height:200px;}</style><title>revengetosiranai.php</title&g......
  • CTF 之 Crypto (Cryptography) 学习笔记
    CTF之Crypto(Cryptography)Chapter0.前置知识群(Group)给定一个集合\(G\neq\emptyset\)以及二元代数运算\(\circ\),若满足:封闭性(Closure):\(\forallu,v\inG\),\(u\circv\inG\);结合律(Associativity):\(\forallu,v,w\inG\),\((u\circv)\circw=u\circ(v......
  • moectf2023 web wp
    gas!gas!gas!直接跑脚本importrequestssession=requests.Session()url="http://127.0.0.1:14447"steering_control=0throttle=1foriinrange(10):datas={"driver":1,"steering_control":steering_control,"throttle":thro......
  • python charm-crypto库的使用
    在ubuntu20.04.6LTS上安装pipinstallcharm-crypto1fromcharm.toolbox.pairinggroupimportPairingGroup,ZR,G1,G2,GT,pair2#创建SS512椭圆循环群3group=PairingGroup('SS512')4#生成ZR群上元素:数字5group.random()6group.order()7group.rand......
  • [MRCTF2020]pyFlag
    [MRCTF2020]pyFlag在3张图片结尾发现有隐藏的压缩包信息提取出来组合成一个压缩包,暴力破解得到密码1234打开压缩包里的2个txt,发现提示和编码后的字符串根据.hint.txt文件的说明,得知flag经过了base加密,且为base16,base32,base64、base85,我们需要根据种base编码的特征来提取信......
  • 零基础被迫参加CTF比赛?CTF高频解题技巧与经验分享
    CTF(CaptureTheFlag)比赛中的高频解题技巧通常涵盖了以下几类技术,涉及从逆向工程、二进制漏洞利用到Web安全、密码学等多个领域。以下是一些高频解题技巧:1.逆向工程(ReverseEngineering)静态分析:通过阅读二进制文件的源代码或反编译代码(......
  • 零基础被迫参加CTF比赛?CTF高频解题技巧与经验分享
    CTF(CaptureTheFlag)比赛中的高频解题技巧通常涵盖了以下几类技术,涉及从逆向工程、二进制漏洞利用到Web安全、密码学等多个领域。以下是一些高频解题技巧:1.逆向工程(ReverseEngineering)静态分析:通过阅读二进制文件的源代码或反编译代码......
  • 第七届封神台CTF
    第七届封神台CTFWebwelcome_to_zkaqctf​​源码:const{promises:fs}=require('fs');constfastify=require('fastify');constflag=process.env.FLAG||'zkaq{do_you_believe_this_is_flag?}';constapp=fastify();app.get('/......
  • BJDCTF2020 ZJCTF,不过如此 1
    #php伪协议#利用伪协议#filegetcomtent用phpinput绕过#PHP对于函数调用的语法问题<?phperror_reporting(0);$text=$_GET["text"];$file=$_GET["file"];if(isset($text)&&(file_get_contents($text,'r')==="Ihaveadream")){......