Trusted SF Member
Joined: 17 Apr 2003
Location: Asheville, NC, US / Uberlāndia, MG, Brazil
|Posted: Tue Dec 30, 2003 9:10 am Post subject: Conventional Algorithm Analysis Prerequisites: A Breakdown
As promised, here is a breakdown of certain mathematical levels that will aid one in familiarizing themselves with the inner workings of basic cryptographic concepts.
Please note that I am focusing on specific mathematical concepts, as applied directly to specific problems within cryptography. With this in mind, the mathematical-to-cryptography relations are by no means limited to this presentation. On that note, here goes it.
Understanding cryptography is understanding analysis. Why? Because those who designed the cryptography we use today are those who first mastered the art of analytical value - the discerning of security and insecurity, if you will.
First of all, to understand the basic analysis of block ciphers, you will need a general understanding of statistics and probability. These two mathematical studies fit hand-in-hand, as the former deals with the sampling and hypothesis of the latter, to be general.
I have found the study of discrete mathematics to be rather useful as well, although you can do without heavy concentration on the like, for the moment.
Now, to grasp the essentials, I will focus primarily on the analysis of conventional block ciphers. First, and foremost, you need a solid background in linear algebra. This will open up the door for several algebraic subsidiaries, such as:
o Lattice Theory
o Et cetera
Along with these different areas comes the basic foundations for combination functions, such as Exclusive OR (XOR) and modular arithmetic. Although you may encounter these areas in other branches of mathematics, such as Calculus, I find their algebraic roots to be much more important, in regards to cryptographic application.
Moving right along, you should familiarize yourself with four different theories, with strong ties to algebraic and discrete mathematics. These four theories include:
o Complexity Theory
o Group Theory
o Field Theory
o Graph Theory
Complexity theory deals basically with the difficulty of solving a given problem. There are generally three classes of problems that one can associate with complexity: P, NP, and NP-complete. P, or polynomial, time is used to classify a situation in which a problem's complexity, or number of operations required to solve, is determined by a power of its overall size. Similarly, an NP, or nondeterministic polynomial time, problem is one exhibiting the above trait, but also allows for nondeterministic solutions. The former can be described as a subsidiary of the latter. Finally, we come to the last class - NP-complete, or nondeterministic polynomial-complete time. This class is extended to a situation where an algorithmic solution to one NP problem can be adapted for any other NP problem.
Group theory is basically an analytical study of systems, physical or abstract, that portray symmetry. This can be extended to other familiar cryptographically-related areas, such as finite, or Galois, groups. Galois is attributed as the father of this theory.
Field theory introduces a very important concept, of which you will encounter throughout a great bulk of cryptography - finite, or Galois, fields. This type of field is simply one with a field order (finite; count of elements), where the field is a prime or power of such. Galois theory can be used to draw correlations between group and field theory.
Graph theory, simply enough, is the study of graphs, which can be loosely defined as a compilation of points and lines, with sets connected in some manner.
To complete the required background knowledge one should know, before they attempt diving into the pond of crypto-guts, let's briefly define a branch of discrete mathematics we call combinatorics. As one would gather from its name, it does pertain to combinations, as well as permutations and enumerations. This is performed on elemental sets, alongside the corresponding characteristics which form mathematical relationships.
To grasp the above is to be comfortable with what makes a block cipher tick. In other words, you should be able to walk through a cipher, step by step, in regards to the security, or insecurity, a particular component provides.
The cryptanalytical approach is also heavily determined by the structure of a block cipher. Two commonly used structures include Feistel Networks and Substitution-Permutation Networks. I'll save these for another article, though.
Cryptanalysis is a game of experience. You must learn to apply an attack, in practical implementation, before you can truly understand how the theory works. You can read all you like, but it's not until you tackle it head on, that you understand. The reason I chose to discuss cryptanalytical prerequisites on block ciphers is because of the dire importance in being familiar with conventional algorithms, which form the bulk of cryptography as we deploy it, in today's modern computing scene.
Many of these same concepts apply to stream cipher design as well, however, you may want to take a look at this thread, as I explain the intricacies of stream-cipher-specific design methodologies, more so.
Also, this presentation is aimed generally towards symmetric block ciphers, which are of the most conventional importance, when it comes to actual data encryption. Later on, I will elaborate on the corresponding mathematics of asymmetric systems, and how they are used in conjunction with symmetric systems, to form hybrid cryptosystems.
Work calls, so that sums it up for now. Feel free to criticize/comment, as feedback is good. In the meanwhile, enjoy and keep in check, as I will add more material soon.