Microprocessor for executing enciphered programs

• US 4,168,396 A
• Filed: 10/31/1977
• Issued: 09/18/1979
• Est. Priority Date: 10/31/1977
• Status: Expired due to Term

• Current Assignee: Dallas Semiconductor Corporation (Analog Devices, Inc.)
• Original Assignee: Robert M. Best
• Inventors: Best, Robert M.
• Primary Examiner(s): Buczinski, S. C.
• Application Number:
  US05/846,638
• Time in Patent Office: 687 Days
• Field of Search: 178/22, 364/200, 364/900, 200/61.08, 339/19, 339/37, 339/39, 174/52 PE, 340/147 MD
• US Class Current: 713/190
• CPC Class Codes: G06F 12/1408 by using cryptography for digital transmission H04L9/00
• CPC Class Codes: G06F 21/123 by using dedicated hardware, e.g. dongles, smart cards, cryptographic processors, global positioning systems [GPS] devices
• CPC Class Codes: G06F 21/72 in cryptographic circuits

Abstract

A microprocessor for executing computer programs which have been enciphered during manufacture to deter the execution of the programs in unauthorized computers. This microprocessor deciphers and executes an enciphered program one instruction at a time, through a combination of substitutions, transpositions, and exclusive-OR additions, in which the address of each instruction is combined with the instruction. Each unit may use a unique set of substitutions so that a program that can be executed in one microprocessor can not be run in any other microprocessor.

Claims

1. A device for processing enciphered information comprising:

addressing means for generating a digital address;

means for accepting a portion of enciphered information from storage means at a location selected by said address;

deciphering means for converting said portion of enciphered information into deciphered information by combining said portion of enciphered information with said address, so as to form a substitute portion of deciphered information; and

processing means for executing a plurality of computer instructions as a function of said deciphered information.

2. The device of claim 1, wherein said deciphering means comprises:

first substitution means for transforming said portion of enciphered information into substitute information, said substitution means comprising table means retaining binary numbers arranged in a secret arrangement; and

gate means for combining the bits of said substitute information with bits of said digital address using modulo-2addition, thereby forming combined information.

3. The device of claim 2, further comprising second substitution means for transforming said combined information into second substitute information, said second substitution means comprising table means retaining binary numbers arranged in a secret arrangement.

4. The device of claim 2, wherein said gate means combines a first portion of bits of said digital address with said substitute information, and further comprising second gate means for combining said substitute information with a second portion of the bits of said digital address.

5. The device of claim 1, wherein said deciphering means comprises:

first substitution means for transforming said portion of enciphered information into first substitute information;

second substitution means for transforming said digital address into second substitute information; and

gate means for combining said first substitute information with said second substitute information using modulo-2 addition, thereby forming combined information.

6. The device of claim 1, wherein said deciphering means comprises:

scrambling means for performing a substitution transformation on said digital address, thereby forming a scrambled address; and

gate means for combining the bits of said scrambled address with bits of said portion of enciphered information using module-2 addition, thereby forming combined information.

7. The device of claim 6, wherein said scrambling means comprises:

grouping means for grouping the bits of said digital address into m sets;

first substitution means for transforming said m sets of bits into m sets of substitute bits, said substitution means comprising m tables, each table retaining numbers arranged in a secret arrangement;

transposition means for regrouping said m sets of substitute bits from said first substitution means into n groups, such that one bit from each set is transposed to each group;

second substitution means for transforming said n groups of bits into n groups of substitute bits, said substitution means comprising n tables, each table retaining numbers arranged in a secret arrangement; and

forming means for grouping said n groups of substitute bits from said second substitution means, thereby forming said scrambled address.

8. The device of claim 6, wherein said deciphering means further comprises substitution means for converting said portion of enciphered information into substitute information, said substitution means consisting of table means retaining numbers arranged in a secret arrangement.

9. The device of claim 1 further comprising enciphering means for converting plain information into enciphered information by combining said plain information with said address.

10. A cryptographic apparatus for converting a block of binary information into a product block cipher, said apparatus comprising:

