EmbeddedMontgomeryRSA

An optimized C implementation of the RSA public key encryption using the Montgomery Multiplication algorithm.

RSA and Modular Exponentiation

The RSA operations for encryption and decryption involve modular exponentiation: X^Y mod M.

• C: Ciphertext
• P: PlainText
• e: Public Exponent
• d: Private Exponent
• M: modulo

• C = P^e mod M (encrypt with public key)

• P = C^d mod M (decrypt with private key)

  The public key is (e,M) and the private key is (d,M).

Generation of Modulus (M)

Choose two prime numbers with half the bit-length of the desired public/private keys.

• p: prime
• q: prime
• M = p x q

See [https://www.mobilefish.com/services/rsa_key_generation/rsa_key_generation.php] for more information.

Generation of Public Exponent (e)

The public exponent (e) is a small integer.
Valid choices are 3, 5, 7, 17, 257, or 65537.
With RSA keys the public exponent is usually 65537.

The requirements for e are:

• 1 < e < phi(M) = (p - 1) * (q - 1)
• e and Euler’s phi(M) function are coprime.

Generaion of Private Exponent (d)

The private exponent is generated from primes p and q and the public exponent.

• d = e-1 mod (p - 1) * (q - 1)

Efficient Modular Exponentiation (using Montgomery Multiplication)

The multiply and square algorithm for Modular Exponentiation requires modular multiplication in the forms:

• Z = X * X mod M
• Z = X * Y mod M

This operation requires expensive multiplication and division operations.
Montgomery Multiplication converts parameters into modular residues wherein multiplication becomes addition and division becomes a bitwise shift.

Modular residues require a pre computed value (R), related to the size of the modulus (M):

• R^2m = 2^2m mod M, where m = # bits of in the modulus (M)

The bitwise Montgomery Multiplication algorithm uses the equation:

• X (residue) = X R^2m (R^-1) mod M

This bitwise algorithm internally calculates the modular inverse (R^-1).
The modular inverse is defined as R^-1 where R * R^-1 mod M = 1.

Optimization Results