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 int41 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 int03 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 int40 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 int21 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 int21 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 int20 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 int20 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 int20 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.
