Public Key Algorithms In Cryptography
Only a couple of practical public-key schemes are developed so far. They depend upon use of trap door functions of large number of produce keys. keys Ke and Kd are a pair of very large numbers, and encryption function performs an operation, such as exponentiation on M, using one of them. Decryption is similar function using other key. If exponentiation uses modular arithmetic, it can be shown that result is same as original value of M; that is: D(Kd, E(Ke, M)) = M.
Principal wishing to participate in secure communication with others makes pair of keys, Ke and Kd, and keeps decryption key Kd secret. Encryption key Ke can be made known publicly for use by anyone who wants to communicate. Encryption key Ke can be seen as part of one-way encryption function E, and decryption key Kd is piece of secret knowledge that enables principal p to reverse encryption. Any holder of Ke (which is widely available) can encrypt messages {M}Ke, but only the principal who has the secret Kd can operate the trapdoor. Use of functions of large numbers leads to large processing costs in computing functions E and D. We shall see later that this is a problem that has to be addressed by the use of public keys only in initial stages of secure communication sessions. RSA algorithm is certainly most widely known public-key algorithm. Another class of algorithms is based on functions derived from behavior of elliptic curves in plane. These algorithms offer possibility of less costly encryption and decryption functions with same level of security, but their practical application is less advanced and we deal with them only briefly.
RSA
Rivest, Shamir and Adelman (RSA) design for public-key cipher [Rivest et al. 1978] is based on use of product of two very large prime numbers (greater than 10100), relying on fact that determination of prime factors of such large numbers is so computationally difficult as to be effectively impossible. Despite extensive investigations no flaws have been found in it, and it is now very widely used. An outline of method follows. To find a key pair <e,d>:
1) Choose two large prime numbers, P and Q (each greater than 10100), and form
N = P x Q
Z = (P–1) x (Q–1)
2) For d, choose any number that is relatively prime with Z (that is, such that d has no common factors with Z).
We illustrate computations involved using small integer values for P and Q:
P = 13, Q = 17 — > N = 221, Z = 192
d = 5
3) To find e, solve the equation:
e x d = 1 mod Z
That is, e x d is smallest element divisible by d in series Z+1, 2Z+1, 3Z+1, …
e x d = 1 mod 192 = 1, 193, 385, …
385 is divisible by d
e = 385/5 = 77
To encrypt text using the RSA method, plain text is divided into equal blocks of length k bits, where 2k < N (that is, such that numerical value of block is always less than N; in practical applications, k is usually in range 512 to 1024).
k = 7, since 2⁷ = 128
Function for encrypting single block of plain text M is:
E’(e,N,M) = M^e mod N
For message M, cipher text is M⁷⁷ mod 221
Function for decrypting a block of encrypted text c to produce the original plain text block is: D’(d,N,c) = c^d mod N
Rivest, Shamir and Adelman proved that E’ and D’ are mutual inverses (that is, E’(D’(x)) = D’(E’(x)) = x) for all values of P in the range 0 ≤ P ≥ N.
Two parameters e, N can be regarded as key for encryption function, and similarly parameters d,N represent a key for the decryption function. So we can write Ke = <e,N> and Kd = <d,N>, and we get encryption functions E(Ke, M) ={M}K (notation here indicating that encrypted message can be decrypted only by holder of private key Kd) and D(Kd, {M}K) = M.
It is worth noting one potential weakness of all public-key algorithms because public key is available to attackers, they can easily generate encrypted messages. Thus they can attempt to decrypt an unknown message by exhaustively encrypting arbitrary bit sequences until a match with target message is achieved. This attack, which is known as a chosen plain text attack, is defeated by ensuring that all messages are longer than key length, so that this form of brute-force attack is less feasible than a direct attack on key.
An intending recipient of secret information must publish or otherwise distribute pair <e,N> while keeping d secret. Publication of <e,N> does not compromise secrecy of d, because any attempt to determine d requires knowledge of original prime numbers P and Q, and these can only be obtained by factorization of N. Factoring of large numbers (we recall that P and Q were chosen to be > 10100, so N > 10200) is extremely time-consuming, even on very high-performance computers. In 1978, Rivest et al. Concluded that factoring a number as large as 10200 would take more than four billion years with best known algorithm on a computer that performs one million instructions per second. A similar calculation for today’s computers would reduce this time to around a million years.
RSA Corporation has issued a series of challenges to factor numbers of more than 100 decimal digits. At time of writing, numbers of up to 174 decimal digits (576 binary digits) have been successfully factored, so use of RSA algorithm with 512-bit keys is clearly unacceptably weak for many purposes. RSA Corporation (holders of patents in RSA algorithm) recommends a key length of at least 768 bits, or about 230 decimal digits, for long-term (~20 years) security. Keys as large as 2048 bits are used in some applications.
Above strength calculations assume that currently known factoring algorithms are best available. RSA and other forms of asymmetric cryptography that use prime number multiplication as their one-way function will be vulnerable if a faster factorization algorithm is discovered.
Elliptic Curve Algorithms
Method for generating public/private key pairs based on properties of elliptic curves has been developed and tested. Keys are derived from a different branch of mathematics, and unlike RSA their security does not depend upon difficulty of factoring large numbers. Shorter keys are secure, and processing requirements for encryption and decryption are lower than those for RSA. Elliptic curve encryption algorithms are likely to be adopted more widely in future, especially in systems such as those incorporating mobile devices, which have limited processing resources. Relevant mathematics involves some quite complex properties of elliptic curves.
