24
$\begingroup$

I am studying the RSA cryptosystem. The public key consists of $(n, e)$, the modulus (product of two large primes), and the encryption exponent. I want to separate the modulus $n$ and exponent $e$. A typical public key is expressed in base64, and is of the following type:

 -----BEGIN PUBLIC KEY-----

 MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCqGKukO1De7zhZj6+H0qtjTkVxwTCpvKe4eCZ0
 FPqri0cb2JZfXJ/DgYSF6vUpwmJG8wVQZKjeGcjDOL5UlsuusFncCzWBQ7RKNUSesmQRMSGkVb1/
 3j+skZ6UtW+5u09lHNsj6tQ51s1SPrCBkedbNf0Tp0GbMJDyR4e9T04ZZwIDAQAB

-----END PUBLIC KEY-----

Now from the above key, it is not clear which part is the modulus and which is the exponent. How can I extract the two?

$\endgroup$
15
$\begingroup$

RSA key formats are defined in at least RFC 3447 and RFC 5280. The format is based on ASN.1 and includes more than just the raw modulus and exponent.

If you decode the base 64 encoded ASN.1, you will find some wrapping (like an object identifier) as well as an internal ASN.1 bitstring, which decodes as:

(
    119445732379544598056145200053932732877863846799652384989588303737527328743970559883211146487286317168142202446955508902936035124709397221178664495721428029984726868375359168203283442617134197706515425366188396513684446494070223079865755643116690165578452542158755074958452695530623055205290232290667934914919, 
    65537
)

The former is the 2048-bit modulus $n$ and the latter the public exponent $e$, which is usually chosen as either 3 or, like here, 65537. To do the same for an arbitrary key, you will need to read up on at least ASN.1, or else use an existing decoder.

$\endgroup$
23
$\begingroup$

I wanted to help break down exactly what you're seeing.

If you take your base64 string:

MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCqGKukO1De7zhZj6+H0qtjTkVxwTCpvKe4eCZ0FPqri0cb2JZfXJ/DgYSF6vUpwmJG8wVQZKjeGcjDOL5UlsuusFncCzWBQ7RKNUSesmQRMSGkVb1/3j+skZ6UtW+5u09lHNsj6tQ51s1SPrCBkedbNf0Tp0GbMJDyR4e9T04ZZwIDAQAB

You then decode it into hex:

30 81 9F 30 0D 06 09 2A  86 48 86 F7 0D 01 01 01
05 00 03 81 8D 00 30 81  89 02 81 81 00 AA 18 AB
A4 3B 50 DE EF 38 59 8F  AF 87 D2 AB 63 4E 45 71
C1 30 A9 BC A7 B8 78 26  74 14 FA AB 8B 47 1B D8
96 5F 5C 9F C3 81 84 85  EA F5 29 C2 62 46 F3 05
50 64 A8 DE 19 C8 C3 38  BE 54 96 CB AE B0 59 DC
0B 35 81 43 B4 4A 35 44  9E B2 64 11 31 21 A4 55
BD 7F DE 3F AC 91 9E 94  B5 6F B9 BB 4F 65 1C DB
23 EA D4 39 D6 CD 52 3E  B0 81 91 E7 5B 35 FD 13
A7 41 9B 30 90 F2 47 87  BD 4F 4E 19 67 02 03 01
00 01 

So the question is: what is this? Well it's actually the DER variant of ASN.1 encoding. ASN.1 is a horrible monstrosity, but you can use the web-based ASN.1 decoder to find that the values are actually this:

30 81 9F             ;30=SEQUENCE (0x9F = 159 bytes)
|  30 0D             ;30=SEQUENCE (0x0D = 13 bytes)
|  |  06 09          ;06=OBJECT_IDENTIFIER (0x09 = 9 bytes)
|  |  2A 86 48 86    ;Hex encoding of 1.2.840.113549.1.1
|  |  F7 0D 01 01 01
|  |  05 00          ;05=NULL (0 bytes)
|  03 81 8D 00       ;03=BIT STRING (0x8d = 141 bytes)
|  |  30 81 89       ;30=SEQUENCE (0x89 = 137 bytes)
|  |  |  02 81 81    ;02=INTEGER (0x81 = 129 bytes) the modulus
|  |  |  00          ;leading zero of INTEGER 
|  |  |  AA 18 AB A4 3B 50 DE EF  38 59 8F AF 87 D2 AB 63 
|  |  |  4E 45 71 C1 30 A9 BC A7  B8 78 26 74 14 FA AB 8B 
|  |  |  47 1B D8 96 5F 5C 9F C3  81 84 85 EA F5 29 C2 62 
|  |  |  46 F3 05 50 64 A8 DE 19  C8 C3 38 BE 54 96 CB AE 
|  |  |  B0 59 DC 0B 35 81 43 B4  4A 35 44 9E B2 64 11 31 
|  |  |  21 A4 55 BD 7F DE 3F AC  91 9E 94 B5 6F B9 BB 4F 
|  |  |  65 1C DB 23 EA D4 39 D6  CD 52 3E B0 81 91 E7 5B 
|  |  |  35 FD 13 A7 41 9B 30 90  F2 47 87 BD 4F 4E 19 67 
|  |  02 03          ;02=INTEGER (0x03 = 3 bytes) - the exponent
|  |  |  01 00 01    ;hex for 65537

