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

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

Expand Messages
  • Paul Leyland
    ... 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
    Message 1 of 18 , Feb 15, 2012
    • 0 Attachment
      On Wed, 2012-02-15 at 18:26 +0000, 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
      algorith,

      > 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.

      Paul
    • Paul Leyland
      ... Give that man a {coconut,cigar,token prize of your choice}.
      Message 2 of 18 , Feb 15, 2012
      • 0 Attachment
        On Wed, 2012-02-15 at 17:20 +0000, djbroadhurst wrote:
        >
        > --- In primenumbers@yahoogroups.com,
        > Phil Carmody <thefatphil@...> wrote:
        >
        > > I was interested in what the title of the paper referred to
        >
        > I suggest that
        > Ron = R.L. Rivest
        > Whit = W. Diffie
        > but I am not sure if they had a direct argument?

        Give that man a {coconut,cigar,token prize of your choice}.
      • djbroadhurst
        ... I think that Phil might be recalling this paper: http://cr.yp.to/lineartime/dcba-20040404.pdf David (the Open DJB :-)
        Message 3 of 18 , Feb 15, 2012
        • 0 Attachment
          --- In primenumbers@yahoogroups.com,
          Phil Carmody <thefatphil@...> wrote:

          > I wouldn't be surprised if DJB
          > (the UIUC one, not the Open one)
          > didn't document such an algorithm

          I think that Phil might be recalling this paper:
          http://cr.yp.to/lineartime/dcba-20040404.pdf

          David (the Open DJB :-)
        • Phil Carmody
          ... Using an algorithm from (other) DJB. I said that might be the case, didn t I? Aparently I d only need to do ~400Mdigit GCDs rather than giga-digit ones,
          Message 4 of 18 , Feb 15, 2012
          • 0 Attachment
            --- On Wed, 2/15/12, djbroadhurst <d.broadhurst@...> wrote:
            > However, the GCD idea seems to work OK:
            >
            > https://freedom-to-tinker.com/blog/nadiah/new-research-theres-no-need-panic-over-factorable-keys-just-mind-your-ps-and-qs

            Using an algorithm from (other) DJB. I said that might be the case, didn't I?

            Aparently I'd only need to do ~400Mdigit GCDs rather than giga-digit ones, and less than half the RAM. That drops the estimation to about a day. Which is in remarkable agreement with that team's results. Most remarkable as it's a distinct algorithm from DJB's. It might be worth actually implementing, to see how the two compare to each other. To have apparently the same Big-Oh and similar constant to a DJB algorithm just from a back-of-a-fag-packet algorithm doesn't happen every day.

            Phil
          • djbroadhurst
            ... Bang on, good Sir! ... Fortune favours the unsecretive :-) David (the Open DJB)
            Message 5 of 18 , Feb 15, 2012
            • 0 Attachment
              --- In primenumbers@yahoogroups.com,
              Phil Carmody <thefatphil@...> wrote:

              > Using an algorithm from (other) DJB.
              > I said that might be the case, didn't I?

              Bang on, good Sir!

              > To have apparently the same Big-Oh and similar constant
              > to a DJB algorithm just from a back-of-a-fag-packet algorithm
              > doesn't happen every day.

              Fortune favours the unsecretive :-)

              David (the Open DJB)
            • Phil Carmody
              ... 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
              Message 6 of 18 , Feb 15, 2012
              • 0 Attachment
                --- 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"?)

                Phil
              • djbroadhurst
                ... It s a poor title for what purports to be a serious article (on insufficient entropy). Try to imagine Pauli using the title Izzy hat geirrt; Bert hat
                Message 7 of 18 , Feb 15, 2012
                • 0 Attachment
                  --- In primenumbers@yahoogroups.com,
                  Paul Leyland <paul@...> wrote:

                  > > I suggest that
                  > > Ron = R.L. Rivest
                  > > Whit = W. Diffie
                  > > but I am not sure if they had a direct argument?
                  >
                  > Give that man a {coconut,cigar,token prize of your choice}.

                  It's a poor title for what purports to be a
                  serious article (on insufficient entropy).

                  Try to imagine Pauli using the title
                  "Izzy hat geirrt; Bert hat recht" in
                  Encyklop├Ądie der Mathematischen Wissenschaften,
                  Vol. 5, 539-775 (1921).

                  David
                • Phil Carmody
                  ... My method s obvious enough that I m sure it must have occured to Dan, and therefore I m pretty sure there must be something like a log log N of leverage in
                  Message 8 of 18 , Feb 15, 2012
                  • 0 Attachment
                    --- On Wed, 2/15/12, djbroadhurst <d.broadhurst@...> wrote:
                    > Phil Carmody <thefatphil@...> wrote:
                    > > Using an algorithm from (other) DJB.
                    > > I said that might be the case, didn't I?
                    >
                    > Bang on, good Sir!
                    >
                    > > To have apparently the same Big-Oh and similar constant
                    >
                    > > to a DJB algorithm just from a back-of-a-fag-packet algorithm
                    > > doesn't happen every day.
                    >
                    > Fortune favours the unsecretive :-)

                    My method's obvious enough that I'm sure it must have occured to Dan, and therefore I'm pretty sure there must be something like a log log N of leverage in his method that makes it win in the long run. (That would be a factor of 20-ish at these sizes, and not to be sniffed at.) However, I will confess to not having read his paper for about 6 years, including today.

                    Phil
                  Your message has been successfully submitted and would be delivered to recipients shortly.