Material related to the lectures on network security.
Most Wikipedia articles on network security related topics are as good or better and more current than the treatment in the textbook Computer Networking.
In the fourth edition it's on page 696.
There is correct proofs for RSA on Wikipedia: http://en.wikipedia.org/wiki/Rsa and in Handbook of Applied Cryptography, Section 8.2.1.
From: Christian Boesgaard [mailto:pink@diku.dk]
Sent: Wednesday, October 11, 2006 3:46 PM
To: ross@poly.edu
Subject: errata for Computer Networking, third edition
I think your proof for RSA on page 669 is wrong as you use a result
that does not cover all cases. You use the result:
If p and q are primes and n=pq, then
x^y mod n == x^( y mod ((p-1) (q-1)) ) mod n
But this does not hold in general, for example the case where x=2,
y=4, p=3, q=3:
2^4 mod 9 = 7, but
2^(4 mod (2 * 2)) mod 9 = 1
So the RSA proof does not hold in general.
I think the result you want is the following corrolar to Eulers theorem:
If p and q are primes and n=pq, then
x^(1 mod ((p-1) (q-1))) mod n == x mod n