From Wikibooks, open books for an open world
(Redirected from Wikibooks:SAND)
Jump to: navigation, search

The elementary working of Public Key Cryptography is best explained with an example. The working below covers the making of simple keys and the encryption and decryption of a sample of plain text. By necessity, the example is greatly simplified. In the examples it is assumed that an encrypted message is to be sent from Site A to Site B.

Basics Summary[edit]

  • Each site has an encryption key and a decryption key of its own, termed the public and private keys respectively. These are essentially very large numbers. These keys are always different, giving rise to the term asymmetrical encryption. In fact the public key is really a pair, a key to use and the modulus of the arithmetic to be used for the work.
  • An intending sender of a message obtains the destination site’s public key from directories, and encrypts the plaintext with it to make a cyphertext. Only the recipient’s private key can decrypt the cyphertext. Modular arithmetic is used in the process.
  • For a simple message sent from A to B, the private key of A is of no importance; it is all about encryption and decryption with B’s keys. A site’s keys are mathematically related in a way that permits this to occur. (See the worked examples below.)
  • The numbers used are very large, and the non one-to-one nature of modular arithmetic presents many possible solutions. These facts make the burden of discovering the decryption key or otherwise cracking the code very great.
  • Such a system finds use when the intrinsic value of the plaintext is lost before the cracking of the code can be confirmed, but depending on the system might not be secure in the long term.

Making Site B's PUBLIC Key[edit]

A recipient's public key used by any who want to send them an encrypted message.

  • Each site's computer produces two very large prime numbers, and since they are the basis of all that follows, these numbers are never revealed to any other. (Prime numbers are those that have no factors other than themselves or unity).
  • These two numbers are multiplied together to produce the modulus used in all of that site's calculations. The main public key is also derived from these primes, and determines the exponent to which the plain language numbers will be raised.
  • This public key is available in directories, so when the SENDER wants to encrypt a message by public key cryptography he uses the recipient's public key and modulus to do it. Each site's public key and modulus are almost certainly different.

To illustrate the point for an intending recipient, let us make a simple example with the large prime numbers replaced with very small ones.

Say the two secretly held prime numbers are:

p = 5  ,  q = 11

The modulus of the arithmetic that will be used is given by their product:

n = 5  x  11 = 55    (the modulus of the arithmetic to use)

The encryption key can be found as follows: Using the two prime numbers, calculate the function:

f(n)  = (p-1) x (q-1)
∴ f(n) = (5-1) x (11-1)
∴ f(n) =  40

then, Select ANY prime number that is less than f(n) and not a factor of it, (relatively prime to it): The possible choices become 3, 7, 11, 13, ect

say we select 7
∴public encrypt key =  7

The receiving site's PUBLIC key can be safely given to the world as :

(7, 55) as (Public encrypt key, modulus)
(In practice the numbers would be much very larger)

Encryption with B's Public Key[edit]

Assume that the public key pair belong to a Site B. Assume also that a plain language character represented by the number '2' is to be encrypted by Site A and sent to the recipient Site B: Site A uses Site B's public key pair to do so.

cyphertext = plaintext public encrypt key mod n
then with plaintext =2, public encrypt key =7, and modulus = 55, we obtain
cyphertext(2) = 27 Mod 55 = 128 Mod 55
∴ cyphertext(2) = 18

With the very small numbers used in the example the cracking of the code would be relatively simple. But for the very large numbers used in practice the matter becomes very time consuming; for example, try finding whether the 5734839567638847th root of some even bigger number is an integer, for each and every character in the encrypted output. And the numbers are much, much bigger than this.

Making Site B's Private KEY[edit]

Used by Site B when decrypting messages that were sent to them, encrypted using Site B's public key.

The private key pair is used to decrypt messages, and this key will only work if the public key of the same site was used to encrypt the message. That is to say, Site B's public key is obtained from a directory, then used by Site A to encrypt a message for them. When the message gets to Site B, Site B uses its own private key for decryption.

Continuing with the simple example above, the private key of Site B is made from its public key as follows.

private decrypt key =  inv(public encrypt key) Mod f(n)
∴ private decrypt key x public encrypt key = 1 Mod 40       
∴ private decrypt key =  inv(7) Mod 40   
∴ 7 x private decrypt key = 1 Mod 40   This leads to:
∴ private decrypt key  = 23
The Site B private key pair is then:
(23,55)  as (Private decrypt key, modulus)

Decryption with B's Private Key pair[edit]

Decryption using the above specific example is acheived as follows: For the received cyphertext(2) = 18

Plaintext = cyphertextprivate decrypt key Mod n
then with cyphertext =18, private decrypt key =23, and modulus = 55, we obtain
Plaintext(18) = 1823 Mod 55 = 74347713614021927913318776832 Mod 55
∴ Plaintext(18) = 2

which is the required result.