Re: Is it hard? How to prove it?


"bobic" <fbloveu@xxxxxxxxxxx> wrote in message
news:40c31c36-876a-4097-9d1c-d834ffdb2b8a@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
On May 21, 5:12 pm, Kristian Gjøsteen <kristiag+n...@xxxxxxxxxxxx>
wrote:
bobic <fblo...@xxxxxxxxxxx> wrote:
Recently, I met the following problem, and I need the problem is
proven-hard. Can you give me some hints to prove it? Thanks in
advance!
*********************************************
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.


--
poncho


.

Relevant Pages

  • Re: Is it hard? How to prove it?
    ... you use that black box to solve RSA (or at least, ... that N is the product of two Sophie Germain primes)? ... just shown that solving your problem is at least as hard as solving RSA ... Given, I cannot generate the other two input items x',X. ...
    (sci.crypt)
  • Re: Is it hard? How to prove it?
    ... proven-hard. ... Can you give me some hints to prove it? ... But I cannot reduce it to RSA. ...
    (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)? ... just shown that solving your problem is at least as hard as solving RSA ... Given, I cannot generate the other two input items x',X. ...
    (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)? ... just shown that solving your problem is at least as hard as solving RSA ... Given a, how can we pick g, x', X so that they satisfy the above relation ...
    (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)? ... just shown that solving your problem is at least as hard as solving RSA ... Given a, how can we pick g, x', X so that they satisfy the above relation ...
    (sci.crypt)
Loading