Anatomy of an RSA private key

Question

I'm learning about OpenSSL and public key infrastructure and am curious about the structure of an RSA key and how it's related to its corresponding public key.

I can generate a private RSA key with the OpenSSL genrsa command:

$ openssl genrsa -aes128 -out fd.key 2048
Generating RSA private key, 2048 bit long modulus
....+++
......................................................................................
+++
e is 65537 (0x10001)
Enter pass phrase for fd.key: ****************
Verifying - Enter pass phrase for fd.key: ****************

I know there are three factors to think about when generating a private key:

1. Algorithm
2. Size
3. Passphrase

In this case, I'm using the RSA algorithm, 2048 bit size, and encrypting the key with AES-128 encryption.

I can view the structure of the RSA key using the rsa command:

$ openssl rsa -text -in fd.key
Enter pass phrase for fd.key: ****************
Private-Key: (2048 bit)
modulus:
    00:b6:ae:03:fa:d5:ec:3d:7b:1e:a5:33:68:44:5f:
    [...]
publicExponent: 65537 (0x10001)
privateExponent:
    1a:12:ee:41:3c:6a:84:14:3b:be:42:bf:57:8f:dc:
    [...]
prime1:
    00:c9:7e:82:e4:74:69:20:ab:80:15:99:7d:5e:49:
    [...]
prime2:
    00:c9:2c:30:95:3e:cc:a4:07:88:33:32:a5:b1:d7:
    [...]
exponent1:
    68:f4:5e:07:d3:df:42:a6:32:84:8d:bb:f0:d6:36:
    [...]
exponent2:
    5e:b8:00:b3:f4:9a:93:cc:bc:13:27:10:9e:f8:7e:
    [...]
coefficient:
    34:28:cf:72:e5:3f:52:b2:dd:44:56:84:ac:19:00:
    [...]
writing RSA key
-----BEGIN RSA PRIVATE KEY-----
[...]
-----END RSA PRIVATE KEY-----

I'm also able to view the public key using the using the rsa command:

$ openssl rsa -in fd.key -pubout
Enter pass phrase for fd.key: ****************
writing RSA key
-----BEGIN PUBLIC KEY-----
MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEAyOYm8hJCi3vKLaud2YTU
O3glFfQUpJ6d4gXiWp//HkDQIvi2BFmvbUyHMh4XWLwPbmaX2dfJ5Aa8+ZIC9KCY
y96Gmbw+v75RzxHq5iFLnZNFhYM2zkMvUUjJs/UqunOL1OoEiC06hb85SBepKtnE
JUUKo/rtZ2Sj/pHvF0Wqu1hLyR3iOxdJb26+m2IhOy4wB3HI6FBcvrMd4Hmejpup
skIRhTQXkV7XQ79yRCTS3ejiGoVvkPKzWxL+OFWOJTduXAk8McMLEozSGZll8bv7
jJUWLhmegvokKS2eLfA4B16yU59EgNbvuoG5doKUeV0LJ03Iiqv81nFB9SqEG/Xe
VQIDAQAB
-----END PUBLIC KEY-----

From the Hexadecimal wiki page:

One hexadecimal digit represents a nibble (4 bits), which is half of an octet or byte (8 bits).

Some things I'm curious about:

• Which numbers correspond to the 2048bit length? Is it prime, exponent, coefficient...?
• How is the public key related to the private key? Is it calculated from the numbers, or is it embedded in the private key?

From reading another answer it sounds like the 2048 length corresponds to the modulus.

However when I calculate the length I get 2056:

$ echo "00:b6:ae:03:fa:d5:ec:3d:7b:1e:a5:33:68:44:5f:d0:6a:0b:b5:87:31:80:a0:50:32:b0:7c:73:4b:f8:a2:03:91:89:c2:11:32:69:2e:13:90:71:f6:a9:48:21:00:c5:ad:1c:93:f0:21:27:ce:ca:15:04:53:30:c6:88:7b:45:c0:f2:01:d5:a7:9e:c1:c5:f2:ae:b0:7f:31:68:b7:3c:c3:62:13:eb:40:25:a9:3f:cd:81:90:9f:a1:3f:02:84:d8:6e:73:d2:5d:53:28:cc:97:35:f6:fa:5c:b7:dc:11:fb:60:08:1b:75:f7:74:dc:24:29:3e:ff:fb:ba:dc:77:2c:48:0d:3b:a1:7b:d9:9a:3d:52:7d:9a:d6:c1:f1:e7:46:df:be:75:b0:d2:0f:d2:1c:7b:25:57:94:33:8f:d5:b3:ee:7f:30:98:a9:06:25:b5:ab:b1:a6:ab:f9:f2:52:b8:e7:8f:87:5f:6d:96:36:67:47:38:4c:ef:29:c7:71:e4:07:7c:13:19:3a:e2:b4:3c:85:18:32:77:a6:98:0e:0d:b4:70:01:75:79:de:e9:83:c5:df:41:2f:69:f6:30:8d:13:29:84:9a:84:3a:c0:6a:4c:0d:bd:cd:9b:1e:93:de:8e:c9:a4:02:b7:0f:a2:96:45:ad:b8:3e:3a:d3:fd:4d" | tr ':' '\n' | wc -l
257

