Cryptosystems Based on Discrete Logarithm - Essay Example

Rather it will be sent as the binary string corresponding to another number which depends on the number 161 according to some fixed rule. For example we can subtract 161 from the largest 3-digit number 999 and send the result 838. Thus the rule for encryption is: But there is a drawback of using this method of encryption. The receiver has also to be conveyed what rule has been used for the encryption, so that he can decrypt it. If some hacker in between cracks the information about this rule, then it is a trivial job for him to get the number 161 back from 838.

For, he will easily deduce from this rule for encryption, the rule for decryption: Therefore we make use of an ingenious technique. This technique makes the decryption of the encrypted message very difficult (if not impossible) for any third person (hacker). In order to know the technique, we need to learn some of the mathematical concepts. So first of all we take up these. Given two natural numbers and an integer n, then by the modular exponentiation of b to the base a, which is symbolized as, we mean obtaining the remainder on dividing.

Thus, for example,, on being evaluated yields 7. Observe that we can also write using the above concept of congruence modulo m. Further given two natural numbers and an integer n, then the smallest (non-negative) integer x (if exists) such that, is known as the discrete logarithm of b to the base a. (http://www.math.clemson.edu., 1)To find the modular exponentiation is an easy task even if the numbers a and b are large. For, we can make use of the 'square and multiply method' (Schneier, 244) as explained in what follows: We know that stands for the remainder obtained on dividing by n.

For large values of a and b, it will be very difficult to evaluate the expression. But to evaluate is much easier. For we can find the remainder (say) on dividing, multiply and obtain the remainder (say) on dividing the product by n; and so on till the number a is taken b times for the multiplication and thus the last remainder is obtained. As an illustration let us compute. Let us find the remainder on dividing; we get 1. Then find the remainder on dividing 1.3 (=3) by 8; we get 3. Now find the remainder on dividing 3.3 (=9) by 8; we get 1.

Again find the remainder on dividing 1.3 (=3) by 8; we get 3. Finally find the remainder on dividing 3.3 (=9) by 8; we get 1, which is the result of the modular exponentiation. For the sake of verification we can compute. It comes out 729. On dividing 729 by 8 we get 1, the same result. However, to find the discrete logarithm for large numbers is a very hard problem by any means. So if we base the cryptosystem on the discrete logarithm, it becomes extremely hard for a hacker to crack it. Now we will describe this system.

The basic work for the development of the system was done by Diffie and Hellman in 1976, but the system was fully developed by ElGamal. ((http://www.math.clemson.edu., 2). First we take up the work done byDiffie-HellmanThese two fellows invented an algorithm which can be used by two persons to generate a secret common key. The algorithm is explained below.Let Alex and Bobby be the two persons who are going to exchange some information over the internet