Mastering Algorithms With C - Kyle Loudon [192]
We can make this simplification because (φ (n) + 1) mod φ (n) = (φ (n) + 1) - φ (n) = 1. We can verify this by inserting any number in place of φ (n). Notice the similarity between this equation and the one used for d earlier in the steps for computing keys. This provides a way to compute d from e and n. Of course, since e and n are public and potentially known to an adversary, one might ask: doesn't this give an adversary the same opportunity to compute the private key? At this point it is worth examining where RSA's security comes from.
RSA gets its security from the critical fact that Euler's function is multiplicative. This means that if p and q are relatively prime (which they are if we choose them both to be prime), then φ (pq) = φ (p)φ (q). Thus, if we have two primes p and q, and n = pq, then φ (n) = (p - 1)(q - 1), and most importantly:
d = e-1 mod (p-1)(q-1)
Therefore, even though an adversary might know both e and n, in order to compute d, she would have to know φ (n), which can only be determined in a practical manner by knowing both p and q. Since these are not known, the adversary is left to factor n, an extremely time-consuming process, provided the values chosen for p and q are large enough.
Enciphering and Deciphering Data Blocks
To encipher and decipher data with RSA, we first need to choose a block size. To do this, we must ensure that the largest value that the block can store, considering its total number of bits, is less than n. For example, if p and q are primes containing 200 decimal digits, n will be just under 400 decimal digits. Therefore, we should choose a block size small enough to store only those numbers with less than this many decimal digits. In practice, we often choose the block size in bits to be the largest power of 2 less than n. For example, if n were 209, we would choose a block size of 7 bits because 27 = 128 is less than 209, but 28 = 256 is greater.
To encipher a block of plaintext Mi , the i th block of data from a buffer M, we use the public key (e, n) to take the numerical value of Mi , raise it to the power of e, and take the result modulo n. This yields a block of ciphertext Ci . The modulo n operation ensures that Ci will fit into the same size block as the plaintext. Thus, to encipher a block of plaintext:
It was mentioned earlier that Euler's function is the basis for using modular exponentiation to encipher data using this equation and, in the equation that follows, for being able to get the original plaintext back. To decipher a block of ciphertext Ci , the i th block of ciphertext from a buffer C, we use the private key (d, n) to take the numeric value of Ci , raise it to the power of d, and take the result modulo n. This yields the original block of plaintext Mi . Thus, to decipher a block of ciphertext:
Interface for RSA
Name
rsa_encipher
Synopsis
void rsa_encipher(Huge plaintext, Huge *ciphertext, RsaPubKey pubkey);
Return Value
None.
Description
Uses RSA to encipher one block of plaintext specified by plaintext. Specify the public key (e, n) in the RsaPubKey structure pubkey. A block the same size as plaintext is returned in ciphertext. It is the responsibility of the caller to manage the storage required in ciphertext. To encipher a large buffer of data, call rsa_encipher in accordance with a block cipher mode (see the example earlier in this chapter).
Complexity
O (1)
Name
rsa_decipher
Synopsis
void rsa_decipher(Huge ciphertext, Huge *plaintext, RsaPriKey prikey);
Return Value
None.
Description
Uses RSA to decipher one block of ciphertext specified by ciphertext. Specify the private key (d,