CTF show unusualrsa4

Lazzaro大佬出的题目，想了几天，也看了hint，还是没思路，在大佬的博客里看了看wp，总算是搞明白了，tql

原wp：https://lazzzaro.github.io/2020/09/01/other-CTFshow供题-unusualrsa系列/

题目

# ********************
# @Author: Lazzaro
# ********************

from Crypto.Util.number import getPrime,bytes_to_long
from gmpy2 import invert
from secret import flag

m = bytes_to_long(flag)
p = getPrime(1024)
q = getPrime(1024)
n = p*q
print(invert(q,p))

e = 0x10001
d = invert(e,(p-1)*(q-1))
print(d)

c = pow(m,e,n)
print(c)

#113350138578125471637271827037682321496361317426731366252238155037440385105997423113671392038498349668206564266165641194668802966439465128197299073392773586475372002967691512324151673246253769186679521811837698540632534357656221715752733588763108463093085549826122278822507051740839450621887847679420115044512
#27451162557471435115589774083548548295656504741540442329428952622804866596982747294930359990602468139076296433114830591568558281638895221175730257057177963017177029796952153436494826699802526267315286199047856818119832831065330607262567182123834935483241720327760312585050990828017966534872294866865933062292893033455722786996125448961180665396831710915882697366767203858387536850040283296013681157070419459208544201363726008380145444214578735817521392863391376821427153094146080055636026442795625833039248405951946367504865008639190248509000950429593990524808051779361516918410348680313371657111798761410501793645137
#619543409290228183446186073184791934402487500047968659800765382797769750763696880547221266055431306972840980865602729031475343233357485820872268765911041297456664938715949124290204230537793877747551374176167292845717246943780371146830637073310108630812389581197831196039107931968703635129091224513813241403591357678410312272233389708366642638825455844282490676862737715585788829936919637988039113463707959069907015464745700766013573282604376277598510224455044288896809217461295080140187509519005245601483583507547733673523120385089098002298314719617693895392148294399937798485146568296114338393548124451378170302291

已知题目给出了 , , ,

hint:

ed=1+kφ
比较e与k比特位数
联立两式，尝试化简 (inv(q,p)·φ) mod p

费马小定理
对于任意 r,k1,k2，当 k2 为 k1 因子时，r mod k2=(r mod k1) mod k2

分析

1. 因为有

   所以

   此处可以爆破k，得到

   注：k与e同比特位，且爆破时应从大到小爆破

2. 由invert(p,q)可知：

   $$\begin{eqnarray} \varphi(n)&=&(p-1)(q-1) \\&=&pq-p-q+1 \\&=&n-p-q+1 \end{eqnarray}$$

   ---

   $$\begin{eqnarray} {\_p*\varphi(n)}\mod(p) &\equiv& {\_p(n-p-q+1)}\mod(p)\\ &\equiv& {(\_pn-\_pp-\_pq+\_p)}\mod(p)\\ &\equiv& {(0-0-1+\_p)}\mod(p) \\ &\equiv& {(-1+\_p)}\mod(p) \end{eqnarray}$$

   所以有

   即 能被 整除

3. 由费马小定理可知：存在任意 满足

   $$\begin{eqnarray} r^{\varphi(n)} &\equiv& (r^{p-1})^{q-1}\\ &\equiv& 1^{q-1}\mod(p)\\ &\equiv& 1\mod(p) \end{eqnarray}$$

   又因为对于任意 ，当为的因子时，有

   所以

   例举 取最小公因数即为

4. 由 可计算出 ，最后得到

脚本

from gmpy2 import *
import libnum

e = 0x10001
d = 27451162557471435115589774083548548295656504741540442329428952622804866596982747294930359990602468139076296433114830591568558281638895221175730257057177963017177029796952153436494826699802526267315286199047856818119832831065330607262567182123834935483241720327760312585050990828017966534872294866865933062292893033455722786996125448961180665396831710915882697366767203858387536850040283296013681157070419459208544201363726008380145444214578735817521392863391376821427153094146080055636026442795625833039248405951946367504865008639190248509000950429593990524808051779361516918410348680313371657111798761410501793645137
for k in range(1000000):
	if((e * d - 1) % (1000000 - k) == 0):
		# print(1000000 - k)
		break
		
# k0 = 250704,125352,83568,62676,41784,31338,27856,20892,15669,13928,10446,6964,5223,3482,1741,144,72,48,36,24,18,16,12,9,8,6,4,3,2,1
k0 = 62676
phi = (e * d - 1) // k0
# print(phi)

_p = 113350138578125471637271827037682321496361317426731366252238155037440385105997423113671392038498349668206564266165641194668802966439465128197299073392773586475372002967691512324151673246253769186679521811837698540632534357656221715752733588763108463093085549826122278822507051740839450621887847679420115044512
x = 1 + _p * phi - _p
# print(x)

y1 = pow(5, phi, x) - 1
y2 = pow(3, phi, x) - 1

p = gcd(y1, y2)
# print(p)

q = invert(_p, p)
n = p * q
c = 619543409290228183446186073184791934402487500047968659800765382797769750763696880547221266055431306972840980865602729031475343233357485820872268765911041297456664938715949124290204230537793877747551374176167292845717246943780371146830637073310108630812389581197831196039107931968703635129091224513813241403591357678410312272233389708366642638825455844282490676862737715585788829936919637988039113463707959069907015464745700766013573282604376277598510224455044288896809217461295080140187509519005245601483583507547733673523120385089098002298314719617693895392148294399937798485146568296114338393548124451378170302291
m = pow(c, d, n)

print(libnum.n2s(m))
# flag{wh47_1f_y0u_kn0w_1nv3r7_q_p~?}