[math-fun] RSA as (bad) secret key cryptosystem (continued...)

...

Gareth McC: Second, the way I had in mind to search for M depended on fact that if message (as integer) exceeds M, then modding by M would lose information. So this must be forbidden. Hence by binary search to see what is forbidden an attacker with black box access to crypto box could determine M.

If this were (1) a problem and (2) the only problem, it would be easy to deal with. Just pick some m smaller than M but not too much smaller, and use that instead of M as the bound.

--no, you cannot do that, because then the encryptions would exceed m, so the decryptor box would have to accept messages above m, so the binary search for M could be undertaken with that box.