M 343 L Computer Project solutions and comments


Do the following projects on the computer of your choice, using
the software of your choice and send me the results by e-mail
to voloch@math.utexas.edu by November, 29th. Make sure to include
your name in your message. A copy of this project is available on the
course web page, so you should NOT retype the numbers below. The big
numbers are broken into two lines but they should be understood as
continuing on the next line.


1. Encrypt your social security number (no dashes) using the El-Gamal
public key cryptosystem with parameters 
p= 646420927782718589563870857770984404869972572954256253542128245272681510686710283
g=5 and 
g^a= 458202247467459013436902049938410237719262178957608031235592810706074908848730866

Solution
(My secret exponent was
a=686270194694237431022221056
but you didn't need to know that)

You need to produce a random number r and send me the pair of
numbers h= g^r (mod p) and c=m*(g^a)^r (mod p), where m is your SSN.

For example, in pari you may enter the above values for p,g,ga ( for g^a, 
don't call it g^a if you don't have a)

r=random() 
(or if you want a big exponent r=bigrandom()=sum(j=0,10,random()*10^(10*j))

h=lift(Mod(g,p)^r)

and if your SSN is 1234567890

c=lift(Mod(1234567890,p)*Mod(ga,p)^r)

You send me h,c

I can decrypt by

a=686270194694237431022221056
ssn(h,c)=lift(Mod(c,p)/(Mod(h,p)^a))

Example session

? bigrandom()=sum(j=0,10,random()*10^(10*j))
? p=646420927782718589563870857770984404869972572954256253542128245272681510686710283
%4 = 646420927782718589563870857770984404869972572954256253542128245272681510686710283
? g=5
%5 = 5
? ga=458202247467459013436902049938410237719262178957608031235592810706074908848730866
%6 = 458202247467459013436902049938410237719262178957608031235592810706074908848730866
? r=bigrandom
%15 = 15019998040760127757135906193011161979230929253064085492829720689048541263288607140825742801317872692084557890
? h=lift(Mod(g,p)^r)
%16 = 291240549423880095513691307414395023185039604919999879943425230789282637525095189
? c=lift(Mod(1234567890,p)*Mod(ga,p)^r)
%17 = 266163362008935925707896039563543659959153582849415550537645039642738838555598760
? a=686270194694237431022221056
%12 = 686270194694237431022221056
? ssn(h,c)=lift(Mod(c,p)/(Mod(h,p)^a))
? ssn(h,c)
%18 = 1234567890


2. Find a composite number which is a strong pseudoprime to all bases
b between 2 and 9. (hint try numbers of the form (n+1)(2n+1)

Solution.
First the Miller-Rabin test, outputs 1 if n is a strong pseudoprime to
base b, 0 if not.
{
milrab(n,b,r)=r=0;
v=valuation(n-1,2);m=(n-1)/(2^v);
c=Mod(b,n)^m;k=0;
if(c==Mod(1,n),r=1,
while(c != Mod(-1,n) && k<v,c=c^2;k++);
if(c==Mod(-1,n),r=1));r
}

Now a function to see if a number passes the test for all bases between 2 and 9

test(n)=flag=1;b=2;while(milrab(n,b)&&b<9,b++);if(b<9;flag=0);flag


Using the hint and the above functions you can find a solution by

for(s=10^5,10^6,n=(s+1)*(2*s+1);if(test(n),print(n)))

I can check your solution using

{
check(n,v)=v=vector(8,j,milrab(n,j+1));if(v==vector(8,j,1),print("correct"),
print("wrong"));v
}

Here are some numbers people have found


307768373641 
546348519181
1362242655901
1871186716981

and an example not of the form (n+1)(2n+1) smaller than the above

3215031751




3. You have discovered that an user with RSA public key 
n= 208930007937735341052334120965253947012127256336800805845963718795438763899534280686071981634026899229367521507631892820985578072794850999404632341833787930505039
and e=17 has decryption exponent 
d= 86030003268479258080372873338633978181464164373976802407161531268710079252749409295004948807037829657936978862430561043089481443563314223834965972053076755249553
Factor n.

Solution, the factors of n are 
323210463891359294781935428885492202434986286477128127457334317330578186365576401
and
646420927782718589563870858241951184995639122375584388998471111936269558016465439

(Irrelevant trivia: the second factor is close, but not equal, to p in the
first question)

If you feed the values of n,e,d to the computer you can find the factors
as follows:

{
m=e*d-1;
v=valuation(m,2);
flag=1;
b=2;
while(flag,s=m;j=v;
while(Mod(b,n)^s==1&&j>0,s=s/2;j--);x=lift(Mod(b,n)^s);
if(x != 1 && x != n-1, print(gcd(x+1,n));print(gcd(x-1,n));flag=0,b++))
}

This is searching for solutions of x^2 =1 mod n, x not 1 or -1, among
the b^((ed-1)/2^j) mod n.


Another solution, that works because ed-1 is not much bigger than n
is to take n as a reasonable approximation to phi(n) (which we don't
know) in the sense that n/phi(n) is close to 1 so (ed-1)/n should
be close to (ed-1)/phi(n). We find that (ed-1)/n is very close to 7
so we can guess that phi(n)=(ed-1)/7 and from that get the factors of n.