Each line contains 2 hexadecimal digits

257 * 2 = 514

Each digit contains 4 bits

514 * 4 = 2056

Shouldn't it add up to 2048?

Answer 1

Which numbers correspond to the 2048bit length? Is it prime, exponent, coefficient...?

Only the modulus really - the key size is identical to the modulus size by definition. The primes are commonly half of the key size for calculations that use 2 primes (multi-prime RSA is faster and on the uptake). The private exponent may not reach the full key size; it's between 0 and the modulus (exclusive). There is a high chance that the size is the same or slightly less than the modulus in bytes.

How is the public key related to the private key? Is it calculated from the numbers, or is it embedded in the private key?

It's calculated during the key pair generation process - the output of which is both a private key and a public key. The private key and public key share the same modulus. Often the private key - generated by a specific tool such as OpenSSL - contains the public exponent, so you can also extract / use the public key if you have the private key.

Usually the public exponent is a known, small value - such as the fourth prime of Fermat: 0x010001. But as that may not be the case the public exponent (and thus the public key) in general isn't calculated from the private key components. If the public exponent is the same size as the private exponent then you cannot calculate it from the private key values.

From reading another answer it sounds like the 2048 length corresponds to the modulus. However when I calculate the length I get 2056 ...

ASN.1 / DER encoded INTEGER values are signed, big endian. As the most significant bit of the positive modulus is always set - assuming that the key size is dividable by 8 - it will always left-pad the modulus with a padding byte set to 00. Otherwise the encoding would represent a negative value in so-called two-complement encoding - the most significant bit is seen as the sign bit: 0 for positive number representation and 1 for negative number representation.

So the signed encoding in octets of the modulus is 2048 + 8 bits or 257 bytes. But the bit length - as it is called in most programming API's - of the modulus is still 2048.

---

Note that OpenSSL shows the generation parameters required to use the Chinese Remainder Theorem to speed up RSA calculations. In principle a private key could also consist of just the private exponent and the modulus.

Answer 2

With regard to the structure of RSA key files, and how the public key is related to the private key - you can see that the modulus in the public key file is the product of the two large primes contained in the private key file by doing the following:

Generate a private key:

openssl genrsa -out private.key 2048

Extract the public key from the private key file:

openssl rsa -in private.key -pubout > public.key

Now, use the following command to view the two large primes in the private key file:

openssl rsa -noout -text -inform PEM -in private.key

In my case, the two large primes are the following (of course, yours will be different):

prime1=00:e7:c4:87:45:a8:9a:1c:62:17:b4:18:a8:28:af:a0:64:f7:ed:58:73:c4:fa:9b:e7:08:68:90:d6:c7:65:f5:33:15:ca:24:d4:aa:94:8b:15:96:4d:5e:12:dd:f2:c7:8a:27:d8:fb:81:b8:c5:fd:b0:51:71:37:92:d8:51:5f:43:2d:c5:15:ba:3a:0a:fd:ef:3b:a0:26:50:3a:79:4f:92:e6:5f:12:a4:a2:9e:ea:bf:e7:32:c0:ec:fd:50:71:d0:56:73:6f:3b:4f:fe:79:21:6e:81:3d:06:03:41:0e:97:1b:2a:7e:e3:a6:e8:3b:53:2f:2c:27:98:8d:a5:6e:6f
prime2=00:c9:26:67:48:c7:b8:8c:9f:51:37:77:f6:ad:6d:96:68:82:e6:3b:ad:fe:e2:2d:0c:78:c7:29:6c:22:5a:f9:be:83:f3:5f:8e:e3:95:b1:d0:71:53:80:14:98:50:d8:cb:5d:1a:be:d4:dc:35:86:66:9a:82:26:38:f5:1a:4d:dc:56:f9:78:ec:67:bb:8d:24:e4:a3:18:ac:d6:0b:76:aa:df:b0:5f:a8:75:83:57:00:d6:43:be:a7:23:36:80:89:ea:cd:4b:b5:e6:cb:db:3f:85:08:c9:b8:63:78:16:f4:46:ad:16:45:87:8a:aa:84:84:c4:dc:19:ff:1c:5f:af

