Encryption-decryption circuit and method of operation

An encryption-decryption circuit for encrypting and decrypting data. The encryption-decryption circuit comprises: 1) an N-bit shift register for storing and shifting an N bit keyword; 2) a first exclusive-OR gate array for receiving M bits from the N-bit shift register and generating a one-bit exclusive-OR result that is shifted into an input of the N-bit shift register; and 3) a second exclusive-OR gate array comprising K exclusive-OR gates, each of the K exclusive-OR gates receiving one of K bits from the N-bit shift register and one of K data bits from a received K-bit data word and generating therefrom an exclusive-OR result. The K exclusive-OR gates thereby produce one of: i) a K-bit encrypted data word and ii) a K-bit unencrypted data word.

TECHNICAL FIELD OF THE INVENTION

The present invention relates generally to data encoding and decoding circuits and, in particular, to a simple encoding and decoding circuit for use in a microcontroller or similar processing circuit having limited memory and processing power.

BACKGROUND OF THE INVENTION

A wide array of consumer and business electronic devices can be upgraded by receiving (i.e., downloading) application programs and data files from an external network, such as the Internet. Initially, this method of upgrading electronic devices was limited primarily to personal computers. Increasingly, however, software upgrades can be applied to ever smaller devices, including cell phones, handheld computers (such as a PalmPilot™) MP3 players, and the like.

Quite often, application programs and data files are encrypted prior to transmission and then decrypted by the downloading device. Encryption is used to prevent the downloaded application programs and data files from being corrupted and/or tampered with during transmission. The application programs and data files are encrypted along with redundancy checksum values derived from the application programs and data files. If the redundancy checksum values are not correct after decryption, the downloaded software may be corrupted and is discarded. Encryption also is used to prevent the downloaded application programs and data files from being illegally copied onto unauthorized devices. Many encryption systems use an embedded encryption key that is unique to each downloading device. Unauthorized devices do not have the correct encryption key and, therefore, cannot decrypt the encrypted downloaded software.

Conventional encryption and decryption techniques require a good deal of memory and processing power. For example, the popular Rivest-Shamir-Adleman (RSA) public key encryption algorithm (and similar cyphers) use large binary numbers (i.e., 1024 bits) and exponential mathematics to encrypt and decrypt data. This requires a great deal of random access memory (RAM) to hold large numbers and also requires wide (i.e., 64 bits or greater) data processors to perform the calculations in a reasonably short period of time.

Unfortunately, many of the smaller devices (e.g. cell phones, handheld computers, MP3 players) that are capable of receiving software upgrades are controller by small (i.e., 8 bit or 16 bit) microcontrollers containing small FLASH memories. These types of devices do not have the required memory size and processing throughput necessary to implement conventional encryption and decryption schemes, such as the RSA public key encryption algorithm.

Therefore, there is a need in the art for improved encryption and decryption systems that do not require large memories and high processing throughput. In particular, there is a need for an encryption and decryption system for use with 8-bit and 16-bit microprocessors, microcontrollers, and similar small scale processors.

SUMMARY OF THE INVENTION

To address the above-discussed deficiencies of the prior art, it is a primary object of the present invention to provide an encryption-decryption circuit for encrypting and decrypting data. According to an advantageous embodiment of the present invention, the encryption-decryption circuit comprises: 1) an N-bit shift register for storing and shifting an N bit keyword; 2) a first exclusive-OR gate array capable of receiving M bits from the N-bit shift register and generating a one-bit exclusive-OR result that is shifted into an input of the N-bit shift register; and 3) a second exclusive-OR gate array comprising K exclusive-OR gates, each of the K exclusive-OR gates capable of receiving one of K bits from the N-bit shift register and one of K data bits from a received K-bit data word and generating therefrom an exclusive-OR result, the K exclusive-OR gates thereby producing one of: i) a K-bit encrypted data word and ii) a K-bit unencrypted data word.

The present invention advantageously allows encryption and decryption operations to be performed using only binary (i.e. base 2) mathematics and operators. In an embodiment in which N equals 128 bits, a shift register of only 16 bytes is required and the number of possible keywords is approximately 3.4×1038.

According to one embodiment of the present invention, the encryption-decryption circuit further comprises a N-bit buffer for storing the N-bit keyword.

According to another embodiment of the present invention, the N-bit keyword is unique to the encryption-decryption circuit.

