查看: 194|回复: 1

[Crypto] watevrCTF _Crypto_ECC-RSA

[复制链接]
发表于 2020-3-10 14:54:00 | 显示全部楼层 |阅读模式
题目描述如下:
ECC + RSA = Double security!
分析一下源码,发现题目使用了ECC和RSA两种加密算法,其中flag是通过RSA加密的,我们知道e和n,但无法直接分解n。同时,我们还知道ECC的曲线(y^2 = x^3 + a*x + b)和曲线参数(a、b、P)以及基点G的值,且(p,q)是椭圆曲线上的一点,即:
q^2 ≡ p^3 + a*p + b (mod P)
同余式两边同时乘上p^2,有:
n^2 ≡ p^5 + a*p^3 + b*p^2 (mod P)
设f ≡ p^5 + a*p^3 + b*p^2 - n^2(mod P),此时多项式f中只有p这一个未知数。我们可以尝试对f分解,在其因式中找到其中度为1的多项式(即p+C这种形式,其中C为任意整数),然后判断该多项式的解和n是否存在1以外的公因子,若存在,则可以认为解出p(需要注意,如果计算出来的解为负数,需要将其对P取模来模正),此时计算n/p即可得到q,从而实现模数n的分解。
将上述推导写成代码形式如下:
from binascii import *

P = 0x1ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
a = -0x3
b = 0x51953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00
n = 0x118aaa1add80bdd0a1788b375e6b04426c50bb3f9cae0b173b382e3723fc858ce7932fb499cd92f5f675d4a2b05d2c575fc685f6cf08a490d6c6a8a6741e8be4572adfcba233da791ccc0aee033677b72788d57004a776909f6d699a0164af514728431b5aed704b289719f09d591f5c1f9d2ed36a58448a9d57567bd232702e9b28f
c = 0x3862c872480bdd067c0c68cfee4527a063166620c97cca4c99baff6eb0cf5d42421b8f8d8300df5f8c7663adb5d21b47c8cb4ca5aab892006d7d44a1c5b5f5242d88c6e325064adf9b969c7dfc52a034495fe67b5424e1678ca4332d59225855b7a9cb42db2b1db95a90ab6834395397e305078c5baff78c4b7252d7966365afed9e

R.<X> = PolynomialRing(GF(P))
f = x^5 + a*x^3 + b*x^2 - n^2
factors = f.factor()

for i in factors:
    i = i[0]
    if i.degree()==1:
        tmp = Integer(mod(-i[0],P))
        if gcd(tmp,n) != 1:
            p = tmp
            q = n/tmp

phi = (p-1)*(q-1)
d = inverse_mod(e,phi)
m = pow(c,d,n)
print unhexlify(hex(Integer(m)))
执行脚本即可得到flag:
watevr{factoring_polynomials_over_finite_fields_is_too_ez}


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

0

主题

93

帖子

0

精华

中级会员

Rank: 8Rank: 8

学币
235
荣耀
0
rank
0
违规
0

    发表于 2020-3-15 09:12:36 | 显示全部楼层
    太给力了,这么多好东西!
    关闭

    论坛公告上一条 /1 下一条

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