# How to find the encoding of an RSA public key?

What practical methods is there to reconstruct an RSA public key in unknown format?

As an illustration, in a database I find this (which doesn't look like ASN to me):

The first step is to check how much data we have. That gives an idea of the size of the public modulus: although it is possible to compress an RSA public modulus $N$ to less bits than its bitlength $\lceil\log_2(N-1)\rceil$, this is uncommon; and most RSA public key formats are larger than the public modulus, and only much larger for digital certificates. Here, excluding the 0x prefix (meaning hexadecimal in many computer languages), the given is 276-character uppercase hex; that probably is hex, coding 138 bytes or 1104 bits, which suggests a 1024-bit RSA public key (the next lowest common size, and also one of the lowest common size).

Next is to confirm this; guess the endianness; and locate the public modulus $N$. The data coding $N$ typically is visually random-like (here, pointing towards the end of the data blob). As a quick test we can use that the low-order bit is set; and the hypothesized bitlength (if exact, which is typical) gives us another bit set. When we have an hypothesis on the location and coding of $N$, we can check it with an often-sufficiently-selective test: the public modulus is a composite with no factor quickly found. With a factoring program that finds factors less than $b$, odds that an incorrect odd guess pass this test are less than $$\epsilon(b)=\prod_{p\text{ prime, }2<p<b}{p-1\over p}$$ That's residual odds below 5.1% to wrongly conclude that a guessed encoding is correct if we only check for at-most-32-bit factors, and perhaps less than a percent for the program I use, gmp-ecm (todo: justify); this is often good enough (especially if we have several examples).

Our data seems to use little-endian byte ordering, transformed to hex using big-endian ordering of the two characters of each hex byte. With that convention, the last 256 characters "170D3375..85B30EE6" would be a 1024-bit (128-byte) public modulus of 0xE60EB385..75330D17, which passes the above test. No other simple ordering that I checked does.

Immediately before that is "01000100", which by the same convention decodes to 0x00010001 and would be the common public exponent $e=65537=2^{(2^4)}+1=F_4$ (the fourth Fermat number).

Immediately before that is "00040000", which by the same convention decodes to 0x00000400, and that would be 1024, the conjectured bit length of the modulus (with $e$ always on 32 bits, as in early Windows CryptoAPI, explaining why there is no length for $e$).

The "52534131" immediately before matches "RSA1" in ASCII, and that could be a format indicator.

Searching for that string, it comes that Microsoft used that as a magic number for RSA keys, followed by bitlen and pubexp on 32-bit (strongly reinforcing the credibility of the above three educated guesses) in a RSAPUBKEY:

typedef struct _RSAPUBKEY {
DWORD magic;
DWORD bitlen;
DWORD pubexp;
} RSAPUBKEY;

[contributed by CodesInChaos]: The first 8 bytes are a PUBLICKEYSTRUC:

typedef struct _PUBLICKEYSTRUC {
BYTE   bType;    // 0x06 = PUBLICKEYBLOB -- The key is a public key.
BYTE   bVersion; // 0x02
WORD   reserved; // 0x0000
ALG_ID aiKeyAlg; // 0x0000a400 = CALG_RSA_KEYX -- RSA public key exchange algorithm.