37
$\begingroup$

I was researching about how to encrypt with RSA. I understood everything but not the format of the private keys.

In the phpseclib (RSA in PHP), you can import your private key (private.key format) and in the key file there is text like this:

-----BEGIN RSA PRIVATE KEY-----
MIIBOQIBAAJBAIOLepgdqXrM07O4dV/nJ5gSA12jcjBeBXK5mZO7Gc778HuvhJi+
RvqhSi82EuN9sHPx1iQqaCuXuS1vpuqvYiUCAwEAAQJATRDbCuFd2EbFxGXNxhjL
loj/Fc3a6UE8GeFoeydDUIJjWifbCAQsptSPIT5vhcudZgWEMDSXrIn79nXvyPy5
BQIhAPU+XwrLGy0Hd4Roug+9IRMrlu0gtSvTJRWQ/b7m0fbfAiEAiVB7bUMynZf4
SwVJ8NAF4AikBmYxOJPUxnPjEp8D23sCIA3ZcNqWL7myQ0CZ/W/oGVcQzhwkDbck
3GJEZuAB/vd3AiASmnvOZs9BuKgkCdhlrtlM6/7E+y1p++VU6bh2+mI8ZwIgf4Qh
u+zYCJfIjtJJpH1lHZW+A60iThKtezaCk7FiAC4= 
-----END RSA PRIVATE KEY-----

But when I decode this with Base64 and then convert it to decimal it is just one number... I thought you need both $p$ and $q$! My question:

If I roll a dice (with 0 and 1) 1024 times and find the nearest prime number it would be my $p$ and I would do this process again so I get $q$, but how do I convert those numbers to the private.key format? And what's the difference?

$\endgroup$
  • 20
    $\begingroup$ Just a small note: You published your private key on the internet. Now it's insecure and you have to generate a new one. $\endgroup$ – Nova Dec 31 '14 at 14:06
  • $\begingroup$ See also What data is saved in RSA private key? $\endgroup$ – Vadzim Feb 6 '18 at 16:44
33
$\begingroup$

Copy / paste that key into http://phpseclib.sourceforge.net/x509/asn1parse.php and you'll see that there are several different integers in there. $p$ is there, $q$ is there as is the exponent and several other integers to speed things up by taking advantage of the Chinese Remainder Theorem.

The key is encoded using DER and derives semantic meaning via ASN.1. The following URL elaborates:

http://tools.ietf.org/html/rfc3447#appendix-C

Quoting I understand the mathematics of RSA encryption: How are the files in ~/.ssh related to the theory?:

The ASN.1 syntax for that DER-encoded string is described in RFC3447 (aka PKCS1):

  Version ::= INTEGER { two-prime(0), multi(1) }
      (CONSTRAINED BY
      {-- version must be multi if otherPrimeInfos present --})

  RSAPrivateKey ::= SEQUENCE {
      version           Version,
      modulus           INTEGER,  -- n
      publicExponent    INTEGER,  -- e
      privateExponent   INTEGER,  -- d
      prime1            INTEGER,  -- p
      prime2            INTEGER,  -- q
      exponent1         INTEGER,  -- d mod (p-1)
      exponent2         INTEGER,  -- d mod (q-1)
      coefficient       INTEGER,  -- (inverse of q) mod p
      otherPrimeInfos   OtherPrimeInfos OPTIONAL
  }

DER encoding uses a tag-length-value notation. So here's a sample private key:

