The security megathread: Detailed info about keypairs, encryption, and more

[NotATether]

I decided to create a single thread where I can explain all security related stuff such as public key cryptography, RSA, AES etc etc all in one place and also list some best practices when writing cryptography related code and helpful information for developers who want to get started writing code involving cryptography no matter what language you work in.

I feel that there is an urgent need for security documentation to be readily accessible because too many people are writing poorly secured programs, especially the ones related to cryptocurrency, which have basic known vulnerabilities in them and causes their users to get hacked later and their money stolen. Having a thread like this available is beneficial to everybody.

So far today I have one topic ready for publishing and that is about public and private keys. More topics will be added at the bottom of this posts and in the reserved posts below.

The types and structure of public and private keys

Status: Work-in-progress

This thread is intended to assist people learning how to use public key cryptography, and developers trying to add public key cryptography to their applications. It will go over many types of private keys including RSA, Ed25519 elliptical curve keys, SSH keys, TLS/HTTPS, PGP keys and bitcoin private keys, as well as other keys which are widely used. I will also show you their composition and what's exactly inside each public and private key.

Public keys and private keys are data structures hat have different fields in them depending on their type. Sometimes you will see different representations of the same private key. For example, Bitcoin's use of numbers as private keys is just a covert representation of elliptical curve private keys, and the Wallet Import Format, or WIF, is an encoding of a bitcoin private key using letters and numbers, and a leading '5'.

First you need to know some preliminary information about public and private keys.

What are public and private keys

A public key is a piece of data that you share with everyone, which identifies the access being granted, while the private key is secret data that grants access to the resources protected by the public key. They are always generated in pairs, that's why you'll sometimes hear them called keypairs when referring to both of them. Think of the public key as a door lock or car lock and the private key being the "key" that unlocks it.

I called them "pieces of data" because some types of keypairs represent them as exponents and primes, others represent each as a single large number. Basically any cryptographic authentication scheme which splits the login into a public part and a private part has some kind of public and private key.

Private keys are always generated from operating-system provided entropy. Operating systems usually use a hardware random number generator to get the bits and then pass them through a second random number generator in the kernel for extra security. This ensures that they are random and not predictable.


Image source: https://en.wikipedia.org/wiki/Public-key_cryptography

Why are public and private keys necessary

Suppose you paid for access to a computing resource. The vendor needs a way to securely provide you the login information to your resource. A lot of them use passwords for this task but the disadvantage of using passwords is that anyone who remembers what your password is can access your resource. There also exist brute-forcing programs for passwords.


These problems are partially mitigated by providing you a private key. First of all, private keys are not human-readable, so someone can't just glance behind your shoulder and remember them. Second, private keys take exponentially more time to brute-force than a medium-length password (you need a password length of about 311 ASCII characters to provide the equivalent security of an RSA-2048 private key, and 622 characters for RSA-4096 key). The only way somebody can possibly know your private key is if they physically steal it from you.

Now we are in a position to explain the different kind of keypairs you will encounter.

1. 2048-bit RSA

Code in this section is credited to
https://rietta.com/blog/openssl-generating-rsa-key-from-command/
https://stackoverflow.com/a/20352821/12452330

This is the most common type of keypair that people use. It is reasonably fast to generate while having enough bits of entropy to resist attacks from organized crime groups and state intelligence agencies. RSA keys in general password-protect the private key, which can be anything from 4 to 1023 characters long. The password is required when extracting the public key from it or for authentication.

You can make these keys on the Linux command line like this:

Code:

openssl genrsa -des3 -out private.pem 2048 #private key
openssl rsa -in private.pem -outform PEM -pubout -out public.pem #public key

This is the error you get if you type the wrong password.

Code:

$ openssl rsa -in private.pem -outform PEM -pubout -out public.pem
Enter pass phrase for private.pem:
unable to load Private Key
140026615993536:error:06065064:digital envelope routines:EVP_DecryptFinal_ex:bad decrypt:crypto/evp/evp_enc.c:583:
140026615993536:error:0906A065:PEM routines:PEM_do_header:bad decrypt:crypto/pem/pem_lib.c:461:

Sometimes you will see vendors giving you private keys without password protection (they also only let you download the private key once, and claim to destroy it from their servers when you finish downloading it). This is how you strip password protection from a private key:

Code:

openssl rsa -in private.pem -out private_unencrypted.pem -outform PEM

