Cryptography Reference
In-Depth Information
Next we are going to generate a public key for the Elgamal encryption scheme
that uses the group
QR
p
. For this we have to choose a random
x
← Z
q
(since
g
x
. For the scheme to be secure,
x
must be chosen
|
QR
p
|=
q
) and compute
h
:=
uniformly at random in
Z
q
and an acceptable compromise for practical use would be
to choose
x
pseudo-randomly using a PRG seeded with a sufficiently large random
seed. Thus we could use the Blum-Blum-Shub PRG as we did, for example, in
7.2.3
but, for simplicity, we are going to use here the Mersenne Twister algorithm
with automatic—and hence non-random—seeding, with the explicit warning that
this method is far from secure.
> SetState():
x := GenerateInteger(range = 1 .. q);
2783249646065996771740046054739270473598657555949565298758512662673167452960306464\
58104708039039362885098861657100793605344879664082558794193452138563885612792802\
57529317032079657377106090678397780580037301145826758289150258633311009363206425\
674520543545235631731672267060814886814127578086202978601734821815
h := Power(g, x) mod p;
7828454224355833980163570231656136263105450707959497692612534324434922200151941258\
11916148010166461105690808335681809483425901923593566905839277101756901875894985\
58602444862876541682381527958578184030274859314473498903445945999366026309981472\
605544932510979171925024202524289188305837323480192632659381528567
The public key will then be
(QR
p
,
g
,
h
)
and the private key
(QR
p
,
g
,
x
)
.Note
QR
p
may be specified by the pair
(
,
)
QR
p
is the unique subgroup
that the group
p
q
(
Z
p
of order
q
), so we may give these keys as Maple lists, with the public key equal
of
to
[
p
,
q
,
g
,
h
]
and the private key equal to
[
p
,
q
,
g
,
x
]
. Suppose now that we want to
encrypt the message:
> message := "This is an example of Elgamal encryption/decryption in the group of
quadratic residues modulo a safe prime"
First of all we must be sure that the message can be encrypted in one pass with
the public key we have defined; if the message were too long then we would have
to split it into blocks as we did, for example, when encrypting with plain RSA. We
are going to convert the message to an integer by regarding its characters, as usual,
as base-256 digits (through their 8-bit ASCII codes). In order to apply the encoding
method explained above, this integer should be
q
and so the number of characters
in the message string should be no greater than the logarithm of
q
to the base 256.
We compute these numbers as follows:
> StringTools:-Length(message);
ilog[256](q);
≤
106
127
We see that the message is short enough and can be encrypted in one pass. We
start by converting the message to a list of bytes (integers in the 0
..
255 range) as
follows:
> messagebytes := convert(message, bytes);
[84, 104, 105, 115, 32, 105, 115, 32, 97, 110, 32, 101, 120, 97, 109, 112, 108, 101,
32, 111, 102, 32, 69, 108, 103, 97, 109, 97, 108, 32, 101, 110, 99, 114, 121, 112,
116, 105, 111, 110, 47, 100, 101, 99, 114, 121, 112, 116, 105, 111, 110, 32, 105,
110, 32, 116, 104, 101, 32, 103, 114, 111, 117, 112, 32, 111, 102, 32, 113, 117, 97,
100, 114, 97, 116, 105, 99, 32, 114, 101, 115, 105, 100, 117, 101, 115, 32, 109,
111, 100, 117, 108, 111, 32, 97, 32, 115, 97, 102, 101, 32, 112, 114, 105, 109, 101]
