# Weak RSA - HTB

**Key-Words : RSA, Crypto**

The "Weak RSA" challenge involde deciphering en flag encrypted with RSA encryption.

-----BEGIN PUBLIC KEY-----
MIIBHzANBgkqhkiG9w0BAQEFAAOCAQwAMIIBBwKBgQMwO3kPsUnaNAbUlaubn7ip
4pNEXjvUOxjvLwUhtybr6Ng4undLtSQPCPf7ygoUKh1KYeqXMpTmhKjRos3xioTy
23CZuOl3WIsLiRKSVYyqBc9d8rxjNMXuUIOiNO38ealcR4p44zfHI66INPuKmTG3
RQP/6p5hv1PYcWmErEeDewKBgGEXxgRIsTlFGrW2C2JXoSvakMCWD60eAH0W2PpD
qlqqOFD8JA5UFK0roQkOjhLWSVu8c6DLpWJQQlXHPqP702qIg/gx2o0bm4EzrCEJ
4gYo6Ax+U7q6TOWhQpiBHnC0ojE8kUoqMhfALpUaruTJ6zmj8IA1e1M6bMqVF8sr
lb/N
-----END PUBLIC KEY-----

Public key seems to be short so we will try to break it. We will firstly extract information from this public key. For exemple N, e and other informations.
I wrote (me and my greatest friend chatGPT) a little python script to do this :

"""
Author : Malo DAMIEN

This program is used to extract informations from an RSA public key It's a .pub . Like modulus, exponent, etc.

Date : 27/12/2023
"""

import argparse
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives import serialization

def extract_rsa_public_key_info(public_key_pem):
    # Load the public key
    public_key = serialization.load_pem_public_key(public_key_pem, backend=default_backend())

    # Extract key components
    key_data = {
        'n': public_key.public_numbers().n,
        'e': public_key.public_numbers().e
    }

    return key_data

def main():
    parser = argparse.ArgumentParser(description="Extract information from an RSA public key.")
    parser.add_argument("-i", "--input", required=True, help="Path to the PEM file containing the RSA public key")
    parser.add_argument("-f", "--format", choices=['hex', 'long'], default='hex', help="Output format: hex or long (default: hex)")

    args = parser.parse_args()

    with open(args.input, "rb") as file:
        public_key_pem = file.read()

    # Extract information from the RSA public key
    public_key_info = extract_rsa_public_key_info(public_key_pem)

    # Print the extracted information in the specified format
    print("RSA Public Key Information:")
    if args.format == 'hex':
        print("Modulus (n):", hex(public_key_info['n']))
        print("Exponent (e):", hex(public_key_info['e']))
    elif args.format == 'long':
        print("Modulus (n):", public_key_info['n'])
        print("Exponent (e):", public_key_info['e'])

if __name__ == "__main__":
    main()


We need know to find if N is already factorised in the factordb database.


Fine ! It's the case, we can know compute $d$ with $p$ and $q$ from $N$.
We find out that $e$ is very large which can be a weakness because it can mean that d is very small.

When $e$ is chosen to optimize the speed of encryption operations, it can lead to vulnerability if the value of $d$ is small compared to n. The weakness lies in how easily Wiener's attack can determine $d$ when $e$ is large compared to $N$, even if $d$ itself is small. It's also the case when $p$ and $q$ are very close. (Here they seems to be close enough and moreover $e$ is very big).

We can therefore perform a Wiener Attack on this key.

Here is a code to solve the challenge using the librairy pycryptodome.

"""
Soluce to the challenge
"""

from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long, long_to_bytes
import owiener


def get_pubkey(f):
    with open(f) as pub:
        key = RSA.importKey(pub.read())
    return (key.n, key.e)


def get_ciphertext(f):
    with open(f, 'rb') as cipher:
        return bytes_to_long(cipher.read())


def decrypt_rsa(N,e,d,ct):
    pt = pow(ct, d, N)
    return long_to_bytes(pt)


N, e = get_pubkey('./key.pub')

d = owiener.attack(e, N)

ct = get_ciphertext('./flag.enc')
pt = decrypt_rsa(N,e,d,ct)
print(f'pt = {str(pt)}')

## Wiener Attack Precision


FLAG : `HTB{s1mpl3_Wi3n3rs_4tt4ck}`