Memory transformation apparatus and method

• US 5,095,525 A
• Filed: 06/26/1989
• Issued: 03/10/1992
• Est. Priority Date: 06/26/1989
• Status: Expired due to Term

• Current Assignee: NXP B.V. (NXP Semiconductors NV)
• Original Assignee: Rockwell International Corporation
• Inventors: Almgren, Ted C., Phillips, Gregory A., Mitchell, James M.
• Primary Examiner(s): Hecker, Stuart N.
• Assistant Examiner(s): Whitfield, Michael A.
• Application Number:
  US07/371,167
• Time in Patent Office: 988 Days
• Field of Search: 364/200 MS File, 364/900 MS File, 380/4, 371/2.2, 371/38
• US Class Current: 711/202
• CPC Class Codes: G06F 12/1408 by using cryptography for digital transmission H04L9/00

Abstract

A computer memory is transformed such that a data word to be sent to an address is transformed into a transformed data word, and the address to which it is to be sent is transformed to a transformed address. Such transformations are by inversion and permutation of the memory lines (address or data). The data transformation process depends on the address. The data inverse transformation process also depends on the address, but there is no address inverse transformation process. The invention may be used whenever it is desired to more nearly equalize the use of all the bits of the memory, or to impede unauthorized persons from extracting the virtual addresses and data from the transformed addresses and data.

Claims

1. A transformed data and address storage and retrieval apparatus comprising:

(a) address transformation means comprising;

(1) means for determining, for each virtual address, exactly one corresponding transformed address, each transformed address being determined by exactly one corresponding virtual address;

(b) virtual information manipulation means comprising;

(1) means for inputting, from a processing unit, a virtual word of data and exactly one corresponding virtual address to which the virtual data word is to be outputted from the processing unit;

(2) means for transforming the virtual data word to a transformed word of data, the virtual data word transformation means further comprising means for combining the virtual data word with the transformed address set out in element (a) or with a combination of the virtual address and the transformed address; and

(3) means for outputting, to a memory, the transformed data word and the transformed address; and

(c) transformed information manipulation means comprising;

(1) means for inputting, from the processing unit, a virtual address from which a virtual word of data is to be outputted from the processing unit;

(2) means for outputting, to the memory, a transformed address determined from the virtual address by the address transformation means;

(3) means for inputting, from the memory, a word of data from the transformed address, the data word being considered to be a transformed data word subject to being inverse transformed to a virtual data word;

(4) means for inverse transforming the data word described in element (c)(3) to a virtual data word, the inverse transformation means being the inverse of the transformation means set out in element (b)(2); and

(5) means for outputting, to the processing unit, the virtual data word.

2. The apparatus of claim 1, wherein the transformation means set out in element (b)(2) further comprises means for combining the virtual data word with the virtual address, or with a combination of the virtual address and the transformed address.

3. The apparatus of claim 1, wherein the virtual information manipulation means further comprises means for XORing each bit of the virtual data word with a corresponding inversion control bit.

4. The apparatus of claim 3, further comprising:

(d) means for ANDing together first and second multiplicands, the first multiplicand being a zeroth bit of a key and the second multiplicand being a corresponding bit of the transformed address, thereby forming a zeroth product;

(e) means for ANDing together third and fourth multiplicands, the third multiplicand being a first bit of the key and the fourth multiplicand being a corresponding bit of the transformed address, thereby forming a first product, the transformed address having at least as many bits as the virtual data word or the transformed data word set out in element (i);

(f) means for ANDing together fifth and sixth multiplicands, the fifth multiplicand being a second bit of the key and the sixth multiplicand being a corresponding bit of the transformed address, thereby forming a second product;

(g) means for ORing together zeroth, first, and second addends, the zeroth addend being the zeroth product set out in element (d), the first addend being the first product set out in element (e) and the second addend being the second product set out in element (f), thereby forming a sum;

(h) means for XORing the sum set out in element (g) with a third bit of the key, thereby forming an inversion control bit; and

(i) means for selectively inverting a bit of the virtual data word or of the transformed data word by XORing the bit of the data word with the inversion control bit set out in element (h).

5. The apparatus of claim 4, wherein the data word has k bits, and wherein the means for forming an ith inversion control bit, where 0≦

i≦

