Cryptography Reference
In-Depth Information
QR
p
. The steps to this are, first,
Next we encode the message as an element of
≤
to convert the message to an integer
q
and then to square this integer in the group
Z
p
QR
p
. As indicated above, one may also add 1 before
squaring but we shall not trouble to do that here, as the only purpose of this addition
is to ensure that the integer obtained is different from 0 (and hence an element of
Z
p
), something that is automatically satisfied by any nonempty Maple text string
such as the one defining
message
.
> messagequadres := ListTools:-DotProduct(messagebytes,
[seq(256ˆi, i=0..nops(messagebytes)-1)])ˆ2 mod p;
2548519170043554204976372516823910677244335083346545318400757089471915899150256312\
98953273271131260701374556359259108912517343063512901734591690458500997214343750\
15405070564590002344473493385924755023527055380053960943428307605808353472823376\
244653663035900221901070124243802789591518469407403725536103110469
To encrypt the message, a random
r
to obtain an element of
← Z
q
must be used. Again, for simplicity,
we use Mersenne Twister to pick this element as follows:
> SetState();
r := GenerateInteger(range = 1 .. q);
4086213236847609125974381426133972929994689285395066824404256474034341417729108420\
96514360151294401790876000690282841458447250178802879740961608266769967608503438\
48016210282171116936369242311021439594753986426043520707243406973034217750839313\
182668219927624758810609948482295601869902796771944801464061981022
Now, the ciphertext is computed:
> c := [Power(g, r) mod p, messagequadres*Power(h, r) mod p];
[2903967680883174654267730577486528723746240603148392060932034623415133260610248\
30204752106169432656548726436503547140640509204923383906229190194576934214051981\
36950097381873221260280334519894458266566335876877126741186170495473397366527709\
937260524682740957057358549334590376732064053495225370106845314631918,
45521190104426618827384708479377423518005279501895390122908123032649165995005811\
95354710040543286414295407080353755429142381723164998726646563263640022912949040\
88860259313033289385688510009832495216081367558026385029222708644345112481226741\
82875942746792152102041286919853686326004199887303155872280327825391]
Let us start the decryption process inwhich the private key (specifically, the integer
x
) is used. The following computation should give us back
messagequadres
:
> d := (Power(c[1], -x mod q) mod p)*c[2] mod p;
2548519170043554204976372516823910677244335083346545318400757089471915899150256312\
98953273271131260701374556359259108912517343063512901734591690458500997214343750\
15405070564590002344473493385924755023527055380053960943428307605808353472823376\
244653663035900221901070124243802789591518469407403725536103110469
Next we have to compute the unique square root of
d
in
Z
p
which is
q
.As
mentioned above, we may use Maple's command
numtheory:-msqrt
but, in
this case, since
q
happens to be a Blum prime, it is also very easy to do it as follows:
> sqroot := Power(d, (p+1)/4) mod p;
1147908219438180195859281292882487496737219939504691270609806761970065178851463508\
83318373932646382503953272750786599072334600130436614624301781722611362912995560\
86347521040423831204131365460839141500677740683958618340535914688652598036788992\
2213427092911921657276777977658962918203775576407841627500894652043
This is one of the two square roots of
d
in
≤
Z
p
but we need to compute the square
root that is
≤
q
, so we check whether this condition holds:
> evalb(q > sqroot);
false
