RSA Baby
Puntuación: 100
El enunciado de este reto indica lo siguiente:
RSA is your quarantine’s friend!
-
Download: https://drive.google.com/file/d/1eV6Xs-_yEPgi03gWKYgCw2tOTEg8pxoI/view?usp=sharing
-
Challenge created by @javierprtd
En este reto nos dan los valores “n, e1, e2, c1 y c2”, los cuales se corresponden a un cifrado RSA de la siguiente manera:
- n: módulo común entre las dos claves públicas
- e1: exponente de la clave pública 1
- e2: exponente de la clave pública 2
- c1: mensaje cifrado con la clave 1
- c2: mensaje cifrado con la clave 2
|
1 2 3 4 5 |
n: 139139098166563368793906426353584775685986156985503895898108450666153804152721077328595298405359402968586164698349127474583831260369056674398122221948323174927823244488759235828048733639655945179009496153393829487742364880448642168094375012523825513069073691277215422154080122721414171233541059159461497574851 e1: 8589547526045561461552680248279757835979283889671962732842177455697481270376746567989084136626965959183030099272662143191917717068451310686662922269968037 e2: 1550875426281080713285640421891864359643668278531602865211049325478612197772168543099328132747062677256718488137967707434694189218634201660188716505159465 c1: 36251028222184669113487409017454975826565106104917435244458509025325597595097437837292486054294655693705631371301937875354932194238774646471806718003961847732817524682493697446263462385101163784046225206169381882321268194820701612704489320707217757417267296259559235617734319007884212443563740615946094992859 c2: 15688769307556061961218947783212296596344168555685824671642275978089568687312912139032947498393471032926950577032514983014105921115080590723699988614214232859981728991429978617821297278877767993295441070537327281816259747634098763766785395724275437311610210946257742159892825472332345447909363995349523623705 |
En este caso vemos que es un mismo mensaje cifrado pero con dos claves diferentes que comparten el mismo módulo.
Crearemos entonces un script sabiendo que podemos obtener el mensaje en claro de los dos textos iguales cifrados con el mismo módulo pero con un exponente diferente si el máximo común divisor de los mismos es 1.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
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('-c1', '--c1', help='First ciphertext', type=long, required=True) required_named.add_argument('-c2', '--c2', 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.c1, args.c2, 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() |
Ejecutamos nuestro script con los valores del reto:
|
1 2 3 4 5 6 7 8 9 10 |
python rsa.py -n "139139098166563368793906426353584775685986156985503895898108450666153804152721077328595298405359402968586164698349127474583831260369056674398122221948323174927823244488759235828048733639655945179009496153393829487742364880448642168094375012523825513069073691277215422154080122721414171233541059159461497574851" \ -e1 "8589547526045561461552680248279757835979283889671962732842177455697481270376746567989084136626965959183030099272662143191917717068451310686662922269968037" \ -e2 "1550875426281080713285640421891864359643668278531602865211049325478612197772168543099328132747062677256718488137967707434694189218634201660188716505159465" \ -c1 "36251028222184669113487409017454975826565106104917435244458509025325597595097437837292486054294655693705631371301937875354932194238774646471806718003961847732817524682493697446263462385101163784046225206169381882321268194820701612704489320707217757417267296259559235617734319007884212443563740615946094992859" \ -c2 "15688769307556061961218947783212296596344168555685824671642275978089568687312912139032947498393471032926950577032514983014105921115080590723699988614214232859981728991429978617821297278877767993295441070537327281816259747634098763766785395724275437311610210946257742159892825472332345447909363995349523623705" [+] Started attack... [+] Attack finished! Plaintext message: flag{C0mm0n_m0duluS_4tt4cK_f0R_k1ll_COVID-19} |
Obteniendo con ello nuestra flag:
|
1 |
flag{C0mm0n_m0duluS_4tt4cK_f0R_k1ll_COVID-19} |
Puedes ver el resto de writeups en este enlace.