means for accepting said block of binary information and grouping the bits of said block into m sets of n bits each;

first substitution means for transforming said m sets of bits into m sets of substitute bits, said substitution means comprising m tables, each table retaining 2ⁿ different numbers consisting of n bits each, arranged in said table in one secret arrangement out of 2ⁿ ! arrangements;

transposition means for regrouping said m sets of n substitute bits from said first substitution means into n groups of m bits each, such that one and only one bit from each set is transposed to each group;

second substitution means for transforming said n groups of bits into n groups of substitute bits, said substitution means comprising n tables, each table retaining 2^m different numbers consisting of m bits each, arranged in said table in one secret arrangement out of 2^m ! arrangements; and

forming means for grouping said n groups of m bits from said second substitution means to form said product block cipher.

11. A process for deciphering enciphered information comprising the steps of:

generating a digital address;

obtaining a byte of enciphered information from a location specified by said digital address;

combining said byte of enciphered information with said address, thereby forming a substitute byte of deciphered information; and

repeating the above steps for each of a plurality of addresses.

12. The process of claim 11, wherein said combining step comprises:

selecting a first subset of bits from said address;

selecting a second subset of bits from said address;

combining said addressed byte of enciphered information with said first address subset, thereby forming a combined byte;

forming a substitute byte as a function of said combined byte; and

combining said substitute byte with said second address subset, thereby forming a deciphered byte.

13. The process of claim 12, wherein said first combining step comprises:

forming a second substitute byte as a function of said addressed byte; and

adding said second substitute byte to said first address subset, using modulo-2 addition.

14. The process of claim 12, wherein said first combining step comprises:

forming a second substitute byte as a function of said first address subset; and

adding said second substitute byte to said addressed byte, using modulo-2 addition.

15. The process of claim 11, wherein said combining step comprises:

selecting a first subset of bits from said address;

selecting a second subset of bits from said address;

forming a first substitute byte as a function of said first address subset;

forming a second substitute byte as a function of said second address subset;

combining said addressed byte of enciphered information with said first substitute byte, thereby forming a combined byte; and

combining said combined byte with said second substitute byte, thereby forming a deciphered byte.

16. The process of claim 11, wherein said combining step comprises:

substituting a scrambled address for said generated address;

adding said scrambled address to said byte of enciphered information using modulo-2 addition, thereby forming a deciphered byte.

17. The process of claim 16, wherein said substituting step comprises the steps of:

grouping the bits of said generated address into a plurality of sets;

substituting one substitute set of bits for each said set, as determined by a secret arrangement of numbers in a substitution table means;

transposing said substitute bits to form a plurality of groups of bits, such that one bit from each said set is transposed to each said group; and

substituting one substitute group of bits for each said group, as determined by a secret arrangement of numbers in a substitution table means, thereby producing a scrambled address.

18. The process of claim 16 further comprising a step of combining a first portion of said scrambled address with a second portion of said address using modulo-2 addition, thereby producing a doubly scrambled address.

19. The process of claim 11 further comprising a step of enciphering said digital address such that said location is a secret function of said digital address.

20. A process for enciphering plain information comprising the steps of:

generating an address for selecting the location where a byte of enciphered information will be stored during a later storing step;

substituting a scrambled address for said generated address;

adding said scrambled address to one byte of said plain information using modulo-2 addition, thereby forming an enciphered byte;

storing said enciphered byte into a storage means at a location selected by said address; and

repeating the above steps for each of a plurality of plain bytes.

21. A process for enciphering a block of binary information comprising the steps of:

grouping the bits of said block into m sets, each set having n bits, where m and n are both greater than one;

substituting for each said set of n bits, one combination of n bits out of 2ⁿ ! combinations of n bits, as determined by a secret arrangement of said combinations in a substitution table means;

transposing said substitute bits to form n groups of m bits each, such that one and only one bit from each said combination of n bits is transposed to each said group of m bits; and

substituting for each said group of m bits, one combination of m bits out of 2^m ! combinations of m bits, as determined by a secret arrangement of said combinations in a substitution table means, thereby producing a product block cipher.

