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 e⋅φ(n) mod ≡ 1 is satisfied. 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 n — p 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]).
Socalled “MultiPrime 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 multiprime 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  

1  import re 
2  import sys 
3  import gmpy2 
4  import base64 
5  import hashlib 
6 

7  from functools import reduce 
8 

9  from OpenSSL import crypto 
10 

11  from pyasn1.type.univ import Sequence, SequenceOf, Integer 
12  from pyasn1.type.namedtype import NamedType, NamedTypes, OptionalNamedType 
13  from pyasn1.codec.der.encoder import encode as der_encode 
14 

15  def product(items): 
16  return reduce(lambda x, y: x * y, items) 
17 

18  class RSAError(ValueError): 
19  pass 
20 

21  # https://tools.ietf.org/html/rfc8017#appendixA.1.2 
22  class OtherPrimeInfo(Sequence): 
23  componentType = NamedTypes( 
24  NamedType('prime', Integer()), 
25  NamedType('exponent', Integer()), 
26  NamedType('coefficient', Integer()) 
27  ) 
28 

29  class OtherPrimeInfos(SequenceOf): 
30  componentType = OtherPrimeInfo() 
31 

32  class RSAPrivateKey(Sequence): 
33  componentType = NamedTypes( 
34  # Version ::= INTEGER { twoprime(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[i1]) 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}\nEND {text}\n'.format( 
111  b64=b64, 
112  text='RSA PRIVATE KEY' 
113  ) 
114 

115  if __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.
opensslmanyprime.diff  

1   openssl1.1.1c.orig/crypto/rsa/rsa_locl.h 
2  +++ openssl1.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   openssl1.1.1c.orig/crypto/rsa/rsa_mp.c 
13  +++ openssl1.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 PrivateKey: (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.