Re: RSA ecnryption confusion

Phil Carmody wrote:
"Blind Anagram" <me@xxxxxxxxxxx> writes:
"Phil Carmody" <thefatphil_demunged@xxxxxxxxxxx> wrote in message
news:87d4nqmxt6.fsf@xxxxxxxxxxxxxxxxxxxxxxx
"Blind Anagram" <me@xxxxxxxxxxx> writes:
"Phil Carmody" <thefatphil_demunged@xxxxxxxxxxx> wrote in message
news:87d4nrmly1.fsf@xxxxxxxxxxxxxxxxxxxxxxx
Blind Anagram <noone@xxxxxxxxxxx> writes:
Pubkeybreaker wrote:

The implementation is *irrelevant*. If the private key is
known, then the public key becomes *trivially* constructible.
It doesn't matter if p,q, are stored directly, if they are
stored in CRT format, or even if they are not stored at all.
If the private exponent is KNOWN, then constructing the
factors requires a simple, polynomial time random algorithm.
When d is less than N^0.29, does the reconstruction of the
factors of N from d work without knowing e?
Yes. If N, e and d are known, factoring N is trivial.
ed is a multiple of lambda(pq), can be used to
reconstruct phi(pq) = pq-p-q+1. Therefore you can
trivially find p+q. 2 equations in 2 unknowns - bingo.
Phil, did you miss the "without knowing e" bit?
No. With knowing e, there's a trivial algorithm as shown.
Therefore the lattice algorithm evidently applies to the
"without knowing e" case. What other case did you think
it applied to?
I was puzzled because most of your answer was about a question that I
did not ask.

Where's the black king? It's not on row 1,2,3,4,5,7, or 8, and not in column 1,2,3,5,6,7,8.

Once you remove other possibilities, that which is left
is clearly defined.

What I am unclear about here is that the two keys (e,N) and (d,N) are interchangeable at the fundamental algorithm level.

Hence if an algorithm can recover the prime factors of N knowing only d when d < N^0.29, why cannot this also be done knowing only e when e is less than N^0.29 (which it pretty well always is)?

I may well be screwed up here since it is a long time since I really looked at any of this. But my uncertainty was such that I felt it was worthwhile posing the question to see what came of it.
.

Relevant Pages

  • Re: RSA ecnryption confusion
    ... stored in CRT format, or even if they are not stored at all. ... If the private exponent is KNOWN, then constructing the ... did you miss the "without knowing e" bit? ... there's a trivial algorithm as shown. ...
    (sci.crypt)
  • Re: RSA ecnryption confusion
    ... stored in CRT format, or even if they are not stored at all. ... If the private exponent is KNOWN, then constructing the ... did you miss the "without knowing e" bit? ... there's a trivial algorithm as shown. ...
    (sci.crypt)
  • Re: Coding Horrors, Cargo Cult Programming, and other Ghoulish Things
    ... Most of the time, the same algorithm will be implemented differently in C, Delphi or Java, and it'll not just be a case of syntax adaptation, but one of a logic variant. ... That means knowing that your code isn't directly executed but an assembly is, that means knowing what an exception frame is, what a stack is, what a thread is, what memory actually is and how values are stored, etc. ... Well, actually you do, if you want to understand why the loop counter variable will sometimes go in reverse in the debugger;) ...
    (borland.public.delphi.non-technical)
  • Re: need help ...
    ... >> The algorithm I'm thinking of actually needs N distinct ... Simply knowing that the range of generated numbers ... It just needs an unbiased PRNG (and since one can ... If equality occurs an ambiguity ...
    (comp.lang.c)
  • Re: RSA Demonstration
    ... May this be the reason why knowing the public key ... > won't give you the private key? ...
    (sci.crypt)