Public key cryptography

From GridInfo

Contents 1 Introduction 2 Authentication using public key cryptography 3 RSA algorithm 3.1 Background definitions and examples 3.2 Encryption formulae 3.3 Factorisation

Introduction

Over its long history, cryptography has been based on having a key with which to encode characters or words. For example, if we represent A, B, C, D, E ... by 1, 2, 3, 4, 5 ..., we could write "a cab" as "1 312". Clearly there are much more sophisticated developments, but all require a table or dictionary to both encode and decode. The traditional problem is that the code is only as secure as the dictionary; since it is necessary for both the code creator and reader to have copies of the dictionary, security is clearly vulnerable.

Most current encryption methods now use what is called asymmetric key encryption. The idea is that you can use one key (the digital equivalent of a table or dictionary) to encyrypt a message, but another key to decrypt. The idea is that two two keys are generated together, but neither can be derived from the other. Neither key can both encrypt and decrypt a message. On this basis, one way to operate is for someone to generate two keys. That person keeps one privately, and makes the other public. Suppose we have two people, Jennifer and Anne. Jennifer generates the two keys and gives one (now called the public key) to Anne. When Anne wants to send an encrypted message to Jennifer, she encrypts the message using the public key, and only Jennifer can decrypt it using the key she kept to herself (now called the private key). When Jennifer replies, she encyrpts her message using Anne's public key, and only Anne can read it because only she has her private key.

Authentication using public key cryptography

Authentication using digital certificates relies on the use of public key cryptography. Suppose Jennifer and Anne want to communicate from different locations, and they want to confirm that each is who they say they are. That is, Jennifer needs to know that whoever is claiming to be Anne really is Anne and not an imposter. To test Anne's authentication, Jennifer can create a short message, encypt it using Anne's public key, and send it to Anne. If Anne can decrypt it and send it back to Jennifer, it implies that whoever is claiming to be Anne really is Anne (unless, of course, someone else now has her private key). Ideally Anne will actually encrypt the reply using Jennifer's public key just to make the process more secure.

This process is easy transformed into machine form, using the method called Secure Sockets Layer (SSL). Rather than Jennifer and Anne encrypting messages and sending to each other, the process can be carried out by computer A and computer B. If you are using a wen browser on computer A and need to send your credit card number to computer B, your browser on Conputer A can get the public key of Computer B and encrypt your credit card number with this public key before sending it over the internet, safe in the knowledge that only Computer B (the intended recipient) can read your credit card number. This is the basis of https (rather than http). Similarly, when logging into another computer using ssh, your password is encrypted using this method so that only the computer you are trying to connect to can read your password.

RSA algorithm

One common public key algorthm is that due to Ron Rivest (MIT), Adi Shamir (Weizmann Institute) and Leonard Adleman (University of Southern California), called the RSA algorithm.

Background definitions and examples

The basic idea can be represented by the following steps:

• Start with two prime numbers, p and q. For real applications these need to be very large.
• Choose another number e, such that 1 < e < pq and such that e and (p – 1)(q – 1) are relatively prime. By "relatively prime" we mean that two numbers have no prime factors in common. An example of a pair of relatively prime numbers is 14 = 2 x 7 and 15 = 3 x 5.
• Now find a number d such that (de – 1) is evenly divisible by (p – 1)(q – 1). Note that (p – 1)(q – 1) is an even number because both p and q, being prime numbers, are odd.

Example: p = 5, q = 11.
Thus pq = 55; (p – 1)(q – 1) = 40 (prime factors 2 and 5).
Let us choose e = 3 (recall the condition 1 < e < pq)
So (3d – 1) should be divisible by 40: one solution is d = 27, giving (3d – 1) = 80.

• Next we need to define the concept of “conjugate modulus”. We write a = x (mod n), defined such that a and x leave the same remainder when divided by n. It follows that a – x is exactly divisible by n.

Example: 14 = 8 (mod 3) ; 14 – 8 = 6 which is divisible by 3
The remainder in both cases following division by 3 is 2

Encryption formulae

• We define a message by the character T.
• There is a formula for encryption formula: C = T^e(mod pq)
• There exists a corresponding formula for decryption: T = C^d(mod pq)
• Note that this pair of equations is not symmetric. This is the basis for the method.

Example: using pq = 55, e = 3, d = 27 from above.
Take T = 6; Thus C = 6³(mod 55) = 216(mod 55) = 51.
The reverse gives T = C^d(mod 55) = 51²⁷(mod 55) = 6 (a method by which this can be derived is given below)

• In public key crytography, e and pq are the public key pair, which you give away. People can use this to encrypt messages to send to you.
• Similarly, d and pq are the private key pair, which you keep secret. You use this to decrypt messages encrypted using your public key.
• Recall that d and e are linked via the relationship between de – 1 and (p – 1)(q – 1). Only you know d, and this can only be calculated if you know both p and q. The point is that no-one knows p or q, only their product pq. In principle you could search for the two prime factors of pq, but in practice this task can be made completely impractical if p and q are large enough.

Factorisation

• The big problem is to factorise the equations.
• Take our example, 51²⁷(mod 55). We can note that 27 = 1 + 2 + 2³ + 2⁴ = 1 + 2 + 8 + 16.
• We will use the following result:
  • for a = x(mod n); b = y(mod n)
  • we have ab = xy(mod n)
• This enables us to write to solve 51²⁷(mod 55) = 51 x 51² x 51⁸ x 51¹⁶(mod 55). We write a table:
  • 51(mod 55) = 51
  • 51²(mod 55) = 2601(mod 55) = 16
  • 51⁴(mod 55) = 16²(mod 55) = 256(mod 55) = 36
  • 51⁸(mod 55) = 36²(mod 55) = 1296(mod 55) = 31
  • 51¹⁶(mod 55) = 31²(mod 55) = 961(mod 55) = 26
• Thus we can write 51²⁷(mod 55) = 51 x 16 x 31 x 26(mod 55). Using the above result we can reduce this to (51 x 16) x 31 x 26(mod 55) = (46 x 31) x 26(mod 55) = (51 x 26)(mod 55) = 6, which is the number we started with.