-----BEGIN RSA PRIVATE KEY-----
MIICXAIBAAKBgQCqGKukO1De7zhZj6+H0qtjTkVxwTCpvKe4eCZ0FPqri0cb2JZfXJ/DgYSF6vUp
wmJG8wVQZKjeGcjDOL5UlsuusFncCzWBQ7RKNUSesmQRMSGkVb1/3j+skZ6UtW+5u09lHNsj6tQ5
1s1SPrCBkedbNf0Tp0GbMJDyR4e9T04ZZwIDAQABAoGAFijko56+qGyN8M0RVyaRAXz++xTqHBLh
3tx4VgMtrQ+WEgCjhoTwo23KMBAuJGSYnRmoBZM3lMfTKevIkAidPExvYCdm5dYq3XToLkkLv5L2
pIIVOFMDG+KESnAFV7l2c+cnzRMW0+b6f8mR1CJzZuxVLL6Q02fvLi55/mbSYxECQQDeAw6fiIQX
GukBI4eMZZt4nscy2o12KyYner3VpoeE+Np2q+Z3pvAMd/aNzQ/W9WaI+NRfcxUJrmfPwIGm63il
AkEAxCL5HQb2bQr4ByorcMWm/hEP2MZzROV73yF41hPsRC9m66KrheO9HPTJuo3/9s5p+sqGxOlF
L0NDt4SkosjgGwJAFklyR1uZ/wPJjj611cdBcztlPdqoxssQGnh85BzCj/u3WqBpE2vjvyyvyI5k
X6zk7S0ljKtt2jny2+00VsBerQJBAJGC1Mg5Oydo5NwD6BiROrPxGo2bpTbu/fhrT8ebHkTz2epl
U9VQQSQzY1oZMVX8i1m5WUTLPz2yLJIBQVdXqhMCQBGoiuSoSjafUhV7i1cEGpb88h5NBYZzWXGZ
37sJ5QsW+sJyoNde3xH8vdXhzU7eT82D6X/scw9RZz+/6rCJ4p0=
-----END RSA PRIVATE KEY-----

Here's the hex encoding:

3082025c02010002818100aa18aba43b50deef38598faf87d2ab634e4571c130a9bca7b878267414
faab8b471bd8965f5c9fc3818485eaf529c26246f3055064a8de19c8c338be5496cbaeb059dc0b35
8143b44a35449eb264113121a455bd7fde3fac919e94b56fb9bb4f651cdb23ead439d6cd523eb081
91e75b35fd13a7419b3090f24787bd4f4e196702030100010281801628e4a39ebea86c8df0cd1157
2691017cfefb14ea1c12e1dedc7856032dad0f961200a38684f0a36dca30102e2464989d19a80593
3794c7d329ebc890089d3c4c6f602766e5d62add74e82e490bbf92f6a482153853031be2844a7005
57b97673e727cd1316d3e6fa7fc991d4227366ec552cbe90d367ef2e2e79fe66d26311024100de03
0e9f8884171ae90123878c659b789ec732da8d762b26277abdd5a68784f8da76abe677a6f00c77f6
8dcd0fd6f56688f8d45f731509ae67cfc081a6eb78a5024100c422f91d06f66d0af8072a2b70c5a6
fe110fd8c67344e57bdf2178d613ec442f66eba2ab85e3bd1cf4c9ba8dfff6ce69faca86c4e9452f
4343b784a4a2c8e01b0240164972475b99ff03c98e3eb5d5c741733b653ddaa8c6cb101a787ce41c
c28ffbb75aa069136be3bf2cafc88e645face4ed2d258cab6dda39f2dbed3456c05ead0241009182
d4c8393b2768e4dc03e818913ab3f11a8d9ba536eefdf86b4fc79b1e44f3d9ea6553d55041243363
5a193155fc8b59b95944cb3f3db22c9201415757aa13024011a88ae4a84a369f52157b8b57041a96
fcf21e4d058673597199dfbb09e50b16fac272a0d75edf11fcbdd5e1cd4ede4fcd83e97fec730f51
673fbfeab089e29d

The 30 is because it's a SEQUENCE tag. The 82025c represents the length. The first byte means the length is of the "long form" (82 & 80) and that the next two bytes represent the length (82 & 7F). So the actual length of the SEQUENCE is 025c. So after that is the value.

