14
$\begingroup$

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):

0x0602000000A40000525341310004000001000100170D33754DB739E6298F70465182848A72C980F7D15D45E3EC91448AFC6088FCED3A880A7CAD8EEF053064F6932183A29A102D3A390E99ECDE03B4456AD5B0389CB3213160511EE2B5473F887294A7572F12A351A70D9DC7C155DFA3C9763986299AE555CFE166123FC2A904199D6A3B0C6AD3F519A849CF4397D91085B30EE6

$\endgroup$
31
$\begingroup$

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. 
} BLOBHEADER, PUBLICKEYSTRUC;

[contributed by Maarten Bodewes]: The overall structure is a PUBLICKEYBLOB:

PUBLICKEYSTRUC  publickeystruc;
RSAPUBKEY       rsapubkey;
BYTE            modulus[rsapubkey.bitlen/8];

Note: The above formula for the size of the modulus field can only be valid if bitlen is a multiple of 8; and then it is prudent and customary to use only multiples of 64, or even 128 for good measure.

$\endgroup$
  • 1
    $\begingroup$ Just checked the format, it's precisely as described. Note that the magic should always be "RSA1" in ASCII, but that Microsoft shows it as a number (i.e., because it is interpreted as little endian, it is in reverse). The magic is therefore in the order you expect. I hate little endian, in case you didn't notice yet. $\endgroup$ – Maarten Bodewes Nov 28 '16 at 16:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.