Cryptography Reference
In-Depth Information
accept public keys and ciphertexts in hexadecimal format but we shall not worry
about this here. The function checks that the encryption exponent in all public keys
is the same and that the number of key/ciphertext pairs is at least equal to the value of
the encryption exponent. If these conditions are met, the function applies the Chinese
remainder theorem in the form just described to obtain the
e
th power of the plaintext
and, after extracting the
e
th root, the plaintext is returned as a character string.
> HastadBroadcastAttack := proc(publickeys::list, ciphertexts::list)
local exps, e, moduli, blocks;
if nops(publickeys) <> nops(ciphertexts) then
error "There must be a ciphertext for each key"
end if;
exps := ListTools:-MakeUnique(op
∼
(2, publickeys));
if nops(exps) <> 1 then
error "Not all public keys have the same exponent"
elif nops(ciphertexts) < exps[1] then
error "Insufficient number of ciphertext/key pairs"
else
e := exps[1]
end if;
moduli := ListTools:-Transpose(publickeys)[1];
if type(ciphertexts, listlist) then
blocks := ListTools:-Transpose(ciphertexts)
else
blocks := [ciphertexts]
end if;
blocks := root
∼
(map(x -> chrem(x, moduli), blocks),e);
convert(ListTools:-Flatten(convert
∼
(blocks, base, 256)), bytes)
end proc:
Example 8.7
Suppose that the message
txt
in Example 8.3 is encrypted with 17
RSA public keys all of which have 17 as encryption exponent. We are going to
recover the message given the public keys and the corresponding ciphertexts. First,
we generate the keys using the function
RSAKeyGen
. We will generate seventeen
2048-bit keys in decimal format as required by
HastadBroadcastAttack
(if
they were in another format, it would be easy to convert them to decimal). For
convenience and speed we will call
RSAKeyGen
with automatic seeding and we
remark that, although this seeding method is not secure, the attack works exactly the
same in case all the keys are generated with truly random seeds of adequate length.
The list of public keys—which we do not print—is obtained as follows:
> pubkeys := [seq(RSAKeyGen(1024, 'e' = 17, format = decimal)[1], i=1..17)]:
Next, we encrypt the plaintext
txt
with all these public keys, again without
printing the ciphertexts:
> ciphtexts := RSAEncrypt
∼
(pubkeys, txt, decimal):
We already have all the data required to recover the plaintext without making
use of the private keys. The process is very efficient in practice, and the plaintext is
returned by Maple in hundredths of a second, but in order to save space we do not
print the plaintext again; we merely check that it is the same as the plaintext that we
keep in the global variable
txt
:
> evalb(HastadBroadcastAttack(pubkeys, ciphtexts) = txt);
true