22. The process of claim 21 for enciphering a 16-bit number, comprising the steps of:

grouping the bits of said number into four 4-bit sets;

substituting a 4-bit substitution cipher for each said set;

transposing the 16 bits from said four substitution ciphers to form four 4-bit groups, such that each group obtains one and only one bit from each said set; and

24. The process of claim 21 for enciphering a 20-bit number, comprising the steps of:

grouping the bits of said number into four 5-bit sets;

substituting a 5-bit substitution cipher for each said set;

transposing the 20 bits from said four substitution ciphers to form five 4-bit groups, such that each group obtains one and only one bit from each said set; and

substituting a 4-bit substitution cipher for each said group, thereby producing a cipher block of 20 bits.

25. The process of claim 21 for enciphering a 25-bit number, comprising the steps of:

grouping the bits of said number into five 5-bit sets;

substituting a 5-bit substitution cipher for each said set;

transposing the 25 bits from said five substitution ciphers to form five 5-bit groups, such that each group obtains one and only one bit from each said set; and

substituting a 5-bit substitution cipher for each said group, thereby producing a cipher block of 25 bits.

27. The apparatus of claim 25, further comprising protective body means of rigid material intimately surrounding said deciphering means, said memory means, and said processing means, for deterring access by anyone to said deciphering means, memory means, and processing means.

23. substituting a 4-bit substitution cipher for each said group, thereby producing a cipher block of 16 bits.

26. A microprocessor apparatus for executing a computer program stored in enciphered form as a plurality of bytes of enciphered information, while protecting the deciphered form of the program, wherein each said byte of enciphered information is identified by a digital address, the apparatus comprising:

deciphering means using alternating steps of substitution and exclusive-OR addition for combining a byte of said enciphered information with its corresponding digital address as a function of substitution information so as to produce a byte of deciphered information;

memory means for storing said substitution information during the production of said byte of deciphered information by said deciphering means; and

processing means for fetching a byte of said deciphered information containing at least a portion of an executable instruction, and for executing said executable instruction, and for addressing a successor byte of enciphered information, said processing means being operative to produce output information from which less than a significant part of said program in deciphered form can be obtained.

28. The apparatus of claim 26, wherein said memory means comprises volatile memory means continuously powered by electrical supply means through a power conductor embedded in said rigid material, wherein damage to said rigid material opens said power conductor and results in erasure of said substitution information.

29. The apparatus of claim 26, wherein said deciphering means, said memory means, and said processing means are constructed as an integrated circuit on a chip of semiconductor material, wherein said chip of semiconductor material comprises a portion of said rigid material, and wherein a second portion of said rigid material consists of opaque glass covering said integrated circuit.

30. The apparatus of claim 26, wherein said deciphering means, said memory means, and said processing means are constructed as a hybrid integrated circuit on chips of semiconductor material, wherein said rigid material includes potting resin in which said hybrid integrated circuit is embedded.

32. The apparatus of claim 30, further comprising protective body means of rigid material intimately surrounding said scrambling means, said deciphering means, and said processing means, for deterring access by anyone to said scrambling means, deciphering means, and processing means.

34. The apparatus of claim 30, wherein said scrambling means comprises substitution table means retaining binary integers arranged in a secret arrangement, wherein a portion of said scrambled address is obtained from said substitution table means by table lookup of a portion of said digital address.

35. The apparatus of claim 30, wherein said scrambling means comprises:

grouping means for grouping the bits of said digital address into m sets;

first substitution means for transforming said m sets of bits into m sets of substitute bits, said substitution means comprising m tables, each table retaining integers arranged in a secret arrangement;

transposition means for regrouping said m sets of substitute bits from said first substitution means into n groups, such that one bit from each set is transposed to each group;

second substitution means for transforming said n groups of bits into n groups of substitute bits, said substitution means comprising n tables, each table retaining integers arranged in a secret arrangement; and

forming means for grouping said n groups of bits from said second substitution means, thereby forming said scrambled address.

36. The apparatus of claim 30, wherein said deciphering means comprises exclusive-OR means for combining said scrambled address with said byte of enciphered information using modulo-2 addition.

