DinS Written on 2018/7/22
Number theory is largely used in cryptography and mainly about modular arithmetic.
General form: a = q x b + r
q – quotient r – remainder
Two members a and b are congruent modulo m if they have the same remainder when divided by m.
a ≡ b (mod m)
Greatest common divisor gcd(a,b) = largest integer that divides both a and b. Convention a, b >=0
Euclid’s lemma: d divides a and b if and only if d divides a-b and b.
We can use Euclid’s algorithm to find gcd.
Extended Euclid’s lemma: if d divides a and b, and d = ax + by for integer x and y. Then d = gcd(a,b). By returning x and y we can make sure that d is gcd.
Least common multiple lcm(a,b) = smallest positive integer that is divisible by both a and b.
lcm(a,b) * gcd(a,b) = a*b
RSA, the most frequently used method in cryptography, builds on number theory. Its building blocks are Theorem of Unique Factorization, Chinese Remainder Theorem, modular exponentiation, Fermat’s Little Theorem, Euler’s Totient Function and Euler’s Theorem. I don’t expect you to write your own implementation of RSA. That’s unnecessary. But to use RSA well you need to understand at least one thing: RSA relies on big primes. It’s very easy to multiply two big primes to get a number. It’s very hard to do the reverse.
RSA roughly works like this:
First you generate two big primes p and q.
Second you compute n = p*q
Third generate random e coprime with (p-1)(q-1)
Publish the public key E which is the pair (n,e)
Save the private key D which is the pair (p,q)
If somebody wants to send you a message encrypted by RSA, he used E to generate a really big integer. You get the integer and decrypt it using D to turn the integer back into a string.
As how to generate and compute these numbers, we use the building blocks mentioned above. Most people will not be interested in it.
Let’s now consider how to break RSA. This will improve your understanding in how to use RSA correctly, which is the most important thing to most people.
1. Simple attack
Use pubic key yourself to see if it coincides with certain message. This works well for a small set o messages.
Counter: add randomness. For example, use first 128 bits for message and append 128 more random bits.
2. Small prime
If p or q < 1000000, it can be factorized brutally.
Counter: use very large prime, 2048-bit numbers.
3. Small difference
If |p-q|<1000000, then there’s a way to narrow the search space and guess the two primes.
Counter: make sure |p-q| is large enough
4. Insufficient randomness
Random number generator may coincide. This will enable attackers to try rng on many machines and if luck favors them, they will happen to generate the same number sequence.
Counter: don’t rely solely on time(). Add some true randomness, for example let users move mouse for some time and add that to seed.
5. Hastad’s Broadcast Attack
If the same message is encrypted using different public key and sent to different users, there’ll be a way to at least partially break it.
Counter: add random padding to message before encrypting.
6. Error code
Usually when server receives wrong message it will send back error code and description. This may prove useful to attackers. They may try random nonsense messages and send them to server to see if the return message makes sense and guess the key.