Cryptography: Project Proposal

Abstract. The presumed problems of discrete logarithm (DLP) in the finite fields are the basis of many public cryptosystems keys. For instance, the secure identification option of the Sun Network File system uses discrete logarithms with a prime p of 192 bits. Presently, the DLP has become the subject of concern to many cryptographers and mathematicians because of its computational problems. The cryptosystems generally rest its securities on the assumption of mathematical problems that are difficult to solve. The difficulty of DLP in most cases tends to lie in the fact of having a one-way property making its computational complexity measured by algorithm computing time solving the mathematical problems. This paper describes the different steps necessary to solve the problem of discrete logarithm as well as discussing various state-of-the-art results obtained for the solution of Discrete Logarithm Problem (DLP). The paper will also present the Sun Network File System (SNF) while discussing its deficiencies.

Table of Contents

TOC o “1-3” h z u 1.0 Introduction PAGEREF _Toc350791829 h 32.0 The Sun NFS Cryptosystem PAGEREF _Toc350791830 h 32.0.1 Different steps necessary to solve the discrete logarithm problem (DLP) PAGEREF _Toc350791831 h 42.0.2 The state-of-the-art results obtained for the solution of DLP. PAGEREF _Toc350791832 h 42.0.3 SUN NFS cryptosystem deficiencies PAGEREF _Toc350791833 h 5

1.0 IntroductionThe Discrete Logarithm Problem (DLP) shows various mathematical problems that looks simple, however there are computational presumption making it to be difficult. The DLP is significant given that, it has various applications in cryptography field. Nevertheless, DLP study constantly bears a great significance in academics making it the subject of interest for cryptographers. The cryptosystems are secured only under definite computational assumptions. Most organizations today use Diffie-Hellman as a public key algorithm for their exchange for key. This is because it is considered as to be much secured when used with sufficient long keys and generators. However, its security usually relies on the problem of discrete logarithm which is assumed to be very computationally the same to the factoring large integers. The Diffie-Hellman is believed to be sensitive to choices of stronger prime and generators.

2.0 The Sun NFS CryptosystemThe Sun security option for their NFS can be built in the basic of Sun Remote Procedure Call (RPC) along with providing an authentication to both the users using the public key cryptosystem that looks as the modification of Diffie- Hellman key exchange system. In the Sun system, the prime is p while the integer is g which happens to be the same for all the users on every machine across the world using the software. Each machine is identified with a secret key m and p is the public. In this case, p always has 192 bits. The authentication generally requires proving that a person is able to possess the key m, although this does not have any effect on the systems’ security. When someone is breaking the Sun system, this is only necessary when finding the two values of m and p.

2.0.1 Different steps necessary to solve the discrete logarithm problem (DLP)There are different steps to be followed when solving the Discrete Logarithm Problem. First step is to let F = GF (q) while taking µ as a primitive element of letter F, whichever c in F* has a unique representation as c = µm, for 0 <= m <= q-1. C can be computed from µ and m with only 2[log2 q] multiplications. In this case, the binary representation of letter m will definitely give the order of the needed multiplications that consist of only squaring as well as multiplying by µ. The second steps involves sorting the pairs for instance, if m = 171 then 171 = 128 + 32 + 8 + 2 + 1 = (10101011)2. The third and the last steps involves computation, the computation of µ171 is then carried out by starting with 1, then, working from the most significant bit down, we square the current value and if there is a 1 in the binary representation we also multiply by µ. Thus, µ171 = ((((((((1)2µ) 2)2µ) 2)2µ) 2)2µ) 2µ.

2.0.2 The state-of-the-art results obtained for the solution of DLP.The results obtained for the solution of DLP makes an exponentiation in a finite field a state of the art. The results obtained can be used for a public exchange of protocol keys. The public knowledge is q, and µmU for each user U, although each user manages to keep the secret of the value mU. When trying to exchange keys exclusive of the transmission, A has to look up for the B’s public key as well as proponent it with its secret exponent. And likewise, B does the same to the A’s public key. Consequently, each of them will have to calculate the similar key value µmBmA = µmAmB. Solving the discrete logarithm problem for q, the Diffie and Hellman has to use a value of q which is at least 100 bits long to obtain the correct results when using discrete logarithm problem (DLP). In summary, the results obtained for the solution of DLP is that, the computing discrete logarithm module, the prime can be only a little harder compared to the factoring integers having the same size. For instance, with the same amount of the effort used in factoring 110 decimal digits integers can be used in computing the discrete logarithms module primes of up to 100 digits.

2.0.3 SUN NFS cryptosystem deficienciesIn spite of using SUN NFS cryptosystem as the best machine for solving logarithm problems, there are still several problems of using it as a larger module. The problem can be stopped by using a faster machine that is ready to compute faster. The speeds of a small workstations are generally increasing rapidly. However, using of faster algorithms can be of a great significance at the level of the basic arithmetic using the pre-computed tables.2.0.4 Recommendations for having a secure size for the prime number p

The most recommended way of securing size for the prime number p in the Diffie-Hellman algorithm is to improve the security of the scheme by having different prime for all the users. With the renowned logarithms problems, the problem of pre-computation of discrete logarithms if applied to a 100 decimal digit prime, it might use about 100 computers for computation. However if the prime happened to be used by everyone on the same network, then it will be necessary to obtain individual keys in a minute as compared when the user have different primes that makes it to be obtained more than a year. For this case, Diffie Hellman Scheme may be one of the only one of many methods that can be used for aunthetication.