Author : William Moore
Page : << Previous 2 Next >>
64. A 64-bit block of plaintext enters USDES, and a 64-bit block of ciphertext is returned by the algorithm. The same algorithm and key are used for both encryption and decryption, with minor changes. The key length is 56 bits. (The key is expressed as a 64-bit number, but every eighth bit is an internal arithmetic (parity) check, and not actually used by the encryption algorithm.) The algorithm is completely public. All security resides within the key.
In USDES, the two fundamental component operations are PERMUTATION and EXCLUSIVE-OR. In a permutation step, the order of the bits in the 64-bit sequence is rearranged, an operation which is easily reversed. In an exclusive-or step, denoted ^ in PERL or JavaScript, each bit is subject to the operation x ^ y = z, where z=1 if x=1 or y=1 but not both; whereas z=0 if both (x=0 and y=0) or both (x=1 and y=1).
For example:
1011001110000101010110110011100001010101101100111000010101010101
^ 1111100001010001010111111000010100010101111110000101000101010101
______________________________________________________________________
0100101111010100000001001011110101000000010010111101010000000000
The exclusive-or operation is likewise easily reversed. That is, if t is the plaintext, k is the key, c is the ciphertext, and t ^ k = c, then c ^ k = t. Both permutation and exclusive-or operations have the desirable mathematical properties that:
(1) the ciphertext is exactly the same size as the plaintext; and
(2) each of these operations is easily reversed.
The USDES consists of a complex sequence of permutations and exclusive-ors.
The USDES is of a complex sequence of permutations and exclusive-ors. After initial permutation of the plaintext, the block is broken into a left and right half, 32 bits apiece, denoted L0 and R0. Then there are 16 ROUNDS of identical operations, denoted as round-function, F(Ri-1,Ki), in which data are combined with various subsets of the key, denoted Ki. After the 16th round, the right and left halves, denoted L16 and R16, are joined, and a final permutation completes the calculation.
In each round:
(1) Li is set equal to Ri-1; and
(2) Ri is set equal to Li-1 ^ F(Ri-1,Ki).
What is Blowfish encryption?
Blowfish encryption was invented by Bruce Schneier in 1993, who published the source code, and released the algorithm into the public domain. There are no restrictions on the use or distribution of Blowfish. After a four years of intensive testing in the public arena, Blowfish's only known fault is that there are some weak keys. Blowfish is present in dozens of commercial products including Symantec's Norton Your Eyes Only and McAfee's PCCrypto.
Schneier B. Applied Cryptography, Second Edition. Protocols, Algorithms, and Source Code in C. New York: John Wiley & Sons, 1996.
Schneier B. The Blowfish Encryption Algorithm. Dr. Dobbs Journal, 19:38-40, 1994.
Claburn T. Blowfish. Wired. p. 7, June, 1997.
What are the design features of Blowfish encryption?
The algorithm is USDES-like, but much faster and easier to understand and to implement on small computers. The algorithm is so simple that it could be explained to an undergraduate mathematics major. The algorithm can be written in PERL and/or JavaScript, both of which are relatively simple programming languages. The algorithm does not use large-integer arithmetic. Blowfish was constructed to meet the following design criteria.
1. Fast.
2. Compact.
3. Simple.
4. Variably Secure.
Blowfish is optimized for applications in which the key does not change often. It is significantly faster than USDES when implemented on a 32-bit microprocessor with large data caches, such as the Pentium.
What are the major features of Blowfish encryption?
Blowfish is a 64-bit-block algorithm with a variable-length key. The algorithm consists to two parts:
1. Key Expansion converts a key of up to 448 bytes into several subkey 32-bit arrays: the permutation-array, denoted Pi (i=1,...18); and the string-array, denoted Si,j (i=1,...4) and (j=0,...255).
2. Data Encryption consists of a Feistel function, F(), iterated for 16 rounds.
To encrypt, divide the initial plaintext into a left and right half, 32 bits apiece, denoted L0 and R0. Then for each i, i=1,...16:
let Li be set equal to Li-1 ^ Pi; let Ri be set equal to F(Li) ^ Pi; then swap Li and Ri.
Finally, swap Li and Ri (i.e., undo the 16th swap). Then:
Let Rfinal be set equal to R16^P17; Let Lfinal be set equal to L16^P18;
Finally, rejoin the right and left halves, denoted Lfinal and Rfinal.
Decryption is the same as encryption, except that P1,... P18 are used in reverse order.
Subkeys are calculated as follows:
1. Initialize P'1,... P'18, and then S'1,0,... S'4,255, in order, using the hexadecimal expansion of pi.
2. Obtain the secret-permutation array, P1,... P18, by letting Pi be set equal to P'i ^ Ki.
3.
4.
In 1976, Diffie, Hellman, and Merkle introduced the paradigm of public-key or asymmetric encryption. In classical, symmetric encryption, the sender and receiver use essentially the same key, or paired keys which are obvious (symmetric) transformations of one another. In asymmetric encryption, the receiver creates a public-key and a private-key. The public-key may be distributed without restriction. The private-key is known only to the receiver, so that there are no problems incumbent upon giving a key to a possibly untrustworthy sender. The basic mathematical principle underlying asymmetric encryption is that it is an enormous computational task to factor a number which is the product of two large prime numbers. The most popular asymmetric encryption algorithm is the RSA public-key encryption algorithm (named after its authors: Ron Rivest, Adi Shamir, and Leonard Adleman). At this time, every public-key encryption algorithm is patented. The U.S. patent for the RSA public-key encryption algorithm expires on September 20, 2000. In asymmetric encryption, the public-key is the product of two, very large prime numbers, whereas the private-key is the factors themselves. The underlying principle of asymmetric encryption is the mathematical conjecture (i.e., unproved mathematical assertion) that it is an enormous computational task to factor a number which is the product of two large prime numbers. This conjecture has never been proved mathematically, but likewise in the past two decades of serious investigation by the world's best cryptanalysts, nobody has successfully challenged this mathematical assertion.
Sample calculation for RSA encryption.
The RSA method is breathtakingly elegant in its simplicity. Beyond the need for obtaining large prime numbers and performing large-integer arithmetic, the concept is so simple that it can be explained to a bright college undergraduate in mathematics. The big problem with public use of RSA in 1997 is that it is patented for the next three years.
Table 1 shows the essential steps in asymmetric encryption by the RSA Method.
TABLE 1:
PUBLIC KEY:
n = product of two prime numbers, p and q.
e is relatively prime to (p-1)*(q-1).
PRIVATE KEY:
d = (e-1) mod((p-1)(q-1)).
ENCRYPTION:
c = (te) mod n.
DECRYPTION:
t = (cd) mod n.
where n is the (public) product, e is the public (=encryption) key, d is the private (=decryption) key, t is the plaintext, and c is the ciphertext. The term x modulo n, or x mod n, denotes the (whole number) remainder of the division of x by n. Modulo arithmetic, or so-called 'clock arithmetic', is the mathematical method by which we determine, say, that five hours after ten o'clock, it is three o'clock. That is, the ordinary clock is a modulo-12 device, and [(5+10) mod 12] equals 3. Similarly, the second-hand and minute-hand on the clock are modulo-60 devides, and the military clock is a modulo-24 device. Modulo arithmetic has the fantastic advantage that integer arithemetic can be performed on huge integers with absolute accuracy, without having intermediate calculations exceed a predetermined size, namely, the square of the modulus. Modulo arithmetic is one of the pillars of modern cryptography.
After determining prime numbers p and q, then calculating n, e, and d, one discards p,q. The receiver distributes numbers (n,e) publicly, whereas d is kept secret and known only to the receiver. The receiver needs numbers (n,d) to decrypt his messages.
The paradigm of asymmetric encryption may be illustrated by a simple example that can be verified on a hand calculator. (Actually, the hand calculator is a bit tedious; it is probably faster to write a program in QBasic, Visual Basic, or JavaScript, if you know these languages.) In the example, let p=31 and q=37. These are not large prime numbers, but they serve as a didactic example. Then n= 31*37 = 1147.
The next task is to select e, which must be relatively prime (i.e., not share a common factor larger than one) with ((p-1)*(q-1)) = 30*36 = 1080. For this simple example,
Page : << Previous 2 Next >>