Browse Prior Art Database

SYSTEM AND METHOD FOR REVERSIBLY MARKING A BINARY FILE WITH RANDOM PATTERNS OF BITS FOR AUTHENTICATION

IP.com Disclosure Number: IPCOM000013949D
Original Publication Date: 2000-Dec-01
Included in the Prior Art Database: 2003-Jun-19
Document File: 5 page(s) / 143K

Publishing Venue

IBM

Abstract

A method for marking the intervals of an input text with extra blanks, generating an output text to be transmitted, is disclosed for the purposes of :

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 41% of the total text.

Page 1 of 5

  SYSTEM AND METHOD FOR REVERSIBLY MARKING A BINARY FILE WITH RANDOM PATTERNS OF BITS FOR AUTHENTICATION

A method for marking the intervals of an input text with extra blanks, generating an output text to be transmitted, is disclosed for the purposes of :

encoding and hiding (secret) binary data on the output text, and at the same time encoding and hiding on the output text the integrity information of the input text, and hiding the distribution of blanks (i.e., the format) of the input text.

The method enables the receiver, from a received marked text:

to recover the (secret) hidden binary data, to recover the original input text, and to verify the integrity of the received text

Hiding and authentication method

    Let 'text' be a text that contains m blank intervals. Let n1 and n2 be two integers such that m >= n1 + n2. Let P be a (secret) binary string of n1 bits. Let MAC be the "message authentication code" of 'text', of n2 bits, computed from a secret key K. To encode and hide both, secret binary string P and MAC into the distribution of blanks of the first (n1+n2) intervals of a marked 'm_text', the following procedure, illustrated in Figure 1 is applied:

i) Using a one-way hash function H compute, from binary string P, a binary string Q of n2 bits. Formally: Q = H(P);

NOTE: For good security it is advisable that n1 and n2 should be at least 128 intervals. Since m >= n1+n2, to securely work with this method 'text' should contain a minimum of about 256 blank intervals. Of course, one could use less intervals if one wants to accept less security.

ii) For each asserted bit of P insert one blank on the corresponding interval of the first n1 intervals of 'text', and for each asserted bit of Q insert one blank on the corresponding interval of the next n2 intervals of 'text'. Let 'p_text' be the resulting text.

iii) Starting from a lexicographic string Xo, consisting on n1 symbols a and n2 symbols b, (e.g., Xo = aaa ... abbb ... b), by means of a suitable permutation functionF, using as input parameters cryptographic key K and 'p_text', by means of unitary transformations of the type SHIFT, PERMUTE and ROTATE (i.e., transformations that preserve the number of symbols of classes a and b), transform Xo into a lexicographic string Xp, formed also by n1 symbols a and n2 symbols b, (i.e., Xp will be a cryptographic permutation of Xo). Formally: Xp = F(Xo, K, 'p_text');

1

Page 2 of 5

Let by definition A and B be, respectively, the subsets of ordinals of the n1 symbols a and of the n2 symbols b on Xp, i.e.:

A = { A(1), A(2), ... , A(n1-1), A(n1) }; 1 <= A(i) <= (n1+n2), i= 1, 2, ... , n1;

B = { B(1), B(2), ... , B(n2-1), B(n2) }; 1 <= B(j) <= (n1+n2), j= 1, 2, ... , n2;

iv) Since the parity of the number of blanks on the intervals of 'p_text' can be "even" or "odd", using a two-way reversible mapping, the parity of the first (n1+n2) intervals of 'p_text' is transformed to the same parity. This mapping would consists in adding, to the first (n1...