RSA Private Key - Side Notes

“What I cannot create, I do not understand” — Richard Feynman

As a fun exercise I wanted to know how to build an RSA private key file from scratch. It turned out that it was not complicated. In fact it was very educational to learn about the PKCS #1 and X.609 standards. By the end of this post you should be able to read DER files without the openssl command, too.

From a mathematical perspective an RSA private key is just a pair of numbers satisfying a few conditions. The first step is to choose two prime numbers. If we want our key to be $k$-bit long then each prime should be $k/2$-bit long. Here are two primes 1024-bit long:

p = 188658351657909995564241240465674883756750911978965594406091265432265641964092435440867010496656290185915042088848864982944624560228571535282140345941898374783486396513112284924130530433476612244870421527834092351771495657957917171265855063528745445693207773620468819387929613829761428627329588653924255089451
q = 314178598271171309643469864042809599136290738797354680579453738873053976803051841787567944451717551290169456210178094252448060684978774667964812128639960504040754248179131205124174037497556941333232996617690501240860884613659741212508891734662698093999296965839284246675187499601986034176733136066305345935229

The product of these primes is a modulus of an RSA key:

n = 59272416476031870310813269456482000649521214839097555249658956878429667033345971911228897520094455477409965068308635488009811551774829628449872899499797577442984988498839316022812024085070921696680719869349925179295023663107587202715785410835479198432493682921268850396489979925015801144167399352584659489661536583643002656464738703092254954684055792766769402010692858706224804514602103071851330570529764510187019367372650739782606640058374679178234229890697709969669187824580807498629684496386911304548122885254757980404399786500026446625957982264789094145961033518145284058963944371890973871992953130981578647169279

To form a public key, we need to select a public exponent. A common choice is

e = 65537

To find the private exponent we need to calculate $t = LCM(p - 1, q - 1)$ and make sure that $t$ and $e$ are relatively prime. In our case

t = 9878736079338645051802211576080333441586869139849592541609826146404944505557661985204816253349075912901660844718105914668301925295804938074978816583299596240497498083139886003802004014178486949446786644891654196549170610517931200452630901805913199738748947153544808399414996654169300190694566558764109914943505624448845595859921831997957745033527125185998846955951218950319914149305826465770482602596898444785155811512270630091202325802194555495831212902685975181807491196648094001430229988075979625161669911184872231135294567704734798040363872577766275101044754796447588498816804543076537734864815067710224841024100

and it is indeed relatively prime with 65537. If it wasn’t we would try another public exponent or different primes.

The private exponent $d$ is a solution of the equation $d e = 1 (\mod t)$:

d = 5713468916051268780132002190819673753298269494741275244475317000371286701232244684486677071989004278539215293013032128257126755518442870024474679399017164287346341262848989717077546426498334823562735569036929683476505833667571970367220374781441535665311810014311952295213788137687613934542118968573398572043557642081710231861001832858546933301048448251370985779305964616826007078677511121329392138316261633140615925043274882325662342756097813929749397956320997349454981862425032501185764338740435657905121325564969361566019276046817336541525431835263330506889244027107578840336789285453607676614980092565853828740673

For cryptographic purposes numbers $n$, $e$, and $d$ is all you need. But for computational efficiency, PKCS #1 requires three more numbers:

dp = 73281896610394353679278716733062018642836992328738378882095081314512206043607445092362352353836446271004764124934396689973927818327643095864587130729861100246627297496594281662474493999496683063272141245923256923555349878154854470435248368894689607565375136076663178588561029330976954828050251588613298774923
dq = 48768464839901517204068219889642523338167534153005007332267007729306774890786065680530520147509386289804139311017314689872196184571907086030883833325515635558640050150698105646096441452349768286357008630113759694878889469685224336708316761779203010669619421601279256624909325014129482974196350049628824697485
qi = 96649294882937985304687069867459392294125861105683721163844518450032271220340037497914128685821080429968806273738795285224909792718537306451785722671106543229818520952472427298015487036380943796651715614555934218685011386800675679145785323478975345929484318504374494139364842881030508783682984009085234707403

That’s all the numbers we need. You can calculate these numbers using any mathematical software that supports arbitrarily long integers. I did it in Erlang

Erlang

P = primes:random_prime(maths:pow(2, 1024), maths:pow(2, 1025) - 1).
Q = primes:random_prime(maths:pow(2, 1024), maths:pow(2, 1025) - 1).
N = P * Q.
T = maths:lcm(P - 1, Q - 1).
E = 65537.
1 = maths:gcd(E, T).       % make sure e and t are co-primes
D = maths:mod_inv(E, T).
DP = maths:mod(D, P - 1).
DQ = maths:mod(D, Q - 1).
QI = maths:mod_inv(Q, P).

The next step is to convert the numbers to hexadecimal strings. Here is an Erlang one-liner for that

