Public Key encryption question?

Robbo777

Hi, so i have watched and read quite a few public/private key related articles and videos but i still have a few question regarding it.
I think i have the premise down with regard to knowing what goes into the procedure, an example being a user connects to a website, say PayPal for example and they're given the sites public key and with it uses it to encrypt the data, being a username or password etc... along with that data being turned into a hash for integrity and then encrypted with something like AES etc.. Then the private key on PayPals end can decrypt the data and then check to see if the hashes match and then the user is accepted. I know that's the basic run down without going to deep but my question related to HOW or what exactly goes into making these public and private keys. I have read a few examples but still dont really understand it, is the concept that the public key is some kind of formula or a set of rules for HOW the data is encrypted using the AES technology? Then the private key is the answer to the riddle so to speak? Meaning that it knows the secret to what goes where and how to decrypt it.

For example: If i had a string such as Hello World and the public key was to encrypt every letter with another letter 4 characters down in the alphabet so A would be E and so on, would the private key then be something along the lines of reverting every letter 4 characters back the other way? I'm probably wrong but i did want an example and a basic understanding of what goes into an example of these.


I know a pre shared key is different where its kind of a password at both ends that gets encrypted and decrypted.

Thanks.

OctalDump

I think that you are asking a difficult question, but you might be asking something simpler. I can give you the simpler answer.

So, a normal encryption algorithm takes two inputs: the plain text to be encoded, and the "key". The key is the unique part. A different key, means the plain text will have a different cipher text. This is not the only method of encryption, but is the most common used on computers. These algorithms have several design goals, one of which is usually that the algorithm can be open without affecting its security. Sometimes computational efficiency or suitability for use in an ASIC is also important. In some cases, computational inefficiency is desirable as it makes brute force attacks more expensive. Generally, these algorithms are designed to make cryptanalysis difficult by employing principles of confusion and diffusion.

Public key cryptography is a system where what is encoded using one key in a pair, is decoded using the other key in the pair. The keys are complementary. Again, the algorithm will just take two inputs - the plain text and one of the keys, for encryption, and the cipher text and the other key for decryption.

The mathematics behind how public key cryptography actually works, is beyond me. I've read the text book explanation, but my mathematics was not good enough to understand it. From what I understand, one method is using two large prime numbers. The two large prime numbers can be multiplied together to give a large number with only these factors. It is very hard problem to factor large numbers. If you know one of the factors, then it is much easier. This means that if you know one half, and the product, then you can find the other half. Now how that actually connects to algorithm, I'm not sure. There is an explanation here: How Public Key Cryptography (PKC) Works

There's other methods as well, such as elliptic curves.

If you really are interested, then the book I recommend is: Cryptography and Network Security Principles and Practice by William Stallings
You'll need some grounding in higher mathematics, maybe 100 level or Discrete mathematics is sufficient. There is some explanation in the book of the basic concepts needed but, being mathematics, it builds on other assumed knowledge.

I plan to revisit cryptography next year or the year after, once I've remediated my maths

Robbo777

I appreciate the help, on this occasion i think you tried to explain what actually goes into the algorithm in these keys, i was just trying to firstly get an idea of how WE go about configuring them. They aren't done automatically are they? Everyone has a different private key so some customisation must go into it. Going back to my example, would the principle be along the lines of something like that? Or am i just way off?

OctalDump

Wow, I was way off. Fun stuff, though.

Yeah, the keys are generated as a pair within whatever suite of tools you are using. The technical details of the algorithm for keys based on primes, actually just picks very big numbers "randomly" which are very likely to be prime, which does the trick. So, the idea is that each pair of keys is very likely to be unique.

What complicates this all in practice, is that asymmetric cryptography is commonly used in the context of a Public Key Infrastructure, where your public key is in a certificate signed with the private key of a Certificate Authority, so it's like a key within a box that's opened by another key.

Regarding the AES, this might be confused for you. When public keys are used in TLS (SSL), they are used to exchange the AES session key - this is a one off key used for the encrypting the rest of the session. AES is a symmetric encryption method. Symmetric encryption is much faster than asymmetric, so this is why they just use the asymmetric (public key) encryption for key exchange.

Robbo777

Right, i think I'm starting to understand it a bit more now then. I was wondering if you could provide just a basic example of what goes into it if we where to configure a public/private key relationship? Not the actual maths involved (i can look that up after i get the concept down).

Cheers

OctalDump

OK, for example with a LAMP stack using OpenSSL (probably 30%+ of implementations are this), to set up a TLS/SSL on the website you start with what's called a CSR - certificate signing request. This process gives you your private key, and the CSR which contains the public key. You send the CSR to a public Certification Authority like Thawte or Verisign, and they send back a certificate signed with their public key. This certificate contains your public key.

Now the obvious question is "why is the public key in a certificate, but the private key is just the private key?". The public key is in the certificate because the certificate contains a lot of extra information along with the actual encryption key. For example it has the server address it pertains to, details of the organisation who owns it, who signed it etc. All that information is so that the client can verify your identity, ie know that the site is genuine and legitimate. The private key is private to the server, so doesn't need anything extra, all it will do is decrypt data.

Most of the public/private systems (all I can think of) generate the keys in pairs in one step. You keep one private, and then publish the other one.