Cryptography Reference
In-Depth Information
In this appendix we look at the basic mathematical concepts that underlie some
of the material in the topic. We stress that study of this appendix is
not required
in order to read this topic. The explanation of these ideas assumes little or no prior
knowledge.
The topics covered in this appendix are:
• Decimal, binary and hex;
• XOR;
• Modular arithmetic;
• Primes, coprimes and greatest common divisors;
• Modular inverses;
• Why RSA works;
• Primitive elements;
• Why ElGamal works.
Everyone is familiar with
decimal numbers
. These are the numbers that we use
every day and are the numbers that we normally write and perform calculations
with. Representing numbers in decimal is just one possible way of writing a
number. There are many other ways of writing a number (for example, Roman
numbers and Chinese characters). This section introduces two other ways of
writing numbers:
binary
and
hex
. Binary and hex are particularly useful in digital
communication. In fact, at the most fundamental level, binary numbers are the
basis of all computing.
In this section we make extensive use of the notation for exponentiation, as
discussed in Section 1.6.1. For example, if we write 10
7
(10 to the power 7) then
we mean 10 multiplied by itself seven times:
10
7
=
10
×
10
×
10
×
10
×
10
×
10
×
10
.
Note that it is standard mathematical convention to say that any number raised
to the power 0 is 1. Thus, for example, 10
0
=
1.
