Overview of Key Topics: Optimizer, Bigints, Prime Generation, RSA Encryption, and Cryptographic Hashing

Five big topics today: the optimizer, bigints, prime generation, RSA Encryption, and Cryptographic Hashing.


1) We talked a bit about the optimizer today, as extra credit was awarded for having Josephus code that would run in 1.5s or so - as it turns out, turning on the optimizer to -O3 resulted in a 300x speedup, which is the highest I've ever seen. It's an important thing to know.


2) We talked about the Boost Multiprecision library, specifically how you can use cpp_ints to make very big integers, way bigger than the normal 64 bit long longs that we use. They work like normal integers, but you can initialize them with strings because only strings can hold a representation of a number large enough.


3) It is important to be able to generate large primes quickly. Factoring to see if something is a prime is not feasible (since factoring is so slow), but fortunately there is an approach that will tell us, probably, if a number is prime or not. In real life, we use an algorithm called Miller-Rabin, but since we've gone over Fermat's Little Theorem, I used that in class. Basically, since for every prime number y, x^(y-1) mod y is 1, if we ever get an answer other than 1, we know y is not prime. So we try a bunch of x's, and if we get 1 every time, we conclude that y is probably prime.



You might think that primes are really rare when they're large, but they're not really. The odds of hitting a prime number is roughly inversely proportional to the number of digits in the number.


4) RSA encryption. The proof for it is a little involved, but the actual algorithm itself is very easy:
1) Step one - randomly generate two prime numbers, called P and Q
2) Compute N = P * Q
3) Compute T = (P-1)*(Q-1)
4) Use 65537 for E, unless N is smaller than that, in which case pick a prime number smaller than N. Publish E and N as your public key.

5) Compute the modular inverse of E mod T. This is called D. Save D and N as your private key. Keep it safe and secret.
6) To encode a message M, you use the Powm function we talked about last time. The encoded message S = powm(M,E,N)
7) To decode an encoded message S, you use the Powm function again to get M back. M = powm(S,D,N)


RSA can be used both to send emails to other people securely, and also to sign documents with your private key.


5) Finally we talked about cryptographic hashes, which are a way of signing binaries without using a private key. You compute a "hash" for the binary, and if the hash algorithm is good, the number you get won't be easy to predict or replicate with another input. This means that when you post your binary online, you can attach the hash to it as a sort of signature, and that allows people to check that the binary they download has the same signature as the one you posted, to prevent tampering.