Sometimes hacking requires doing things that, while possible to do with some algorithm, simply aren’t supported by any existing implementation. Usually for good reason. A good example of this that I’ve run into in the past is needing to initialize a hash algorithm with a specific state. There’s really not any reason to do this unless you’re trying to execute a length extension attack, and with the exception of HashPump (which was written specifically for that use case) I’m not aware of any library that supports it. I recently ran into this with problem with RSA.

A Quick Review of RSA Keys

RSA private keys consist of:

  • n, the composite modulus
  • e, the public exponent
  • d, the private exponent
  • some other values that can be ignored for now

In order to find d, φ(n) must first be computed by subtracting one from each of the prime factors of n and taking their product. Next d is calculated using the extended Euclidean algorithm to find the modular multiplicative inverse of e with respect to φ(n), such that demodφ(n)  ≡ 1. For the math to work out, e cannot share any factors with φ(n). The security of RSA relies on it being infeasible to find d without the prime factors of n. In practice, keys are normally generated by picking two random prime numbers of similar length, using 65537[1] for e, and computing everything else from there.

Readers already familiar with RSA may be wondering why I haven’t mentioned the customary names for the primes factors of np and q. That is because RSA works just fine with more than two primes. There was an offhand reference to this in the original RSA patent:

In alternative embodiments, the present invention may use a modulus n which is a product of three or more primes (not necessarily distinct[2]).

So-called “Multi-Prime RSA” allows faster computations with a given modulus size, but as far as I can tell it’s never seen much use. There’s been some interest as a performance optimization since CAs started requiring a minimum modulus size of 2048 bits, but wide support for ECDSA (which is much faster for private key operations) has relegated it to obscurity.

Shenanigans

In my previous post, “Stupid Certificate Tricks”, I showed how to create an RSA key with custom parameters in order to embed data in a certificate. That was a relatively simple case — PyCryptodome[3] has RSA.construct() which allows a key to be instantiated with arbitrary values for the modulus n, public exponent e, private exponent d, first prime p, and second prime q. Having to compute n and d even though they can be derived from the other three values is a mild annoyance, but in the end not a big deal. Unfortunately the API doesn’t allow specifying a third or further primes, which I found myself needing to do.

Serialization

When I went to research possible solutions, I made several surprising discoveries. First, support for multi-prime RSA had been added to Go’s standard library in 2011. Second, PKCS defined serialization of such keys in version 2.1, which was released in 2002. Finally, OpenSSL added support in version 1.1.1.

At this point, I was gritting my teeth a bit because like many TLS related data formats, RSA private keys use ASN.1. I like dealing with ASN.1 about as much as I like dealing with XML, which is to say, not at all. A bit of searching turned up pyasn1 which made things tolerable. To make the ASN.1 serialization work, all I had to do was translate the definitions from RFC 8017 into Python and write a bit of code to compute all of the derived values given a public exponent and list of primes.

