安恒月赛 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,其作用是求逆元。求解可能要用到逆元。