安恒月赛 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。

    一些想法:
    关于取模运算的一些性质:
    bcbeaba9-34ba-4bd6-8c35-89e3f32fc7e8-image.png
    (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,其作用是求逆元。求解可能要用到逆元。


Log in to reply