攻防世界Crypto-二元一次方程组

分析：

import libnum
from Crypto.Util import number
from secret import flag


size = 256
e = 65537
p = number.getPrime(size)
q = number.getPrime(size)
avg = (p+q)/2
n = p*q

m = libnum.s2n(flag)
c = pow(m, e, n)

print('n = %d' % n)
print('avg = %d' % avg)
print('c = %d' % c)

看上述代码感觉老朋友了，详情可以看上一篇的baigeiRSA

size = 256
e = 65537

size=256定义了生成的素数p和q的比特长度

e=65537是RSA公钥指数，是一个固定的值

p = number.getPrime(size)
q = number.getPrime(size)
avg = (p+q)/2
n = p*q

生成 RSA密钥

其中设计两个公式：

$$avg = \frac{p+q} {2}$$

$$n=p*q$$

m = libnum.s2n(flag)
c = pow(m, e, n)

libnum.s2n(flag)：将flag字符串转换为一个大整数m（s2n表示“string to number”）。

c = pow(m, e, n)：计算密文c，即m^e mod n（RSA加密的核心操作）。

之后两个print即输出结果

我们回到上面的两个公式，再结合题目名称，将第一个公式的分母移至左边，加上公式2可以得到

$$p + q = 2avg$$

$$p * q = n$$

于是这题可以使用韦达定理来解体

Exploit：

import libnum

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


n = 5700102857084805454304483466349768960970728516788155745115335016563400814300152521175777999545445613444815936222559357974566843756936687078467221979584601
avg = 75635892913589759545076958131039534718834447688923830032758709253942408722875
c = 888629627089650993173073530112503758717074884215641346688043288414489462472394318700014742820213053802180975816089493243275025049174955385229062207064503
e = 65537
phi_n = n - 2 * avg + 1  # phi(n) = (p-1)(q-1) = pq-(p+q)+1
d = modinv(e, phi_n)  # de = 1 mod phi_n, d = e^-1 mod phi_n
m = pow(c, d, n)
print(libnum.n2s(m))