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+1if isPrime(n1):breakwhile True:a2 = getRandomNBitInteger(dbit)b2 = getRandomNBitInteger(nbit//2-dbit)n2=a2*b2+1n3=a1*b2+1if isPrime(n2) and isPrime(n3):breakwhile True:a3=getRandomNBitInteger(dbit)if gmpy2.gcd(a3,a1*b1*a2*b2)==1:v1=(n1-1)*(n2-1) # phi1k=(a3*inverse(a3,v1)-1)//v1  # k * phi1=k * v1 = ed-1v2=k*b1+1if 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)

所以

可以考慮使用連分數獲取k，a2

接下來，注意到：

然后有了模數和余數后我們就可以使用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

推出：

所以我們從上式右邊向下爆破即可

3.解題

1.獲取k,a2

from Crypto.Util.number import *
from sympy.ntheory.modular import crtdef continuedFra(x, y):cF = []while y:cF += [x // y]x, y = y, x % yreturn cFdef Simplify(ctnf):numerator = 0denominator = 1for x in ctnf[::-1]:numerator, denominator = denominator, x * denominator + numeratorreturn (numerator, denominator)def getit(c):cf = []for i in range(1, len(c)):cf.append(Simplify(c[:i]))return cfN1 = 112187114035595515717020336420063560192608507634951355884730277020103272516595827630685773552014888608894587055283796519554267693654102295681730016199369580577243573496236556117934113361938190726830349853086562389955289707685145472794173966128519654167325961312446648312096211985486925702789773780669802574893
N2 = 95727255683184071257205119413595957528984743590073248708202176413951084648626277198841459757379712896901385049813671642628441940941434989886894512089336243796745883128585743868974053010151180059532129088434348142499209024860189145032192068409977856355513219728891104598071910465809354419035148873624856313067cf = 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 * modfor i in range(12):#從右往左爆破一定數量phi = right - i*modtry:d = inverse(e,phi)m = pow(enc1,d,N1)flag = long_to_bytes(m).decode()#decode()過濾多數字符print(flag)except:pass
#flag{b5073f3d774c460ae2b714010cc69435}

4.參考

題解1