Then you get to the version. 02 is of type int, 01 is the tag length and 00 is the value. ie. it's a two-prime key as opposed to a multi-prime key.

More info on the Distinguished Encoding Rules.

Trying to understand ASN.1 is a lot more complicated and a lot of it, for the purpose of understanding the formatting of RSA private keys, is unnecessary. For X.509 it becomes more necessary but RSA keys aren't nearly as complicated, formatting-wise, as X.509 certs.

Hope that helps!

$\endgroup$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – e-sushi Jun 9 '17 at 23:36
24
$\begingroup$

It is correct that the given private key does not encode a single integer, and that it includes two primes $p$ and $q$. More precisely, that Base64 data encodes a string of bytes, which is an RSAPrivateKey encoded per ASN.1 DER-TLV (and thus BER-TLV) following PKCS#1v2.2 Appendix A.1.2 (likely restricted to version 0). It decodes to:

  • 30 ASN.1 tag for sequence, a BER-TLV tag (Application class, Constructed encoding, Tag number 0)
  • 82 01 39 Length as prefix plus two bytes, of 0x139 = 313 (number of bytes following)
    • 02 ASN.1 tag for int, also a BER-TLV tag (Universal class, Primitive encoding, Tag number 2)
    • 01 Length encoded on one byte, of 0x01 = 1
      • 00 Version 0, meaning RSA private key with 2 primes
    • 02 ASN.1 tag for int
    • 41 Length encoded on one byte, of 0x41 = 65
      • 00 83 8B 7A 98 1D A9 7A CC D3 B3 B8 75 5F E7 27 98 12 03 5D A3 72 30 5E 05 72 B9 99 93 BB 19 CE FB F0 7B AF 84 98 BE 46 FA A1 4A 2F 36 12 E3 7D B0 73 F1 D6 24 2A 68 2B 97 B9 2D 6F A6 EA AF 62 25 public modulus $n$ (big-endian, leftmost bit is sign)
    • 02 ASN.1 tag for int
    • 03 Length encoded on one byte, of 0x03 = 3
      • 01 00 01 public exponent $e$ (big-endian, leftmost bit is sign)
    • 02 ASN.1 tag for int
    • 40 Length encoded on one byte, of 0x40 = 64
      • 4D 10 DB 0A E1 5D D8 46 C5 C4 65 CD C6 18 CB 96 88 FF 15 CD DA E9 41 3C 19 E1 68 7B 27 43 50 82 63 5A 27 DB 08 04 2C A6 D4 8F 21 3E 6F 85 CB 9D 66 05 84 30 34 97 AC 89 FB F6 75 EF C8 FC B9 05 private exponent $d$ (big-endian, leftmost bit is sign)
    • 02 ASN.1 tag for int
    • 21 Length encoded on one byte, of 0x21 = 33
      • 00 F5 3E 5F 0A CB 1B 2D 07 77 84 68 BA 0F BD 21 13 2B 96 ED 20 B5 2B D3 25 15 90 FD BE E6 D1 F6 DF secret prime $p$ (big-endian, leftmost bit is sign)
    • 02 ASN.1 tag for int
    • 21 Length encoded on one byte, of 0x21 = 33
      • 00 89 50 7B 6D 43 32 9D 97 F8 4B 05 49 F0 D0 05 E0 08 A4 06 66 31 38 93 D4 C6 73 E3 12 9F 03 DB 7B secret prime $q$ (big-endian, leftmost bit is sign)
    • 02 ASN.1 tag for int
    • 20 Length encoded on one byte, of 0x20 = 32
      • 0D D9 70 DA 96 2F B9 B2 43 40 99 FD 6F E8 19 57 10 CE 1C 24 0D B7 24 DC 62 44 66 E0 01 FE F7 77 $dp=d\bmod(p-1)$ (big-endian, leftmost bit is sign)
    • 02 ASN.1 tag for int
    • 20 Length encoded on one byte, of 0x20 = 32
      • 12 9A 7B CE 66 CF 41 B8 A8 24 09 D8 65 AE D9 4C EB FE C4 FB 2D 69 FB E5 54 E9 B8 76 FA 62 3C 67 $dq=d\bmod(q-1)$ (big-endian, leftmost bit is sign)
    • 02 ASN.1 tag for int
    • 20 Length encoded on one byte, of 0x20 = 32
      • 7F 84 21 BB EC D8 08 97 C8 8E D2 49 A4 7D 65 1D 95 BE 03 AD 22 4E 12 AD 7B 36 82 93 B1 62 00 2E $q_\text{inv}=q^{-1}\bmod p$ (big-endian, leftmost bit is sign)

