Prev: Binary code
Next: question about the Secure Remote Password protocol
From: mark on 31 Mar 2010 01:53
I understand that if we can factor large numbers quickly, we can
determine p and q from n in an RSA cryptosystem. However, what about
in other applications?

For example, we have a challenge/response protocol where a trusted
server uses an RSA-like scheme to determine a modulus n for the
challenge/response session. If we could factor large numbers quickly,
how is this compromised?
From: Joseph Ashwood on 31 Mar 2010 04:10
"mark" <cheesemonkey22(a)gmail.com> wrote in message
news:50adca08-80c2-415c-a434-96c3db6a26d6(a)k19g2000yqn.googlegroups.com...
> I understand that if we can factor large numbers quickly, we can
> determine p and q from n in an RSA cryptosystem. However, what about
> in other applications?
>
> For example, we have a challenge/response protocol where a trusted
> server uses an RSA-like scheme to determine a modulus n for the
> challenge/response session. If we could factor large numbers quickly,
> how is this compromised?

The attacker can now compromise the entire challenge response system, so the
attacker can impersonate the client or the server.

There is also the matter that DLP (integer Discrete Logarithm Problem)
appears to be polynomially equivalent to IFP (Integer Factoring Problem), so
a fast factoring algorithm will probably not only fell RSA, but also DH,
ElGamal and related technologies.

A fast factoring algorithm may not break "everything" but it will break an
enormous amount.
Joe



From: Pubkeybreaker on 31 Mar 2010 07:53
On Mar 31, 4:10 am, "Joseph Ashwood" <ashw...(a)msn.com> wrote:
> "mark" <cheesemonke...(a)gmail.com> wrote in message
>
> news:50adca08-80c2-415c-a434-96c3db6a26d6(a)k19g2000yqn.googlegroups.com...
>
> > I understand that if we can factor large numbers quickly, we can
> > determine p and q from n in an RSA cryptosystem.  However, what about
> > in other applications?
>
> > For example, we have a challenge/response protocol where a trusted
> > server uses an RSA-like scheme to determine a modulus n for the
> > challenge/response session.  If we could factor large numbers quickly,
> > how is this compromised?
>
> The attacker can now compromise the entire challenge response system, so the
> attacker can impersonate the client or the server.
>
> There is also the matter that DLP (integer Discrete Logarithm Problem)
> appears to be polynomially equivalent to IFP (Integer Factoring Problem),

Stop posting misinformation. Your last assertion is not correct.

*IF* we can solve DLP in an arbitrary finite ring (e.g. one of
unknown order),
then we can factor quickly. So far, we don't even have a sub-
exponential
algorithm for doing so. The best we have is a sub-exponential
algorithm
for DLP over rings of KNOWN order.

And noone knows how to do the converse: solve DLP quickly if we can
factor
quickly.
From: Joseph Ashwood on 31 Mar 2010 08:23
"Pubkeybreaker" <pubkeybreaker(a)aol.com> wrote in message
news:3aa4fff6-8104-48a0-a2ba-c7d1b1bbc989(a)k13g2000yqe.googlegroups.com...
> On Mar 31, 4:10 am, "Joseph Ashwood" <ashw...(a)msn.com> wrote:
>> There is also the matter that DLP (integer Discrete Logarithm Problem)
>> appears to be polynomially equivalent to IFP (Integer Factoring Problem),
>
> Stop posting misinformation. Your last assertion is not correct.
>
> *IF* we can solve DLP in an arbitrary finite ring (e.g. one of
> unknown order),
> then we can factor quickly. So far, we don't even have a sub-
> exponential
> algorithm for doing so. The best we have is a sub-exponential
> algorithm
> for DLP over rings of KNOWN order.
>
> And noone knows how to do the converse: solve DLP quickly if we can
> factor
> quickly.

That's why I said "appears." The fastest algorithms for factoring also solve
discrete log. As you stated the actual proof only goes one direction
time(DLP) >= time(IFP), but with the fastest known algorithms for IFP also
solving DLP it currently appears that they may in fact be equivalent.

At this point it is far from certain that they are the same, and only
certain, as you noted, that DLP is at least as hard as IFP, but with the
fastest non-quantum and fast quantum algorithms both solving DLP and IFP the
likelihood is significant.
Joe

From: Pubkeybreaker on 31 Mar 2010 16:49
On Mar 31, 8:23�am, "Joseph Ashwood" <ashw...(a)msn.com> wrote:
> "Pubkeybreaker" <pubkeybrea...(a)aol.com> wrote in message
>
> news:3aa4fff6-8104-48a0-a2ba-c7d1b1bbc989(a)k13g2000yqe.googlegroups.com...
>
>
>
>
>
> > On Mar 31, 4:10 am, "Joseph Ashwood" <ashw...(a)msn.com> wrote:
> >> There is also the matter that DLP (integer Discrete Logarithm Problem)
> >> appears to be polynomially equivalent to IFP (Integer Factoring Problem),
>
> > Stop posting misinformation. �Your last assertion is not correct.
>
> > *IF* �we can solve DLP in an arbitrary finite ring (e.g. one of
> > unknown order),
> > then we can factor quickly. �So far, �we don't even have a sub-
> > exponential
> > algorithm for doing so. �The best we have is a sub-exponential
> > algorithm
> > for DLP over rings of KNOWN order.
>
> > And noone knows how to do the converse: �solve DLP quickly if we can
> > factor
> > quickly.
>
> 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.

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