第四届“长城杯”网络安全大赛暨京津冀网络安全技能竞赛crypto（初决赛）

Random RSA（初赛）

题目

import gmpy2
import random
from secret import flag
from Crypto.Util.number import *

class LCG:
    def __init__(self,p,a,b):
        self.p=p
        self.a=a
        self.b=b
        self.x=random.randint(0,p-1)
        print(self.p,self.a,self.b)

    def next(self):
        self.x=(self.a*self.x+self.b)%self.p
        return self.x

def getPrimes(bits,k):
    p=getPrime(bits)
    a=random.randint(0,p-1)
    b=random.randint(0,p-1)
    l=LCG(p,a,b)
    return [gmpy2.next_prime(l.next()) for _ in range(k)]

p,q=getPrimes(1024,2)
n=p*q
e=65537
m=bytes_to_long(flag)
c=pow(m,e,n)
print(n,c)
'''
170302223332374952785269454020752010235000449292324018706323228421794605831609342383813680059406887437726391567716617403068082252456126724116360291722050578106527815908837796377811535800753042840119867579793401648981916062128752925574017615120362457848369672169913701701169754804744410516724429370808383640129 95647398016998994323232737206171888899957187357027939982909965407086383339418183844601496450055752805846840966207033179756334909869395071918100649183599056695688702272113280126999439574017728476367307673524762493771576155949866442317616306832252931038932232342396406623324967479959770751756551238647385191314 122891504335833588148026640678812283515533067572514249355105863367413556242876686249628488512479399795117688641973272470884323873621143234628351006002398994272892177228185516130875243250912554684234982558913267007466946601210297176541861279902930860851219732696973412096603548467720104727887907369470758901838
5593134172275186875590245131682192688778392004699750710462210806902340747682378400226605648011816039948262008066066650657006955703136928662067931212033472838067050429624395919771757949640517085036958623280188133965150285410609475158882527926240531113060812228408346482328419754802280082212250908375099979058307437751229421708615341486221424596128137575042934928922615832987202762651904056934292682021963290271144473446994958975487980146329697970484311863524622696562094720833240915154181032649358743041246023013296745195478603299127094103448698060367648192905729866897074234681844252549934531893172709301411995941527 2185680728108057860427602387168654320024588536620246138642042133525937248576850574716324994222027251548743663286125769988360677327713281974075574656905916643746842819251899233266706138267250441832133068661277187507427787343897863339824140927640373352305007520681800240743854093190786046280731148485148774188448658663250731076739737801267702682463265663725900621375689684459894544169879873344003810307496162858318574830487480360419897453892053456993436452783099460908947258094434884954726862549670168954554640433833484822078996925040310316609425805351183165668893199137911145057639657709936762866208635582348932189646
'''

题解

