Subject: missing primes

From: Ingo Luetkebohle <[email-masked]>
Date: Mon, 25 Jun 2001 23:29:43 +0200

Hello,

what are the primes in an OpenPGP RSA secret key packet used for?
AFAICT, they are not needed for encryption and/or signing.

Related to that: What will happen if they are omitted, e.g. because an
underlying library can only supply exponent and modulus?

Regards

-- 
	Ingo Luetkebohle / [email-masked] / 95428014
/
| Student of Computational Linguistics & Computer Science;
| Fargonauten.DE sysadmin; Gimp Registry maintainer;
| FP: 3187 4DEC 47E6 1B1E 6F4F  57D4 CD90 C164 34AD CE5B

---

From: Derek Atkins <[email-masked]>
Date: 25 Jun 2001 18:54:00 -0400

The primes are used for the Chinese Remainder Theorem, an RSA
speed-up technique.

-derek

Ingo Luetkebohle <[email-masked]> writes:

> --1yeeQ81UyVL57Vl7
> Content-Type: text/plain; charset=us-ascii
> Content-Disposition: inline
> Content-Transfer-Encoding: quoted-printable
> 
> Hello,
> 
> --=20
> --1yeeQ81UyVL57Vl7
> Content-Type: application/pgp-signature
> Content-Disposition: inline
> 
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.0.6 (GNU/Linux)
> Comment: Weitere Infos: siehe http://www.gnupg.org
> 
> iD8DBQE7N61HzZDBZDStzlsRAfDeAKCJCFUVCZutKDoUqm+QtDb/E+unbwCfTa+0
> JzImBpl9kop/T3tiO+Nrx04=
> =Z/Jv
> -----END PGP SIGNATURE-----
> 
> --1yeeQ81UyVL57Vl7--

-- 
       Derek Atkins, SB '93 MIT EE, SM '95 MIT Media Laboratory
       Member, MIT Student Information Processing Board  (SIPB)
       URL: http://web.mit.edu/warlord/    PP-ASEL-IA     N1NWH
       [email-masked]                        PGP key available

---

From: "Michael Young" <[email-masked]>
Date: Tue, 26 Jun 2001 13:29:53 -0400

-----BEGIN PGP SIGNED MESSAGE-----

In addition to CRT-based optimizations (as Derek Atkins noted),
consistency checks may (or should) look at the p,q, and u values,
to detect modifications in the secret key packet.  In the wake of
an "attack" discovered by some Czech researchers recently,
I expect most implementations to have such checks in place now.
(No pun intended. :-)

Consequently, a key without these fields will not be usable by most other
implementations.

---

From: "Michael Young" <[email-masked]>
Date: Tue, 26 Jun 2001 17:15:08 -0400

-----BEGIN PGP SIGNED MESSAGE-----

> underlying library can only supply exponent and modulus?

I suppose I should have addressed the underlying issue -- you can always
compute (p,q,u) from (n,e,d) and build a full packet anyway.

Knowing e*d, you can generate a non-trivial square root of 1 (mod n),
which will yield (p+-1) or (q+-1).  Here's a quick draft of an
algorithm:
    Compute z=(e*d-1) and find odd t such that z=t*2^s.
    Note that for all x relatively prime to n, x^(e*d)~=x, so x^z~=1.
    Choose random x (as above), and compute y=x^t.
    Continue squaring y until y^2==1 (mod n).
    Now, (y+1)(y-1)=p*q*k (for some k).  If y is not +-1, then k is not zero,
     and there must be a factor of p in (y+1) or (y-1).
    Test gcd(y+-1, n).
    Try x values until you succeed; each try has a 50% chance of winning.

---

From: Ingo Luetkebohle <[email-masked]>
Date: Wed, 27 Jun 2001 12:37:47 +0200

Hello,

many thanks to Derek and Michael, their helpful explanations were very
enlightening :)

Regards