Prev: Binary code
Next: question about the Secure Remote Password protocol
From: Joseph Ashwood on 1 Apr 2010 02:43
"Pubkeybreaker" <pubkeybreaker(a)aol.com> wrote in message
news:54d910a5-bd62-445d-913b-88ecf9f749f3(a)e6g2000yqh.googlegroups.com...
> On Mar 31, 8:23�am, "Joseph Ashwood" <ashw...(a)msn.com> wrote:
>> That's why I said "appears." The fastest algorithms for factoring also
>> solve
>> discrete log.
>
> No, they do NOT. NFS can be used for factoring and DLP over
> finite fields or groups of KNOWN order that can be embedded in Q.
>
> . It can not solve DLP over a ring/group
> of UNKNOWN order.

And in integers, for the integer DLP, you'll find my initial response was
specific on this, calculating the order is trivial, and a trivial operation
past factoring. This makes DLP of an unknonw order a matter of
time(factoring)+time(known order DLP), reducing assypmtotically to the same
function as for known. Yes it is more complex, more costly, and costs twice
as much in every way, but "If we could factor large numbers quickly" it
becomes rather inexpensive, with significant probability.
Joe

From: Pubkeybreaker on 1 Apr 2010 07:49
On Apr 1, 2:43 am, "Joseph Ashwood" <ashw...(a)msn.com> wrote:
> "Pubkeybreaker" <pubkeybrea...(a)aol.com> wrote in message
>
> news:54d910a5-bd62-445d-913b-88ecf9f749f3(a)e6g2000yqh.googlegroups.com...
>
> > On Mar 31, 8:23 am, "Joseph Ashwood" <ashw...(a)msn.com> wrote:
> >> That's why I said "appears." The fastest algorithms for factoring also
> >> solve
> >> discrete log.
>
> > No, they do NOT.  NFS can be used for factoring and DLP over
> > finite fields or groups of KNOWN order that can be embedded in Q.
>
> > .  It can not solve DLP over a ring/group
> > of UNKNOWN order.
>
> And in integers, for the integer DLP, you'll find my initial response was
> specific on this, calculating the order is trivial, and a trivial operation
> past factoring. This makes DLP of an unknonw order a matter of
> time(factoring)+time(known order DLP), reducing assypmtotically to the same
> function as for known. Yes it is more complex, more costly, and costs twice
> as much in every way, but "If we could factor large numbers quickly" it
> becomes rather inexpensive, with significant probability.
>                     Joe


Idiot. You have no idea what you are talking about.

What you posted "isn't even wrong".
From: Joseph Ashwood on 2 Apr 2010 08:44
"Pubkeybreaker" <pubkeybreaker(a)aol.com> wrote in message
news:7a919ab3-c0c9-4e9e-b3ec-59187f09909f(a)h27g2000yqm.googlegroups.com...

> Idiot. You have no idea what you are talking about.
>
> What you posted "isn't even wrong".

In that case lets step though the "isn't even wrong," step me when I lose
you. Of course I could just go back to my original statement "a fast
factoring algorithm will probably not only fell RSA, but also DH,
ElGamal and related technologies" which all have known orders but where's
the fun in that?

Since we're dealing strictly with integers, I'll be working exclusively in
those. For simplicity I'll simply work with Zn where p is the modulus, where
p is not necessarily prime
Assume the order is unknown.
Step 1: Calculate the order
Step 2: perform DLP on known order



Step 1: Calculate the order
Because p is not necessarily prime, the order cannot be computed
immediately, 2^k mod 10 is one example
Given the factors of p though it is trivially calculated
Factor p, this is complex, but it is O(nfs)
compute the order
time O(nfs)

Step 2: Perform the DLP on known order
time O(nfs)

sum it up to get 2*O(nfs) is assymptotically equivalent to O(nfs). There may
be faster methods of calculating the order, but this makes the assymptotic
math easier.

So "a fast factoring algorithm will probably not only fell RSA, but also DH,
ElGamal and related technologies."
Joe
Joe

