中国剩余定理

中国剩余定理

1.中国剩余定理

• 设p和q是不同的质数，且n = p*q。对于任意(X1, x2)，其中 0 ≤ x1 < p 和 0 ≤ x2 < q，存在数x，其中 0 ≤ x < n。
• 中国剩余定理给出了以下的一元线性同余方程组：
• x1 = x mod p
• x2 = x mod q
• 因此，任何整数x (0 < x< n)都可以在其CRT表示(X1, X2)中唯一表示。

2.欧拉定理

• 欧拉定理是费马小定理的推广。或称为欧拉-费马定理。
• n是一个正整数，a是gcd(a, n) = 1的任意整数，则a^Φ(n) = 1 (mod n)。
• Φ(n)是欧拉函数，即不超过n，与n互素的正整数的个数。对于质数p， Φ § = p-1。

3.RSA解密流程

• 根据中国剩余定理可以将 m = c^d mod n写成
  m1=c^d mod p
  m2=c^d mod q
• 这个时候n的位数降低了。但是d的位数依旧很大。 为了计算c^d mod p，我们可以使用欧拉定理来降低d的位数
  c ^ d mod p = c ^ ( d mod Φ ( p ) ) mod p = c ^ ( d mod (p-1) ) mod p 上面式子证明如下：d = kφ( p ) + d mod φ( p )（或者d = k(p-1) + d mod ( p-1 )）
  其中k是一个整数。c ^ d = c ^( k φ ( p ) + d mod φ( p ) ) = (c ^ φ( p )) ^k * c ^ d mod φ( p )根据欧拉定理可以得到c ^ φ ( p ) = 1 (mod p)则 c ^ d = 1^k * c ^ d mod φ( p ) = c ^ d mod φ( p ) ( mod p)`
• 同理可得：
  c ^ d mod q = c ^ ( d mod Φ ( q ) ) mod q = c ^ ( d mod (q-1) ) mod q 令dP = d mod (p-1） = e^(-1)mod(p-1)
  dQ = d mod (q-1） = e^(-1)mod(p-1) m1 = c^dP mod p
  `m2 = c^dQ mod q
• 则RSA的求解过程如下所示：
  qInv = q ^ (-1) mod p h = qInv * ( m1-m2 ) mod p
  `m = m2 + h*q (m为明文)(https://file.pop.atomgit.com/atomgit/information/2025/04/03/6e0f1c67d6194ecb950e8179a43d540a.png)
• 最后的求解过程可以写成：
  `S=CRT(m1,m2)=m2+((m1–m2)(q^(–1)modp) modp)⋅q
  

4.例题