Therefore, this private keys has:

  • $n$ = 6889562268374622799957651484276189567066573692163081374402850932375514118031048420110853972747558241305562483958233191802399592639320405757333978594894373
  • $e$ = 65537
  • $d$ = 4036265671212347870735218712159303880670782869380678233214786480134242711167668040594757438422211656546040377235338723652323162649874081271989898105895173
  • $p$ = 110926848377808511478526072563819593239744031998335766139683653481372583065311
  • $q$ = 62109059881601353504240950986730444628975000449359215027377545384004575026043
  • $dp$ = 6264251733315063261699879374379301990940883202249731761950794231267222026103
  • $dq$ = 8414580201851449070969916288679366126930879182597013446268294634551118019687
  • $q_\text{inv}$ = 57677188406707620788831013172875873422122983590947547357547002213122938372142

As expected, these values verify:

  • $n=p\cdot q$
  • $e\cdot d\equiv 1\pmod{\operatorname{lcm}(p-1,q-1)}$
  • $dp=e^{-1}\bmod(p-1)=d\bmod(p-1)$
  • $dq=e^{-1}\bmod(q-1)=d\bmod(q-1)$
  • $q_\text{inv}=q^{-1}\bmod p$

The public modulus $n$ is 512-bit, which is too small to be safe.


If one draws $p$ and $q$ using 1024 dice throws for each, rounding to the nearest lower prime, $p$ and $q$ are about (and at most) 1024-bit each, thus the public modulus $n$ about 2048-bit, which is safe. With overwhelming odds, $p$ and $q$ are distinct.

It is customary and recommended to ensure that $n$ has exactly $k$ bits with $k$ a multiple of some power of two at least 64, and towards that goal to choose $p$ and $q$ above $2^{(k-1)/2}$.

It is customary and unobjectionable to choose $e=2^{16}+1=65537$, and towards that goal to choose $p$ and $q$ such that $p\not\equiv1\pmod{65537}$ and $q\not\equiv1\pmod{65537}$.

Afterwards, one

  • computes $n$, $d$, $dp$, $dq$, $q_\text{inv}$, $d$; for $d$, among other options, one can
    • compute $d=e^{-1}\bmod((p-1)\cdot(q-1))$ as in the private key above,
    • compute $d=e^{-1}\bmod(\operatorname{lcm}(p-1,q-1))$ for a slightly smaller $d$,
    • build $d$ from $dp$ and $dq$;
  • encodes the private key per ASN.1 DER-TLV following PKCS#1v2 Appendix A.1.2, as above;
  • converts to Base64;
  • adds -----BEGIN RSA PRIVATE KEY----- and -----END RSA PRIVATE KEY----- delimiters;
  • adds line breaks as appropriate (including at least before and after each delimiter, except that a newline is not necessary at start of file).