k-1, comprises;

(j) means for ANDing together first and second ith multiplicands, the first ith multiplicand being the zeroth bit of the key and the second ith multiplicand being the xth bit of the transformed address or of a portion of the transformed address, where 0≦

x≦

k-1 and x=i+1<

k and x=i+1-k if i+1≧

k, thereby forming a zeroth ith product;

(k) means for ANDing together third and fourth ith multiplicands, the third ith multiplicand being the first bit of the key and the fourth ith multiplicand being the yth bit of the transformed address or of a portion of the transformed address, where 0≦

y≦

k-1 and y=i+2 if i+2<

k and y=i+2-k if i+2≧

k, thereby forming a first ith product;

(l) means for ANDing together fifth and sixth ith multiplicands, the fifth ith multiplcand being the second bit of the key and the sixth ith multiplicand being the zth bit of the transformed address or of a portion of the transformed address, where 0≦

z≦

k-1 and z=i+3 if i+3<

k and z=i+3-k if i+3≧

k, thereby forming a second ith product;

(m) means for ORing together zeroth, first, and second ith addends, the zeroth ith addend being the zeroth ith product set out in element (j), the first ith addend being the first ith product set out in element (k), and the second ith addend being the second ith product set out in element (l), thereby forming an ith sum;

(n) means for XORing the ith sum set out in element (m) with the third bit of the key, thereby forming an ith inversion control bit; and

(o) means for selectively inverting an ith bit of the virtual data word or of the transformed data word by XORing the ith bit of the data word with the ith inversion control bit set out in element (n).

6. A transformed memory data and address storage and retrieval apparatus comprising:

(a) address transformation means comprising;

(1) means for determining, for each virtual address, exactly one corresponding transformed address, wherein each transformed address is determined by exactly one corresponding virtual address;

(b) virtual information manipulation means comprising;

(1) means for inputting, from a processing unit, a virtual word of data and exactly one corresponding virtual address to which the virtual data word is to be outputted from the processing unit;

(2) means for determining, for each virtual data word, exactly one corresponding transformed data word, wherein each transformed data word is determined by exactly one corresponding virtual data word;

(c) transformed information manipulation means comprising;

(1) means for inputting, from the processing unit, a virtual address from which a virtual word of data is to be outputted from the processing unit;

(2) means for outputting, to a memory, a transformed address determined from the virtual address by the address transformation means;

(3) means for inputting, from the memory, a word of data from the transformed address, the data word being considered to be a transformed data word subject to being inverse transformed to a virtual data word;

(4) means for inverse transforming the data word described in element (c)(3) to a virtual data word, the inverse transformation means being the inverse of the transformation means set out in element (b)(2); and

(5) means for outputting, to the processing unit, the virtual data word;

wherein;

(i) each transformed address and corresponding virtual address comprise an equal number of bits and the address transformation means further comprises means for permuting the bits of the virtual address;

or

(ii) each transformed data word and corresponding virtual data word comprise an equal number of bits and the virtual data transformation means further comprises means for permuting the bits of the virtual data word;

or

(iii) each transformed address and corresponding virtual address comprise an equal number of bits and the address transformation means further comprises means for permuting the bits of the virtual address, and each transformed data word and corresponding virtual data word comprise an equal number of bits and the virtual data transformation means further comprises means for permuting the bits of the virtual data word.

7. The apparatus of claim 6, wherein:

(d) the address transformation means further comprises means for inverting selected bits of the virtual address;

or

(e) the virtual data word transformation means further comprises means for inverting selected bits of the virtual data word;

or

(f) the address transformation means further comprises means for inverting selected bits of the virtual address, and the virtual data word transformation means further comprises means for inverting selected bits of the virtual data word.

8. The apparatus of claim 7, wherein the virtual information manipulation means further comprises:

(g) means for permuting the bits of the virtual data word depending on the virtual address; and

(h) means for inverting the bits of the virtual data word depending on the transformed address.

9. The apparatus of claim 7, wherein the virtual information manipulation means further comprises means for inverting the bits of the virtual address, the virtual address bit inverting means comprising means for XORing the bits of the virtual address with corresponding bits of a key or a portion of a key.

10. The apparatus of claim 6, wherein the virtual information manipulation means further comprises means for determining, for each virtual data word, exactly one corresponding transformed data word, the determining means comprising:

