FORM-2
THE PATENT ACT, 1970
(39 of 1970)
&
THE PATENT RULES, 2003
PROVISIONAL SPECIFICATION
(See section 10 and Rule 13)
DETERMINISTIC RANDOM NUMBER GENERATORS
FOR INFORMATION SECURITY AND DIGITAL
WATERMARKING
TATA CONSULTANCY SERVICES LTD.
an Indian Company
of Bombay House, 24, Sir Homi Mody Street, Mumbai-400 001, Maharashtra, India,
THE FOLLOWING SPECIFICATION DESCRIBES THE INVENTION

Field of Invention
The present invention is in the field of Cryptography and Digital Watermarking. The invention pertains to design of a new deterministic random number generator (DRNG) to produce cryptographically secure and robust watermarking sequences.
Background of Invention
Cryptography and Image watermarking are filled with apparent oxymora and paradoxes. Random sequences are used as keys to encrypt information to be used as watermark during embedding the watermark and also to extract the watermark during detection. Therefore a deterministic random number sequence is very much useful for watermarking applications. In order to obtain the same random number sequence, we need to pass the same seed to the generator.
Many researchers have used DRNG for cryptographic applications and Pseudo Noise Random sequence (PN) for watermarking. Even though, there are some weaknesses in PN due to attacks, the research community used it mostly in digital watermarking. On the other hand, DRNG has not been widely used in watermarking due to its computational complexity and non-robustness. Therefore, we have invented a new design of generating DRNG using Pi-series to make it useful for Cryptographic and Digital watermarking applications.
Prior Art
The present invention provides a tool to design a new deterministic random number generator (DRNG), which is cryptographically secure and robust in terms of watermarking.


United States Patent 6862605 by Wilber, Scott A. et al discloses true random number generator and entropy calculation device and method. This random number generator includes a first oscillator that provides a first oscillatory signal to a processor, and a second oscillator that provides a signal to a frequency multiplier, which in turn provides a second oscillatory signal to the processor. The relative jitter between the two oscillatory signals contains a calculable amount of entropy that is extracted by the processor to produce a sequence of true random numbers.
United States Patent 6215874 by Borza, Stephen J. Freedman, Gordon et al discloses a method and system of generating random numbers using imaging transducers of a charge coupled array. Noise signals detected by a first and a second imaging transducers of the array are processed together to yield a first value; noise signals detected by a third and a fourth imaging transducers are processed together to yield a second value; the first and second values are processed together to yield the random number.
United States Patent 20050098945 by Carter, Michael L. et al discloses an apparatus for generating random indicia sequences.
United States Patent 5057795 by William M. Hawthorne et al discloses a pseudo-random sequence generator characterized by comprising a plurality of substantially similar elements adapted to operate in parallel.
United States Patent 20070165848 by Reyes, Sergio et al discloses Lightweight pseudo-random number generator.


U.S patent no. 6533664 by Hardy Lee Crumby et al discloses gaming system with individualized centrally generated random number generator seeds.
United States Patent 6101602 by Fridrich, Jiri et al discloses digital watermarking by adding random, smooth patterns.
United States Patent 7099493 by Hirofumi Muratani et al discloses digital watermarking device and method thereof.
Summary of Invention
The DRNG in accordance with this invention is based on Leibniz Pi series that is secure and robust and it is useful for Cryptographic and Digital watermarking applications. Initially, there is taken a finite sequence S„ from a partial sum of Leibniz Pi infinite series
( S(-l)(n+1)/(2n-l), where n =1,2,...). In order to achieve the randomness, the sequence Sn is passed into a layer of 3 operations: Irreversible shuffling, Non-linear function and LFSR. In each operation, the entropy of Sn increases. After passing Sn through all three operations, the output satisfies statistical tests of randomness. Since the entire flow of operations is not bijective, it is difficult to predict Sn from the given output. Therefore, the output is random as well as secure. Some statistical properties of DRNG using Leibniz Pi and PN sequences have been observed and analyzed. Since the proposed scheme performs well in terms of correlation and randomness properties, it is recommended to use the proposed DRNG in Spread spectrum based Digital watermarking techniques as well as Cryptographic applications. Analogously, Ramanujan Pi value instead Leibniz Pi have been attempted in the invented DRNG and then the performance and outcomes are also good.


