DiGuru said:
I think you guys lost most of us. Care to explain the above in a way we mere mortals can grasp it?
Abstract algebra is a field of math that attempts to "abstract" many of the facets of number systems and algebra to study the pure structure of these systems. I'm sure if you've done operator overloading in a programming language, you're familiar with the concept of creating new types and new operators to deal with them.
Abstract algebra starts off with the simplist structure called a Group, this branch of the theory called "Group Theory" (ok, there are simplest structures, like semigroups for the nitpickers)
A group consists of a set of elements (which may be infinite), an identity element (usually denoted 'e'), and a binary operation that takes two elements of the set and produces another element of the set. Associativity must hold, such as (a*b)*c=a*(b*c) and for each element a, there must exist an element b, such that a*b=e, that is, b is the inverse of a. You may more clearly see this as "a/b = 1" that is, a = 1/b if this were regular algebra.
Examples of groups are things like, the integers modulo prime p with multiplication as the operation. Or, say, the possible rotations of a square (0 degrees, 90 degrees, 180 degrees, 270 degrees, horizontal flip, verticle flip, and two diagonal flips).
For example, given element D_90, it's inverse is D_270, that is D_90 * D_270 = D_0 (identity element, 0 degree rotation) You can see that if you rotate a square by 90 degrees, and then by 270 degrees, it's the same as no rotation.
Now, given a group, we are generally interested in questions like: how many elements does it have? (called the order of the group) Does the commutative property hold (a*b=b*a)? How many subgroups does it have? What are the orders of the elements? (the order of an element a is the what is the smallest value n, such that a^n = e) What groups are isomorphic to this group? What are its homomorphisms, etc.
Sounds boring, but the study of groups led mathematicians to realize that many of what they thought were completely different systems were in fact, exactly the same with different syntax, or intimately related in surprising ways.
Next up in Ring Theory. A Ring is like a group, but has two binary operations (+,*) call them addition and multiplication if you wish. Addition is the same as in groups, but a Ring may or may not have a multiplicative identity (call it '1' or unity) whereas it MUST have an additive identity (call it '0'). Moreover, even if it has a multiplicative identity, each element need not have a multiplicative inverse.
For example, consider the integers modulo 4. 3 has an inverse (3*3 mod 4 = 1) but 2 does not (no x exists such that x * 2 = 1 mod 4). The integers modulo 4 form a ring with unity (has a '1') Rings have lots of interesting subdivisions, there are things called Ideals, Unique Factorization Domains, Principlal Ideal Domains, Integral Domains, Euclidean Domains, etc.
Leading up to the next step: Field Theory. A Field is a Ring with unity ('1') where every element MUST have an inverse. The integers modulo a prime is an example. The Rational Numbers are an integer. Etc. In fields, lots of fun surrounds something called Extension Fields.
Now, none of this would be interesting unless there were some pretty startling results. For example, there is something called a Simple Group and the Classification of the Simple Groups theorem (10,000 pages long proof! took 30 years of work by hundreds!) But, in the end, they classified every possible simple group (there are 4 main classes, and 26 sporadic groups, the largest of which is the Monster Group, lookup Monstrous Moonshine for some fun). What did they discover? A sort of "Periodic Table of the Elements" for all of algebra. Simply put, any group you can possibly think of, can be constructed via Simple Groups, like molecules are constructed by atoms. (A similar theorem exists for commutative groups. ANY group whose operation is commutative can be constructed as a product of cyclic groups of prime power order. For example, any group you design with 6 elements can be represented as the cartesian product of integers modulo 2 and integers modulo 3)
Now what does this have to do with cryptography? Depends on which kind of cryptography. Number Theory is a subset of algebra algebra, and many of the fundamental cryptographic primitives like public key cryptography, bit-commitment, oblivious transfer, key exchange, etc rely on properties of finite fields.
Take the RSA public key algorithm. We know from Fermat that x^(p-1) mod p = 1. For example, 2^6 mod 7 = 64 mod 7 = 1. Or 5 ^ 2 mod 3 = 25 mod 3 = 1. Euler extended this to x^phi(m) = 1 mod m. The phi function is defined as the number of elements e less than m such that gcd(e,m) = 1. For example, phi(6). The elements less than 6 are 1, 2, 3, 4, 5, and only 1 and 5 share no common divisors with 6, so phi(6) = 2.
Therefore, x^2 mod 6 should be equal to 1 (if gcd(x,6) == 1). Like 7^2 = 49 mod 6 and 11 ^ 2 = 121 mod 6 and 13^2 = 169 mod 6)
Now, here's the problem: Calculating phi(m) is *really really hard* unless you know the factors of m. If you know the factors of m=pq, then phi(m) = phi(p) * phi(q) and phi(x) where x is prime is just x-1. So returning to phi(6), we have phi(6)=phi(2)*phi(3) = (2-1)*(3-1) = 1*2 = 2 which agrees with our brute force calculation.
Now we have the necessary components for public key cryptography. Let M be our message.
M^phi(m) = 1 mod m
then of course
M^(phi(m) + 1) = M mod m
that is, M raised to this power, returns M
We also know that
phi(m) + 1 = e*d mod phi(m)
That is, given a carefully chosen element 'e' in the ring defined by integers mod phi(m), there must be a element 'd' that is the multiplicative inverse of e.
Let us call 'e' the encryption key, and 'd' the decryption key.
Now I encrypt a message to you. I take M and raise it to the 'e' power modulo m. C = M^e mod m. I send you C.
It is impossible for you to take the 'e'th root of M mod m.
Now, to decrypt, you simply take C^d mod m. Now let's proove this decrypts it.
C^d = (M^e)^d = M^(e*d) mod m.
If e*d = 1 mod phi(m) than by the definition of congruence, e*d = 1 + r*phi(m) for some integer r.
Therefore we have
M^(1 + r*phi(m))
or
M^1 * M^(r*phi(m))
or
M^1 * M^(phi(m)^r) mod m
but M^(phi(m)) = 1 mod m from Euler's theorem so this reduces to
M^1 * 1^r mod m
= M^1 = M