(d) means for adding a data permutation portion of a key to

(1) the virtual address,

(2) the transformed address,

(3) a portion of either of the foregoing, or

(4) a combination of any of the foregoing, thereby forming a sum;

(e) means for dividing a dividend by a divisor, the dividend being the sum set out in element (d) and the divisor being the number of bits of the virtual data word, thereby forming a remainder; and

(f) means for permuting the bits of the virtual data word according to the remainder;

each transformed data word being determined by exactly one corresponding virtual data word, and each transformed data word and corresponding virtual data word comprising an equal number of bits.

11. A transformed memory data and address storage and retrieval method comprising:

(a) an address transformation step comprising;

(1) the step of determining, for each virtual address, exactly one corresponding transformed address, each transformed address being determined by exactly one corresponding virtual address;

(b) a virtual information manipulation step comprising;

(1) the step of inputting, from a processing unit, a virtual word of data and exactly one corresponding virtual address to which the virtual data word is to be outputted from the processing unit;

(2) the step of transforming the virtual data word to a transformed word of data, the virtual data word transformation step further comprising the step of combining the virtual data word with the transformed address set out in step (a) or with a combination of the virtual address and the transformed address; and

(3) the step of outputting, to a memory, the transformed data word and the transformed address; and

(c) a transformed information manipulation step comprising;

(1) the step of inputting, from the processing unit, a virtual address from which a virtual word of data is to be outputted from the processing unit;

(2) the step of outputting, to the memory, a transformed address determined from the virtual address by the address transformation step;

(3) the step of inputting, from the memory, a word of data from the transformed address, the data word being considered to be a transformed data word subject to being inverse transformed to a virtual data word;

(4) the step of inverse transforming the data word described in step (c)(3) to a virtual data word, the inverse transformation step being the inverse of the transformation step set out in step (b)(2); and

(5) the step of outputting, to the processing unit, the virtual data word.

12. The method of claim 11, wherein the transformation step set out in step (b)(2) further comprises the step of combining the virtual data word with the virtual address, or with a combination of the virtual address and the transformed address.

13. The method of claim 11, wherein the virtual information manipulation step further comprises the step of XORing each bit of the virtual data word with a corresponding inversion control bit.

14. The method of claim 13, further comprising:

(d) the step of ANDing together first and second multiplicands, the first multiplicand being a zeroth bit of a key and the second multiplicand being a corresponding bit of the transformed address, thereby forming a zeroth product;

(e) the step of ANDing together third and fourth multiplicands, the third multiplicand being a first bit of the key and the fourth multiplicand being a corresponding bit of the transformed address, thereby forming a first product, the transformed address having at least as many bits as the virtual data word or the transformed data word set out in step (i);

(f) the step of ANDing together fifth and sixth multiplicands, the fifth multiplicand being a second bit of the key and the sixth multiplicand being a corresponding bit of the transformed address, thereby forming a second product;

(g) the step of ORing together zeroth, first, and second addends, the zeroth addend being the zeroth product set out in step (d), the first addend being the first product set out in step (e), and the second addend being the second product set out in step (f), thereby forming a sum;

(h) the step of XORing the sum set out in step (g) with a third bit of the key, thereby forming an inversion control bit; and

(i) the step of selectively inverting a bit of the virtual data word or of the transformed data word by XORing the bit of the data word with the inversion control bit set out in step (h).

15. The method of claim 14, wherein the data word has k bits, and wherein the step of forming an ith inversion control bit, where 0≦

i≦

k-1, comprises;

(j) the step of ANDing together first and second ith multiplicands, the first ith multiplicand being the zeroth bit of the key and the second ith multiplicand being the xth bit of the transformed address or of a portion of the transformed address, where 0≦

x≦

k-1 and x=i+1 if i+1<

k and x=i+1-k if i+1≧

k, thereby forming a zeroth ith product;

(k) the step of ANDing together third and fourth ith multiplicands, the third ith multiplicand being the first bit of the key and the fourth ith multiplicand being the yth bit of the transformed address or of a portion of the transformed address, where 0≦

y≦

k-1 and y=i+2 if i+2<

k and y=i+2-k if i+2≧

k, thereby forming a first ith product;

