IEEE P1363 Research Contributions: Cryptanalysis

Cryptanalysis in Prime Order Subgroups of Zn*
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
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(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)
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 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
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=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)
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.
IEEE Logo IEEE Standards Logo IEEE P1363 Logo
IEEE Home Page IEEE Standards IEEE P1363