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

Key Size	Auto Opt. CPU Time (sec)	All Opt.	Optimization (%)
512	2.42	0.53	78.1
1024	9.58	2.05	78.6
2048	38.49	8.27	78.5