According to still another embodiment of the present invention, the encryption-decryption circuit further comprises a N×M switch capable of coupling M selected ones of the N bits in the N-bit shift register to the first exclusive-OR gate array.

According to yet another embodiment of the present invention, the encryption-decryption circuit further comprises a N×K switch capable of coupling K selected ones of the N bits in the N-bit shift register to inputs of the K exclusive-OR gates in the second exclusive-OR gate array.

According to a further embodiment of the present invention, the second exclusive-OR gate array further comprises adder circuitry capable of adding a K-bit value to the K-bit encrypted data word.

According to a still further embodiment of the present invention, the second exclusive-OR gate array further comprises subtraction circuitry capable of subtracting a K-bit value from the received K-bit data word prior to generation of the exclusive-OR result by the second exclusive-OR gate array.

DETAILED DESCRIPTION OF THE INVENTION

FIG. 1illustrates exemplary microcontroller100, which contains an encryption-decryption circuit according to a first embodiment of the present invention. Microcontroller100comprises processor core logic and FLASH memory circuit110and encryption and decryption circuit120. Processor core logic and FLASH memory circuit110executes the primary functions of microcontroller100. Encryption and decryption circuit120is used to encrypt and decrypt data.

According to an advantageous embodiment of the present invention, microcontroller100is able to receive encrypted data, such as object code, from an external source, such as the Internet or an external processing system to which microcontroller100is connected. Advantageously, microcontroller100may also send encrypted data to the external source. Processor core logic and FLASH memory circuit110controls encryption and decryption circuit120using the control lines LOAD, SHIFT, ENCRYPT/DECRYPT (E/D), and the data buses DATA IN and DATA OUT. When the ENCRYPT/DECRYPT is set to Encrypt Mode, processor core logic and FLASH memory circuit110is operable to transfer unencrypted data to encryption and decryption circuit120on the K-bit DATA IN bus and to receive encrypted data from encryption and decryption circuit120on the K-bit DATA OUT bus. When the ENCRYPT/DECRYPT is set to Decrypt Mode, processor core logic and FLASH memory circuit110is operable to transfer encrypted data to encryption and decryption circuit120on the K-bit DATA IN bus and to receive unencrypted data from encryption and decryption circuit120on the K-bit DATA OUT bus.

Encryption and decryption circuit120comprises N-bit shift register122, N-bit keyword buffer124, exclusive-OR (XOR) gate array126, and exclusive-OR (XOR) +/− Y gate array127. N-bit keyword buffer124contains an N-bit binary data key that is unique to microcontroller100. The key may be broken into two N/2-bit keys, one of which is held within microcontroller100, such as a serial number. This is used to limit the distribution of the software to only one target machine (such as a license upgrade).

Processor core logic and FLASH memory circuit110loads the key into N-bit shift register122by enabling the LOAD signal. XOR gate array126receives M arbitrary bits from N-bit shift register122and determines a single bit exclusive-OR result of all M bits. Thus, the single bit XOR result, f(b), is given by:
f(b)=Ba⊕Bb⊕Bc⊕ . . . ⊕Bg
where Ba, Bb, Bc, . . . , and Bg are the M arbitrarily selected ones of bits B1, B2, B3, . . . , Bn from N-bit shift register122. The XOR result, f(b), is then input to N-bit shift register122. Processor core logic and FLASH memory circuit110shifts the N binary bits in N-bit shift register122using the SHIFT control signal.

For each shift of N-bit shift register122, K arbitrary bits from N-bit shift register122are also applied to XOR +/− Y gate array127. XOR +/− Y gate array127comprises K exclusive-OR gates, each of which has two inputs and one output. Each of the K arbitrary bits from N-bit shift register122is XORed with one of the K bits on the DATA IN bits to produce one of the K bits on the DATA OUT bus. Since exclusive OR is a reversible operation if the output (i.e., result) and one input are known, the present invention has the advantage of being symmetrical between encryption and decryption.

Thus, unencrypted data may be encrypted by exclusive-ORing with the K bits from N-bit shift register122. The encrypted data may then be decrypted by exclusive-ORing with the K bits from N-bit shift register122. The data pattern in N-bit shift register is completely deterministic given a known key and the number of shifts.