def Legendre(n, p):
      return gmpy2.powmod(n, (p - 1) // 2, p)

  def Tonelli_Shanks(n, p):
      assert Legendre(n, p) == 1
      if p % 4 == 3:
          return gmpy2.powmod(n, (p + 1) // 4, p)
      q = p - 1
      s = 0
      while q % 2 == 0:
          q = q // 2
          s += 1
      for z in range(2, p):
          if Legendre(z, p) == p - 1:
              c = gmpy2.powmod(z, q, p)
              break
      r = gmpy2.powmod(n, (q + 1) // 2, p)
      t = gmpy2.powmod(n, q, p)
      m = s
      if t % p == 1:
          return r
      else:
          i = 0
          while t % p != 1:
              temp = gmpy2.powmod(t, 2 ** (i + 1), p)
              i += 1
              if temp % p == 1:
                  b = gmpy2.powmod(c, 2 ** (m - i - 1), p)
                  r = r * b % p
                  c = b * b % p
                  t = t * c % p
                  m = i
                  i = 0
          return r

wp

from Crypto .Util.number import *
from sympy.ntheory.residue_ntheory import nthroot_mod
from tqdm import tqdm

p =170302223332374952785269454020752010235000449292324018706323228421794605831609342383813680059406887437726391567716617403068082252456126724116360291722050578106527815908837796377811535800753042840119867579793401648981916062128752925574017615120362457848369672169913701701169754804744410516724429370808383640129
a =95647398016998994323232737206171888899957187357027939982909965407086383339418183844601496450055752805846840966207033179756334909869395071918100649183599056695688702272113280126999439574017728476367307673524762493771576155949866442317616306832252931038932232342396406623324967479959770751756551238647385191314
b =122891504335833588148026640678812283515533067572514249355105863367413556242876686249628488512479399795117688641973272470884323873621143234628351006002398994272892177228185516130875243250912554684234982558913267007466946601210297176541861279902930860851219732696973412096603548467720104727887907369470758901838
n =5593134172275186875590245131682192688778392004699750710462210806902340747682378400226605648011816039948262008066066650657006955703136928662067931212033472838067050429624395919771757949640517085036958623280188133965150285410609475158882527926240531113060812228408346482328419754802280082212250908375099979058307437751229421708615341486221424596128137575042934928922615832987202762651904056934292682021963290271144473446994958975487980146329697970484311863524622696562094720833240915154181032649358743041246023013296745195478603299127094103448698060367648192905729866897074234681844252549934531893172709301411995941527
c =2185680728108057860427602387168654320024588536620246138642042133525937248576850574716324994222027251548743663286125769988360677327713281974075574656905916643746842819251899233266706138267250441832133068661277187507427787343897863339824140927640373352305007520681800240743854093190786046280731148485148774188448658663250731076739737801267702682463265663725900621375689684459894544169879873344003810307496162858318574830487480360419897453892053456993436452783099460908947258094434884954726862549670168954554640433833484822078996925040310316609425805351183165668893199137911145057639657709936762866208635582348932189646
e = 65537

for k1 in tqdm(range(400,1000)):
    for k2 in range(1000):
         A = a
         B = b + k2 + k1 * a
         C = k1 * (b + k2) - n
         # Ax^2 + Bx + C - n = 0
         # 求根公式
         # n = a * p ^ 2 + (b + y + a * x) * p + (b + y) * x
         delta = nthroot_mod(B**2 - 4 * A * C,2,p)
         if delta is not None:
             p1 = (-B + delta) * inverse(2 * A, p) % p + k1
             p2 = (-B - delta) * inverse(2 * A, p) % p + k1
             if n % p1 == 0:
                 p = p1
                 q = n // p
                 d = inverse(e, (p - 1) * (q - 1))
                 print(long_to_bytes(pow(c, d, n)))
                 break
             elif n % p2 == 0:
                 p = p2
                 q = n // p
                 d = inverse(e, (p - 1) * (q - 1))
                 print(long_to_bytes(pow(c, d, n)))
#b'flag{j1st_e_s1mp1e_b3ute}'

near(决赛）

题目

# sage -pip install pycryptodome

from Crypto.Util.number import *
from sympy import nextprime
import os
from gmpy2 import *
from tqdm import tqdm

'''
Too next maybe.
'''

class MyRSA():
    def __init__(self,flag:bytes,nbits:int):
        self.n, self.phi = self.GetMyModulus()
        self.e = 0x10001
        self.d = inverse(self.e,self.phi)
        self.flag = self.pad_pkcs77(flag,nbits)
    def GetMyModulus(self):
        u = getPrime(1024)
        u = (u >> 414) << 414
        p = nextprime(u)
        q = getPrime(326)
        n = p^5*q
        phi = p^4*(p-1)*(q-1)
        return n, phi

    def pad(self,flag,nbits:int):
        flag = flag + os.urandom(1)*(nbits//8 - len(flag))
        return flag

    def pad_pkcs77(self,flag:bytes,nbits:int)->bytes:
        pad_len = (nbits - len(flag)) % 256
        return flag + bytes([pad_len]*pad_len)
    def Encrypt(self,flag:bytes)->int:
        return pow(bytes_to_long(flag),self.e,self.n)

    def Decrypt(self,c:int)->bytes:
        return long_to_bytes(pow(c,self.d,self.n))

    def GetPublicKey(self)->tuple:
        return self.e,self.n

R = MyRSA(flag,4096)
e,n = R.GetPublicKey()
c = R.Encrypt(R.flag)
assert flag in R.Decrypt(c)
print(f'n = {n}')
print(f'c = {c}')
print(f'e = {e}')
n = 10823775490240073819631917849117225946287891171185101059838012738590942083286491895086451201330121282239112048818281379201392391711081928618707509066233928638187019201160301050490769069075313289908655264579328149828347872699697195230421390529843974340674990548004216615592682491515978442178349653549929465663244023757359796216867165844075976331191951027290725012210177449053555588254681079976280745286908897416681478813013297839608241067674026010720343633012556240553683175172988624633735387588606867666858001973089190528295159219227069810517454677330841359125440162677002725561779009788936368150290859696939093099879034996630579194814736517706689658051035296730348668338031728823161338125653461172596730500445378167749498084676295147743704190979584713779480154941790026465774118720519452568935866964502632734126766023547271771741522485702708564882312127253470312413231358374856453986812653197218096126488261909815753848184984064628112603870471377689973632577669755803660286519111642490140982595789903748438781184726565551753915521681764875126384100543905139578572437448873221310081171658381184510994313626085298420060720405712211118973379978497950555404038223284628782496353636937575849667836726918752652643522916609808294676912772669709626282702678281989896980713944961023191040866155298213017019008276602607515680628655918406129027549335549388661763175355900965439242125850380340787177957488885171013738475994880288387184114946910361655893886743701515443028478684376198033356669188403171941244027967567591761268196312412901508832292242743552450482860690493244338059935380601338109164461877746510598646182450038161334450878692284043867773
c = 10660090497301432537437820885848286020311835935260034549173484275959379310864520958356152878610641549326516182239849660339867147213565561569490658510864241912091951711562645132218482839920377179333386420114391233630515012393090359381717875467071280927583120692784917275074532993409388122061004854178182661632604182150765151482558156183912422898613209559942234127025063687928879910292952039316531554812705081695248540209866005563219806997627684236587554109286831877006896470109805219447282525518519161097673276492456094713735029038771812376330352652393029164468202357817665724369560583349301558861453705718562711798522554316893417360531922795446452749685308492123451575279293644339041629468390133378328145993285368218775498976282596017084494092950586275565868969964447619034372770452127643594002885530340353730337577609060573094563836165559288998090805166088888016631981190567474132421889397451224492478175286707362679459528061705122579238644392225558752144211463152201143723558678398331677420261413849490732610210418705205396485108198008618730081560787598535809656356334449123152662358838247968331030455386114998823400263422044625507507829935684490654252473089135735147481428318393546785418776661158864450118169388804900558540117140348002680864998171847298229035444536926030071973643938958868695657994095200366957439503117930474161132984898344356321926977383591037057394861749532205998932840557833372993944408083463060446903121200107227041538939713625198024076302549803852074630498649236538622458710733295489005936281570737839438843387492079285997225293361642946364581369251919661240027265549956890265107036578709824437885345581015267152770
e = 65537

题解

u = getPrime(1024)
u = (u >> 414) << 414
p = nextprime(u)
q = getPrime(326)
n = p^5*q

wp

n = 10823775490240073819631917849117225946287891171185101059838012738590942083286491895086451201330121282239112048818281379201392391711081928618707509066233928638187019201160301050490769069075313289908655264579328149828347872699697195230421390529843974340674990548004216615592682491515978442178349653549929465663244023757359796216867165844075976331191951027290725012210177449053555588254681079976280745286908897416681478813013297839608241067674026010720343633012556240553683175172988624633735387588606867666858001973089190528295159219227069810517454677330841359125440162677002725561779009788936368150290859696939093099879034996630579194814736517706689658051035296730348668338031728823161338125653461172596730500445378167749498084676295147743704190979584713779480154941790026465774118720519452568935866964502632734126766023547271771741522485702708564882312127253470312413231358374856453986812653197218096126488261909815753848184984064628112603870471377689973632577669755803660286519111642490140982595789903748438781184726565551753915521681764875126384100543905139578572437448873221310081171658381184510994313626085298420060720405712211118973379978497950555404038223284628782496353636937575849667836726918752652643522916609808294676912772669709626282702678281989896980713944961023191040866155298213017019008276602607515680628655918406129027549335549388661763175355900965439242125850380340787177957488885171013738475994880288387184114946910361655893886743701515443028478684376198033356669188403171941244027967567591761268196312412901508832292242743552450482860690493244338059935380601338109164461877746510598646182450038161334450878692284043867773
c = 10660090497301432537437820885848286020311835935260034549173484275959379310864520958356152878610641549326516182239849660339867147213565561569490658510864241912091951711562645132218482839920377179333386420114391233630515012393090359381717875467071280927583120692784917275074532993409388122061004854178182661632604182150765151482558156183912422898613209559942234127025063687928879910292952039316531554812705081695248540209866005563219806997627684236587554109286831877006896470109805219447282525518519161097673276492456094713735029038771812376330352652393029164468202357817665724369560583349301558861453705718562711798522554316893417360531922795446452749685308492123451575279293644339041629468390133378328145993285368218775498976282596017084494092950586275565868969964447619034372770452127643594002885530340353730337577609060573094563836165559288998090805166088888016631981190567474132421889397451224492478175286707362679459528061705122579238644392225558752144211463152201143723558678398331677420261413849490732610210418705205396485108198008618730081560787598535809656356334449123152662358838247968331030455386114998823400263422044625507507829935684490654252473089135735147481428318393546785418776661158864450118169388804900558540117140348002680864998171847298229035444536926030071973643938958868695657994095200366957439503117930474161132984898344356321926977383591037057394861749532205998932840557833372993944408083463060446903121200107227041538939713625198024076302549803852074630498649236538622458710733295489005936281570737839438843387492079285997225293361642946364581369251919661240027265549956890265107036578709824437885345581015267152770
e = 65537
# u = (u >> 414) << 414
# p = nextprime(u)  p=x*2^414
# n = p^5*q    n=(x*2^414+y)^5*q=q*((x*2^414)^5+5*(x*2^414)^4*y+10*(x*2^414)^3*y^2+10*(x*2^414)^2*y^3+5*(x*2^414)*y^4+y^5)
#              n=y^5*q mod 2^414
nn=n%(2**414)
for y in tqdm(range (2,1000000000)):
    q=nn//(y**5)
    if n%q==0 and isPrime(q):
        print(q)
        break
p=n//q
phi= p**4*(p-1)*(q-1)
d = inverse(e, phi)
m=pow(c,d,n)
print(long_to_bytes(m))
# 128482134863854651455837456755308096854198494400560216319687161937112331696534208532263283890109273
# b'flag{01b3d0ba-06af-4b38-b5a3-fed994023841}\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6\xd6

第四届“长城杯”网络安全大赛暨京津冀网络安全技能竞赛crypto（初决赛）

Random RSA（初赛）

题目

题解

wp

near(决赛）

题目

题解

wp

总结：