Datanet Resources

Material related to the lectures on network security.


Recommended reading

Short introductions:


Most Wikipedia articles on network security related topics are as good or better and more current than the treatment in the textbook Computer Networking.


Error in RSA proof in Computer Networking

In the fourth edition it's on page 696.

There is correct proofs for RSA on Wikipedia: and in Handbook of Applied Cryptography, Section 8.2.1.

From: Christian Boesgaard []
Sent: Wednesday, October 11, 2006 3:46 PM
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