37. The apparatus of claim 30, wherein said deciphering means further comprises substitution table means for converting said byte of enciphered information into substitute information.

39. The apparatus of claim 37, wherein the operation of said deciphering means is a function of substitution information, wherein said apparatus further comprises volatile storage means for storing said substitution information during the production of said deciphered information, and wherein said protective body means intimately surrounds said volatile storage means in addition to said memory means, said deciphering means and said processing means.

31. A microprocessor apparatus for executing a computer program stored in enciphered form as a plurality of bytes of enciphered information, while protecting the deciphered form of the program, wherein each said byte of enciphered information is identified by a digital address, the apparatus comprising:

scrambling means for performing a substitution transformation on the digital address of a byte of said enciphered information, so as to produce a scrambled address;

means for deciphering said byte of enciphered information by combining said scrambled address with said byte of enciphered information so as to produce a byte of deciphered information; and

processing means for fetching a byte of said deciphered information containing at least a portion of an executable instruction, for executing said executable instruction, and for addressing a successor byte of enciphered information, said processing means being operative to produce output information from which less than a significant part of said program in deciphered form can be obtained.

33. The apparatus of claim 31, wherein the operation of said scrambling means is a function of substitution information, wherein said apparatus further comprises volatile memory means for storing said substitution information during the production of said scrambled address, and wherein said protective body means intimately surrounds said volatile memory means in addition to said scrambling means, said deciphering means and said processing means.

38. A microprocessor apparatus for executing a computer program stored in enciphered form as a plurality of bytes of enciphered information, while protecting the deciphered form of the program, wherein each said byte of enciphered information is identified by a digital address, the apparatus comprising:

memory means for storing a plurality of bytes of information;

deciphering means for combining a byte of enciphered information obtained from said memory means with its corresponding digital address so as to produce a byte of deciphered information;

processing means for fetching a byte of said deciphered information containing at least a portion of an executable instruction, for executing said executable instruction, and for addressing a successor byte of enciphered information, said processing means being operative to produce output information from which less than a significant part of said program in deciphered form can be obtained; and

protective body means of rigid material intimately surrounding said deciphering means, said memory means, and said processing means, for deterring access by anyone to said deciphering means, memory means, and processing means.

40. A microprocessor apparatus for providing restricted access to data information available to the apparatus in enciphered form, while controlling the amount of the data information output by the apparatus in deciphered form, wherein each byte of said enciphered data information is identified by a digital address, the apparatus comprising:

deciphering means for combining a byte of enciphered information with its corresponding digital address so as to produce a byte of deciphered information;

processing means for fetching and executing a plurality of executable instructions, and for addressing portions of enciphered information responsive to said instructions, so as to restrict the portions of enciphered information which are deciphered by said deciphering means, and for producing output information from said byte of deciphered information; and

protective body means of rigid material intimately surrounding said deciphering means and said processing means, for deterring access by anyone to said deciphering means, processing means, and executable instructions.

41. A cryptographic microprocessor constructed as an integrated circuit chip comprising:

substitution table means included in said chip for cryptographically transforming a byte of an enciphered program of executable instructions obtained from a storage means location to produce a byte of deciphered information;

processing means included in said chip for fetching a byte of said deciphered information containing at least a portion of an executable instruction in said program, and for executing said executable instruction, and for fetching a byte of said deciphered information containing at least a portion of a storage means address, and for addressing a location in said storage means specified by the storage means address to select a byte of said enciphered program for transforming by said table means, the processing means being operative to produce output information;

external bus means for conveying said output information to a location externally of the microprocessor; and

internal bus means included in said chip for conveying said instruction portion and said address portion from said substitution table means to said processing means, the internal bus means being selectively isolated from said external bus means so as to prevent external access through said external bus means to portions of said deciphered information.

43. The microprocessor of claim 41, further comprising:

internal bus means for conveying said instruction portion and said address portion from said second substitution means to said processing means, the internal bus means being selectively isolated from said external bus means so as to prevent external access via said external bus means to portions of said deciphered information.