mprsa.py
1import re
2import sys
3import gmpy2
4import base64
5import hashlib
6
7from functools import reduce
8
9from OpenSSL import crypto
10
11from pyasn1.type.univ import Sequence, SequenceOf, Integer
12from pyasn1.type.namedtype import NamedType, NamedTypes, OptionalNamedType
13from pyasn1.codec.der.encoder import encode as der_encode
14
15def product(items):
16 return reduce(lambda x, y: x * y, items)
17
18class RSAError(ValueError):
19 pass
20
21# https://tools.ietf.org/html/rfc8017#appendix-A.1.2
22class OtherPrimeInfo(Sequence):
23 componentType = NamedTypes(
24 NamedType('prime', Integer()),
25 NamedType('exponent', Integer()),
26 NamedType('coefficient', Integer())
27 )
28
29class OtherPrimeInfos(SequenceOf):
30 componentType = OtherPrimeInfo()
31
32class RSAPrivateKey(Sequence):
33 componentType = NamedTypes(
34 # Version ::= INTEGER { two-prime(0), multi(1) }
35 NamedType('version', Integer()),
36 NamedType('modulus', Integer()),
37 NamedType('publicExponent', Integer()),
38 NamedType('privateExponent', Integer()),
39 NamedType('prime1', Integer()),
40 NamedType('prime2', Integer()),
41 NamedType('exponent1', Integer()),
42 NamedType('exponent2', Integer()),
43 NamedType('coefficient', Integer()),
44 OptionalNamedType('otherPrimeInfos', OtherPrimeInfos())
45 )
46
47 # instantiate private key given public exponent and list of primes
48 def __init__(self, e, primes):
49 super().__init__()
50
51 if len(set(primes)) != len(primes):
52 raise RSAError('Cannot compute CRT coefficents with repeat primes')
53
54 primes = [2] + primes
55
56 # compute modulus
57 n = product(primes[1:])
58
59 primes_minus_one = [x - 1 for x in primes]
60 phi = product(primes_minus_one[1:])
61
62 if gmpy2.gcd(e, phi) != 1:
63 raise RSAError('e and phi(n) are not coprime')
64
65 # compute private exponent
66 d = int(gmpy2.invert(e, phi))
67
68 exponents = [d % x for x in primes_minus_one]
69
70 coefficients = [None] * len(primes)
71 # inv q mod p
72 coefficients[2] = int(gmpy2.invert(primes[2], primes[1]))
73 for i in range(3, len(primes)):
74 # inv product(r[1] ... r[i-1]) mod r[i]
75 coefficients[i] = int(gmpy2.invert(product(primes[1:i]), primes[i]))
76
77 # base set of rsa private key values
78 self['modulus'] = n
79 self['publicExponent'] = e
80 self['privateExponent'] = d
81 self['prime1'] = primes[1]
82 self['prime2'] = primes[2]
83 self['exponent1'] = exponents[1]
84 self['exponent2'] = exponents[2]
85 self['coefficient'] = coefficients[2]
86
87 # add values for additional primes if needed
88 if (len(primes) - 1) > 2:
89 self['version'] = 1
90 otherPrimeInfos = OtherPrimeInfos()
91 for i in range(3, len(primes)):
92 info = OtherPrimeInfo()
93 info['prime'] = primes[i]
94 info['exponent'] = exponents[i]
95 info['coefficient'] = coefficients[i]
96 otherPrimeInfos.setComponentByPosition(i - 3, info)
97
98 self['otherPrimeInfos'] = otherPrimeInfos
99 else:
100 self['version'] = 0
101
102 @property
103 def der(self):
104 return der_encode(self)
105
106 @property
107 def pem(self):
108 b64 = base64.b64encode(self.der).decode()
109 b64 = '\n'.join(b64[i:i+64] for i in range(0, len(b64), 64))
110 return '-----BEGIN {text}-----\n{b64}\n-----END {text}-----\n'.format(
111 b64=b64,
112 text='RSA PRIVATE KEY'
113 )
114
115if __name__ == '__main__':
116 e = int(sys.argv[1])
117 primes = list(map(int, sys.argv[2:]))
118 sys.stdout.write(RSAPrivateKey(e, primes).pem)

With that out of the way, I generated a key and tried to use it with OpenSSL. It did not work.

$ ./mprsa.py 16209469334791745752099089153245209595938905391366915442843655311870250775988478962443242925129138403268309023495340941270951066230818482657126058912138893504120575530462325274587 223 373 505511 62264393819 692091200694401 48054446430444121028200972020533400162078125396018622197185481602069377646593949231788063528654342806608883936083928621453549454859416361204853853702948393735291252921874962603428963373263708172690458493327748172536543917708281204835129658881247320770314746942732710565970028734766695760731222427123603048615247949771446031873465256836264652436820606092660156412961641977084159217469138549478995858415013921 > multi.key

$ openssl req -new -batch -key multi.key -out multi.csr -subj '/CN=test'
139698227354952:error:0D0DC006:asn1 encoding routines:ASN1_item_sign_ctx:EVP lib:crypto/asn1/a_sign.c:224:

This somewhat confusing error message seems to be the result of some hard coded limits in OpenSSL. It won’t work with keys having more than five primes at all, and has further restrictions in some cases depending on key size. Fortunately, it was trivial to patch these limits out.

openssl-manyprime.diff
1--- openssl-1.1.1c.orig/crypto/rsa/rsa_locl.h
2+++ openssl-1.1.1c/crypto/rsa/rsa_locl.h
3@@ -10,7 +10,7 @@
4 #include <openssl/rsa.h>
5 #include "internal/refcount.h"
6
7-#define RSA_MAX_PRIME_NUM 5
8+#define RSA_MAX_PRIME_NUM 64
9 #define RSA_MIN_MODULUS_BITS 512
10
11 typedef struct rsa_prime_info_st {
12--- openssl-1.1.1c.orig/crypto/rsa/rsa_mp.c
13+++ openssl-1.1.1c/crypto/rsa/rsa_mp.c
14@@ -111,5 +111,5 @@ int rsa_multip_cap(int bits)
15 if (cap > RSA_MAX_PRIME_NUM)
16 cap = RSA_MAX_PRIME_NUM;
17
18- return cap;
19+ return RSA_MAX_PRIME_NUM;
20 }

