22-11-01-Qq

Posted on Edited on In Symbols count in article: 7.2k Reading time ≈ 7 mins.

The problem is mainly based on the backdoor. In RSA library, it has the CVE of CVE-2017-15361.In this case, we can calculate the prime which is likely random with the equation that:
$$
Prime = k \times M + (65537^{a} \mod M)
$$
It means that produce the list of primes and make them to collide， which satisfy the condition, thus output the target prime.

Also，the PKI system has different standards， we make some distinctions between different standards.

RSA Backdoor

reference: https://asecuritysite.com/encryption/copper

description

In RSALib, the prime is produced by the equaction:
$$
Prime = k \times M + 65537^{a} \mod M
$$
which means that the $M$ is the multiplication of the generated primes.
$$
M = \prod_{i=1}^{n}{P_{i}}= P_{1} \times P_{2} \times \cdots \times P_{n}
$$
$M$ must be large and is around the same size of they generated. The weakness is the $k$ and $a$ are relatively small values. The entropy is also must drop.

The problem is common provided with $c$, $e$ and $n$, and just do the commandRSA_Backdoor(n). If the problems satisfy the conditions, the function will return the $p$ and the $q$.

Openssl

relate to the PKI system.

generate

In kali, you can directly input the command that openssl.

1
2
3
4
5
6
7
8
9
openssl genrsa -out [pri].pem 1024
openssl rsa -in [pri].pem -pubout -out [pub].pem

## if needs to encrypto, like AES or anything else
openssl genrsa [-aes256 -passout pass:111111] -out [pri].key 2048
openssl rsa -in [pri].key -pubout -out [pri].key
Enter pass phrase for [pri].key:
# openssl rsa -in [pri].key -passin pass:111111 -pubout -out [pub].key
writing RSA key

If in python, we can import something to ensure the same consequence. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.PublicKey import RSA
# RSA.generate(bits, randfunc = None, e = 65537)
# - bits: bit_length
# - randfunc: Crypto.Random.get_random_bytes()
# - e(int): odd, common is 65537
rsa = rsa.generate(1024)
# export prikey
pri = rsa.exportKey()
# export pubkey
pub = rsa.publickey().exportKey()
# or write in the file
with open('pri.pem', 'wb') as f1:
    f1.write(pri)
with open('pub.pem', 'wb') as f2:
    f2.write(pub)

reverse

1
2
3
4
5
6
7
8
9
10
11
# PKCS1 -> PKCS8 privatekey
openssl pkcs8 -topk8 -inform PEM -in rsa_pri.pem -outform PEM -nocrypt -out rsa_pri_pkcs8.pem

# PKCS8 -> PKCS1 privatekey
openssl rsa -inform PEM -in rsa_pri_pkcs8.pem -outform PEM -out rsa_pri_pkcs1.pem

# PKCS8 -> PKCS1 publickey
openssl rsa -pubin -in rsa_pub.pem -RSAPublicKey_out -out rsa_pub_pkcs1.pem

# PKCS1 -> PKCS8 publickey
openssl rsa -RSAPublicKey_in -in rsa_pub_pkcs1.pem -pubout -out rsa_pub_pkcs8.pem

Key_Differences

PKCS#8

1
2
3
4
5
6
7
8
9
10
11
# pubkey
-----BEGIN PUBLIC KEY-----
-----END PUBLIC KEY-----

# prikey
-----BEGIN PRIVATE KEY-----
-----END PRIVATE KEY-----

# prikey encrypted
-----BEGIN PRIVATE KEY-----
-----END PRIVATE KEY-----

PKCS#1

import rsa

the default is PKCS#1

1
2
3
4
5
6
7
# pubkey
-----BEGIN RSA PUBLIC KEY-----
-----END RSA PUBLIC KEY-----

# prikey
-----BEGIN RSA PRIVATE KEY-----
-----END RSA PRIVATE KEY-----

Rsatool

GitHub - ius/rsatool: rsatool can be used to calculate RSA and RSA-CRT parameters

requirements

  • python3.7+
  • pyasn1
  • gmpy2

usage

pem

1
2
python3 rsatool.py -f PEM -o key.pem -n [n] -d [d]
python3 rsatool.py -f PEM -o private.pem -p [p] -q [q] -e [e]

der

1
python3 rsatool.py -f DER -o key.der -p [p] -q [q]

Pem in RSA

The pem can be used in different ways in RSA.

One is to extract the $n$ and the $e$—— when you get $p$, $q$ from the $n$, we can change flag.enc to $c$ by using the function bytes_to_long().

The other way is also extract the $n$ and the $e$ ——however, we MUST construct the primes and others into the pri.pem. Using the pri.pem，and we can decrypt the flag.enc to get the message.

[1101]qq

mainly using bytes_to_long()

flag.enc

1
CwhE2kUKvphGegBRgnZeM8iE2oTPfmzMYfL4cO262NkQpId+JzH4pEyiS3cdyhDRsU+huX9cnIE=

pub_key.pem

1
2
3
4
-----BEGIN PUBLIC KEY-----
MFMwDQYJKoZIhvcNAQEBBQADQgAwPwI4EkoKC0EfUXgDvsQUYRI+j0/XPrqQxHJ+
v3CKL9WVp5SMk0Njud03to6sxuvPt93fSGHkAsW+wHsCAwEAAQ==
-----END PUBLIC KEY-----