44. The microprocessor of claim 41, further comprising:

internal bus means for conveying said instruction portion and said address portion from said second substitution means to said processing means; and

buffer means connected to receive said output information from said processing means, and connected to said external bus means, and operating under control of said processing means in either an output state or an isolation state, and for conveying said output information to said external bus means during said output state, and for substantially isolating said internal bus means from said external bus means during said isolation state, said processing means effecting the isolation state of the buffer means during said fetching of a byte of said deciphered information via said internal bus means, thereby preventing external access via said external bus means to said computer program in deciphered form.

45. The microprocessor of claim 41, further comprising memory means for storing said portions of enciphered information.

46. The microprocessor of claim 41, further comprising enciphering means for transforming a portion of unenciphered information into a portion of enciphered information.

48. The microprocessor of claim 46, further comprising memory means for storing said portions of enciphered information.

42. A cryptographic microprocessor for executing a computer program stored in enciphered form as a plurality of portions of enciphered information, while protecting the deciphered form of the program, the apparatus comprising:

first substitution means comprising m tables of integers, the integers in each table having a predetermined permutation, for transforming m portions of said enciphered information into m sets of substitute bits, wherein m is greater than one;

transposition means for regrouping said m sets of substitute bits into n groups of bits and for transposing one bit from each set to each group, wherein n is greater than one;

second substitution means comprising n tables of integers, the integers in each table having a predetermined permutation, for transforming said n groups of bits into n groups of substitute bits, wherein said n groups of substitute bits comprise a portion of deciphered information;

processing means for fetching a byte of said deciphered information containing at least a portion of an executable instruction, and for executing said executable instruction, and for fetching a byte of said deciphered information containing at least a portion of a storage means address, the processing means being operative to produce output information; and

external bus means for conveying said output information externally of the microprocessor.

47. A cryptographic microprocessor for providing limited access to data information available to the apparatus in enciphered form, while controlling the amount of the data information output by the apparatus in deciphered form, the apparatus comprising:

first substitution means comprising m tables of integers, the integers in each table having a predetermined permutation, for transforming portions of said enciphered information into m sets of substitute bits, wherein m is greater than one;

transposition means for regrouping said m sets of substitute bits into n groups of bits and for transposing one bit from each set to each group, wherein n is greater than one;

second substitution means comprising n tables of integers, the integers in each table having a predetermined permutation, for transforming said n groups of bits into n groups of substitute bits, wherein said n groups of substitute bits comprise a portion of deciphered information;

processing means for fetching and executing a plurality of executable instructions, and for addressing portions of said enciphered information responsive to said instructions, and for producing output information from said portion of deciphered information;

external bus means for conveying said output information externally of the apparatus; and

internal bus means selectively isolated from said external bus means, for conveying said portion of decipered information from said second substitution means to said processing means, the isolation between said buses preventing external access via said external bus means to portions of said deciphered information not output by said processing means.

49. A cryptographic apparatus for converting a block of binary information into a product block cipher, the apparatus comprising:

first substitution means comprising m tables of integers, the integers in each table having a predetermined permutation, for transforming m portions of said block into m sets of substitute bits, wherein m is greater than one;

transposition means for regrouping said m sets of substitute bits into n groups of bits and for transposing one bit from each set to each group, wherein n is greater than one; and

second substitution means comprising n tables of integers, the integers in each table having a predetermined permutation, for transforming said n groups of bits into n groups of substitute bits, wherein said n groups of substitute bits comprise said product block cipher.

50. A cryptographic microprocessor apparatus constructed as an integrated circuit chip for executing a computer program of instructions stored in enciphered form in a storage means as a plurality of bytes of enciphered program information, the apparatus comprising:

deciphering means included in said chip for cryptographically transforming a portion of said enciphered program information obtained from a storage means location to produce a portion of deciphered information;

processing means included in said chip for fetching a byte of said deciphered information containing at least a portion of an executable instruction in said program, and for executing said executable instruction, and for fetching a byte of said deciphered information containing at least a portion of a storage means address, and for addressing a location in said storage means specified by the storage means address to select a portion of said enciphered program information for transforming by said deciphering means, the processing means being operative to produce output information;