After installing a patched OpenSSL package, I tried again.

$ openssl req -new -batch -key multi.key -out multi.csr -subj '/CN=test'

$ openssl x509 -signkey multi.key -in multi.csr -req -days 999 -out multi.crt
Signature ok
subject=CN = test
Getting Private key

$ openssl verify -CAfile multi.crt multi.crt
multi.crt: OK

$ openssl rsa -noout -text -in multi.key
RSA Private-Key: (1472 bit, 6 primes)
modulus:
    00:aa:98:6c:52:74:cf:48:d3:13:3c:5d:42:35:c2:
    e0:d7:f2:62:ef:41:e5:bc:bc:bb:d5:44:28:b4:c2:
    51:52:3e:80:b4:92:17:e2:e0:e6:34:de:f5:37:95:
    7c:78:70:7a:71:a2:00:64:9f:7a:15:e0:d0:73:9e:
    b7:95:70:45:c8:6b:0f:01:2b:48:9a:97:2e:f2:78:
    e4:19:14:8f:53:82:59:5c:5d:7c:a7:fc:02:a5:a4:
    03:3a:7a:d7:40:e4:fc:6b:aa:e7:6f:a9:a9:2d:78:
    8e:33:c6:0b:c0:a6:b9:32:3e:47:a0:53:8d:91:45:
    2d:bd:72:ed:48:49:b6:5d:98:8d:f7:cd:2d:6b:2f:
    a5:02:96:b3:92:e6:77:11:52:6b:8a:f0:70:85:ba:
    ab:e2:73:58:6b:da:4b:21:84:7f:9f:05:b0:06:6f:
    9e:f8:83:24:31:f1:b7:95:6a:5c:32:22:14:2c:47:
    09:40:40:cb:bf
publicExponent:
    01:00:01:b7:02:e0:7a:d7:1c:d6:8e:e8:4a:58:f7:
    92:eb:c8:db:27:0b:0d:d2:25:61:27:18:1f:c2:1c:
    db:6f:38:46:92:3d:dc:a2:d3:e7:a2:76:8b:28:56:
    bd:25:97:c1:4d:43:c7:5d:d0:27:68:91:d3:b2:c5:
    98:0e:d6:57:c6:3e:a2:ba:a8:70:94:6b:30:77:db
privateExponent:
    00:8c:ea:a5:ac:1a:12:53:1b:28:5b:75:0a:85:cb:
    d0:4b:48:2c:cb:c3:16:bf:72:10:c0:6b:eb:8e:2b:
    1a:63:d3:d2:3f:4e:ac:72:04:8a:83:cc:e8:a8:05:
    e4:76:04:aa:64:3a:02:90:fa:f4:d2:6d:dc:5b:a7:
    ff:8e:a1:d9:6f:81:8a:56:d8:dc:cd:b0:64:ff:5f:
    73:b0:9d:fb:8b:72:91:39:e3:7f:84:5c:c3:d1:6e:
    4a:f0:be:7e:d0:40:31:e2:06:5f:5c:72:74:88:9b:
    ff:6c:1a:2e:1e:b4:b6:3c:9f:32:57:5c:96:10:67:
    c3:a6:7b:06:44:a3:ca:4a:2d:d4:76:f3:98:9e:61:
    f5:6e:55:8e:fa:d6:26:e8:b8:5d:d6:4a:9f:21:21:
    60:fc:59:d5:d6:cc:58:c1:9d:9f:89:d0:b3:f1:ad:
    b2:3d:d9:d0:45:b0:c1:3d:46:5e:e8:86:68:bb:02:
    5d:ce:5c:ac:53
