home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / sci / crypt / 2792 < prev    next >
Encoding:
Text File  |  1992-07-31  |  1.2 KB  |  32 lines
  1. Newsgroups: sci.crypt
  2. Path: sparky!uunet!sun-barr!cs.utexas.edu!torn!watserv2.uwaterloo.ca!watserv1!graceland.uwaterloo.ca!shallit
  3. From: shallit@graceland.uwaterloo.ca (Jeffrey Shallit)
  4. Subject: Re: RSA keys
  5. Message-ID: <Bs8xDs.Ctp@watserv1.uwaterloo.ca>
  6. Sender: news@watserv1.uwaterloo.ca
  7. Organization: University of Waterloo
  8. References: <1992Jul30.213709.26515@sfc.sony.com>
  9. Date: Fri, 31 Jul 1992 09:08:14 GMT
  10. Lines: 20
  11.  
  12. In article <1992Jul30.213709.26515@sfc.sony.com> weaver@sfc.sony.com (Eric Weaver) writes:
  13.  
  14. [In RSA scheme, with N = PQ, and DE = 1 (mod (P-1)(Q-1))]
  15.  
  16. >
  17. >Question for cognoscenti: How hard is it REALLY to guess or search D
  18. >from PQ?
  19. >-- 
  20. >Eric Weaver  Sony AVTC  677 River Oaks Pkwy, MS 35  SJ CA 95134  408 944-4904
  21. >& Eng. Asst., KFJC 89.7 -  Foothill College, Los Altos Hills, CA 94022
  22.  
  23. DE-1 is a multiple of (P-1)(Q-1) = phi(N).  Gary Miller showed
  24. in his thesis how to factor general N in random polynomial time,
  25. given an oracle that returns an arbitrary small multiple of
  26. phi(N).  The reduction is quite efficient.  Therefore, any general
  27. method for finding D (given E and N) would give a fast integer
  28. factoring algorithm, which some would say is unlikely.
  29.  
  30. Jeff Shallit
  31.  
  32.