RSA keys

Thread View: sci.crypt

2 messages

[T] Back to Threads [V] Tree View [G] Group Articles

2 total messages Started by Eric Weaver Thu, 30 Jul 1992 21:37

#542

Author: Eric Weaver
Date: Thu, 30 Jul 1992 21:37

28 lines
1264 bytes

Summarized for those who haven't a Knuth Vol. II:

 Pick two primes, P and Q, which are NOT one greater than a multiple of 3
  (e.g. 37 won't do).  Probabilistic prime tests are good for this.

 Take a frame of bits F, no shorter than 1/3 the length of PQ (the
public, encryption key), and less than PQ.  

 Encrypt:  F[enc] = F^3 mod PQ.

 Let D (private, decryption key) = [(P-1)(Q-1)/6]+1

 Decrypt: F = F[enc]^D mod PQ.


 P and Q should be of approx. 25% difference in length, and of at
least 450 bits total.  1000 bits or more, if you can afford it, would
be best.

 Decryption is pretty expensive, obviously, so this technique is
commonly used only to exchange key and digest info.

Question for cognoscenti: How hard is it REALLY to guess or search D
from PQ?
-- 
Eric Weaver  Sony AVTC  677 River Oaks Pkwy, MS 35  SJ CA 95134  408 944-4904
& Eng. Asst., KFJC 89.7 -  Foothill College, Los Altos Hills, CA 94022

Re: RSA keys

#546

Author: Jeffrey Shallit
Date: Fri, 31 Jul 1992 09:08

19 lines
1231 bytes

In article <1992Jul30.213709.26515@sfc.sony.com> weaver@sfc.sony.com (Eric Weaver) writes:

[In RSA scheme, with N = PQ, and DE = 1 (mod (P-1)(Q-1))]

>
>Question for cognoscenti: How hard is it REALLY to guess or search D
>from PQ?
>-- 
>Eric Weaver  Sony AVTC  677 River Oaks Pkwy, MS 35  SJ CA 95134  408 944-4904
>& Eng. Asst., KFJC 89.7 -  Foothill College, Los Altos Hills, CA 94022

DE-1 is a multiple of (P-1)(Q-1) = phi(N).  Gary Miller showed
in his thesis how to factor general N in random polynomial time,
given an oracle that returns an arbitrary small multiple of
phi(N).  The reduction is quite efficient.  Therefore, any general
method for finding D (given E and N) would give a fast integer
factoring algorithm, which some would say is unlikely.

Jeff Shallit

Thread Navigation

This is a paginated view of messages in the thread with full content displayed inline.

Messages are displayed in chronological order, with the original post highlighted in green.

Use pagination controls to navigate through all messages in large threads.

Back to All Threads