Topic: The security megathread: Detailed info about keypairs, encryption, and more (Read 197 times)

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.

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.

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.

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


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.


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:


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.


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

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.

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:

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?

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!

Reserved for more future material.

Reserved for future material.

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.


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:



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


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:


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

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

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

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:
private.pem and private_unencrypted.pem (doesn't matter):
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:


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.