Re: Is it hard? How to prove it?


"bobic" <fbloveu@xxxxxxxxxxx> wrote in message
news:fc21d946-197c-48d5-8ef8-b3809cf7d2c2@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
On May 22, 10:42 am, "Scott Fluhrer" <sfluh...@xxxxxxxxxxxxx> wrote:
*********************************************
Given N, g, x', a, X,C, such that N=pq, p=2p'+1, q=2q'+1,
p,q,p',q'
are primes, g^{p'q'}=1 mod N, x'=xa mod p'q', X=g^x mod N.
To compute m, such that m^a=C mod N.
***********************************************************
Reduce it to RSA.
Thank you for your reply.
But I cannot reduce it to RSA. Since compared to RSA, the new
problem
have three more input items, x', g, and X.

Can you give me more hints?

Suppose that someone gave you a black box that solved your problem.
Could
you use that black box to solve RSA (or at least, RSA with the
restriction
that N is the product of two Sophie Germain primes)? If you can,
you've
just shown that solving your problem is at least as hard as solving
RSA
(with the restriction).

To get you started, the appropriate restricted RSA problem can be
formulated
as:

Given N, a, C, such that N=pq, p=2p'+1, q=2q'+1, p,q,p',q' are
primes,
The problem is to compute m, such that m^a=C mod N.

Thank you for your hint!

Your method cannot work.

Given (N,a,C), I cannot generate the other two input items x',X.

Three, actually, you get to pick g as well...

Note
that we cannot set that x'=xe, since x'=xe mod p'q' is more generic
than x'=xe.

If we rewrite the last two requirements (x'=xa mod p'q', X=g^x mod N) to
eliminate the free x variable, we get:

g^x' = X^a (mod N).

Given a, how can we pick g, x', X so that they satisfy the above
relation
(oh, and you'll also need to make sure that g^{p'q'} = 1 mod N)?


Yes.
Given a, It is hard to pick g, x', X so that they satisfy the above
relation.
Since if it is easy, we can solve the strong RSA problem.

Do you have a proof of that? Here are two trivial ways that you can pick g,
x', X in such a way as to make the equivilance work:

g=X, x'=a

g = X^a mod N, x'=1

However, it would be better if we had a way of generating 'random' instances
of the equivilance; this would allow us to make the stronger statement:

- Given an oracle that has a nontrivial probability of solving random
instances of the bobic problem, we can create a method that has a nontrivial
probability of solving random instances of the restricted RSA problem.

So, is there a way of generating random instances of the above equivilance?
[Hint: the answer is "yes"]

--
poncho


.

Relevant Pages

  • Re: Weak keys for RSA ?
    ... Robert D. Silverman RSA Public Key Validation, ... that p,q are so-called strong primes. ... outline how to guard against the Bach/Shallit ... a standard. ...
    (sci.crypt)
  • Re: Is it hard? How to prove it?
    ... But I cannot reduce it to RSA. ... that N is the product of two Sophie Germain primes)? ... probability of solving random instances of the restricted RSA problem. ... is there a way of generating random instances of the above equivilance? ...
    (sci.crypt)
  • Re: SF: Back to theory
    ... you could pick up a pile of RSA challenge checks ... those upset with my saying special primes, ... Now if mathematicians were honest, good folk, who are sensible, as some ... If surrogate factoring gets quietly developed, ...
    (sci.math)
  • Re: SF: Back to theory
    ... you could pick up a pile of RSA challenge checks ... those upset with my saying special primes, ... Now if mathematicians were honest, good folk, who are sensible, as some ... If surrogate factoring gets quietly developed, ...
    (sci.crypt)
  • Re: Pell equation X^2=d*Y^2+1 where d=RSA number
    ... I think i can easily push the size of d into the RSA range. ... primes from your set, and found that in every case Y has ... interesting that you aren't using continued fractions. ... The notation i'm using always has a common factor for y and d. ...
    (sci.math)
Quantcast