##
IEEE P1363 Research Contributions: Cryptanalysis

**
Cryptanalysis in Prime Order Subgroups of ***Z*_{n}^{*}

Wenbo Mao

Many cryptographic protocols and cryptosystems have been proposed
to make use of prime order subgroups of *Z*_{n}^{*}
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
*Z*_{n}^{*} (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 *Z*_{n}^{*}. 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**

Michael Wiener and Robert Zuccherato

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*(2^{m}),
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*(2^{ed}) with coefficients
defining the curve restricted to
*GF*(2^{e}), the attack time
can be reduced by a factor of the square root of 2*d*. In particular
for curves over *GF*(2^{m}) 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 2*m*.
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 over*GF*(2^{163}) is reduced from
2^{81} to 2^{77}
elliptic curve operations.

PostScript File (404K)

Zipped PostScript File (87K)

**
Improving the parallelized Pollard lambda search on binary anomalous curves**

Robert Gallant, Robert Lambert, and Scott Vanstone

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 over*GF*(2^{m}), the new
method speeds up the standard method by a factor ofabout the square root
of 2*m*. For example, for binary anomalous curves over
*GF*(2^{200}), the speedup is about
20 times over previous methods.

PostScript File (135K)

**
ISO 9796 1 and the new forgery strategy**

Don Coppersmith, Shai Halevi and Charanjit Jutla

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)

Zipped PostScript File (August 23, 1999) (45K)

Adobe Acrobat (.pdf) File (August 23, 1999) (152K)

**
On Rabin-type Signatures**

Marc Joye and Jean Jacques Quisquater

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)

Zipped PostScript File (August 9, 1999) (94K)

Adobe Acrobat (.pdf) File (August 9, 1999) (279K)

**
On the Security of EPOC and TSH-ESIGN**

Tatsuaki Okamoto and Tetsutaro Kobayashi

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=p*^{2}*q*,
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=p*^{2}*q* 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)

Zipped PostScript File
(November 18, 1999) (113K)

Adobe Acrobat (.pdf) File
(November 18, 1999) (93K)

**
Formal Security Proofs for a Signature Scheme with Partial Message Recovery**

Daniel R. L. Brown and Don B. Johnson

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)

Zipped PostScript File
(February 24, 2000) (623K)

Adobe Acrobat (.pdf) File
(February 24, 2000) (73K)

**
Optimal Parameterization of SNFS**

Robert D. Silverman

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)

*This page was last modified on April 11, 2004.*