What need to be Implemented The first step for you is to understand the steps in

Question

What need to be Implemented The first step for you is to understand the steps involved in the Diffie-Hellman key exchange protocol. You need to implement a program as follows (a). Your program should take the size of the prime number p (in bits) as an argument during execution.

Based on the size of p, your program should be able to compute and print the values of p, the generator g, random numbers a, b Z p , and other intermediate results computed in the Diffie-Hellman protocol.

Note that the values of p, g, a, and b have to be generated randomly by your program based on the input argument.

Your program should finally output the shared key generated. (b). Suppose your program name is Assignment2.java.

Here is a sample case of what your code is expected to output upon its execution >> java Assignment 5

The value of p selected: 23

The value of g selected: 5

The value of a selected by Alice: 6

The value of b selected by Bob: 15

The value of A sent to Bob by Alice: 8

The value of B sent to Alice by Bob: 19

The value of key shared between Alice and Bob: 2

In the above scenario, the program takes 5 as input meaning that the size of p should be 5 bits (i.e., the value of p should be selected in the range (16, 31]). Note that since the values of p, g, a, b are assumed to be generated randomly as per the Diffie-Hellman protocol, their values and the shared key value can be very different during each execution.

Please note that you can use any programming language (C, C++, Java, etc.) to implement this assignment as per your convenience. However, it is your responsibility to check whether the programming language you select supports proper crypto libraries that you may want to use in your program. C, C++, JAVA and many other programming languages provide support for various crypto libraries which you can directly use to compute generators and random numbers in a group. Also, note that your program should be able to handle large numbers (for example of size 1024 bits), therefore, you have to use large-number arithmetic built-in libraries depending on the language used.

Explanation / Answer

Beginning of Public Key Cryptography   
Public Key Cryptography started in 1976 when 31-year-old computer wizard named Whitfield Diffie came up with a new system that surprised the world of ciphers. As a child, Diffie devoured all the books he could find on the subject of cryptography. Certainly there is something about codes -- secret rings, intrigue -- that appeals to youngsters. Diffie, son of an historian, took them very seriously.
Diffie-Hellman Key Exchange

In 1976, the two Mathematicians Whitfield Diffie and Martin Hellman devised the notion of Public-Key-Cryptography in “New Directions in Cryptography” . They showed how two communication partners that are at different locations can publicly create a common key without fearing that a third person who observes the key generation could crack it. The public creation of a common secret key was the first major step in Public Key Cryptography. It enables two parties to establish secure communication without having to deliver the secret key at some earlier point in time.

Since you know how to perform MOD arithmetic you will understand the Diffie-Hellman Key Exchange between Alice and Bob easily. Here it is in 4 steps. The two left columns show the general key exchange protocol. The two right columns display an example for the key exchange protocol:

1) Alice and Bob publicly pick 2 integers:
a)   a prime number p
b)   and an integer s between 1 and p.     1) Alice and Bob publicly pick
a)   p = 11 and
b)   s = 3.
2) Alice picks a random number a that is less than p.
   2) Bob picks a random number b that is less than p.   2) Alice picks a=2.   2) Bob picks b=4.
3) Alice computes
A = sa MOD p and sends A to Bob.
   3) Bob computes
B = sb MOD p and sends B to Alice.   3) Alice computes
A = 32 MOD 11 = 9    3) Bob computes
B = 34 = 81
= 4 MOD 11
4) Alice computes the key K = Ba MOD p.   4) Bob computes the key K = Ab MOD p.   4) Alice computes
K = 42 MOD 11 = 5    4) Bob computes
K = 94 = 6561 MOD 11 = 5.

We have to answer the following two questions:
1)   Why do Alice and Bob always end up with the same key K ?
2)   Why can’t an eavesdropper compute K ?

Answer to questions 1):
Alice and Bob compute the key K in the final step as follows:
Alice: K = Ba = sba MOD p.
Bob: K = Ab = sab MOD p.
Since sba = sab MOD p both Alice and Bob compute the same key K.

Answer to questions 2):
Say, an eavesdropper did a great job by intercepting the values A and B, p and s. In order to uncover the key K he has to compute either a or b. Mathematics teaches that this is impossible if a, b, p, s, A, B were chosen as of 100-digits numbers or larger.
The reason: although it is quite simple to compute i.e. A = sa MOD p, however, solving this equation for a is impossible. More formally stated: Although the “discrete exponential function” can be executed, its inverse, the “discrete logarithm function” can not. Hence, the “discrete exponential function” is an example of a “One-Way function”. We will study such functions later on this chapter.

4.1.2 Diffie’s Search for a Public Key Cryptosystem

While Hellman was working on the public key exchange algorithm, Diffie continued his research. His public key exchange idea is feasible, however, it has one major practical limitation: Both parties have to first create their secret key in a mutual process. As a consequence, the sender has to wait until the common key is created to send the encrypted message. Diffie tried to overcome this deficit as follows: Each party shall possess a key pair, a public and a private key. I.e. Alice’s public key is used by Bob to encrypt the message for Alice whereas her private key is used to decrypt Bob’s encrypted message.

