Public-Key Encryption - Introduction to Cryptography with Maple - page 497

interesting example is the class of algorithms grouped under the term 'index calculus
method' for discrete logarithms in subgroups of the multiplicative groups of finite
fields (including the subgroups of Z p ). These algorithms are subexponential and

hence, while the DL problem in the groups to which they apply may still be difficult,
longer keys are required in comparison with the groups where only generic methods
are available.
The best candidates for Elgamal encryption are certain elliptic curve groups
because no subexponential DL algorithms are known for them and, in addition,
there are arguments that suggest that finding factor base methods for these groups is
unlikely. Thus these groups, which we study in more detail in Chap. 11 , provide the
best framework for Elgamal encryption as they allow the use of relatively small key
lengths.

Example 8.16 We do a Maple example of Elgamal encryption/decryption in the
group of quadratic residues modulo a safe prime. Instead of doing it by means of a
couple of Maple functions we do it step by step. Let us start by generating a 1024-bit
safe prime:
> with(RandomTools:-MersenneTwister):
SetState():
p := numtheory:-safeprime(GenerateInteger(range = 2ˆ1023 .. 2ˆ1024-1));
q := (p-1)*(1/2);

1147908219438180195859281292882487496737219939504691278046016128744748265383550076\
31544383780919151280021483785611314193935700316382925350855203524942353588443747\
91267140488803819589982541261134527771769114749053208882475046989398435949915706\
7815461640743393990002257739746934789542921424927668167609477230303
5739541097190900979296406464412437483686099697523456390230080643723741326917750381\
57721918904595756400107418928056570969678501581914626754276017624711767942218739\
56335702444019097949912706305672638858845573745266044412375234946992179749578533\
907730820371696995001128869873467394771460712463834083804738615151
Let us check that p is indeed a safe prime and what the congruence class of q
modulo 4 is:
> isprime ∼ (p, q);
q mod 4;

true
3
Knowing that q is congruent to 3modulo 4 serves to computemodular square roots
modulo p more easily but this condition is not necessary and Maple will compute
square roots with the command numtheory:-msqrt modulo any prime (or any
integer that can be easily factored). Next we compute a generator of the group QR p :

> g := GenerateInteger(range = 2 .. q)ˆ2 mod p;
4080474388601972312967023621368538858717876436186784786557820049810548447893112252\
82912715144684349326439631033401028575620059134024518497952467296825396986949975\
86085016795574962824474619787629165967684545703419915995537544726751398807209274\
37279240812610154413863887129261780360015451595219835560020279537
We know that this element is a generator because the group of quadratic residues
modulo p (to which g belongs since it is a square) has order q , which is prime, and
hence any element distinct from 1 is a generator. However, we can also check it by
letting Maple compute its order, which will turn out to be q :

> evalb(numtheory:-order(g, p) = q);
true