Cryptography 101

[Robert J. Hansen]

(For non-US readers: in the United States university system, classes 
have departments, names, and numbers. In any department, the 101 class 
is almost always "Introduction to...". Hence, Computer Science 101 is 
Introduction to Computer Science, and Cryptography 101 would be...)

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.


-------------- next part --------------
A non-text attachment was scrubbed...
Name: OpenPGP_signature.asc
Type: application/pgp-signature
Size: 236 bytes
Desc: OpenPGP digital signature
URL: <https://lists.gnupg.org/pipermail/gnupg-users/attachments/20251019/afd3288d/attachment.sig>