• ？SimpleRSA
  题目代码：

  #!/usr/bin/env python3.9
  
  # -*- coding: utf-8 -*-
  
  import gmpy2
  
  from Crypto.Util.number import getPrime, isPrime, bytes_to_long
  
  from secret import FLAG, E1, E2, P, Q1, Q2
  
    
    
  
  def next_prime(num: int) -> int:
  
      num = num + 2 if num % 2 else num + 1
  
      while not isPrime(num):
  
          num += 2
  
      return num
  
    
    
  
  p = getPrime(1024)
  
  q = next_prime(getPrime(16) * p + 38219)
  
  n = p * q
  
  c = pow(E1, 65537, n)
  
  print(f'n = {n}')
  
  print(f'c = {c}')
  
  # n = 1605247600724752598798254639224215706171506359654961357324428027985787942008103766562745464838961569081446916113769517713344420113584254259000172572811154232107339480903672251992191997458469905064423618888336088652352540882576826988355783159237971043770132628344798937353150930071309347972804118952814447576207066147031238749098842662046825743988208813903138796789940911515825517078554074496474819128789835309636804325132602557092847746454786387067599510769382078521691609970320528531270474091713477040343897269903489441410062592732302402854035415438078656688806905350495825334584533345448091335565792091890185673190424063
  
  # c = 751639057610677013264061431434189083017589908118307247217007533938435229431015858783222167911772848893015518607229280589985711010766459396989232072512314594917029375221335361209036112742388866873824163350886610514973038316512032459352053158417705406031466332440378871927174731975794579894912999936641163063898365134788537389162378185448090279397717831977803284480743612393591614284972981435749362255654561121758163485884075260156288337176713756471879489767416836868661153693157792733142765671887792303181376620864506386820826866340907593080654521498766421056474652652337037121881207188033108746890998208582406826010121861
  
    
  
  assert E2.bit_length() == 69
  
  ns = [getPrime(1024) * getPrime(1024) for _ in range(3)]
  
  cs = [pow(E2, 89, n) for n in ns]
  
  print(f'ns = {ns}')
  
  print(f'cs = {cs}')
  
  # ns = [15863230586500684911356384742123404120213699052018048588650392009927565369685497256344682150189923131009586323640507773706997704860898682946308031020361302334248895233255911348365179153799197341744863134926804603973507415697810440916305092395180382239729550833607847524005391137474497849077097574452115379368463540087172800902210822143687014813631366360652583216269138116785489485772437870528892032119729929607857459621078790511144060710035933887337208301078892163837203412081114510143406013892393607932596921308889058909544584619676380766485493114814753878272881866907210235681877689493671668534251778397658670518117, 14144098469438619358682652828507744381697293556670717685553585719665002440476256008471235313826051740009083510860714991201047915737216102220242621674841600987122005914542061963618272275986835928673920375768272390912778741502655909281390948606467847118377641357547931472588836726339758576038273820470879637555458446243401248151675266602656677360819563744765522495640821496694918515669243614141704744848980746101569785439728585144841655665959389460512628800782742764147773150430552859331269667626942993392101897661719871375721143240270211821269260950380944670195863016621594387236339317938305273510719419578308449465183, 27563822879593503938377821960427219022565215631856333510782568496016547757945464794632272818101891677705256471714805217606503652132995136255720639088424576003650628211271025648183600635145895528466199068640094470078526413324708028578289949241288828542143203769199399500669311878391255837977932634772778594526940501234736059441483897017015324765266787399950699732518347518591167932031031320265136158304460199654008895095274754918153773566824931440342525688741289235153882699461549523425169846266597156773535163599640189457171272058311480951820887261040891344076039474315985825984444520336790670313179493074014037981261]
  
  # cs = [3833095607830862948079097323254872789586576953317671099752083261949616608759231291050566542764984974722790226120399722937104503590740358249900089784508490830379531632752169777949200718567033018577184658177019404903817920024468923715441355404672443007723525750768430895425376124679225715687382380114628103058312176343693900115638265002657622618744666247132114654135429040069316368839938881716554901593031901272992940200484460436193699175500376368456706998564064693820008778900344357745691652875500810447147088715289581351501876012044611990972521570253106671158207677490849249612002954497927762168699886110455354481924, 1502420121177211156091634258259634977709023894278792755694473756163084431123774101512866316989917922052023168401167212284219907272528117024670443698990238243030221117004372456475521502350404137469088570170885409265567084376069256924135270283335242133163303599239181417949980292944203204296598188175632723968779672994090788585343302473442389865459398142634104331743517384589200789331489394375604801951994831647339839112698394141328178967516636452592385248135340133712522135715943787590172334743893259621909532456281362868290556461907936774231166936915669816509378419892149164552548131776979706381641477878931403040942, 8992204063713908492214256291861339175525948946919629972908439132005643626148678347198381531633907182877152728077958345519083406637446972079387161726967295886447791613166577391233866583354793842121902234644830640050181130381996083089350911224037154798259291124104894554037604500881250119806371348673833105103600782286898276354573884788251542211434143476774391457587885772379990104835187104619922442613860682792470389490804228050671124495925536024571104944112397143299499508504917890140939438891891453283594000764399193028606955089853654071198909973555844004685149713774167524224100487937899126480545681565581673958854]
  
    
  
  qq = getPrime(1024)
  
  nn = P * qq
  
  qqq = qq >> 460 << 460
  
  print(f'nn = {nn}')
  
  print(f'qqq = {qqq}')
  
  # nn = 16851735797771199659625936797279158526379741298692339786049494329385618191510929735113284926125682522862667382938603116481087115598324232020838136618518964343752653000145611092980612556947954728339508416646035295651852840099205127587606898235203114875942637900167644300657599966420459187131027117268004042708998239798434578246497419547543598779697909298102358128788120332794123690714647499091326245022977970510468925837363300545900657420134894815246189043375619879915523611890538142257042753868665844692029124229028056547096764320547579965641276151760507921199827910445919017775913411823263307923216323527883262438117
  
  # qqq = 121042531930820997492656296084544616958724191434895945419858099204426898711413526806300854553993738803031497438495403291406481997877273916883918253302909196533823945327277312672931819555344139777992801106437643790498379469530787985051569590331291422592393540391481519004782904598710037907420679190942964514816
  
    
  
  assert len(FLAG) == 42
  
  n1 = P * Q1
  
  n2 = P * Q2
  
  c1 = pow(bytes_to_long(FLAG), E1, n1)
  
  c2 = pow(bytes_to_long(FLAG), E2, n2)
  
  print(f'n1 = {n1}')
  
  print(f'n2 = {n2}')
  
  print(f'c1 = {c1}')
  
  print(f'c2 = {c2}')
  
  # n1 = 21655617838358037895534605162358784326495251462447218485102155997156394132443891540203860915433559917314267455046844360743623050975083617915806922096697304603878134295964650430393375225792781804726292460923708890722827436552209016368047420993613497196059326374616217655625810171080545267058266278112647715784756433895809757917070401895613168910166812566545593405362953487807840539425383123369842741821260523005208479361484891762714749721683834754601596796707669718084343845276793153649005628590896279281956588607062999398889314240295073524688108299345609307659091936270255367762936542565961639163236594456862919813549
  
  # n2 = 24623016338698579967431781680200075706241014384066250660360949684385831604822817314457973559632215801205780786144608311361063622813017396858888436529116737754653067203843306015767091585697803364656624926853551997229897087731298797904208292585562517602132663331748784390752958757661484560335406769204491939879324079089140420467301773366050084810282369044622442784113688062220370531522036512803461607049619641336524486507388232280683726065679295742456158606213294533956580462863488082028563360006966912264908424680686577344549034033470952036766850596897062924137344079889301948258438680545785139118107899367307031396309
  
  # c1 = 2615722342860373905833491925692465899705229373785773622118746270300793647098821993550686581418882518204094299812033719020077509270290007615866572202192731169538843513634106977827187688709725198643481375562114294032637211892276591506759075653224150064709644522873824736707734614347484224826380423111005274801291329132431269949575630918992520949095837680436317128676927389692790957195674310219740918585437793016218702207192925330821165126647260859644876583452851011163136097317885847756944279214149072452930036614703451352331567857453770020626414948005358547089607480508274005888648569717750523094342973767148059329557
  
  # c2 = 6769301750070285366235237940904276375318319174100507184855293529277737253672792851212185236735819718282816927603167670154115730023644681563602020732801002035524276894497009910595468459369997765552682404281557968383413458466181053253824257764740656801662020120125474240770889092605770532420770257017137747744565202144183642972714927894809373657977142884508230107940618969817885214454558667008383628769508472963039551067432579488899853537410634175220583489733111861415444811663313479382343954977022383996370428051605169520337142916079300674356082855978456798812661535740008277913769809112114364617214398154457094899399
  

  求E1：
  由q = next_prime(getPrime(16) * p + 38219)可知，q为p*getPrime(16)+38219的下一个素数，因此getPrime(16)较小，所以我们可以在其取值范围为遍历出符合题目的值,从而解出q。
  脚本：

  # 遍历一个范围内的整数，从2^15到2^16
  for i in range(2 ** 15, 2 ** 16):
      # 检查当前的整数i是否是素数
      if isPrime(i):
          # 计算一个候选的q值
          # i * iroot(n // i, 2)[0] 是一个基于n和i的某种计算,iroot(n // i, 2)[0]   可能是计算n//i开平方根
          # +38219 是一个偏移量，可能是为了增加随机性或避免某些特殊情况
          # next_prime函数找到大于或等于该值的下一个素数
          q = next_prime(i * iroot(n // i, 2)[0] + 38219)
          # 检查n是否能被q整除
          if n % q == 0:
              # 如果能整除，打印出q并退出循环
              print(q)
              break
  
  # 计算p的值，p是n除以q的结果
  p = n // q
  # 计算欧拉函数phi(n)，在RSA中phi(n) = (p - 1) * (q - 1)
  phi = (p - 1) * (q - 1)
  # 计算私钥d，d是e在模phi(n)下的逆元
  # invert函数可能是用来计算模逆元的函数
  d = invert(e, phi)
  # 使用私钥d对密文c进行解密，得到明文E1
  # pow函数在这里实现了模幂运算，即c^d % n
  E1 = pow(c, d, n)
  # 打印解密后的明文E1
  print(E1)
  
  

  获得E1 = 377312346502536339265
  求解E2：
  中国剩余定理简单处理一下，之后开e次方即可。
  脚本：

  from functools import reduce  # 导入reduce函数，用于计算多个数的乘积
  
  # 定义中国剩余定理函数
  def chinese_remainder(modulus, remainders):
      # 初始化最终结果的累加器
      Sum = 0
      # 计算所有模数的乘积，即prod = m1 * m2 * ... * mn
      prod = reduce(lambda a, b: a * b, modulus)
      
      # 遍历模数列表和余数列表
      for m_i, r_i in zip(modulus, remainders):
          # 计算 p_i = prod / m_i，即每个模数对应的“部分乘积”
          p = prod // m_i
          # 计算每个同余方程的贡献：r_i * (p_i的逆元 * p_i)
          # inverse(p, m_i) 是计算 p_i 在模 m_i 下的逆元
          Sum += r_i * (inverse(p, m_i) * p)
      
      # 最终结果是累加器Sum对prod取模的结果
      return Sum % prod
  
  ns = [15863230586500684911356384742123404120213699052018048588650392009927565369685497256344682150189923131009586323640507773706997704860898682946308031020361302334248895233255911348365179153799197341744863134926804603973507415697810440916305092395180382239729550833607847524005391137474497849077097574452115379368463540087172800902210822143687014813631366360652583216269138116785489485772437870528892032119729929607857459621078790511144060710035933887337208301078892163837203412081114510143406013892393607932596921308889058909544584619676380766485493114814753878272881866907210235681877689493671668534251778397658670518117, 14144098469438619358682652828507744381697293556670717685553585719665002440476256008471235313826051740009083510860714991201047915737216102220242621674841600987122005914542061963618272275986835928673920375768272390912778741502655909281390948606467847118377641357547931472588836726339758576038273820470879637555458446243401248151675266602656677360819563744765522495640821496694918515669243614141704744848980746101569785439728585144841655665959389460512628800782742764147773150430552859331269667626942993392101897661719871375721143240270211821269260950380944670195863016621594387236339317938305273510719419578308449465183, 27563822879593503938377821960427219022565215631856333510782568496016547757945464794632272818101891677705256471714805217606503652132995136255720639088424576003650628211271025648183600635145895528466199068640094470078526413324708028578289949241288828542143203769199399500669311878391255837977932634772778594526940501234736059441483897017015324765266787399950699732518347518591167932031031320265136158304460199654008895095274754918153773566824931440342525688741289235153882699461549523425169846266597156773535163599640189457171272058311480951820887261040891344076039474315985825984444520336790670313179493074014037981261]
  cs = [3833095607830862948079097323254872789586576953317671099752083261949616608759231291050566542764984974722790226120399722937104503590740358249900089784508490830379531632752169777949200718567033018577184658177019404903817920024468923715441355404672443007723525750768430895425376124679225715687382380114628103058312176343693900115638265002657622618744666247132114654135429040069316368839938881716554901593031901272992940200484460436193699175500376368456706998564064693820008778900344357745691652875500810447147088715289581351501876012044611990972521570253106671158207677490849249612002954497927762168699886110455354481924, 1502420121177211156091634258259634977709023894278792755694473756163084431123774101512866316989917922052023168401167212284219907272528117024670443698990238243030221117004372456475521502350404137469088570170885409265567084376069256924135270283335242133163303599239181417949980292944203204296598188175632723968779672994090788585343302473442389865459398142634104331743517384589200789331489394375604801951994831647339839112698394141328178967516636452592385248135340133712522135715943787590172334743893259621909532456281362868290556461907936774231166936915669816509378419892149164552548131776979706381641477878931403040942, 8992204063713908492214256291861339175525948946919629972908439132005643626148678347198381531633907182877152728077958345519083406637446972079387161726967295886447791613166577391233866583354793842121902234644830640050181130381996083089350911224037154798259291124104894554037604500881250119806371348673833105103600782286898276354573884788251542211434143476774391457587885772379990104835187104619922442613860682792470389490804228050671124495925536024571104944112397143299499508504917890140939438891891453283594000764399193028606955089853654071198909973555844004685149713774167524224100487937899126480545681565581673958854]
  e = 89
  m_e = chinese_remainder(ns,cs)
  E2 = gmpy2.iroot(m_e,e)[0]
  print(E2)