prime1: 223 (0xdf)
prime2: 373 (0x175)
exponent1: 205 (0xcd)
exponent2: 319 (0x13f)
coefficient: 168 (0xa8)
prime3: 505511 (0x7b6a7)
exponent3: 201953 (0x314e1)
coefficient3: 141986 (0x22aa2)
prime4: 62264393819 (0xe7f3f405b)
exponent4: 34891590717 (0x81fb36c3d)
coefficient4: 15148084064 (0x386e56b60)
prime5: 692091200694401 (0x275740a2b6881)
exponent5: 552465485917523 (0x1f676e509ed53)
coefficient5: 78237913099958 (0x47282f04aeb6)
prime6:
    7d:25:8e:35:a8:57:b2:4b:8c:56:6b:67:85:e0:bd:
    03:61:a8:9c:ab:50:dc:a2:25:61:0f:c8:af:7d:0f:
    51:f3:24:11:26:3c:e9:2f:0f:c7:1e:9b:96:7e:d3:
    e0:56:38:1e:48:de:df:11:e6:bf:8e:86:8a:3a:d8:
    d4:ec:9b:a9:7e:b7:f2:84:0e:c3:f3:3c:e7:bb:69:
    fd:6e:db:1e:07:58:35:ae:de:b1:e6:82:12:61:73:
    87:18:e7:e8:d5:31:0f:59:f1:05:b7:32:21:ef:cd:
    28:6c:56:4e:fa:be:67:02:c2:2a:ed:24:8c:8d:56:
    d5:12:ee:49:05:74:a3:ac:7d:d1:01:07:25:c2:ff:
    ba:07:10:f5:26:14:41:07:8b:c8:e7:fc:96:d2:81:
    24:b6:3b:a5:7d:ae:15:f5:34:b9:73:b5:af:05:70:
    5e:69:d0:21
exponent6:
    54:7c:0f:4c:e7:e2:e5:2e:9d:54:dd:25:cf:39:f5:
    ca:a4:3a:90:a7:69:87:de:ad:9c:e8:be:e8:98:60:
    b0:22:0c:50:f3:74:25:9a:e4:04:b2:19:56:74:95:
    ed:0c:65:c2:a9:4b:dc:f2:87:d1:b3:59:c6:9f:28:
    88:a8:0a:85:61:53:46:90:b1:3c:14:9f:d4:33:b3:
    b0:05:27:a0:9c:93:c7:65:30:76:d7:59:01:8d:f1:
    b8:6d:c2:b4:34:1d:10:67:ef:b9:d0:f1:64:62:d9:
    8f:78:8a:f2:fc:84:9b:55:dd:dd:b6:a7:e3:21:df:
    00:9c:03:4c:89:0a:66:52:4f:0d:ae:d4:cc:2d:79:
    5b:81:f6:4a:bb:82:c8:bc:5c:51:fc:9f:91:d3:6f:
    ec:0e:43:af:98:3f:90:bb:8b:db:bd:de:b6:6e:04:
    c3:bc:73:93
coefficient6:
    4a:9c:ed:70:1f:c7:4b:f4:0b:e0:32:a5:db:f5:07:
    13:88:25:e9:c0:21:16:a2:09:5d:a6:db:00:c9:b2:
    5e:63:90:b7:a1:0f:aa:60:ed:39:fd:3a:2b:ab:21:
    c9:c8:d6:ab:e0:40:e9:29:fa:b4:84:11:6a:a8:f2:
    2f:b6:27:6b:5e:50:1a:4b:55:74:83:51:7c:83:91:
    bf:ce:46:ee:30:76:68:21:71:a3:9d:cd:04:54:41:
    24:98:5e:a4:61:c5:0f:b5:5a:24:f8:d1:3a:39:21:
    ce:af:a8:33:e0:0a:ee:dd:7d:21:b5:e6:e8:f8:32:
    5d:59:d9:09:5e:62:53:82:0c:e8:df:21:76:35:fe:
    47:d8:9e:56:e7:a5:2f:45:d2:e0:25:21:1e:da:63:
    ec:be:fa:f3:47:a0:0a:1b:7b:42:6c:9e:0f:b3:91:
    83:f6:38:3f

It works!

One thing I did notice when testing is that when using keys with particularly small primes, I’d sometimes get errors about “no inverse”. I’m not entirely sure of the cause, but I was able to get around it by retrying operations a few times.

[1]In hex, 65537 is 0x010001 which has only two bits set. RSA implementations use exponentiation by squaring which is faster when the exponent has few bits set. In my own testing, OpenSSL public key computations using 65535 (one bit shorter, but all bits set) as e took about 80% longer vs 65537. It’s even more efficient to use 3, but for historical reasons that is generally avoided.
[2]Practical implementations of RSA use optimizations based on the Chinese remainder theorem which do require the primes factors of n to be distinct.
[3]I originally used PyCrypto, but that project is no longer maintained. PyCryptodome was created to be a mostly drop-in replacement for it.