RSA Security 5.2.2 manual Modular Math, MultiPrime Numbers, RSA Algorithm

Cryptography Overview

authentication that MIT professors Ronald L. Rivest, Adi Shamir, and Leonard M. Adleman invented in 1977. It is actually similar to the example in the previous section that takes numbers to a power, except that it works in modular math.

Modular Math

Modular math uses a positive integer as a modulus; the only numbers under consideration are the integers from 0 to one less than the modulus. So for mod n, only the integers from 0 to (n–1) are valid operands, and the results of operations will always be numbers from 0 to (n–1). When an operation such as addition or multiplication would give a result that is greater than the modulus, the remainder of the result after division by n is used instead. Therefore, two numbers are equal mod n if and only if their difference is an even multiple of n.

For example, think of military time where the modulus is 2400. For instance, 2200 hours (10:00 P.M.) plus 4 hours is not 2600, but 0200 hours, or 2:00 in the morning. Likewise, if we start at 0, or midnight, 6 times 5 hours (say six 5-hour shifts) is not 3000, but 0600, or 6:00 A.M. the following day.

Another aspect of modular math is the concept of an inverse. Two numbers are the inverse of each other if their product equals 1. For instance, 7·343 = 2401, but if our modulus is 2400, the result is (7·343) mod 2400 ≡ 2401 – 2400 = 1 mod 2400.

Prime Numbers

The RSA algorithm also employs prime numbers, or primes. A prime number is a number that is evenly divisible by only 1 and itself. For example, 10 is not prime because it is evenly divisible by 1, 2, 5, and 10. But 11 is prime, because its only factors are 1 and 11.

MultiPrime Numbers

MultiPrime RSA functionality was added to Crypto-C V5.1. This new function allows you to generate RSA public/private key pairs. RSA MultiPrime key generation follows the same steps as standard RSA key generation with only a couple of exceptions: the use of a different AI, AI_RSAMultiPrimeKeyGen, and a different AM, AM_RSA_MULTI_PRIME_KEY_GEN, must be passed in during the B_GenerateInit call.

The RSA Algorithm

The RSA algorithm works as follows: take two large primes, p and q, and find their product n = pq; n will be the modulus. Choose a public value, e (also known as the public exponent), that is less than n. There are other constraints on e that are described

5 2 R S A B S A F E C r y p t o - C D e v e l o p e r ’s G u i d e