After implementing and playing around with famous "Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standard PKCS #1" there couple of questions which I can't really grasp.
- Why do we get intervals with their ends interchanged?
- Why does it work to discard intervals in pairs?
Intervals Ends
I looked at several other implementation in different programming languages, and it's common to have a check that new interval beginning is actually less than its finish.
It's hard for me to explain appearance of this "interchanged" intervals by wrapping around modulus. But no good ideas comes to my mind to help.
Could you explain this effect?
Discarding Whole Interval
My initial intuition after reading the article was that every new interval should move a boundary (if it can), narrowing the tracking interval. So if new interval overlap with our tracking, then we continue to track overlapping part of them. But actual solution turned out to be more straightforward to discard whole interval which isn't inside the one we track (so that both ends of new interval are inside the one we track).
Does there always* exist $r$ which gives interval of length 1? Does it depends of r increment/increase, so that it's possible not to try all r, but predict what values of it would probably five this interval of length 1? And of course, why is it so?
(*) -- or most of the time, as I didn't really check or prove finding $m_0$ 100% of times, but overall it works well.
PS
Please hint me, if I should create two separate pages for each of my two questions regarding this topic.
