Crypto Redacted RSA 1#

I have a RSA private key, but it is partially redacted. Can you recover that? Run openssl pkeyutl -decrypt -inkey key-recovered.pem -in encrypted.txt -out plaintext.txt after you have recovered the key.

First, you turn the Pem to Hex using cyberchef.

Basically, only the bottom part of it was redacted. So we only need to understand the whole structure:

Structure of PEM in DER

ASN.1 Cheatsheets#

Format: (type) (byte size @ length in bytes)#

NOTE
1 byte = 2 Hex

Type:

02: INTEGER
04: OCTET STRING (a sequence of bytes)
06: OBJECT IDENTIFIER (like a unique name)
05: NULL (no value)
30: SEQUENCE (a collection of items)

Byte Size @ length:

82: the next 2 bytes are the length
03: 3 bytes
01: 1 byte

The first column means:

30: structure type (the whole PEM)
82: next 2 bytes are the length
0929: length in hex value

The second column means:

02: integer type
01: next 1 byte is the length
00: length 0

Starting from the third column onwards, shows the N, e, d, p, q ,… and so on

02: integer type
82: next 2 bytes are the length
0201: decimal 513 bytes (1026 hexa digits)
009d47... after 0201 (513 bytes) is the N modular

After I extracted the data, I found the complete of n, e, d:

1
n = {LARGE_HEX}
2
e = 01001 (65537 normal value)
3
d = {LARGE_HEX}

after this just run this code to generate a pem file

1
from Crypto.PublicKey import RSA
2

3
n = int("YOUR_N_VALUE", 16)
4
e = int("YOUR_E_VALUE", 16)
5
d = int("YOUR_D_VALUE", 16)
6

7
key = RSA.construct((n, e, d))
8

9
with open("key-recovered.pem", "wb") as f:
10
    f.write(key.export_key())

alternative without pem file (by neno)

1
Nstr="" # N in string
2
dstr="" # d in string
3
encrypted_hex="" # the encrypted.txt in hex
4

5
import base64
6
from Crypto.PublicKey import RSA
7
from Crypto.Util import number
8

9
ciphertext = base64.b64decode(encrypted_hex)
10
N = int(Nstr, 16)
11
d = int(dstr, 16)
12

13
ciphertext_int = number.bytes_to_long(ciphertext)
14

15
# Perform RSA decryption: M = C^d % N
16
decrypted_int = pow(ciphertext_int, d, N)
17

18
# Convert the decrypted integer back to a string
19
decrypted_message = number.long_to_bytes(decrypted_int).decode('latin-1')
20

21
print("Decrypted Message:", decrypted_message)

Crypto Redacted RSA 2#

This one is same as RSA 1 but the redaction covered up the middle and the bottom (only parts of it showed).

Same strategy, read the Pem in Hex with cyberchef and extract the data:

Here’s some useful data extracted:

1
n = {LARGE_NUMBER}
2
e = {010001} #65537
3
dp = d mod (q-1) = {LARGE_NUMBER}

So, for a valid PEM, I need to get p or q or d.

How can we find it without large computing power?#

Welp, time to google! I found this stackexchange forum particularly helpful for this.

So, chatgpt it, and here’s the code:

1
import random
2
from math import gcd
3
from sympy import mod_inverse  # To compute modular inverse
4

5
def hex_to_int(hex_value):
6
    """
7
    Convert a hex string to an integer.
8
    """
9
    return int(hex_value, 16)
10

11
def find_dp(n, e, dp):
12
    """
13
    Find the factorization of n and recover d using dp.
14
    """
15
    # Choose a random r
16
    r = random.randint(2, n - 1)
17

18
    # Compute r^(e * dp) mod n
19
    r_exp = pow(r, e * dp, n)
20

21
    # Compute gcd of n and (r_exp - r)
22
    factor = gcd(n, r_exp - r)
23

24
    if factor == 1 or factor == n:
25
        print("Failed to find a factor. Try again.")
26
        return None
27

28
    # Factorization of n: p and q
29
    p = factor
30
    q = n // p
31

32
    # Recover private key components
33
    phi = (p - 1) * (q - 1)
34
    d = mod_inverse(e, phi)
35

36
    return d, p, q
37

38
# Example inputs (hexadecimal values)
39
n_hex = "8D23"
40
e_hex = "11"
41
dp_hex = "0D"
42

43
n = hex_to_int(n_hex)
44
e = hex_to_int(e_hex)
45
dp = hex_to_int(dp_hex)
46

47
# Find d and factors
48
result = find_dp(n, e, dp)
49
if result:
50
    d, p, q = result
51
    print(f"Recovered d: {hex(d)}")
52
    print(f"Factors p: {hex(p)}, q: {hex(q)}")