% $RCSfile: rsa.tex,v $ % % $Log: rsa.tex,v $ % Revision 1.1 1995/07/28 21:19:57 slm % Initial revision % % Revision 1.6.1.1 1994/10/21 00:00:17 hkaram % New branch % % Revision 1.6 1994/08/02 23:55:43 davidm % Sectioning commands now use \protspec and \topic so latex2html has % an easier time. % % Revision 1.5 1994/07/05 00:42:34 ho % Indexed. % % Revision 1.4 1994/01/14 19:29:44 menze % Fixed KEYS subsection to not make TOC entry % % Revision 1.3 1994/01/12 01:31:42 menze % Fixed an exponentiation % \protspec{RSA}{RSA (Rivest-Shamir-Adleman Encryption Algorithm)} \index{rsa} \index{RSA encryption} \index{cryptography, public key} \label{RSA} \input cryptDist \topic{SPECIFICATION} \noindent The RSA protocol encrypts all bytes of all packets sent using the RSA encryption algorithm in ECB (electronic code book) mode. RSA uses the key manager protocol (KM, page~\pageref{KM}) to map from the destination address passed in at open time to an RSA key. Each message is encrypted independently. RSA is designed to be composed over any datagram protocol, and it accepts arbitrary address types at open time. RSA lengthens each packet by as much as a few hundred bytes. When packets are received, decryption reverses the encryption, and the original packet lengths are restored. The important cryptographic feature of RSA is that the encryption and decryption keys contain different information, so that the encryption key may be published, without compromising the decryption key. \topic{SYNOPSIS} \noindent When an RSA session is opened, it opens the protocol configured below it with the addresses passed to it during open. It then performs a GETPARTICPANTS operation on the newly opened session to acquire the fully resolved addresses of the participants. The first two participants are then used as arguments to open two key manager (KM) sessions. When a message is pushed to an RSA session a KM\_RESOLVE operation is done on the destination key manager session to get the current remote encryption key. This will be a series of two or three large numbers, expressed in decimal as a string, several hundred characters long. A special parsing routine converts the numbers to the binary values required for the RSA algorithm. The character string key, and converted binary key are cached; on subsequent messages, the key returned from the key manager is compared to the cached value, and if it hasn't changed, the conversion step is skipped. The message length is prepended to the message as an unsigned four byte number. The message is divided into blocks of size (binary-key-size - 1) bytes. The last block is padded with 0s if needed. Each block is encrypted with the RSA algorithm, producing an output block one byte larger than the input block. These blocks are concatenated to make the output message. A typical RSA key size is 64 bytes: In this case, input messages of size 0 - 59 bytes will expand upon encryption to one block of 64 bytes; a message of size 1000 bytes will expand to 1024 bytes. Decryption is straightforward, using essentially the same algorithm. (The KM\_RESOLVE is done with the local host address.) Some partial checking is done that the decrypted input makes sense. Of course, received packets shrink some when they are decrypted. RSA has not been tested on little-endian machines, or between machines of differing endianness. RSA discards the attributes attached to any outgoing message. This is done to minimize out-of-band information transmittal. RSA does not touch any attributes attached to incoming messages, and forwards them along with the decrypted data up to the next protocol. Exception: If the IP psuedoheader length fixup flag is turned on, the length field is adjusted in upgoing pseudoheaders. For packets going in either direction, if the KM\_RESOLVE fails, the message is dropped. The present code assumes that the decimal-to-binary conversion operation on the key will succeed; bad format keys will probably cause a memory fault. \topic{REALM} RSA is in the ASYNC realm. \topic{PARTICIPANTS} RSA passes participants to the lower protocols without manipulating them. It uses the first two participants to lookup the keys for encryption and decryption. \topic{CONTROL OPERATIONS} RSA recognizes the following control operations; all others are passed unchanged to the lower protocol or session. To prevent an outbound channel, the data buffer is zeroed in the downward direction. GETMAXPACKET and GETOPTPACKET: The packet size returned by the lower protocol/session is passed on unchanged. This isn't exactly the right thing to do. IP\_PSEUDOHDR: This control operation turns on the IP pseudoheader length-fixup flag, either for a session or the entire protocol. The control operation is also passed to the lower session or protocol. See IP (page~\pageref{IP}) for an explanation of this kludge. ETH\_REGISTER\_ARP is recognized by rsaControlProtl, and is passed down without zeroing the data buffer. RSA does not support the CRYPT series of control operations for communicating with the key manager. \topic{CONFIGURATION} RSA expects to be configured on top of a transport protocol and a key manager. The transport protocol must preserve packet boundaries (i.e. RSA will not work on top of TCP). Example of a graph.comp file: \begin{verbatim} --------------------------------- @; name=simeth/0; name=eth protocols=simeth/0; name=arp protocols=eth; name=vnet protocols=eth,arp; name=ip protocols=vnet; name=km; name=rsa protocols=ip,km; name=udp protocols=rsa; name=udpcrypttest protocols=udp; @; prottbl = ../../../etc/prottbl.nonstd; --------------------------------- \end{verbatim} \topic{KEYS} An RSA key is a set of three numbers, separated by any nonnumeric characters. The three numbers are the Modulus, the Encryption exponent, and the Decryption exponent, in decimal. The decryption exponent may be 0 if absent. A bad format key can cause a core dump in the key parser. No consistency checking is done on the numbers. No cryptographic care is taken by the key parser to erase intermediate results. The modulus M is the product of two large primes P and Q, each typically around 75 digits. P and Q don't appear explicitly in the key. They must be kept secret. There is various magic for selecting ``good'' primes, but random primes of the right size are usually ok. In the example below, I have standardized on the value $2^{511}+3$ as the encryption exponent E. Any large number about the size of the modulus may be used for E, but it must be relatively prime to (P-1)*(Q-1). The modulus and the encryption exponent are published. The decryption exponent D is the solution to D*E = 1 (mod (P-1)*(Q-1)). It must be kept secret. Example of a keys file: \begin{verbatim} --------------------------------- 4 10-1000 10 0xc00c4574 #leibniz # P = 314159*10^70 + 143; Q = largest prime < 2^512/P # Mod = P*Q; EncExp = 2^511+3 "1340780792994259709957402499820584612747936582059239337\ 7723561443721764030073217999499518551191939614890369525\ 058823497765371118769307671100370276265584333 6703903964971298549787012499102923063739682910296196688\ 8617807218608820150367734884009371490834517138450159290\ 93243025426876941405973284973216824503042051 2210719290388045346905339355787434075468743397471703259\ 9002057100400698735281575781871972803870117115603534718\ 25220112394617831579775760441554445681825271" 0xc00c4554 #cottonwood # P = 271828*10^70 + 183; Q = largest prime < 2^512/P # Mod = P*Q; EncExp = 2^511+3 "1340780792994259709957402499820584612747936582059239337\ 7723561443721764030073529800297232392991909065538380829\ 542476840196156388644073364112998961600082697 6703903964971298549787012499102923063739682910296196688\ 8617807218608820150367734884009371490834517138450159290\ 93243025426876941405973284973216824503042051 5907169959764554352962919640402328589843757838494447294\ 1156728779748701667813048426221184319210061087236538029\ 59044237615679489623343998139399365759904515" --------------------------------- \end{verbatim} For testing, I have all my machines sharing one keys file, and the decryption exponent is included with each key. In normal use, each host will have its own keys file, and the third number in each key will be 0 except for the host's own key. \topic{RESTRICTIONS} \noindent Most of the restrictions mentioned in CRYPT also apply to RSA. One additional weakness of RSA is that it operates in ECB (electronic code book) mode, so, in a message that contains a repeated block of plaintext, the plaintext will be enciphered to the same value each time. A block of 0s enciphers to a block of 0s, and a block with all zeros except the low bit will encipher to the same thing. RSA is quite slow. \topic{ACKNOWLEDGMENT} \noindent RSA uses the GNU multiprecision package to do its bignum arithmetic. \topic{AUTHOR} \noindent Richard Schroeppel