Although it was not Diffie who actually designed an algorithm that realizes his provoking idea of a public and private key, he deserves credit for making the inconceivable conceivable. He initiated mathematical research groups worldwide to find an appropriate mathematical setting that realizes his vision. The research question was:
Which mathematical function allows anybody to encrypt a secret message for Alice using her publicly known encoding key e and prevents everybody but Alice to decrypt such cipher message?
It requires an experienced mathematician to find such one-way functions since most functions are two-way and can thus be reversed. I.e. A Caesar right shift can be reversed by a corresponding left shift. Mathematically, since addition can be reversed by subtraction it is (the simplest) two-way function.   

The winners of the worldwide search for appropriate one-way functions are the 3 Israelis Ronald Rivest, Adi Shamir and Leonard Adleman . Let’s talk for a moment about how the three MIT researchers Rivest, Shamir and Adleman came up with their idea for the RSA Ciphers in 1977.

The irony of the process to create the RSA Cipher is that Rivest, Shamir and Adleman originally tried to prove that Diffie’s idea of a public and a private key could NOT be realized by showing that there are no appropriate one-way functions. Thus, while being unsuccessful the three Cryptographers became really successful: While Rivest devised encryption ideas, Adleman tried to attack them and Shamir contributed to both . The final RSA idea was ground-breaking as it simultaneously answers the contemporary quests for a public key cipher as well as a scheme to perform digital signatures.

4.1.3 The RSA Cipher is a Public-Key-Cryptosystem

Given sufficiently large key lengths, RSA realizes the

Public-Key Property:
The knowledge of the encoding key does not reveal the knowledge of the decoding key. Even the usage of the most powerful computers combined will not suffice to crack the secret decoding key based on the knowledge of the publicly known encoding key.   

Although the encoding keys are publicly known, nobody in the world can make use of that knowledge in order to crack the secret decoding key. WHY is that? How can the knowledge of the encoding key NOT reveal the decoding key? What do we have to consider when choosing the encoding key so that its decoding key remains secret? The next section will tell you.

As a consequence:
Only one key pair per person is needed. Therefore, a total of only n key pairs are needed for n communicating people.   

In particular, 100 people communicating just need 100 key pairs. The 100 encoding keys are publicly known. Think of them being listed in a directory. These days the internet provides the means to locate the public encoding key of any correspondent. Currently, the public keys of the most popular encryption software, “Pretty Good Privacy” or simply “PGP”, can be looked up at http://pgp.mit.edu . The corresponding 100 private decoding keys must be kept absolutely secure (i.e. in a vault) by its respective owner. They should not be saved on the hard-drive or other accessible devices.

Exercise 1: Ever since its invention in 1978, RSA has heavily impacted secure communication such as financial transactions, electronic mail, Pay TV, secure telephone calls etc. To gain further insight into RSA and its impact, research RSA usage and security on the internet by searching for “RSA encryption” and visiting sites such as www.rsasecurity.com.

Exercise 2: Find out about the RSA implementations in the Netscape Navigator for secure web-based transactions.

Exercise 3: (Discover how the RSA-Cipher works): Click here to perform your own RSA encryption. Try to figure out how the cipher numbers are produced from the plain letter numbers. By doing so you can discover for yourself how the RSA encryption works before I will introduce it in the next section.   
The RSA Cipher is actually quite easy to understand. Don’t be mislead: The fact that a cipher can be executed easily does not make it insecure. On the other hand, ciphers that are hard to execute are not necessarily secure. The 4 steps involved in the RSA Cipher are displayed in the middle column. In the right column I demonstrate how the word “SAFE” is en- and decrypted using the RSA Cipher. We use the same letter values as in the previous chapters to encrypt: S=18, A=0, F=5, E=4. Again, the choice of the letter values is arbitrary. It just matters that sender and recipient use the same letters values. Let’s go ahead and perform the RSA encryption.

Example for RSA Encryption and Decryption:   
1.   Step:
Preparation   a) Choose two primes p and q so that their product n=p*q is greater than the used alphabet length M (i.e. here M=26).
c)   Compute (n).   a) Say p=3 and q=11, then n=33

b) (33) = (3-1)*(11-1) = 20
2. Step:
Encryption
uses the public key (n,e)   a) Choose a public encoding key e that has to be relative prime to (n).
b) We now encrypt each plain letter P by computing

C=Pe MOD n.
   a) Here, possible values for e are 3, 7, 9, 11, 13, 17, 19. Let’s pick e=3.
b) We encrypt as follows:

S =18: 183 = 24 MOD 33
A = 0: 03 = 0 MOD 33
F = 5: 53 = 26 MOD 33
E = 4: 43 = 31 MOD 33

3. Step:
Decryption
uses the private key
(d,n)   a) The private decoding key d is chosen as the inverse of e MOD (n): e * d = 1 MOD (n)
Mathematically, find integers d and k that fulfill: e * d = 1 + k * (n) via the Extended Euclidean Algorithm.

b) We decrypt by computing P=Cd MOD n
   a) d=7 since 3*7 = 1 MOD 20.

b)
247 = 18 MOD 33, 18=S.
07 = 0 MOD 33, 0=A.
267 = 5 MOD 33, 5=F.
317 = 4 MOD 33, 4=E.

Remark: I computed the above powers MOD 33 using the Windows 98 calculator. Let’s verify by hand that i.e. the computation of 317 actually yields 4 MOD 33:
Since 31= -2 MOD 33 I can just multiply –2 by itself 7 times to compute (-2)7 and obtain –128. Now, –128 = -95 = -62 = -29 = 4 MOD 33 which produces the calculator answer.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.