From: Pubkeybreaker on 2 Apr 2010 10:00
On Apr 2, 8:44 am, "Joseph Ashwood" <ashw...(a)msn.com> wrote:
> "Pubkeybreaker" <pubkeybrea...(a)aol.com> wrote in message
>
> news:7a919ab3-c0c9-4e9e-b3ec-59187f09909f(a)h27g2000yqm.googlegroups.com...
>
> > Idiot.  You have no idea what you are talking about.
>
> > What you posted "isn't even wrong".
>
> In that case lets step though the "isn't even wrong," step me when I lose
> you. Of course I could just go back to my original statement "a fast
> factoring algorithm will probably not only fell RSA, but also DH,
> ElGamal and related technologies" which all have known orders but where's
> the fun in that?


You also said:

"There is also the matter that DLP (integer Discrete Logarithm
Problem)
appears to be polynomially equivalent to IFP (Integer Factoring
Problem), "

And this is grossly wrong. They are NOT known to be polynomially
equivalent.

*IF* we can solve DLP in a group of unknown order quickly, then yes,
we can factor
quickly. There is no known method that allows the reverse.

>
> Since we're dealing strictly with integers, I'll be working exclusively in
> those. For simplicity I'll simply work with Zn where p is the modulus, where
> p is not necessarily prime

Huh? What is "p? You have not defined it!


> Assume the order is unknown.
> Step 1: Calculate the order

OK, if we have a P-time factoring algorithm we can do this.


> Step 2: perform DLP on known order

How? You have totally failed to show that a P-time factoring
algorithm
allows us to solve DLP in P-time. We can then solve DLP using NFS
but NFS is NOT P-time!!!! Thus, while a P-time factoring algorithm
allows
us to compute the order quickly, we still can't solve the DLP
quickly.
NFS is the best we have for DLP and it is NOT fast. --> it is sub-
exponential.

A fast factoring algorithm gives us the ability to transform DLP over
a group of
unknown order to solving DLP over a group of known order. But this
does
NOT yield a fast algorithm for the latter!

> So "a fast factoring algorithm will probably not only fell RSA, but also DH,
> ElGamal and related technologies."

Justify the "probably" quantifier.


From: Joseph Ashwood on 4 Apr 2010 05:12
"Pubkeybreaker" <pubkeybreaker(a)aol.com> wrote in message
news:61ac9911-485d-4f2f-be17-63e8715805fe(a)q23g2000yqd.googlegroups.com...
> On Apr 2, 8:44 am, "Joseph Ashwood" <ashw...(a)msn.com> wrote:
>> "Pubkeybreaker" <pubkeybrea...(a)aol.com> wrote in message
>>
>> news:7a919ab3-c0c9-4e9e-b3ec-59187f09909f(a)h27g2000yqm.googlegroups.com...
>>
>> > Idiot. You have no idea what you are talking about.
>>
>> > What you posted "isn't even wrong".
>>
>> In that case lets step though the "isn't even wrong," step me when I lose
>> you. Of course I could just go back to my original statement "a fast
>> factoring algorithm will probably not only fell RSA, but also DH,
>> ElGamal and related technologies" which all have known orders but where's
>> the fun in that?
>
>
> You also said:
>
> appears to be

> And this is grossly wrong. They are NOT known to be polynomially
> equivalent.

Now I see where I lost you. You didn't see the "appears to be" as being
different from "is." You should know by now that if I say "appears to be" I
do not mean "is" I mean "appears to be"

So exactly where did I actually claim that are polynomially equivalent?
You'll find I never did, I said they "appear" to be, I said that with
current algorithms they are, etc, but I never actually stated they are
proven to be the same.

I still stand by the statement, integer DLP and IFP appear to be
polynomially equivalent, the next evolution in the algorithmic progress may
separate them again, but for now they appear to be polynomially equivalent.
Joe

First  |  Prev  |  Next  |  Last
Pages: 1 2 3
Prev: Binary code
Next: question about the Secure Remote Password protocol