text: The use of inexpensive microprocessors to control home appliances, answering machines, automotive ignition systems, security systems as well as hosts of other items is becoming common place. This is due in large part to the continuing decline in the cost of microprocessors, e.g., 8 bit microprocessors. Frequently, such 8 bit microprocessors cost only a small fraction of the sales price of an appliance.
  With the common place use of microprocessor based control devices, a fair amount of emphasis is now being placed on controlling such devices either remotely or through the use of a centralized controller, e.g., in the case of home systems.
  To avoid the need to hardwire devices to controllers, the use of existing power lines as a communication medium and/or wireless communication techniques, e.g., the use of radio signals, are often favored for use with home control and other types of systems. Unfortunately, individuals who are not authorized to access such systems often have the same degree of access to the communications medium used, e.g., the radio signals or power lines, that authorized individuals have. This poses a security problem.
  Accordingly, there is a need to add encryption and/or authentication capabilities to systems, e.g., home control systems, auto ignition systems, answering machines, etc., where an unauthorized individual has or can gain easy access to the communications medium used to communicate messages to a remotely controlled device. Furthermore, it is desirable that implemented security methods be safe from replay attacks where an unauthorized individual attempts to gain access by replaying a previously transmitted, and all too frequently recorded, message.
  The problem of adding security to microprocessor and micro-controller controlled devices, e.g., home appliance devices, is frequently compounded by cost pressures. For cost reasons, relatively inexpensive microprocessors and/or micro-controllers such as, e.g., the eight bit Intel.TM. 8051, are often used to control home appliance devices. Such microprocessors offer relatively few resources, e.g., 1 KB flash EPROM, 64 bytes of program RAM, 64 bytes of data RAM, 128 bytes of EEPROM and an instruction rate of 1 MHz or less. Of these resources, after the communication and control applications which are necessary to performing the primary control task of the microprocessor are accounted for, there is very little left, particularly in the case of memory, which can be used for the implementation of security schemes.
  Various security algorithms which currently exist include the SAFER-SK.TM. family of algorithms which offer a good degree of security. Unfortunately, the SAFER-SK algorithms require 512 bytes of ROM to implement two substitution boxes in addition to another 1-2 KB bytes of memory to store the algorithms code. Getting that amount of memory from the inexpensive microprocessors which are preferred for use in home appliance applications is impractical given the need to allocate memory to the controller's primary functions as well.
  TEA, which stands for Tiny Encryption Algorithm, is another well known security algorithm. While TEA.TM. is relatively tiny when considered in the context of the memory and processing resources of a 32 bit microprocessor, it is not sufficiently small for implementation on an 8 bit micro-controller which is responsible for performing other tasks as well. Furthermore, TEA involves the use of processing operations that are difficult to implement using 8 bit microprocessors.
  Accordingly, the memory and/or processing requirements of existing encryption algorithms make them unsuitable for low cost applications where resources are limited to the memory and processing capability that is incorporated into an 8 bit controller which must also perform other tasks in addition to an encryption/authentication task.
  In view of the above discussion, it is clear that there is a need for encryption and/or authentication methods which can be implemented using relatively little in terms of memory and/or processing capability resources. Furthermore, it is desirable that such methods be capable of being implemented using relatively inexpensive, e.g., 8 bit, microprocessors and/or micro-controllers dedicated to performing other functions in addition to the encryption/authentication function. It is also desirable that such methods be safe from replay attacks where an old message or command is played back in an attempt to gain unauthorized access to a device or to have a device perform an unauthorized operation.