Cryptography Reference
In-Depth Information
Example 8.6
Suppose that Eve intercepts the following ciphertext that Alice sends
to Bob. The public key of Bob is, again, the value of
pk
in Example 8.2. Eve wants
to recover the plaintext
m
.
> c := RSAEncrypt(pk, m, decimal);
9013813990195011902482091471990199730458117192679987474726233797695553586884023787\
47105281934160690005014031738117790204702745404894350444588369932348867238422482\
58411418890363549042995404074652493229968514265882893474505993086560322750885651\
21150154761398485614893692796218770764805883143898949647238924409445436033337718\
35546149437997049833916726315768207604427628541524923907366640353192538207463607\
39427463038749508842211134999261755810210905350018057384501908516676423051774092\
73316470584127036980099203705226917872616502283181159585580232283138210496130198\
316260789680206628883061708314573842379215309022725717
Eve then pseudo-randomly chooses an element
r
∈ Z
n
, where
n
is the RSA
modulus in the public key of Bob (she just chooses it in
Z
n
and then checks that it
Z
n
, which occurs with overwhelming probability):
> with(RandomTools):
n := convert(pk[1], decimal, hex):
e := convert(pk[2], decimal, hex):
MersenneTwister:-SetState():
r := MersenneTwister:-GenerateInteger(':-range' = 0 .. n);
igcd(r, n);
4908248663891392609944333686227141620920836851120339550886089371809471319689897613\
83829323204479697237508635335378131194154477831278267863578420194017705473129419\
56351254618650801951111438217492636158352831931096220947698963914188698295961379\
10792141474472001814487773268352895423211586046140653110789831640495317123204459\
83643211823395871203738759662381824260404421504904517122258603622753476453622894\
40324758815095419556809654161084112988630543770558992247261292457763711233144804\
69938321488811567777140364544962519225036453910118341690883922720938999496204141\
584632803453282488752056204112883431350981097338223278
1
belongs to
r
e
c
mod
n
and sends it to Bob:
Then Eve computes
f
:=
> f := Power(r, e)*c mod n;
1248964202184754477876352112155230158797007622033952785683294002559949743199187384\
37063802207879442544426205249128649864016817384385817965133190889363303911560209\
24362964871814325196001079958929153805251611659880064078312932767681724146259790\
97382105510447735012397026460172864188416313602754195924049905867079814752892199\
79441626873204448490310154438686669727090251743048604915287270867812914813927785\
33940704790883735732125243434465428203118683014248165699250223204491879723241207\
27866465404097019219989416663668752041400271930624298432293263807269571726252406\
6384398246583721674190088861700063710083657835165146244
Bob decrypts
f
by computing
RSADecrypt
(
,
)
but obtains gibberish con-
taining many non-printable characters. He wants to send it to Eve but, as it is non-
printable, Bob computes the plaintext corresponding to
f
in decimal form (as an
element of
sk
f
Z
n
) and obtains the following value
x
:
> x := Power(f, convert(sk[2], decimal, hex)) mod n;
9835790710599266407092643451240075521978739495334677707894789949539669540859810475\
96959780700523797996818131689990414044155033068744266833068151814460463805809784\
10770168256986873562616093593478838099286816382554895563971343988511791821470026\
59840101750030307401099786957066819102341901746975257929138473255689415468442999\
49837410232051229512008883956140589987585635140991837577073880983946824608979742\
13791031507856704231786204117678594549247575155825243681263481345469331878317051\
52794598995507992790478938312144195891200001238888053247817096366012519746211702\
868077834915924845287751137348554913217051434763976470
Now, Bob sends
x
to Eve adding: Look at what you just sent me, it makes no
sense! But Eve knows that
x
is the result of applying the decryption algorithm to the
pair
(
,
)
sk
f
, i.e., letting
d
be the decryption exponent (unknown to Eve):