Erlang

[integer_to_list(X, 16) || X <- [N, E, D, P, Q, DP, DQ, QI]].

 n = 01D58729C5FFE1785360D7A2B532EAA6329C9B8BD95AF105422B40368630F636E1CB0B847D74798BD95249B42A47971BB5903FC87A97B7D541AC599961B8B0EB6CF24F7DFC798434EAE2E3D4E741D4FEC9C696208015205A50258B688A5475751B361C57CAEBE26DB3CF92AA4F4A69DD936E14A7A58072CFF461035ED9D448D1161E2C0DFFDF2A36B42CABC6B2D8FDACB7BC4C113890E69124E4FBD488AF9FBC5550C7586C5412E01A6DE9F2A8966E7C183C5A4CADD93E85FE6B1286211DEE62F29274358F569E20F169F1A2D01259710503AC6AD1DA8FC2C6C4C6933C78D1AE37DE30A0A84676FD11D95D43B5B93C032F52CEC2B1E636FC94E9FEA2F321A668FF
 e = 010001
 d = 2D426781C68B4810AC227274B50119742CD471994A1836EC37446BFD1375D30F2B860E0769D582E837F3BD8235D46DBF5AB5A09AF09FAFD6DCC8E642C7E2DB4EC282172037367498BA60EBD7943E4BDBCCB611514762B9A74577380F32DA54FCD7D7C8E9594397AA358AC0655444502F889F9A696C5AFA3611AE997E0B3B2F0185C60257E90D1955546F0190DF57F1674F0AD912BD8FFEAEAE65A79E0D9783E980E3C5CCC1B18D524296B806BDA4EC28DF028CCDA91FD94A89228EFA1B82A6B0B4C0A142EE7C890BE97C30F58232BEC26E897E25FC61B432CC651F82622132F3BE34E764623E4DD75DD469703C0081DCCE7F58C8A3DC72D46FB2BE548E5AF641
 p = 010CA88D97C90A5544D1CA63A5916B20CA2FC92C5CE2EB43409D953009630B322723D15581610A6CFE7686710A0086776C8929106646A4118CDC937E1B443F32D8B8255F4AB631D11C818D4D3411CF72D41780FC6354E6198BD6BE6D9790C12F6CB596B1C9BAC4F53B34C833375B60E1EC5EF71407FBA5229BDECEE38C8841432B
 q = 01BF67B98C4202D2BF8510B0F84752C26BF6C1E3C464B6678E612904F471A2D9E3A251B39416701F19290EC9957EA1EBB08ADABD3088018E7F81A57F3E287C3387EFDDC6ABBA7CDD446F089930071EDD3D06EB0D69AA334F23C7C7E8648AFC4C3C781BEBE6428949A2841E555B754685C2AAF2BA1E6F7F1A049CABFDC7FD5F577D
dp = 685B5CCCD5F1E69759EA84F47E5D1F9A8A1F59D526EBFDEEAE8791E6438BC8CA7D56462180815D3F26E928259B78A0110FE25C956DE13354052661B8D3B4BCDA84053853BC1BF3BF5FEF744AC2945365614FE039F17383FED6C697A965383564C3D0AA74D2D0C8F55B965C96A72F25F2FC1C7BB272247E220FD54B7C7E3CE38B
dq = 4572D7658335A6FB1DAFAA98CF91742688262EB1E4A43FCCE51E15EBCFDBE490A638A274814B2438A69BEA04AFA478CE6DAF68A0A8EBFCEFA3F3499E1F70B01B10CBCF3406FDACE71B892D263C64B918E9030190FE5F7A9066498CB456B2B52EC9C223CB1956F03C2EDFFA85F8DD5A940E2F215EEA15C3B7258EB9151B2A7A8D
qi = 89A217111B58DD54CCFB00C4873DB4EF6716283AEA77D2B46D85F1D8D47F2C0EC21AA37EBB26781C19EC43EB9583FB47205D83692D7CDCA9528B69C19EEFC100624A31907B33AFB9008C4685EB8AB709B890D7C6A6BD50BD41EE5A373FD31701F516FDB30C694243FBCB0851E237EA31703A2BC2A945EE5B9F12DCD574F3FBCB

Now we need to encode every number according to the ASN.1 DER. Let’s start with $n$. Under the DER, a value has three components: a type tag, a length in octets, and content. Since $n$ is an integer, its type tag is 0x02. The length of $n$ in octets is 257 = 0x0101. Since it’s greater than 127, we use the long format for the length. 0x0101 occupies 2 bytes, hence the length spec value is 2 = 0x02. To indicate that the length format is long we change its leftmost bit to 1, which gives us 0x82. The final length value is then 0x820101 and $n$’s final encoding is (with spaces added for readability)