According to an advantageous embodiment, the K bit binary value Y may be added after the XOR operation during Encryption Mode and K bit binary value Y may be subtracted prior to the XOR operation during Decryption Mode. In an exemplary embodiment of the present invention, Y=0, so that only the XOR function is implemented by XOR +/− Y gate array127.

According to an advantageous embodiment of the present invention, the value of K is the same as the data width of processor core logic and FLASH memory circuit110. Thus, if microcontroller100is an 8-bit processing device, K=8, if microcontroller110is a 16-bit processing device, K=16, and so forth.

By way of example, in a representative microcontroller, N-bit shift register122may be a 128 shift register, M may be 25, and K may be 16. Thus, the 128 bits from 128 bit keyword buffer124may be loaded into shift register122and shifted S times to an arbitrary starting point. On each shift, 25 arbitrary bits from shift register122are exclusive-ORed (XORed) together to produce a one bit result that is shifted into shift register122. Once the starting point is reached, 16 arbirtrary bits from shift register122are XORed with the 16 bits from the DATA IN bus to produce 16 encrypted bits on the DATA OUT bus. Each subsequent shift of shift register122produces a new 16 bit pattern that is XORed with the next 16 bit data word on the DATA In bus, until all data words are encrypted.

A similar operation occurs during decryption. The 128 bits from 128 bit keyword buffer124are loaded into shift register122and shifted S times to the arbitrary starting point, just as during encryption. On each shift, 25 arbitrary bits from shift register122are exclusive-ORed (XORed) together to produce a one bit result that is shifted into shift register122. Once the starting point is reached, 16 arbitrary bits from shift register122are XORed with the 16 encrypted data bits from the DATA IN bus to produce 16 unencrypted bits on the DATA OUT bus. Each subsequent shift of shift register122produces a new 16 bit pattern that is XORed with the next 16 bit encrypted data word on the DATA IN bus, until all encrypted data words are unencrypted (decrypted).

FIG. 2illustrates exemplary microcontroller200containing an encryption-decryption circuit according to a second embodiment of the present invention. Microcontroller200is similar to microcontroller100inFIG. 1in most respects. Microcontroller200comprises processor core logic and FLASH memory circuit210and encryption-decryption circuit220. Processor core logic and FLASH memory circuit210executes the primary functions of microcontroller200. Encryption and decryption circuit220is used to encrypt and decrypt data.

Processor core logic and FLASH memory circuit210controls encryption and decryption circuit220using the control lines LOAD, SHIFT, and ENCRYPT/DECRYPT (E/D), the switch select control lines, SWITCH SELECT, and the data buses DATA IN and DATA OUT. When the ENCRYPT/DECRYPT is set to Encrypt Mode, processor core logic and FLASH memory circuit210is operable to transfer unencrypted data to encryption-decryption circuit220on the K-bit DATA IN bus and to receive encrypted data from encryption and decryption circuit220on the K-bit DATA OUT bus. When the ENCRYPT/DECRYPT is set to Decrypt Mode, processor core logic and FLASH memory circuit210is operable to transfer encrypted data to encryption and decryption circuit220on the K-bit DATA IN bus and to receive unencrypted data from encryption and decryption circuit220on the K-bit DATA OUT bus.

The primary difference between microcontroller200and microcontroller100inFIG. 1is that the M bits applied to XOR gate array226are not fixed, but rather are selectable by the SWITCH SELECT control signals using N×M switch225. Similarly, the K bits applied to XOR gate array228are not fixed, but rather are selectable by the SWITCH SELECT control signals using N×K switch225. Switch225and switch227are optional and may be implemented to provide additional levels of security.

FIG. 3depicts flow diagram300, which illustrates the operation of the exemplary encryption-decryption circuit according to the principles of the present invention. Initially, microcontroller200loads the N bit keyword into shift register222(process step305). Optionally, microcontroller200sets SWITCH SELECT signals for one or both of N×M switch225and N×K switch227if the switches are implemented (process step310). Next, microcontroller200shifts the bits in shift register222S times to establish a starting point (process step310). Then, microcontroller200applies the first K bit data word to XOR +/− Y gate array228via the DATA IN bus and reads the result from the DATA OUT bus (process step320). Finally, microcontroller200shifts the data in shift register222and applies the next K bit data word to XOR +/− Y gate array228via the DATA IN bus and reads the result from the DATA OUT bus (process step325). Microcontroller200repeats step325until all data is encrypted or decrypted (process step330).