CSE 247 Module 12: Diffie–Hellman
one-time pad (OTP) is a provably unbreakable
encryption scheme. Alice and Bob each have identical copies of the OTP, and
they use the OTP's values to communicate secretly.
Messages can be encrypted
and decrypted using exclusve-or as shown
The key problem, so to speak, in using an OTP is distribution of the pad. Transport of the pad admits the possibility of Eve seeing its contents, and
once known, Eve can decrypt messages sent by Alice and Bob.
We solve the OTP distribution problem here by using Diffie–Hellman
to compute the OTP by Alice and Bob simultaneously. The values are
computed by generating (most likely different) random values separately by Alice
and Bob, which are turned into agreement on each side using Diffie–Hellman.
Overview of the software for this assignment
- This program demonstrates the Caesared
class,which rotates certain characters of a message. You looked
at this in studio, but run it again here to
make sure you understand its effects. In particular, it rotates only lower-case
characters, so that punctuation and upper-case letters are preserved in
- As described in lecture, this
class generates powers of a base to a specified modulus.
The class can be used in two ways:
- Instantiate an MExp with a specified base and modulus,
and then use toThePowerOf to compute powers of the base to
the specified modulus. This is useful for RSA encryption, where the
base and modulus stay the same, and each character c is encrypted
by raising the base to the c power.
- The static method gToTheXModP accepts a base, exponent, and
modulus and computes the appropriate result.
It is often the case that we want all results computed for a certain base
and modulus. The DHFactory captures the base and modulus and
ensures that each call to nextDH(long privKey) returns a
Diffie–Hellman object with the agreed upon base and modulus.
- This is the only class you must complete for this assignment.
The constuctor accepts the base, privKey (private key), and modulus.
solution must arrange for the following:
- getPubKey() must return baseprivKey mod modulus. You are welcome to use the MExp class to
compute your result.
- getAgreedNum(long otherPubKey should compute the
Diffie–Hellman agreement result by returning
otherPubKeyprivKey mod modulus.
In the running example
from lecture, Alice and Bob agreed upon a base and
modulus of 5 and 23, respectively.
Alice's privKey was 6, and so a call to getPubKey() would
return 8 for her,
which is 56 mod 23.
Bob's public key was 19, so a call on Alice's DH object of
getAgreedNum(19) would return 2, computed
as 196 mod 23—the number upon which Alice and
Bob agreed in lecture.
is the unit test for your DH implementation.
Make sure you pass this test before submitting your work.
- computes the Alice and Bob results described above, as well as the
results of a random computation.
- is a participant in using a one-time pad to rotate and unrotate
text for encryption and decryption, respectively. The agents are used by…
- extracts the next public key from the sender and receiver.
- asks the sender to rotate the next character of a message by using
the receiver's public key (along with the sender's private key). That
rotational amount is essentially the next integer of a virtual one-time pad.
- the receiver is sent the rotated character, along with the public key
of the sender. It will use its private key and that public key to determine
the agreed upon amount of rotation, and then unrotate the supplied
character to see it clearly.
- demonstrates the SendMessage class with two messages,
one all caps (so nothing is rotated) and one with all lower case.
In studio, all characters were rotated the same
amount and you determined that rotation value by analysis. Here, each
character is rotated a different amount, depending on the
Diffie–Hellman agreement integers.
Thus, a given character (such as e) will not be rotated the
same amount throughout the message.
- allows you to type in a string and see it sent via the one-time pad
This seems like a perfect encryption scheme, because it apparently
uses a one-time pad
between the sender and receiver. Below is a sample of output from
Looking at the first three letters of the lower case alphabet portion,
which were received properly as
a, b, and c, they were sent as r, y, and r.
So a was sent as r, but two characters later,
c was also sent as r. This is because the rotation
amount changes for each character according to the one-time pad computed
by the sender and receiver.
Is this a perfect encryption scheme? Why or why not?
Submitting your work (read carefully)
- Make sure your code passes the tests as we originally gave them to you.
It's those tests we will run to see if your code functions properly.
- Make sure you eliminate or disable any print statements you used
for debugging, as they may slow down your code when we test and cause you
- Make sure you have placed ticker.tick() calls appropriately
in your solution. Failure to do so will cost you points on this assignment.
- Make sure your solution's ticks behave in a manner consistent with the
asymptotic complexity you should see for your solution.
You must commit and push all of your work to your repository. It's best to do this
from the top-most level of your repository, which bears your name and student ID.
You can tell that your code was pushed by logging into
bitbucket.org, clicking on
your repository, and seeing the
push in the associated log traffic.
Because of this, you have no excuse for failing to push your code. Check
and make sure it was pushed so your work is counted.
Work that is not pushed will receive no credit.
Last modified 14:14:23 CST 01 December 2016