Public Key (or Asymmetric) Technique

A number of problems in using symmetric algorithms in distributed systems, mostly to do with key distribution, led to the development of public key or asymmetric algorithms. The principal idea is that a pair of keys are used with a single algorithm. Of this pair, only one needs to kept secret the other is made public knowledge. Currently only one algorithm is widely known to be suitable for general use, it is called RSA after the inventors Rivest, Shamir and Adleman [RSA]. This algorithm relies on the fact that factorising very large numbers into two primes is a very hard problem and should take a computer a long time. The keys used are the two factors. Unfortunately, there is only empirical evidence that this is true; which means that no one has found an easy way, but no one has proved that an easy way does not exist either. Improvements in theory and technology continue to make the problem a little easier all the time. The basis of the public key system is the two keys, one kept secret by the owner #tex2html_wrap_inline3858# and the other made publicly available #tex2html_wrap_inline3860#. Information that is enciphered by one key can only be deciphered by the other. So to make information confidential to the owner it is encrypted by the public key, then only the owner (or authorized holders of the secret key) may decipher the data to use it, similarly to protect information for integrity it is checksummed using the secret key. Anyone having access to the public key can check the integrity of the data, but only holders of the secret key can change the data. Obviously, this mechanism reduces the number of entities in a distributed system that need to know the secret key. The primary use for public key systems is in an environment involving a large population; in this sense they are very important for distributed systems. To send data with confidentiality it is enciphered with the public key of the recipient:


(#tex2html_wrap_inline3862# means enciphered using the recipient's public key) and on receipt it is deciphered with the recipient's secret key:


Since the public key is common knowledge anyone can send a confidential message to a known recipient. Integrity is achieved in the same way. To obtain authentication of origin a second transformation needs to be applied. Since the recipient's public key can be used by anyone it does not prove who the sender is; to do this we need a secret from the sender. To provide this component the sender's secret key is used in a separate transformation of the data.


which is then transmitted and deciphered by


at the recipient end. Note that the actual secret used by the sender is not sent, only the effect of the secret which can be checked. This is an important advantage in using public keys for authentication (the distribution of the public keys apart). If authentication and confidentiality are required then the two transformations are carried out on the data, the sender would do:


and the recipient would reverse both of these as:


For this to work the mathematical function must be chosen so that


which is currently only true of the RSA algorithms as stated above. Public key algorithms appear to have the advantage over secret key algorithms in that the secret key does not have to be known by every party in a communication. It also means the computer system can apply protection using the public key. In the above examples the secret key only needs to be known by one entity, all the others use the public key. In practice the algorithms for public keys take a lot longer to transform the same amount of data as a symmetric algorithm, consequently they are not used on large items of data. This limits their use in general communications support.