Which are the most important Math skills in order to better understand cryptography?

Question

I need to have a better understanding of cryptography, specially the mathematics behind some of the core concepts.

However, my High School Maths knowledge has gone a bit blunt, and so I was wondering which topics I should revisit for this purpose?

Answer 1

I think discrete mathematics will be a very good friend in understanding some core concepts.

-- Oh sorry, I guess you are looking for "single subjects" ?

Well, then the lists gets a bit more comprehensive...: Primes, permuatations, matrix, equations, and so on... But you should really take on a course of Discrete mathematics to understand a bit more....

Answer 2

You might think about picking up the book 'Applied Cryptography' by Bruce Schneier. It covers the protocols, algorithms and includes some C source code.

You also might take a listen to 'Security Now' which is a podcast put on by Leo Leporte and Steve Gibson. Steve does a great job of explaining many crypto concepts and the associated math for non-mathematicians. You could start with episodes 30 through 37.

Here is the site for Security Now: https://www.grc.com/securitynow.htm

Answer 3

Discrete mathematics is definitely needed for cryptography, and there is no way around it.

off the top of my head, you won't get far without:

• Modular exponentiation
• primes (of course), and more specifically the difficulty of factoring a (large) number into its primes, actually it is one of the fundamental principles used for most asymmetric encryption schemes in use today.
• the understanding of what one-way-functions are (if they exist at all)
• the difference between symmetric and asymmetric key algorithms
• computational complexity (and it's big oh notation)

but really, most of these are directly related to discrete mathematics, so there is no way around (re)studying that.

Answer 4

The basic topic you're really looking at is number theory, which is also one of the more enjoyable kinds of math. Of course, I'm a crypto geek so I'd say that. You also need a good grounding in probability. Here are a few good books that have appropriate topics:

• Concrete Mathematics, Graham, Knuth, and Patashnick
• Foundations of Cryptography, Oded Goldreich
• Cryptography: Theory and Practice, Douglas Stimson

Answer 5

Knowing what an injective, a surjective and a bijective function are is helpful.

Some areas that might be useful:

• Number theory - some algorithms use the difficulty of factoring large numbers as their basis.
• Probability - used in analysing many kinds of ciphers.
• Linear algebra - Linear Feedback Shift Registers, which are used as primitives in many applications have their basis in this.
• Group theory - some algorithms are based on elliptic curves.

These are just to start with.

The Handbook of Applied Cryptography may also be useful: http://www.cacr.math.uwaterloo.ca/hac/

Answer 6

Here's an incomplete list:

• Number theory -- to understand why and how RSA works. It's also used for n-of-n threshold secret sharing.
• Group theory -- to understand why and how El Gamal works.
• Probability theory -- to better understand what "statistical security" means.
• Algebra -- the theory of finite fields is used in multiparty computation.
• Linear Algebra -- lagrange interpolation is used in Shamir's Secret Sharing Scheme. Some linear operations are also used in AES.

That's probably the order in which I'd go about studying the topics as well.

Answer 7

I'd actually recommend just picking a good book, eg Applied Cryptography, and learning the required math on a need-to-know basis. I certainly wouldn't like to discourage you from exploring interesting areas of mathematics mentioned by others here, but be warned that there's a huge amount of accumulated knowledge in each of these areas, and only small parts are actually used in cryptography. I'd say get the big picture of cryptography first, and then you'll know much better which areas of mathematics you need to study more.

This assumes that your goal is to actually understand how cryptography works. If your real goal is to use it in practice (ie computer security), I think you should rather concentrate on understanding abstractions (eg public key crypto, digital signature, hash function, protocol, mode of operation), not on how they are implemented. Understand these abstractions, use standard implementations (libraries), and above all, don't invent your own.

Answer 8

I think... handbook of cryptography and A Computational Introduction to Number Theory and Algebra by Victor shoup

are the 2 books you can refer for start and then move to other books...