Official quick maffs Discussion

Official discussion thread for quick maffs. Please do not post any spoilers or big hints.

Wow no blood so far, crazy

Yeah if anyone has any advice, feel free to send it my way. I have been looking at common modulus attacks and a bunch of different stuff for a while now… Would love a nudge. I suppose that means someone else needs to solve it first though…

As always, I’m sure it’ll be obvious in hindsight, but for an “easy” challenge, this seems far less straightforward than the last two RSA challenges (Lost Modulus and Lost Modulus Again). Given that I can’t find any obvious weakness in the modulus, my current leads are:

1. The public exponent, e, is one of the 172 prime numbers under 1024 (2^10).
2. The hint confirms that the three plaintexts are all 231 bits in length or less (i.e. the messages are either not padded, or not padded properly).

I did wonder whether either of the numbers in the challenge text may have some relevance (i.e. “there have to be 4529837459872034759 different equations and 347293475923709458 different fields”) but I can’t see anything obvious, and they have a few repeating digits, and no 1s or 6s, suggesting it was just someone hammering out a long number on the keyboard.

I’ve also been exploring various attacks on small public exponents, and unpadded messages, but nothing working so far…

Oof, finally got it! Some very general hints:

• Definitely not an easy challenge, though it only took about a dozen lines of Sage code to solve once I found the correct attack in an old paper.
• Even if the public exponent were given this would be a cool problem.
• So nobody goes down this rabbit hole: The numbers in the challenge text had nothing to do with the solution, at least the way I did it.

Feel free to DM me with what you’ve tried and I’ll see if I can steer you in the right direction.

Same struggle here @onetimepad ! For a moment I saw light thinking that “pure numbers” were “perfect numbers” but I found none, even in the description.

Made a little progress by decomposing the hint in base 256: this may help to guess letters & length of the strings, but nothing 100%.

If anyone ends up at the same point I did, where you have a working method to solve this in Sage, but it takes too long to test values of e larger than 13 or so, be aware that Sage has an internal implementation of the relevant technique that runs much more quickly than doing it yourself manually. You’ll know what this is called if you actually read the relevant research more closely than I did! Thank you @coletree!

I recommend doing the medium “Lost modulus again” before this easy chall hahaha

Also thanks to @coletree for saving me from those unending computations

While it’s true that for e>13 it is quite slow, the naive method is not terribly slow, and the correct value of e can be bruteforced in like 10 minutes or so… it’s too weak.

I am also pretty stuck atm. Would appreciate it if anyone can pm me

This is a “find the paper” crypto challenge (that’s often used derisively, but I think it provides a great opportunity to increase a skill you’ll need if you want to get better at crypto and that’s reading math papers)…so basically, look at what attacks sort of seem like they might be related, then go dig up the original papers and read them. When you find the right one, it will show how to solve the exact setup from this problem

Now I can’t find the paper after 6 months I only know that it’s a scanned document
what a hard lesson on keeping notes well

EDIT: found again. Here are some hints and confirmations for finding the paper.

• @Hilbert 's comment is really helpful, so think about the keywords before you search!
• @coletree 's is right about that it’s an old paper - really old, I’m not sure if applying date restriction in search engine can help though.

EDIT 2: found e and solved. @onetimepad is right.

back to this problem after over a year and the idea just strikes through. finally find the right paper.

hint for those also stuck on this one: the paper is not necessary.
try reduce the size of the problem. looks familiar now? yeah a famous RSA problem (investigate the wiki is enough). extend the solution for this one.