article

Free access

Orderly enumeration of nonsingular binary matrices applied to text encryption

Authors:

W. H. Payne,

K. L. McMillenAuthors Info & Claims

Communications of the ACM, Volume 21, Issue 4

Pages 259 - 263

https://doi.org/10.1145/359460.359464

Published: 01 April 1978 Publication History

PDF eReader

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.

Google Scholar

[2]

Chase, P.J. Algorithm 382. Combinations of m out of n objects. Comm. ACM 13, 6 (June 1970), 368.

Digital Library

Google Scholar

[3]

Ehrlich, G. Algorithm 466. Four combinatorial algorithms. Comm. ACM 16, II (Nov. 1973), 690-691.

Digital Library

Google Scholar

[4]

Ives, R.M. Permutation enumeration: Four new algorithms. Comm. ACM 19, 2 (Feb. 1976), 68-72.

Digital Library

Google Scholar

[5]

Kurtzberg, J. Algorithm 94. Combination. Comm. A CM 5, 6 (June 1962), 344.

Digital Library

Google Scholar

[6]

Lehmer, D.H. The machine tools of combinatorics. In Applied Combinatorial Mathematics, E.F. Beckenback, Ed., Wiley, New York, 1964.

Google Scholar

[7]

Lewis, T.G., and Payne, W.H. Generalized feedback shift register pseudorandom number generator. J A CM 20, 3 (July 1973), 456-468.

Digital Library

Google Scholar

[8]

Liu, C.N., and Tang, D.T. Algorithm 452. Enumerating combinations ofm out ofn objects. Comm. ACM 16, 8 (Aug. 1973), 485.

Digital Library

Google Scholar

[9]

Martin, J. Security, Accuracy, and Privacy in Computer Systems. Prentice-Hall, Englewood Cliffs, N.J., 1973.

Digital Library

Google Scholar

[10]

Mifsud, C.J. Algorithm 154. Combination in lexicographical order. Comm. ACM 6, 3 (March 1963), 103.

Digital Library

Google Scholar

[11]

Shannon, C.E. The communication theory of secrecy systems. Bell. Syst. Tech. J. 28 (Oct. 1949), 656-715

Crossref

Google Scholar

[12]

Tang, D.T., and Liu, C.N. Distance-2 cyclic chaining of constantweight codes. IEEE Trans. Comptrs. C-22, 2 (1973), 176-180.

Digital Library

Google Scholar

[13]

Tantzen, R.G. Algorithm 199. Conversion between calendar date and Julian day number. Comm. ACM 6, 8 (August 1963), 444.

Digital Library

Google Scholar

Cited By

View all

Feng WZhang ZJia ZFu Z(2006)Reversible Sketch Based on the XOR-Based HashingProceedings of the 2006 IEEE Asia-Pacific Conference on Services Computing10.1109/APSCC.2006.91(93-98)Online publication date: 12-Dec-2006
https://dl.acm.org/doi/10.1109/APSCC.2006.91
Vattulainen IKankaala KSaarinen JAla-Nissila T(1995)A comparative study of some pseudorandom number generatorsComputer Physics Communications10.1016/0010-4655(95)00015-886:3(209-226)Online publication date: May-1995
https://doi.org/10.1016/0010-4655(95)00015-8
Xu-Duan LChang-Nian C(1990)Classes of GFSR sequences and their fast generationApplied Mathematics Letters10.1016/0893-9659(90)90023-53:2(97-100)Online publication date: 1990
https://doi.org/10.1016/0893-9659(90)90023-5
Show More Cited By

Index Terms

Orderly enumeration of nonsingular binary matrices applied to text encryption

Recommendations

Some results on determinants and inverses of nonsingular pentadiagonal matrices

A block matrix analysis is proposed to justify, and modify, a known algorithm for computing in O ( n ) time the determinant of a nonsingular n n pentadiagonal matrix ( n 6 ) having nonzero entries on its second subdiagonal. Also, we describe a procedure ...
$LDU$ Factorization of Nonsingular Totally Nonpositive Matrices

An $n \times n$ real matrix $A$ is said to be (totally negative) totally nonpositive if every minor is (negative) nonpositive. In this paper, we study the properties of a totally nonpositive matrix and characterize the case of a nonsingular totally ...
Parameterized low-rank binary matrix approximation
Abstract
Low-rank binary matrix approximation is a generic problem where one seeks a good approximation of a binary matrix by another binary matrix with some specific properties. A good approximation means that the difference between the two matrices in ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Communications of the ACM Volume 21, Issue 4

April 1978

73 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/359460

Editor:
Robert L. Ashenhurst
The Univ. of Chicago, Chicago, IL

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 1978

Published in CACM Volume 21, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
516
Total Downloads

Downloads (Last 12 months)76
Downloads (Last 6 weeks)13

Reflects downloads up to 12 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Feng WZhang ZJia ZFu Z(2006)Reversible Sketch Based on the XOR-Based HashingProceedings of the 2006 IEEE Asia-Pacific Conference on Services Computing10.1109/APSCC.2006.91(93-98)Online publication date: 12-Dec-2006
https://dl.acm.org/doi/10.1109/APSCC.2006.91
Vattulainen IKankaala KSaarinen JAla-Nissila T(1995)A comparative study of some pseudorandom number generatorsComputer Physics Communications10.1016/0010-4655(95)00015-886:3(209-226)Online publication date: May-1995
https://doi.org/10.1016/0010-4655(95)00015-8
Xu-Duan LChang-Nian C(1990)Classes of GFSR sequences and their fast generationApplied Mathematics Letters10.1016/0893-9659(90)90023-53:2(97-100)Online publication date: 1990
https://doi.org/10.1016/0893-9659(90)90023-5
Fushimi M(1990)Random number generation with the recursion Xt = Xt−3p ⊕ Xt−3qJournal of Computational and Applied Mathematics10.1016/0377-0427(90)90341-V31:1(105-118)Online publication date: Jul-1990
https://doi.org/10.1016/0377-0427(90)90341-V
Fushimi M(1989)An equivalence relation between Tausworthe and GFSR sequences and applicationsApplied Mathematics Letters10.1016/0893-9659(89)90006-22:2(135-137)Online publication date: 1989
https://doi.org/10.1016/0893-9659(89)90006-2
Prieto ATomas J(1987)A model to order the encryption algorithms according to their qualityACM SIGCOMM Computer Communication Review10.1145/36727.3673217:3(30-47)Online publication date: 1-Jul-1987
https://dl.acm.org/doi/10.1145/36727.36732
Collings BHembree G(1986)Initializing generalized feedback shift register pseudorandom number generatorsJournal of the ACM10.1145/6490.649333:4(706-711)Online publication date: 10-Aug-1986
https://dl.acm.org/doi/10.1145/6490.6493
Fushimi MTezuka S(1983)The k-distribution of generalized feedback shift register pseudorandom numbersCommunications of the ACM10.1145/358150.35815926:7(516-523)Online publication date: 1-Jul-1983
https://dl.acm.org/doi/10.1145/358150.358159
HSIAO DKERR DMADNICK S(1979)CRYPTOGRAPHIC TRANSFORMATIONSComputer Security10.1016/B978-0-12-357650-7.50013-2(135-163)Online publication date: 1979
https://doi.org/10.1016/B978-0-12-357650-7.50013-2

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

Some results on determinants and inverses of nonsingular pentadiagonal matrices

$LDU$ Factorization of Nonsingular Totally Nonpositive Matrices

Parameterized low-rank binary matrix approximation

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations