Cryptography Reference
In-Depth Information
multiply( &tmp1, &tmp2 );
divide( &tmp1, n, NULL );
}
}
while ( i );
free_huge( &tmp1 );
free_huge( &tmp2 );
// Result is now in “h2”
}
Besides the introduction of a call to divide , for its side effect of computing a
modulus, and the substitution of m and c for h1 , Listing 3-19 is identical to the
exponentiate routine in Listing 3-18. This works, and performs reasonably
quickly, using a reasonable amount of memory, even for huge values of m , e , and
n . Given a message m and a public key e and n , you encrypt like this:
huge c;
mod_pow( &m, &e, &n, &c );
Decrypting with RSA
Decryption is identical, except that you swap e with d and of course you switch
c and m :
huge m;
mod_pow( &c, &d, &n, &e );
There is one subtle, but fatal, security fl aw with this implementation of decrypt,
however. Notice that you multiply and divide log 2 d times as you iterate through
the bits in d looking for 1 bits. This is not a problem. However, you do an addi-
tional multiply and divide at each 1 bit in the private exponent d . These multiply
and divide operations are reasonably effi cient, but not fast. In fact, they take long
enough that an attacker can measure the time spent decrypting and use this to
determine how many 1 bits were in the private exponent, which is called a timing
attack . This information drastically reduces the number of potential private keys
that an attacker has to try before fi nding yours. Remember, part of the security
of the RSA public key cryptosystem is the infeasibility of a brute-force attack.
The most straightforward way to correct this is to go ahead and perform the
multiply and divide even at the 0 bits of the exponent, but just throw away
the results. This way, the attacker sees a uniform duration for every private key
operation. Of course, you should only do this for the private-key operations.
You don't care if an attacker can guess your public key (it's public, after all).
It may occur to you that, if the modulus operation is distributive through-
out exponentiation, it must also be distributive throughout multiplication
and even addition. It is perfectly reasonable to defi ne “modulus-aware” addition
Search WWH ::




Custom Search