HITCON 2019 Lost Modular again writeup

算是基础题，有很多之前题的影子，做不出来纯属菜。

题目

• 加密脚本

from Crypto.Util.number import *

class Key:
    def __init__(self, bits):
        assert bits >= 512
        self.p = getPrime(bits)
        self.q = getPrime(bits)
        self.n = self.p * self.q
        self.e = 0x100007
        self.d = inverse(self.e, (self.p-1)*(self.q-1))
        self.dmp1 = self.d%(self.p-1)
        self.dmq1 = self.d%(self.q-1)
        self.iqmp = inverse(self.q, self.p)
        self.ipmq = inverse(self.p, self.q)

    def encrypt(self, data):
        num = bytes_to_long(data)
        result = pow(num, self.e, self.n)
        return long_to_bytes(result)

    def decrypt(self, data):
        num = bytes_to_long(data)
        v1 = pow(num, self.dmp1, self.p)
        v2 = pow(num, self.dmq1, self.q)
        result = (v2*self.p*self.ipmq+v1*self.q*self.iqmp) % self.n
        return long_to_bytes(result)

    def __str__(self):
        return "Key([e = {0}, n = {1}, x = {2}, y = {3}])".format(self.e, self.d, self.iqmp, self.ipmq)

def main():
    key = Key(1024)
    flag = open('flag').read()
    encrypt_flag = key.encrypt(flag)
    assert key.decrypt(encrypt_flag) == flag
    print key
    print encrypt_flag.encode('hex')

if __name__ == '__main__':
    main()

• 输出

Key([e = 1048583, n = 20899585599499852848600179189763086698516108548228367107221738096450499101070075492197700491683249172909869748620431162381087017866603003080844372390109407618883775889949113518883655204495367156356586733638609604914325927159037673858380872827051492954190012228501796895529660404878822550757780926433386946425164501187561418082866346427628551763297010068329425460680225523270632454412376673863754258135691783420342075219153761633410012733450586771838248239221434791288928709490210661095249658730871114233033907339401132548352479119599592161475582267434069666373923164546185334225821332964035123667137917080001159691927, x = 22886390627173202444468626406642274959028635116543626995297684671305848436910064602418012808595951325519844918478912090039470530649857775854959462500919029371215000179065185673136642143061689849338228110909931445119687113803523924040922470616407096745128917352037282612768345609735657018628096338779732460743, y = 138356012157150927033117814862941924437637775040379746970778376921933744927520585574595823734209547857047013402623714044512594300691782086053475259157899010363944831564630625623351267412232071416191142966170634950729938561841853176635423819365023039470901382901261884795304947251115006930995163847675576699331])
32074de818f2feeb788e36d7d3ee09f0000381584a72b2fba0dcc9a2ebe5fd79cf2d6fd40c4dbfea27d3489704f2c1a30b17a783baa67229d02043c5bc9bdb995ae984d80a96bd79370ea2c356f39f85a12d16983598c1fb772f9183441fea5dfeb5b26455df75de18ce70a6a9e9dbc0a4ca434ba94cf4d1e5347395cf7aafa756c8a5bd6fd166bc30245a4bded28f5baac38d024042a166369f7515e8b0c479a1965b5988b350064648738f6585c0a0d1463bd536d11a105bb926b44236593b5c6c71ef5b132cd9c211e8ad9131aa53ffde88f5b0df18e7c45bcdb6244edcaa8d386196d25297c259fca3be37f0f2015f40cb5423a918c51383390dfd5a8703

初步分析

题目给定了e,d,x,y，\(x = q^{-1} \mod p,y = p^{-1} \mod q\)(代码命名混乱)。

根据rsa的原理，\(ed == 1 \mod \phi(n)\)，故\(e*d-1\)一定是\(\phi(n)\)的倍数，即\(e*d-1==k*\phi(n)\)，\(k\)是整数，由于\(d<n\)故\(k<e\)。\(e\)的值不是很大，通过枚举可以确定所有\(k\)的可能值，代入\(e*d-1==k*\phi(n)=k*(p-1)*(q-1)\)，得到关于\(p,q\)的方程。凭借直觉，通过\(x,y\)肯定能确定另外一个方程，最后解出\(p,q\)。