n = 02 820101 01D58729C5FFE1785360D7A2B532EAA6329C9B8BD95AF105422B40368630F636E1CB0B847D74798BD95249B42A47971BB5903FC87A97B7D541AC599961B8B0EB6CF24F7DFC798434EAE2E3D4E741D4FEC9C696208015205A50258B688A5475751B361C57CAEBE26DB3CF92AA4F4A69DD936E14A7A58072CFF461035ED9D448D1161E2C0DFFDF2A36B42CABC6B2D8FDACB7BC4C113890E69124E4FBD488AF9FBC5550C7586C5412E01A6DE9F2A8966E7C183C5A4CADD93E85FE6B1286211DEE62F29274358F569E20F169F1A2D01259710503AC6AD1DA8FC2C6C4C6933C78D1AE37DE30A0A84676FD11D95D43B5B93C032F52CEC2B1E636FC94E9FEA2F321A668FF

Let’s encode $e$. Again, the tag value is 0x02. The length in octets is 3 = 0x03. Since it’s less than 128, we use the short format, without length spec. The final encoding is

e = 02 03 010001

Analogously we encode $d$, $p$, $q$, $dp$, and $dq$

 d = 02 820100 2D426781C68B4810AC227274B50119742CD471994A1836EC37446BFD1375D30F2B860E0769D582E837F3BD8235D46DBF5AB5A09AF09FAFD6DCC8E642C7E2DB4EC282172037367498BA60EBD7943E4BDBCCB611514762B9A74577380F32DA54FCD7D7C8E9594397AA358AC0655444502F889F9A696C5AFA3611AE997E0B3B2F0185C60257E90D1955546F0190DF57F1674F0AD912BD8FFEAEAE65A79E0D9783E980E3C5CCC1B18D524296B806BDA4EC28DF028CCDA91FD94A89228EFA1B82A6B0B4C0A142EE7C890BE97C30F58232BEC26E897E25FC61B432CC651F82622132F3BE34E764623E4DD75DD469703C0081DCCE7F58C8A3DC72D46FB2BE548E5AF641
 p = 02 8181 010CA88D97C90A5544D1CA63A5916B20CA2FC92C5CE2EB43409D953009630B322723D15581610A6CFE7686710A0086776C8929106646A4118CDC937E1B443F32D8B8255F4AB631D11C818D4D3411CF72D41780FC6354E6198BD6BE6D9790C12F6CB596B1C9BAC4F53B34C833375B60E1EC5EF71407FBA5229BDECEE38C8841432B
 q = 02 8181 01BF67B98C4202D2BF8510B0F84752C26BF6C1E3C464B6678E612904F471A2D9E3A251B39416701F19290EC9957EA1EBB08ADABD3088018E7F81A57F3E287C3387EFDDC6ABBA7CDD446F089930071EDD3D06EB0D69AA334F23C7C7E8648AFC4C3C781BEBE6428949A2841E555B754685C2AAF2BA1E6F7F1A049CABFDC7FD5F577D
dp = 02 8180 685B5CCCD5F1E69759EA84F47E5D1F9A8A1F59D526EBFDEEAE8791E6438BC8CA7D56462180815D3F26E928259B78A0110FE25C956DE13354052661B8D3B4BCDA84053853BC1BF3BF5FEF744AC2945365614FE039F17383FED6C697A965383564C3D0AA74D2D0C8F55B965C96A72F25F2FC1C7BB272247E220FD54B7C7E3CE38B
dq = 02 8180 4572D7658335A6FB1DAFAA98CF91742688262EB1E4A43FCCE51E15EBCFDBE490A638A274814B2438A69BEA04AFA478CE6DAF68A0A8EBFCEFA3F3499E1F70B01B10CBCF3406FDACE71B892D263C64B918E9030190FE5F7A9066498CB456B2B52EC9C223CB1956F03C2EDFFA85F8DD5A940E2F215EEA15C3B7258EB9151B2A7A8D

$qi$ is a bit trickier. Its leftmost bit is 1, so in ASN.1 it would be encoded as a negative integer. To keep it positive we have to prepend one byte of zeros to it. With this additional byte, the octet length becomes 129 = 0x81 and the final encoding is

qi = 02 8181 0089A217111B58DD54CCFB00C4873DB4EF6716283AEA77D2B46D85F1D8D47F2C0EC21AA37EBB26781C19EC43EB9583FB47205D83692D7CDCA9528B69C19EEFC100624A31907B33AFB9008C4685EB8AB709B890D7C6A6BD50BD41EE5A373FD31701F516FDB30C694243FBCB0851E237EA31703A2BC2A945EE5B9F12DCD574F3FBCB

After we encoded all RSA numbers, the only thing left from the PKCS #1 perspective is to encode the RSA version and the ASN.1 sequence. For a two-prime RSA key, the version is 0 which is encoded as

02 01 00