Contents of 2048-bit RSA keypairs

Each of these files is in human readable PEM format.

public.pem: starts with BEGIN PUBLIC KEY and ends with END PUBLIC KEY

Code:

-----BEGIN PUBLIC KEY-----
MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEAs89ZZGKv2lle+/itDyWY
HjJ1AuP1BaVhZLOcROJmsfhnq/ThRb/z6QOOpq0pbxLMdSGibORfbVwclnVC72ie
raWJNf06fuVCEvsgny3scEwP/ulc4k4EndgkPeMCDpcbRnF8pWNaBVYSrWg5psz4
uJCcrGFYZ+AAhZZVgSPFu3RjSqsWln0BNRs/CuDA9PqECmNZEPXLy+hcFR9+ix9x
xoKh5CuoGLdrz+EViUHOiotw9o2AEDIKCyo8bK4S9dY/5mZhxk+/tK7qgyoVixK5
bnEegJKt9P6Jdq6KtSKCJZHTs9ZArfRjeyjjD6E5tMp/LiCWmEHGmeMmN3foWhw4
ZQIDAQAB
-----END PUBLIC KEY-----

private.pem: starts with BEGIN RSA PRIVATE KEY, ends with END RSA PRIVATE KEY, and has ENCRYPTED in the second line.

Code:

-----BEGIN RSA PRIVATE KEY-----
Proc-Type: 4,ENCRYPTED
DEK-Info: DES-EDE3-CBC,9B618056BEFE7CBE

0vm09rYDjBIe2mNKA/mV/r6O+DbD/zzw1C1NrJNoX+OgdrVve7T4q7wehmsPu8Mg
qa4HbNtiINQMRXiQGNCEbW8MmcvWOOMUr2cF1fEj4mScV4xxtZzubf2/B1v/TZbN
zNRbw57+/l2DKrTEX0lyje4U9IWjD2JlGvrPUdE5NNx6qQpstfORzYvq+XCWuvnY
hzWvWEkc1SdBS10N78NqSVHl1LsAGpTgtqfQDj1Wd7v2k3kdjzI2Aw5bSGhB+btK
JAUB6ILCO0jhcW0J5jwEdQnsnw9QlXFxdgIbeWdMycQ6vq7dgMYyYrlIu9vMdiVC
U87Jwn84Tzp+nsrizsxu+QDDUNOUgeZlMUyZcA58UReZB7R84XqevP5btdiFt6eE
sJJwiTJfxhsNvARYg8ZWpRLOWPxmA3tzdNu486yUlapGYMUi5z33U5iox6jVUWk3
fVGcConma8xSe220zEzdjwq2P2+08Qz5dfiRgjOfdSXxYtNWI7CiJDWJQv2tB+lL
y+2DlrB7JYvFsmmpsjyIXkcWHEYN6mYKlCSHWyFGrEXqYie5nCjXfo185lYqH9x2
h4+sB1wcmlR3jbVN1c6J1kdXoEKSYVSvDCX7/GJS4uvqgvqgUqgIVdxL0M4pAM+A
dEoOdv8Y6E6MDsB2zIrXU6eXaWR1IJkcpqrq/Ip6uXTD7oLGaPl/MDeZLM4CbL6R
/5w9rEn41exzU8NFRthhqUQ1Kp7Qx/cM8tyUO7vvKvkhj9vMg3pG4neL3NJXnujH
WGUt+UAu8tyPIdJgRuqWrdg8KOEp5asELImckEKVgrWKLpySJ0t4iSJYrJCI5Tk4
FPgAa8+ie54XaGYAfN3vaQq4lymCpd36+voqeMNBPVOBBdzz7rsSHTNfHJB83fH+
+CBpEKlJmy/GFUOKHw0ZS06hpgzMcrLgAsKznW+muvUdcExGS/xivEMlFy7K98J+
qoig2dWVgeOE4TtQYK5W7ZcnIyQMET3PWEzSbP7cUr6Fk3ad9Pw6HYU5Lp62d9E5
9YH/3LomXSqHvyuTylD7n5UeV1oB/HMwHnhSBOpaDlACPtaTrNcvmo08TfZCvb8x
EI6qTZKVQyxvLKSUxkMUupjPZ516iUyh2+OUMEB8WmM4na0g8AaGKkIfZjIEHSSY
wag+wkOuleWx/f5Q+bVFwzaUiz0z+lYn1OEjq3z9OJX7JSBV9ZFLFzMn/mFhjEJl
1JiKsowO6hB7upOEZxyMhrU1x+qtFH2JQEuSaF4u6lbfoCvkNQYxzbyUaIMc7h6G
B5LwsIfDYDi5YG402BRBcHGqGXf6kq+LXpEz/awiXDdMy213LRO9pDBc5AMuRiJI
JYxohhuo6eupgio+zRkyQ6xkfWPEY48bhn3n4VTBF5rJ1Uvaog51XqzyegH6fgQ9
uev17Hmj86QYyRA0t5fRgykGnvDFa552Eg6fRxH1yfxlsJch7xHKdV89baiBnunB
H9wp5ubpK2q5JSBuZManfNyS1X8M30+NSBPVsba6Zfz4cpEC2rxeDt3PY/a1CUYE
zxfPvlwAM/rJV4NXygoWOvUslezwuJg96Az6Dcm0/RSC8/Op62ckew==
-----END RSA PRIVATE KEY-----

