# What is the lowest level of mathematics required in order to understand how encryption algorithms work?

What mathematical fields of knowledge would be required in order to get a good understanding of encryption algorithms?

Is it basic algebra, or is there a "higher education" mathematical field dedicated to encryption? I know there is the cryptography field, but what is the subset of knowledge required for cryptographers?

-

## migrated from security.stackexchange.comSep 20 '13 at 7:27

This question came from our site for information security professionals.

Depends a lot of which parts of crypto you want to understand. For asymmetric crypto you need number theory, for symmetric crypto you need a combination of probability theory and cryptography specific knowledge. For cryptographic protocols you need very little math, mainly logical thinking and knowledge of the properties different primitives have. –  CodesInChaos Sep 19 '13 at 18:58
–  LamonteCristo Sep 19 '13 at 19:30
Rule of thumb: The more a solution moves away from information-theoretic security and towards user convenience, the more complex and subtle the required compromises and associated mathematics become. –  LateralFractal Sep 19 '13 at 23:22
It would be really awesome if more people would ask this question. –  Nemo Sep 21 '13 at 2:19
@Nemo Not really, those would be closed as duplicates. ;) –  e-sushi Nov 2 '13 at 9:59

Most encryption is based heavily on number theory, most of it being abstract algebra. Calculus and trigonometry isn't heavily used. Additionally, other subjects should be understood well; specifically probability (including basic combinatorics), information theory, and asymptotic analysis of algorithms. There's also more math that's worth knowing to be a good programmer which is key if you really want to be an expert. The number theory is more important with understanding asymmetric encryption, but does come up in symmetric encryption as well (e.g., in AES how to derive the S-box and MixColumns relates to understanding Galois fields).

First, you need to learn some notation. Things like logical operators, most importantly for cryptography XOR (sometimes denoted as circle plus: ⊕), where 0 XOR 1 = 1 XOR 0 = 1, and 0 XOR 0 = 1 XOR 1 = 0. It also helps to be able to understand the notation and language of abstract mathematics and set theory; e.g., {0,1}128 means the set of all strings that are made up of 128 binary digits (each digit is a 0 or 1). Similarly, F: {0,1}64 → {0,1}128 means F is a function that maps a 64 bit input into an output that is 128-bit string. You'll have to learn the difference between a function, bijection, permutation, etc, but again this is mostly just terminology of relatively simple concepts.

