We got encrypted text like this.
It seems like it had been encrypted using RSA
algorithm since it shows e
, n
, and ct
.
n
are stands for modulus value,
e
are the exponent, and
ct
are the encrypted text
The n
value are same, the difference are located on e
and ct
value. We can decrypt the encrypted text using Common Modulus Attack.
You can read the explanations here.
You can use this script for decrypting the flag.
Exploits-and-Scripts/RSA: Common modulus attack.py at master ยท a0xnirudh/Exploits-and-Scripts
I've made little modification of the script so it can print the flag directly
#!/usr/bin/python3.4
import gmpy2
class RSAModuli:
def __init__(self):
self.a = 0
self.b = 0
self.m = 0
self.i = 0
def gcd(self, num1, num2):
"""
This function os used to find the GCD of 2 numbers.
:param num1:
:param num2:
:return:
"""
if num1 < num2:
num1, num2 = num2, num1
while num2 != 0:
num1, num2 = num2, num1 % num2
return num1
def extended_euclidean(self, e1, e2):
"""
The value a is the modular multiplicative inverse of e1 and e2.
b is calculated from the eqn: (e1*a) + (e2*b) = gcd(e1, e2)
:param e1: exponent 1
:param e2: exponent 2
"""
self.a = gmpy2.invert(e1, e2)
self.b = (float(self.gcd(e1, e2)-(self.a*e1)))/float(e2)
def modular_inverse(self, c1, c2, N):
"""
i is the modular multiplicative inverse of c2 and N.
i^-b is equal to c2^b. So if the value of b is -ve, we
have to find out i and then do i^-b.
Final plain text is given by m = (c1^a) * (i^-b) %N
:param c1: cipher text 1
:param c2: cipher text 2
:param N: Modulus
"""
i = gmpy2.invert(c2, N)
mx = pow(c1, self.a, N)
my = pow(i, int(-self.b), N)
self.m= mx * my % N
def print_value(self):
hex_vallue = hex(self.m)[2::]
print("Plain Text: ", bytes.fromhex(hex_vallue))
def main():
c = RSAModuli()
N = 21388731509885000178627064516258054470260331371598943108291856742436111736828979864010924669228672392691259110152052179841234423220373839350729519449867096270377366080249815393746878871366061153796079471618562067885157333408378773203102328726963273544788844541658368239189745882391132838451159906995037703318134437625750463265571575001855682002307507556141914223053440116920635522540306152978955166077383503077296996797116492665606386925464305499727852298454712455680910133707466125522128546462287576144499756117801116464261543533542827392699481765864054797509983998681705356909524163419157085924159390221747612487407
c1 = 10832767136661619622293208748444962392355211301390434120939858183061348121126484914263671262032603875084667844823015664447375648718327494489656817860025737727356822703892293211022320699697919627907394583787345038714333739600698382532854618636094930253033489471351451429607353151015568123268427367950348329135569722792929241394325167453525160818746481257803112384890621897151307914147207385945644054978785846514561379487923125221730977998641404608153621221989242862072038048891093337039913905830269768414927334743978508494831586214464123847828971941221037875260516473982025116976142753481691811417555124564400023181428
c2 = 15339581512280546253022387613330506135473528946217386214104392886174532962135139018179028980415602501799731665623533337161466343141774695260798342966907592969192136730428838101668117599627074424456369362732331025534652310626217911372168741784410233370188819015541694457313359727564553135243865091813543574169503409997765186767976316668351998243685484183615633052413572395870658899189135714137152486690320920884963915388873421509027812888500063744545503640233833759600980489533968220839778372130766115290961393758948141655306677776381429819578626575875511596616706688649422193432129579216085481063417748767088461582856
e1 = 65537
e2 = 35
c.extended_euclidean(e1, e2)
c.modular_inverse(c1, c2, N)
c.print_value()
if __name__ == '__main__':
main()
Running the script will give us a flag