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


SOLUTION:

# python code I will need

def egcd(a,b):  # a > b > 0
    """ Extended great common divisor, returns x , y
        and gcd(a,b) so ax + by = gcd(a,b)       """
    if a%b==0: return (0,1,b)
    q=[]
    while a%b != 0:
        q.append(-1*(a//b))
        (a,b)=(b,a%b)
    (a,b,gcd)=(1,q.pop(),b)
    while q:(a,b)=(b,b*q.pop()+a)
    return (a,b,gcd)

def modpow(b,e,n): 
    """ b**e % n """
    if e==0: return 1
    if e==1: return b % n
    if e%2==0 :
        return (modpow(b,e/2,n)**2)%n
    else:
        return (b*modpow(b,e-1,n))%n
        
# solution to just the first, the second is the same

>>> n1 = 162923536687342547650035962362180916008930610563231005065751860054664532911933446508252812611120292261808665100071547265321778517845923834244318395663800739741837717
>>> n2 = 169953630517007227605649200875127136721395489599178186948454033809084986142807536151511191811122949587350062871061714431281984015079051686178201851384023588569351421
>>> # you had to take the hint, that the moduli must share something:
>>> p1 = egcd(n1,n2)[2]
>>> p1
3586420730428501486799804587268520423291459681059978161140231860633948450858040593963L
>>> q1 = n1/p1
>>> q1
45427892858481394071686190649738831656137145778469793250959984709250004157335359L
>>> phi1 = (p1-1)*(q1-1)
>>> pri1 = egcd(31,phi1)[0]%phi1
>>> # the last mod makes the value positive
>>> ct = 35429592043950089770912446391872778247263761773013376101162597459331049204331996405551482572744539757992687934506989254700433157881293527780143449195405146157631894
>>> modpow(ct,pri1,n1)
12345678901234567891123456789212345678931234567894123456789L
>>> 

========================================================


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.

SOLUTION

everyone got this

========================================================



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.


SOLUTION

179863

as in: 

hohokus: cat hashing.pl
#!/usr/bin/perl


$LIMIT = 1000000 ;
$i = 0 ;
$h = 10000 ;
while ($i< $LIMIT) {
  $i++ ;
  $s = "".$h ;
  $er = `echo $s | md5` ;
  if ( $er =~ /234$/ ) { 
    printf( "%s %s\n", $s, $er );
    break ; }
  $h ++ ;
}

hohokus: ./hashing.pl 
11304 621f0af63038a76058e7605c29673234
14880 15647e20e337948cbf08864c952ee234
15425 dad663255fa694aedb0c5e901109c234
20250 e3aeb2cda9c2270fc0913242c1e22234
31272 9feb5163956455d39457110904e52234
38723 c7f9edf403232f596eab093ced1c0234
39039 0dd9f6228c8d617050d8be895c1bf234
40596 ecd5b4b83767a2c35f1ec97a349ae234
46075 297bf02b53fbe0f961a61ac357e84234
52351 8670b9d222d4ef0ea4a0aff87a8fc234
58037 80dca84b8a66137caf05d8e402502234
64031 868815eebafc232ab5293ffa3148f234
69809 652651553671acb766764cbffcce4234
83827 cd64e9fab41178357e62f2762a79e234
87829 585f2ab6fa1bf1dc44dde6e38ba6a234
88791 569c4594617d0c5a990555a191ff2234
96812 704c7b713696540cfa59e79f289a5234
98142 2eb1d7356a27f657e2c2efb661bee234
111008 9ec9ca5e20409556649212342248a234
124252 c61a993f959bf981819e34e3277c7234
124641 1871a4bef55a12b69b8f751cd6ce3234
125902 4c3ba8845f7e304b7e5f259c9fe4d234
132715 e5e7d81f1b11894032059ca79d39b234
136058 ea28771c586cfe116729b4365918b234
136392 e18e02122eebe7a05ce526056ca22234
145315 3671e3f7755f67c67f15cd28d1116234
155097 7c9db6339f4dec645c624f0f95773234
156562 2b49cde1e7cede91e1251389ee625234
158455 db1c2b85645a30c7b4a4fa176a4c2234
159240 fb3edde6e65ec9db3bf41cdfa28d5234
164949 87f909e8dd53aa32cf3913f76a76e234
169305 a09f178a01a7ced6817140c2156ba234
169403 add141d06cdf8e2d6bed219bcc42e234
171435 bb155405f9b83009e7f6a1f27879d234
175169 1607bcbad63305eb22280baaaa397234
179863 03c8cff65670fa5712ae895604a91234
^C

about 30 minutes on a MacBook 2.4 GHz Intel Core 2 Duo



========================================================



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.

SOLUTION

Most people got this. It was sort of a crazy problem.

========================================================



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 has 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?

SOLUTION

I wanted people to draw it out like follows, and the questions are:

Q1: It's a subgroup because g^i*g^j=g^(i+j), so you can multiply. You have
inverses because 1 is in the group and you can work out the j such that 
g^(i+j) = 1, that makes g^j the inverse of g^i.

Q2: By Lagrange's Theorem

Q3: Look at the integers mod 28 over addition, which by discrete logs is
isomorphic. The generator each sized subgroup is obvious.

Q4: This is an important fact, and here is the score card:

GROUP SIZE | PHI(SIZE) | GENERATORS

1            1           1
2            1           28
4            2           12, 17
7            6           7, 16, 20, 23, 24, 25
14           6           4, 5, 6, 9, 13, 22
28           12          2, 3, 8, 10, 11, 14, 15, 18, 19, 21, 26, 27

     Total = 28 (all elements accounted for)
     
     
The important thing is there is JUST ONE GROUP for each and every size k that divides n.
There are phi(k) different ways to get that one group.



def orbitsize(g,n):
    i = 1
    r = g
    print r,
    while r!=1:
        i += 1
        r = r*g % n
        print r,
    return i
    
>>> orbitsize(2,29)
2 4 8 16 3 6 12 24 19 9 18 7 14 28 27 25 21 13 26 23 17 5 10 20 11 22 15 1
28
>>> orbitsize(3,29)
3 9 27 23 11 4 12 7 21 5 15 16 19 28 26 20 2 6 18 25 17 22 8 24 14 13 10 1
28
>> orbitsize(4,29)
4 16 6 24 9 7 28 25 13 23 5 20 22 1
14
>>> orbitsize(5,29)
5 25 9 16 22 23 28 24 4 20 13 7 6 1
14
>>> orbitsize(6,29)
6 7 13 20 4 24 28 23 22 16 9 25 5 1
14
>>> orbitsize(7,29)
7 20 24 23 16 25 1
7
>>> orbitsize(8,29)
8 6 19 7 27 13 17 20 15 4 3 24 18 28 21 23 10 22 2 16 12 9 14 25 26 5 11 1
28
>>> orbitsize(9,29)
9 23 4 7 5 16 28 20 6 25 22 24 13 1
14
>>> orbitsize(10,29)
10 13 14 24 8 22 17 25 18 6 2 20 26 28 19 16 15 5 21 7 12 4 11 23 27 9 3 1
28
>>> orbitsize(11,29)
11 5 26 25 14 9 12 16 2 22 10 23 21 28 18 24 3 4 15 20 17 13 27 7 19 6 8 1
28
>>> orbitsize(12,29)
12 28 17 1
4
>>> orbitsize(13,29)
13 24 22 25 6 20 28 16 5 7 4 23 9 1
14
>>> orbitsize(14,29)
14 22 18 20 19 5 12 23 3 13 8 25 2 28 15 7 11 9 10 24 17 6 26 16 21 4 27 1
28
>>> orbitsize(15,29)
15 22 11 20 10 5 17 23 26 13 21 25 27 28 14 7 18 9 19 24 12 6 3 16 8 4 2 1
28
>>> orbitsize(16,29)
16 24 7 25 23 20 1
7
>>> orbitsize(17,29)
17 28 12 1
4
>>> orbitsize(18,29)
18 5 3 25 15 9 17 16 27 22 19 23 8 28 11 24 26 4 14 20 12 13 2 7 10 6 21 1
28
>>> orbitsize(19,29)
19 13 15 24 21 22 12 25 11 6 27 20 3 28 10 16 14 5 8 7 17 4 18 23 2 9 26 1
28
>>> orbitsize(20,29)
20 23 25 7 24 16 1
7
>>> orbitsize(21,29)
21 6 10 7 2 13 12 20 14 4 26 24 11 28 8 23 19 22 27 16 17 9 15 25 3 5 18 1
28
>>> orbitsize(22,29)
22 20 5 23 13 25 28 7 9 24 6 16 4 1
14
>>> orbitsize(23,29)
23 7 16 20 25 24 1
7
>>> orbitsize(24,29)
24 25 20 16 7 23 1
7
>>> orbitsize(25,29)
25 16 23 24 20 7 1
7
>>> orbitsize(26,29)
26 9 2 23 18 4 17 7 8 5 14 16 10 28 3 20 27 6 11 25 12 22 21 24 15 13 19 1
28
>>> orbitsize(27,29)
27 4 21 16 26 6 17 24 10 9 11 7 15 28 2 25 8 13 3 23 12 5 19 20 18 22 14 1
28
>>> orbitsize(28,29)
28 1
2
>>> orbitsize(1,29)
1
1
>>>