Subject: Quick comment on the Small Subgroup Attack draft

From: Tony Mione <[email-masked]>
Date: Thu, 15 Jul 1999 11:43:33 -0400 (EDT)

I noticed a subtle problem in the text in section 3.3. The first paragraph
reads:

 The prime p could be chosen such that p-1=2*q*j where j is the product 
                                                 ^^^^^^^^^^^^^^^^^^^^^^
 of large primes (large means greater than or equal to q).  This will 
 ^^^^^^^^^^^^^^^

 prevent an attacker from being able to find an element of small order 
 modulo p, thus thwarting the small-subgroup attack.  One method to 
 produce primes of this form is to run the prime generation algorithm 
 multiple times until an appropriate prime is obtained.  As an example, 
 the value of j could be tested for primality.  If j is prime, then the 
                                                ^^^^^^^^^^^^^
 value of p could be accepted, otherwise the prime generation algorithm 
 would be run again, until a value of p is produced with j prime.
                                                    ^^^^^^

Last time I read the definition, a number cannot be both prime and the
product of 2 primes at the same time. Are we talking about j in the last
sentence or one of the other variables in the expression 'p-1=...'?

Tnx.

Tony Mione, RUCS/TD, Rutgers University, Hill 055, Piscataway,NJ - 732-445-0650
[email-masked]                        W3: http://noc.rutgers.edu/~mione/
PGPFP:D4EEA987E870277C  24AAE6E9E6ABD088     ***** Important: Rom 10:9-11 *****
Author of 'CDE and Motif : A Practical Primer', Prentice-Hall PTR

---

From: Darren Harter <[email-masked]>
Date: Thu, 15 Jul 1999 17:48:37 +0100

Tony,

I believe it should read

The prime p could be chosen such that p-1=2*q*j where j is a large prime (large means greater than or equal to q). i.e. (p-1) is a product of large primes.

Regards,

Darren

------------------------------------------------------------------------
Darren Harter B.Sc (Hons) CEng MBCS
Application Development Group, UK
Entegrity Solutions Corp.
Tel: +44 1452 371383
Fax: +44 1452 371384
Cell: +44 7801 812850
Email: mailto:[email-masked]
http://www.entegrity.com
http://www.entegrity.co.uk

-----Original Message-----
From:	Tony Mione [SMTP:[email-masked]]
Sent:	Thursday, July 15, 1999 4:44 PM
To:	[email-masked]
Cc:	Tony Mione
Subject:	Quick comment on the Small Subgroup Attack draft

Tnx.

---

From: Robert Zuccherato <[email-masked]>
Date: Thu, 15 Jul 1999 13:19:07 -0400

The first sentence should read:

The prime p could be chosen such that p-1=2*q*j where j is prime or the
product of large primes (large means greater than or equal to q).

That should make more sense.

> ----------
> From: 	Tony Mione[SMTP:[email-masked]]
> Sent: 	Thursday, July 15, 1999 11:43 AM
> To: 	[email-masked]
> Cc: 	Tony Mione