RSA, a short recap
In a public key scheme, and for the sake of simplicity, assume a public scheme based on encryption-decryption (as opposed to e.g. DSA, the Digital Signature Algorithm, where the digital signature generated by the secret key is verified to satisfy a mathematic equation using the corresponding public key), you have two mathematical functions, called keys, the secret key S and the public key P and one is the inverse of the other, e.g. on a message m, P(S(m)) = S(P(m)) = m. RSA is the only widely used public key encryption scheme, constructed as follows: Generate two primes p and q of a fixed bit length, say 512 bits using a sufficiently random input. Denote the product by n, also known as the modulus. Now chose an appropriate so-called public exponent e. It must be prime to p - 1 and q - 1 (and there is no point in choosing it larger than φ(n) := (p - 1)(q - 1), as always, mφ(n) = 1 mod n - see below). There are computation advantages in choosing e small, such as 3, 17 or 65537 = 216 + 1, also known as the 4th Fermat prime. By running an extended version of Euclid's algorithm, which normal outputs the smallest common divisor of two numbers a and b, you can relatively easily find a number d such that for some number a, e∙d -a∙φ(n) = 1 modn. In the following, we just write ab rather than a∙b.
