Mastering Algorithms With C - Kyle Loudon [194]
The runtime complexity of rsa_decipher is O (1) because all of the steps in deciphering a block of data run in a constant amount of time. Since the block size is constant, the loop in modexp runs in a constant amount of time.
Example 15.4. Implementation of RSA
/*****************************************************************************
* *
* --------------------------------- rsa.c -------------------------------- *
* *
*****************************************************************************/
#include "encrypt.h"
/*****************************************************************************
* *
* -------------------------------- modexp -------------------------------- *
* *
*****************************************************************************/
static Huge modexp(Huge a, Huge b, Huge n) {
Huge y;
/*****************************************************************************
* *
* Compute pow(a, b) % n using the binary square and multiply method. *
* *
*****************************************************************************/
y = 1;
while (b != 0) {
/**************************************************************************
* *
* For each 1 in b, accumulate y. *
* *
**************************************************************************/
if (b & 1)
y = (y * a) % n;
/**************************************************************************
* *
* Square a for each bit in b. *
* *
**************************************************************************/
a = (a * a) % n;
/**************************************************************************
* *
* Prepare for the next bit in b. *
* *
**************************************************************************/
b = b >> 1;
}
return y;
}
/*****************************************************************************
* *
* ----------------------------- rsa_encipher ----------------------------- *
* *
*****************************************************************************/
void rsa_encipher(Huge plaintext, Huge *ciphertext, RsaPubKey pubkey) {
*ciphertext = modexp(plaintext, pubkey.e, pubkey.n);
return;
}
/*****************************************************************************
* *
* ----------------------------- rsa_decipher ----------------------------- *
* *
*****************************************************************************/
void rsa_decipher(Huge ciphertext, Huge *plaintext, RsaPriKey prikey) {
*plaintext = modexp(ciphertext, prikey.d, prikey.n);
return;
}
Questions and Answers
Q: Suppose we would like to encrypt a file containing flags that enable or disable certain attributes in an application based on the features a customer has paid for. Which method of encryption presented in this chapter would be best suited to this scenario?
A: Since in this scenario only one party, the application itself, needs to read the file, it makes sense to use a symmetric cipher such as DES. Before installing the file, we encipher it with a key that only the application knows about. Whenever the application needs to read the file, it deciphers it using the same key.
Q: Suppose a party A is making sensitive requests for data across the Internet to another party B. B is the only one who should be able to decipher the data enciphered by A, and A is the only one who should be able to decipher data enciphered by B specifically for A. B also receives requests from several other parties, all of whom should not be able to hear what each other is saying. Which method of encryption from this chapter would be best in this scenario?
A: Since all parties must be able to communicate with B but without anyone else being able to decipher the communications, we should use a public-key cipher such as RSA. Consider the case of A making a request to B. A