Browse Prior Art Database

Encryption Properties of Arithmetic Codes

IP.com Disclosure Number: IPCOM000052054D
Original Publication Date: 1981-Apr-01
Included in the Prior Art Database: 2005-Feb-11
Document File: 2 page(s) / 14K

Publishing Venue

IBM

Related People

Langdon, GG: AUTHOR [+4]

Abstract

This invention relates to a method for encrypting a bit stream from binary coded sources by recursively encoding the bits according to the Rissanen/Langdon FIFO arithmetic compression algorithm. The compression aspects of this algorithm are described, for example, in the IBM Technical Disclosure Bulletin Vol. 22, March 1980, at pages 4688-4689. The encryption method uses a key formed from the initial encoder state, a permutation of the initial state element bits, and alteration of the skew number as a function of the key itself and the past code history.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 2

Encryption Properties of Arithmetic Codes

This invention relates to a method for encrypting a bit stream from binary coded sources by recursively encoding the bits according to the Rissanen/Langdon FIFO arithmetic compression algorithm. The compression aspects of this algorithm are described, for example, in the IBM Technical Disclosure Bulletin Vol. 22, March 1980, at pages 4688-4689. The encryption method uses a key formed from the initial encoder state, a permutation of the initial state element bits, and alteration of the skew number as a function of the key itself and the past code history.

In October 1979, Frank Rubin, in Cryptologia, Vol. 3, No. 4, pages 202-205, suggested the use of arithmetic stream codes for cryptographic purposes. He recognized that part of the key is the initial encoder state. He did not suggest a key utilizing an amendable skew number.

In arithmetic codes, the property of interest of each symbol is its probability. The code itself is further dependent upon the ordering of the symbols. However, the value of the augend added to the code string is approximately the sum of the probabilities of the symbols preceding it in the assumed ordering. The sum of the probabilities must not exceed unity. A permuted ordering gives the same compression, but the augend values are changed. For an N-symbol alphabet, there are N-factorial permutations.

An encryption advantage accrues to arithmetic coding because it maps a source string into a number. For decoding, it is necessary to do magnitude comparisons. Each source symbol causes an augend magnitude to be added to the code string, followed by a scaling shift. Following the encoding of a symbol, a new state is entered. As a result of generating the code string as a sum of overlapping scaled magnitudes, a symbol frequency analysis is difficult. This is derived from the fact that there are no readily identifiable code string symbols.

In the binary arithmetic code there is provided a scaling shift of up to fifteen. In this case, the augend can be made to include thirty-two bits. This results in an augend overlap of at least two augends per bit position.

In arithmetic coding, the analogy of a substitution cipher is the use of a code table where each symbol is equally probable. Since the probability ordering is known, the opponent knows the augend and shift (next state function). The opponent is also supplied with the initial state of the system when coding starts. Thus, the opponent can decode the code string and obtain a corresponding string of concatenated ordering. Through frequency an...