Cryptography Reference
In-Depth Information
since g ϕ( m ) ≡ 1 (mod m ).
After we get through a bit more algebra, we will see how we can use the Euler totient theorem and its corol-
laries for cryptography.
2.3 Algebra Refresher Course
“Algebra? Why study algebra in a topic about cryptanalysis? Let's just break some codes already!” the reader
might exclaim. And a very valid set of concerns this is.
In the preceding section, we did a quick refresher on number theory and probability, and it seems natural
to express most of the operations in cryptography and cryptanalysis based on them. After all, we know how to
do arithmetic and other operations on numbers, and computers are constructed for working well with integers
represented in binary.
It turns out, however, that many important mathematical properties of cryptography and cryptanalysis are
based on algebraic concepts. Furthermore, many modern cryptographic algorithms are based on algebraic con-
structs, such as elliptic curves, that are not easy to manipulate using normal kinds of mathematical operations.
Even understanding some of these algorithms requires at least some knowledge of algebra, and attempting
to break them even more so! Furthermore, many algebraic techniques can be used to break cryptographic al-
gorithms based on numbers too. Hence, familiarity with algebra is important to cryptanalysis.
Again, however, this is not a math textbook; if the reader wishes to understand the subject of algebra more
deeply, then he or she should consult a more thorough source than this. Here, we provide a crash course in al-
gebra to help refresh your knowledge, or at least provide enough of an understanding that you can attempt to
understand the methods of cryptography presented in this chapter.
2.3.1 Definitions
The study of collections of objects and operations on those objects is called algebra . In algebra, these opera-
tions are constructs that take as input two objects and return an object, usually (but not always) with all three
objects belonging to the collection with which we are concerned. These operations are examples of functions,
which formally means that there has to be an output for every possible input, and there can be only one output
for every input (so you can't run the function twice with the same input and get different outputs). For example,
a simple function from the integers to the integers is f ( x ) = x 2 , so that = f (1), f (2) = 4, f (3) = 9, and so forth.
Note that every integer has a square, and that you can't square the same integer twice and get different results,
therefore this is definitely a function.
In general, we often denote these collections of objects, or sets , that we are operating on with capital letters,
such as A, F, or G, with the operations being symbols such as , +, or ×, although this is merely convention. A
set is normally written with curly braces around the objects contained in it. For example, A = {0, 1, 2} is a set
containing three objects: the numbers 0,1, and 2. The objects need not be numbers: B = {cat, dog, 18, } is a
set containing much more arbitrary objects, but it is still a set.
We also often want more compact and unambiguous ways of writing operations so that everyone is on the
same page. We write an operation often as
Search WWH ::




Custom Search