Use the following command to view the modulus in the public key file:

openssl rsa -noout -text -inform PEM -in public.key -pubin

In my case, I get:

modulus=00:b6:1c:12:e3:bc:3b:f3:4e:be:a1:dd:26:40:b4:35:d5:12:79:d2:63:3a:c4:f0:6f:b2:5c:13:fe:67:32:58:5b:2a:5a:b2:83:dc:db:e1:86:1d:ac:38:12:73:66:fd:f9:fe:24:cc:61:6b:c0:c8:76:b8:3e:dd:ed:9f:f1:c9:fb:f5:19:a9:32:67:0c:9a:46:36:1e:40:ed:9c:b3:22:b9:66:f4:8e:dc:56:10:d1:39:43:ec:35:dd:eb:fd:4c:a0:72:cf:cd:01:17:d9:69:6c:d9:29:c9:ce:bf:57:cc:23:b3:9a:26:c4:25:d3:80:0b:e1:28:c4:f0:38:8e:37:4a:c8:e8:9d:0c:be:75:3e:00:56:04:17:4a:eb:15:1c:7b:78:f6:01:66:78:92:1b:12:58:62:2d:c7:25:2b:db:63:07:5b:be:0e:2c:18:7d:9c:ba:2c:78:9c:1d:66:63:eb:8d:bd:36:8c:21:6f:ae:41:89:91:dd:f3:d0:96:d1:75:00:39:bf:a4:05:12:fb:b2:75:81:07:cd:e6:e0:80:d7:5e:45:9f:ee:0a:11:a7:c6:4c:e1:5a:7c:5b:15:d1:c2:f4:c6:36:5d:81:e6:cc:35:10:0c:fa:79:34:35:fd:74:fb:0c:95:fe:1c:7f:ef:19:b4:b3:21:c8:dd:35:ae:e1

You can write a short python program to multiply the two large primes to calculate the modulus, and output all three values in hex format.

prime1=0x00e7c48745a89a1c6217b418a828afa064f7ed5873c4fa9be7086890d6c765f53315ca24d4aa948b15964d5e12ddf2c78a27d8fb81b8c5fdb051713792d8515f432dc515ba3a0afdef3ba026503a794f92e65f12a4a29eeabfe732c0ecfd5071d056736f3b4ffe79216e813d0603410e971b2a7ee3a6e83b532f2c27988da56e6f
prime2=0x00c9266748c7b88c9f513777f6ad6d966882e63badfee22d0c78c7296c225af9be83f35f8ee395b1d0715380149850d8cb5d1abed4dc3586669a822638f51a4ddc56f978ec67bb8d24e4a318acd60b76aadfb05fa875835700d643bea723368089eacd4bb5e6cbdb3f8508c9b8637816f446ad1645878aaa8484c4dc19ff1c5faf
modulus=prime1*prime2
print('prime1', hex(prime1))
print('prime2', hex(prime2))
print('modulus', hex(modulus))

This produces

prime1:  0xe7c48745a89a1c6217b418a828afa064f7ed5873c4fa9be7086890d6c765f53315ca24d4aa948b15964d5e12ddf2c78a27d8fb81b8c5fdb051713792d8515f432dc515ba3a0afdef3ba026503a794f92e65f12a4a29eeabfe732c0ecfd5071d056736f3b4ffe79216e813d0603410e971b2a7ee3a6e83b532f2c27988da56e6f
prime2:  0xc9266748c7b88c9f513777f6ad6d966882e63badfee22d0c78c7296c225af9be83f35f8ee395b1d0715380149850d8cb5d1abed4dc3586669a822638f51a4ddc56f978ec67bb8d24e4a318acd60b76aadfb05fa875835700d643bea723368089eacd4bb5e6cbdb3f8508c9b8637816f446ad1645878aaa8484c4dc19ff1c5faf
modulus: 0xb61c12e3bc3bf34ebea1dd2640b435d51279d2633ac4f06fb25c13fe6732585b2a5ab283dcdbe1861dac38127366fdf9fe24cc616bc0c876b83edded9ff1c9fbf519a932670c9a46361e40ed9cb322b966f48edc5610d13943ec35ddebfd4ca072cfcd0117d9696cd929c9cebf57cc23b39a26c425d3800be128c4f0388e374ac8e89d0cbe753e005604174aeb151c7b78f6016678921b1258622dc7252bdb63075bbe0e2c187d9cba2c789c1d6663eb8dbd368c216fae418991ddf3d096d1750039bfa40512fbb2758107cde6e080d75e459fee0a11a7c64ce15a7c5b15d1c2f4c6365d81e6cc35100cfa793435fd74fb0c95fe1c7fef19b4b321c8dd35aee1

