Cryptography Reference
In-Depth Information
Chapter 2
Number Theoretical Ciphers
In recent years, many cryptographic algorithms have been based on mathematical structures designed to hide in-
formation: Information is very easy to obscure if you know the correct trick. This trick is knowing the scheme
and a key of some sort, as is the case for the previously studied simple ciphers.
All ciphers are based on tricks: Those in Chapter 1 were more mechanical in nature. A person or computer can
perform the encryption and decryption by using a table or a very simple algorithm, and translating the result. This
chapter introduces cryptographic algorithms in which the encryption and decryption algorithms are very math-
ematical, using recent advances in number theory and algebra to make finding the information difficult.
Thisisnotamathematics topic,butitisnecessarytoknowalittle bitaboutmathematics inordertounderstand
some of these ciphers. Regardless, I do not want to drown you with math notation or obscure notions. This ex-
planation is not exhaustive (or formal), but it should eliminate any reader confusion about the subject.
I am also torn between two desires: the desire to explain everything, but also the desire to not lose the reader
in details and in lots of tedious mathematics. I will try to explain everything necessary in as simple terms as pos-
sible, but I will understand if you gloss over some of the mathematics and get straight to the juicy stuff. Just know
that the math is there if you want or need to read it, although for more comprehensive looks into these topics, you
will need to look elsewhere (such as in some of the topics in the references).
2.1 Probability
This section constitutes a quick review of definitions and a few principles of probability, which most likely will
be review or just plain common sense.
We normally define the
probability
of an occurrence as being the likelihood that it happens, on a scale of 0
to 1: 0 meaning that it never happens, and 1 meaning that it always happens. Furthermore, if we have some set
of occurrences, say X, then the sum of the probabilities of each of the occurrences happening has to be 1, since
something
must
happen. We can define situations to be more complex, where several things can happen at once,
but it is best to consider a more basic set of occurrences and build more complicated events out of it. Because
we want only one occurrence to happen at a time, we want each particular occurrent at this level to be mutually
exclusive.
For example, if we flip a standard, two-sided coin, we have a set of two events that could happen, {heads,
tails}. We denote the probability with a capital letter P. When we flip a
fair
(ideal) coin, we have an equal prob-
ability of either side facing up after flipping it, so that
P
(heads) = 0.5 and
P
(tails) = 0.5, and their sum is 1.
The fact that the probability has to be between 0 and 1 is also convenient, because we can calculate a negative
probability as well. If we have a standard deck of 52 cards, then the probability of drawing the jack of diamonds
is 1/52. The probability of drawing anything but the jack of diamonds is therefore 1 − (1/52) = 51/52.
Search WWH ::
Custom Search