Math 124, HW #3, Page 1, December 12, 2001  Student, F.

1. We are interested in s = g^{mn}.

? Mod(454,3793)^1208
%1 = Mod(2156, 3793)

So the secret code is s = 2156. For fun, let’s find n and check:

? ?znlog
znlog(x,g): g as output by znprimroot (modulo a prime). Return smallest
positive n such that g^n = x.
? znlog(454,Mod(7,3793))      \\ Solve 7^x = 454 mod 3793
%6 = 3004                     \\ n = 3004
? ((Mod(7,3793))^3004)^1208
%7 = Mod(2156, 3793)          \\ (g^n)^m
? ((Mod(7,3793))^1208)^3004
%8 = Mod(2156, 3793)          \\ (g^m)^n

2. (a) Using the system we prescribed in class (base 27, first letter is least significant digit), we calculate:

    ? \r math124/rsa.gp
    ? message_to_number(["V", "E", " ", "R", "I", " ", "T", "A", "S"])
    %11 = 5384375093542
    ? letter_to_number("V")*1 + letter_to_number("E")*27
      + letter_to_number(" ")*27^2 + letter_to_number("R")*27^3
      + letter_to_number("I")*27^4 + letter_to_number(" ")*27^5
      + letter_to_number("T")*27^6 + letter_to_number("A")*27^7
      + letter_to_number("S")*27^8
    %12 = 5384375093542  \\ Good, they agree!

(b) We need to find the greatest integer n such that 27^{n} − 1 < 10^{2}0. (27^{n} − 1 is the word consisting of n Z ’s.

    ? floor(log(10^20+1)/log(27))
    %28 = 13
    ? message_to_number(["Z","Z","Z","Z","Z","Z","Z","Z","Z","Z","Z","Z","Z"])
                                          <10^20%29 = 1   \\ 13 letters works
    ? message_to_number(["Z","Z","Z","Z","Z","Z","Z","Z","Z","Z","Z","Z","Z",
                                          "Z"])<10^20
    %30 = 0   \\ 14 letters doesn't

3. Michael and Nikita chose small numbers, so we just can loop through and try a bunch of numbers (this takes practically no time) to find their codes.

? for(X=1,500,if(lift((Mod(5,97))^X)==3,print(X)))
70               \\ These are all valid n's

262
358
454
? for(X=1,500,if(lift((Mod(5,97))^X)==7,print(X)))
31               \\ m's
127
223
319
415
? Mod(5,97)^70
%31 = Mod(3, 97)
? Mod(5,97)^31
%32 = Mod(7, 97)
? Mod(5,97)^(31*70)
%33 = Mod(44, 97)  \\ secret code = 44!

So we have n = 70, m = 31, and s = 44.

4. ? Mod(2004,441484567519)^238402465195
%34 = Mod(409520440852, 441484567519)

I’ve encoded 2004! The message 409520440852 ≡ (2004)^{e} (mod n).

5. (a) We ask PARI to factor n:

    ? factor(5352381469067)
    %72 =
    [141307 1]
    [37877681 1]

So, de ≡ 1 mod (ϕ(n)), but ϕ(n) = (141307−1)(37877681−1) = 5352343450080. We solve this:

    ? (141307-1)*(37877681-1)
    %73 = 5352343450080   \\ phi(n)
    ? e=4240501142039;
    ? d=lift(Mod(e,%73)^(-1))
    %86 = 5195621988839   \\ d
    ? Mod(e*5195621988839, 5352343450080)
    %79 = Mod(1, 5352343450080)
    ? ((Mod(15,n)^e)^d)   \\ Final check: encode and decode 15.
    %85 = Mod(15, 5352381469067)

So d = 5195621988839.

(b) Noting the errata sent to us by e-mail, we raise 3539014000459 to the power of d modulo n:

? lift(Mod(3539014000459,n)^d)
%88 = 18464
? number_to_message(18464)
%89 = "WHY"

6. Encrypting every letter individually is not a secure method. Rather, it is as secure as having a table of mappings of every letter to a number on both ends. This sort of encryption is very susceptible to word frequency examinations and the like. If you’re encrypting just one letter, it’s perfectly secure, but if you’re encrypting, say, a couple of pages of text, it will be possible to recognize (based on repeating words like “the” and frequent letters like space and e) certain patterns and eventually decode the system.

7. (a) ? \\ Consider m = ed -1
? m=329222149569169*116439879930113 - 1
%92 = 38334587566167741692779486096
? \\ Let's check if a^(m/2) == 1 (mod n) for a bunch of a...
? n = 1433811615146881
%93 = 1433811615146881
? for(a=15,30,if(Mod(a,n)^(m/2)!=1,print(a)))
? m = m/2      \\ Divide m by 2
%94 = 19167293783083870846389743048
? for(a=15,30,if(Mod(a,n)^(m/2)!=1,print(a)))
? m=m/2        \\ Divide m by 2 again
%95 = 9583646891541935423194871524
? for(a=15,30,if(Mod(a,n)^(m/2)!=1,print(a)))
17
18
20
21
23
27
28
29
30    \\ Aha!
? p=gcd(lift(Mod(17,n)^(m/2))-1,n)   \\ Note that we had to choose 17,
                                    \\ or another number from that list
%125 = 37865717
? q = n/p
%126 = 37865693
? p*q == n
%128 = 1

We’ve factored n = (37865717 ∗ 37865693).

(b) ? \\ Let's try the probabilistic algorithm
? t = floor(sqrt(n))
%129 = 37865704

? sqrt((t)^2 - n)
%130 = 8702.37122857902448376595102931867100032...*I
? sqrt((t+1)^2-n)
%131 = 12.00000000000000000000000000000000000...
? \\ Well, already!
? p = t + 1 + 12
%143 = 37865717
? q=t + 1 - 12
%144 = 37865693
? p*q == n
%148 = 1

So we can do the same thing using “Fermat Factorization.”