https://github.com/Ganapati/RsaCtfTool
kali@kali:~/0.htb/challenges/Crypto/TwoForOne$ RsaCtfTool/RsaCtfTool.py --public "*.pem" --isroca
private argument is not set, the private key will not be displayed, even if recovered.
[-] Details for key2.pem:
[-] Public key key2.pem: is not roca, you are safe
[-] Details for key1.pem:
[-] Public key key1.pem: is not roca, you are safe
kali@kali:~/0.htb/challenges/Crypto/TwoForOne$
kali@kali:~/0.htb/challenges/Crypto/TwoForOne$ RsaCtfTool/RsaCtfTool.py --public "*.pem" --dumpkey
private argument is not set, the private key will not be displayed, even if recovered.
Details for key2.pem:
n: 25080356853331150673712092961488349508728123694382279186941974911344272809718201683391687288116618021523872262260746884803456249468108932413753368793568123710905490623939699616018064364038794824072468125668702688048418916712950393799664781694224559810656290997284081084848717062228887604668548576609649709572412523306016494962925450783098637867249337121156908328927249731928363360657779226929980928871118145919627109584218577535657544952661333527174942990937484743860494188129607347202336812042045820577108243818426559386634634103676467773122325120858908782192357380855678371737765634819794619802582481594876770433687
e: 343223
Details for key1.pem:
n: 25080356853331150673712092961488349508728123694382279186941974911344272809718201683391687288116618021523872262260746884803456249468108932413753368793568123710905490623939699616018064364038794824072468125668702688048418916712950393799664781694224559810656290997284081084848717062228887604668548576609649709572412523306016494962925450783098637867249337121156908328927249731928363360657779226929980928871118145919627109584218577535657544952661333527174942990937484743860494188129607347202336812042045820577108243818426559386634634103676467773122325120858908782192357380855678371737765634819794619802582481594876770433687
e: 65537
kali@kali:~/0.htb/challenges/Crypto/TwoForOne$ openssl rsa -pubin -inform PEM -text -noout <key1.pem
RSA Public-Key: (2048 bit)
Modulus:
00:c6:ac:b8:df:48:6e:66:71:d4:a5:56:48:03:e1:
c3:21:4a:8e:27:4d:e0:ac:00:43:ec:28:c8:58:9f:
37:7c:7e:8d:30:8b:c3:e3:02:85:03:84:34:4b:a7:
98:88:85:62:0a:41:8e:6a:d9:55:57:82:84:fc:04:
f2:89:f1:26:b3:8a:01:81:62:51:ce:f9:a1:4f:d4:
c2:49:d9:6b:69:08:7f:a9:1b:2e:1a:db:dc:80:cb:
96:ff:0c:cb:61:29:d8:f6:73:7d:a8:50:c4:51:f2:
ed:3f:6c:b6:1c:36:89:1d:c9:24:d0:ab:28:f2:6a:
df:0e:d3:57:ce:84:8d:02:ff:e0:09:12:71:4c:cf:
63:72:c1:f4:10:80:e8:67:47:a0:30:3e:b5:cd:f6:
ce:91:2f:11:44:fd:4f:55:74:3c:79:68:75:a1:4f:
df:f8:f8:b6:62:15:0c:56:be:58:b0:92:39:77:1d:
c4:4d:96:90:79:c4:ad:8f:d9:93:bc:63:0b:78:55:
d2:e0:2e:8b:e1:68:24:dc:d5:ab:38:13:23:1c:17:
31:11:0a:8b:d0:28:d7:a1:df:ab:89:2e:75:29:45:
57:ba:fc:71:ae:af:5e:48:db:02:67:a6:db:63:d3:
50:f9:95:06:8e:e1:ca:d6:d3:2d:f1:1a:49:bd:24:
ba:97
Exponent: 65537 (0x10001)
kali@kali:~/0.htb/challenges/Crypto/TwoForOne$ openssl rsa -pubin -inform PEM -text -noout <key2.pem
RSA Public-Key: (2048 bit)
Modulus:
00:c6:ac:b8:df:48:6e:66:71:d4:a5:56:48:03:e1:
c3:21:4a:8e:27:4d:e0:ac:00:43:ec:28:c8:58:9f:
37:7c:7e:8d:30:8b:c3:e3:02:85:03:84:34:4b:a7:
98:88:85:62:0a:41:8e:6a:d9:55:57:82:84:fc:04:
f2:89:f1:26:b3:8a:01:81:62:51:ce:f9:a1:4f:d4:
c2:49:d9:6b:69:08:7f:a9:1b:2e:1a:db:dc:80:cb:
96:ff:0c:cb:61:29:d8:f6:73:7d:a8:50:c4:51:f2:
ed:3f:6c:b6:1c:36:89:1d:c9:24:d0:ab:28:f2:6a:
df:0e:d3:57:ce:84:8d:02:ff:e0:09:12:71:4c:cf:
63:72:c1:f4:10:80:e8:67:47:a0:30:3e:b5:cd:f6:
ce:91:2f:11:44:fd:4f:55:74:3c:79:68:75:a1:4f:
df:f8:f8:b6:62:15:0c:56:be:58:b0:92:39:77:1d:
c4:4d:96:90:79:c4:ad:8f:d9:93:bc:63:0b:78:55:
d2:e0:2e:8b:e1:68:24:dc:d5:ab:38:13:23:1c:17:
31:11:0a:8b:d0:28:d7:a1:df:ab:89:2e:75:29:45:
57:ba:fc:71:ae:af:5e:48:db:02:67:a6:db:63:d3:
50:f9:95:06:8e:e1:ca:d6:d3:2d:f1:1a:49:bd:24:
ba:97
Exponent: 343223 (0x53cb7)
kali@kali:~/0.htb/challenges/Crypto/TwoForOne$ Common Modulus Attack (same n)
https://gist.github.com/ofaurax/6103869014c246f962ab30a513fb5b49
python3 241.py
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
import sys,gmpy,base64
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 Exception('modular inverse does not exist')
else:
return x % m
def pad_even(x):
return ('', '0')[len(x)%2] + x
def CipherB2n(c):
c = base64.b64decode(c)
temp = ''
for i in c:
temp += pad_even(str(hex(i))[2:])
temp = eval('0x'+temp)
return (temp)
def CipherN2b(m):
hex_m=hex(m)[2:]
if hex_m[-1] == 'L' :
hex_m=hex_m[:-1]
return bytes.fromhex(hex_m).decode('utf-8')
if __name__ == '__main__':
sys.setrecursionlimit(1000000)
e1 = 65537
e2 = 343223
s = egcd(e1, e2)
s1 = s[1]
s2 = s[2]
c1 = 'RBVdQw7Pllwb42GDYyRa6ByVOfzRrZHmxBkUPD393zxOcrNRZgfub1mqcrAgX4PAsvAOWptJSHbrHctFm6rJLzhBi/rAsKGboWqPAWYIu49Rt7Sc/5+LE2dvy5zriAKclchv9d+uUJ4/kU/vcpg2qlfTnyor6naBsZQvRze0VCMkPvqWPuE6iL6YEAjZmLWmb+bqO+unTLF4YtM1MkKTtiOEy+Bbd4LxlXIO1KSFVOoGjyLW2pVIgKzotB1/9BwJMKJV14/+MUEiP40ehH0U2zr8BeueeXp6NIZwS/9svmvmVi06Np74EbL+aeB4meaXH22fJU0eyL2FppeyvbVaYQ=='
c2 ='TSHSOfFBkK/sSE4vWxy00EAnZXrIsBI/Y6mGv466baOsST+qyYXHdPsI33Kr6ovucDjgDw/VvQtsAuGhthLbLVdldt9OWDhK5lbM6e0CuhKSoJntnvCz7GtZvjgPM7JDHQkAU7Pcyall9UEqL+W6ZCkiSQnK+j6QB7ynwCsW1wAmnCM68fY2HaBvd8RP2+rPgWv9grcEBkXf7ewA+sxSw7hahMaW0LYhsMYUggrcKqhofGgl+4UR5pdSiFg4YKUSgdSw1Ic/tug9vfHuLSiiuhrtP38yVzazqOZPXGxG4tQ6btc1helH0cLfw1SCdua1ejyan9l1GLXsAyGOKSFdKw=='
c1 = CipherB2n(c1)
c2 = CipherB2n(c2)
n = 25080356853331150673712092961488349508728123694382279186941974911344272809718201683391687288116618021523872262260746884803456249468108932413753368793568123710905490623939699616018064364038794824072468125668702688048418916712950393799664781694224559810656290997284081084848717062228887604668548576609649709572412523306016494962925450783098637867249337121156908328927249731928363360657779226929980928871118145919627109584218577535657544952661333527174942990937484743860494188129607347202336812042045820577108243818426559386634634103676467773122325120858908782192357380855678371737765634819794619802582481594876770433687
if s1<0:
s1 = - s1
c1 = modinv(c1, n)
elif s2<0:
s2 = - s2
c2 = modinv(c2, n)
m=(pow(c1,s1,n)*pow(c2,s2,n)) % n
print(m)
print(CipherN2b(m))kali@kali:~/0.htb/challenges/Crypto/TwoForOne$ python3 241.py
29754482138600667824873548828684976503132905299031678355938493565
HTB{C0mmon_M0dUlu5S_1S_b4D}
https://github.com/HexPandaa/RSA-Common-Modulus-Attack/blob/master/rsa-cm.py
kali@kali:~/0.htb/challenges/Crypto/TwoForOne$ python3 rsa-cm.py -c1 message1 -c2 message2 -k1 key1.pem -k2 key2.pem
[+] Recovered message:
29754482138600667824873548828684976503132905299031678355938493565
[+] Recovered bytes:
b'HTB{C0mmon_M0dUlu5S_1S_b4D}'
#getflag.py
from Crypto.Util.number import *
from Crypto.PublicKey import RSA
import base64
import gmpy2
with open('key1.pem') as f:
pk1 = RSA.import_key(f.read())
with open('key2.pem') as f:
pk2 = RSA.import_key(f.read())
with open('message1') as f:
c1 = base64.b64decode(f.read())
c1 = bytes_to_long(c1)
with open('message2') as f:
c2 = base64.b64decode(f.read())
c2 = bytes_to_long(c2)
g, a1, a2 = gmpy2.gcdext(pk1.e, pk2.e)
m = pow(c1, a1, pk1.n) * pow(c2, a2, pk2.n) % pk1.n
print(long_to_bytes(m))#rsa-cm.py
#!/bin/env python3
# -*- coding: utf-8 -*-
__author__ = "HexPandaa"
from Crypto.PublicKey import RSA
from Crypto.Util.number import (
long_to_bytes,
bytes_to_long,
GCD
)
import gmpy2
from base64 import b64decode
import argparse
import sys
def parse_args():
parser = argparse.ArgumentParser(description="A simple script to perform RSA common modulus attacks.",
epilog="More info at https://github.com/HexPandaa/RSA-Common-Modulus-Attack/")
parser.add_argument("-c1", type=argparse.FileType("r"), metavar="ciphertext1", required=True,
help="The first ciphered message")
parser.add_argument("-c2", type=argparse.FileType("r"), metavar="ciphertext2", required=True,
help="The second ciphered message")
parser.add_argument("-k1", type=argparse.FileType("rb"), metavar="pubkey1", required=True,
help="The first public key")
parser.add_argument("-k2", type=argparse.FileType("rb"), metavar="pubkey2", required=True,
help="The second public key")
parser.add_argument("-o", type=argparse.FileType("wb"), metavar="outfile", required=False,
help="Output file")
args = parser.parse_args()
return args
# Source: https://crypto.stackexchange.com/a/60404
def bytes_to_integer(data):
output = 0
size = len(data)
for index in range(size):
output |= data[index] << (8 * (size - 1 - index))
return output
def integer_to_bytes(integer, _bytes):
output = bytearray()
for byte in range(_bytes):
output.append((integer >> (8 * (_bytes - 1 - byte))) & 255)
return output
# Source: https://github.com/ashutosh1206/Crypton/blob/master/RSA-encryption/Attack-Common-Modulus/exploit.py
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)
# Calculates a^{b} mod n when b is negative
def neg_pow(a, b, n):
assert b < 0
assert GCD(a, n) == 1
res = int(gmpy2.invert(a, n))
res = pow(res, b*(-1), n)
return res
# e1 --> Public Key exponent used to encrypt message m and get ciphertext c1
# e2 --> Public Key exponent used to encrypt message m and get ciphertext c2
# n --> Modulus
# The following attack works only when m^{GCD(e1, e2)} < n
def common_modulus(e1, e2, n, c1, c2):
g, a, b = egcd(e1, e2)
if a < 0:
c1 = neg_pow(c1, a, n)
else:
c1 = pow(c1, a, n)
if b < 0:
c2 = neg_pow(c2, b, n)
else:
c2 = pow(c2, b, n)
ct = c1*c2 % n
m = int(gmpy2.iroot(ct, g)[0])
return m
def main(args):
pubkey1 = RSA.import_key(args.k1.read())
pubkey2 = RSA.import_key(args.k2.read())
c1 = b64decode(args.c1.read())
c1 = bytes_to_long(c1)
c2 = b64decode(args.c2.read())
c2 = bytes_to_long(c2)
# We first check that the modulus N of both public keys are equal
if pubkey1.n != pubkey2.n:
sys.stderr.write("[ERROR] The modulus of both public keys must be the same\n")
sys.exit(1)
if GCD(pubkey1.e, pubkey2.e) != 1:
sys.stderr.write("[ERROR] The greatest common denominator between the exponent of each keys should be 1\n")
sys.exit(2)
deciphered_message = common_modulus(
pubkey1.e,
pubkey2.e,
pubkey1.n,
c1,
c2
)
deciphered_bytes = long_to_bytes(deciphered_message)
print("[+] Recovered message:")
print(deciphered_message)
print("[+] Recovered bytes:")
print(deciphered_bytes)
if args.o:
args.o.write(deciphered_bytes)
if __name__ == '__main__':
args = parse_args()
main(args)