Forum

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

  By: Veselovský on Aug. 13, 2011, 6:18 p.m.

hmmm… I am wondering where I made a mistake, because my program works perfectly with smaller numbers but can not find factors of n from the challenge.

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

  By: Veselovský on Aug. 13, 2011, 9:11 p.m.

Now I see where the problem was… and probably all people there who can not solve this have the same problem…
Sometimes even a good meant advise (hint) can confuse people if it is understood literally and people do not think about what it really could mean

Someone here said that primes are not too far from each other… so people start to think that difference of p-q (or p-sqrt(n)) is small, but that is not the case, in fact the distance of primes is quite big.
So if your method was to check every prime above Floor(sqrt(n))+1 whether it divides n then it can take billions of years (my guess) to find the answer…

What was meant by the hint is that primes are near each other enough that it is easy to find them with some efficient method… in this case Fermat's factorization method
So just apply simple Fermat's factorization method and the result is guaranteed

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

  By: Veselovský on Aug. 14, 2011, 11:06 a.m.

DarkFibre,
my last post has helped, hasn't it? :-D ;-)

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

  By: fretty on Aug. 14, 2011, 12:13 p.m.

No, DarkFibre had already implemented Fermat factorization and had run it for 2.5 weeks.

I PM'ed him and told him where our programs were failing (basically in the square root stage) and once rectified he got a solve.

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

  By: h3po on Aug. 21, 2011, 8:47 p.m.

interesting thing, i had yafu x64 (a highly optimized toolkit for prime testing and factorization, as i'm told) running on n while i implemented fermat factorization (and struggled with my sqare-multiply) in python.
after one hour runtime, yafu hasn't found the primes while python did it in 0.6 seconds.
so, the upshot, as many times before: don't bother trying to apply real-world problem solvers to crypto challenges which are weakend by design ^^

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

  By: DarkFibre on Aug. 23, 2011, 6:19 p.m.

I don't know exactly where my program was going wrong, but I removed all optimizations and then it worked. Maybe some vars weren't staying as GMP? Maybe the optimizations change things? It worked with little numbers and medium numbers just fine.

The not knowing is making me paranoid in other challenges…

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

  By: aurelie on Aug. 26, 2011, 4:30 p.m.

Since there seem to have been some digits in the pdfs that simply went missing, please use the additional file for the right values of N and CT.

I updated the slights but it might take some time until the corrected version is finally only.

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

  By: Dano on Oct. 3, 2011, 12:37 a.m.

thanks for hint with "Fermat's factorization method" :)

mfg Dano

Fermat works well, but...  

  By: cfreuden on Jan. 15, 2016, 3:05 p.m.

I had no problems finding the factors for N but I am stuck anyway.

N is 300+ digit figure, my solutions for p and q are 150+ digit figures - so far so good.
Given that the public key e is given (e=17) it should be straight forward to calculate d now using "standard RSA math".
I don't know if I should mention the alogrithm to do so here but my solution is again a 300+ digit figure.

Now in order to get the plain text I should calculate the power of a 300+ digit figure (ct) with a 300+ digit figure (d) - which would be a 90000 digit figure…

Any suggestions what I am doing wrong?

Re: Fermat works well, but...  

  By: Bart13 on Jan. 15, 2016, 3:32 p.m.

It's a while since I solved this challenge so I'm not quite sure, but I think this is your problem:
To get the plaintext it is not ct^d but ct^d mod N

I hope this helps.

Re: Fermat works well, but...  

  By: cfreuden on Jan. 15, 2016, 7:14 p.m.

It's a while since I solved this challenge so I'm not quite sure, but I think this is your problem:
To get the plaintext it is not ct^d but ct^d mod N

I hope this helps.

Yes, I am aware of that. Would that transform to
ct*d mod N = (ct mod N) * (d mod N) ?

Re: Challenge  

  By: cfreuden on Jan. 18, 2016, 2:29 p.m.

ok finally got it - Modular exponentiation is key here, should have just read the docu on the python pow() function… ;-)

Re: Challenge  

  By: yult on July 12, 2019, 8:03 p.m.

At first, I implemented the factorisation myself in python using sage but I got modulo error. I was unsure what causes this so I copied a more efficient factorisation code from github and I got the primes.

It turns out that I have already found the primes using my code. But since I mixed every part of code, I didn't see it.

This sentence should be ignored "(this should be the same as dividing by 2^200 and finding the remainder)". This is because it modulo 2^200 is too big for sage. Directly cutting it is a more sensible way of remove the padding.

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

  By: crown.mp18@gmail.com on Sept. 26, 2022, 3:45 a.m.

Hi,

I am trying to solve this challenge, but I am not able to access the parameters file linked at https://mysterytwister.org/images/challenges/mtc3-schaefer-01-rsa-parameters.txt in the PDF.

Can someone please help me with the parameters or point me in the right direction please?

Thanks.

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

  By: newton on Sept. 26, 2022, 10:17 a.m.

Thank you for notifying us about this issue.

While we fix the link, you can find the file here:

https://seafile.noc.ruhr-uni-bochum.de/f/e1a405fc61e74bf2bf69/?dl=1

Best, Newton


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