private_unencrypted.pem: Same as private.pem but without the second ENCRYPTED line.

Code:

-----BEGIN RSA PRIVATE KEY-----
MIIEowIBAAKCAQEAs89ZZGKv2lle+/itDyWYHjJ1AuP1BaVhZLOcROJmsfhnq/Th
Rb/z6QOOpq0pbxLMdSGibORfbVwclnVC72ieraWJNf06fuVCEvsgny3scEwP/ulc
4k4EndgkPeMCDpcbRnF8pWNaBVYSrWg5psz4uJCcrGFYZ+AAhZZVgSPFu3RjSqsW
ln0BNRs/CuDA9PqECmNZEPXLy+hcFR9+ix9xxoKh5CuoGLdrz+EViUHOiotw9o2A
EDIKCyo8bK4S9dY/5mZhxk+/tK7qgyoVixK5bnEegJKt9P6Jdq6KtSKCJZHTs9ZA
rfRjeyjjD6E5tMp/LiCWmEHGmeMmN3foWhw4ZQIDAQABAoIBADzYgJZwsrM/pN29
I8rJXPVy+5eTzhkwAooSIWJJ/phgx6wvvH9e2knSc1ZBqJC2mstUK2OP0B7wmZfs
bE8ZZwC50HmdjEreh4Jmyn4zCxxhENSg4VaPMg670l/CzrJjPc6TnqtUuGSv4Lgf
Wcrw94V1Ih9O/ZyA94w8+AgwM7wfr2mSidVtF1pOyGEu1w7Pq7bTA/RUNw9H4taA
vyWcKslyDkr8DfRQnZ3G2l9TrnYzv8Yg8c6lJ5SjOxfMLzadCfJpwGDhgn0dXqTN
XlMTM7vI2r3U1qtbTu4/XnqnHbPzwpS8583P9UunMX87WeXi5pUkLPlxHDPxm3RP
CsiTr00CgYEA7nmlBu3Up2NpWnfAxIuXGjSTqoxoQaZUm4sMtwBZIdIOWA6j7xla
OY+0XalXqXy0/MG9tDeCc1VVU3sGccXB5S5gsSCpzHKHjD+ZI6sKrJRFtAZzDepY
cn64xTk+nYA2DsxSfaZQuSYAMwS7ybCcg+MO4uRTNUQsEzKEMoV1Z78CgYEAwQYO
FztUgGGeGXG9FxHSkjhcdQb4I6hvTtTbXPrhpIndDHICfQZaUqAqOSAD185tSA3J
UjSzEn5YI7MziWA8bUl/LRcTbKdzFbMWdJOzJmjf/wiq22JqCYOWLtRgMHluHf3D
0muqmgydLs7rAvZUaoCz96zjr7GOrdR/jAwxiNsCgYAjGYhuoqbAFGO3SxT2WM1e
sApj+dKGhyLA2hB/BvAXiEFQOKdsU8Dx4/LaLkiWy6If6awwUFNFAnRSmzLxn/fP
8amNqI8VZm4I+HtjwpMJn7E6tBBPJgTqpTgw3yIWMH7EYtJpaAdNmQhCehnhr7r5
tnvEbXLJzkTmdnL6tKX5JQKBgCs8h/t8NrlrJFbeu1RnkZtfNJaiMQMLv6MQ2vJA
4DpTB0i6YQRQX/sSFWMmYLX+b0wsimP3mgUSd/vHMEwdWmvAgtQ+zwMPnx/FNcp3
KzH3W/Vso5jwun/XEdT7jXBOQvRE25BOvbA0EyFhCBNpyg7xNV7NQ1Mfmq4lY0yj
jpTxAoGBAInPJA2Jdt1x8JxB7P8SU2n+qC8TAJC11NuLPFc5eOPXbG5LLehvAu5k
T/cLW2X2mTb6ladqTzYStNjZcK2IqwJ/ZEahyC/KWimYG50+DgTM8oWaPVwnUhr+
TXb+6K7HnP2QNF2BhC6g8vx9sflapE9eQ4WyyByz5tusF3dEucc5
-----END RSA PRIVATE KEY-----