To encode the ASN.1 sequence, we need to calculate the total length of all the values we encoded so far. That will be the sequence’s content. If we concatenate all the values (version and RSA numbers), the total length in octets would be 1187 = 0x04A3. That means the sequence value is encoded as

30 8204A3

We can now put everything together. Here is the hexadecimal representation of our RSA private key (with line breaks added for readability):

rsa-private.hex

308204A30201000282010101D58729C5FFE1785360D7A2B532EAA6329C9B8BD9
5AF105422B40368630F636E1CB0B847D74798BD95249B42A47971BB5903FC87A
97B7D541AC599961B8B0EB6CF24F7DFC798434EAE2E3D4E741D4FEC9C6962080
15205A50258B688A5475751B361C57CAEBE26DB3CF92AA4F4A69DD936E14A7A5
8072CFF461035ED9D448D1161E2C0DFFDF2A36B42CABC6B2D8FDACB7BC4C1138
90E69124E4FBD488AF9FBC5550C7586C5412E01A6DE9F2A8966E7C183C5A4CAD
D93E85FE6B1286211DEE62F29274358F569E20F169F1A2D01259710503AC6AD1
DA8FC2C6C4C6933C78D1AE37DE30A0A84676FD11D95D43B5B93C032F52CEC2B1
E636FC94E9FEA2F321A668FF0203010001028201002D426781C68B4810AC2272
74B50119742CD471994A1836EC37446BFD1375D30F2B860E0769D582E837F3BD
8235D46DBF5AB5A09AF09FAFD6DCC8E642C7E2DB4EC282172037367498BA60EB
D7943E4BDBCCB611514762B9A74577380F32DA54FCD7D7C8E9594397AA358AC0
655444502F889F9A696C5AFA3611AE997E0B3B2F0185C60257E90D1955546F01
90DF57F1674F0AD912BD8FFEAEAE65A79E0D9783E980E3C5CCC1B18D524296B8
06BDA4EC28DF028CCDA91FD94A89228EFA1B82A6B0B4C0A142EE7C890BE97C30
F58232BEC26E897E25FC61B432CC651F82622132F3BE34E764623E4DD75DD469
703C0081DCCE7F58C8A3DC72D46FB2BE548E5AF641028181010CA88D97C90A55
44D1CA63A5916B20CA2FC92C5CE2EB43409D953009630B322723D15581610A6C
FE7686710A0086776C8929106646A4118CDC937E1B443F32D8B8255F4AB631D1
1C818D4D3411CF72D41780FC6354E6198BD6BE6D9790C12F6CB596B1C9BAC4F5
3B34C833375B60E1EC5EF71407FBA5229BDECEE38C8841432B02818101BF67B9
8C4202D2BF8510B0F84752C26BF6C1E3C464B6678E612904F471A2D9E3A251B3
9416701F19290EC9957EA1EBB08ADABD3088018E7F81A57F3E287C3387EFDDC6
ABBA7CDD446F089930071EDD3D06EB0D69AA334F23C7C7E8648AFC4C3C781BEB
E6428949A2841E555B754685C2AAF2BA1E6F7F1A049CABFDC7FD5F577D028180
685B5CCCD5F1E69759EA84F47E5D1F9A8A1F59D526EBFDEEAE8791E6438BC8CA
7D56462180815D3F26E928259B78A0110FE25C956DE13354052661B8D3B4BCDA
84053853BC1BF3BF5FEF744AC2945365614FE039F17383FED6C697A965383564
C3D0AA74D2D0C8F55B965C96A72F25F2FC1C7BB272247E220FD54B7C7E3CE38B
0281804572D7658335A6FB1DAFAA98CF91742688262EB1E4A43FCCE51E15EBCF
DBE490A638A274814B2438A69BEA04AFA478CE6DAF68A0A8EBFCEFA3F3499E1F
70B01B10CBCF3406FDACE71B892D263C64B918E9030190FE5F7A9066498CB456
B2B52EC9C223CB1956F03C2EDFFA85F8DD5A940E2F215EEA15C3B7258EB9151B
2A7A8D0281810089A217111B58DD54CCFB00C4873DB4EF6716283AEA77D2B46D
85F1D8D47F2C0EC21AA37EBB26781C19EC43EB9583FB47205D83692D7CDCA952
8B69C19EEFC100624A31907B33AFB9008C4685EB8AB709B890D7C6A6BD50BD41
EE5A373FD31701F516FDB30C694243FBCB0851E237EA31703A2BC2A945EE5B9F
12DCD574F3FBCB

We just need to convert this octet string to list of bytes and this will give us the RSA private key in DER format

$ xxd -r -p rsa-private.hex rsa-private.der

If you want the key in PEM format, just base64 encode the DER file

$ base64 -b 64 -i rsa-private.der

and encapsulate it with the RSA PRIVATE KEY boundary. Here is the final result