# What course sequence should I study in order to build a foundation for studying cryptography and signal processing?

I studied mathematics about two decades ago, but unfortunately, I remember little of it. I'm hoping to start studying cryptography and signal processing, but I'm not entirely sure what course/self-study sequence to follow. My initial ideas are something along these lines:

1. Number theory
2. Linear algebra and multivariable calculus
3. Abstract algebra and probably some coding theory
4. Analysis, both real and complex
5. ...

Given how little I remember, I'm not sure how much overlap I might be missing. For example, I know that coding theory utilises quite a bit of group theory, but I don't quite know the extent of the overlap.

-
I think you'll want to toss in some probability theory too. And analysis may be useful overall, but I would not say it is particularly useful in cryptography or signal processing. – TMM Feb 7 '13 at 20:11
@TMM Good to know. I vaguely remembered reading that the study of elliptic curves was useful in cryptography, and that it relied on complex analysis somewhat. – Ricardo Altamirano Feb 7 '13 at 20:27
I'm not an expert on elliptic-curve cryptography, so maybe you are right. But "cryptography" is still quite broad, and you can build all the cryptographic primitives you need (efficiently) without ever using elliptic curves. So in that sense, the real question is: Do you want to study elliptic curves and complex analysis? – TMM Feb 7 '13 at 20:40

For cryptography, you need some math courses in number theory and abstract algebra, but it sounds like you know about those.

We have three main cartographic ciphers in the form of symmetric ciphers (algorithmic based like the Advanced Encryption Standard - AES), asymmetric ciphers and stream ciphers.

Asymmetric ciphers are based on 'trap-door' mathematical functions that use the integer factorization problem (like RSA), discrete log problem (like Diffie-Hellman) or elliptic curve discrete log problem (elliptic curve crypto).

Cryptography Books

• A Course in Number Theory and Cryptography, Neal Koblitz

• Algebraic Aspects of Cryptography, Neal Koblitz

• Elliptic Curves: Number Theory and Cryptography, Second Edition (Discrete Mathematics and Its Applications), Lawrence C. Washington

• The mathematics of ciphers: number theory and RSA cryptography, Coutinho S C, Severino Collier Coutinho

• An Introduction to Cryptography, Richard A. Mollin

• Introduction to Cryptography with Coding Theory (2nd Edition) by Wade Trappe and Lawrence C. Washington (Jul 25, 2005)

• Handbook of Applied Crytography, Alfred Menezes, Paul van Oorschot, Scott Vanstone

• Guide to Elliptic Curve Cryptography, Darrel Hankerson, Alfred Menezes, and Scott Vanstone

• Practical Cryptography, Niels Ferguson, Bruce Schneier

Also note that there is also the field of cryptanalysis, which is more statistically and probability theory focused.

You might want to peruse the MIT Open Courseware on Crypto for further guidance on courses and areas to brush up on.

Here are some notes and here is another set of notes (and you can find other very good mathematically based ones online too).

Here is a list of topical areas that involve crypto to get an idea of scope.

For cryptanalysis read these from an expert.

That should be enough to help guide you forward and to help you figure out what courses you need.

Regards

-
I see cryptography and cryptanalysis and inextricably linked, so I would probably include the latter in my efforts as well (perhaps after I've covered significant quantities of material in cryptography). – Ricardo Altamirano Feb 7 '13 at 22:20
Nice work, Amzoti! You could be a "subject librarian" for math.se! – amWhy May 4 '13 at 0:22
@amWhy: There is so much I can and cannot say about this topic on the site! :-) – Amzoti May 4 '13 at 0:32

I also picked up cryptography as a hobby and took a few introductory courses and then just studied by myself. You are of course right about abstract algebra but just want to emphasize that an intro to abstract algebra won't be enough. You'll need to get a bit deeper into field theory so if somebody says to add two numbers in $\mathbb{F}_{2048}$ you would know how to do that. Finite fields (especially of characteristic two) and then finite vector spaces built on top of them are ubiquitous in cryptography. And these don't behave like real or complex vector spaces at all. You also want to pick up some probability. Of course, depending on if you want to study just theory or actual implementations and why is AES the way it is and what is differential cryptanalysis then some comp sci background will also help.

For signal processing, are talking about just fourier analysis or any thing "modern" that's out there (like wavelets)? For that real and complex analysis will help. Intro to PDEs will be useful too learning about fourier series and fourier transforms. And then the most useful thing will be a really really good numerical analysis sequence. First start with the basics of fourier transform, then the discrete fourier transform, and then understanding what is fast fourier transform. And then whatever additional techniques you want to learn like radial basis functions and/or wavelets.

-