According to this invention, there is provided a method and a system to find a new deterministic random number generator (DRNG) and a method and a system to implement the DRNG.
In accordance with a preferred embodiment of this invention the method and a system comprises 4 operations in a sequential order: A) Selecting Sn from Pi series B) Irreversible Shuffling function C) Non-linear function and D) LFSR.
Typically, the operation A computes a finite sequence Sn from a partial sum of infinite Pi series. The operation B has one-way functions and it cannot be deshuffled. The operation C is not bijective and the operation D is bijective w.r.to the primitive polynomial used in LFSR as well as output of LFSR.
In one embodiment of the invention, the process A—>B—»C—»Dis not bijective.
Particularly, Ramanujan Pi series are used and tested in the method and system in accordance with this invention.
Particularly, the system in accordance with this invention performs better than PN sequence.
Particularly, the seeds of this system are secure and is suitable for Information security and Digital watermarking applications.
Brief Description of the Accompanying Drawings
The invention is described with reference to the accompanying drawings in which;


Figure 1 shows Invented DRNG process
Figure 2 shows Irreversible shuffling process
Figure 3 shows Non linear process
Figure 4 shows compression level of the invented DRNG
Figure 5 shows applications of the invented DRNG
Detailed Description of Invention
The methods and/or systems by which a deterministic random number sequence is generated are now described. The invention discloses a new DRNG process used to compute and generate a random sequence that is suitable for cryptographic and digital watermarking applications. The invented DRNG process consists of 4 operations: Selecting Sn from Pi series, Irreversible shuffling, Non-linear function and LFSR. Each operation is explained as follows.
Selecting Sn from Pi series
A finite sequence Sn is selected from a partial sum of infinite Pi series ][a; where n is as per the requirement of random numbers and each Sn consists of higher order decimal values. Then a sequence S is obtained where S= {Si, S2,...,Sn} for a large size n so that Sn converges to Pi value as n —* oo (where Sn = a1 + a2 + ... + an).
For instance, the inventors have implemented and analyzed using a finite sequence Sn from a partial sum of Leibniz or Ramanujan Pi infinite series.

wherep(n) = (4n)! (1103+26390 n), q(n) = (n!)4 3964n and n = 1,2,...


Irreversible Shuffling of bits
The Shuffling function takes Sn as input and shuffles the bits of Sn followed by a one-way masking. The one-way masking function (like discrete logarithm / integer factorization) is used in shuffling function, so that it cannot be de-shuffled. Hence the inverse of the shuffling cannot be easily accomplished. It follows that the shuffling function is cryptographically secure. Due to diffusion property of the shuffling function, the output gets random. More over, two seed values are used in the shuffling function: First seed is based on primitive polynomials and second seed on prime numbers. Users supply both seeds during the execution of shuffling operations.
For example, the input x is shuffled and transformed in the following manner. Here, the seed values are 0xFBDB1169 (32-bit primitive polynomial) and OxFFFFFFFB (prime number). Stepl





Non-linear function
The output of the shuffling function is the input to the non-linear function. Since the non-linear function diffuses the input, the entire sequence of bits increases entropy. Given non-linear function is irreversible so that input and output cannot be correlated. Further, seed values could also be incorporated in the non-linear function in order to improve the strength of the function.
For example, consider f(n) = ((n + n + c) & OxFFFFFFFF) where c is a constant value provided by users. Then compute g(m) = (mn) mod p, where m = f(n) and p is prime. The output g(m) and input n cannot be correlated and the entropy of g(m) is relatively higher than n. As we discussed two functions f(n) and g(m), users could consider the constant c and prime p as seeds.
LFSR (Linear Feedback Shift Register)
The output of the nonlinear function is given as input to the LFSR. Primitive polynomials over GF(2n) are useful in the design of LFSRs for generating sequences of maximum period. All generated primitive polynomials are highly dense as well as random (highly dense means more number of tabs used). In the LFSR operation, the given primitive polynomial acts as seed so that it is secure to generate different combination of sequence of bits.
Each time, the n-bits input is executed with a primitive polynomial of degree n and the linear shift process undergoes for different cycles. Thus, even if the input bits are identical, the output will be random.
For instance, the primitive polynomial used in LFSR is x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 +x5 + x4 + x2 + x + 1 over GF(232). This is an irreducible polynomial of degree 32 whose period is 232-l. Experimentally,


it is tested that the output of LFSR round gets more random, when each 32-bit input is shifted with the given primitive polynomial for 4 to 15 cycles.
Inverse of LFSR can be obtained with respect to the same primitive polynomial used for LFSR as well as output of LFSR. Therefore LFRS is bijective. The inverse operation consumes a little bit time. For a large size of n, it is not an easy task to find the input from LFSR output without knowing a primitive polynomial employed in the LFSR operation.
Invented DRNG - Non invertible
The invented DRNG is capable of producing a random sequence with high entropy. The process starts from Sn that undergoes Irreversible shuffling, Non-linear and LFSR operations and produces the output as a deterministic random number sequence. It is theoretically and practically impossible to predict n and Sn from a given random sequence due to nonlinear and oneway properties involved in the DRNG process.
The tool in accordance with this invention can be used in Cryptographic applications and Digitial watermarking. Unlike DRNG, the sequence PN can be realized by LFSR with Exclusive OR operations and is good for spread spectrum communications. When an attacker comes to know what kind of polynomial is used in the sequence PN, the input and output processes of PN could be judged - a vulnerable attack. Whereas in the invented DRNG, even the attacker comes to know the core operations in LFSR, it is difficult to judge the behavior of nonlinear and discreet logarithm properties involved in the DRNG process. Therefore, the invented DRNG is cryptographically secure and performs well in terms of robustness in watermarking applications due to its correlation properties.


Analysis of DRNG (invented) and PN
PN possesses good Autocorrelation and Cross correlation properties. It is well suited for Digital Watermarking, but not for Cryptographic applications. Sometimes, the PN sequences may not have good entropy values. Whereas the invented DRNG performs well in terms of Autocorrelation, Cross Correlation, Entropy, Compression, Frequency, Arithmetic Mean, Serial Correlation, Chi square distribution and Monte Carlo value tests.
The invented DRNG is compared with PN and Alternating sequences.

Alternating sequence Invented DRNG PN
The sequence follows a pattern No pattern No pattern
Not random Random Random
Not at all secure Secure for Cryptographic and watermarking applications Secure for watermarking applications. It can be used for Cryptographic applications with risk.
Suitable for spread spectrum based digital watermarking application Suitable for spread spectrum based digital watermarking applications Suitable for spread spectrum based digital watermarking application.
Recovery of watermarked image is good with error level 2-3% Recovery of watermarked image is good with error level 5-6% Recovery of watermarked image is good with error level 8-9%
Image smoothness is good At par At par
Table 1: Comparison of different sequences


IMPLEMENTATION RESULTS:
Entropy and randomness tests have been performed on the input and output files of the invented DRNG. The entropy of the output file is at maximum level (7.9 per byte) and it was always higher than that of the corresponding input file.
The following results are analyzed using Statistical tests on the input and output files of the invented DRNG.
Result 1:
Using Leibniz Pi series of file size 192 KB
Statistical results of Input file
Entropy = 4.310153 bits per byte.
Optimum compression would reduce the size
of this 200000 byte file by 46 percent.
Chi square distribution for 200000 samples is 10209131.42, and randomly
would exceed this value 0.01 percent of the times.
Arithmetic mean value of data bytes is 68.1466 (127.5 = random).
Monte Carlo value for Pi is 3.628716287 (error 15.51 percent).
Serial correlation coefficient is 0.355382 (totally uncorrelated = 0.0).
Statistical results of Output file
Entropy = 7.999012 bits per byte.
Optimum compression would reduce the size
of this 200000 byte file by 0 percent.
Chi square distribution for 200000 samples is 274.08, and randomly
would exceed this value 25.00 percent of the times.
Arithmetic mean value of data bytes is 127.5066 (127.5 = random).


Monte Carlo value for Pi is 3.129871299 (error 0.37 percent).
Serial correlation coefficient is -0.003409 (totally uncorrelated = 0.0).
Result 2:
Using Leibniz Pi series of file size 391 KB
Statistical results of Input file
Entropy = 4.330900 bits per byte.
Optimum compression would reduce the size
of this 400000 byte file by 45 percent.
Chi square distribution for 400000 samples is 20325590.43, and randomly
would exceed this value 0.01 percent of the times.
Arithmetic mean value of data bytes is 69.9801 (127.5 = random).
Monte Carlo value for Pi is 3.630276303 (error 15.56 percent).
Serial correlation coefficient is 0.383419 (totally uncorrelated = 0.0).
Statistical results of Output file
Entropy = 7.999509 bits per byte.
Optimum compression would reduce the size
of this 400000 byte file by 0 percent.
Chi square distribution for 400000 samples is 272.38, and randomly would
exceed this value 25.00 percent of the times.
Arithmetic mean value of data bytes is 127.5831 (127.5 = random).
Monte Carlo value for Pi is 3.136291363 (error 0.17 percent).
Serial correlation coefficient is 0.001422 (totally uncorrelated = 0.0).


Result 3:
Using Ramanujan Pi series of file size 128 KB
Statistical results of Input file
Entropy = 3.676774 bits per byte.
Optimum compression would reduce the size
of this 130790 byte file by 54 percent.
Chi square distribution for 130790 samples is 2659228.87, and randomly
would exceed this value 0.01 percent of the times.
Arithmetic mean value of data bytes is 48.9852 (127.5 = random).
Monte Carlo value for Pi is 4.000000000 (error 27.32 percent).
Serial correlation coefficient is 0.267845 (totally uncorrelated = 0.0).
Statistical results of Output file
Entropy = 7.998604 bits per byte.
Optimum compression would reduce the size
of this 130792 byte file by 0 percent.
Chi square distribution for 130792 samples is 254.30, and randomly would
exceed this value 50.00 percent of the times.
Arithmetic mean value of data bytes is 127.4260 (127.5 = random).
Monte Carlo value for Pi is 3.166896046 (error 0.81 percent).
Serial correlation coefficient is 0.004917 (totally uncorrelated = 0.0).
Result 4:
Using Ramanujan Pi series of file size 256 KB Statistical results of Input file Entropy = 3.659939 bits per byte. Optimum compression would reduce the size


of this 263188 byte file by 54 percent.
Chi square distribution for 263188 samples is 5377266.89, and randomly
would exceed this value 0.01 percent of the times.
Arithmetic mean value of data bytes is 48.9443 (127.5 = random).
Monte Carlo value for Pi is 4.000000000 (error 27.32 percent).
Serial correlation coefficient is 0.262759 (totally uncorrelated = 0.0).
Statistical results of Output file
Entropy = 7.999243 bits per byte.
Optimum compression would reduce the size
of this 263188 byte file by 0 percent.
Chi square distribution for 263188 samples is 275.66, and randomly
would exceed this value 25.00 percent of the times.
Arithmetic mean value of data bytes is 127.6200 (127.5 = random).
Monte Carlo value for Pi is 3.133229984 (error 0.27 percent).
Serial correlation coefficient is -0.000643 (totally uncorrelated = 0.0).
INDUSTRIAL APPLICATIONS
The invented DRNG described above finds a number of applications in Information Security and Digital watermarking. Some specific areas where our process can be applied are:
1. Session key generation
2. Signature protocols
3. Client-Server protocols
4. Encryption
5. Spread spectrum communications
6. Digital Signal Process


While considerable emphasis has been placed herein on the particular features of the preferred embodiment and the improvisation with regards to it, it will be appreciated the various modifications can be made in the preferred embodiments without departing from the principles of the invention. These and the other modifications in the nature of the invention will be apparent to those skilled in art from disclosure herein, whereby it is to be distinctly understood that the foregoing descriptive matter is to interpreted merely as illustrative of the invention and not as a limitation.