What does Eve learn from eavesdropping on the communication between
Alice and Bob? She learns the number Alice is using as
AlicePart, and she learns the number Bob is using as BobPart.
In principle, therefore, she could determine the key. For example,
she could calculate the base 2 mod m logarithm of AlicePart,
which is A. She could then, like Alice, calculate
. The problem with this approach, of course, is
that it would take Eve too long to calculate A (unless she knows of
an exciting new algorithm for the modular logarithm problem) because
the modulus is so big. She
could similarly try to calculate Bob's secret number B, but this
would probably be just as difficult.
Is there no other approach for Eve? Might there be another way for her to calculate the key from AlicePart and BobPart? Well, we don't know--there might be, but no better approach is known.
Does it make you nervous, the idea of relying for your privacy on some computational problems being difficult to solve? It might be that solving these problems is inherently too difficult, that nobody will discover a good algorithm for these problems because none exists. Certainly there are computational problems for which we can mathematically prove there is no good algorithm. However, there have also been breakthroughs in algorithms research, discoveries of algorithms that people thought didn't exist.
It seems inevitable that cryptography will rely on the uncertain. It has been said that cryptographers seldom sleep soundly. However, you should keep in mind an important but somewhat difficult point. For a traditional cryptographic system (such as a typical one-key encryption scheme), the security rests on the difficulty of a much more complicated and messy computational problem. You might think this would make such a problem less likely to be solvable, but in fact the messiness may be concealing what is fundamentally an easy problem. Paradoxically, the mathematical simplicity and clarity of the modular logarithm problem should give you more confidence, because if there were a fundamental weakness it would be more obvious. Then again, you never know.