Forum

Re: Challenge  

  By: aurelie on Nov. 28, 2013, 11:11 p.m.

Hello Francisco,

have you seen this hint by jomandi:

let N = p*q. the following calculations are modulo p:

let g be a generator modulo p. then you have:

  • g^k != 1 mod p, for 0[HTML_REMOVED] - g^(k*(p-1)) = 1 mod p, for all k>=0
  • for each number m with 0[HTML_REMOVED]
    obviously 0 is a trivial solution of m^e = m mod p. for m != 0 mod p you have:
    m^e = m mod p
    => m^(e-1) = 1 mod p
    => m^(e-1) = (g^x)^(e-1) = g^(x*(e-1)) = 1 mod p

so you have to find all solutions of the equation g^(x*(e-1)) = 1 mod p.

analog for q. with the help of the crt, you get all solutions.

I hope this helps you with the challenge.

Best regards,
Lena

Re: Challenge  

  By: fmoraes on Nov. 29, 2013, 2:02 a.m.

Hello Francisco,

have you seen this hint by jomandi:

let N = p*q. the following calculations are modulo p:

let g be a generator modulo p. then you have:

  • g^k != 1 mod p, for 0[HTML_REMOVED] > - g^(k*(p-1)) = 1 mod p, for all k>=0
  • for each number m with 0[HTML_REMOVED] >
    obviously 0 is a trivial solution of m^e = m mod p. for m != 0 mod p you have:
    m^e = m mod p
    => m^(e-1) = 1 mod p
    => m^(e-1) = (g^x)^(e-1) = g^(x*(e-1)) = 1 mod p

so you have to find all solutions of the equation g^(x*(e-1)) = 1 mod p.

analog for q. with the help of the crt, you get all solutions.

I hope this helps you with the challenge.

Best regards,
Lena

My problem is with the last part of the hint about solving for x. That appears to be a discrete logarithm problem.

Re: Challenge  

  By: fmoraes on Nov. 29, 2013, 4:18 p.m.

My problem is with the last part of the hint about solving for x. That appears to be a discrete logarithm problem.

Never mind, I think I figured it out for part one as I can generate the messages. Have to work on part 2 next.

Re: Challenge  

  By: ExAstris on June 29, 2018, 12:15 a.m.

Hello all,

I read Jomandi's useful tips, and I have a few questions.
I am new at this, so bear with me, I am probably missing something really simple.

1) how do we know m < p ?
Is there a guarantee that there are always a few m's < p, such that m^e = m mod p ?

2) in the quote, "for each number m with 0[HTML_REMOVED] p.
Unless all the steps for p can be done 'easily'.

I have read a few papers that all mention how to calculate the fixed points; however, they don't describe how to get all the other m's in a non-"brute force" way.

I would be grateful if someone could point to where my logic fails.

I like these mathematical puzzles, and I learn a lot in the process!

Thanks,

Eric

Re: Challenge  

  By: kumaus on April 2, 2019, 2:33 p.m.

Hello all,

I read Jomandi's useful tips, and I have a few questions.
I am new at this, so bear with me, I am probably missing something really simple.

1) how do we know m < p ?
Is there a guarantee that there are always a few m's < p, such that m^e = m mod p ?

2) in the quote, "for each number m with 0[HTML_REMOVED]
3) if the generator g is also 0 < g < p, then together with x, doesn't it mean that it is going to take (p-1)^2 power modulo operations to find all the (g, x) pairs ?

4) given m < p, wouldn't it be faster to calculate m^e mod p directly, since it requires "only" (p-1) power modulo operations ?

5) "analog for q": I take it to mean 'use the CRT and qinv', and not 'do all the same operations than for p', given that q > p.
Unless all the steps for p can be done 'easily'.

I have read a few papers that all mention how to calculate the fixed points; however, they don't describe how to get all the other m's in a non-"brute force" way.

I would be grateful if someone could point to where my logic fails.

I like these mathematical puzzles, and I learn a lot in the process!

Thanks,

Eric

Hi Eric,

this is a really nice challenge, well worth the work! I'll try to answer your questions as far as I can (no number theory crack …)

Generally, you need to understand finite fields of prime order (see e.g. https://en.wikipedia.org/wiki/Finite_field) and Euler's theorem (https://en.wikipedia.org/wiki/Euler%27s_totient_function). The integers mod p are such a finite field F_p, and such field have the property that they are cyclic, i.e. there exists a generator g such that
F_p = {0} U {g^x : 1 <= x <= p-1}
All elements y of F_p have the property (Euler's Theorem)
y^(p-1) = 1 mod p

1) We do not know that m < p. This is the reason why the CRT is required to construct m from solutions m_p, m_q of m_p^e = m_p mod p and m_q^e = m_q mod q.
Let r = (p-1) / gcd(e-1, p-1).
If you start with a generator g of F_p, take
y = g^r mod p
Then y^(e-1) = 1 mod p, and the same holds for powers of y. Because r * gcd(e-1,p-1) = p-1, there are only gcd(e-1,p-1) distinct powers of y modulo p.

2) See above … 1 <= x <= p-1. Note that x is unique.

3) Why do you need to find all (g, x) pairs? All you need is one generator g, and take modular powers of that.

4) You only need gcd(e-1, p-1) modular powers once you found the generator g, see answer to 1). Luckily!!! [HTML_REMOVED]

5) No, the finite field F_q is quite different from F_p; it is irrelevant that q>p. The generator is (usually) different, so you need to do it again.

Hope this helps (without spoiling …). Good luck!!

Re: Challenge  

  By: Veselovský on May 3, 2019, 3:47 p.m.

To summarize:

n=p*q
Solve for m1, where m1^e=m1 (mod p)
Solve for m2, where m2^e=m2 (mod q)

Notice that these are not discrete logarithm problems. We are solving simple polynomial equation modulo prime. And these are easily solved. If you do not want to know theory behind it just insert it in SAGE or other similar math software.
(one remark: "e" can be replaced with much smaller value, but it does not really matter how big the exponent is anyway, the difficulty does not change)

Then use CRT. Input to CRT are m1, m2, p, q and output would be all "m" that satisfy m^e=m (mod p*q). Again use math software.

If you want to know also theory behind it, then posts by jomandi and kumaus are relevant.


Currently 31 guests and 0 members are online.
Powered by the CrypTool project
Contact | Privacy | Imprint
© 2009-2024 MysteryTwister team