exp.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.PublicKey import RSA
from Crypto.Util.number import *
import gmpy2
import base64

with open('pub_key.pem', 'rb') as f:
    pub = RSA.import_key(f.read())

# print(pub.e)
# print(pub.n)
with open('flag.enc', 'rb') as f:
    cipher = base64.b64decode(f.read())
c = bytes_to_long(cipher)
e = 65537
n = 51926993165717444667250925590498598946377319881662556610174970468991791873398735735101740226707561968771963673353253102616246155657339
p, q = RSA_Backdoor(n)
N = (p-1) * (q-1)
d = int(gmpy2.invert(e, N))
m = pow(c, d, n)
print(m)
print(long_to_bytes(m).decode())
# 2761328357323929478367647741211050583178552594955214217850793389028221
# flag{We@k_Pr1me_1s_d@nger0us}

[ACTF2018]可怜的RSA

construct to private key

flag.enc

1
GVd1d3viIXFfcHapEYuo5fAvIiUS83adrtMW/MgPwxVBSl46joFCQ1plcnlDGfL19K/3PvChV6n5QGohzfVyz2Z5GdTlaknxvHDUGf5HCukokyPwK/1EYU7NzrhGE7J5jPdi0Aj7xi/Odxy0hGMgpaBLd/nL3N8O6i9pc4Gg3O8soOlciBG/6/xdfN3SzSStMYIN8nfZZMSq3xDDvz4YB7TcTBh4ik4wYhuC77gmT+HWOv5gLTNQ3EkZs5N3EAopy11zHNYU80yv1jtFGcluNPyXYttU5qU33jcp0Wuznac+t+AZHeSQy5vk8DyWorSGMiS+J4KNqSVlDs12EqXEqqJ0uA==

public.key

1
2
3
4
5
6
7
8
9
-----BEGIN PUBLIC KEY-----
MIIBJDANBgkqhkiG9w0BAQEFAAOCAREAMIIBDAKCAQMlsYv184kJfRcjeGa7Uc/4
3pIkU3SevEA7CZXJfA44bUbBYcrf93xphg2uR5HCFM+Eh6qqnybpIKl3g0kGA4rv
tcMIJ9/PP8npdpVE+U4Hzf4IcgOaOmJiEWZ4smH7LWudMlOekqFTs2dWKbqzlC59
NeMPfu9avxxQ15fQzIjhvcz9GhLqb373XDcn298ueA80KK6Pek+3qJ8YSjZQMrFT
+EJehFdQ6yt6vALcFc4CB1B6qVCGO7hICngCjdYpeZRNbGM/r6ED5Nsozof1oMbt
Si8mZEJ/Vlx3gathkUVtlxx/+jlScjdM7AFV5fkRidt0LkwosDoPoRz/sDFz0qTM
5q5TAgMBAAE=
-----END PUBLIC KEY-----

exp.py

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
from Crypto.PublicKey import RSA
from base64 import *
import binascii
from Crypto.Util.number import *
import gmpy2
from Crypto.Cipher import PKCS1_OAEP

"""
2. public.key：rb->RSA.import_key->e,n
3. construct to privatekey
    1. (n,e,d,(p),(q)) to save
    2. RSA.construct() to construct
    3. 2.exportKey() import
    4. RSA.importKey() export
    5. PKCS1_OAEP.new()  -> important!
4. d by using invert(), and int(d) to get integer
5. use private key to decrypt
"""
with open('public.key', 'rb') as f:
    pub = RSA.import_key(f.read())
e = pub.e
n = pub.n
# e = 65537
# n = 79832181757332818552764610761349592984614744432279135328398999801627880283610900361281249973175805069916210179560506497075132524902086881120372213626641879468491936860976686933630869673826972619938321951599146744807653301076026577949579618331502776303983485566046485431039541708467141408260220098592761245010678592347501894176269580510459729633673468068467144199744563731826362102608811033400887813754780282628099443490170016087838606998017490456601315802448567772411623826281747245660954245413781519794295336197555688543537992197142258053220453757666537840276416475602759374950715283890232230741542737319569819793988431443

# yafu-x64/factordb.com
p = 3133337
q = 25478326064937419292200172136399497719081842914528228316455906211693118321971399936004729134841162974144246271486439695786036588117424611881955950996219646807378822278285638261582099108339438949573034101215141156156408742843820048066830863814362379885720395082318462850002901605689761876319151147352730090957556940842144299887394678743607766937828094478336401159449035878306853716216548374273462386508307367713112073004011383418967894930554067582453248981022011922883374442736848045920676341361871231787163441467533076890081721882179369168787287724769642665399992556052144845878600126283968890273067575342061776244939
N = (p-1) * (q-1)
d = int(gmpy2.invert(e, N))
with open('flag.enc', 'r') as f:
    cipher = b64decode(f.read())
    # print(c)
con = RSA.construct((n, e, d, p, q))
pri = PKCS1_OAEP.new(RSA.importKey(con.exportKey()))
m = pri.decrypt(cipher)
print(m)
# b'afctf{R54_|5_$0_B0rin9}'
-------------THE END-------------