Cryptography Overview
52 RSA BSAFE Crypto-C Developer’s Guide
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 –240 0 = 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 e venly divis ible by 1, 2, 5, and 10. Bu t 11 is prime , because it s only facto rs
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