Asymmetric Encryption Bloodsuckers use different asymmetric encryption algorithms to send messages to their partners. You may be able to exploit such communications, but first you should be able to recognize the used asymmetric algorithms.
Server: nc 200.136.213.110 7777
We fire netcat and we obtain the following:
1 2 3 4 5
q = 896922063827 g = 12424931089 h = 574559267769 enc(a) = (453104394915, 390471080026) enc(3*a + 32)?
We notice that the cryptosystem here must be ElGamal. One can obtain the encryption of 3*a, because ElGamal is homomorphic in relation to the multiplication, i.e. E(m1)*E(m2) = E(m1*m2). But, it is not in relation to the addition. Therefore, it is required to find the private key x such that g^x mod q = h. As the prime q only has 40 bits, it is easy to find out with the baby step giant step meet in the middle attack. We used https://github.com/viralpoetry/Baby-step-giant-step to compute the discrete log. We obtain x = 202922528794.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
>>> x = 202922528794 >>> q = 896922063827 >>> h = 574559267769 >>> g = 12424931089 # we have now to find a >>> enc = (453104394915, 390471080026) >>> s = pow(enc[0], x, q) >>> sinv = modinv(s, q) # (modinv from https://stackoverflow.com/questions/4798654/modular-multiplicative-inverse-function-in-python) >>> a = enc[1] * sinv % q >>> a 108768066438L >>> to_encrypt = 3*a + 32 >>> r = 5# we chose a small random number for the encryption. it could be whatever you wanted < q >>> result = (pow(g, r, q), to_encrypt * pow(h, r, q) % q) >>> result (801172058328L, 410122112192L)
Easy. We have our first correct answer.
1 2 3 4 5 6 7 8 9 10 11
q = 896922063827 g = 12424931089 h = 574559267769 enc(a) = (453104394915, 390471080026) enc(3*a + 32)? (801172058328, 410122112192) Correct! Next... n = 659381354716006369742363 e = 65537 enc(a) = 554863447144015806910906 enc(a^5 + 2*a + 41)?
Now, this is clearly RSA. The modulus is small. Let’s use yafu to compute the factors of 659381354716006369742363. We obtain p = 864367132729 and q = 762848712947.
1 2 3 4 5 6 7 8 9 10
>>> p = 864367132729 >>> q = 762848712947 >>> n = p * q >>> e = 65537 >>> d = modinv(e, (p-1)*(q-1)) >>> a = pow(554863447144015806910906, d, n) >>> a 218624962707346537869456L >>> pow(a**5 + 2*a + 41, e, n) 215275919603710085695724L
We have our second answer correct.
1 2 3 4 5 6 7 8 9 10
n = 659381354716006369742363 e = 65537 enc(a) = 554863447144015806910906 enc(a^5 + 2*a + 41)? 215275919603710085695724 Correct! Next... n = 776738987646974637425039 g = 776738987646974637425040 enc(a) = 104466234975614190334351556746005105225005455760 enc(a^5)?
Now, this looks like Paillier cryptosystem. We used yafu to discover n = p * q. We obtain p = 952658582963 and q = 815338256053.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
>>> p = 952658582963 >>> q = 815338256053 >>> n = p * q >>> g = 776738987646974637425040 >>> enc = 104466234975614190334351556746005105225005455760 >>> phi = (p-1)*(q-1) >>> miu = modinv((pow(g, phi, n**2)-1)/n, n) # decrypt and find a >>> z = pow(enc, phi, n**2) >>> z = (z - 1)/n >>> a = z*miu % n >>> a 593865001407021231568482L # encrypt a^5 >>> r = 5 #whatever number >>> (pow(g, a**5, n**2) * pow(r, n, n**2)) % (n**2) 551344609697032782258820295222867131320370770770L
Correct. Next we find again ElGamal.
1 2 3 4 5 6 7 8 9 10 11
n = 776738987646974637425039 g = 776738987646974637425040 enc(a) = 104466234975614190334351556746005105225005455760 enc(a^5)? 551344609697032782258820295222867131320370770770 Correct! Next... q = 162468360679141142763506469479039044723348598131343445023537528281758038856725899813448600764965664562827243890486154155054547681581530078506256454819062823302171522262160978639320056038295558351438333626355253455829930861656788077110705347484186791527605530619097928023950578487542852122604132414043739150119 g = 71617122044994067303905663362038925673552248437100144808168324877801061768171815833721974961532703253044394601768959631644002378569370957141698573753120813269172546820898334296643254497348710964283337196775523365259211998702039022625622498418357561295233596431521761773785941196196533383471457791068304542860 h = 111066648693171887028924716387930536202901514118903026147266454463707523131763918297711469710662207420385870870164685517351171893585068487655691524361140991885848958718360460992751593253073812391597394918180851967495018510187596343611325247877606623904208279091478507563768905318293335621925954116646006910388 enc(a) = (21624535586567506603984186779885207318602579759808112698630259017417529498649485922951645341096345328763025063786609897082667076531258136422106222993285575007280223388512289362685146566945916187517382905780252904425034481330835615708515857702294263742141184959896884068790745261235435155068299465225574582560, 38537941029975848030592009789690349376115082020053275876066791343139798710924237464927608815778845257515757255006036413842443376625286738601962899180988337782103893434680014360059921519888813156293982852260141731565853893416439570684816679875490888188370627554793241614773190030997959436875113067106880655048) enc(a^7)?
This one is easy. The ElGamal encryption of a is the following.
1
E(a) = (g^r mod q, a * h^r mod q)
To obtain the encryption of a^7, we elevate E(a) to the power of 7.
1
E(a)^7 = ((g^r mod q)^7, (a * h^r mod q)^7) = (g^(7r) mod q, a^7 * h^(7r) mod q) = E(a^7)
Therefore:
1 2 3 4 5 6
... define q, h, g ... >>> enc = (21624535586567506603984186779885207318602579759808112698630259017417529498649485922951645341096345328763025063786609897082667076531258136422106222993285575007280223388512289362685146566945916187517382905780252904425034481330835615708515857702294263742141184959896884068790745261235435155068299465225574582560, 38537941029975848030592009789690349376115082020053275876066791343139798710924237464927608815778845257515757255006036413842443376625286738601962899180988337782103893434680014360059921519888813156293982852260141731565853893416439570684816679875490888188370627554793241614773190030997959436875113067106880655048) >>> (pow(enc[0], 7, q), pow(enc[1], 7, q)) (111943704492198613677284064414263835827314903408795497288196730523366749172531261312939368180540744924661825776170153157857298436145855968660805139686412343878802804331392369688765040244903208295888020856843171734022924414044150587927040617364297225555547079482268117880403242431146502775006475807941590243957, 146944962972196061304452302982428886923580067615704091332968984386866821167820106942309825648793805501664148988040753726356825992452196561280275962919553230491290426455421904803150216668843887712124953140424115672066452860798980586595286092420270643236030879120858647424877506090672990669173730588282484181475)
Correct. The next one is another RSA with the following parameters.
1 2 3 4
n = 116129573369269565162236051660667188158855673329540427297390499575862981989835841843866583577063083766954029063144621040623764875768299287457499920694511048949688694670794953791035923764107936680805021705444041635396218234076099965276137996734996446529395542124683260815237555361324912425749295153953132095761 e = 65537 enc(a) = 113404819639317667150945206046179254025822100958261129257002960505190359188994098567188808686386964857225447271200495440587539103432162087685650112552863460383570740714408941280241382042752738643406032354358166194009200674868816147437559543328518217678994594982357470461665835857915008170677398859755267093420 enc((31*a)^7)?
RSA is homomorphic to the multiplication and powers. Just do the following.
Encrypt 31.
Multiply the encryption of 31 to the encryption of a. (z = E(31) * E(a) % n)
Power it. (result = pow(z, 7, n))
Done. result is 79422070142774248998696748364536969928051026241019028333521995212847190464228596819898318295431833653185507986566295081274239311469462993984644730127173443271940560058698451295020485382667406426759092058704807263661852917928725084340240033097368645878075171977767675641790645116925564507723204703462264972052
Next. Another Paillier.
1 2 3 4 5
n = 8621606345813741778522514266054273377220780538934639795782688699674225088206322295464704691574306739432963387326203941438845912627154353843605597106654023 g = 8621606345813741778522514266054273377220780538934639795782688699674225088206322295464704691574306739432963387326203941438845912627154353843605597106654024 enc(a) = 7937660128690175325568344972823559278861468103813145508603245376730524355646304917359508580566100608589042820651231838238609822717639617861887063282742304194177278580800908754694218555803321746479637321316698926171902620676195782762387943008573984077258721183694556844093549693467565523559928218327284235089 enc(b) = 33387753148071257428905539518160221978694704069687353836469091655010096223312256529016397591008817430414577588510555623557614906758093969392417915817764626568693773437705685363505728318306424617495507184665856273528630405473435911817059436953757079883134497707484413544554359132244534862297762773379557525426 enc(31*a + 12*b + 56)?
Pallier is homomorphic to the addition and the multiplication, in the following way:
