Max size for exponent and modulus in RSA and for y, p, q, g in DSS

Question

I'm writing a method in Java to read SSH public key in RFC 4253 format, which, in my case, can be either RSA, or DSS.

What I really need is to read exponent and modulus for RSA key and y, p, q, g values for DSS key, which, according to the standard are of type mpint (multiple precision integers).

So basically, what I'm doing, is reading an integer first (that becomes "length"), then reading as many bytes as this integer is, then converting this byte array to Java's BigInteger.

It works perfectly well for valid keys. But the problem appears if there's a malformed key where this first integer is some extremely big number (let's say Integer.MAX_VALUE). Then such an approach results in Requested array size exceeds VM limit exception or some other Java errors related to memory. What I want to do to solve this issue is pre-checking if the length-integer is in a valid range (smaller then some max value).

And here comes the question: what are the max values for exponent, modulus, y, p, q and g? Is there even any maximum for them?

Answer 1

The cryptosystems themselves have no limit. You can use a DSA or RSA system with any kind of key size.

However, generating the DSA domain parameters over 16Ki or generating an RSA key over 16Ki in size is a very CPU consuming operation. My computer generating a 17Ki RSA key pair as I type this, just to give bartonjs another anecdote to tell his grand-children one time ;)

Ah, there it is, the modulus is (in hex):

ba948ca14989fa57a16d492243a9be9452f54d6d5f568956c246f8ecfe8e7a04a9cd827314f0c8d70e99c02fc01546ee70ed2a0222ac909d6f8f0f8e5a10838173daf9903bdab2587e57be5bfbe5a1f1161e3b2b8361562adcf36fa4d94c4f145bcb3de1fdf44715fc64611eee3925e9f06734065dee2a9c970a33f62adf385f683d71c5d6cb9a1dbeba801feefb3edacdc13d3ddcc41b8b1f91ee84fdec758e1fedca74684ace88b1e28f79ef0b3381384b1f4339751875098b584b85d04576d7e4755e537b877e033b6c5726f1896aa5e5c635875b9499d3515e618e08001a4e3516aa687cbf55ffa94f1e6e978ebc7dfd5bf7e11fa045339cda817413a7674a73e53b00270d880bd73d236422ba8a5fd48bec4686ac9d0e0d8641e1451a8fef69607cfa3d1a2ffcb2a24edcd3d1dc028e6a14aed9dca587fc8d79fb9c3c8759ec8924aa9f3abedd7b986491e2fed16d445430339f45e433d46cbdf94e929748a8544de973cbe3aa67285c38787b9e45f2ce64a58b7d78078141c584905611b63a6f438efd4ed52d161568b57b39db4b4391f35b2fea1ff52bc0ff79fd2cd8cd069f0e20b4ed06f16909983d9f46416ef2775dddf4d4a120f99c7baee0b2a06be383579f13093c3f3e62508955462e5ceefda4483a75f1b03badce08ee26283195c1072844f19d0156e7527b3df2615938f14e22259fa14d04292c2367a94814711b396716f5911faef248c520b9b4410a53dac5c6d19f382f02a25607032a2745dfb1f647a28a3d403562f177996c4c6657a0db2d3cf0bfc84af69e1b607552a242ea07e89f2281c4040844cfae816a0111fdc8ff570b3facb669fefcfacd5812d9eb46131e20c106ec8bf70668b1d6b61bd72f9aaabb22bd4f3fdbbf060f894ac8a919f61c7fc46ef091c3523c902c1fd961dbddfc6df9a7e0d2f68cd04a0698aa0db465e05d74c0b906cdb0f27b31df2c43f59ef04b1f791f360a8e4d3ffb0a6ab38d5075171139268ed749263c5dd1618b6c243f823c7a982755bb990dc6270cc84867c58de4086ed05a8c5fabaaa0c34d79d4820b37afc47b8bcc08e4729620ef46ed192c7c17cce0afedb707143d7161f586680356f6e596482a317b20e44f486504cc78b0c692253c6230f35dd5998d84ab2b03ada45a90bed258db611a5583995b4b1c10023d8875c9d1e4ddcfa7ab834a0bed9161eaf187f21409d0168cce2dc0965188e2c67967c1557b90e806f5af45191cc2cdf5ec93892aec5d32fe380d1c57ec4fd9696a05a1bea22199e490c0a03829eebbf32cd7cf7cb5507c90a9c6e066f1381754e6a7319d8d5931ebc23239165b632f4e59feabf1dea6bcea421ff1ab891735ca11082f4126fe696dd16e751521db92f502339e567cbb1b335688f83ba1e6bf8ec0926b79a2f09ffc462c5ceddcbaa71aaa24662d7cd319dd4194b48eaa8f5fb5c340fd96ad4b8db57e856a4d971beec6eff512ebc41d0887392c77c7318ae182a4be13563ac2e67b7c4ebb1f3b3e8d3ce9da3bf5e643bc1e0da91bd208a90f5a3df8e1184bf1ce7b4c7c4aaec85491fb7f7844df26240e6f7e2a90d6cab247dbfd35f839d9773b5501df43134788421023b1592d0da1994f722903c83e91f2d1f3adeade9aa7c0deaa38c0768bde2d6338091e8c51718d39050ff18d1d115bf55b292e0a70dc6c0f35fd519b858869744dd4276a20584532117b436aab0fd9c8580dfbd30755e6a4518a48f32bba63450b597d4e1229baa3821cd819e811b3fd05b702bb99d7f6ddb601e579fdd43bdb4e950b6be66e68c3c5ffd1ebbe75e2e80fefd786718d9dc4ce7ef522bd9988201e874993cd84db9591182817f18ccf4c0f1dff89dd548b57b680eab917b67b76ae7daab46f4feeb5c533cbad3b0187ffbccb479e30510a9e99b5a4696ab58986d681837806f17ef2c698a5dba8a3ad099b96e6483d0445c42a97c8e2f139fcb26c3120c3a4ac9a43443de7603cf47701db975c5687aaabf3d52953c5e63cc2984b4b995dbdf2827d6c2d2862ef51eb7e958c6b6eac6ef0d30bee671f9c251912d964cfbfd5c535d1d6f5951795cf2d43da776f63e5b42abc0885fa59a4554988d7d7e24b054e7aac3946ba4f438927a21b2e9e388d357229e7bea9c3fe8d3d560d605e16a2d364b6cac7868e148dc158b50b6fe592eae7a016b9adc7e5b251a6c9cd32cc9d271366c003975f21b52c0f03badf481ee7000e74b1abfd267ef42e4cd1c53a80ff44c9e0c68291575c4eb876751c701da70fbf8a43f8312f68cc866bdd4b14d3e9a475505dda90c467b687562fcd6b9d79bfafce27d6dcaa7f89790a26e754251466d7d3a45a9472e1b32aa3b56b96f9a0bcc3ca7226ddcd528ac8666c9e661d408f8a87a218ab5a41b5fb332ba2caf02778f2942659c8542581cecf7dfb337c8f81343a1778976c30472f95d759fdf43ec1e4fe8d68ed3b1f4fe8959c4eccc51eb6bff2ad29bb41142c58482acd8dedaae37a2f02610848b87007f290a6385d479cc55c83933f2cb4daf5ef85846d0cb4176b27464c7942ddd8357e38fcfc434667e6d2851a10d19b5fc3553269fc8de342c485aa59941e4b810457902e9830cfdf3f3ca1cd5026f2c716a954ec1b7248d59df382d270c712c81f0997099187bddb6620bb982333449c84f9a4340b3d639edf9b66ebdd966ae919b37c462e64f75b96767f5473178bee02c648f12857ffc692d805ac7523ff978c5b0bed858dc01a5b25ead826fe34c9c2b4a437b7b60227f3fd190e38d01ce08e52502d54642bc80054bcf155423e9faacffa8d6d409610f8b2c71c14f8d625c78d54a5f0db76c5e23e10dd5d3874ebbe7db5a36021c341b8d56362ee4a5ba89ecef3ad4b9d06701fe09c460f34893fe8008e3cc487f3ac0bce387d77afbce666002565e514a2ba61cb29652a2d5bcdb21167a2f2e3ae1eb459d6e457565e73f203ca34995f37db4d949761d7f0778bce198a1f2978c02f8f631656ecc10e2eac3029ded2598d544020dd78ebb61d13b373498039e122dbdb0b45850cb416b748ee60034727

For practical purposes however the 4Ki and 16 Ki limit proposed by bartonjs would be fine.

Nobody would begrudge you if you only support key sizes that are multiples of 8 or even 32 either; there are a lot of implementations that do this; few would support RSA with a key size that cannot be divided by 8, even if that is perfectly possible.

---

For the SSH protocol, you have to look at section 5 of RFC 4251 which specifies the data types. Here mpint is a signed big endian value encoded as a string type. This string type itself is an octet string (byte array in Java) preceded by an unsigned 32 bit integer encoding the length.

That means that a 00 valued padding byte will be required at the left of the modulus. So you should allow 16Ki / 8 = 2Ki byte for each number plus the one padding byte (not including the 4 bytes overhead that is used to encode the size of the mpint itself). Here 1Ki = 1024 bytes (so 2Ki + 1= 2049 bytes would be the total size of the number).

Note that RSA signatures are encoded as unsigned octet string, so you would require just 2Ki bytes for a 16Ki signature.

---

As example you could give the value 2049 as value of mpIntMaxBytes:

/**
 * Parses the <code>mpint</code> (multi-precission integer) SSH type
 * specified in RFC 4251 section 5. This method advances the position in the
 * buffer to the byte after the parsed <code>mpint</code>. If a
 * {@link SSHDataParseException} occurs then the buffer will have advanced
 * an unspecified number of times.
 * 
 * @param buf
 *            the buffer that contains the <code>mpint</code> encoding from
 *            the current position
 * @param mpIntMaxBytes
 *            the maximum number of bytes that the signed encoding of the
 *            <code>mpint</code> may use
 * @return the <code>mpint</code> as BigInteger
 * @throws SSHDataParseException
 *             if the <code>mpint</code> encoding is too large or if it is
 *             empty
 */
public BigInteger parseMPInt(ByteBuffer buf, int mpIntMaxBytes)
        throws SSHDataParseException {
    if (mpIntMaxBytes < 1) {
        throw new IllegalArgumentException(
                "maxBytes should be larger than 0 to contain an mpint");
    }

    long mpIntSize = parseStringSize(buf);
    if (mpIntSize == 0) {
        throw new SSHDataParseException(
                "A number consists of at least 1 byte (00h represents zero)");
    }

    if (mpIntSize > mpIntMaxBytes) {
        throw new SSHDataParseException("Number exceeds maximum size");
    }

    // get mpint from the buffer using newly generated array (BigInteger
    // does not allow reading from a specific offset)
    byte[] mpIntBuf = new byte[(int) mpIntSize];
    buf.get(mpIntBuf);

    // an mpint is a signed big endian byte array, just like the default
    // BigInteger encoding
    return new BigInteger(mpIntBuf);
}

/**
 * Parses the size of the (octet) string, where the size of the string is a
 * 32 bit uint.
 * 
 * @param buf
 *            the buffer that contains the size encoding from the current
 *            position
 * @return the size as a value between 0 and 2^32 - 1
 */
public long parseStringSize(ByteBuffer buf) {
    return buf.getInt() & 0xFFFFFFFF;
}

public static class SSHDataParseException extends Exception {
    private static final long serialVersionUID = 1L;

    public SSHDataParseException(String message) {
        super(message);
    }
}

Note that this code still doesn't check if the returned BigInteger is positive or negative, of a specific bit size, nor if the minimum encoding has been used. Parsing is validating until you see blue from exhaustion I'm afraid.

And to make matters worse, this is untested code, good luck!

Answer 2

For DSA/DSS the key sizes are restricted by FIPS 186-4, so nothing will ever exceed 4096-bit.

For RSA, anecdotally the largest size anyone supports is 16k-bit, so a Modulus value expressed in 2049 bytes (2048 plus one padding byte).