Explanation of how RSA encryption and signatures work

RSAExplainer.cs

using System.Diagnostics;

int p = 23, q = 29; // two private primes
int pubMod = p * q; // 667, the neighbor of the beast
// In practice, the primes used are crazy big (1024-bit each), making it infeasible to factor pubMod (2048-bit).
// Even if you could try 4B factors a second, on 4B machines, each with 4B CPUs, for 4B seconds (~126 years), you
// could only explore 128-bits worth of possibilities! And that doesn't mean you're an eighth of the way there. It
// would be if the number were 131-bits in length. Each extra bit doubles the effort required.
int pubExp = 257; // third Fermat prime (2^2^n+1, where n=3)
// The real RSA uses the fourth, and believed to be the last, Fermat prime, 2^2^4+1=65537.

int msg = 420; // can be most anything in the range of pubMod
// there is a chance of collision, although vanishingly small in practice.
int encMsg = ModPow(msg, pubExp, pubMod); // msg^pubExp%pubMod - will in the range of pubMod, but will NOT be 420
Debug.Assert(encMsg != msg);
Console.WriteLine($"Encrypted message: {encMsg}");

// Q: If encMsg=msg^pubExp, can't we do something like encMsg^(1/pubExp) to recover msg? Let's try.
int hackExp = ModInverse(pubExp, pubMod); // 1/pubExp%pubMod - our hack attempt to "undo" the operation
int hackMsg = ModPow(encMsg, hackExp, pubMod); // will NOT be 420, hack thwarted
Debug.Assert(hackMsg != msg);
Console.WriteLine($"Hacked message: {hackMsg}");

int phi = (p - 1) * (q - 1); // Euler's totient φ - 22*28=616 in our case (factors: 2*2*2*7*11)
int phi2 = pubMod - (p + q - 1); // Alternate way to calculate it that avoids big number multiplication
// Think of it like pubMod being a rectangle of size p by q, and we are shaving off 1 from each dimension.
// Euler's totient counts the positive integers up to n that are relatively prime to n. Since p and q are prime, 
// the totient counts them all except for the number itself. That's why it is p-1 and q-1.
int priExp = ModInverse(pubExp, phi); // 1/pubExp%phi - our private exponent - 465, in our case
// This answers the question of what number, when multiplied by pubExp, yields 1 modulo phi?
// Note that, in practice, it is possible that phi will have pubExp as a factor which will cause the above
// operation to fail. In that case, we simply regenerate new prime values for p and q and try again.
int decMsg = ModPow(encMsg, priExp, pubMod); // encMsg^priExp%pubMod - should be 420
Debug.Assert(decMsg == msg);
Console.WriteLine($"Decrypted message: {decMsg}");

// Signatures
int sign = ModPow(msg, priExp, pubMod); // msg^priExp%pubMod - we "encrypt" with private exponent to sign message.
// Note that here we are reusing the same key pair for both encryption and signatures, but this is not recommended
// in practice. Instead, you should use a separate key pair. While no existing attack works based on knowing both
// msg^pubExp and msg^priExp, there is a concern and there isn't enough research to rule out such an attack.
Debug.Assert(sign != encMsg && sign != msg);
Console.WriteLine($"Signature: {sign}");

int veri = ModPow(sign, pubExp, pubMod); // sign^pubExp%pubMod - we "decrypt" with public exponent to verify signature.
Debug.Assert(veri == msg);
Console.WriteLine($"Verify: {veri}");

for (int mi = 0; mi < pubMod; mi++) {
    int ei = ModPow(mi, pubExp, pubMod);
    if (mi == ei) Console.WriteLine($"Encryption collision at {mi}");
    int di = ModPow(ei, priExp, pubMod);
    Debug.Assert(mi == di);
    
    int si = ModPow(mi, priExp, pubMod);
    if (mi == si) Console.WriteLine($"Signature collision at {mi}");
    int vi = ModPow(si, pubExp, pubMod);
    Debug.Assert(mi == vi);
    
    if (mi != ei && mi != vi) Debug.Assert(ei != si);
}

// use binary multiplication of squarings to perform exponentiation
static int ModPow(int n, int e, int m) {
    for (int r = 1;;) { // starting with n^0 (1)
        if ((e & 1) == 1) // if least significant bit of e is 1...
            r = (int)((long)r * n % m); // r=r*n mod m
        e >>= 1; // shift bits of e right by 1
        if (e == 0) // are we done?
            return r;
        n = (int)((long)n * n % m); // n=n² mod m
    }
}
// Example: given n=3, e=5 and m=infinity to compute 3^5=243
// n=3, r=1, e=5, low bit of e is set, so we multiply n(3) on to r(1), shift e right, then we square n.
// n=9, r=3, e=2, low bit of e is not set, shift e right, then we square n.
// n=81, r=3, e=1, low bit of e is set, so we multiply n(81) on to r(3), shift e right, e is zero so we are done.
// r=243

// Use Euclidean algorithm to get multiplicative modular inverse
// What number when multiplied by `n` yields 1 modulo `m`?
static int ModInverse(int n, int m) {
    int t = 0, r = m;
    for (int t2 = 1, r2 = n % m; r2 != 0; ) {
        int q = r / r2;
        (r, r2) = (r2, r - q * r2);
        (t, t2) = (t2, t - q * t2);
    }
    if (r > 1) throw new ArgumentException($"No inverse exists! {n} and {m} are not coprime.");
    return t < 0 ? t + m : t;
}