| Previous | Table of Contents | Next |
first break it into small blocks. Three-digit blocks work nicely in this case. The message is split into six blocks, mi, in which
The first block is encrypted as
Performing the same operation on the subsequent blocks generates an encrypted message:
Decrypting the message requires performing the same exponentiation using the decryption key of 1019, so
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 |
| Previous | Table of Contents | Next |