(l) the step of ANDing together fifth and sixth ith multiplicands, the fifth ith multiplicand being the second bit of the key and the sixth ith multiplicand being the zth bit of the transformed address or of a portion of the transformed address, where 0≦

z≦

k-1 and z=i+3 if i+3<

k and z=i+3-k if i+3≧

k, thereby forming a second ith product;

(m) the step of ORing together zeroth, first, and second ith addends, the zeroth ith addend being the zeroth ith product set out in step (j), the first ith addend being the first ith product set out in step (j), and the second ith addend being the second ith product set out in step (l), thereby forming an ith sum;

(n) the step of XORing the ith sum set out in step (m) with the third bit of the key, thereby forming an ith inversion control bit; and

(o) the step of selectively inverting an ith bit of the virtual data word or of the transformed data word by XORing the ith bit of the data word with the ith inversion control bit set out in step (n).

16. A transformed memory data and address storage and retrieval method comprising:

(a) an address transformation step comprising;

(1) the step of determining, for each virtual address, exactly one corresponding transformed address, wherein each transformed address is determined by exactly one corresponding virtual address;

(b) a virtual information manipulation step comprising;

(1) the step of inputting, from a processing unit, a virtual word of data and exactly one corresponding virtual address to which the virtual data word is to be outputted from the processing unit;

(2) the step of determining, for each virtual data word, exactly one corresponding transformed data word, wherein each transformed data word is determined by exactly one corresponding virtual data word;

(c) a transformed information manipulation step comprising;

(1) the step of inputting, from the processing unit, a virtual address from which a virtual word of data is to be outputted from the processing unit;

(2) the step of outputting, to a memory, a transformed address determined from the virtual address by the address transformation step;

(3) the step of inputting, from the memory, a word of data from the transformed address, the data word being considered to be a transformed data word subject to being inverse transformed to a virtual data word;

(4) the step of inverse transforming the data word described in step (c)(3) to a virtual data word, the inverse transformation step being the inverse of the transformation step set out in step (b)(2); and

(5) the step of outputting, to the processing unit, the virtual data word;

wherein;

(i) each transformed address and corresponding virtual address comprise an equal number of bits and the address transformation step further comprises the step of permuting the bits of the virtual address;

or

(ii) each transformed data word and corresponding virtual data word comprise an equal number of bits and the virtual data transformation step further comprises the step of permuting the bits of the virtual data word;

or

(iii) each transformed address and corresponding virtual address comprise an equal number of bits and the address transformation step further comprises the step of permuting the bits of the virtual address, and each transformed data word and corresponding virtual data word comprise an equal number of bits and the virtual data transformation step further comprises the step of permuting the bits of the virtual data word.

17. The method of claim 16, wherein:

(d) the address transformation step further comprises the step of inverting selected bits of the virtual address;

or

(e) the virtual data transformation step further comprises the step of inverting selected bits of the virtual data word;

or

(f) the address transformation step further comprises the step of inverting selected bits of the virtual address, and the virtual data transformation step further comprises the step of inverting selected bits of the virtual data word.

18. The method of claim 17, wherein the virtual information manipulation step further comprises:

(g) the step of permuting the bits of the virtual data word depending on the virtual address; and

(h) the step of inverting the bits of the virtual data word depending on the transformed address.

19. The method of claim 17, wherein the virtual information manipulation step further comprises the step of inverting the bits of the virtual address, the virtual address bit inverting step comprising the step of XORing the bits of the virtual address with corresponding bits of a key or a portion of a key.

20. The method of claim 16, wherein the virtual information manipulation step further comprises the step of determining, for each virtual data word, exactly one corresponding transformed data word, the determining step comprising:

(d) the step of adding a data permutation portion of a key to

(1) the virtual address,

(2) the transformed address,

(3) a portion of either of the foregoing, or

(4) a combination of any of the foregoing, thereby forming a sum;

(e) the step of dividing a dividend by a divisor, the dividend being the sum set out in step (d) and the divisor being the number of bits of the virtual data word, thereby forming a remainder; and

(f) the step of permuting the bits of the virtual data word according to the remainder;

each transformed data word being determined by exactly one corresponding virtual data word, and each transformed data word and corresponding virtual data word comprising an equal number of bits.