external bus means for conveying said output information to a location externally of the apparatus; and

internal bus means included in said chip for conveying said instruction portion and said address portion from said deciphering means to said processing means, the internal bus means being selectively isolated from said external bus means so as to prevent external access through said external bus means to portions of said deciphered information.

51. A cryptographic microprocessor apparatus constructed as an integrated circuit chip for executing a computer program of instructions stored in enciphered form in a storage means as a plurality of bytes of enciphered program information, the apparatus comprising:

deciphering means included in said chip for cryptographically transforming a portion of said enciphered program information obtained from a storage means location to produce a portion of deciphered information;

processing means included in said chip for fetching a byte of said deciphered information containing at least a portion of an executable instruction in said program, and for executing said executable instruction, and for fetching a byte of said deciphered information containing at least a portion of a storage means address, and for addressing a location in said storage means specified by the storage means address to select a portion of said enciphered program information for transforming by said deciphering means, the processing means being operative to produce output information;

external bus means for conveying said output information to a location externally of the apparatus;

internal bus means included in said chip for conveying said instruction portion and said address portion from said deciphering means to said processing means; and

buffer means included in said chip and connected to receive said output information from said processing means, and connected to said external bus means, and operating under control of said processing means in either an output state or an isolation state, and for conveying said output information to said external bus means during said output state, and for substantially isolating said internal bus means for said external bus means during said isolation state, said processing means effecting the isolation state of the buffer means during said fetching of a byte of said deciphered information through said internal bus means, thereby preventing external access through said external bus means to said computer program in deciphered form.

52. A cryptographic microprocessor apparatus for executing a computer program of instructions stored in enciphered form as a plurality of bytes of enciphered program information, the apparatus comprising:

deciphering means for cryptographically transforming a portion of said enciphered program information into a portion of deciphered information;

processing means for fetching a byte of said deciphered information containing at least a portion of an executable instruction, and for executing said executable instruction, and for fetching a byte of said deciphered information containing at least a portion of a storage means address, the processing means being operative to produce output information;

external bus means for conveying said output information to a location externally of the apparatus; and

internal bus means for conveying said instruction portion and said address portion from said deciphering means to said processing means, the internal bus means being selectively isolated from said external bus means so as to prevent external access through said external bus means to portions of said deciphered information.

53. A cryptographic microprocessor apparatus for executing a computer program of instructions including executable portions stored in enciphered form as portions of enciphered program information, portions of the program being stored at respective storage means locations, each location having a storage means address, the apparatus comprising:

deciphering means for cryptographically transforming a portion of said enciphered program information from said storage means to produce a portion of deciphered information;

processing means for fetching a byte of said deciphered information containing an executable portion of an instruction in said program, and for executing said instruction, and for fetching a byte containing at least a portion of a specific address in said program, and for addressing in said storage means a location specified by said specific address to select a subsequent portion of said enciphered program information for transforming by said deciphering means; and

internal bus means for conveying said executable portion form said deciphering means to said processing means, the internal bus means being isolated from external access during conveying of said executable portion so as to prevent external access to portions of said program in deciphered form.

54. A cryptographic microprocessor apparatus constructed as an integrated circuit chip for executing a computer program of instructions including executable portions and address portions stored in enciphered form as a plurality of bytes of enciphered program information at respective storage means locations, the apparatus comprising:

deciphering means included in said chip for cryptographically transforming a portion of said enciphered program information from said storage means to produce a portion of deciphered information;

processing means included in said chip for fetching a byte of said deciphered information containing an executable portion of an instruction in said program, and for executing said instruction, and for fetching a byte of said deciphered information containing at least a portion of a deciphered address in said program, and for addressing in said storage means a location specified by said deciphered address to select a subsequent portion of said enciphered program information for transforming by said deciphering means; and

internal bus means included in said chip for conveying said executable portion and said address portion from said deciphering means to said processing means, the internal bus means being isolated from external access during said conveying so as to prevent external access to portions of said program in deciphered form.