安恒月赛 not_rsa

[林航锌]

只看了这道题，但是做不出来，太菜了
题目：

from Crypto.Util.number import getPrime as getprime ,long_to_bytes,bytes_to_long,inverse
from secret import flag,p,q
from sympy import isprime,nextprime
import random

m=bytes_to_long(flag)
n=p*q
g=n+1
r=random.randint(1,n)

c=(pow(g,m,n*n)*pow(r,n,n*n))%(n*n)
print "c=%d"%(c)
print "n=%d"%(n)

'''
c=29088911054711509252215615231015162998042579425917914434962376243477176757448053722602422672251758332052330100944900171067962180230120924963561223495629695702541446456981441239486190458125750543542379899722558637306740763104274377031599875275807723323394379557227060332005571272240560453811389162371812183549
n=6401013954612445818165507289870580041358569258817613282142852881965884799988941535910939664068503367303343695466899335792545332690862283029809823423608093
'''

n能通过yafu分解成两个近似的值p，q，引用的getprime和nextprime暗示这一点。

但之后不知道该如何下手了，看起来有点像rsa，但题目注释说不是rsa。

一些想法：
关于取模运算的一些性质：

(pow(g,m,nn)pow(r,n,nn))%(nn)等价于(pow(g,m)pow(r,n))%(nn)

模运算与基本四则运算有些相似，但是除法例外。其规则如下：
(a + b) % p = (a % p + b % p) % p
(a - b) % p = (a % p - b % p) % p
(a * b) % p = (a % p * b % p) % p
a ^ b % p = ((a % p)^b) % p
结合律：
((a+b) % p + c) % p = (a + (b+c) % p) % p
((ab) % p c)% p = (a * (bc) % p) % p
交换律：
(a + b) % p = (b+a) % p
(a b) % p = (b * a) % p
分配律：
(a+b) % p = ( a % p + b % p ) % p
((a +b)% p * c) % p = ((a * c) % p + (b * c) % p) % p

形如a^b(mod p)=d且p为质数的方程之解
https://www.jianshu.com/p/155a130eb4b1?utm_campaign=maleskine&utm_content=note&utm_medium=seo_notes&utm_source=recommendation
https://blog.csdn.net/acdreamers/article/details/9500215
大步小步算法BSGS
https://blog.csdn.net/lycheng1215/article/details/79047734#4-扩展大步小步算法bsgsex

随机数r比较头疼，编造了个flag试试，由于每次r不同，c值都不一样。

题目引用了inverse，其作用是求逆元。求解可能要用到逆元。