watevrCTF _Crypto_ECC-RSA

roger

题目描述如下：

ECC + RSA = Double security!

Files:ecc-rsa.py, ecc-rsa.txt

分析一下源码，发现题目使用了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}

monkeyman

太给力了，这么多好东西！