As you can see, this shows that the modulus calculated by multiplying the two large primes from the private key file matches the modulus contained in the public key file.

With regard to the question about whether or not the modulus is actually embedded in the private key file - it is. You can run the following command to convert the base64-encoded binary in the private key file to hex:

cat private.key | grep -v ^- | base64 -d | xxd -c32

This produces:

00000000: 3082 04a4 0201 0002 8201 0100 b61c 12e3 bc3b f34e bea1 dd26 40b4 35d5 1279 d263  0................;.N...&@.5..y.c
00000020: 3ac4 f06f b25c 13fe 6732 585b 2a5a b283 dcdb e186 1dac 3812 7366 fdf9 fe24 cc61  :..o.\..g2X[*Z........8.sf...$.a
00000040: 6bc0 c876 b83e dded 9ff1 c9fb f519 a932 670c 9a46 361e 40ed 9cb3 22b9 66f4 8edc  k..v.>.........2g..F6.@...".f...
00000060: 5610 d139 43ec 35dd ebfd 4ca0 72cf cd01 17d9 696c d929 c9ce bf57 cc23 b39a 26c4  V..9C.5...L.r.....il.)...W.#..&.
00000080: 25d3 800b e128 c4f0 388e 374a c8e8 9d0c be75 3e00 5604 174a eb15 1c7b 78f6 0166  %....(..8.7J.....u>.V..J...{x..f
000000a0: 7892 1b12 5862 2dc7 252b db63 075b be0e 2c18 7d9c ba2c 789c 1d66 63eb 8dbd 368c  x...Xb-.%+.c.[..,.}..,x..fc...6.
000000c0: 216f ae41 8991 ddf3 d096 d175 0039 bfa4 0512 fbb2 7581 07cd e6e0 80d7 5e45 9fee  !o.A.......u.9......u.......^E..
000000e0: 0a11 a7c6 4ce1 5a7c 5b15 d1c2 f4c6 365d 81e6 cc35 100c fa79 3435 fd74 fb0c 95fe  ....L.Z|[.....6]...5...y45.t....
00000100: 1c7f ef19 b4b3 21c8 dd35 aee1 0203 0100 0102 8201 003e fa26 6e2b 4270 39e3 2306  ......!..5...........>.&n+Bp9.#.
00000120: df9b b0b6 8d20 fe90 0b50 df9a 6686 3fe1 8a31 15f0 0856 f556 96d3 6216 f3d2 7f24  ..... ...P..f.?..1...V.V..b....$
00000140: 44fd 33b8 d123 5a86 738a 57f8 fb55 6c28 436c f4a8 ed41 2dc6 9d6f 95a4 2473 c2b2  D.3..#Z.s.W..Ul(Cl...A-..o..$s..
00000160: a179 7759 a2d4 3fee c7b3 dbcc ff08 c63f 3aa7 c9c9 1e13 9659 46ef 8078 3cf4 3cc7  .ywY..?........?:......YF..x<.<.
00000180: 5580 4654 8a64 2a03 0e02 26ca 3951 7c4f dee3 300b 5e73 b57f 0a9e eac6 ac02 4261  U.FT.d*...&.9Q|O..0.^s........Ba
000001a0: 1051 9009 15ca b50d 249d 79b7 1483 4727 3bab 70a6 a3f3 4cac 949c 5930 77fd f6d9  .Q......$.y...G';.p...L...Y0w...
000001c0: 4b4e 216f 920b 27e2 9482 260a 0f02 c335 7ea0 d9e2 8ecd 4d24 fbfb c30b 8f35 db4f  KN!o..'...&....5~.....M$.....5.O
000001e0: ff28 a240 3dad adce c9c1 e110 5f0b e1e0 223f 5df9 54b4 008d 563e 0372 4d20 2f09  .(.@=......._..."?].T...V>.rM /.
00000200: 2aa8 b56b d594 ee07 839b 6f56 ac44 a6dc d0ca b1c8 2102 8181 00e7 c487 45a8 9a1c  *..k......oV.D......!.......E...
00000220: 6217 b418 a828 afa0 64f7 ed58 73c4 fa9b e708 6890 d6c7 65f5 3315 ca24 d4aa 948b  b....(..d..Xs.....h...e.3..$....
00000240: 1596 4d5e 12dd f2c7 8a27 d8fb 81b8 c5fd b051 7137 92d8 515f 432d c515 ba3a 0afd  ..M^.....'.......Qq7..Q_C-...:..
00000260: ef3b a026 503a 794f 92e6 5f12 a4a2 9eea bfe7 32c0 ecfd 5071 d056 736f 3b4f fe79  .;.&P:yO.._.......2...Pq.Vso;O.y
00000280: 216e 813d 0603 410e 971b 2a7e e3a6 e83b 532f 2c27 988d a56e 6f02 8181 00c9 2667  !n.=..A...*~...;S/,'...no.....&g
000002a0: 48c7 b88c 9f51 3777 f6ad 6d96 6882 e63b adfe e22d 0c78 c729 6c22 5af9 be83 f35f  H....Q7w..m.h..;...-.x.)l"Z...._
000002c0: 8ee3 95b1 d071 5380 1498 50d8 cb5d 1abe d4dc 3586 669a 8226 38f5 1a4d dc56 f978  .....qS...P..]....5.f..&8..M.V.x
000002e0: ec67 bb8d 24e4 a318 acd6 0b76 aadf b05f a875 8357 00d6 43be a723 3680 89ea cd4b  .g..$......v..._.u.W..C..#6....K
00000300: b5e6 cbdb 3f85 08c9 b863 7816 f446 ad16 4587 8aaa 8484 c4dc 19ff 1c5f af02 8181  ....?....cx..F..E.........._....
00000320: 00e1 38c3 d357 625b 4e9f 862d a7cb d1cf 660e dfa0 62ef fa30 e233 f399 3c7e 0c80  ..8..Wb[N..-....f...b..0.3..<~..
00000340: 58a2 460b c075 fb5f a51c a816 50f3 49e7 ca43 aac1 cd6f 8747 5dbd e6ed 804f a1d3  X.F..u._....P.I..C...o.G]....O..
00000360: 96ee b564 c5d1 7db9 026f c8d3 3287 8037 69a3 60a4 3744 a875 ab02 baf9 6bd3 4607  ...d..}..o..2..7i.`.7D.u....k.F.
00000380: 33d3 aedd 5aa0 03c4 264e c25c 50a9 7ce0 f6ca 3963 914a 32c6 e3b1 2591 5cd7 d8f9  3...Z...&N.\P.|...9c.J2...%.\...
000003a0: 1502 8180 256b 9f8b 4a9c 6a8c b8ef 38c2 0b41 77d9 b980 5b59 e330 f070 8187 8b8d  ....%k..J.j...8..Aw...[Y.0.p....
000003c0: 3256 fa5f 16ed 0fb9 e55c d3d7 933d 9576 3f5f caf5 0a3d 0f83 49f4 2b2c ab51 cb0a  2V._.....\...=.v?_...=..I.+,.Q..
000003e0: 8d8e 772d a680 829e 782d cbf4 3114 a662 80ef 6104 28d9 06f2 afe9 df25 a8b6 b1a1  ..w-....x-..1..b..a.(......%....
00000400: 264b dd5d caf0 a645 10ca 9bdf 1540 ad46 403a f70a 3a9b b8a8 f6ae 354a b1e8 6d89  &K.][email protected]@:..:.....5J..m.
00000420: e88b bec1 0281 8100 e531 018b fb6a aa77 2b6a 04d8 ae8c 3487 de6e 0aff cc9a 4843  .........1...j.w+j....4..n....HC
00000440: df3f 9ea8 76f8 bdf2 6917 2c9e 93eb baa1 0a1e 1050 73b1 ea13 c37f 8e31 1ea6 8cca  .?..v...i.,........Ps......1....
00000460: 297f 7f12 7528 5832 de3c 0618 f3ef 815b 10a8 4cf5 4cef e7c9 808c 30e6 dfe0 0462  )...u(X2.<.....[..L.L.....0....b
00000480: 4cbd ba75 a03c 0c5d 5145 e4f9 dc78 bb24 843b 562c 7ad7 cb30 e957 57f9 bbfa 8e56  L..u.<.]QE...x.$.;V,z..0.WW....V
000004a0: 0724 ff43 fe10 2059                                                              .$.C.. Y

As you can see, the modulus is embedded in the private key file, starting at the 13th byte. You can also see that the first prime starts at the 282nd byte, and the second prime starts at the 350th byte

Answer 3

For the relation between public and private key : the second integer of the private key is called the decrypting exponent, it is computed with the encrypting exponent $e$ and $\phi(n)$. It is the modular inverse of $e$ mod $\phi(n)$. $\phi(n)$ is computed with the decomposition in prime factors of $n$.

So, when you encrypt a number using the public encrypting exponent, (and always mod n), the decrypting exponent of the private key lets you get your number back.