Orderly enumeration of nonsingular binary matrices applied to text encryption

ABSTRACT

Nonsingular binary matrices of order N, i.e., nonsingular over the field {0, 1}, and an initial segment of the natural numbers are placed in one-to-one correspondence. Each natural number corresponds to two intermediate vectors. These vectors are mapped into a nonsingular binary matrix. Examples of complete enumeration of all 2 × 2 and 3 × 3 nonsingular binary matrices were produced by mapping the intermediate vectors to the matrices. The mapping has application to the Vernam encipherment method using pseudorandom number sequences. A bit string formed from bytes of text of a data encryption key can be used as a representation of a natural number. This natural number is transformed to a nonsingular binary matrix. Key leverage is obtained by using the matrix as a “seed” in a shift register sequence pseudorandom number generator.

REFERENCES

• 1: Bright, H.S., and Enison, R.L. Cryptography using modular software elements. Proc. AFIPS 1976 NCC, Vol. 45, AFIPS Press, Montvale, N.J., pp. 113-123.
• 2: Phillip J. Chase, Algorithm 382: combinations of M out of N objects [G6], Communications of the ACM, v.13 n.6, p.368, June 1970 [doi>10.1145/362384.362502]
• 3: Gideon Ehrlich, Algorithm 466: four combinatorial algorithm [G6], Communications of the ACM, v.16 n.11, p.690-691, Nov. 1973 [doi>10.1145/355611.362541]
• 4: F. M. Ives, Permutation enumeration: four new permutation algorithms, Communications of the ACM, v.19 n.2, p.68-72, Feb. 1976 [doi>10.1145/359997.360002]
• 5: Jerome Kurtzberg, Algorithm 94: Combination, Communications of the ACM, v.5 n.6, p.344, June 1962 [doi>10.1145/367766.368162]
• 6: Lehmer, D.H. The machine tools of combinatorics. In Applied Combinatorial Mathematics, E.F. Beckenback, Ed., Wiley, New York, 1964.
• 7: T. G. Lewis , W. H. Payne, Generalized Feedback Shift Register Pseudorandom Number Algorithm, Journal of the ACM (JACM), v.20 n.3, p.456-468, July 1973 [doi>10.1145/321765.321777]
• 8: C. N. Liu , D. T. Tang, Algorithm 452: enumerating combinations of m out of n objects [G6], Communications of the ACM, v.16 n.8, p.485, Aug. 1973 [doi>10.1145/355609.362322]
• 9: James Marting, Security, Accuracy, and Privacy in Computer Systems, Prentice Hall PTR, Upper Saddle River, NJ, 1973
• 10: Charles J. Mifsud, Algorithm 154: combination in lexicographical order, Communications of the ACM, v.6 n.3, p.103, March 1963 [doi>10.1145/366274.366309]
• 11: Shannon, C.E. The communication theory of secrecy systems. Bell. Syst. Tech. J. 28 (Oct. 1949), 656-715
• 12: Tang, D.T., and Liu, C.N. Distance-2 cyclic chaining of constantweight codes. IEEE Trans. Comptrs. C-22, 2 (1973), 176-180.
• 13: Robert G. Tantzen, Algorithm 199: conversions between calendar date and Julian day number, Communications of the ACM, v.6 n.8, p.444, Aug. 1963 [doi>10.1145/366707.390020]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

Additional Classification:
  E. Data
  E.3 DATA ENCRYPTION

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
  G.3 PROBABILITY AND STATISTICS
      Subjects: Random number generation

General Terms:
Design, Performance, Security, Theory

Keywords:
Vernam, binary matrices, combinations, combinatorics, encryption, feedback shift register sequences, nonsingular matrices, pseudorandom numbers, random numbers