Forum

Challenge "Unconcealed RSA messages"

Challenge "Unconcealed RSA messages"  

  By: admin on Nov. 2, 2011, 8:16 a.m.

A strange effect might occur if you encrypt a message using the RSA cipher: The encrypted message has got the same value as the plaintext. Can you find all of these unconcealed messages for the given public key?
Read more...

 Last edited by: admin on Oct. 31, 2021, 2:54 a.m., edited 1 time in total.

Re: Challenge  

  By: DarkFibre on Nov. 2, 2011, 11:52 p.m.

Usually I'm really good with the RSA challenges but I am completely stumped by this one. These numbers seem way to large for brute force so there must be a formula. I looked at 20 different books and a bunch of papers and none mention how to find these points and refer back to papers that are unavailable online except for ridiculous amounts of money.

Re: Challenge  

  By: Veselovský on Nov. 3, 2011, 2:21 a.m.

When I started to make this challenge I had no idea how to find them. Similarly I was not able to find a method in books or the Internet. I just found the formula for computing their number, which is given as a hint.
But anyway I was able to program my own algorithm which finds them very quickly even on my old almost 15 years old computer ;-)

Re: Challenge  

  By: DarkFibre on Nov. 3, 2011, 4:38 a.m.

Is hint #2 really only a hint for step II, or for both steps?

Re: Challenge  

  By: Veselovský on Nov. 3, 2011, 11:10 a.m.

Is hint #2 really only a hint for step II, or for both steps?

…as is said.

Do not care about second hint until you can solve the first part of the challenge.
When you figure out how to solve the first part, then it will be clear what is the purpose of the second hint.

Re: Challenge  

  By: randall77 on Nov. 3, 2011, 9:04 p.m.

It seems to me that this task requires factorization of N. For instance, one value for m is going to satisfy m = 1 mod p, m = 0 mod q. If we can find it (which we must do to answer the question), then we can use this m to factor N, as q = gcd(N,m).

What am I missing here? Or are we supposed to be able to factor these large Ns?

Re: Challenge  

  By: Dano on Nov. 5, 2011, 11:29 p.m.

hi,

is there a way to compute the unconcealed messages or is this bruteforce?

part1:
N is factorized.
P,Q,D are now known

i know that there xxx possible unconcealed messages

wha is now to do?
CRT?
BF?
or is there a other way to solve Part1?

mfg Dano

Re: Challenge  

  By: jomandi on Nov. 6, 2011, 12:29 a.m.

When you take e.g. p (N=p*q) then you can CALCULATE the fixed points mod p (a generator mod p could be very helpful).
The rest should be clear.

Re: Challenge  

  By: fretty on Nov. 6, 2011, 4:06 p.m.

I haven't started work on this so far but:

m^e = m mod N leads to 4 situations:

1) m = 0 mod p and m = 0 mod q. This gives (by CRT) the m=0 unconcealed message.

2) m^(e-1) = 1 mod p and m^(e-1) = 1 mod q. This gives (by CRT) the m's satisfying m^(e-1) = 1 mod N. The (always occuring) unconcealed messages m=1, m=N-1 come from this situation, but there may be more (this is basically a group theory problem but I am not sure if there is an algorithm to solve this problem other than brute force).

3) m = 0 mod p and m^(e-1) = 1 mod q.

4) m = 0 mod q and m^(e-1) = 1 mod p.

If you know p and q then I imagine 3) and 4) are easier to solve.

I am guessing that the intended solution will be some simplified brute force by using these facts.

Re: Challenge  

  By: jomandi on Jan. 29, 2012, 10:31 p.m.

i got a pm with a request for a hint for this challenge. since i think that others could also benefit from a hint, i answer the request in the forum.

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]=0
  • for each number m with 0[HTML_REMOVED] 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.

best regards,
jomandi

Re: Challenge  

  By: DarkFibre on Feb. 23, 2012, 3:08 a.m.

That was the perfect hint. It said almost nothing, but was just enough to point those of us with no number theory in the right direction. Thanks!

What I don't understand is how the primes were picked to spell out the chosen messages. (And I'm still not sure I get hint #2 in the pdf.)

Re: Challenge  

  By: Veselovský on Feb. 23, 2012, 1:23 p.m.

What I don't understand is how the primes were picked to spell out the chosen messages.

Well, making the challenge was a bigger challenge than the challenge itself.
It is much harder to find proper primes (big enough) that produce the desired messages than to find the messages when the primes (actually the modulus) are given.
Try it for yourself I will not spoil your fun with giving hints.

I will send you a PM concerning the hint #2 in the PDF.
I can imagine that the challenge can be solved even without the hint #2. But this hint makes it a little easier.

Re: Challenge  

  By: Etschupu on July 6, 2012, 11:37 a.m.

Is hint #2 really only a hint for step II, or for both steps?

…as is said.

Do not care about second hint until you can solve the first part of the challenge.
When you figure out how to solve the first part, then it will be clear what is the purpose of the second hint.

Does this mean, that one has to use some of the results of the first part to be able to factor the second public key efficiently? (the part "bestimmten Quadratzahl" bothers me [HTML_REMOVED] )

Or does the second hint just reveals the structure of the two primes in order to implement the correct factoring algorithm? And with "relative kleinen Vielfachen" you mean small enough to bruteforce or small compared to the size of N but way to large to bruteforce?

Re: Challenge  

  By: jomandi on July 6, 2012, 2:49 p.m.

Is hint #2 really only a hint for step II, or for both steps?

…as is said.

Do not care about second hint until you can solve the first part of the challenge.
When you figure out how to solve the first part, then it will be clear what is the purpose of the second hint.

Does this mean, that one has to use some of the results of the first part to be able to factor the second public key efficiently? (the part "bestimmten Quadratzahl" bothers me [HTML_REMOVED] )

Or does the second hint just reveals the structure of the two primes in order to implement the correct factoring algorithm? And with "relative kleinen Vielfachen" you mean small enough to bruteforce or small compared to the size of N but way to large to bruteforce?

you don't have to use any results from the first part in the second part. you only need the "method" how to find the fixed points from the first part.

the hint #2 is only a help to factorize the second modulus N.

hint #2 says the following:
|p-x^2|[HTML_REMOVED] p-x^2=-1,0 or +1 => p=x^2-1,x^2 or x^2+1
|kq-x|[HTML_REMOVED] kq-x=-1,0 or +1 => k*q=x-1,x or x+1

you get now the following equation:
(p)(kq)=k(pq)=kN=(x^2+a)(x+b), with a in {-1,0,+1} and b in {-1,0,+1}

this equation has a solution for x with -1<=a<=+1, -1<=b<=+1 and a not so big k ([HTML_REMOVED] p=x^2+a and q=(x+b)/k

Re: Challenge  

  By: fmoraes on Nov. 28, 2013, 4:20 p.m.

Do I need to find the primitive roots mod p and q in order to solve this?

Francisco


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