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-progressThis 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 keysA
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.
![](https://ip.bitcointalk.org/?u=https%3A%2F%2Fupload.wikimedia.org%2Fwikipedia%2Fcommons%2Fthumb%2F3%2F32%2FPublic-key-crypto-1.svg%2F480px-Public-key-crypto-1.svg.png&t=665&c=rSXUDlhxz-kZqg)
Image source:
https://en.wikipedia.org/wiki/Public-key_cryptographyWhy are public and private keys necessarySuppose 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 RSACode in this section is credited to
https://rietta.com/blog/openssl-generating-rsa-key-from-command/https://stackoverflow.com/a/20352821/12452330This 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:
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.
$ 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:
openssl rsa -in private.pem -out private_unencrypted.pem -outform PEM
Contents of 2048-bit RSA keypairsEach of these files is in human readable PEM format.
public.pem: starts with BEGIN PUBLIC KEY and ends with END PUBLIC KEY
-----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.
-----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.
-----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:
openssl rsa -pubin -in public.pem -text -noout
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):
openssl rsa -in private.pem -text -noout
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 keypairsFirst 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
![Smiley](https://bitcointalk.org/Smileys/default/smiley.gif)
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.htmlSo 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 parametersWarning: 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
prime22. Compute
modulus =
prime1 *
prime23. 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
publicExponent5. Calculate
privateExponent = (
publicExponent**-1) mod
carmichael6. 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)#Example1. Compute
m1 = (
encryptedMessage**
exponent1) mod
prime12. Compute
m2 = (encryptedMessage**
exponent2) mod
prime23. Compute
h =
coefficient * (
m1 -
m2) mod
prime14. The final result is
secretMessage =
m2 +
h*
prime2.
2. 4096-bit RSATODO
3. Keypairs using the Ed25519 curveTODO
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.