So encoded in there are the two important numbers in hex:

  • Exponent: 65537 (Nearly everyone universally uses 65,537 as their prime exponent)
  • Modulus: 00 AA 18 AB A4 3B 50 DE EF 38 59 8F AF 87 D2 AB 63 4E 45 71 C1 30 A9 BC A7 B8 78 26 74 14 FA AB 8B 47 1B D8 96 5F 5C 9F C3 81 84 85 EA F5 29 C2 62 46 F3 05 50 64 A8 DE 19 C8 C3 38 BE 54 96 CB AE B0 59 DC 0B 35 81 43 B4 4A 35 44 9E B2 64 11 31 21 A4 55 BD 7F DE 3F AC 91 9E 94 B5 6F B9 BB 4F 65 1C DB 23 EA D4 39 D6 CD 52 3E B0 81 91 E7 5B 35 FD 13 A7 41 9B 30 90 F2 47 87 BD 4F 4E 19 67

Or, in decimal, your modulus is:

119,445,732,379,544,598,056,145,200,053,932,732,877,863,846,799,652,384,989,588,303,737,527,328,743,970,559,883,211,146,487,286,317,168,142,202,446,955,508,902,936,035,124,709,397,221,178,664,495,721,428,029,984,726,868,375,359,168,203,283,442,617,134,197,706,515,425,366,188,396,513,684,446,494,070,223,079,865,755,643,116,690,165,578,452,542,158,755,074,958,452,695,530,623,055,205,290,232,290,667,934,914,919

No need for OpenSSL and it's voodoo commands.

$\endgroup$
  • $\begingroup$ Actually the DER/BER encoding of OID isn't 'hex', it's 7bit-chunks with 'more' flag except the first two arcs are special. That said, there are many tools around to encode/decode it so you don't need to do it by hand. Also note $e$ is usually chosen prime, including 65537, but RSA only requires it be coprime to Carmichael($n$). $\endgroup$ – dave_thompson_085 Jun 15 '16 at 12:29
  • $\begingroup$ @dave_thompson_085 What you see is the hex encoding of the OID. I know of no tool that can turn an OID into hex (i.e. 8-bit binary) $\endgroup$ – Ian Boyd Jun 15 '16 at 13:33
  • 1
    $\begingroup$ @IanBoyd Great explanation of the DER variant. $\endgroup$ – kadaj May 9 '17 at 11:13
  • $\begingroup$ Great explanation of DER. $\endgroup$ – Jingguo Yao Apr 6 '18 at 9:25
19
$\begingroup$

In practice, one can use openssl to extract the information:

$ cat pubkey.txt
-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCqGKukO1De7zhZj6+H0qtjTkVxwTCpvKe4eCZ0
FPqri0cb2JZfXJ/DgYSF6vUpwmJG8wVQZKjeGcjDOL5UlsuusFncCzWBQ7RKNUSesmQRMSGkVb1/
3j+skZ6UtW+5u09lHNsj6tQ51s1SPrCBkedbNf0Tp0GbMJDyR4e9T04ZZwIDAQAB
-----END PUBLIC KEY-----

$ openssl rsa -pubin -in pubkey.txt -text -noout
Public-Key: (1024 bit)
Modulus:
    00:aa:18:ab:a4:3b:50:de:ef:38:59:8f:af:87:d2:
    ab:63:4e:45:71:c1:30:a9:bc:a7:b8:78:26:74:14:
    fa:ab:8b:47:1b:d8:96:5f:5c:9f:c3:81:84:85:ea:
    f5:29:c2:62:46:f3:05:50:64:a8:de:19:c8:c3:38:
    be:54:96:cb:ae:b0:59:dc:0b:35:81:43:b4:4a:35:
    44:9e:b2:64:11:31:21:a4:55:bd:7f:de:3f:ac:91:
    9e:94:b5:6f:b9:bb:4f:65:1c:db:23:ea:d4:39:d6:
    cd:52:3e:b0:81:91:e7:5b:35:fd:13:a7:41:9b:30:
    90:f2:47:87:bd:4f:4e:19:67
Exponent: 65537 (0x10001)

The modulus is printed in hexadecimal, how to obtain its decimal value is left as an exercise to the reader.

$\endgroup$
1
$\begingroup$

You can use directly the -modulus parameter of the openssl rsa command:

echo '-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCqGKukO1De7zhZj6+H0qtjTkVxwTCpvKe4eCZ0
FPqri0cb2JZfXJ/DgYSF6vUpwmJG8wVQZKjeGcjDOL5UlsuusFncCzWBQ7RKNUSesmQRMSGkVb1/
3j+skZ6UtW+5u09lHNsj6tQ51s1SPrCBkedbNf0Tp0GbMJDyR4e9T04ZZwIDAQAB
-----END PUBLIC KEY-----' | openssl rsa -pubin -modulus -noout

Modulus=AA18ABA43B50DEEF38598FAF87D2AB634E4571C130A9BCA7B878267414FAAB8B471BD8965F5C9FC3818485EAF529C26246F3055064A8DE19C8C338BE5496CBAEB059DC0B358143B44A35449EB264113121A455BD7FDE3FAC919E94B56FB9BB4F651CDB23EAD439D6CD523EB08191E75B35FD13A7419B3090F24787BD4F4E1967

$\endgroup$

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.