I've said a lot recently about how important it is to be able to ask basic questions about whether a cipher forms a mathematical group. I figure people might benefit from hearing a little bit about it.
Group theory is to mathematics what Perl scripting is to system administration: it doesn't get much respect but knowing it is an essential, non-negotiable skill purely because of how much it glues the whole system together.
Put broadly, group theory is the study of absolutely anything that has these properties: well-defined inputs and outputs taken from the same set, and a function that obeys the associative property and can be used to do identities and inverses.
For instance, do the integers form a group under addition?
* Inputs: and outputs are from the same set? Yes, integers!
* Can addition do identities? Yes, add zero!
* Can addition invert itself? Yes, add a negative!
* Does addition associate? Yes!
Therefore, we would say the integers form a group under addition, and
that means anything involving adding two integers together can be
studied with group theory.
Hmm.
Do Rubik's cubes form groups under rotations?
* Inputs and outputs are from the same set? Yes, cube configs!
* Can you rotate a face such that the cube doesn't change? Yes!
* Can rotations invert themselves? Yes, twist it the other way!
* Do cubes associate? Yes! (higher math proof omitted)
So wait, we've got a single coherent mathematical theory that describes
not just numbers like arithmetic, but big complicated objects like
Rubik's cubes.
When considering a mathematical concept, one of the very first things mathematicians -- and every cryptographer is a mathematician -- ask is, "does this thing form a group?" Because if so, wow, you can do the mathematical equivalent of running off to look at CPAN to see all the stuff people have *already proved about your problem* just by nature of the fact it's a group.
The moment you say "oh, it's a group," you have something like 3,500 major results in mathematics pre-proven for your problem. Answer four questions, get 3,500 theorems about your problem. That is *breathtaking* power.
For instance, with respect to layering ciphers: there's a theorem which says "if your cipher is a group, nope, you're fooling yourself." You can prove ROT is a group (go ahead: try to prove it yourself!), so we know layering is ineffective.
=====Another good reason to study group theory: it is the foundation of RSA, Diffie-Hellman, DSA, and Elgamal, including elliptical curve variants. All of those algorithms are based on the "hidden subgroup problem", which, as you might guess from the name, is a part of group theory best described with tools from group theory.
=====If you're interested, MIT makes their entire abstract algebra curriculum ("abstract algebra" being the branch of math that contains group theory) available via their Open CourseWare site:
https://ocw.mit.edu/courses/18-703-modern-algebra-spring-2013/pages/lecture-notes/It will be hard. It will challenge you. But if you can understand the basics of group theory, you will have in your mathematical repertoire the equivalent of Perl and a copy of the Camel book. It is powerful, it is useful, and it's there for the taking.
OpenPGP_signature.asc
Description: OpenPGP digital signature
_______________________________________________ Gnupg-users mailing list [email protected] https://lists.gnupg.org/mailman/listinfo/gnupg-users
