[ciscn 2022 东北赛区]math

1.题目

import gmpy2
from Crypto.Util.number import *
from flag import flag
assert flag.startswith(b"flag{")
assert flag.endswith(b"}")
message=bytes_to_long(flag)
def keygen(nbit, dbit):
    if 2*dbit < nbit:
        while True:
            a1 = getRandomNBitInteger(dbit)
            b1 = getRandomNBitInteger(nbit//2-dbit)

            n1 = a1*b1+1

            if isPrime(n1):
                break
        while True:
            a2 = getRandomNBitInteger(dbit)
            b2 = getRandomNBitInteger(nbit//2-dbit)

            n2=a2*b2+1

            n3=a1*b2+1
            if isPrime(n2) and isPrime(n3):
                break
        while True:
            a3=getRandomNBitInteger(dbit)
            if gmpy2.gcd(a3,a1*b1*a2*b2)==1:
                v1=(n1-1)*(n2-1) # phi1
                k=(a3*inverse(a3,v1)-1)//v1  # k * phi1=k * v1 = ed-1
                v2=k*b1+1
                if isPrime(v2):
                    return a3,n1*n2,n3*v2
def encrypt(msg, pubkey):
    return pow(msg, pubkey[0], pubkey[1])

nbit = 1024
dbit = 256
e, n1, n2=keygen(nbit, dbit)
print('e =', e)
print('n1 =', n1)
print('n2 =', n2)
c1 = encrypt(message, [e, n1])
c2 = encrypt(message, [e, n2])
print('enc1 =', c1)
print('enc2 =', c2)
# e = 86905291018330218127760596324522274547253465551209634052618098249596388694529
# n1 = 112187114035595515717020336420063560192608507634951355884730277020103272516595827630685773552014888608894587055283796519554267693654102295681730016199369580577243573496236556117934113361938190726830349853086562389955289707685145472794173966128519654167325961312446648312096211985486925702789773780669802574893
# n2 = 95727255683184071257205119413595957528984743590073248708202176413951084648626277198841459757379712896901385049813671642628441940941434989886894512089336243796745883128585743868974053010151180059532129088434348142499209024860189145032192068409977856355513219728891104598071910465809354419035148873624856313067
# enc1 = 71281698683006229705169274763783817580572445422844810406739630520060179171191882439102256990860101502686218994669784245358102850927955191225903171777969259480990566718683951421349181856119965365618782630111357309280954558872160237158905739584091706635219142133906953305905313538806862536551652537126291478865
# enc2 = 7333744583943012697651917897083326988621572932105018877567461023651527927346658805965099102481100945100738540533077677296823678241143375320240933128613487693799458418017975152399878829426141218077564669468040331339428477336144493624090728897185260894290517440392720900787100373142671471448913212103518035775

2.分析

注意各个数据的生成：

n1 = a1*b1 + 1

n2 = a2*b2 + 1

n3 = a1*b2 + 1

N1 = n1*n2

N2 = n3*v2

v1 = phi(n1*n2)=phi(N1)

k*v1 = ed - 1

v2 = k*b1+1

e = a3

bit_length 1024: v1, d,N1,N2

bit_length 512:n1,n2,n3

bit_length256:a1,b1,a2,b2,a3,k

由于N1，N2已经给出，我们仔细观察这两个数怎么使用，

注意到：

N1 = (a1*b1 + 1)*(a2*b2 + 1)

N2 = (a1*b2 + 1) * (k*b1 + 1)

所以 $\frac{N_1}{N_2} \approx \frac{a_2}{k}$

可以考虑使用连分数获取k，a2

接下来，注意到：

$v1 = a1*b1*a2*b2 \rightarrow v1 \equiv 0 \ mod \ a2$

$k * v1 = ed - 1 \equiv -1 \ mod \ e \rightarrow v1 \equiv - k^{-1} \ mod \ e$

然后有了模数和余数后我们就可以使用CRT求解v1了

但是这一题中观察e(=a3)、a2的生成方式，我们知道e和a3可能是不互素的，所以CRT得到的结果应该是模LCM（e，a2）下的结果，而可能不是模e*a2下的结果，所以我们需要进行一定量的破解

记我们得到的结果是v1'，则v1'与v1之间存在以下关系：
v1 = lcm(a3, a2)*t + v1'

v1 = N1 -(n1 + n2) + 1

推出：

$v1 \leqslant N1 // lcm(a2,a3) * lcm(a2,a3) + v1'$

所以我们从上式右边向下爆破即可

3.解题

1.获取k,a2

from Crypto.Util.number import *
from sympy.ntheory.modular import crt

def continuedFra(x, y):
    cF = []
    while y:
        cF += [x // y]
        x, y = y, x % y
    return cF

def Simplify(ctnf):
    numerator = 0
    denominator = 1
    for x in ctnf[::-1]:
        numerator, denominator = denominator, x * denominator + numerator
    return (numerator, denominator)

def getit(c):
    cf = []
    for i in range(1, len(c)):
        cf.append(Simplify(c[:i]))
    return cf

N1 = 112187114035595515717020336420063560192608507634951355884730277020103272516595827630685773552014888608894587055283796519554267693654102295681730016199369580577243573496236556117934113361938190726830349853086562389955289707685145472794173966128519654167325961312446648312096211985486925702789773780669802574893
N2 = 95727255683184071257205119413595957528984743590073248708202176413951084648626277198841459757379712896901385049813671642628441940941434989886894512089336243796745883128585743868974053010151180059532129088434348142499209024860189145032192068409977856355513219728891104598071910465809354419035148873624856313067

cf = continuedFra(N1, N2)
#N1 / N2 ~ a2 / k

#k,a在cf中，需要进行特定判断（比如bit_length）可以得到

2.对可能的k,a2组合进行爆破（代码需承接上面）

for (k,a2) in getit(cf):
    if(len(bin(a2)[2:]) == 256):
        modlist = [e,a2]
        clist = [-inverse(k,e),0]
        phi_ = crt(modlist,clist)[0]
        mod = e*a2 // GCD(e,a2)

        right = phi_ + N1 // mod * mod
        for i in range(12):#从右往左爆破一定数量
            phi = right - i*mod
            try:
                d = inverse(e,phi)
                m = pow(enc1,d,N1)
                flag = long_to_bytes(m).decode()
                #decode()过滤多数字符
                print(flag)
            except:
                pass
#flag{b5073f3d774c460ae2b714010cc69435}