QCTF 2018-Xman-RSA

XMan-RSA
この問題はRSA暗号化で、pythonに似たスクリプトファイルをあげましたが、文字は再置換されています.return、while、importなどのキーワードで、対応する関係を見つけて復元することで、pythonファイルの本来の姿を見ることができます.
論理的には、まずmsgをパリティで2つの文字列に分割し、その後、2つの文字列をそれぞれ異なるeパラメータでRSA暗号化する.RSA暗号化について、最も重要な式とパラメータは以下の通りです.

e = 0x10001     #    0x1001 0x101     
m = xxxxxxx      #      
c = xxxxxxx      #      
n = xxxxxxx      #    mod
d = xxxxxxx      #      
p =   
q =   
       ：
C = (M ^ e1) % n
M = (C ^ d) % n
n = p * q 
e d   (n )   ， ed ≡ 1，   libnum     d. d = invmod(e, (p-1)*(q-1))

タイトルには2つのbase 64符号化データが与えられ,復号後に対応するのがn 2とn 3であることが分かった.また,2セグメントの暗号化後のデータを与え,n 1を2回異なるeで暗号化した暗号文である.
n 3は現在知られており、n 1が要求されている.最初はn 3を分解してp,qを解き,n 1を解きたいと思っていました.後で大物は私に教えて、n 3を観察して知っていて、このような512 bit以上の数字はまったく爆破を考えないで、関数をよく観察してn 1を暗号化する2回はeパラメータが異なるだけで、関係式を書きます:

c1 = (n1 ^ e1) % n3
c2 = (n1 ^ e2) % n3
          ，  e1,e2  ， e1x + e2y = 1      。        ，             
((n1 ^ e1) ^ x )% n3 * ((n1 ^ e2) ^ y )% n3 = (n1 ^ (e1*x + e2*y)) ≡ c1 ^ x * c2 ^y

pythonのlibnumライブラリはe 1 x+e 2 yの整数解を容易に求めることができる
x=-120,y=1913に解く
n 1≡pow(c 1,−120,n 3)を顧みるが,Pythonのpow関数ではべき乗は負数ではない.そこで方法を変えて、まずc 1^-1を求め、ここでlibnumの求逆関数invmod(c 1,n 3)%n 3を用いてn 1を求める
次に、n 1=p 1*p 2,n 2=p 1*p 3が知られており、gcd(n 1,n 2)を用いてp 1を求め、p 2,p 3を算出することができる.
最後に、dを求める式を用いてd 1,d 2を求め、2つの密文をそれぞれ復号する.コードフォーマットに注意して挿入するとflagになります