Biomedical Engineering Reference
In-Depth Information
for the computation in Z p, which reduces the cost for each exponentiation when d is
larger than the primes. It is common to refer to dp and dq as the CRT-exponents.
The first method to use the CRT for decryption was proposed by Quisquater and
Couvreur [
3
,
6
].
Since the method requires knowledge of p and q, the key generation algorithm
needs to be modified to output the private key (d, p, q) instead of (d, N). Given the
private key (d, p, q) and a valid ciphertext C Z N, the CRT decryption algorithm is
as follows:
(a) Compute Cp = Cdp mod p.
(b) Compute Cq = Cdq mod q.
(c) Compute M0 = (Cq - Cp). p - 1 mod q.
(d) Compute the plaintext M = Cp ? M0. p.
This version of CRT-decryption is simply Garner's Algorithm for the CRT
applied to RSA. If the key generation algorithm is further modified to output the
private key (dp, dq, p, q, p - 1 mod q), the computational cost of CRT-decryption
is dominated by the modular exponentiations in steps (a) and (b) of the algorithm.
When the primes p and q are roughly the same size (i.e., half the size of the
modulus), the computational cost for decryption using CRT-decryption (without
parallelism) is theoretically 1/4 the cost for decryption using the original method
[
7
]. Using RSA along with CRT-decryption allows for extremely fast encryption
and decryption that is at most four times faster than standard RSA [
8
].
3. Message Digest 5 (MD5) Algorithm
MD5 consists of 64 of these operations, grouped in four rounds of 16 opera-
tions. F is a nonlinear function; one function is used in each round. Mi denotes a
32-bit block of the message input, and Ki denotes a 32-bit constant, different for
each operation. s is a shift value, which also varies for each operation [
3
].
MD5 processes a variable length message into a fixed-length output of 128 bits.
The input message is broken up into chunks of 512-bit blocks; the message is
padded so that its length is divisible by 512 [
9
]. The padding works as follows: first
a single bit, 1, is appended to the end of the message. This is followed by as many
zeros as are required to bring the length of the message up to 64 bits less than a
multiple of 512. The remaining bits are filled up with a 64-bit integer representing
the length of the original message [
10
].
The main MD5 algorithm operates on a 128-bit state, divided into four 32-bit
words, and are denoted A, B, C, and D. These are initialized to certain fixed
constants. The main algorithm then operates on each 512-bit message block in
turn, each block modifying the state. The processing of a message block consists of
four similar stages, termed rounds; each round is composed of 16 similar opera-
tions based on a nonlinear function F, modular addition, and left rotation. Many
message digest functions have been proposed and are in use today. Here are just a
few like HMAC, MD2, MD4, MD5, SHA, SHA-1. Here, we concentrate on MD5,
one of the widely used digest functions [
1
].
Search WWH ::
Custom Search