Wenbo Mao
Many cryptographic protocols and cryptosystems have been proposed to make use of prime order subgroups of Zn* where n is the product of two large distinct primes. In this paper we analyse a number of such schemes. While these schemes were proposed to utilise the difficulty of factoring large integers or that of finding a trapdoor in Zn* (for instance, the order of an RSA group), our analyses show much easier problems,some even trivially easy, as their real security bases. We summarise three classes of security failures in these schemes, and provide a formula to help factoring n which has a special structure designed for makinguse of a prime order subgroup in Zn*. The formula provides a lowertime complexity for factorisation time which is independent of the length of n, and in most cases will be much faster than the known fastest factorisation.
PostScript File (113K)
Faster Attacks on Elliptic Curve Cryptosystems
The previously best attack known on elliptic curve cryptosystems used
in practice was the parallel collision search based on Pollard's rho method.
The complexity of this attack is the square root of the prime order of the
generating point used. For arbitrary curves, typically defined over
GF(p) or GF(2m),
the attack time can be reduced by a factor or the square root of 2, a small
improvement. For subfield curves, those defined over
GF(2ed) with coefficients
defining the curve restricted to
GF(2e), the attack time
can be reduced by a factor of the square root of 2d. In particular
for curves over GF(2m) with
coefficients in GF(2), called anomalous binary curves or Koblitz curves,
the attack time can be reduced by a factor of the square root of 2m.
These curves have structure which allows faster cryptosystem computations.
Unfortunately, this structure also helps the attacker. In an example, the time
required to compute an elliptic curve logarithm on an anomalous binary curve overGF(2163) is reduced from
281 to 277
elliptic curve operations.
PostScript File (404K)
Improving the parallelized Pollard lambda search on binary anomalous curves
This paper shows how to apply a Pollard lambda search on a set of equivalence
classes derived from the structure of the elliptic curve and which requires
fewer interationsthat the standard method. In the case of binary anomalous
curves overGF(2m), the new
method speeds up the standard method by a factor ofabout the square root
of 2m. For example, for binary anomalous curves over
GF(2200), the speedup is about
20 times over previous methods.
PostScript File (135K)
ISO 9796 1 and the new forgery strategy
In this note we show how the new forgery strategy of Coron, Naccache and
Sterncan be modified to break the ISO 9796-1 standard for RSA and Rabin
digital signatures. Note: By authors' request, this
contribution is password protected. In order to get the password,
please subscribe to the P1363 mailing list.
PostScript File (August 23, 1999) (146K)
On Rabin-type Signatures
This note specializes the recent signature forgery by Coron, Naccache and
Stern (1999) to Rabin-type systems. Note: By authors' request,
this contribution is password-protected. In order to get the password, please
subscribe to the P1363 mailing list.
PostScript File (August 9, 1999) (238K)
On the Security of EPOC and TSH-ESIGN
We submitted a public-key encryption scheme, EPOC, and digital signature scheme,
TSH-ESIGN, to IEEE P1363a. The security of EPOC and TSH-ESIGN is based on the
intractability of factoring n=p2q,
where p and q are primes. TSH-ESIGN is also based on the intractability
of the approximate e-th root (AERP) assumption, which is the approximate
version of the RSA assumption. This draft describes the latest research status on
the intractability of factoring based on the intractability of factoring
n=p2q and the approximate
e-th root (AERP) assumption, and concludes that these problems are
considered to be almost as intractable as those of factoring n=pq and of
inverting the RSA function (i.e., solving the e-th root).
PostScript File
(November 18, 1999) (242K)
Formal Security Proofs for a Signature Scheme with Partial Message Recovery
The Pintsov-Vanstone signature scheme with partial message recovery
(PVSSR) is a variant of the Schnorr signature scheme. It produces
very short signatures on messages with inherent redundancy. This
article gives a formal proof of the security of PVSSR, which reduces
the difficulty of existential forgery to the difficulty of the
discrete logarithm problem. The proof works in the random oracle
model (which assumes an ideal hash function) combined with an ideal
cipher model. Suggested instantiations for the ciphers in
cryptographic applications are symmetric encryption primitives,
such as DEA or an AES finalist. A second proof is given, in which
the random oracle model is replaced by the generic group model.
A third proof permits the cipher to be XOR, by working in both the
random oracle model and the generic group model.
PostScript File (February 24, 2000) (1197K)
Optimal Parameterization of SNFS
The Special Number Field Sieve factoring algorithm has a large number of parametric choices,
each of which can affect its run time. We give guidelines for these choices along with a discussion of useful
coding optimizations. We also give a theoretical argument which proves that the choice of sieving region that
has been used so far in successful factorizations is not optimal and show how to obtain an improved sieve
region. The improvement has yielded a 15% speed increase in practice.
PostScript File (Posted
April 11, 2005) (1403K)
Michael Wiener and Robert Zuccherato
Zipped PostScript File (87K)
Robert Gallant, Robert Lambert, and Scott Vanstone
Don Coppersmith, Shai Halevi and Charanjit Jutla
Zipped PostScript File (August 23, 1999) (45K)
Adobe Acrobat (.pdf) File (August 23, 1999) (152K)
Marc Joye and Jean Jacques Quisquater
Zipped PostScript File (August 9, 1999) (94K)
Adobe Acrobat (.pdf) File (August 9, 1999) (279K)
Tatsuaki Okamoto and Tetsutaro Kobayashi
Zipped PostScript File
(November 18, 1999) (113K)
Adobe Acrobat (.pdf) File
(November 18, 1999) (93K)
Daniel R. L. Brown and Don B. Johnson
Zipped PostScript File
(February 24, 2000) (623K)
Adobe Acrobat (.pdf) File
(February 24, 2000) (73K)
Robert D. Silverman
This page was last modified on April 11, 2004.
IEEE Home Page
IEEE Standards
IEEE P1363