One of the most important topics is modular arithmetic. E.g., 1 ≡ 64 (mod 21) where (mod N) means you only care about the remainder when dividing by N (since 64/21 = 3 with remainder 1; the modulo is 1). One important notation to learn (that's a potential source of confusion) is that the (mod N) applies to both sides of the equation; so you could equivalently say 8^2 ≡ 1 (mod 21). Many programming languages (e.g., C, Java, python, javascript) use % to do modulo division -- e.g., 64 % 21 gives 1. The cool thing about modular arithmetic is that you can just do normal arithmetic (addition and multiplication) and reduce at the end (or at any step in the middle) as modular arithmetic forms a finite field; e.g., 8 ≡ 29 ≡ 50 (mod 21) so since 8*8 ≡ 64 ≡ 1 (mod 21) we also know that 29*8 = 232 ≡ 29*50 = 1450 ≡ 1 (mod 21). With modular arithmetic there's no difference both 8, 29, 50 represent the exact same number.

You'll need to understand things like Fermat's little theorem, Euler's theorem (based on totient), Euclid's algorithm for greatest common denominators (specifically Euclid's extended algorithm to generate multiplicative inverses), Carmichael numbers, Fermat primality test, Miller-Rabin primality test, modular exponentiation, and discrete logarithms.

If you want to go further you may want to learn about things like finite fields (specifically Galois fields), polynomial rings, elliptic curves, etc. This isn't meant to limit things; e.g., cryptography (and attacks on cryptography) aren't necessarily limited to these types of math. E.g., NUTRUEncrypt is based on lattices/shortest vector problem, and the McEliece Cryptosystem is based on Goppa codes, but again you still need to learn the math above to be able to understand this math.

And then you have the basic math background to learn about cryptography, which isn't just the math but also involves using the math in secure ways. (For example, textbook RSA c = m^e mod p q is insecure for a variety of reasons - you should use a secure randomized padding scheme to your message and likely combine with symmetric encryption for long messages).

Free Electronic References

• The Handbook of Applied Cryptography - Chapter 2 has a decent introduction to these concepts for the advanced learner -- it introduces concepts very quickly and compactly, and is probably better as a reference or second/third attempt at the material.

• Chapter 1 of Algorithms by DPV (specifically sections 1.2 to 1.4) give a gentler introduction to the math behind RSA.

• Shoup - A Computational Introduction to Number Theory and Algebra - From the preface "Number theory and algebra play an increasingly significant role in computing and communications, as evidenced by the striking applications of these subjects to such ﬁelds as cryptography and coding theory. My goal in writing this book was to provide an introduction to number theory and algebra, with an emphasis on algorithms and applications, that would be accessible to a broad audience." Very detailed and fairly accessible.

• Stick-figure introduction to AES at various levels of complexity with the last level showing where the number theory goes in.

• The Udacity Applied Crypto course. More of an introduction to the cryptography than the math behind it, but introduces the math when necessary.

• Dan Boneh's Coursera cryptography course. Solid introduction to cryptography, again introducing the math when necessary.
-

@dr jimbob gives a pretty solid answer, so let me just summarize it: finite fields. Regardless of the area of cryptography you are interested in, you always end up with finite fields, in particular Zp (with p prime), for RSA / DH / DSA / some elliptic curves, and Z2 and extensions thereof (GF(2m)) for symmetric cryptography and some other types of elliptic curves (you have to know what it means when we say "linear approximation of a S-box": it is all about vector spaces with Z2 as base field).

This book is good; not really as an introduction, but if you can get through it, then you know enough to do crypto. If you don't, then it shows areas where you still need practice.

-

The lowest level of mathematics required would be binary mathematics like the XOR operator. If you can understand that then you can understand a one-time pad which is mathematically unbreakable.

Most other fields of cryptography focus on making life more convenient for the user e.g. using a single key for all communications at the expense of information-theoretic security. There's a reason why militaries and governments don't compromise on security though and still use one-time pads. You should use one-time pads if you want any privacy from those governments as well.

If you look at this basic stick figure guide to AES you can see it starts off fairly simple but then near the end it starts explaining the complex mathematics behind it. Even with all its complex mathematics there's still attacks on AES and it's nowhere near as strong as a one-time pad. My point is you could spend your whole life learning all the complex mathematics in dr jimbob's post, but still not be able to invent something stronger than the one-time pad. There's lots of interesting areas for research and improvement though so don't let that discourage you from trying!

-
Yes, XOR is minimal (but does it provide a "good understanding" of encryption?). The perfect security of OTP doesn't matter in practice, since OTP requires securely storing a key that's the same size as the text (and only using it once) so its rarely used in practice (why not just store the text securely)? But the math I mentioned doesn't require devoting your whole life to it; learning modular arithmetic to understand RSA takes a few days at most if you take the time to digest each part and play around with toy examples. Yes, there's much more to learn after that, but its easy to start. –  dr jimbob Sep 20 '13 at 21:45

It depends on what kind of encryption you're interested in. AES, DES, MD5, SHA-1, and basically all other hashes/symmetric block ciphers can be understood with no mathematical background at all, as long as you understand basic programming constructs like xor and bit-shifts. See for example A Stick Figure's Guide to AES. Additionally, things like modes of encryption, The TLS (SSL) Protocol, and Mental Poker can be understood with no mathematical background, as long as you accept that the ciphers they rely on work as advertised.

A surprising number of mathy crypto-algorithms can be understood with just a basic knowledge of modular arithmatic. I wrote a series of blog posts on how the asymmetric cipher RSA works a few years back, which can be found here. The Blum-Blum-Shub symmetric stream cipher and the ubiquitous Diffie-Hellman key exchange protocol are also require only basic modular arithmetic.

Things like Elliptic Curve Cryptography and Shamir's Secret Sharing involve more in-depth knowledge of finite fields, which is kind of like an abstraction of modular arithmetic.

-

A fun book to start with for the number theory side of things:

http://www.amazon.com/Friendly-Introduction-Number-Theory-4th/dp/0321816196/ref=sr_1_2?ie=UTF8&qid=1326998078&sr=8-2

It's pretty accessible for the mathematically inclined but for whatever reason didn't get the grounding they should have in college.

I haven't found a good intro book on Probability, but I think a part of that is that I took it in college so I haven't really tried. I'd love to hear some good recommendations, I could use an easy going refresher (a surprisingly hard thing to find for math.. mathematicians seem to think everything should be left up as an exercise to the reader, even if you're stuck. Those who can get over such conceit are the real math gods to me..)

-