Test Problem Generation - Public Key\302\251Mike May, S.J 2007, maymk@slu.eduA problem for teachers is to construct problems in cryptography that the student can solve with the appropriate level of technology. This worksheet looks at constructing problems that students can solve with Maple and an appropriate method, but where they will have difficulty if they do not use the suggested method.restart:
<Text-field style="Heading 1" layout="Heading 1">Generation of prime for use with Pohlig-Helman</Text-field>The idea is to generate a prime p such that p-1 factors into a product of small primes.The technique is to look for a value q that is a product of small primes and then check values of the form kq+1 intil a prime is found.q := 3^5*5^4*7^4*11;k := 1:
p:= 2*k*q+1:
test := isprime(p):
while not(test) do
k:= k+1:
p:= 2*k*q+1:
test := isprime(p):
end do:
"The prime found " = p;
"The factor k " = k;
"The factorization of p "= ifactor(p-1);We also want to check generators by looking at candidates raised to powers (p-1)/q for the factors of p-1. We run through a number of candidates for a generator and print out the generators.gentest := x -> (Power(x,(p-1)/2) mod p, Power(x,(p-1)/5) mod p, Power(x,(p-1)/3) mod p, Power(x,(p-1)/7) mod p, Power(x,(p-1)/11) mod p):for i from 2 to 50 do
test := min(gentest(i)):
if (test > 1) then print([i, gentest(i)]) end if;
end do:
<Text-field style="Heading 2" layout="Heading 2"></Text-field>with(numtheory);x := mlog(2,7,p);showstat(mlog);showstat(numtheory::_mlogsolve);This gives a prime and a generator where the prime is to large to check.
<Text-field style="Heading 1" layout="Heading 1">Carmichael numbers</Text-field>Carmichael numers are useful as exampels with some primlity tests. In particular, a Carmichael numer is likely to be factorable with the Miller-Rabin method.k:= nextprime(rand(10^20)());
test := isprime(6*k+1) and isprime(12*k+1) and isprime(18*k+1);
while (not(test)) do
k:= nextprime(k):
test := isprime(6*k+1) and isprime(12*k+1) and isprime(18*k+1):
end do:
k;
n := (6*k+1)*(12*k+1)*(18*k+1);n;k := n-1;
s := 0:
while (irem(k,2)= 0) do
s := s+1:
k := k/2:
end do:
's' =s;
'k' = k;
n-k*2^s;test := Power(6,k) mod n;for i from 2 to 15 do
test := Power(i,k) mod n;
p1 := igcd(test-1,n):
if ((p1 > 1) and (n>p1)) then
n1 := n/p1:
print([i, p1, n1]):
end if:
end do:ifactor(n,lenstra);
<Text-field style="Heading 1" layout="Heading 1">Quadratic Sieve problems</Text-field>We would like to have nice numbers to test factoring with a quadratic sieve. We first want to collect a set of primes of the appropriate size, then multiply two of them together as a candidate n. We then see if the method produces a factorization/p1 := nextprime(rand(10^4)());
p2 := nextprime(rand(2*10^4)());
p3 := nextprime(rand(5*10^4)());
p4 := nextprime(rand(3*10^4)());n := p4*p1;
sqrtn := isqrt(n);
sqrt2n := isqrt(2*n);
TestRange := floor((sqrt2n-sqrtn)/2);The first method is to look at numbers just bigger than sqrt(n*i) for a reasonable value of i.smallprime := 2*3*5*7*11*13*17*19;
for i from 1 to 200 do
t1 := ceil(sqrt(n*i)):
t2 := t1^2 mod n:
t3 := irem(smallprime^10, t2):
if (t3 = 0) then print(i, t1, t2, ifactors(t2)) fi;
end do:This gives us some candidates.igcd(64430-2*9*7,n);
igcd(96645-3^3*7,n);The second method looks at numers where we mod using a^2-nsmallPrimeProd := product(ithprime(j), `j`=1..20);
smallPrimeSet := {seq(ithprime(i), i=1..20)};
expVectorMaker := proc(n, m)
local smallPrimeTable, expVector, smallPrimeProd, i,
capPrime, facList, count, pFactor:
smallPrimeTable := table([seq(ithprime(i)=i+1,i=1..m)]):
expVector := [seq(0, i=1..m+1)]:
capPrime := ithprime(m+1):
facList := ifactors(n):
if (op(1,facList) = -1) then expVector[1] := 1 end if:
count := nops(op(2,facList)):
for i from 1 to count do
pFactor := op([2,i,1],facList):
if (pFactor < capPrime) then
expVector[smallPrimeTable[pFactor]] := op([2,i,2],facList)
end if:
end do:
expVector;
end proc:n:= p2*p3;
sqrtn := isqrt(n);
sqrt2n := isqrt(2*n);primeVector := [-1, seq(ithprime(i), i=1..20)];
goodLines := {}:
for i from 1 to sqrt2n do
temp := i^2 - n:
factorSet := numtheory[factorset](temp):
if (factorSet subset smallPrimeSet) then
V1 := ifactor(temp):
V2 := map(irem,expVectorMaker(temp, 20),2):
V3 := {(op(zip((x,y) -> x*y, primeVector, V2)))}:
goodLines:= goodLines union {[i, V1, V2, V3]}:
end if:
end do:
goodLines := [op(goodLines)]:
goodLines := sort(goodLines,(x,y)-> max(op(x[4]))<max(op(y[4]))):
nLines := linalg[vectdim](goodLines):
for i from 1 to nLines do
print(goodLines[i,1], goodLines[i,2], goodLines[i,4]);
end do;This gives a pair of lines that produces a factorization igcd(26927*23788-2*3*7^3*23*31,n);
<Text-field style="Heading 1" layout="Heading 1">RSA generation</Text-field>p := nextprime(rand(10^60)());
q := nextprime(rand(10^60)());n := p*q;
n1 := (p-1)*(q-1);
e := 2^16+1;
d := 1/e mod n1;m := 23;
c := Power(m,e) mod n;
m1 := Power(c,d) mod n;
<Text-field style="Heading 1" layout="Heading 1">El Gamal generation</Text-field>q := nextprime(rand(10^40)());
k := rand(10^20)();s := 1:
p := 2*s*k*q+1:
while not(isprime(p)) do
s:= s+1:
p := 2*s*k*q+1:
end do:
"factors of s" =ifactor(s);
"factors of k " = ifactor(k);
'p' = p;for i from 3 to 20 do
testSet := (Power(i,(p-1)/2) mod p, Power(i,(p-1)/3) mod p,
Power(i,(p-1)/5) mod p, Power(i,(p-1)/20333) mod p,
Power(i,(p-1)/4373284687738033) mod p,
Power(i,(p-1)/q) mod p):
gentest := min(testSet):
print([i,gentest]);
end do:alpha := 3;
a := rand(10^4..p-10)();
beta := Power(alpha,a) mod p;