ietf-openpgp
[Top] [All Lists]

## Re: missing primes

2001-06-26 14:18:00
```
-----BEGIN PGP SIGNED MESSAGE-----

```
```Related to that: What will happen if they are omitted, e.g. because an
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.

-----BEGIN PGP SIGNATURE-----
Version: PGP Personal Privacy 6.5.3

iQEVAwUBOzj7EGNDnIII+QUHAQGoTgf+O6Ttd5bP9Fbux3QcCx1DV2XTol9ms2aV
Nr8RN19ps14ya5cL3CND0Z70J8+h1hyP9Gr/9wDENs0OxBcAJz3Yxk6Hf4EW/VNa
0RteTeTlDK70lAZF6f13ESIukqyIFDAQuhC/7jnB0rFJ2JDzndOewCcmDFrubJAt
eNBvBLvXPIjksBaS78gGnL60WQAHajF96HnUyoXGlspmiZiSc/4iK3Vy86N/Bzkq
8VZ5fIfYZGR0BNwFwmXTNhkq9xXZq/z83EFzUN8Glph0I4QiLsb1lNZdgNhjfRPu
1B0SbPf0Et0tOpeZCyyEpkPt6rQrWCfNHjR2ueamWOqDQOM6CfftTA==
=Ah3x
-----END PGP SIGNATURE-----

```
 Current Thread missing primes, Ingo Luetkebohle Re: missing primes, Derek Atkins Re: missing primes, Michael Young Re: missing primes, Ingo Luetkebohle Re: missing primes, Michael Young <=