home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / sci / crypt / 5822 < prev    next >
Encoding:
Internet Message Format  |  1992-12-20  |  1.2 KB
  1. Path: sparky!uunet!ogicse!flop.ENGR.ORST.EDU!flop.ENGR.ORST.EDU!usenet
  2. From: koc@rize.ECE.ORST.EDU (Cetin Kaya Koc)
  3. Newsgroups: sci.crypt
  4. Subject: Re: RSA
  5. Message-ID: <1grc92INNb6i@flop.ENGR.ORST.EDU>
  6. Date: 18 Dec 92 02:16:02 GMT
  7. Article-I.D.: flop.1grc92INNb6i
  8. References: <226XVB4w164w@k5qwb.lonestar.org>
  9. Organization: College of Engineering, Oregon State University
  10. Lines: 18
  11. NNTP-Posting-Host: rize.ece.orst.edu
  12.  
  13. In article <226XVB4w164w@k5qwb.lonestar.org> lrk@k5qwb.lonestar.org (Mr.  
  14. Lyn R. Kennedy) writes:
  15. > Also, for ANY value of n ( =p*q), there are at least nine values of m 
  16. > (the message) that will encrypt as m. I.e. E(m) = m and D(m) = m. Three 
  17. > of these are trivial, m=0, 1, and n-1. The other six allow factoring n. 
  18. > For some values of e, there are more cases but I'm not sure how easy it 
  19.  
  20. E(m) = m for as many as k messages where
  21.    k = [1+gcd(e-1,p-1)]*[1+gcd(e-1,q-1)].
  22.  
  23. The smallest value k=[1+2]*[1+2]=9 as pointed out. This is because
  24.    gcd(e-1,p-1) >= 2 
  25. since p and e are odd numbers; p is prime, and gcd(e,(p-1)(q-1))=1 and
  26. thus e is odd.
  27.  
  28. Thus, you want gcd(e-1,p-1) and gcd(e-1,q-1) as small as possible.
  29.  
  30. Ref: Blakley & Borosh. Comp. & Math. with App. 5:169-178, 1979.
  31.