Assignment 9 - due Friday, December 3, midnight, by email
Please do work on your own - no group work. If you are stuck,
contact me. Collaborating on this assignment will be viewed
as cheating.
Problem 1
We will work on the Diffie-Helman shared-key cryptosystem first. See my
slides from last week.
Part a. For this part, we will use last week's lecture on Diffie-Helman.
See slides. What I am going to do is email with one of my graduate students,
Jason. We are going to use Diffie-Helman to agree on a shared key. You will see
all the transactions between us. Your job is to write a program that will
crack Diffie-Helman, and hence, obtain our shared key.
You can see a rough algorithm for the cracking problem off last week's slides.
Here is a start:
<![CDATA[
import java.util.*;
import java.math.BigInteger;
class DH_Cracker {
public static void main( String [] args ){
//all of these are public (see email)
long Y = ...;
long P = ...;
long alpha = ...;
long beta = ...;
//these two are secret and you have to figure them out
long A;
long B;
/**
You will need to use a new method to compute
q**r%n. It is called powerMod. It takes three
arguments: powerMod( q, r, n). It returns a long
value which is the result of taking q to the r,
and then modding that with n.
**/
//your cracking code goes here. See slides for hint.
System.out.println( "The value of A is " + A );
System.out.println( "The value of B is " + B );
} //main
static long powerMod( long q, long r, long n ){
return new BigInteger(""+q).modPow( new BigInteger(""+r), new BigInteger(""+n) ).longValue();
}
} //DH_Cracker
]]>
Below is the correspondence between Jason and I that you were able to capture.
Note that before the first email I send, I have (secretly) chosen an A. I don't
send this, but keep it locked away somewhere. Before Jason sends his message,
he chooses his secret number B and locks it away. Your job is to discover
these two numbers we have locked up.
<![CDATA[
Date: Thu, 18 Nov 2004 16:00:42 -0800
From: Stephen Fickas <fickas@cs.uoregon.edu>
To: Jason Prideau <jprideau@cs.uoregon.edu>
cc: Stephen Fickas <fickas@cs.uoregon.edu>
Subject: I want to send you some sensitive information
Let's use Diffie-Helman to generate a shared key.
I propose we use the following values:
Y=5779
P=10273
Here is my value for alpha. I'll wait for your value of beta.
alpha=1494
Steve
===============================================================
To: "'Stephen Fickas'" <fickas@cs.uoregon.edu>
From: "Jason Prideaux" <jprideau@cs.uoregon.edu>
Subject: RE: I want to send you some sensitive information
Date: Thu, 18 Nov 2004 16:11:06 -0800
Okay. Here's my value for beta:
beta=1692
Jason
]]>
At this point, we both calculate our shared key and can then
use that to start sending encrypted messages. I won't carry
on that conversation here, because you have all you need to
get A and B. You don't need to see the encrypted messages
that follow.
Turn-in: Your code and the secret values of A and B.
Problem 2
Ok, on to the main event: Chapter 37 - public key cryptography.
Read chapter 37 in Dewdney. However, note that we will *not* be using the
knapsack algorithm, but instead, the RSA cryptosystem. So you can read the
pages up to 256 to get a general understanding of the early days of public
key cryptography. But page 256 describes the actual concept we will be using.
Part a. Jason and I suspect that you have been able to crack our shared key
system. So we have chosen to use the RSA algorithm. I would like you to write
a program that will crack RSA. More specifically, I would you to guess my
private key. Here is a start. (This program can be found in the code directory.
Don't copy and paste this. Instead, download the one in code directory.)
<![CDATA[
import java.util.*;
import java.math.BigInteger;
class RSA_Cracker {
public static void main( String [] args ){
//these pair of numbers are Steve's public key
long e; //you don't need this number for part a - but it is public knowledge
long n = ...L; //you know that n = p*q. Note the L at end of number.
//these numbers are Steve's private key
long p; //a prime
long q; //a prime
long d; //you won't need to com;ute this for part a
/**
Your cracking code goes here. It is a matter of factoring n, i.e.,
you need to find p and q. And you know that they are both
primes. General algorithm:
1. loop through all numbers p from 2 to n-1
1. if p divides n evenly, you have found your answer
Hint: I would use a while loop so you can define a boolean
variable found_it that will allow you to exit the loop when you
find the right p. This is similar to your prime checker
code from last week.
**/
System.out.println( "The value of p is " + p);
System.out.println( "The value of q is " + q); //once you know p, you should know q as well
} //main
static boolean isPrime( long x ){
return new BigInteger(""+x).isProbablePrime( 1 ); //.5 probability of being correct
}
static long powerMod( long q, long r, long n ){
return new BigInteger(""+q).modPow( new BigInteger(""+r), new BigInteger(""+n) ).longValue();
} //RSA_Cracker
]]>
Here is the email between Jason and I.
<![CDATA[
Date: Thu, 18 Nov 2004 16:21:53 -0800
From: Stephen Fickas <fickas@cs.uoregon.edu>
To: Jason Prideau <jprideau@cs.uoregon.edu>
Subject: Hi Jason
I think the students have cracked our Diffie-Helman
shared key. I think it would be wise to go to an
RSA scheme. I've generated the following public
key for myself:
e = 15
n = 109275027171421
Go ahead and send me a test message to try it out.
Steve
============================================================
From: "Jason Prideaux" <jprideau@cs.uoregon.edu>
To: "'Stephen Fickas'" <fickas@cs.uoregon.edu>
Subject: RE: Hi Jason
Date: Thu, 18 Nov 2004 18:30:18 -0800
Here is my top secret message encoded with the
public key that you sent:
8560903022630
-Jason
]]>
Turn-in: a program that can be used to find my secret key (values of p and q). Note, you do
not have to turn this in as a separate program if you solve part b below. But it would be
a good idea to save your solution here in PartASolution so you have it in case you cannot
get part b working. Please tell me how many seconds it takes you to crack my code (use
your watch to count seconds).
Part b. This is optional. I will give you 50 extra points if you take it on.
Think about ways to
make your code run faster, i.e., optimize the loop. I can think
of at least two ways to cut the amount of looping in half.
Go ahead and make one or more changes, and then time your code
again. Report results.
Turn-in: your modified code and timing results. Note that it is not required
that your optimization produces any speed-up. As long as it makes logical sense.