Analysis
Inside the file ‘flipping_bits.jar’ we have only one file, flipping_bits.txt. This challenge provided two messages RSA encoded with different public exponents and the same modulus.
We have:
Cyphertext ct1: 13981765388145083997703333682243956434148306954774120760845671024723583618341148528952063316653588928138430524040717841543528568326674293677228449651281422762216853098529425814740156575513620513245005576508982103360592761380293006244528169193632346512170599896471850340765607466109228426538780591853882736654
Cyphertext ct2: 79459949016924442856959059325390894723232586275925931898929445938338123216278271333902062872565058205136627757713051954083968874644581902371182266588247653857616029881453100387797111559677392017415298580136496204898016797180386402171968931958365160589774450964944023720256848731202333789801071962338635072065
Exponent e1: 13
Exponent e2: 15
Modulus (n): 103109065902334620226101162008793963504256027939117020091876799039690801944735604259018655534860183205031069083254290258577291605287053538752280231959857465853228851714786887294961873006234153079187216285516823832102424110934062954272346111907571393964363630079343598511602013316604641904852018969178919051627
In RSA encryption, the modulus n should be the product of two large prime numbers p and q:
Large prime number p, Large prime number q
Modulus n = p * q
But when we were searching for those numbers, we find that n was itself a prime number. So what?
Solution
Using the same modulus with different exponents leaves RSA open to a “Common Modulus Attack” described in many places (like here).
As described in the link, this can be solved by performing the Extended Euclidean Algorithm (EEA) on the two exponents and using the result in a mathematical operation.
With the EEA we can compute the integers such that
x * e1 + y * e2 = 1 (Bézout’s identity)
The extended GCD can be found using wolfram alpha and solves as
ExtendedGCD[13,15] = [7, -6]
[We could also use xgcd from libnum library as libnum.xgcd(13, 15) ]
So x = 7 and y = – (6).
And for Bézout’s Identity:
7*13 + (-6)*15 = 1
Because y < 0 we’ll need to compute the inverse of (ct2 mod N) later.
Now:
Plaintext = ct1x * ct2y mod N
Plaintext = ct17 mod N * ct2(-6) mod N
In Python, we can translate with the function pow(x, y, z), computed more efficiently than pow(x, y) % z.
It returns x to the power y; if z is present, return x to the power y, modulo z.
Using this with the python code below gives the solution. Note that to raise to a negative power the value needs to be inverted first (i.e. gmpy2.invert), else Python throws an error:
TypeError: pow() 2nd argument cannot be negative when 3rd argument specified
The function gmpy2.invert(x,m) returns y such that x * y == 1 modulo m, or 0 if no such y exists.
We wrote a Python script to solve this, and called flipping-bits-solve.py
import gmpy2
import binascii
ct1 = 13981765388145083997703333682243956434148306954774120760845671024723583618341148528952063316653588928138430524040717841543528568326674293677228449651281422762216853098529425814740156575513620513245005576508982103360592761380293006244528169193632346512170599896471850340765607466109228426538780591853882736654
ct2 = 79459949016924442856959059325390894723232586275925931898929445938338123216278271333902062872565058205136627757713051954083968874644581902371182266588247653857616029881453100387797111559677392017415298580136496204898016797180386402171968931958365160589774450964944023720256848731202333789801071962338635072065
e1 = 13
e2 = 15
modulus = 103109065902334620226101162008793963504256027939117020091876799039690801944735604259018655534860183205031069083254290258577291605287053538752280231959857465853228851714786887294961873006234153079187216285516823832102424110934062954272346111907571393964363630079343598511602013316604641904852018969178919051627
# ct1 == plaintext1 ** 13 % modulus
# ct2 == plaintext2 ** 15 % modulus
plaintext = pow(ct1,7,modulus) * pow(gmpy2.invert(ct2,modulus),6,modulus)
plaintext = plaintext % modulus
cyphertext2 = plaintext ** 15 % modulus
print 'plaintext1:'
print(plaintext)
print ''
print 'Hex plaintext1:'
print hex(plaintext)
print ''
print 'Plaintext 1:'
print(binascii.unhexlify('%x'%plaintext))
print ''
print 'Cyphertext 2:'
print cyphertext2
print ''
if (cyphertext2 == ct2):
print "Plaintext1 and Plaintext2 are the same."
else:
print "Plaintext1 and Plaintext2 are not the same."
And this is the result:
The flag we were searching for is:
flag-54d3db5c1efcd7afa579c37bcb560ae0