另一个方程的推导

\[xq = 1 + w_1*p,yp = 1 + w_2*q\]

\[xq-1 = w_1*p,yp-1 = w_2*q\]

我们的目的是得到\(p,q\)的数量关系，势必要去掉\(w_1,w_2\)。所以两边相乘\(xypq-xq-yp+1=w_1w_2pq\)，\(xq+yp-1= (xy-w_1w_2)*pq\)。这里我们知道\(x<p,y<q\)。所以\(0<(xy-w_1w_2)*pq<2*pq\)。这样我们就知道了其实\(xy-w_1w_2=1\)。这样我们又得到了一个关于\(p,q\)的等式。通过两个方程联立，最终可以解出\(p,q\)的值。

解决脚本

依赖

• pycryptodome
• tqdm
• gmpy2

from Crypto.Util.number import long_to_bytes
from tqdm import trange
import gmpy2,binascii

d = 20899585599499852848600179189763086698516108548228367107221738096450499101070075492197700491683249172909869748620431162381087017866603003080844372390109407618883775889949113518883655204495367156356586733638609604914325927159037673858380872827051492954190012228501796895529660404878822550757780926433386946425164501187561418082866346427628551763297010068329425460680225523270632454412376673863754258135691783420342075219153761633410012733450586771838248239221434791288928709490210661095249658730871114233033907339401132548352479119599592161475582267434069666373923164546185334225821332964035123667137917080001159691927
x = 22886390627173202444468626406642274959028635116543626995297684671305848436910064602418012808595951325519844918478912090039470530649857775854959462500919029371215000179065185673136642143061689849338228110909931445119687113803523924040922470616407096745128917352037282612768345609735657018628096338779732460743
y = 138356012157150927033117814862941924437637775040379746970778376921933744927520585574595823734209547857047013402623714044512594300691782086053475259157899010363944831564630625623351267412232071416191142966170634950729938561841853176635423819365023039470901382901261884795304947251115006930995163847675576699331
e = 1048583

klist = []
for i in trange(1,e):
    if (e*d-1)%i==0:
        klist.append(i)
print(len(klist))
nlist = []
for k in klist:
    w = (e*d-1)//k
    a = y-1
    b = x-y-w
    c = 1-x+w*x
    delt = b*b-4*a*c
    if delt<0 :
        continue
    s,t = gmpy2.isqrt_rem(delt)
    if t!=0:
        continue
    if (s-b)%(2*a)!=0:
        continue
    q = (s-b)//(2*a)
    if (w+q-1)%(q-1)!=0:
        continue
    p = (w+q-1)//(q-1)
    n = p*q
    nlist.append(n)
print(nlist)
n = 22509077260984027608263845908083202879597081619164800783060781115945741547031252889863077300004310236160814653393991988068104999928735140821504649764471313283345921984799288521496479399032837319974588038186917872597078510975400908137738190304700710900604891709265153418588830065918981914371070605822998222527238465925300150253661563857557769597206945843298561291788401379974127990007737364134474570192828364417568030703631487414510799126846577679080152555651843717973023204220528124089432708534457966658829476472791371567790491496967424845002161008643478300481541860754837427906812836584810660110698219790829058527133
c = 0x32074de818f2feeb788e36d7d3ee09f0000381584a72b2fba0dcc9a2ebe5fd79cf2d6fd40c4dbfea27d3489704f2c1a30b17a783baa67229d02043c5bc9bdb995ae984d80a96bd79370ea2c356f39f85a12d16983598c1fb772f9183441fea5dfeb5b26455df75de18ce70a6a9e9dbc0a4ca434ba94cf4d1e5347395cf7aafa756c8a5bd6fd166bc30245a4bded28f5baac38d024042a166369f7515e8b0c479a1965b5988b350064648738f6585c0a0d1463bd536d11a105bb926b44236593b5c6c71ef5b132cd9c211e8ad9131aa53ffde88f5b0df18e7c45bcdb6244edcaa8d386196d25297c259fca3be37f0f2015f40cb5423a918c51383390dfd5a8703
m = gmpy2.powmod(c,d,n)
print(long_to_bytes(m))