学逆向论坛

找回密码
立即注册

只需一步,快速开始

发新帖

2万

积分

41

好友

1157

主题
发表于 2020-2-26 17:22:47 | 查看: 2814| 回复: 0

相关题目:

♦ 2019rearrange

分析一下源码,发现我们的任务是已知n, e1, noise1, c1, e2, noise2, c2参数的值,求m的值。其中:
c1 ≡ (m+noise1)^e1 (mod n)
c2 ≡ (m+noise2)^e2 (mod n)
我们考虑采用多项式的思想来解题,将上述两个方程看成多项式的形式,有:
f1(x) = (x+noise1)^e1 - c1
f2(x) = (x+noise2)^e2 - c2
显然,当x=m时,有:
f1(x) = f2(x) = 0
即x = m是多项式f1和f2的一个公共解,也即f3 = gcd(f1,f2)的一个公共解,因此我们只需要计算gcd(f1,f2),即可得到关于m在模n意义下的多项式方程,从而求出m。
将上述推导写成SageMath代码形式如下:
from binascii import *

n = 99432613480939068351562426450736079548256649399824074125897023718511347184177748762719404609118999419018534660223144728190056735099787907299980625300234355248546050583144387977927309463501291854876892509630938617460690481497010165530214494306444999151252999850250583288798888278770654238342967653191171473013
e1, noise1, c1 = (9102, 42926763857648808452080305910241720054908809667539630194138718908195450776152522239791644645043372458139920503040529361726409749150633609223017012694569617522037971161448894459262110250322393703607247036022683527543284339763718964451482238661494995313111724858075982045508601405376724544741352142401794693054, 48276023282567629527195243870327301962656940680898728928903255577939008086657887592958073923577657060463242759606506812938152312008130198252498457257386413883443843887507528097024367788094619479032221547513746486475136282357337951126122694205225292004957793882304453164618423156810792171305978347365910972343)
e2, noise2, c2 = (2109, 51208643076502294588477225830948052764402322839126847164816681682357946991156728371602766970288519802146987999203830056494899211501025949997165558057140744445002699137286162872658309250096136525032077525028373299701055357023079519776378532002052890676446838318133048612893135724217301724754396467377231356425, 30644829500627448217295366947497931474953886995151259599263428251525601964766004111974074015504963773615137800165460045351514062357500899618814273135292073698096477339942069685331462828432407501524816375109607227118357281435280158409804228556720158131377342049528810546024786899763038442784789928604641662412)

def Pgcd(a, b):
    while b != 0:
        a, b = b, a%b
    return a

P.<x> = PolynomialRing(Zmod(n))
f1 = (x+noise1)^e1 - c1
f2 = (x+noise2)^e2 - c2
f3 = Pgcd(f1,f2)
a, b = f3.coefficients()[::-1]
x = inverse_mod(ZZ(a),n)*(-b)
print unhexlify(hex(int(x))[2:-1])
执行脚本即可得到flag:
TetCTF{1t_1s_4ll_4b0ut_GCD_0v3r_p0lyn0m14ls}


温馨提示:
1.如果您喜欢这篇帖子,请给作者点赞评分,点赞会增加帖子的热度,评分会给作者加学币。(评分不会扣掉您的积分,系统每天都会重置您的评分额度)。
2.回复帖子不仅是对作者的认可,还可以获得学币奖励,请尊重他人的劳动成果,拒绝做伸手党!
3.发广告、灌水回复等违规行为一经发现直接禁言,如果本帖内容涉嫌违规,请点击论坛底部的举报反馈按钮,也可以在【投诉建议】板块发帖举报。
论坛交流群:672619046

小黑屋|手机版|站务邮箱|学逆向论坛 ( 粤ICP备2021023307号 )|网站地图

GMT+8, 2024-3-29 08:22 , Processed in 0.118003 second(s), 35 queries .

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

快速回复 返回顶部 返回列表