Cryptography Reference
In-Depth Information
the random oracle model (where the hash function
H
is modeled as a full domain
random oracle) under the assumption that quadratic residuosity is hard. We refer to
the original paper by Cocks as well as [36], where a quadratic residuosity-based IBE
scheme which is space-efficient is presented and the security properties are analyzed
in more detail. We remark, however, that this scheme is not IND-ID-CCA secure
because, as it encrypts one bit at a time, in a CCA attack the ciphertext correspond-
ing to, say, a single plaintext bit, could be inserted by the adversary into a longer
ciphertext submitted to the oracle, thus recovering the plaintext bit by bit.
On the other hand, there is a method to construct an IND-ID-CCA secure scheme
from an IND-ID-CPA secure scheme (or even from an OW-CPA secure scheme).
This is accomplished by a generic transformation due to Fujisaki and Okamoto which
applies not just to IBE schemes but also to standard ones, see [79]. This transformation
uses random oracles, so that the security of the schemes thus obtained is relative to
the random oracle model. Until 2004, no IBE schemes that could be proved to be
IND-ID-CCA secure without random oracles were known but, recently, several such
schemes have been introduced. We refer to [36] and to several chapters in [107] for
more details on IBE schemes and their security properties.
10.3.4 The Cocks IBE Scheme in Maple
Here we give a Maple implementation of the Cocks IBE scheme. As usual, we
make use of several previously defined functions. For starters, we need a function to
generate the modulus, which may be built on top of the
RSAKeyGen
function.
Exercise 10.4
Write a Maple function that calls
RSAKeyGen
and, on input para-
meters similar to those in the latter function, returns an RSA modulus and its prime
factorization.
Since the encryption and decryption exponents are not needed here, we are going to
proceed differently and we will construct the function
GenModulus
as a simplified
form of
RSAKeyGen
which calls
RSAPrime
to generate the modulus. The inputs
are the same as in
RSAKeyGen
, except the (optional) encryption exponent that does
not appear here:
> GenModulus := proc(k::posint, seed1::{posint, string}, seed2::{posint, string},
{format::name := hex})
uses RandomTools:-MersenneTwister;
local s, p, q, m, n, key;
if _params['seed1'] = NULL then
SetState();
s := GenerateInteger(':-range' = 2ˆ(127) .. 2ˆ(256))
else
s := stringposint(seed1)
end if;
p := RSAPrime(k, s);
m := ceil(2ˆ(2*k-1)/p);
if _params['seed2'] = NULL then
SetState();
s := GenerateInteger(':-range' = 2ˆ(127) .. 2ˆ(256))