Now I will decode the PEM data into the mathematical variables stored inside.

An RSA public key has a modulus and a publicExponent.
An RSA private key has a modulus, publicExponent, privateExponent, prime1, prime2, exponent1, exponent2 and coefficient.

public.pem:

Code:

openssl rsa -pubin -in public.pem -text -noout

Code:

RSA Public-Key: (2048 bit)
Modulus:
    00:b3:cf:59:64:62:af:da:59:5e:fb:f8:ad:0f:25:
    98:1e:32:75:02:e3:f5:05:a5:61:64:b3:9c:44:e2:
    66:b1:f8:67:ab:f4:e1:45:bf:f3:e9:03:8e:a6:ad:
    29:6f:12:cc:75:21:a2:6c:e4:5f:6d:5c:1c:96:75:
    42:ef:68:9e:ad:a5:89:35:fd:3a:7e:e5:42:12:fb:
    20:9f:2d:ec:70:4c:0f:fe:e9:5c:e2:4e:04:9d:d8:
    24:3d:e3:02:0e:97:1b:46:71:7c:a5:63:5a:05:56:
    12:ad:68:39:a6:cc:f8:b8:90:9c:ac:61:58:67:e0:
    00:85:96:55:81:23:c5:bb:74:63:4a:ab:16:96:7d:
    01:35:1b:3f:0a:e0:c0:f4:fa:84:0a:63:59:10:f5:
    cb:cb:e8:5c:15:1f:7e:8b:1f:71:c6:82:a1:e4:2b:
    a8:18:b7:6b:cf:e1:15:89:41:ce:8a:8b:70:f6:8d:
    80:10:32:0a:0b:2a:3c:6c:ae:12:f5:d6:3f:e6:66:
    61:c6:4f:bf:b4:ae:ea:83:2a:15:8b:12:b9:6e:71:
    1e:80:92:ad:f4:fe:89:76:ae:8a:b5:22:82:25:91:
    d3:b3:d6:40:ad:f4:63:7b:28:e3:0f:a1:39:b4:ca:
    7f:2e:20:96:98:41:c6:99:e3:26:37:77:e8:5a:1c:
    38:65
Exponent: 65537 (0x10001)

