MIT 6.857 Computer and Network Security Class Notes
1
File: http://theory.lcs.mit.edu/˜rivest/notes/notes.pdf
Revision: December 2, 2002
Computer and Network Security
MIT 6.857 Class Notes
by Ronald L. Rivest
December 2, 2002
1Copyright c© 2002 Ronald L. Rivest. All rights reserved. May be freely reproduced for educational or personal use.
MIT 6.857 Computer and Network Security Class Notes
2
File: http://theory.lcs.mit.edu/˜rivest/notes/ntintro.pdf
Revision: December 2, 2002
Introduction to Number Theory
Elementary number theory provides a rich set of tools for the implementation of cryptographic schemes.
Most public-key cryptosystems are based in one way or another on number-theoretic ideas.
The next pages provide a brief introduction to some basic principles of elementary number theory.
1Copyright c© 2002 Ronald L. Rivest. All rights reserved. May be freely reproduced for educational or personal use.
MIT 6.857 Computer and Network Security Class Notes
3
File: http://theory.lcs.mit.edu/˜rivest/notes/bignum.pdf
Revision: December 2, 2002
Bignum computations
Many cryptographic schemes, such as RSA, work with large integers, also known as “bignums” or “multi-
precision integers.” Here “large” may mean 160–4096 bits (49–1233 decimal digits), with 1024-bit integers
(308 decimal digits) typical. We briefly overview of some implementation issues and possibilities.
When RSA was invented, efficiently implementing it was a problem. Today, standard desktop CPU’s perform
bignum computations quickly. Still, for servers doing hundreds of SSL connections per second, a hardware
assist may be needed, such as the SSL accelerators produced by nCipher www.ncipher.com/.
A popular C/C++ software subroutine library supporting multi-precision operations is GMP (GNU Multi-
precision package) www.swox.com/gmp/. A more elaborate package (based on GMP) is Shoup’s NTL
(Number Theory Library) www.shoup.net/ntl/. For a survey, see
https://www.cosic.esat.kuleuven.ac.be/nessie/call/mplibs.html.
Java
has
excellent
support
for
multiprecision
ope