Navigation

    喵了个咪乎

    • Register
    • Login
    • Search
    • Categories
    • Recent
    • Tags
    • Popular
    • Users
    • Groups

    安恒月赛 not_rsa

    学习打卡区
    1
    1
    7
    Loading More Posts
    • Oldest to Newest
    • Newest to Oldest
    • Most Votes
    Reply
    • Reply as topic
    Log in to reply
    This topic has been deleted. Only users with topic management privileges can see it.
    • 林
      林航锌 last edited by

      只看了这道题,但是做不出来,太菜了😢
      题目:

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

      1 Reply Last reply Reply Quote 0
      • First post
        Last post