Forum

Challenge "Not-so-Secret Message from Malawi — Part I (RSA)"  

  By: admin on May 15, 2010, 1:06 p.m.

When creating RSA keys, it is important to choose the n and e parameters wisely. This was not done in this example, and thus you should be able to decipher this ciphertext message sent from Malawi. The plaintext gives the codeword, which is related to the photo.
Read more...

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

Re: Challenge "Not-so-secret message from Malawi – Part I"  

  By: Ishaan on March 7, 2011, 9:58 p.m.

Can anyone give me hints on how to start about solving this problem…..

Re: Challenge "Not-so-secret message from Malawi – Part I"  

  By: be on March 8, 2011, 4:49 a.m.

Can anyone give me hints on how to start about solving this problem…..

Hello,

For RSA the two primes p and q are used to build the semi-prime n.
One requirement for the two primes p and q is that these primes should be of equal size but not TOO close together. If so, special methods can be applied for factorization…
Does this help?

Where do you come from? How did you get information about this cipher challenge?

Best regards.

Re: Challenge "Not-so-secret message from Malawi – Part I"  

  By: -=Aloras=- on March 30, 2011, 11:58 p.m.

Is there anny way to avoid a Quadratic sive ?

My first Idea is maby N has a small primefactor

I tried to look for a Prime divisor without a remainder I tested the first 15.000.000 Prime Numbers I used a CAS (Mathematica)

is my idea right ?

Re: Challenge "Not-so-secret message from Malawi – Part I"  

  By: be on March 31, 2011, 7:11 p.m.

Is there any way to avoid a Quadratic sieve ?

What do you mean with this question?

My first idea is maybe N has a small prime factor. Is my idea right ?

Using one of the two factors as a small number would be very bad and this is not the case here. But look in the other direction, it could also a bad implementation if it allows that the two factors are too close to each other.

Re: Challenge "Not-so-secret message from Malawi – Part I"  

  By: -=Aloras=- on April 16, 2011, 8:49 p.m.

I played a littel bit with some Prime numbers and found this as closer p and q get to each other as closer one of the factors ist near by the root of N ist this a normal behaviour or is this a coincidence?

Am I on the right way ?
I tried looking for a Faktor near the root but I didnot found one was my calculation period to short?

Re: Challenge "Not-so-secret message from Malawi – Part I"  

  By: be on April 17, 2011, 11:47 p.m.

… and found: As closer p and q get to each other as closer one of the factors ist near by the root of N. Is this a normal behaviour or is this a coincidence?

Yes this is normal. (Even if root of N is an integer and even if this integer is a prime, it cannot be used for RSA as the 2 factors must be different.)

Am I on the right way ?
I tried looking for a faktor near the root but I did not found one. Was my calculation period to short?

You are on the right way. Please enhance the interval around root of N and look for the primes in it.

Hooray!  

  By: smai on April 20, 2011, 10:43 a.m.

Wow. I tried the naive approach first, well not-so-naive as I was not starting with 2 and 3, but the other way round. Still that would take years to solve. But better mathematics led me to a method which, even on my old notebook, solved the problem in about 10 seconds (written in C with the gmp library). Finding the method and implementing it, however, took substantially longer than 10 seconds [HTML_REMOVED]

Thank you for this challenge!

Re: Challenge "Not-so-secret message from Malawi – Part I"  

  By: -=Aloras=- on April 27, 2011, 11:14 p.m.

I found Fermats Factorizing algorithem Wich should be eficcent for P and Q if they are the same size I Tested my Software with small N and it worked . But the test if a number is a Square takes extrem long. I ignore all cases were my Number ends with 2,3,7 or 8 because this numbers cant be a square for any other number I start calculating the root . But this Operation seems to be very slow what are fast ways to calculate a root of a BigInteger

Re: Challenge "Not-so-secret message from Malawi – Part I"  

  By: be on April 29, 2011, midnight

As you solved it in the mean time. Could you pls give a short hint, how you managed to do so.

Re: Challenge "Not-so-Secret Message from Malawi – Part I"  

  By: DarkFibre on July 22, 2011, 8:30 p.m.

I'm very interested in how someone solved this in ten seconds. I've been running Fermat's method for 13 or so hours and no answer yet. Maybe I overlooked some bugs?

Re: Challenge "Not-so-Secret Message from Malawi – Part I"  

  By: fretty on July 22, 2011, 8:38 p.m.

I did this too, the "closeness" of the two primes is definitely not within 10 million. I got maple to do a backward search.

I ran fermat with different multipliers (upto 10) and let the computer search 1000000 or so possibilities each time. Still I got nowhere.

Re: Challenge "Not-so-Secret Message from Malawi – Part I"  

  By: DarkFibre on July 26, 2011, 12:57 a.m.

Ummmmmmmmmmmmm… I didn't bother with running any of those checks mentioned in the additional files because hey, it's just a cut and paste, what could possibly go wrong?

n cut and paste from file,
N cut and paste from PDF:
n=316033277426326097045474758505704980910037958719395560565571239100878192955228495343184968305477308460190076404967552110644822298179716669689426595435572597197633507818204621591917460417859294285475630901332588545477552125047019022149746524843545923758425353103063134585375275638257720039414711534847429265419
N=3160332774263260970454747585057049809100379587193955605655712391008781929552284953431849683054773084601900764049675521106448222817971666968942659543557259719763350781820462159191746041785929428547563090133258854547755212504701902214974652484354592375842553103063134585375275638257720039414711534847429265419

Notice the latter is 2 digits shorter. One goes …2229817… the other …222817… and is missing a digit somewhere else. Same for ct. Yet the number is written correctly in the PDF, it just cuts and pastes wrong?!?!? (Using Adobe inside Firefox)

Anyway, giving this one another shot, this time with the correct N.

Re: Challenge "Not-so-Secret Message from Malawi – Part I"  

  By: fretty on July 26, 2011, 11:18 a.m.

Well all along I have been using the bottom N.

Re: Challenge "Not-so-Secret Message from Malawi – Part I"  

  By: DarkFibre on July 26, 2011, 4:47 p.m.

The top, longer N is the correct one.


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