Applied Cryptography, Second Edition: Protocols, Algorthms, and Source Code in C (cloth)
(Publisher: John Wiley & Sons, Inc.)
Author(s): Bruce Schneier
ISBN: 0471128457
Publication Date: 01/01/96

first break it into small blocks. Three-digit blocks work nicely in this case. The message is split into six blocks, mi, in which

m1 = 688
m2 = 232
m3 = 687
m4 = 966
m5 = 668
m6 = 003

The first block is encrypted as

68879 mod 3337 = 1570 = c1

Performing the same operation on the subsequent blocks generates an encrypted message:

c = 1570 2756 2091 2276 2423 158

Decrypting the message requires performing the same exponentiation using the decryption key of 1019, so

15701019 mod 3337 = 688 = m1

The rest of the message can be recovered in this manner.

RSA in Hardware

Much has been written on the subject of hardware implementations of RSA [1314, 1474, 1456, 1316, 1485, 874, 1222, 87, 1410, 1409, 1343, 998, 367, 1429, 523, 772]. Good survey articles are [258, 872]. Many different chips perform RSA encryption [1310, 252, 1101, 1317, 874, 69, 737, 594, 1275, 1563, 509, 1223]. A partial list of currently available RSA chips, from [150, 258], is listed in Table 19.3. Not all are available on the open market.

Speed of RSA

In hardware, RSA is about 1000 times slower than DES. The fastest VLSI hardware implementation for RSA with a 512-bit modulus has a throughput of 64 kilobits per second [258]. There are also chips that perform 1024-bit RSA encryption. Currently chips are being planned that will approach 1 megabit per second using a 512-bit modulus; they will probably be available in 1995. Manufacturers have also implemented RSA in smart cards; these implementations are slower.

In software, DES is about 100 times faster than RSA. These numbers may change slightly as technology changes, but RSA will never approach the speed of symmetric algorithms. Table 19.4 gives sample software speeds of RSA [918].

Software Speedups

RSA encryption goes much faster if you’re smart about choosing a value of e. The three most common choices are 3, 17, and 65537 (216 + 1). (The binary representation of 65537 has only two ones, so it takes only 17 multiplications to exponentiate.) X.509 recommends 65537 [304], PEM recommends 3 [76], and PKCS #1 (see Section 24.14) recommends 3 or 65537 [1345]. There are no security problems with using any of these three values for e (assuming you pad messages with random values—see later section), even if a whole group of users uses the same value for e.

Table 19.3
Existing RSA Chips

Company Clock Speed Baud Rate Per 512 Bits Clock Cycles Per 512 Bit Encryption Technology Bits per Chip Number of Transistors

Alpha Techn. 25 MHz 13 K .98 M 2 micron 1024 180,000
AT&T 15 MHz 19 K .4 M 1.5 micron 298 100,000
British Telecom 10 MHz 5.1 K 1 M 2.5 micron 256 ——
Business Sim. Ltd. 5 MHz 3.8 K .67 M Gate Array 32 ——
Calmos Syst. Inc. 20 MHz 28 K .36 M 2 micron 593 95,000
CNET 25 MHz 5.3 K 2.3 M 1 micron 1024 100,000
Cryptech 14 MHz 17 K .4 M Gate Array 120 33,000
Cylink 30 MHz 6.8 K 1.2 M 1.5 micron 1024 150,000
GEC Marconi 25 MHz 10.2 K .67 M 1.4 micron 512 160,000
Pijnenburg 25 MHz 50 K .256 M 1 micron 1024 400,000
Sandia 8 MHz 10 K .4 M 2 micron 272 86,000
Siemens 5 MHz 8.5 K .3 M 1 micron 512 60,000

[an error occurred while processing this directive]