24 Jun 2019

RSA-Broadcast Attack

RSA-Broadcast Attack

  • Broadcast Attack

    • 中国剩余定理

      中国剩余定理

    • 例子
      import gmpy
      def extended_gcd(a, b):
          x,y = 0, 1
          lastx, lasty = 1, 0
          while b:
              a, (q, b) = b, divmod(a,b)
              x, lastx = lastx-q*x, x
              y, lasty = lasty-q*y, y
          return (lastx, lasty, a)
      def crt(items):
        N = 1
        for a, n in items:
          N *= n
        result = 0
        for a, n in items:
          m = N/n
          r, s, d = extended_gcd(n, m)
          if d != 1:
            N=N/n
            continue
          result += a*s*m
        return result % N, N
          
      datas= [{"c": 19131432661217908470262338421299691998526157790583544156741981238822158563988520225986915234570037383888112724408392918113942721994125505014727545946133307329781747600302829588248042922635714391033431930411180545085316438084317927348705241927570432757892985091396044950085462429575440060652967253845041398399648442340042970814415571904057667028157512971079384601724816308078631844480110201787343583073815186771790477712040051157180318804422120472007636722063989315320863580631330647116993819777750684150950416298085261478841177681677867236865666207391847046483954029213495373613490690687473081930148461830425717614569, "e": 4, "n": 20129615352491765499340112943188317180548761597861300847305827141510465619670536844634558246439230371658836928103063432870245707180355907194284861510906071265352409579441048101084995923962148527097370705452070577098780246282820065573711015664291991372085157016901209114191068574208680397710042842835940428451949500607613634682684113208766694028789275748528254287705759528498986306494267817198340658241873024800336013946294891687591013414935237821291805123285905335762719823771647853378892868896078424572232934360940672962436849523915563328779942134504499568866135266628078485232098208237036724121481835035731201383423},
          
      	{"c": 15341898433226638235160072029875733826956799982958107910250055958334922460202554924743144122170018355117452459472017133614642242411479849369061482860570279863692425621526056862808425135267608544855833358314071200687340442512856575278712986641573012456729402660597339609443771145347181268285050728925993518704899005416187250003304581230701444705157412790787027926810710998646191467130550713600765898234392350153965811595060656753711278308005193370936296124790772689433773414703645703910742193898471800081321469055211709339846392500706523670145259024267858368216902176489814789679472227343363035428541915118378163012031, "e": 4, "n": 31221650155627849964466413749414700613823841060149524451234901677160009099014018926581094879840097248543411980533066831976617023676225625067854003317018794041723612556008471579060428898117790587991055681380408263382761841625714415879087478072771968160384909919958010983669368360788505288855946124159513118847747998656422521414980295212646675850690937883764000571667574381419144372824211798018586804674824564606122592483286575800685232128273820087791811663878057827386379787882962763290066072231248814920468264741654086011072638211075445447843691049847262485759393290853117072868406861840793895816215956869523289231421},
          
      	{"c":18715065071648040017967211297231106538139985087685358555650567057715550586464814763683688299037897182845007578571401359061213777645114414642903077003568155508465819628553747173244235936586812445440095450755154357646737087071605811984163416590278352605433362327949048243722556262979909488202442530307505819371594747936223835233586945423522256938701002370646382097846105014981763307729234675737702252155130837154876831885888669150418885088089324534892506199724486783446267336789872782137895552509353583305880144947714110009893134162185382309992604435664777436197587312317224862723813510974493087450281755452428746194446 , "e": 4, "n":29944537515397953361520922774124192605524711306753835303703478890414163510777460559798334313021216389356251874917792007638299225821018849648520673813786772452822809546571129816310207232883239771324122884804993418958309460009406342872173189008449237959577469114158991202433476710581356243815713762802478454390273808377430685157110095496727966308001254107517967559384019734279861840997239176254236069001453544559786063915970071130087811123912044312219535513880663913831358790376650439083660611831156205113873793106880255882114422025746986403355066996567909581710647746463994280444700922867397754748628425967488232530303},
          
      	{"c":2282284561224858293138480447463319262474918847630148770112472703128549032592187797289965592615199709857879008271766433462032328498580340968871260189669707518557157836592424973257334362931639831072584824103123486522582531666152363874396482744561758133655406410364442174983227005501860927820871260711861008830120617056883514525798709601744088135999465598338635794275123149165498933580159945032363880613524921913023341209439657145962332213468573402863796920571812418200814817086234262280338221161622789516829363805084715652121739036183264026120868756523770196284142271849879003202190966150390061195469351716819539183797 , "e": 4, "n": 25703437855600135215185778453583925446912731661604054184163883272265503323016295700357253105301146726667897497435532579974951478354570415554221401778536104737296154316056314039449116386494323668483749833147800557403368489542273169489080222009368903993658498263905567516798684211462607069796613434661148186901892016282065916190920443378756167250809872483501712225782004396969996983057423942607174314132598421269169722518224478248836881076484639837343079324636997145199835034833367743079935361276149990997875905313642775214486046381368619638551892292787783137622261433528915269333426768947358552919740901860982679180791}]
      data = []
      for data in datas:
          e=data['e']
          n=data['n']
          msg=data['c']
          data = data + [(msg, n)]
      x, n = crt(data)
      e=data['e']
      plain = gmpy.mpz(x).root(e)[0].digits()
      print(plain)
      
  • Broadcast Attack with Linear Padding

    • 原理

      $ c_1={(a_1*m+b_1)}^3modn_1$

      $ c_2={(a_2*m+b_2)}^3modn_2$

      $ c_3={(a_3*m+b_3)}^3modn_3$

      $T_1modn_1=1$

      $T_1modn_2=0$

      $T_1modn_3=0$

      $T_2modn_1=0$

      $T_2modn_2=1$

      $T_2modn_3=0$

      $T_3modn_1=0$

      $T_3modn_2=0$

      $T_3modn_3=1$

      $[T_1(a_1m+b_1)^3-c_1]modn_1n_2n_3=0$

      $[T_2(a_2m+b_2)^3-c_2]modn_1n_2n_3=0$

      $[T_3(a_3m+b_3)^3-c_3]modn_1n_2n_3=0$

    • 例子
      cArray=[0x3ec0dac47c45bcb89edda91a302ee32b7202a93fac6056176cd6bd8f7a94b5f2c43fa10c5e4dae5e2bef32f13141889ea7ac09bae39966821e1c3b516eb7ddc41de8d9db2fed5f012614a1ee4fc8515fb18cfed81834be3f869dfb6d38279a1f670ccfa56ef1f1377651e11c2e9dd917701f1eac41653138e1777006d41b3f6b,
      0x2a50058d6bac5ecc1d20e60e6dd3b74b372e761b49be0826f2c803fe7dff502b64202905fad1f336650313825b1e3d5e5bfb739f135e3bc69052394a20d1cfe6498d9e78730b3cab49b78e64b6388d0e7cb3a4ad9458ec4cc6415bc509af080d20dc6f95056f7619c525bc482389afea0e8c5693b6e46f06e28dac8867ee987a,
      0x20ac4dd17cfd459112dbd86d024a4a44d841bf7eaec3167cc0a430bf6854c6552dde5aad514fdff23fa9ee9f416000450b772406e9ba545076787ce6e9dedf38d70601dcdc3a7cc46fa60c1877ec680081dd324de5235d40526c55d0f975f65e4e6734871e0338503b7256f7e9ad16cbe4d1329675d7fd7c97778a5c32ca1127]
           
      nArray=[0x8de0792c98a93c950ea12c65d62fdbbfd46d6aab145bc39ecebb371acd6774ee9fba24db94437485b5938249bdedf32d2aa2e8799b6aa6db63bbb2ddd5b458f1f437769a7710eee95069b3650e96253e4b0c5e2a22389673f74b0b01bd0956669a519aec556383f9b8d76f04b2a00a491625649bc6af4a1fa4e10aefc8c33cb5,
      0x948279bc2d86bee933357246711e64b5dff9f924e97559d0527aaa265e441a5ca259538161d5fe3efcbdc85b72b46b96d50afa3bf5d4bab7b850bcfa604fa74ef525b710e11d7f2c26b6df595cb9ea2b9a81fc81f0a721fbd9b0fef341bd471457c64efad02df1a2e93ada374627f55c33a178890904adb982e3d5df4fe78433,
      0xa98e47d25554632b5c2a2b6d292f2caf088050eb1ffbc556c062bebdb10f65fcbb942b9f0fdafa724ca90ea85ab17c1c2cd15eb4a59bf672909fbf0ef0fb88ac2569e571741162805c495b60dd8ea0eee9e5afb2ddcd5435d5fcfbd1c49f496eaef37ecde17b6a64a69cb869425d77d13f487632504b851f309ff36c826570cb]
      aArray=[0x8f2b591edb38649f6637abc8cd63f2e9f50e024d7230151b1f888190a821d10213587f34633dd2a7b40f4d37c338c420acdc2df19f88e958a250cd691922c781,
      0xae3e922d88e35e986e5dd4e8dedab00a1ab7f9f5f3fd658eade9371d1247ef7ada800ca381ff3f9c69a30dbf3c61c9f9539863fdb2d2c8af23d4cb87a9e5857f,
      0xe4550619a6029ac6158f188a969741cdd2cc37d1ff2c9dd1f24a7f6b12357196a15852912cb61e64e4ccb2ff6dae5a5f654fbe20623f04c6d8428d72ad5e02ef]
      bArray=[0xc955b34abfce3a409449bebc24163397795a163d337b7fb1320900aaffc21576d785b115f7d3dca7ada072f1c6608dfeb49c6c6264e5f691cf9bb96548222581,
      0xcb50868d5d12d5f166b2e57ef4789f8ebaacc1137a055118d1650e4557bcf05f3858a9124783c8be9be947667b45cdf1a4e2604e544210e8acc665e1c1c0d2ef,
      0x97a4d4c4b3e5ed99a5539ac17cde2a32890a0601be7f7bb6026cfe4a9ffe93633be15c4345268fec2bc69030353db729ccacfeaa3aa0952df418220db0266b4f]
           
      """
      Performs Hastads attack on raw RSA with no padding.
      cArray = Ciphertext Array
      nArray = Modulus Array
      e = public exponent
      """
      def hastads(cArray,nArray,e=3):
      	if(len(cArray)==len(nArray)==e):
      		for i in range(e):
      			cArray[i] = Integer(cArray[i])
      			nArray[i] = Integer(nArray[i])
      		M = crt(cArray,nArray)
      		return(Integer(M).nth_root(e,truncate_mode=1))
      	else:
      		print("CiphertextArray, ModulusArray, need to be of the same length, and the same size as the public exponent")
           
           
      """
      Performs Hastads attack on raw RSA with no padding.
      This is for RSA encryptions of the form: cArray[i] = pow(aArray[i]*msg + bArray[i],e,nArray[i])
      Where they are all encryptions of the same message.
      cArray = Ciphertext Array
      nArray = Modulus Array
      aArray = Array of 'slopes' for the linear padding
      bArray = Array of 'y-intercepts' for the linear padding
      e = public exponent
      """
      def linearPaddingHastads(cArray,nArray,aArray,bArray,e=3,eps=1/8):
      	if(len(cArray) == len(nArray) == len(aArray) == len(bArray) == e):
      		for i in range(e):
      			cArray[i] = Integer(cArray[i])
      			nArray[i] = Integer(nArray[i])
      			aArray[i] = Integer(aArray[i])
      			bArray[i] = Integer(bArray[i])
      		TArray = [-1]*e
      		for i in range(e):
      			arrayToCRT = [0]*e
      			arrayToCRT[i] = 1
      			print arrayToCRT
      			TArray[i] = crt(arrayToCRT,nArray)
      		print TArray
      		P.<x> = PolynomialRing(Zmod(prod(nArray)))
      		gArray = [-1]*e
      		for i in range(e):
      			gArray[i] = TArray[i]*(pow(aArray[i]*x + bArray[i],e) - cArray[i])
      		print gArray
      		g = sum(gArray)
      		g = g.monic()
      		# Use Sage's inbuilt coppersmith method
      		roots = g.small_roots(epsilon=eps)
      		if(len(roots)== 0):
      			print("No Solutions found")
      			return -1
      		return roots[0]
      	else:
      		print("CiphertextArray, ModulusArray, and the linear padding arrays need to be of the same length," + "and the same size as the public exponent")
           
      print(hastads(cArray,nArray))
      print(linearPaddingHastads(cArray,nArray,aArray,bArray))
      

Tags:
0 comments



本作品采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议CC BY-NC-ND 4.0)进行许可。

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License (CC BY-NC-ND 4.0).