private.pem and private_unencrypted.pem (doesn't matter):

Code:

openssl rsa -in private.pem -text -noout

Code:

RSA Private-Key: (2048 bit, 2 primes)
modulus:
    00:b3:cf:59:64:62:af:da:59:5e:fb:f8:ad:0f:25:
    98:1e:32:75:02:e3:f5:05:a5:61:64:b3:9c:44:e2:
    66:b1:f8:67:ab:f4:e1:45:bf:f3:e9:03:8e:a6:ad:
    29:6f:12:cc:75:21:a2:6c:e4:5f:6d:5c:1c:96:75:
    42:ef:68:9e:ad:a5:89:35:fd:3a:7e:e5:42:12:fb:
    20:9f:2d:ec:70:4c:0f:fe:e9:5c:e2:4e:04:9d:d8:
    24:3d:e3:02:0e:97:1b:46:71:7c:a5:63:5a:05:56:
    12:ad:68:39:a6:cc:f8:b8:90:9c:ac:61:58:67:e0:
    00:85:96:55:81:23:c5:bb:74:63:4a:ab:16:96:7d:
    01:35:1b:3f:0a:e0:c0:f4:fa:84:0a:63:59:10:f5:
    cb:cb:e8:5c:15:1f:7e:8b:1f:71:c6:82:a1:e4:2b:
    a8:18:b7:6b:cf:e1:15:89:41:ce:8a:8b:70:f6:8d:
    80:10:32:0a:0b:2a:3c:6c:ae:12:f5:d6:3f:e6:66:
    61:c6:4f:bf:b4:ae:ea:83:2a:15:8b:12:b9:6e:71:
    1e:80:92:ad:f4:fe:89:76:ae:8a:b5:22:82:25:91:
    d3:b3:d6:40:ad:f4:63:7b:28:e3:0f:a1:39:b4:ca:
    7f:2e:20:96:98:41:c6:99:e3:26:37:77:e8:5a:1c:
    38:65
publicExponent: 65537 (0x10001)
privateExponent:
    3c:d8:80:96:70:b2:b3:3f:a4:dd:bd:23:ca:c9:5c:
    f5:72:fb:97:93:ce:19:30:02:8a:12:21:62:49:fe:
    98:60:c7:ac:2f:bc:7f:5e:da:49:d2:73:56:41:a8:
    90:b6:9a:cb:54:2b:63:8f:d0:1e:f0:99:97:ec:6c:
    4f:19:67:00:b9:d0:79:9d:8c:4a:de:87:82:66:ca:
    7e:33:0b:1c:61:10:d4:a0:e1:56:8f:32:0e:bb:d2:
    5f:c2:ce:b2:63:3d:ce:93:9e:ab:54:b8:64:af:e0:
    b8:1f:59:ca:f0:f7:85:75:22:1f:4e:fd:9c:80:f7:
    8c:3c:f8:08:30:33:bc:1f:af:69:92:89:d5:6d:17:
    5a:4e:c8:61:2e:d7:0e:cf:ab:b6:d3:03:f4:54:37:
    0f:47:e2:d6:80:bf:25:9c:2a:c9:72:0e:4a:fc:0d:
    f4:50:9d:9d:c6:da:5f:53:ae:76:33:bf:c6:20:f1:
    ce:a5:27:94:a3:3b:17:cc:2f:36:9d:09:f2:69:c0:
    60:e1:82:7d:1d:5e:a4:cd:5e:53:13:33:bb:c8:da:
    bd:d4:d6:ab:5b:4e:ee:3f:5e:7a:a7:1d:b3:f3:c2:
    94:bc:e7:cd:cf:f5:4b:a7:31:7f:3b:59:e5:e2:e6:
    95:24:2c:f9:71:1c:33:f1:9b:74:4f:0a:c8:93:af:
    4d
prime1:
    00:ee:79:a5:06:ed:d4:a7:63:69:5a:77:c0:c4:8b:
    97:1a:34:93:aa:8c:68:41:a6:54:9b:8b:0c:b7:00:
    59:21:d2:0e:58:0e:a3:ef:19:5a:39:8f:b4:5d:a9:
    57:a9:7c:b4:fc:c1:bd:b4:37:82:73:55:55:53:7b:
    06:71:c5:c1:e5:2e:60:b1:20:a9:cc:72:87:8c:3f:
    99:23:ab:0a:ac:94:45:b4:06:73:0d:ea:58:72:7e:
    b8:c5:39:3e:9d:80:36:0e:cc:52:7d:a6:50:b9:26:
    00:33:04:bb:c9:b0:9c:83:e3:0e:e2:e4:53:35:44:
    2c:13:32:84:32:85:75:67:bf
prime2:
    00:c1:06:0e:17:3b:54:80:61:9e:19:71:bd:17:11:
    d2:92:38:5c:75:06:f8:23:a8:6f:4e:d4:db:5c:fa:
    e1:a4:89:dd:0c:72:02:7d:06:5a:52:a0:2a:39:20:
    03:d7:ce:6d:48:0d:c9:52:34:b3:12:7e:58:23:b3:
    33:89:60:3c:6d:49:7f:2d:17:13:6c:a7:73:15:b3:
    16:74:93:b3:26:68:df:ff:08:aa:db:62:6a:09:83:
    96:2e:d4:60:30:79:6e:1d:fd:c3:d2:6b:aa:9a:0c:
    9d:2e:ce:eb:02:f6:54:6a:80:b3:f7:ac:e3:af:b1:
    8e:ad:d4:7f:8c:0c:31:88:db
exponent1:
    23:19:88:6e:a2:a6:c0:14:63:b7:4b:14:f6:58:cd:
    5e:b0:0a:63:f9:d2:86:87:22:c0:da:10:7f:06:f0:
    17:88:41:50:38:a7:6c:53:c0:f1:e3:f2:da:2e:48:
    96:cb:a2:1f:e9:ac:30:50:53:45:02:74:52:9b:32:
    f1:9f:f7:cf:f1:a9:8d:a8:8f:15:66:6e:08:f8:7b:
    63:c2:93:09:9f:b1:3a:b4:10:4f:26:04:ea:a5:38:
    30:df:22:16:30:7e:c4:62:d2:69:68:07:4d:99:08:
    42:7a:19:e1:af:ba:f9:b6:7b:c4:6d:72:c9:ce:44:
    e6:76:72:fa:b4:a5:f9:25
exponent2:
    2b:3c:87:fb:7c:36:b9:6b:24:56:de:bb:54:67:91:
    9b:5f:34:96:a2:31:03:0b:bf:a3:10:da:f2:40:e0:
    3a:53:07:48:ba:61:04:50:5f:fb:12:15:63:26:60:
    b5:fe:6f:4c:2c:8a:63:f7:9a:05:12:77:fb:c7:30:
    4c:1d:5a:6b:c0:82:d4:3e:cf:03:0f:9f:1f:c5:35:
    ca:77:2b:31:f7:5b:f5:6c:a3:98:f0:ba:7f:d7:11:
    d4:fb:8d:70:4e:42:f4:44:db:90:4e:bd:b0:34:13:
    21:61:08:13:69:ca:0e:f1:35:5e:cd:43:53:1f:9a:
    ae:25:63:4c:a3:8e:94:f1
coefficient:
    00:89:cf:24:0d:89:76:dd:71:f0:9c:41:ec:ff:12:
    53:69:fe:a8:2f:13:00:90:b5:d4:db:8b:3c:57:39:
    78:e3:d7:6c:6e:4b:2d:e8:6f:02:ee:64:4f:f7:0b:
    5b:65:f6:99:36:fa:95:a7:6a:4f:36:12:b4:d8:d9:
    70:ad:88:ab:02:7f:64:46:a1:c8:2f:ca:5a:29:98:
    1b:9d:3e:0e:04:cc:f2:85:9a:3d:5c:27:52:1a:fe:
    4d:76:fe:e8:ae:c7:9c:fd:90:34:5d:81:84:2e:a0:
    f2:fc:7d:b1:f9:5a:a4:4f:5e:43:85:b2:c8:1c:b3:
    e6:db:ac:17:77:44:b9:c7:39

The relation between the mathematical parameters and keypairs

First off, we have the equation for encryption and decryption is just ((secretData**publicExponent)**privateExponent) = secretData % modulus. Now this equation is composed of two parts: the encryption expression secretData**publicExponent = encryptedData, and the decryption expression: encryptedData**privateExponent = secretData. These expressions are the heart of the RSA encryption/decryption process.

The exponentiation that you see here is not conventional exppnentation, but modular exponentiation, where after you take the exponent you modulate the result by a number known as the modulus. Usually secretData % modulus (also applies to encryptedData) is equivalent to just secretData, because secretData is less than modulus.

The modulus itself is created by multiplying two secret prime numbers prime1 and prime2. Every public key's modulus is different as a result. It is extraordinarily difficult to factor a large enough number into two primes, hence it is called the factoring problem. The RSA company in its early days actually used to make challenges for researchers to factor certain large numbers and offer rewards to the winners.

The reason the primes have to be secret but the modulus can be public is because the primes can be used to calculate the privateExponent, but the modulus cannot be used for this by itself. You actually have to compute the least common multiple of prime1 - 1 and prime2 - 1, and once you have that (we'll just call it a for brevity), you can get privateExponent using (publicExponent**-1) mod a. That's why it's so important to keep the primes secret.

[1] a is technically called the Carmichael function λ(n) and has some nice properties, such as if n is prime, then λ(n) is just n-1, whole if λ(n) has unique prime factors (e.g. 35 --> 3 5 7) then λ(n) is just leastCommonMultiple(prime1-1, prime2-1, ... primeN-1) and if any factors repeat, such as 20 --> 2 2 5, the function evaluates to leastCommonMultiple((prime1^timesPrime1Repeats)-1, (prime2**timesPrime2Repeats)-1, ... (primeN**timesPrimeNRepeats)-1). All in regular arithmetic without performing modulus 


So what are those other values doing in the private key if the above three are all that's necessary? The answer is here:

It has to do with optimizing RSA.

It turns out that using the Chinese Remainder Theorem with 𝑝, 𝑞, 𝑑(mod𝑝−1), and 𝑑(mod𝑞−1) (i.e., prime1, prime2, exponent1, exponent2 from the data structure in the question) to run the decryption operation faster than if you only had 𝑑,𝑛.

For more information on how it is done, I found this reference http://www.di-mgt.com.au/crt_rsa.html

So this means the decryption process using the Chinese Remainder Theorem with all those variables is faster than modular exponentiation with the privateExponent.

Not shown in the answer above is the coefficient which is also used in the Chinese Remainder Theorem optimization speedup. It's value is just (prime2**-1) mod prime1.

How to generate a private key from the mathematical parameters

Warning: never attempt to perform any operations on private keys by hand in production applications. You may accidentally code known vulnerabilities into your implementation. Always use the OpenSSL library or comparable for your language and platform for key generation. The material in this section is for educational purposes only and I do not recommend implementing them on your own in production programs.

With that out of the way, this section only covers generation of the private key. The public key can be created by extracting the modulus and publicExponent fields of the private key.

So the steps are:

1. Use random entropy to generate two large prime numbers prime1 and prime2
2. Compute modulus = prime1 * prime2
3. Compute the Carmichael function of modulus i.e. just compute carmichael = lcm(prime1-1, prime2-1)
4. Pick a number between 1 and carmichael and use that as your publicExponent
5. Calculate privateExponent = (publicExponent**-1) mod carmichael
6. Compute the values of exponent1, exponent2 and coefficient using the formulas above and shove them into the private key PEM. This can be done in parallel to the other steps as they aren't used during key generation.
7. Extract modulus and publicExponent from the private key and put them in the public key.
8. Optionally, password-protect the private key file.

To encrypt a message with RSA:

This is easy, you just have to compute encryptedMessage = secretMesaage**publicExponent mod modulus. The private key isn't even required for this. That's how you're able to encrypt a message for someone else's public key without having their private key, because all the required information for encryption is encoded in their public key.

Decrypting a message with RSA:

Average-speed way: compute secretMessage = encryptedMesaage**privateExponent mod modulus. You need to get the user password for the private key if it is password-protected (encryption doesn't require a password prompt).

Fast way using Chinese Remainder Theorem:

Algorithm is credit to https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Example

1. Compute m1 = (encryptedMessage**exponent1) mod prime1
2. Compute m2 = (encryptedMessage**exponent2) mod prime2
3. Compute h = coefficient * (m1 - m2) mod prime1
4. The final result is secretMessage = m2 + h*prime2.

2. 4096-bit RSA

TODO

3. Keypairs using the Ed25519 curve

TODO


Due to space limitations for the topic, future concepts will be in new posts in this thread.

Local rules:

- Questions and discussion about anything security or cryptography related is welcome! But please don't post conspiracy-theory-like material here such as Microsoft vs Linux debate, "X company has an NSA backdoor in their software" if it can't be reliably proven, etc.
- No trolling.
- If you quote the entire OP, your post will be deleted.  No exceptions. It's way too long to navigate.

[NotATether]

Reserved for future material.

[NotATether]

Reserved for more future material.

[BlackHatCoiner]

This is a great topic. I hope you continue expanding it. I like spending my free time by just going through all these technical explanations, even if I'm not good enough on fully understanding them. Some questions:

Second, private keys take exponentially more time to brute-force than a medium-length password (you need a password length of about 311 ASCII characters to provide the equivalent security of an RSA-2048 private key, and 622 characters for RSA-4096 key).

Can you explain why that happens? And brute forcing what algorithm? I suppose that since RSA encryption is different than just keeping hashed passwords on a database, you probably mean brute forcing a message digest algorithm. But why 311?

Decrypting a message with RSA:

Average-speed way: compute secretMessage = encryptedMesaage**privateExponent mod modulus. You need to get the user password for the private key if it is password-protected (encryption doesn't require a password prompt)

I get that it is possible and thankfully, you wrote the mathematical equation, but why does that happen? Why do you get the message once you rise the encryptedMessage to the power of privateExponent and then take the modulus of this process? I don't understand how we end up with the secret message with these mathematical operations. Sorry for my terrible mathematical grammar. I don't tend to write about maths very often. I actually only discuss about maths and cryptography on bitcointalk.

AFAIK modulus is the remainder of a division. With what do you divide encryptedMesaage**privateExponent?


My suggestion is to explain ECC in one of these future materials. I would be very interested understanding the maths behind ECDSA encryption which tyrannizes me these days!

[yo_mama]

Nice, very good material!
Do you want to add some analysis about quantum proof? Quantum computers are in rapid development quietly, and the exponential nature of Moore's law means it'll be there probably sooner than all of us can expect. Years ago Vitalik Buterin wrote a short article about Bitcoin's quantum proof on Bitcoin magazine, but probably people weren't paying enough attention.

[NotATether]

I'll edit this post tomorrow with the answers to the rest of everyone's questions and suggestions as it's getting late here.

Why do you get the message once you rise the encryptedMessage to the power of privateExponent and then take the modulus of this process?

In layman's terms, the public exponent is derived from the private exponent in such a way that multiplying (edit: taking the exponent, sorry) some message data, in big integer form, with both of them cancels each other out.

AFAIK modulus is the remainder of a division. With what do you divide encryptedMesaage**privateExponent?

In the private (and public) key file there is a field called "modulus" which is used for that.

EDIT: The answers to the rest of your inquiries:

Can you explain why that happens? And brute forcing what algorithm? I suppose that since RSA encryption is different than just keeping hashed passwords on a database, you probably mean brute forcing a message digest algorithm. But why 311?

311 is the amount of characters required to make the search space approximately equal to the size of RSA-2048. And that's if we only use printable characters in the ASCII character set, so excluding 0x00-0x1f and 0x7fffffff, leaves us 96 characters, and 96**311 is almost equal to 2048.

Obviously I have to take into account the hashing algorithm used to store passwords, whether it be bcrypt or SHA256, and compare that to the running time of some RSA2048 brute-forcing program, so my quote is not 100% accurate.

Nice, very good material!
Do you want to add some analysis about quantum proof? Quantum computers are in rapid development quietly, and the exponential nature of Moore's law means it'll be there probably sooner than all of us can expect. Years ago Vitalik Buterin wrote a short article about Bitcoin's quantum proof on Bitcoin magazine, but probably people weren't paying enough attention.

Appreciated! Though it will be troublesome to find material related to quantum encryption algorithms, it's definitely on my TODO list now.

[acquafredda]

Great thread man. After reading your OP I found this very interesting article on how to generate your very own btc private keys.
https://www.freecodecamp.org/news/how-to-generate-your-very-own-bitcoin-private-key-7ad0f4936e6c/
If you find it relevant for the content of your thread, consider adding it to your list. I found it very informative and well explained.

[Smartvirus]

A public key is a piece of data that you share with everyone, which identifies the access being granted, while the private key is secret data that grants access to the resources protected by the public key. They are always generated in pairs, that's why you'll sometimes hear them called keypairs when referring to both of them. Think of the public key as a door lock or car lock and the private key being the "key" that unlocks it.

I didn't really get this illustration at first, getting to see it as a door look as, public keys are transparent and as such though unaccessible, it's content is visualizable meanwhile, most doors are designed to be opaque but then,I came to the realization that, there are actually transparent glass doors that comes with locks and a key. So, it's a very correct illustration.

Why are public and private keys necessary

Suppose you paid for access to a computing resource. The vendor needs a way to securely provide you the login information to your resource. A lot of them use passwords for this task but the disadvantage of using passwords is that anyone who remembers what your password is can access your resource. There also exist brute-forcing programs for passwords.


These problems are partially mitigated by providing you a private key. First of all, private keys are not human-readable, so someone can't just glance behind your shoulder and remember them. Second, private keys take exponentially more time to brute-force than a medium-length password (you need a password length of about 311 ASCII characters to provide the equivalent security of an RSA-2048 private key, and 622 characters for RSA-4096 key).

311, that's a lot of numbers but still, I don't think the length actually makes for a better distinguishing factor as one can choose to combine numbers in ways hat could be unique to them to make out a lengthy password and that still doesn't make it a private key. I think the difference is more about it's generation as one follows a definite pattern when it's human because, there could only be about a point humans follow as to generating a combination set for easy remembrance which won't be random enough but the machine generated keys uses an algorithm set and is very much random.

It's a nice piece and I like the way it gradually moved along the parts of complexity. Still trying to grasp some information contained in the content though but, sure would be watching out for info's as these.