51
$\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?

Improve this question
$\endgroup$
1
  • 5
    $\begingroup$ Off-topic, but incredibly convenient: paste it at https://lapo.it/asn1js/, then read and interpret per either common sense or documentation. That applies to a helluva of other practical questions. $\endgroup$
    – fgrieu ♦
    Commented Sep 5, 2019 at 9:42

5 Answers 5

Reset to default
29
$\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.

Improve this answer
$\endgroup$
51
$\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.

Improve this answer
$\endgroup$
5
  • $\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
    Commented Jun 15, 2016 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
    Commented Jun 15, 2016 at 13:33
  • 1
    $\begingroup$ @IanBoyd Great explanation of the DER variant. $\endgroup$
    – John Doe
    Commented May 9, 2017 at 11:13
  • $\begingroup$ Great explanation of DER. $\endgroup$
    – Jingguo Yao
    Commented Apr 6, 2018 at 9:25
  • $\begingroup$ @IanBoyd: FWIW Here is such a tool. $\endgroup$
    – psmears
    Commented Jul 16, 2020 at 14:15
31
$\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.

Improve this answer
$\endgroup$
5
$\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

Improve this answer
$\endgroup$
2
$\begingroup$

You can use openssl asn1parse to examine any ASN.1 structure. In your case

$ openssl asn1parse -i -dump -in cse-18031
 0:d=0  hl=3 l= 159 cons: SEQUENCE
 3:d=1  hl=2 l=  13 cons:  SEQUENCE
 5:d=2  hl=2 l=   9 prim:   OBJECT            :rsaEncryption
16:d=2  hl=2 l=   0 prim:   NULL
18:d=1  hl=3 l= 141 prim:  BIT STRING
   0000 - 00 30 81 89 02 81 81 00-aa 18 ab a4 3b 50 de ef   .0..........;P..
   0010 - 38 59 8f af 87 d2 ab 63-4e 45 71 c1 30 a9 bc a7   8Y.....cNEq.0...
   0020 - b8 78 26 74 14 fa ab 8b-47 1b d8 96 5f 5c 9f c3   .x&t....G..._\..
   0030 - 81 84 85 ea f5 29 c2 62-46 f3 05 50 64 a8 de 19   .....).bF..Pd...
   0040 - c8 c3 38 be 54 96 cb ae-b0 59 dc 0b 35 81 43 b4   ..8.T....Y..5.C.
   0050 - 4a 35 44 9e b2 64 11 31-21 a4 55 bd 7f de 3f ac   J5D..d.1!.U...?.
   0060 - 91 9e 94 b5 6f b9 bb 4f-65 1c db 23 ea d4 39 d6   ....o..Oe..#..9.
   0070 - cd 52 3e b0 81 91 e7 5b-35 fd 13 a7 41 9b 30 90   .R>....[5...A.0.
   0080 - f2 47 87 bd 4f 4e 19 67-02 03 01 00 01            .G..ON.g.....

The output is the key type and a bit string. Disapointing, I know. But no need to worry. ASN.1 structures like to contain other ASN.1 structures labeled as bit strings. We just needs to note the first number on the line that says "bit string" which is it's offset and run asn1parse again.

$ openssl asn1parse -i -dump -in cse-18031 -strparse 18
  0:d=0  hl=3 l= 137 cons: SEQUENCE
  3:d=1  hl=3 l= 129 prim:  INTEGER           :AA18ABA43B50DEEF38598FAF87D2AB634E4571C130A9BCA7B878267414FAAB8B471BD8965F5C9FC3818485EAF529C26246F3055064A8DE19C8C338BE5496CBAEB059DC0B358143B44A35449EB264113121A455BD7FDE3FAC919E94B56FB9BB4F651CDB23EAD439D6CD523EB08191E75B35FD13A7419B3090F24787BD4F4E1967
135:d=1  hl=2 l=   3 prim:  INTEGER           :010001

The output a simple sequence of two integers. It's obvious which one is the modulus and which is the exponent.

You actually can use the very same workflow for any asn.1 you come along. All identifiers are globally assigned and there are no "codepages" to chase around.

Improve this answer
$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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