Public key encryption overview

Locked
User avatar
Pigeon
Posts: 18055
Joined: Thu Mar 31, 2011 3:00 pm

Public key encryption overview

Post by Pigeon » Wed Mar 20, 2013 1:23 am

The first public key encryption algorithm: RSA

The first algorithms using asymmetric keys were devised in secret by the British government's SIGINT agency, GCHQ, in 1973. That work was not made public, however, until 1997, when the British government declassified it.

The first published, commercially available algorithm (which happened to work in much the same way as GCHQ's worked, albeit in a more generalized form) was invented in 1977, and it was called RSA after the names of its three inventors (Ron Rivest, Adi Shamir and Leonard Adleman).

Symmetric algorithms essentially depend on jumbling up the plaintext in complex ways and doing so lots of times; the key is what specifies the exact jumbling up pattern that was used. Asymmetric algorithms take a different approach. They depend on the existence of hard mathematical problems. The keys here are solutions to these mathematical problems.

The problem that RSA is built around is that of integer factorization. Every integer has a unique prime factorization; that is, it can be written as a multiplicative product of prime numbers. For example, 50 is 2×52. While factorization is something that we all learn at school, it's actually a hard problem, especially when dealing with large numbers.

The naive algorithm you learn in school is called "trial division"; you divide the number you are trying to factorize by each prime number in turn, starting at 2 and working your way up, and check to see if it's wholly divisible. If it's wholly divisible then you then factorize the number that's left over, starting at the same prime as you just divided by. If it isn't, you try the next prime number. You only stop when you've tried every prime number less than or equal to the square root of the number you're trying to factorize.

This is easy enough for small numbers, but for big numbers it's very time-consuming. There are various algorithms that are a bit quicker than trial division, but only incrementally so.

RSA key pairs (that is, the pair of private and public keys) are generated in the following way:

Choose two large, distinct prime numbers, called p and q.
Compute p × q, and call this n. The size of this number in bits is the key length, and it gives an indication of how strong the key is: the longer, the better.
Compute (p - 1) × (q - 1), and call this φ(n).
Pick an integer e that is coprime with φ(n). That is to say, a prime factorization of e should have no factors shared by a prime factorization of φ(n).
Calculate d such that d × e = 1 (mod φ(n)). This multiplication uses modulo arithmetic (also known as clock arithmetic). Modulo arithmetic wraps around. It counts normally from 0 to mod φ(n) - 1, then wraps around back to 0 again. This is much the same as the way that on a clock, the number after 12 isn't 13; it's 1.

The public key is the pair of numbers (e, n). The private key is the pair (d, n). p, q, and φ(n) must also be kept secret.

Encryption and decryption are both quite simple. A ciphertext c is generated from a plaintext m as follows:

c = me (mod n)

Decryption is similar:

m = cd (mod n)

Here's where the difficulty of integer factorization is important: if n could easily be factorized then anyone could determine p and q, hence φ(n), and hence d. If d were known to everyone then they could decrypt the messages encrypted with e with ease.

Conventionally, e, the public key, is chosen to be a smaller number than d, typically 65,537.

Link


User avatar
Pigeon
Posts: 18055
Joined: Thu Mar 31, 2011 3:00 pm

Re: Public key encryption overview

Post by Pigeon » Wed Mar 20, 2013 1:25 am

Public key cryptography in practice

Perhaps surprisingly, one of the things it's not good for is general-purpose encryption. Those exponentiation operations used in RSA's encryption and decryption (or similar operations in other algorithms) are slow and expensive to compute; as a result, RSA isn't well-suited to encrypting large chunks of data. What it is good for, however, is encrypting small pieces of data—such as the encryption keys for symmetric algorithms, which are good for encrypting large amounts of data.

An example of this is the PGP program, first released in 1991. PGP, standing for "Pretty Good Privacy," is a program for sending secure messages using a combination of symmetric and asymmetric encryption algorithms. Everyone who wants to receive PGP-secured messages publishes their PGP public key. Traditionally, this is an RSA public key, though nowadays other algorithms are also supported.

To send a secure message, you first generate a random key for use with a symmetric algorithm. You use that key and the symmetric algorithm to encrypt your message. The original PGP implementation used an algorithm called IDEA for this purpose, though modern versions offer a variety of options for this, too. You then encrypt that random key with the RSA public key and bundle the two things—symmetrically encrypted message, asymmetrically encrypted random key.

To decrypt the message, the recipient uses his private key to decrypt the random key, and then uses the random key to decrypt the message itself.

Similar schemes are used for the S/MIME secure e-mail standard: public key cryptography is used to secure keys, and symmetric cryptography is used for the bulk encryption.

Disk encryption systems like Microsoft's BitLocker also uses a similar approach on systems equipped with TPM (Trusted Platform Module) chips. These chips securely store encryption keys and in principle only allow authorized software to access them. The bulk encryption of the data on the disk uses the AES symmetric algorithm; that key is then encrypted using RSA.

The ssh network protocol widely used for remote connections to Unix-like operating systems can also use public key cryptography for logging in. Users connecting to systems by ssh generate their own key pairs and associate their public keys with their user accounts on every server they want to connect to. Each time a user connects to the server, the server verifies that they're in possession of the corresponding private key by exploiting the fact that only the private key can decrypt messages encrypted with the public key.


User avatar
Pigeon
Posts: 18055
Joined: Thu Mar 31, 2011 3:00 pm

Re: Public key encryption overview

Post by Pigeon » Wed Mar 20, 2013 1:26 am

Signed, sealed, and delivered

Both RSA keys can be used to encrypt data. For secure communications, the public key is used to encrypt and the private key to decrypt, but the reverse is also useful; using the private key to encrypt and the public key to decrypt. This is useful because it proves authenticity. If a message can be decrypted using the public key then that proves that it was encrypted by the private key.

To create a digital signature, first the message is fed into a hash algorithm. Hash algorithms convert variable length data into fixed length numbers. Simple hash algorithms are widely used to provide probabilistic detection of changes to data due to things like transmission errors or disk corruption. Hash algorithms used in cryptographic applications are generally a bit more complex, because they're designed to ensure that it's all but impossible for someone to construct a file in order to have a specific hash value.

The output of this hash function, called the hash, is then encrypted using the private key. The encrypted hash and the message are then distributed.

To verify the signature, the encrypted hash is decrypted. The message is hashed using the same hash algorithm, and this hash is compared to the decrypted value. If they match, then it proves two things: first that the message was sent by the owner of the private key, second that the message has not been subsequently modified.

Public Key Infrastructure

The biggest single use of public key cryptography, however, is building public key infrastructure (PKI). PKI uses public key cryptography to create digital certificates that allow for secure attestation of identity.

Digital certificates are little chunks of data that contain some information about an identity (so they could represent a company, a subdivision of a company, or an individual person, say), some usage information about the certificate itself (a certificate might be legitimate only for signing e-mail messages, or for signing software, or for encrypting files), and a public key.

These chunks of data are then all signed by a certificate authority; an organization that's in some sense trusted to have performed verification of the identity of the person the certificate belongs to. Each certificate also has a corresponding private key that is given to the certificate's owner.

Like normal public keys, certificates are freely published; the private keys, of course, are not.

PKI is something that most of us unwittingly use every single day, because these certificates are used for Web serving with secure HTTP (HTTPS). HTTPS is used for both encryption, to prevent people from eavesdropping on your connection to your bank, and also authentication, so that you can prove that it's really your bank you're talking to and not some hacker.

The authentication aspect is provided by the use of digital certificates: whenever a client connects to a server, the server sends its certificate for the client to inspect. For its encryption, HTTPS follows the same pattern that we've seen before; bulk encryption of the data using a symmetric algorithm and a random key, with the key transported using asymmetric encryption. The specifications underpinning HTTP (namely, secure socket layer [SSL] and transport layer security [TLS]) allow a variety of symmetric and asymmetric algorithms, but RSA is one of the more common. When RSA is used, the server certificate's public key itself is used to encrypt the secret key.


User avatar
Pigeon
Posts: 18055
Joined: Thu Mar 31, 2011 3:00 pm

Re: Public key encryption overview

Post by Pigeon » Wed Apr 27, 2022 9:44 pm

Basic maths


Locked