Skip to content

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

Notifications You must be signed in to change notification settings

tsalomon/EmbeddedMontgomeryRSA

Repository files navigation

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 = Pe mod M (encrypt with public key)
  • P = Cd 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):

  • R2m = 22m mod M, where m = # bits of in the modulus (M)

The bitwise Montgomery Multiplication algorithm uses the equation:

  • X (residue) = X * R2m * (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

About

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

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages