Navigation Menu

Skip to content

Instantly share code, notes, and snippets.

@apogiatzis
Created November 13, 2018 04:25
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 2 You must be signed in to fork a gist
  • Save apogiatzis/00b047b6d6570d4e94b4ae00db6fc6e7 to your computer and use it in GitHub Desktop.
Save apogiatzis/00b047b6d6570d4e94b4ae00db6fc6e7 to your computer and use it in GitHub Desktop.
RSA Common modulus attack
import argparse
from fractions import gcd
parser = argparse.ArgumentParser(description='RSA Common modulus attack')
required_named = parser.add_argument_group('required named arguments')
required_named.add_argument('-n', '--modulus', help='Common modulus', type=long, required=True)
required_named.add_argument('-e1', '--e1', help='First exponent', type=long, required=True)
required_named.add_argument('-e2', '--e2', help='Second exponent', type=long, required=True)
required_named.add_argument('-ct1', '--ct1', help='First ciphertext', type=long, required=True)
required_named.add_argument('-ct2', '--ct2', help='Second ciphertext', type=long, required=True)
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)
def modinv(a, m):
g, x, y = egcd(a, m)
if g != 1:
raise ValueError('Modular inverse does not exist.')
else:
return x % m
def attack(c1, c2, e1, e2, N):
if gcd(e1, e2) != 1:
raise ValueError("Exponents e1 and e2 must be coprime")
s1 = modinv(e1,e2)
s2 = (gcd(e1,e2) - e1 * s1) / e2
temp = modinv(c2, N)
m1 = pow(c1,s1,N)
m2 = pow(temp,-s2,N)
return (m1 * m2) % N
def main():
args = parser.parse_args()
print '[+] Started attack...'
try:
message = attack(args.ct1, args.ct2, args.e1, args.e2, args.modulus)
print '[+] Attack finished!'
print '\nPlaintext message:\n%s' % format(message, 'x').decode('hex')
except Exception as e:
print '[+] Attack failed!'
print e.message
main()
@idarthjedi
Copy link

Good day! Made a few minor updates to your gist for Python 3, and added a few extra lines so it could be imported as a module instead of running as a command line. Can't PR, but passing along the URL in case you wanted to update.

https://gist.github.com/idarthjedi/1ab9c9ccd4803dbc40c801fbc5f2488f

Thanks a ton for your GIST!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment