This assignment is Homework 18, and is due at classtime on Monday, April 10.

Assignment

  1. This question is about the Diffie-Hellman key exchange.

    Suppose that Alice and Bob want to establish a shared secret over the internet. They (publicly) agree to use the prime p = 67 and generator g = 2.

    1. Alice chooses secret number a = 5. What does she send to Bob?
    2. Bob chooses secret number b = 42. What does he send to Alice?
    3. What is Alice and Bob's shared secret number?
  2. This question is about the Diffie-Hellman key exchange.

    Realizing that p = 67 is much too small of a prime to use for security purposes, Alice and Bob now (publicly) agree to use the prime p = 22953686867719691230002707821868552601124472329079 and generator g = 22.

    1. Alice chooses secret number a = 100. What does she send to Bob?
    2. Bob chooses secret number b = 4039. What does he send to Alice?
    3. What is Alice and Bob's shared secret number?

    Note that a 50-digit prime is still too small for security purposes. Real implementations of the Diffie-Hellman key exchange use primes with hundreds of digits. See, for example, this page, and note that the primes listed are considered "small".

  3. Recall that a prime number \(n\) is a positive integer that has no factors other than 1 and \(n\). Many encryption algorithms depend on prime numbers. Write a function that determines whether or not a number is prime. Your function header should be:

    def isPrime(n):

    For example, isPrime(7) returns True, while isPrime(9) returns False.

    Since 1 is not a prime number, make sure that isPrime(0) returns False!

    Hint: It suffices to test whether \(n\) is divisible by any integer between 2 and \(\sqrt{n}\). If no such integer divides \(n\), then \(n\) is prime. To do this, you probably want to use math.sqrt and math.floor (refer to the Python math documentation).

  4. This question asks you to use Python to write a recursive function.

    The greatest common divisor (GCD) of two integers is the largest number that divides both integers without remainder.

    Write a recursive function gcd(a, b) that finds the GCD of two integers a and b. Assume that a > b ≥ 0. The GCD can be computed by the following algorithm:

    For example, gcd(63, 24) should return 3, and gcd(90, 9) should return 9.

Submitting your work

After you have finished your solutions, paste them into a single Python file. Make sure that Python can run your file without error! Please use comments (lines that begin with a # symbol) to clearly state the problem number for each solution in your file. Save your file and upload it to the HW18 assignment on Moodle.