Posted by arlene

This is a form of cryptography which does not require the use of the same key to encrypt and decrypt a plain text; rather it uses two keys: a public key and a private key. One key is held securely, while the other is distributed. They have the two properties:

• Keys must be generated in pairs and it must be computationally infeasible to obtain one key from the other key alone.

• Information that is encrypted by one key can be decrypted only by the other key of the key pair, and information decrypted by one of the keys could only have been encrypted by the other key of the key pair.

It was originally proposed by two American researchers, Whitfield Diffie and Martin Hellman, as a means of eliminating the need for a key to be transmitted from one party to another party when using symmetric encryption. The details of the schema are complex and quite mathematical, so all that is worth saying about it is that it was originally based on the fact that finding the prime factors of large integers greater than say 10¹⁰⁰ is so computationally difficult that it is effectively impossible to do.

The recipient of a message which uses public key encryption uses the two keys in the following way:

• They publish their public key, for example on their Web site.
• Anyone who wants to send a message to the recipient uses the public key to carry out encryption.
• The encrypted text is processed by the recipient who applies a decryption algorithm which employs the secret key.

In this way there is no need for the recipient to publish the key that is used for decryption. It is worth at this stage comparing the two methods of encryption before looking at some of the technologies and some of the attacks that have been carried out on public key systems.

• When they use sufficiently large keys both methods are secure.
• Public key encryption is easier to implement because there is no need to worry about transmitting keys over some insecure medium.
• The processing power required for symmetric key encryption is much lower than for public key encryption. This means that for the bulk transmission of data symmetric key encryption is normally preferred.

Sarah Flannery and public key encryption

There have been a number of improvements to public key encryption. One of the most remarkable was devised in 1999 by a 16-year-old Irish schoolgirl, Sarah Flannery, who developed a technique which was almost 30 times faster than one of the existing, widely-used public key systems. However, while her achievement can be hailed as a major one, it still does not alter the processing imbalance between public and symmetric key methods.

Technologies

There are a number of technologies and different implementations of public key cryptography.

Smart cards, private keys and public keys

One of the most secure ways of ensuring privacy of a private key is to store it on a smart card. These are credit-card-sized pieces of plastic which can contain both the private and public keys. They can be plugged into a computer, with the private key being sent to the computer carrying out encryption. This means that the private key need never be stored on the computer and anyone who wants to find your private key has to steal the smart card. Even then it might be impossible to use the private key because smart cards can be programmed to demand a PIN number before they are used.

The first is Diffie—Hellman key exchange. This is a technique that is used to secure a key used in symmetric key encryption. With this the two parties who are going to exchange some information first negotiate and exchange a private key using public key technology.

RSA is almost certainly the most well-known public key cryptography system. It was developed by three professors at the Massachusetts Institute of Technology: Ronald Rivest, Adi Shamir and Leonard Adelman. RSA can be used for sending data over an insecure line and also used for constructing digital signatures: sequences of characters which provide evidence that the initiator of a transaction is who they claim they are.

The ElGamel sytem is a public key system based on the Diffie—Hellman key exchange idea. It can be used for digital signatures.

The Digital Signature Standard, often known as DSS, was developed by the American National Security Agency and has been enshrined as a standard by the American National Institute of Standards. In its original form it can only be used for digital signatures; however, it can be modified for normal data transfer. The technique relies on an algorithm known as the Digital Signature Algorithm.

Attacks on public key systems

There are two types of attack on public key systems. The first is the factoring attack. You will remember that early I described the fact that popular public key encryption methods rely on the huge difficulty of solving inverse problems such as factoring very large numbers. Anyone who can factor very large numbers efficiently is capable of breaking a public key system based on factoring. This is not an unlikely occurrence: mathematicians working in the area known as number theory have beer studying problems involving factoring for a very long time and have been partiall) successful with numbers which have special properties.

The RSA-129 attack

Almost certainly the most famous factoring attack has been that on the RSA-129 number (129 digits). This large number was published in an issue of the American magazine Popular Science in 1977. It was eventually factored by a team of researchers coordinated by Arjen Lenstra who was then working at Bellcore.

The other technique used to crack a public key encryption is to find a flaw in the algorithm used. For example, one of the problems first posted as a candidate for a computationally hard problem to base public key encryption techniques on was one known as the knapsack problem. It has been found that it can be quite easy to derive a private key from a public key in a system which is based on this type of problem.

Elliptic curve cryptography

A very promising form of cryptography which threatens to overtake the use of factoring in public key systems is elliptic curve cryptography. It involves solving computationally very hard problems using a family of curves known as elliptic curves. Many public key systems uses RSA; however, the increasing power of computers has meant that bit lengths have had to be increased for this technique, which has led to greater and greater computational demands. Elliptic curve cryptography seems to be as secure as RSA; however, it requires smaller bit lengths and, as a consequence, requires less powerful processing. The Web reference at the side contains links for the mathematically brave reader.

Possibly related posts: (automatically generated)
Public key Cryptography, when can be seriously Attack

• Cryptography (Public-Key) Standards and Protocols Notice
• Cryptography MITM Attacks
• Using Cryptography: Confidentiality, Integrity, Digital Signatures
• Internet Security, Public Key Encryption and Digital Certificates
• Public Key Destruction and Distribution
• Public-key Certificates and Certificate Authorities
• Coded Data Cryptographic Systems Software
• Internet Key Exchange (IKE)
• Network and Programming: the .Net framework
• Security Facilities in Java