Loading ...
Sorry, an error occurred while loading the content.

24056Re: [PrimeNumbers] Re: ...factorizer to break RSA...

Expand Messages
  • Phil Carmody
    Feb 15, 2012
      --- On Wed, 2/15/12, Paul Leyland <paul@...> wrote:
      > Phil Carmody wrote:
      > > And is the title of the paper also shrouded in obscurity that you're
      > > sworn not to reveal, or was that just an oversight in your attempt to
      > > swiftly assert that the algorithm I hadn't even yet told you about
      > > could never work?
      > Two things.
      > 1) Never ascribe to malice that which is adequately explained by
      > incompetence.
      > 2) I never said your algorithm couldn't work, only that it might not be
      > as easy to implement and run as it is to assert that you have an
      > algorithm

      I was trying to give as little away as possible, as clearly Lenstra et al. didn't want too much made public about the technique they used, and whilst I'm under no obligation to honour that I thought I'd play along. Anyone who could implement such an algorithm would probably recognize its ingredients, and vice versa. When such things get questioned, my steepest gradient it to simply leak parts of the algorithm I had in mind, obviously.

      It would have been quicker, but far less fun, to run off to my archive of DJB papers, and hunt out the relevant "essentially linear time" paper. So in some ways I'm glad I had to concretise the ideas. When I first had them, they were just so obviously workable, I didn't bother with anything apart from 1-significant-figure guestimations (as you can tell from the factor of 2.5 in my estimation of the size of the input), I'm quite pleased how close they appear to be to potential reality.

      > > Does it just refer to the fact that the *R*SA with multiple prime
      > > secrets is "wrong" compared the single prime secred of *D*H?
      > Yup.

      OK, thanks for that. It was not clear as if there was some rump or coffee (or wine?) session comment that had historically been made between the pair (or to a third party) that I wasn't aware of. If the above is the full story, then I think it's unfair to say that "Ron is wrong", as the mathematics and the algorithmics of composite secrets are still bulletproof. It's just that some people (apparently not too many, fortunately) simple can't implement the algorithm correctly. I believe it's even specified that two times as much apparent entropy must be fed into the system as the length of the primes extracted from it. Clearly nothing like that has been honoured in the failing cases. (Can anyone say "15 bits of entropy"?)

    • Show all 18 messages in this topic