Easily missed rules when encoding to ASN.1 DER-TLV by induction from example:

  • length encoding (in the context of RSA, all length are usually in range [1..0xFFFF], but some implementations have a lower size restriction)
    • any length from 0 up to 0x7F is encoded as one byte in 00..7F;
    • any higher length up to 0xFF is encoded as prefix 81 and one byte;
    • any higher length up to 0xFFFF is encoded as prefix 82 and two bytes;
    • any higher length up to 0xFFFFFF is encoded as prefix 83 and three bytes;
    • any higher length up to 0xFFFFFFFF is encoded as prefix 84 and four bytes;
    • the rule goes on for higher lengths, but some standards (including ISO/IEC 7816-4:2013, appendix E.2) explicitly exclude these.
  • the byte representation of a non-negative integer must be the shortest big-endian byte representation with leftmost sign bit; therefore:
    • it starts with a byte in range 00..7F;
    • and if that first byte is 00, then the next byte (if present) must be in range 80..FF.
$\endgroup$
  • $\begingroup$ Wouldn't each roll of a fair, 6-sided die contribute $\log_2(6) \approx 2.6$ bits to each number, or about 2647 bits after 1024 rolls? $\endgroup$ – neirbowj Jul 29 '17 at 14:13
9
$\begingroup$

To conclude the answers here's a note about the simplest way (on linux at least) to view the contents of such keys with openssl:

$ openssl rsa -in test.key -text
Private-Key: (512 bit)
modulus:
    00:83:8b:7a:98:1d:a9:7a:cc:d3:b3:b8:75:5f:e7:
    27:98:12:03:5d:a3:72:30:5e:05:72:b9:99:93:bb:
    19:ce:fb:f0:7b:af:84:98:be:46:fa:a1:4a:2f:36:
    12:e3:7d:b0:73:f1:d6:24:2a:68:2b:97:b9:2d:6f:
    a6:ea:af:62:25
publicExponent: 65537 (0x10001)
privateExponent:
    4d:10:db:0a:e1:5d:d8:46:c5:c4:65:cd:c6:18:cb:
    96:88:ff:15:cd:da:e9:41:3c:19:e1:68:7b:27:43:
    50:82:63:5a:27:db:08:04:2c:a6:d4:8f:21:3e:6f:
    85:cb:9d:66:05:84:30:34:97:ac:89:fb:f6:75:ef:
    c8:fc:b9:05
prime1:
    00:f5:3e:5f:0a:cb:1b:2d:07:77:84:68:ba:0f:bd:
    21:13:2b:96:ed:20:b5:2b:d3:25:15:90:fd:be:e6:
    d1:f6:df
prime2:
    00:89:50:7b:6d:43:32:9d:97:f8:4b:05:49:f0:d0:
    05:e0:08:a4:06:66:31:38:93:d4:c6:73:e3:12:9f:
    03:db:7b
exponent1:
    0d:d9:70:da:96:2f:b9:b2:43:40:99:fd:6f:e8:19:
    57:10:ce:1c:24:0d:b7:24:dc:62:44:66:e0:01:fe:
    f7:77
exponent2:
    12:9a:7b:ce:66:cf:41:b8:a8:24:09:d8:65:ae:d9:
    4c:eb:fe:c4:fb:2d:69:fb:e5:54:e9:b8:76:fa:62:
    3c:67
coefficient:
    7f:84:21:bb:ec:d8:08:97:c8:8e:d2:49:a4:7d:65:
    1d:95:be:03:ad:22:4e:12:ad:7b:36:82:93:b1:62:
    00:2e

If you have only a public RSA key - just add -pubin flag to openssl.

$\endgroup$
  • $\begingroup$ To answer your last question I can share a Python script: pastie.org/9808687 though I am not sure if it is the best method for stackexchange.. $\endgroup$ – Hyperflame Jan 1 '15 at 22:26
3
$\begingroup$

What about the beautiful images on this page, Certificate Binary Posters part 1 and part 2? I'd believe they would be useful in this case.

$\endgroup$
0
$\begingroup$

Actually, the Base64 string doesn't contain just the private key but a specific data structure with additional information. In particular, your data contains a RSAPrivateKey object, which contains several values, including primes p and q. You can see a description of that object here.

$\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.