Cryptography Reference
In-Depth Information
2. Skip through the mathematics and just try to grasp the essence of what is going
on. This is a perfectly valid option, although the details of these public-key
cryptosystems will probably remain something of a 'fuzzy cloud'.
The main mathematical ideas that we will need are the following.
PRIMES
A
prime number
, which we will simply refer to as a
prime
, is a number for which
there are no numbers other than itself and 1 that divide into the number 'neatly'
(in other words, without a remainder). Such neatly dividing numbers are termed
factors
. For example, 17 is a prime since the only numbers that divide neatly into
17 are 1 and 17. On the other hand, 14 is
not
a prime since 2 and 7 both divide
neatly into, and are thus factors of, 14. There are an infinite quantity of primes,
with the smallest ten primes being 2, 3, 5, 7, 11, 13, 17, 19, 23 and 29. Primes
play a very important role in mathematics, and a particularly important role in
cryptography.
MODULAR ARITHMETIC
The public-key cryptoystems that we will describe do not operate directly on
binary strings. Instead they operate on
modular numbers
. There are only finitely
many different modular numbers, in contrast to the types of numbers that we
are most familiar with using.
Modular arithmetic
provides rules for conducting
familiar operations such as addition, subtraction and multiplication on these
modular numbers. The good news is that modular numbers, and modular
arithmetic, are concepts that most people are familiar with, even if they have
never described them in such terms. An introduction to modular numbers and
modular arithmetic is provided in the Mathematics Appendix.
SOME NOTATION
We will also introduce some simple notation. The important thing to remember
about notation is that it is just shorthand for words. We could replace any
mathematical equation with a sentence having the same meaning. However, the
resulting sentences often become cumbersome and awkward. Notation helps to
keep statements precise and clear.
Firstly, the symbol
×
is usually used tomean 'multiply'. Thus
a
×
b
is shorthand
for '
a
multiplied by
b
'. However, it will sometimes be convenient to write this
statement even more concisely. Thus we will sometimes drop the
×
symbol and
just write
ab
. Thus '
a
multiplied by
b
',
a
×
b
and
ab
all mean exactly the same
thing. If we write an equation
y
=
ab
then this means that 'the number
y
is equal
to the number
a
multiplied by the number
b
'.
Secondly, when we write two numbers in brackets, separated by a comma, then
this is just a convenient way of saying that these two numbers are to be regarded
as a 'package' and that we cannot have one without having the other. Thus if we
say that a key is (
a
,
b
) then all that this means is that the key is made up of the
