MIDTERM
CSC 507.122
CSC 609.122
Out: Thursday, March 29, 1 AM
Due: Friday, March 30, 10:15 AM



PROBLEM 1: RSA.

Two messages are encoded using RSA.

First message:
    public exponent = 31
    n =
    1629235366873425476500359623621809160089306105632310050657518600
    5466453291193344650825281261112029226180866510007154726532177851
    7845923834244318395663800739741837717
    encrypted message =
    3542959204395008977091244639187277824726376177301337610116259745
    9331049204331996405551482572744539757992687934506989254700433157
    881293527780143449195405146157631894

Second message:
    public exponent = 31
    n = 
    1699536305170072276056492008751271367213954895991781869484540338
    0908498614280753615151119181112294958735006287106171443128198401
    5079051686178201851384023588569351421
    encrypted message =
    8490931084280409560633498991236883398097536264361662337346051641
    4284306283252270807060383372587482168228907706583247576947524866
    93312512391922509101418937237795789

Decode them both.

Hint: I am giving you two RSA moduli





PROBLEM 2: DISCRETE LOGS

I'm thinking of a number 0 through 9999. What's the number? So I can't 
cheat I will commit to my choice. It is equal to c%10000, where:

1231234**c = 431351354 mod 479001599

Hint: 431351354 lies in a subgroup of size 1/106 the entire group.





PROBLEM 3: HASH FUNCTIONS

Find a document D such that md5sum(D) or md5(D) has the last four hex digits: 1234.
Note: md5sum is a linux command, md5 is a FreeBSD, and therefore OsX command.
They are equivalent programs.





PROBLEM 4: RANDOM BITS

Here's a large number:

    n = 
    12993773880316502853877845054866481704876979688406725004560736974
    018089298613795184807910750926954077314494681510896553503569

It is the product of two primes, and each of those primes is 3 mod 4.

Certainly s_0 = 123123**2 = 15159273129 is a square mod n. From this
square get more squares by repeated squaring:

    s_i = s_(i-1)**2 mod n.
    
For instance, s_1 = 229803561799621450641.

The sequence of whether s_i is even or odd is a sequence just as
random as the flip of a coin (as far as polynomial time computation 
can tell).

Lets take a random coin sequence, 10 heads in a row. It should occur in
a sequence of coin flips. In fact, the waiting time for this occurance
should be 2**11-1 flips. Find this sequence in the sequence. Does it
occur frequently enough? Too frequently?

How about the sequence HTHTHTHTHT?

Think up six improbable strings before your next breakfast and try to find 
them occuring in the string of bits produced by this generator.





PROBLEM 5: SUBGROUPS

Consider the group Z*_29.

This group has small groups inside of it. These groups inside the group,
where you just take some of the numbers, is a subgroup.

The smallest group inside of it
is the trivial group of one element {1}. The next largest group is {1, 28}.
Why is {1,28} a group? It is the group of two elements, essentially 1 and -1,
and you multiply and find inverses.

You can't just take any collection of numbers. You have to be able to take 
numbers in the collection and mutliply them and have the result also be
in the collection. For any a and b in the collection there must a solution
x to the equation a x = b (29) with x also in the collection.

We will find all subgroups in Z*_29, and the numbers of different generators
of each subgroup.

For each number 1, 2, ... 28, write down the orbit of the
number. That is, if the number is 2, write down 2, 4, 8, 16, 3, 6, .... and 
so on. Do this for all number 1 through 28.

Each of the resulting collections is a subgroup.

Question 1: Why?

Question 2: Each subgroup as a size which divides 28. Why?

Question 3: For each k which divides 28 there is a subgroup of that size. Why?

Question 4: For each subgroup there are phi(k) different ways that that
subgroup turns up, where k is the subgroup size. E.g. for the subgroup
of size 7, it turns on phi(7)=6 ways. Why?