# Patent

## Title
Method, system and computer program for polynomial based hashing and message authentication coding with separate generation of spectrums

## Abstract

Computer software or integrated circuit for performing a secure hashing method including one or more of the following: representing an initial sequence of bits as a specially constructed set of polynomials; transformation of this set by masking; partitioning the transformed set of polynomials into a plurality of classes; forming the bit string during the (separated) partitioning; for each of the plurality of classes, factoring each of the polynomials and so as to define a set of irreducible polynomials and collecting these factors in registers defined for each of the plurality of classes; wrapping the values of the registers from the plurality of classes by means of an enumeration; organizing the enumerations and the bit strings into a knapsack; and performing an exponentiation in a group to obtain the hash value or the MAC value.

## Background
FIELD OF INVENTION
The present invention relates generally to data communication and storage. More specifically, the present invention relates to systems and methods for improving the security associated with data integrity and authentication.
BACKGROUND OF INVENTION
A hash function is best understood as a map that sends binary strings of arbitrary length to binary strings of length τ (or hash length).

H: {0,1}*→{0,1}τ

This τ value is fixed in advance. Commonly used hash functions have a τ value that varies from 32 to 512 (A. J. Menezes, P. C. van Oorschot, S. A. Vanstone, Handbook of Applied Cryptography, CRC Press, 1997).
A Message Authentication Code (or MAC) is a hash function that incorporates a key, namely:

H: {0,1}*×K→{0,1}τ

where K is a key space. When a user sends data, the hash value, or MAC value of the data is also calculated and appended to the message. The recipient can then verify the integrity of the data by recomputing the hash value or MAC value and comparing it with the one that was appended to the message, thereby enabling the recipient, for example, to authenticate the message.

One of the challenges in providing hash-based data integrity solutions is that the hash value needs to be efficiently computable, and collisions should be improbable. Specifically, given a binary string M, it should be computationally infeasible to find another string M′, satisfying the following equation:

H(M)=H(M′)

Hash and MAC algorithms are extremely important and at the same time the most vulnerable systems of network security (A. J. Menezes, P. C. van Oorschot, S. A. Vanstone, Handbook of Applied Cryptography, CRC Press, 1997). If a hash or MAC value can be determined by an external agency, a “collision” has occurred. If hash or MAC values are subject to collisions, the recipient of data can never be certain that the data in question has not been tampered with or corrupted. Its collision resistance measures the value of a hash (MAC) algorithm. Since the algorithm produces a string of fixed length from a message of any length, it is clear that there will be collisions. However, a good hash algorithm is one for which it is computationally infeasible to create a collision.
In a recent dramatic development, all the main hash algorithms MD-5, RIPEMD, and the MAC algorithm SHA-1 were compromised. Collisions were created for MD-5 and RIPEMD, and a group of Chinese mathematicians managed to reduce the number of operations needed to realise the brute-force attack on SHA-1 to a danger level. It should be noted that SHA-1 is the hash algorithm currently recommended by the US government. Keeping in mind that a lot of different security applications (Kerberos, MIME, IpSec, Digital Signatures and so forth) are using hash algorithms (mainly SHA-1), there is an urgent need to construct new hash algorithms.
All the main hash functions and secure functions, including those mentioned above, are referred to as iterated hash functions. They are based on an idea proposed by Damgard-Merkle (R. C. Merkle, Secrecy, Authentication, and Public Key Systems, UMI Research Press, Ann Arbor, Mich., 1979). According to this idea, the hash function takes an input string of bits, and partitions it into fixed-sized blocks of a certain size q. Then a compression function takes q bits of i-th partition and m bits from the previous calculation and calculates m bits of i+1 iteration. The output value of the last iteration (of size m) is the hash value.
Since it now appears to be easier to create a collision in existing main hash functions and secure functions, the development of new hashing algorithms that would not be based on the Damgard-Merkle approach, is extremely desirable.
Various authors have considered hash algorithms when a message to be hashed is presented as a class of various algebraic objects—elements of fields, groups, etc. Hashing based on polynomial representation is known. One of the most famous approaches is to present data as a collection of polynomials over the field of a certain characteristic. Carter and Wegman (Universal classes of hash functions. J. of Computer and System Sciences 18, 1979, 143-154) proposed the method of presenting a message as coefficients of a polynomial, and a certain point of evaluation of the polynomial is used as a key.
Krovetz and Rogaway (Fast universal hashing with small keys and no preprocessing: the PolyR construction, in: Information Security and Cryptology ICICS 2000, pp. 73-89, ed. D. H. Won, Lecture Notes in Computer Science, 2015, Springer-Verlag, 2000) considered a message as a collection of elements (m0, m1, . . . , mn) of a certain field F. A hash value of the message is a point y∈F, which is computed by calculation in the field F of the value m0kn+m1kn−1+ . . . +mnk0 for some key k∈F.
However, these approaches do not represent the data in terms of polynomials, nor do they compute the hash value using the factorization of these polynomials.
There is a need therefore for methods, computer programs and computer systems that while utilizing hash or MAC algorithms (in particular algorithms of the SHA family) are operable to provide an improved level of security over existing methods, computer programs and computer systems that implement SHA type hash and MAC algorithms. There is a further need for the methods, computer programs and computer systems that meet the aforesaid criteria and are further easy to implement with existing technologies, and are computationally feasible.
SUMMARY OF INVENTION
In one aspect of the present invention, a secure hashing method is provided consisting of: (1) representing an initial sequence of bits as a specially constructed set of polynomials as described herein, (2) transformation of this set by masking, (3) partitioning the transformed set of polynomials into a plurality of classes, (4) forming the bit strings during the partitioning, (5) for each of the plurality of classes, factoring each of the polynomials and, so as to define a set of irreducible polynomials, collecting these factors in registers defined for each of the plurality of classes, (6) wrapping the values of the registers from the plurality of classes by means of an enumeration, (7) organizing the enumerations and the bit strings into a knapsack, and, finally, (8) performing an exponentiation in a group to obtain the hash value or the MAC value.
Step (8) above may consist of the calculation of αV in the field F2τ, where α is a generator of the multiplicative group F2n×. Alternatively, one may consider Vγ, where E is an elliptic curve over F2τ and γ is a generator of the group E(F2τ). In fact, both of these methods are special cases of a more general scheme in which we consider any abstract cyclic group G with a generator g. We assume that the numeration of the elements of G requires a binary string of the size τ and that the discrete logarithm problem in G is difficult.
Because of the polynomial representation described above, in order to create a collision in accordance with the secure hash function described above, an attacker would be required to solve a collection of systems of non-linear iterated exponential equations over a finite field having specific constraints. In the case of a MAC, this difficulty is combined with the difficulty of opening the knapsack, and the difficulty of (a) solving the elliptic curve discrete logarithm referred to below, or (b) the discrete logarithm problem in the finite field, and this further contributes to the security of the method of the present invention.
As a result of the structure of the procedure, the resulting hash or MAC value has the following important attributes:

    
    
        a) the length of the output can be changed simply by changing the final step;
        b) the computation is a bit-stream procedure as opposed to a block procedure;
        c) creating a collision requires the solution to several difficult mathematical problems; and
        d) varying some parameters (the number of the bit strings, or the length of the bit strings, for example) allows easy variation of the difficulty of creating a collision.
    
    





BRIEF DESCRIPTION OF DRAWINGS
A detailed description of the preferred embodiment(s) is(are) provided herein below by way of example only and with reference to the following drawings, in which:
FIG. 1 “Scheme of hashing with separate generation of spectrums” is a flowchart diagram illustrating the steps involved in the present invention in connection with secure hashing.
FIG. 2 “Hashing with iterations” is a flowchart diagram illustrating the steps involved in the present invention with consideration of rounds (iterations) in the process of the calculation of a hash value.
FIG. 3 “Message authentication coding with iterations” is a flowchart diagram illustrating the steps involved in the present invention with consideration of rounds (iterations) in the process of the calculation of a MAC value.



In the drawings, preferred embodiments of the invention are illustrated by way of example. It is to be expressly understood that the description and drawings are only for the purpose of illustration and as an aid to understanding, and are not intended as a definition of the limits of the invention.
DETAILED DESCRIPTION OF THE INVENTION
The secure hashing method more particularly consists of: (1) representing an initial sequence of bits as a specially constructed set of polynomials as described herein, (2) transformation of this set by masking, (3) partitioning the transformed set of polynomials into a plurality of classes, (4) forming the bit string during the partitioning, (5) for each of the plurality of classes, factoring each of the polynomials and, so as to define a set of irreducible polynomials, collecting these factors in registers defined for each of the plurality of classes, (6) wrapping the values of the registers from the plurality of classes by means of an enumeration, (7) organizing the enumerations and the bit strings into a knapsack, and finally, (8) performing an exponentiation in a group to obtain the hash value or the MAC value.
A number of notations used in this disclosure should be understood. M∈{0,1}* shall represent a sequence of bits, where {0,1}* is the set of all possible finite strings. |M| shall represent the length of M in bits. By M[k]M[l] we denote the concatenation of two bits from M, namely the k-th and l-th bits. We will write M(i,j) for the sequence of bits M[i]M[i+1] . . . M[j], if i≦j, j≦|M| or M[j]M[j−1] . . . M[i] if j≦i, i≦|M|. By M(k,i)M(l,j) we denote the concatenation of two strings M(k,i) and M(l,j). If M and M1 are two strings such that |M|=|M1| then M⊕M1 is their bitwise xor. For a sequence of bits M(i,j) denote by M(i,j) the complement string. Where there is no danger of confusion, we will denote M(i,j) by Mi.
The method of the present invention uses polynomials of some fixed degree, say n. To make this computationally efficient, we choose an n satisfying 4≦n≦10. In this range, we can store a lookup table to make factorization of polynomials very fast. We could choose a larger value of n if we wished, provided we had more memory and computational power.
Irreducible polynomials of degree m are obtained as follows. For m≧1, the number of irreducible polynomials of degree m over F2 is given by the well-known formula




  
    1
    m
  
  ⁢
  
    
      ∑
      
        d
        /
        m
      
    
    ⁢
    
      
        μ
        ⁡
        
          (
          
            m
            /
            d
          
          )
        
      
      ⁢
      
        2
        d
      
    
  




where μ is the Möbius function. For m=0, we have 2 “polynomials”, namely the two elements of the field. In particular, we have the following table of values for small values of m:















degree
Number of irreducible polynomials









0
2



1
2



2
1



3
2



4
3










Denote by J(n) the lexicographically ordered set of all irreducible polynomials of degree less than n with coefficients in F2, the finite field of two elements. Denote by irr(n) the cardinality of J(n). Thus, irr(4)=7 and J(4) is the following ordered list:














Number
Polynomial









1
0



2
1



3
x



4
x + 1



5
x2 + x + 1



6
x3 + x + 1



7
X3 + x2 + 1










For h∈F2n, FCn(h, i) indicates the multiplicity of the i-th irreducible polynomial from J(n) in the factorization of h. For example, for n=4, noting that the third element in J(4) is the polynominal x and the fourth element is x+1, we have

FC4(x2+x, 1)=0, FC4(x2+x, 4)=1, FC4(x3+x2, 3)=2.

It is evident that FCn(h, 1)=1 if and only if h=0 and FCn(h,2)=1 if and only if h=1. Later, when it is clear from the context, we will omit n and simply write J and FC(h, i).
It should be understood that for any polynomial h over F2 of degree less than n denote by int(h) an integer number represented by h as a binary number. For instance, int(x3+x2+x)=14 and int(x3+1)=9. In general, if

h=α0xn−1+α1xn−2+ . . . +αn−1 

is a polynomial with coefficients a0, . . . , an−1, from F2, then let us define the integer ã by





  
    
      a
      ~
    
    i
  
  =
  
    {
    
      
        
          
            
              0
            
            
              
                
                  if
                  ⁢
                  
                    
                  
                  ⁢
                  
                    a
                    i
                  
                
                =
                
                  0
                  ⁢
                  
                    
                  
                  ⁢
                  in
                  ⁢
                  
                    
                  
                  ⁢
                  
                    F
                    2
                  
                
              
            
          
          
            
              1
            
            
              
                
                  If
                  ⁢
                  
                    
                  
                  ⁢
                  
                    a
                    i
                  
                
                =
                
                  1
                  ⁢
                  
                    
                  
                  ⁢
                  in
                  ⁢
                  
                    
                  
                  ⁢
                  
                    
                      F
                      2
                    
                    .
                  
                
              
            
          
        
        ⁢
        
          

        
        ⁢
        Then
      
      ,
      
        

      
      ⁢
      
        
          int
          ⁡
          
            (
            h
            )
          
        
        =
        
          
            
              
                a
                ~
              
              0
            
            ⁢
            
              2
              
                n
                -
                1
              
            
          
          +
          
            
              
                a
                ~
              
              1
            
            ⁢
            
              2
              
                n
                -
                2
              
            
          
          +
          ...
          +
          
            
              
                a
                ~
              
              
                n
                -
                1
              
            
            ⁢
            
              
                2
                0
              
              .
            
          
        
      
    
  




Padding

It should be understood that a sequence of bits always has to be padded. Let M be any sequence of bits. We pad M by putting in the end of M the sequence of bits 1010 . . . 10 of a size 4096 bits.
Splitting
Splitting is best understood as a stage in accordance with the present invention whereby the initial string of bits is decomposed into smaller, overlaid bit segments or “classes”. This decomposition can be achieved in two ways: direct splitting and backward splitting.
A. Direct Splitting
Let M be any preliminary padded sequence of bits. Denote k=|M| and choose some n1, n2, . . . nc, where 4≦ni≦10. We split M into the set of the following sequences:




  
    
      
        
          
            
              
                M
                ⁡
                
                  (
                  
                    1
                    ,
                    
                      n
                      1
                    
                  
                  )
                
              
              ,
              
                M
                ⁡
                
                  (
                  
                    2
                    ,
                    
                      
                        n
                        1
                      
                      +
                      1
                    
                  
                  )
                
              
              ,
              ...
              ⁢
              
                
              
              ,
              
                M
                ⁢
                
                  (
                  
                    
                      k
                      -
                      
                        n
                        1
                      
                      +
                      1
                    
                    ,
                    k
                  
                  )
                
              
              ,
            
          
        
        
          
            
              
                M
                ⁢
                
                  (
                  
                    
                      k
                      -
                      
                        n
                        
                          
                            
                          
                          ⁢
                          1
                        
                      
                      +
                      2
                    
                    ,
                    k
                  
                  )
                
                ⁢
                
                  M
                  ⁡
                  
                    [
                    1
                    ]
                  
                
              
              ,
              
                
                  M
                  ⁡
                  
                    (
                    
                      
                        k
                        -
                        
                          n
                          1
                        
                        +
                        3
                      
                      ,
                      k
                    
                    )
                  
                
                ⁢
                
                  M
                  ⁡
                  
                    (
                    
                      1
                      ,
                      2
                    
                    )
                  
                
              
              ,
              ...
              ⁢
              
                
              
              ,
              
                
                  M
                  ⁡
                  
                    [
                    k
                    ]
                  
                
                ⁢
                
                  
                    M
                    ⁡
                    
                      (
                      
                        1
                        ,
                        
                          
                            n
                            1
                          
                          -
                          1
                        
                      
                      )
                    
                  
                  .
                
              
            
          
        
        
          
            
              
                M
                ⁢
                
                  (
                  
                    1
                    ,
                    
                      n
                      2
                    
                  
                  )
                
              
              ,
              
                M
                ⁡
                
                  (
                  
                    2
                    ,
                    
                      
                        n
                        2
                      
                      +
                      1
                    
                  
                  )
                
              
              ,
              ...
              ⁢
              
                
              
              ,
              
                M
                ⁢
                
                  (
                  
                    
                      k
                      -
                      
                        n
                        2
                      
                      +
                      1
                    
                    ,
                    k
                  
                  )
                
              
              ,
            
          
        
        
          
            
              
                M
                ⁢
                
                  (
                  
                    
                      k
                      -
                      
                        n
                        
                          
                            
                          
                          ⁢
                          2
                        
                      
                      +
                      2
                    
                    ,
                    k
                  
                  )
                
                ⁢
                
                  M
                  ⁡
                  
                    [
                    1
                    ]
                  
                
              
              ,
              
                
                  M
                  ⁡
                  
                    (
                    
                      
                        k
                        -
                        
                          n
                          2
                        
                        +
                        3
                      
                      ,
                      k
                    
                    )
                  
                
                ⁢
                
                  M
                  ⁡
                  
                    (
                    
                      1
                      ,
                      2
                    
                    )
                  
                
              
              ,
              ...
              ⁢
              
                
              
              ,
              
                
                  M
                  ⁡
                  
                    [
                    k
                    ]
                  
                
                ⁢
                
                  
                    M
                    ⁡
                    
                      (
                      
                        1
                        ,
                        
                          
                            n
                            2
                          
                          -
                          1
                        
                      
                      )
                    
                  
                  .
                
              
            
          
        
        
          
            ...
          
        
        
          
            
              
                M
                ⁡
                
                  (
                  
                    I
                    ,
                    
                      n
                      c
                    
                  
                  )
                
              
              ,
              
                M
                ⁡
                
                  (
                  
                    2
                    ,
                    
                      
                        n
                        c
                      
                      +
                      1
                    
                  
                  )
                
              
              ,
              ...
              ⁢
              
                
              
              ,
              
                M
                ⁡
                
                  (
                  
                    
                      k
                      -
                      
                        n
                        c
                      
                      +
                      1
                    
                    ,
                    k
                  
                  )
                
              
              ,
            
          
        
        
          
            
              
                M
                ⁢
                
                  (
                  
                    
                      k
                      -
                      
                        n
                        
                          
                            
                          
                          ⁢
                          c
                        
                      
                      +
                      2
                    
                    ,
                    k
                  
                  )
                
                ⁢
                
                  M
                  ⁡
                  
                    [
                    1
                    ]
                  
                
              
              ,
              
                
                  M
                  ⁡
                  
                    (
                    
                      
                        k
                        -
                        
                          n
                          
                            
                              
                            
                            ⁢
                            c
                          
                        
                        +
                        3
                      
                      ,
                      k
                    
                    )
                  
                
                ⁢
                
                  M
                  ⁡
                  
                    (
                    
                      1
                      ,
                      2
                    
                    )
                  
                
              
              ,
              ...
              ⁢
              
                
              
              ,
              
                
                  M
                  ⁡
                  
                    [
                    k
                    ]
                  
                
                ⁢
                
                  
                    M
                    ⁡
                    
                      (
                      
                        1
                        ,
                        
                          
                            n
                            
                              
                                
                              
                              ⁢
                              c
                            
                          
                          -
                          1
                        
                      
                      )
                    
                  
                  .
                
              
            
          
        
      
    
    
      
        (
        1
        )
      
    
  




Note that any sequence M(i, i+nj−1) can be considered as a polynomial of degree less than nj over F2, that is, if for some i≦k−nj+1 sequence M(i, i+nj−1) is a0, a1, . . . , anj−1, then the corresponding polynomial is

a0xnj−1+a1xnj−2+ . . . +anj−1 

B. Backward Splitting
Let again M be any sequence of bits. When we apply the backward splitting we pad M from the beginning, that is, we add 4096 corresponding bits before M[l]. Now, based on chosen some m1, m2, . . . , mc, where 4≦mi≦10, we split preliminary padded M into the following collections of sequences:




  
    
      
        
          
            
              
                M
                ⁢
                
                  (
                  
                    k
                    ,
                    
                      k
                      -
                      
                        m
                        
                          
                            
                          
                          ⁢
                          1
                        
                      
                      +
                      1
                    
                  
                  )
                
              
              ,
              
                M
                ⁡
                
                  (
                  
                    
                      k
                      -
                      1
                    
                    ,
                    
                      k
                      -
                      
                        m
                        
                          
                            
                          
                          ⁢
                          1
                        
                      
                    
                  
                  )
                
              
              ,
              ...
              ⁢
              
                
              
              ,
              
                M
                ⁢
                
                  (
                  
                    
                      m
                      
                        
                          
                        
                        ⁢
                        1
                      
                    
                    ,
                    1
                  
                  )
                
              
              ,
              
                M
                ⁢
                
                  (
                  
                    
                      
                        m
                        
                          
                            
                          
                          ⁢
                          1
                        
                      
                      -
                      1
                    
                    ,
                    1
                  
                  )
                
                ⁢
                
                  M
                  ⁡
                  
                    [
                    k
                    ]
                  
                
              
              ,
            
          
        
        
          
            
              
                
                  M
                  ⁡
                  
                    (
                    
                      
                        
                          m
                          1
                        
                        -
                        2
                      
                      ,
                      1
                    
                    )
                  
                
                ⁢
                
                  M
                  ⁡
                  
                    [
                    k
                    ]
                  
                
                ⁢
                
                  M
                  ⁡
                  
                    [
                    
                      k
                      -
                    
                    ]
                  
                
              
              ,
              ...
              ⁢
              
                
              
              ,
              
                
                  M
                  ⁡
                  
                    [
                    1
                    ]
                  
                
                ⁢
                
                  M
                  ⁡
                  
                    (
                    
                      k
                      ,
                      
                        k
                        -
                        
                          m
                          1
                        
                        +
                        1
                      
                    
                    )
                  
                
              
              ,
            
          
        
        
          
            
              
                M
                ⁢
                
                  (
                  
                    k
                    ,
                    
                      k
                      -
                      
                        m
                        
                          
                            
                          
                          ⁢
                          2
                        
                      
                      +
                      1
                    
                  
                  )
                
              
              ,
              
                M
                ⁡
                
                  (
                  
                    
                      k
                      -
                      1
                    
                    ,
                    
                      k
                      -
                      
                        m
                        2
                      
                    
                  
                  )
                
              
              ,
              ...
              ⁢
              
                
              
              ,
              
                M
                ⁢
                
                  (
                  
                    
                      m
                      2
                    
                    ,
                    1
                  
                  )
                
              
              ,
              
                M
                ⁢
                
                  (
                  
                    
                      
                        m
                        2
                      
                      -
                      1
                    
                    ,
                    1
                  
                  )
                
                ⁢
                
                  M
                  ⁡
                  
                    [
                    k
                    ]
                  
                
              
              ,
            
          
        
        
          
            
              
                
                  M
                  ⁡
                  
                    (
                    
                      
                        
                          m
                          2
                        
                        -
                        2
                      
                      ,
                      1
                    
                    )
                  
                
                ⁢
                
                  M
                  ⁡
                  
                    [
                    k
                    ]
                  
                
                ⁢
                
                  M
                  ⁡
                  
                    [
                    
                      k
                      -
                      1
                    
                    ]
                  
                
              
              ,
              ...
              ⁢
              
                
              
              ,
              
                
                  M
                  ⁡
                  
                    [
                    1
                    ]
                  
                
                ⁢
                
                  M
                  ⁡
                  
                    (
                    
                      k
                      ,
                      
                        k
                        -
                        
                          m
                          2
                        
                        +
                        1
                      
                    
                    )
                  
                
              
              ,
            
          
        
        
          
            ...
          
        
        
          
            
              
                M
                ⁢
                
                  (
                  
                    k
                    ,
                    
                      k
                      -
                      
                        m
                        
                          
                            
                          
                          ⁢
                          c
                        
                      
                      +
                      1
                    
                  
                  )
                
              
              ,
              
                M
                ⁡
                
                  (
                  
                    
                      k
                      -
                      1
                    
                    ,
                    
                      k
                      -
                      
                        m
                        
                          
                            
                          
                          ⁢
                          c
                        
                      
                    
                  
                  )
                
              
              ,
              ...
              ⁢
              
                
              
              ,
              
                M
                ⁢
                
                  (
                  
                    
                      m
                      
                        
                          
                        
                        ⁢
                        c
                      
                    
                    ,
                    1
                  
                  )
                
              
              ,
              
                M
                ⁢
                
                  (
                  
                    
                      
                        m
                        
                          
                            
                          
                          ⁢
                          c
                        
                      
                      -
                      1
                    
                    ,
                    1
                  
                  )
                
                ⁢
                
                  M
                  ⁡
                  
                    [
                    k
                    ]
                  
                
              
              ,
            
          
        
        
          
            
              
                
                  M
                  ⁡
                  
                    (
                    
                      
                        
                          m
                          c
                        
                        -
                        2
                      
                      ,
                      1
                    
                    )
                  
                
                ⁢
                
                  M
                  ⁡
                  
                    [
                    k
                    ]
                  
                
                ⁢
                
                  M
                  ⁡
                  
                    [
                    
                      k
                      -
                      1
                    
                    ]
                  
                
              
              ,
              ...
              ⁢
              
                
              
              ,
              
                
                  M
                  ⁡
                  
                    [
                    1
                    ]
                  
                
                ⁢
                
                  
                    M
                    ⁡
                    
                      (
                      
                        k
                        ,
                        
                          k
                          -
                          
                            m
                            c
                          
                          +
                          1
                        
                      
                      )
                    
                  
                  .
                
              
            
          
        
      
    
    
      
        (
        2
        )
      
    
  




And again, any element M(i, i−mj) can be considered as a polynomial over F2.
Denote by S(M, n1), S(M, n2), . . . , S(M, nC,) the given ordered sets (1) and note that any S(M, nj) contains k polynomials. Remark also that the just described procedure of forming the sequences S(M, nj), j=1, . . . c is a stream procedure. Of course, in practise, there is no need to consider all sets S(M, nj) for j=1, . . . , c, as the time of the calculation of a hash (or MAC) value in that case will be increased, which will be discussed below.
EXAMPLE I
As an example, consider the following sequence of bits M without padding:

011010

Let n1=4 and n2=6. Let the procedure of forming sequences be S(M, 4) and S(M, 6). So, the elements of S(M, 4) are

x2+x, x3+x2+1, x3+x, x2, x3+1, x+1

while S(M, 6) contains elements

x4+x3+x, x5+x4+x2, x5+x3+1, x4+x+1, x5+x2+x, x3+x2+1.

Now, we want to express relations between the elements of S(M, nj) for different j for the case of the forward splitting.
Consider some nj, j=1, . . . , c and the corresponding sequence of polynomials S(M, nj) for the case of the forward splitting. It is clear that the same correspondences (with minor changes) can be built for the backward splitting too. It is not hard to see that for any i=1, . . . , k we get

Mi+1=AMiT⊕BMi+2T,  (3)

where




  
    
      A
      =
      
        (
        
          
            
              0
            
            
              1
            
            
              0
            
            
              ...
            
            
              0
            
            
              0
            
          
          
            
              0
            
            
              0
            
            
              1
            
            
              ...
            
            
              0
            
            
              0
            
          
          
            
              0
            
            
              0
            
            
              0
            
            
              ...
            
            
              0
            
            
              0
            
          
          
            
              
                
              
            
            
              ...
            
            
              
                
              
            
            
              
                
              
            
            
              
                
              
            
            
              
                
              
            
          
          
            
              0
            
            
              0
            
            
              0
            
            
              ...
            
            
              0
            
            
              1
            
          
          
            
              0
            
            
              0
            
            
              0
            
            
              ...
            
            
              0
            
            
              0
            
          
        
        )
      
    
    ,
    
      

    
    ⁢
    
      and
    
  




  
    
      B
      =
      
        (
        
          
            
              0
            
            
              0
            
            
              0
            
            
              ...
            
            
              0
            
            
              0
            
          
          
            
              0
            
            
              0
            
            
              0
            
            
              ...
            
            
              0
            
            
              0
            
          
          
            
              0
            
            
              0
            
            
              0
            
            
              ...
            
            
              0
            
            
              0
            
          
          
            
              
                
              
            
            
              ...
            
            
              
                
              
            
            
              
                
              
            
            
              
                
              
            
            
              
                
              
            
          
          
            
              0
            
            
              0
            
            
              0
            
            
              ...
            
            
              0
            
            
              0
            
          
          
            
              0
            
            
              0
            
            
              0
            
            
              ...
            
            
              1
            
            
              0
            
          
        
        )
      
    
    ,
  



are nj×nj matrices, MiT and Mi+2T are transposed vectors.

Consider two sequences S(M,nj1), and S(M,nj2), where nj1<nj2. Denote elements from S(M,nj1) and S(M,nj2) by Minj1 and Minj2, correspondingly. Then the following hold:




  
    
      
        
          
            
              
                
                  M
                  i
                  
                    n
                    
                      j
                      1
                    
                  
                
                =
                
                  
                    
                      D
                      1
                    
                    (
                    
                      M
                      i
                      
                        n
                        
                          j
                          2
                        
                      
                    
                    )
                  
                  T
                
              
              ,
            
          
        
        
          
            
              
                
                  M
                  
                    i
                    +
                    1
                  
                  
                    n
                    
                      j
                      1
                    
                  
                
                =
                
                  
                    
                      D
                      2
                    
                    (
                    
                      M
                      i
                      
                        n
                        
                          j
                          2
                        
                      
                    
                    )
                  
                  T
                
              
              ,
            
          
        
        
          
            
              ...
              ⁢
              
                
              
              ,
            
          
        
        
          
            
              
                
                  M
                  
                    i
                    +
                    q
                  
                  
                    n
                    
                      j
                      1
                    
                  
                
                =
                
                  
                    
                      D
                      q
                    
                    (
                    
                      M
                      i
                      
                        n
                        
                          j
                          2
                        
                      
                    
                    )
                  
                  T
                
              
              ,
            
          
        
      
    
    
      
        (
        4
        )
      
    
  




where, q=nj2−nj1, and





  
    
      
        
          
            D
            1
          
          =
          
            (
            
              
                
                  1
                
                
                  0
                
                
                  0
                
                
                  ...
                
                
                  0
                
                
                  0
                
              
              
                
                  0
                
                
                  1
                
                
                  0
                
                
                  ...
                
                
                  0
                
                
                  0
                
              
              
                
                  0
                
                
                  0
                
                
                  1
                
                
                  ...
                
                
                  0
                
                
                  0
                
              
              
                
                  
                    
                  
                
                
                  ...
                
                
                  
                    
                  
                
                
                  
                    
                  
                
                
                  
                    
                  
                
                
                  
                    
                  
                
              
              
                
                  0
                
                
                  0
                
                
                  0
                
                
                  ...
                
                
                  0
                
                
                  0
                
              
              
                
                  0
                
                
                  0
                
                
                  0
                
                
                  
                    ...
                    ⁢
                    
                      
                    
                    ⁢
                    1
                    ⁢
                    
                      
                    
                    ⁢
                    ...
                  
                
                
                  0
                
                
                  0
                
              
            
            )
          
        
        ,
      
    
  
  
    
      
        
          
            D
            2
          
          =
          
            (
            
              
                
                  0
                
                
                  1
                
                
                  0
                
                
                  ...
                
                
                  0
                
                
                  0
                
              
              
                
                  0
                
                
                  0
                
                
                  1
                
                
                  ...
                
                
                  0
                
                
                  0
                
              
              
                
                  0
                
                
                  0
                
                
                  0
                
                
                  ...
                
                
                  0
                
                
                  0
                
              
              
                
                  
                    
                  
                
                
                  ...
                
                
                  
                    
                  
                
                
                  
                    
                  
                
                
                  
                    
                  
                
                
                  
                    
                  
                
              
              
                
                  0
                
                
                  0
                
                
                  0
                
                
                  ...
                
                
                  0
                
                
                  0
                
              
              
                
                  0
                
                
                  0
                
                
                  0
                
                
                  
                    ...
                    ⁢
                    
                      
                    
                    ⁢
                    01
                    ⁢
                    
                      
                    
                    ⁢
                    ...
                  
                
                
                  0
                
                
                  0
                
              
            
            )
          
        
        ,
      
    
  
  
    
      
        ...
        ⁢
        
          
        
        ,
      
    
  
  
    
      
        
          
            D
            q
          
          =
          
            (
            
              
                
                  0
                
                
                  0
                
                
                  0
                
                
                  
                    ...
                    ⁢
                    
                      
                    
                    ⁢
                    1
                    ⁢
                    
                      
                    
                    ⁢
                    ...
                  
                
                
                  0
                
                
                  0
                
              
              
                
                  0
                
                
                  0
                
                
                  0
                
                
                  ...
                
                
                  0
                
                
                  0
                
              
              
                
                  0
                
                
                  0
                
                
                  0
                
                
                  ...
                
                
                  0
                
                
                  0
                
              
              
                
                  
                    
                  
                
                
                  ...
                
                
                  
                    
                  
                
                
                  
                    
                  
                
                
                  
                    
                  
                
                
                  
                    
                  
                
              
              
                
                  0
                
                
                  0
                
                
                  0
                
                
                  ...
                
                
                  1
                
                
                  0
                
              
              
                
                  0
                
                
                  0
                
                
                  0
                
                
                  ...
                
                
                  0
                
                
                  1
                
              
            
            )
          
        
        ,
      
    
  




are nj1×nj2 matrices and (Minj2)T is a transposed vector Minj2.

Denote by N the set {1, 2, . . . , c} . Denote by N1 the subset of N, for which we generate forward splitting (1), that is we form S(m,ni) for i∈N1. Denote by N2 the subset of N indices, for which we generate the backward splitting (2). N1 and N2 may contain common elements, moreover, N1 and N2 can be even equal.
Again, we generate the sequences (1) for some jail the elements from N2. In contrary splitting, we need to have at least one sequence in form (1′). Note that the division of the set {n1, n2, . . . , nc} into subsets N1 and N2 can be done arbitrarily.
Multiple Masking
The elements of the sets

S(M, n1), S(M, n2), . . . , S(M, nc)   (5)

will be further transformed in accordance with a multiple masking procedure. Remark that some of the sequences S(M,ni), i=1, . . . ,c are constructed in accordance with the backward splitting.

Masking is a transformation of the elements of a sequence S(M, n). In fact, masking is a non-linear function that generates polynomials new polynomials, having the polynomials from
S(M, n) as its input. It is clear that for any 4≦n≦10 the ordered collection of polynomials S(M,n) represents a sequence M in a unique way. We further transform S(M,n) in order to obtain a new collection of polynomials. The transformation is fast, non-linear and represents a sequence S(M,n) in a unique way. In general any non-linear function can be used for masking if the calculation of values of the function is fast, non-linear and represents the initial sequence of polynomials in a unique way. We have chosen a function that is quite fast and that forces one to solve a system of exponential iterated equations for obtaining the polynomials S(M, n) from the transformed collection of polynomials. Below, we describe the construction of the transformation.
Based on the sequence of sets S(M, n1), S(M, n2), . . . , S(M, nc) we prepare c registers CUR, so that, for any sequence S(M, nj), we associate a register CURnj. We need to show how to calculate the values of the registers and we describe the procedure for a fixed n, so we write simply CUR.
We describe the calculation of the values of CUR iteratively. Let δ and β be generators of GF(2n). We set




  
    
      
        
          
            
              
                
                  CUR
                  1
                
                =
                
                  
                    M
                    1
                  
                  ⊕
                  δ
                  ⊕
                  β
                
              
              ,
            
          
        
        
          
            
              
                
                  CUR
                  2
                
                =
                
                  
                    M
                    2
                  
                  ⊕
                  
                    δ
                    
                      int
                      ⁡
                      
                        (
                        
                          M
                          1
                        
                        )
                      
                    
                  
                  ⊕
                  
                    β
                    
                      
                        int
                        ⁡
                        
                          (
                          CUR
                          )
                        
                      
                      1
                    
                  
                
              
              ,
            
          
        
        
          
            
              
                
                  CUR
                  3
                
                =
                
                  
                    M
                    3
                  
                  ⊕
                  
                    δ
                    
                      
                        (
                        
                          
                            int
                            ⁡
                            
                              (
                              
                                M
                                2
                              
                              )
                            
                          
                          +
                          
                            int
                            ⁡
                            
                              (
                              
                                M
                                1
                              
                              )
                            
                          
                        
                        )
                      
                      ⁢
                      mod
                      ⁢
                      
                        
                      
                      ⁢
                      
                        2
                        n
                      
                    
                  
                  ⊕
                  
                    β
                    
                      
                        (
                        
                          
                            int
                            ⁡
                            
                              (
                              
                                CUR
                                2
                              
                              )
                            
                          
                          +
                          
                            int
                            ⁡
                            
                              (
                              
                                CUR
                                1
                              
                              )
                            
                          
                        
                        )
                      
                      ⁢
                      
                        
                          mod
                          ⁢
                          2
                        
                        n
                      
                    
                  
                
              
              ,
            
          
        
        
          
            ...
          
        
        
          
            
              
                CUR
                i
              
              =
              
                
                  M
                  i
                
                ⁢
                
                  ⊕
                  
                    
                      (
                      
                        
                          int
                          ⁡
                          
                            (
                            
                              M
                              
                                i
                                -
                                1
                              
                            
                            )
                          
                        
                        +
                        
                          int
                          ⁡
                          
                            (
                            
                              M
                              
                                i
                                -
                                2
                              
                            
                            )
                          
                        
                      
                      )
                    
                    ⁢
                    
                      
                        mod
                        ⁢
                        2
                      
                      n
                    
                  
                
                ⁢
                
                  ⊕
                  
                    β
                    
                      
                        (
                        
                          
                            int
                            ⁡
                            
                              (
                              
                                CUR
                                
                                  i
                                  -
                                  1
                                
                              
                              )
                            
                          
                          +
                          
                            int
                            ⁡
                            
                              (
                              
                                CUR
                                
                                  i
                                  -
                                  2
                                
                              
                              )
                            
                          
                        
                        )
                      
                      ⁢
                      mod
                      ⁢
                      
                        
                      
                      ⁢
                      
                        2
                        n
                      
                    
                  
                
              
            
          
        
      
    
    
      
        (
        6
        )
      
    
  




for i=1, . . . , 2n+1.

For i=2n+2, . . . , k we calculate CURi in accordance with

CURi=Mi⊕δ(int(Mi−1)+int(CURd1))mod 2n⊕β(int(CURi−1)+int(CURd2))mod 2n,

where

di=i−2−int(Mi−1), d2=i−2−int(CURi−1).

We stress that the procedure just described for calculating the values CURi is, in fact, a stream procedure.
We note that for the manipulations above, we are viewing F2n as a field and also as a vector space over F2. Let f(x) be a polynomial so that there is an isomorphism of fields.
Denote by φf the isomorphism of vector spaces

F2[x]/(f(x))→F2n.

Let δ and β be generators of F2n× corresponding to polynomials f(x) and g(x) . We set

CURi=Mi⊕φf(δ)⊕φg(β),

CURi=Mi⊕φf(δ(int(Mi−1)+int(Mi−2))mod 2n)⊕φg(β(int(CURi−1)+int(CURi−2))mod 2n)

for i=1, . . . , 2n+1. For i=2n+2, . . . , k we calculate CURi by

CURi=Mi⊕φf(δ(int(Mi−1)+int(CURd1))mod 2n)⊕φg(β(int(CURi−1)+int(CURd2))mod 2n)

where

di=i−2−int(Mi−1), d2=i−2−int(CURi−1).

As it was mentioned above, we calculate the values of registers CURnj for all the elements of the sequences S(M,n1), S(M,n2), . . . , S(M,nc). Of course, for different nj we use different fields F2nj with the corresponding generators. Thus, we have prepared c sets of collections of polynomials

CURin1, CURin2, . . . , CURinc,  (7)

where i=1, . . . , k. It is clear that the combination of splitting and masking is a stream procedure.

The following theorem shows that CURn is a collection of polynomials that in a unique way represents S(M,n) and therefore M. We present it here without a proof.
Theorem. Let M and M′ be any two sequences of k bits. Let, further, S(M, n), S(M′, n), CURn and CURn′ be the corresponding sequences of polynomials. Then for any n

CUR1=CUR1′, . . . , CURk=CUR′k

if and only if

M1=M′1, . . . , Mk=M′k.

Iterated Masking

The iterated masking is a procedure of forming CUR* based on CUR. We again fix some n and omit here the corresponding upper indices nj. j=1, . . . , c. We form CURi* using polynomials CURi as we did it forming CURi using polynomials Mi. So for a fixed n and i=1, . . . , 2n+1 we have




  
    
      
        
          
            CUR
            1
            *
          
          =
          
            
              CUR
              1
            
            ⊕
            δ
            ⊕
            β
          
        
        ,
      
    
  
  
    
      
        
          CUR
          2
          *
        
        =
        
          
            CUR
            2
          
          ⊕
          
            δ
            
              int
              ⁡
              
                (
                
                  CUR
                  1
                
                )
              
            
          
          ⊕
          
            β
            
              int
              ⁡
              
                (
                
                  CUR
                  1
                  *
                
                )
              
            
          
        
      
    
  
  
    
      
        
          CUR
          3
          *
        
        =
        
          
            CUR
            3
          
          ⊕
          
            δ
            
              
                (
                
                  
                    int
                    ⁡
                    
                      (
                      
                        CUR
                        2
                      
                      )
                    
                  
                  +
                  
                    int
                    ⁡
                    
                      (
                      
                        CUR
                        1
                      
                      )
                    
                  
                
                )
              
              ⁢
              mod
              ⁢
              
                
              
              ⁢
              
                2
                n
              
            
          
          ⊕
          
            β
            
              
                (
                
                  
                    int
                    ⁡
                    
                      (
                      
                        CUR
                        2
                        *
                      
                      )
                    
                  
                  +
                  
                    int
                    ⁡
                    
                      (
                      
                        CUR
                        1
                        *
                      
                      )
                    
                  
                
                )
              
              ⁢
              mod
              ⁢
              
                
              
              ⁢
              
                2
                n
              
            
          
        
      
    
  
  
    
      ...
    
  
  
    
      
        
          CUR
          i
          *
        
        =
        
          
            CUR
            i
          
          ⊕
          
            δ
            
              
                (
                
                  
                    int
                    ⁡
                    
                      (
                      
                        CUR
                        
                          i
                          -
                          1
                        
                      
                      )
                    
                  
                  +
                  
                    int
                    ⁡
                    
                      (
                      
                        CUR
                        
                          i
                          -
                          2
                        
                      
                      )
                    
                  
                
                )
              
              ⁢
              mod
              ⁢
              
                
              
              ⁢
              
                2
                n
              
            
          
          ⊕
          
            β
            
              
                (
                
                  
                    int
                    ⁡
                    
                      (
                      
                        CUR
                        
                          i
                          -
                          1
                        
                        *
                      
                      )
                    
                  
                  +
                  
                    int
                    ⁡
                    
                      (
                      
                        CUR
                        
                          i
                          -
                          2
                        
                        *
                      
                      )
                    
                  
                
                )
              
              ⁢
              mod
              ⁢
              
                
              
              ⁢
              
                2
                n
              
            
          
        
      
    
  
  
    
      and
    
  
  
    
      
        
          CUR
          i
          *
        
        =
        
          
            CUR
            i
          
          ⊕
          
            δ
            
              
                (
                
                  
                    int
                    ⁡
                    
                      (
                      
                        CUR
                        
                          i
                          -
                          1
                        
                      
                      )
                    
                  
                  +
                  
                    int
                    ⁡
                    
                      (
                      
                        CUR
                        
                          d
                          1
                        
                      
                      )
                    
                  
                
                )
              
              ⁢
              mod
              ⁢
              
                
              
              ⁢
              
                2
                n
              
            
          
          ⊕
          
            β
            
              
                (
                
                  
                    int
                    ⁡
                    
                      (
                      
                        CUR
                        
                          i
                          -
                          1
                        
                        *
                      
                      )
                    
                  
                  +
                  
                    int
                    ⁡
                    
                      (
                      
                        CUR
                        
                          d
                          2
                        
                        *
                      
                      )
                    
                  
                
                )
              
              ⁢
              mod
              ⁢
              
                
              
              ⁢
              
                2
                n
              
            
          
        
      
    
  




for i=2n+2, . . . , k, where

di=i−2−int(CURi−1), d2=i−2−int(CUR*i−1).

We will call the construction of forming CUR* the iterated masking of the first degree, while the construction of generating CUR is the iterated masking of zero degree. By analogy we consider CUR**, CUR***, . . . —the iterated masking of the second, the third degree and so forth.
Partitioning
So, we prepared c sets of the sequences of polynomials (7) for i=1, . . . , k of the corresponding degrees. Now we choose some rj≧200. The value of rj will define the number of classes, on which we will split each sequence. On the other hand, rj will also define the number of elements of a knapsack that we are going to form. In order to construct the knapsack of a cryptographic significance (for constructing MAC) we choose rj not less than 200. We wish to distribute the elements of all the sequences (7) between the partitions. It can be done in many ways.
One of the simplest ways of such a distribution is to assign the first k/rj elements to the first partition, then next k/rj elements to the second partition and so forth. The last partition in that case will contain k mod rj polynomials.
Let us present another possibility of the partitioning. The specific feature of the partitioning is that we do not define the number of partitions from the beginning. We form partition by partition and process them one by one after the preparation.
For hardware implementation of the presented hash and MAC system, an efficient way of distributing the elements of sequences (7) between partitions can be defined as follows. We choose some number z greater than or equal to 1 and assign the first z elements of the sequences to the first partition, the next z elements to the second partition and so forth. When the last rj-th partition is considered we return to the very first partition and the next z elements we assign to it, then we again use the second partition and so forth. In the case of MAC number z can be defined by a key.
Note that the methods of partitioning the polynomials presented above have one specific feature, namely, a few (neighbouring) polynomials can be assigned to one and the same partition, say, in a framework of one iteration.
Now we present a few methods of the partitioning, usage of which will guarantee that any two neighbouring elements cannot be sent to one and the same partition, during one iteration. We will refer the methods to as the separated partitions.
The next few possibilities of partitioning are based on the calculation of special indices. We calculate c sets of indices in accordance with




  
    
      
        
          
            
              
                
                  
                    ind
                    1
                    
                      n
                      j
                    
                  
                  ⁡
                  
                    (
                    1
                    )
                  
                
                =
                
                  1
                  +
                  
                    int
                    ⁢
                    
                      (
                    
                    ⁢
                    
                      CUR
                      1
                      
                        n
                        j
                      
                    
                    ⁢
                    
                      )
                    
                    ⁢
                    mod
                    ⁢
                    
                      
                    
                    ⁢
                    
                      r
                      j
                    
                  
                
              
              ,
            
          
        
        
          
            
              
                
                  ind
                  1
                  
                    n
                    j
                  
                
                ⁡
                
                  (
                  2
                  )
                
              
              =
              
                1
                +
                
                  
                    (
                  
                  ⁢
                  
                    
                      ind
                      1
                      
                        n
                        j
                      
                    
                    ⁡
                    
                      (
                      1
                      )
                    
                  
                
                +
                
                  int
                  ⁢
                  
                    (
                  
                  ⁢
                  
                    CUR
                    1
                    
                      n
                      j
                    
                  
                  ⁢
                  
                    ))
                  
                  ⁢
                  mod
                  ⁢
                  
                    
                  
                  ⁢
                  
                    r
                    j
                  
                
              
            
          
        
        
          
            ...
          
        
        
          
            
              
                
                  ind
                  1
                  
                    n
                    j
                  
                
                ⁡
                
                  (
                  i
                  )
                
              
              =
              
                1
                +
                
                  
                    (
                  
                  ⁢
                  
                    
                      ind
                      1
                      
                        n
                        j
                      
                    
                    ⁡
                    
                      (
                      
                        i
                        -
                        1
                      
                      )
                    
                  
                
                +
                
                  int
                  ⁢
                  
                    (
                  
                  ⁢
                  
                    CUR
                    i
                    
                      n
                      j
                    
                  
                  ⁢
                  
                    )
                  
                  ⁢
                  
                    )
                  
                  ⁢
                  mod
                  ⁢
                  
                    
                  
                  ⁢
                  
                    r
                    j
                  
                
              
            
          
        
      
    
    
      
        (
        8
        )
      
    
  




for j=1, . . . , c, i=3, . . . , k. We need to assign to each value CURinj one of rj partitions, where j=1, . . . , c, i=1, . . . , k. We calculate value ind1nj(i) in accordance with (8) for CURinj and the value will define the index (number) of the partition, to which CURinj will be assigned.

Consider a few more variants of constructing the index of the partitioning




  
    
      
        
          
            
              
                ind
                2
                
                  n
                  j
                
              
              ⁡
              
                (
                1
                )
              
            
            =
            
              1
              +
              
                
                  int
                  ⁡
                  
                    (
                    
                      
                        CUR
                        1
                        
                          n
                          j
                        
                      
                      ⊕
                      
                        M
                        1
                      
                    
                    )
                  
                
                ⁢
                mod
                ⁢
                
                  
                    
                  
                  ⁢
                  
                    
                  
                
                ⁢
                
                  r
                  j
                
              
            
          
          ,
          
            

          
          ⁢
          
            
              
                ind
                2
                
                  n
                  j
                
              
              ⁡
              
                (
                2
                )
              
            
            =
            
              1
              +
              
                
                  (
                  
                    
                      
                        ind
                        2
                        
                          n
                          j
                        
                      
                      ⁡
                      
                        (
                        1
                        )
                      
                    
                    +
                    
                      int
                      ⁡
                      
                        (
                        
                          
                            CUR
                            2
                            
                              n
                              j
                            
                          
                          ⊕
                          
                            M
                            2
                          
                        
                        )
                      
                    
                  
                  )
                
                ⁢
                mod
                ⁢
                
                  
                
                ⁢
                
                  r
                  j
                
              
            
          
          ,
          
            

          
          ⁢
          ...
        
        ⁢
        
          

        
        ⁢
        
          
            
              ind
              2
              
                n
                j
              
            
            ⁡
            
              (
              i
              )
            
          
          =
          
            1
            +
            
              
                (
                
                  
                    
                      ind
                      2
                      
                        n
                        j
                      
                    
                    ⁡
                    
                      (
                      
                        i
                        -
                        1
                      
                      )
                    
                  
                  +
                  
                    int
                    ⁡
                    
                      (
                      
                        
                          CUR
                          2
                          
                            n
                            j
                          
                        
                        ⊕
                        
                          M
                          2
                        
                      
                      )
                    
                  
                
                )
              
              ⁢
              mod
              ⁢
              
                
                  
                
                ⁢
                
                  
                
              
              ⁢
              
                r
                j
              
            
          
        
        ⁢
        
          

        
        ⁢
        or
      
    
    
      
        (
        9
        )
      
    
  
  
    
      
        
          
            
              
                ind
                3
                
                  n
                  j
                
              
              ⁡
              
                (
                1
                )
              
            
            =
            
              1
              +
              
                
                  (
                  
                    
                      int
                      ⁡
                      
                        (
                        
                          CUR
                          1
                          
                            n
                            j
                          
                        
                        )
                      
                    
                    +
                    
                      int
                      ⁢
                      
                        
                      
                      ⁢
                      
                        (
                        
                          M
                          1
                        
                        )
                      
                    
                  
                  )
                
                ⁢
                mod
                ⁢
                
                  
                
                ⁢
                
                  r
                  j
                
              
            
          
          ,
          
            

          
          ⁢
          
            
              
                ind
                3
                
                  n
                  j
                
              
              ⁡
              
                (
                2
                )
              
            
            =
            
              1
              +
              
                
                  (
                  
                    
                      
                        ind
                        3
                        
                          n
                          j
                        
                      
                      ⁡
                      
                        (
                        1
                        )
                      
                    
                    +
                    
                      int
                      ⁡
                      
                        (
                        
                          CUR
                          1
                          
                            n
                            j
                          
                        
                        )
                      
                    
                    +
                    
                      int
                      ⁡
                      
                        (
                        
                          M
                          1
                        
                        )
                      
                    
                  
                  )
                
                ⁢
                mod
                ⁢
                
                  
                
                ⁢
                
                  r
                  j
                
              
            
          
          ,
          
            

          
          ⁢
          ...
        
        ⁢
        
          

        
        ⁢
        
          
            
              
                ind
                3
                
                  n
                  j
                
              
              ⁡
              
                (
                i
                )
              
            
            =
            
              1
              +
              
                
                  (
                  
                    
                      
                        ind
                        3
                        
                          n
                          j
                        
                      
                      ⁡
                      
                        (
                        
                          i
                          -
                          1
                        
                        )
                      
                    
                    +
                    
                      int
                      ⁡
                      
                        (
                        
                          CUR
                          i
                          
                            n
                            j
                          
                        
                        )
                      
                    
                    +
                    
                      int
                      ⁡
                      
                        (
                        
                          M
                          i
                        
                        )
                      
                    
                  
                  )
                
                ⁢
                mod
                ⁢
                
                  
                    
                  
                  ⁢
                  
                    
                  
                
                ⁢
                
                  r
                  j
                
              
            
          
          ,
          
            

          
          ⁢
          and
        
      
    
    
      
        (
        10
        )
      
    
  
  
    
      
        
          
            
              
                ind
                4
                
                  n
                  j
                
              
              ⁡
              
                (
                1
                )
              
            
            =
            
              1
              +
              
                
                  int
                  ⁡
                  
                    (
                    
                      CUR
                      1
                      
                        n
                        j
                      
                    
                    )
                  
                
                ⁢
                mod
                ⁢
                
                  
                
                ⁢
                
                  r
                  j
                
              
            
          
          ,
          
            

          
          ⁢
          
            
              
                ind
                4
                
                  n
                  j
                
              
              ⁡
              
                (
                2
                )
              
            
            =
            
              1
              +
              
                
                  (
                  
                    
                      
                        ind
                        4
                        
                          n
                          j
                        
                      
                      ⁡
                      
                        (
                        1
                        )
                      
                    
                    +
                    
                      int
                      ⁡
                      
                        (
                        
                          CUR
                          2
                          
                            n
                            j
                          
                        
                        )
                      
                    
                  
                  )
                
                ⁢
                mod
                ⁢
                
                  
                
                ⁢
                
                  r
                  j
                
              
            
          
          ,
          
            

          
          ⁢
          ...
        
        ⁢
        
          

        
        ⁢
        
          
            
              ind
              4
              
                n
                j
              
            
            ⁡
            
              (
              i
              )
            
          
          =
          
            1
            +
            
              
                (
                
                  
                    
                      ind
                      4
                      
                        n
                        j
                      
                    
                    ⁡
                    
                      (
                      
                        i
                        -
                        1
                      
                      )
                    
                  
                  +
                  
                    int
                    ⁡
                    
                      (
                      
                        CUR
                        i
                        
                          n
                          j
                        
                      
                      )
                    
                  
                
                )
              
              ⁢
              mod
              ⁢
              
                
                  
                
                ⁢
                
                  
                
              
              ⁢
              
                r
                j
              
            
          
        
      
    
    
      
        (
        11
        )
      
    
  




for i=1, . . . , k. In general, any function of calculating the indices that involves in one way or another the elements of the corresponding S(M,nj) or CURnj can be used for defining the indices. When we consider MAC, such a function can be dependent on a key.

Now we present one more important way of constructing a separated partition, which we will refer to as the conditional distribution.
Consider the following table.













j















1
2
3
4
5
6
7




















nj
4
5
6
7
8
9
10



sj
4
5
8
11
16
22
32










To every j=1, . . . , c we associate sj ordered sets Φij of pairs (x,y), where x and y are such integers that x=1, . . . , i, y=1, . . . , i and |Φij|≦2i, i=1, . . . , sj. In other words,

Φij={(x,y)|x=1, . . . , i, y=1, . . . , i}, 

where i=1, . . . , sj. For instance, if nj=4 (j=1) we get the following ordered sets of pairs Φi1 

Φ11={(1,1)}, Φ21={(1,1), (1,2), (2,1), (2,2)},

and so forth. The elements (pairs) of Φij can be considered as indices of the corresponding entries (row by row from left to right) of the corresponding square matrices. It is clear that Φ41 contains exactly 24 elements.

Remark, that |Φjsj|=2sj for j=1, 3, 5, 7 and |Φjsj|<2sj for j=2, 4, 6.
Further, to every j=1, . . . , c we associate an integer fj, where 0<fj≦sj.
Then, for any j=1, . . . , c, if M[1] is 1, we assign CU R1nj to partition 1+x mod rj, otherwise, to partition 1+(x+y)mod rj, where (x,y) is the (int(CUR1nj)mod fj)−s element (a pair) of set Φfjj. Denote the index of the activated partition by h1. If, then, M[2] is 1, we assign CU R2nj to the partition 1+(h1+x)mod rj, otherwise, polynomial CU R2nj will be sent to partition 1+(h1+x+y)mod rj, where now (x,y) is the (int(CUR2nj)mod fj)−s element of set Φfjj, and so forth. So, if on the i-th step of the calculation the index of the current partition is hi, then if M[i+1] is 1, we assign polynomial CU Ri+1nj to partition 1+(hi+x)mod rj, otherwise, polynomial CU Ri+1nj will be sent to partition 1+(hi+x+y)mod rj, where (x,y) is the (int(CURinj)mod fj)−s element of set Φfjj.
Note that if we numerate the partitions starting from 0, that is, if we associate to any nj partitions 0, 1, . . . , rj, j=1, . . . , c the formulas defining the index of partition for the conditional distribution on the i−s step will be

(hi+x)mod(rj+1) or (hi+x+y)mod(rj+1)

depending on the value of Mi.

In that case the formulas (8), (9), (10) and (11) will be slightly modified too.
Forming the Bit Strings
In a framework of the current subsection we will refer to tables, instead of partitions. We will show now how to construct special row matrices, which will be named the bit strings. Note that the bit strings are constructed so as not to allow sending any two neighbouring polynomials from any sequence CURnj to one and the same table. In other words, the bit strings are constructed just in the case of usage the separated partitions.
Denote by Tbinj the i-th table, related to sequence CURnj and by Tbini(s) let us denote the s-th, element (entry) of a table Tbinj, where s=1, . . . , 2nj−1, j=1, . . . , c. So, a table Tbinj (or a partition) is a row matrix containing 2nj elements.
To each table Tbinj we associate, then, in general not more than 2nj bit strings of length szinj that is, the length of the bit strings for different tables of a sequence CURnj can be different. To any element s of a table Tbinj we associate a bit string eis+1nj, j=1, . . . , c, i=1, . . . , rnj, s=0, . . . , 2nj−1. We reserve one more special bit string ei0nj that is not related to any particular element s of a table Tbinj. Denote, at last, by eisnj(t), t=0, . . . , szinj the t-th bit of bit string eisnj. The bit strings are changed during the partitioning. Before the partitioning all the bits of all bit strings are set to 0.
Denote by Θinj a collection of the indices of the corresponding bit strings that we prepare for a table Tbinj. So, s∈Θinj means that a bit string enj is prepared and the bit string is associated to element s−1 of a table Tbinj. (Note that there is considerable flexibility in the choice of the Θinj). If Θinj contains all the indices s=1, . . . , 2nj we do not need a special bit string ei0nj, and therefore, in that case 0∈Θinj. Otherwise any Θinj contains 0, that is, a special bit string is always prepared.
Without loss a generality, we describe the procedure of updating the bit strings for the case of the conditional distribution.
Assume that table Tbinj is activated on the w-th step of the calculation, that is,

i=1+(x+hi−1)mod rj) or i=1+(x+y+hi−1)mod rj)

depending on the value of Mi for the corresponding x and y.

Assume further that fj(w)≦szinj and consider a polynomial CURwnj. If s∈Θinj, where

s=int(CURwnj)+1

we set

eisnj(fj(w))=1,

otherwise

ei0nj(fj(w))=1.

Let fj(w)>szinj. Again, if s∈Θinj, where s=int(CURwnj)+1 we set

eisnj(t′)=B⊕1,

otherwise

ei0nj(t′)=B⊕1.

Here t′=fj(w)mod szinj+1 and B is one of the values {0,1} of the t′-th bit of the corresponding bit string before the updating.
So at the end we obtain the bit strings eiknj, i=1, . . . , rj, k∈Θinj. Recall that any Θinj contains at least one element 0.
Based on the bit strings we compute integers BS as follows




  
    
      BS
      
        n
        j
      
    
    ⁡
    
      (
      i
      )
    
  
  =
  
    
      ∑
      
        x
        ⁢
        
          
        
        ⁢
        ε
        ⁢
        
          
        
        ⁢
        
          Θ
          i
          
            n
            j
          
        
      
      
        
      
    
    ⁢
    
      
        (
        
          x
          +
          1
        
        )
      
      ⁢
      
        
          int
          ⁡
          
            (
            
              e
              ix
              
                n
                j
              
            
            )
          
        
        .
      
    
  




We will use integers BSnj(i), i=1, . . . , rj when we calculate the knapsack.
The bit strings play a role of a “time” dimension for the elements of the tables. Indeed, when we activate the tables we just increment their values and we do not have any idea about when the activation took place. Using the bit strings, we fix the “time” of the activation. By “time” we mean value fj(i), i=1, . . . , k defined above. In other words, we are interested in knowing during which iteration of the distribution of the elements of CURnj between the tables, that or another table was activated, firstly, and exactly which entry of the table was incremented (of course, if the corresponding bit string was prepared for considered entry).
Changing the number of bit strings sufficiently increases the number of states of the FSM (finite state machine) that is related to the considered hash function. In other words, the collision resistance of the function depends on the number of bit strings ant their length.
In general, there is no need to generate all bit strings eisnj, for all s=1, . . . , 2nj, as it can reduce the speed of the program and will require extra memory.
Factoring
For every sequence of polynomials CU Rnj (that have already been distributed between the corresponding partitions), prepare new registers Riknj i=1, . . . , r, k=1, . . . , irr(nj), j=1, . . . , c, where, again, irr(nj) is the number of irreducible polynomials of degree less than n1. So for the sequence of polynomials CU Rnj we define rj partitions (tables) and any partition is associated with irr(nj) registers. Before the factorization procedure we set the initial values of all the registers equal to zero. The values of the registers will be determined by means of factoring the polynomials of sequences (6) in the following way.
On the i-th step, having calculated the value CU Rnj, (which has been assigned to, say, partition x), we increase the values of the registers Riknj by

FCnj(CURinj,k)

for k=1, . . . , irr(nj). The values of the registers Riknj of all the sequences (6) are the desired features of initial sequence of bits (file) M. We will call values Riknj the spectrums.

We describe one more algorithm of the factoring. We will call it the conditional factoring.
Assume that each of the partitions “is responsible” for certain section of a file. We can do it by means of certain formula, say, elements M1, M200, . . . and so on form “the area of responsibility” of the first partition (assume that considered rj is equal to 200), then M2, M201, . . . belong to the “area of responsibility” of the second partition and so forth. Such a formula can be not that straightforward, that is, any easily calculated rule of the conditional distribution can be considered. When we calculate CU Rinwe also calculate the index of partition to which it has to be assigned. Assume that partition q is chosen. In this case, if Mi from the considered CU Rni belongs to the “area of responsibility” of the current partition, that is, partition q, we multiply the corresponding factors, say, by 2 (in general, by any fixed number) before adding it to the corresponding spectrum, otherwise we do not change it.
Enumerating the Spectrums
I. Cantor Enumeration
Cantor enumeration can be presented as a recursive function (A. LMal'cev, Algorithms and recursive functions, Wolters-Noordhoff Pub. Co. 1970)

cd: Nd→N,

which enumerates any finite ordered sequences of integers. If d=2 then for any pair of integers <x,y> we have





  
    
      c
      2
    
    ⁡
    
      (
      
        x
        ,
        y
      
      )
    
  
  =
  
    
      
        
          
            (
            
              x
              +
              y
            
            )
          
          2
        
        +
        
          3
          ⁢
          x
        
        +
        y
      
      2
    
    .
  




Let n=c(x,y) for an arbitrary pair <x,y>. Then there exist two functions l(n) and r(n) such that x=l(n) and y=r(n), where




   
  
    
      l
      ⁡
      
        (
        n
        )
      
    
    =
    
      n
      -
      
        0.5
        ⁢
        
          ⌈
          
            
              
                ⌈
                
                  
                    
                      8
                      ⁢
                      n
                    
                    +
                    1
                  
                
                ⌉
              
              +
              1
            
            2
          
          ⌉
        
        ⁢
        
          ⌈
          
            
              
                ⌈
                
                  
                    
                      8
                      ⁢
                      n
                    
                    +
                    1
                  
                
                ⌉
              
              -
              1
            
            2
          
          ⌉
        
        ⁢
        
           
          
            

          
          ⁢
          
             
            
              
                and
                ⁢
                
                  

                
                ⁢
                
                  r
                  ⁡
                  
                    (
                    n
                    )
                  
                
              
              =
              
                
                  ⌈
                  
                    
                      
                        ⌈
                        
                          
                            
                              8
                              ⁢
                              n
                            
                            +
                            1
                          
                        
                        ⌉
                      
                      +
                      1
                    
                    2
                  
                  ⌉
                
                -
                
                  l
                  ⁡
                  
                    (
                    n
                    )
                  
                
                -
                1.
              
            
          
        
      
    
  




The functions c(x,y), l(n) and r(n) are related by the following correspondences

c(l(n), r(n))=n, l(c(x,y))=x, r(c(x,y))=y. 

One can easily enumerate triples, quadruples of numbers and so on. Indeed,

c3(x1,x2,x3)=c2(c2(x1,x2),x3),

More generally, define

cn+1(x1, x2, . . . , xn+1)=cn(c2(x1,x2), x3, . . . , xn+1).

Number

cn(x1, x2, . . . , xn)

is called the Cantor number of the n-tuple

<x1, x2, . . . , xn>.

Note that if

cn(x1, x2, . . . , xn)=x, 

then

xn=r(x), xn−1=rl(x), . . . , x2=rl . . . l(x), x1=ll . . . l(x).

II. Calculations of Cantor Numbers of the Spectrums

Consider any sequence CU Rn, for which we have already calculated spectrums Rij i=1, . . . , rl, j=1, . . . , irr(nl), l=1, . . . , c (we omitted upper indices of the registers Rij here). Define now the enumerating procedure of spectrums (registers) Rij, 1≦i≦r, 1≦j≦irr(nl). If we compute numbers Ei for 1≦i≦r by means of direct enumerating, that is,

Ei=cirr(nl)(Ri1, Ri2, . . . , Riirr(nl)),

where cirr(nl) is the above-described Cantor enumeration function, we can obtain really huge numbers. For instance, if we enumerate the following spectrum for n=6 directly, that is, by

Ei=c16(5, 3, 161, 139, 37, 21, 13, 9, 6, 3, 2, 2, 3, 1, 4, 2)

we obtain the number in 32892 digits, which is unacceptable. Therefore we describe the following enumerating procedure.

Consider any spectrum Specj={s1, s2, . . . , sj}, where j=7, 10, 16, 25, 43, 71, 129, which, in turn, corresponds to nj=4, 5, . . . , 10.

    CASE 1. j=7. We set

E7=c(c(c(c(s1, s2), s3), c(s4, s5)), c(s6, s7)).

    CASE 2. j=10. We set

E10=c(c(c(c(s1, s2), s3), c(s4, s5)), c(c(s6, s7), c(c(s8, s9), s10))).

    CASE 3. j=16. We set

E′16=c(c(c(s1, s2), c(s3, s4)), c(c(s5, s6), c(s7, s8)),

E′16=c(c(c(s9, s10), c(s11, s12)), c(c(s13, s14), c(s15, s16))),

and finally

E16=c(E′16, E′′16).

    CASE 4. j=25, 43. We divide 25 and 43 elements of the spectrums into 7 and 10 groups, correspondingly, in the following way. We take the first nine elements of Spec25 and compute integers

c(s1, c(s2, s3)), c(s4, c(s5, s6)), c(s7, c(s8, s9).



Then we divide 16 remaining elements of Spec25 into four groups by four elements in each group and calculate four integers by

c(c(s10, s11), c(s12, s13)), c(c(s14, s15), c(s16, s17)),

c(c(s18, s19), c(s20, s21)), c(c(s22, s23), c(s24, s25).

We eventually get seven integers, which will be enumerated as it was described in CASE 1. Considering Spec43 we act in the same manner, just divide the elements of the spectrum into 7 groups by 4 elements each and 15 last elements by 5 elements each. Below we show how to enumerate the group of five elements a, b, c, d, e. We set

c(c(a, c(b, c)), c(d, e)).

We obtain ten integers and apply the procedure, described in CASE 2 above.

    CASE 5. j=71, 129. Consider Spec71. We divide the elements of the spectrum into 16 groups. First nine groups contain 4 elements each and 7 remaining groups contain 5 elements each. We have already shown how to enumerate a group of four or five elements. We get 16 integers and apply the method of CASE 3.


All the elements of Spec129 are divided into 25 groups. The first 25 groups contain 5 elements each and the last group contains 9 elements, which we enumerate in accordance with

c(c(c(a, c(b, d)), c(e, c(f, h))), c(g, c(i, j))).

We get 24 integers, which we enumerate in accordance with the method of CASE 4.
In general, one can use one and the same formula of enumerating the spectrums for different nj, j=1, . . . c.
As we calculate the enumeration procedure for every partition i=1, . . . , rl and for every sequence CU Rnl, l=1, . . . , c we obtain rl c integers Eij.
Organizing a Knapsack
As a result of enumeration we obtain integers Eij, i=1, . . . , rj, j=1, . . . , c. These integers are associated with the corresponding tables that we obtain after the factorization. The corresponding integers BSnj(i), that are calculated based on the bit strings also are related to the tables and therefore we want to show how Eij and BSnj(i) should be combined. We compute c knapsacks (sums) for j=1, . . . , c

Vj=E1j+BSnj(1)+2(E2jBSnj(2))+ . . . +rj(Erjj+BSnj(rj)).

In the Damgard-Merkle construction, each block of fixed size is hashed and the calculated intermediate hash value is combined with the next block. In the construction described above, we have a different situation. Each block and associated bit string yields a factor table. Moreover, the bit string is xor-ed to the bit string of the next block, and the factor table construction is iterated. Finally, we obtain a bit string and a cumulative factor table.
Exponentiation
Let, further, G be a cyclic group, for which the discrete logarithm problem is hard, and assume that g is a generator of G. Let τ be the size (in bits) of presentation of any element from G. We define a general scheme of computing points Hi of group G, based on Vi, i=1, . . . , c. We set

Hi=gVi 

We show two examples of the calculation of Hi, based on the above-described general scheme.
EXAMPLE 1
Let τ be a length of a hash-value. Choose a primitive element

γ∈GF(2τ)

Then values Hi of G are defined by

Hi=γVi  (14)

EXAMPLE 2
Choose a GF(2τ) and let E be an elliptic curve over GF(2τ) with good cryptographic properties (N. Koblitz, Elliptic Curve cryptosystems, Math. Comp., 48(1987), 203-209). Let γ be a generator of E(GF(2τ)). Then the points Hi of E(GF(2τ)) are calculated by

Hi=Viγ  (15)

The Final Hash Value Calculation

Thus, we have c elements Hi=gVi of the corresponding group G. We generate the final hash value H of string of bits M in accordance with

H=n1H1×n2H2× . . . ×ncHc,

where × is the group operation. For instance, in the case of group E(GF(2τ)) for some elliptic curve E over GF(2τ) we get

H=n1H1+n2H2+ . . . +ncHc.

In that case, the x-coordinate of H is the final hash value of initial message (sequence of bits) M.
Message Authentication Coding
A secure hash function, or MAC is a map

H: {0,1}*×K→{0,1}τ, 

where K is a key space. A key can be involved in the process of constructing a fingerprint in some of the considered stages of generation of a hash value. The analysis of all the cases will be done below.

We want to present some of the possibilities of the transforming the ash function into a MAC function. So, let K be a key. Using K as an input for an appropriate pseudo-random generator we generate a sequence S of size k, where k is the length (in bits) of initial sequence M. Denote by Si the i-th bit of sequence S.
There is another possibility to form a sequence of bits Si based an a key K. Indeed, if l is the length of a key K, for any i=1, . . . k we consider value Si=K[j] where j=1+i mod l. Recall that K[j] is the j−s bit of K.
Below we describe various possibilities of transforming the hash function into MAC.
Key Scheme on the Stage of Splitting


    A. At the stage of splitting for some fixed j we form the sequence of polynomials S(M, nj) in the following way. For any i we consider the value Si. If Si is equal to 1, we include element Mi into S(M, nj), otherwise, element Mi is not included in S(M, nj).
    B. We apply the same procedure of including elements Mi into S(M, nj), depending on the value of Si for all j=1, . . . , c.
    C. For some fixed j for any i if Si is equal to 1, we include element Mi into S(M, nj), otherwise, instead of Mi, we include its negation, that is, element Mi.
    D. The procedure described in C is applied to all j=1, . . . , c.


We do not change any of the remaining stages of the generation of a fingerprint of M.
Key Scheme on the Stage of Masking


    A. For some fixed j and for any i=1, . . . , k if Si, for instance, is 1, we calculate

CURinj=Mi⊕δ(int(Mi−1)+ind(Md1))mod 2nj⊕β(int(CURi−1nj)+int(CURd2))mod2nj.



If Si is 0, then




  
    CU
    ⁢
    
      
    
    ⁢
    
      R
      i
      
        n
        j
      
    
  
  =
  
    
      
        
          M
          i
        
        ⊕
        
          δ
          
            
              (
              
                
                  int
                  ⁡
                  
                    (
                    
                      M
                      
                        i
                        -
                        1
                      
                    
                    )
                  
                
                +
                
                  ind
                  ⁡
                  
                    (
                    
                      M
                      
                        d
                        1
                      
                    
                    )
                  
                
              
              )
            
            ⁢
            
              
                mod
                ⁢
                2
              
              
                n
                j
              
            
          
        
        ⊕
        
          β
          
            
              (
              
                
                  int
                  ⁡
                  
                    (
                    
                      CUR
                      
                        i
                        -
                        1
                      
                      
                        n
                        j
                      
                    
                    )
                  
                
                +
                
                  int
                  ⁡
                  
                    (
                    
                      CU
                      ⁢
                      
                        
                      
                      ⁢
                      
                        R
                        
                          d
                          2
                        
                      
                    
                    )
                  
                
              
              )
            
            ⁢
            mod
            ⁢
            
              
            
            ⁢
            
              2
              
                n
                j
              
            
          
        
      
      _
    
    .
  




    B. We apply the procedure, described in A to all j=1, . . . , c.
    C. The j, for which we apply scheme A, is defined by a key K, that is, it is a part of a key K.


We do not change any of the remaining stages of the generation of a fingerprint of M.
Key Scheme on the Stage of Partitioning
We describe the scheme of involving a key on the stage of partitioning CU Rinj.

    A. Based on a key K, generate randomly k integers xi and form the following sequence of integers yi 






  
    y
    i
  
  =
  
    
      ∑
      
        i
        =
        1
      
      k
    
    ⁢
    
      
    
    ⁢
    
      
        x
        i
      
      ⁢
      
        
      
      ⁢
      mod
      ⁢
      
        
      
      ⁢
      
        r
        .
      
    
  




For some fixed j, CU Rinj is assigned to partition yi+1.

    B. The procedures described in A is applied to all j=1, . . . , c.
    C. In schemes A and B, the fixed j is defined by a part of a key K.


We do not change any of the remaining stages of the generation of a fingerprint of M.
Key Scheme on the Stage of Forming the Bit Strings


    A. A key K defines the sequence of the elements for the corresponding tables for which we will prepare the bit strings for a certain j. For instance, based on a key K, we again generate integers yij, i=1, . . . , fj, fj<rj and for the tables yij we prepare the bit strings for the first yij mod 2nj elements that activate the corresponding tables.
    B. The same as A but for all j.


We do not change any of the remaining stages of the generation of a fingerprint of M.
Enhancing the Security
The proposed hash function has at least four optional parameters changing of which leads to enhancing the security of the function.
First of all it is necessary to use at least c=2 and to form one forward and one backward splitting. In general, the grater the value of c, the more secure the hash function, that is, it is more difficult to create a collision. However, increasing the value of c we also reduce the speed of the algorithm. In any case at least one splitting has to be always backward splitting.
Secondly, the security of the hash (and MAC) function can be sharply increased by means of increasing the number and the sizes of the bit strings. It is important to remark that such an increasing does not lead to a rapid reducing the speed of the algorithm.
Thirdly, choosing the iterated masking of higher degree increasing the security of the hash function, as in that case the analysis of the relation between Mi and, say, CUR**i becoming practically non-realisable. And again, it leads to reducing the speed of the algorithm.
At last, considering the conditional distribution of CURi (or CUR**i) between the partitions and choosing fi equal to si (or at least, close to si) increases the security of the algorithm and does not reduce the speed rapidly.
Iterated masking; see the flow charts “Hashing with iterations” and “Message authentication coding with iterations” also increases the resistance to creating a collision, as in that case, the collection of the systems system of the corresponding non-linear iterated equations will be much more difficult.
Implementation
As one example, the method of the present invention can be readily implemented in a Dynamically Linked Library or DLL which is linked to a computer program that utilizes an algorithm that embodies the hash function or MAC function described above, for example, an encryption, decryption or authentication utility that is operable to apply said algorithm.
The computer program of the present invention is therefore best understood as a computer program that includes computer instructions operable to implement an operation consisting of the calculation of the hash value or MAC value as described above.
Another aspect of the present invention is a computer system that is linked to a computer program that is operable to implement on the computer system the transformation of a MAC-value, in accordance with the present invention.
This invention will be of use in any environment where hash functions and MAC functions are used for data integrity or authentication (digital signatures being an example).
An example is secure email. Several widely used systems for secure email (such as PGP and S/MIME) use SHA-1 as the hash algorithm.
Another application is to secure Virtual Private Networks (VPNs) by operation of the present invention. Such networks allow clients to use standard internet connections to access closed private networks. The authentication of such networks is based on a protocol such as IPSec or SSL. In both cases, the authentication uses a MAC algorithm such as SHA-1. Thus, vulnerability in SHA-1 will result in vulnerability of the VPN. By introducing a MAC algorithm based on the above, these vulnerabilities are mitigated.
One more application is to secure Digital Signatures by operation of the present invention. One of the algorithmic stages of any Digital Signatures is hashing. In fact, a Digital Signatures algorithm is usually applied to a hash (or MAC) value of a file. And almost all Digital Signatures algorithms now using SHA-1 as such a hash (or MAC) algorithm. And, again, vulnerability in SHA-1 will result in vulnerability of all the Digital Signatures algorithms.
As another example, the method of the present invention can be readily implemented in a specially constructed hardware device. As discussed above, the bit stream specific is one of the most important features of the present invention. It means that the hardware implementation of the present invention is very convenient and easily realisable. Moreover, such a hardware implementation of the present invention enables a dramatic increase in the speed of hashing, as all the hardware implementations of stream algorithms are usually much faster than the corresponding software implementations. We stress here that all the algorithms of the SHA family (as well as the MD and RIPEMD families) are block-based algorithms and are not convenient for hardware implementations.
An integrated circuit can be created to perform the calculations necessary to create a hash value or MAC value. Other computer hardware can perform the same function. Alternatively, computer software can be created to program existing computer hardware to create hash or MAC values.

## Claims

1. A computer implemented method for performing a secure hashing method, the computer implemented method comprising the steps of:
(1) representing, or facilitating the representing, by one or more computer processors, an initial sequence of bits as a set of polynomials constructed to a fixed-degree;
(2) transforming, or facilitating the transforming, by one or more computer processors, the set of polynomials by masking;
(3) partitioning, or facilitating the partitioning, by one or more computer processors, the transformed set of polynomials into a plurality of classes;
(4) forming, or facilitating the forming, by one or more computer processors, a bit string during the partitioning, said partitioning involving separated partitions;
(5) for each of the plurality of classes, factoring, or facilitating the factoring, by one or more computer processors, each polynomial of the set of polynomials transformed into the plurality of classes and so as to define a set of irreducible polynomials and collecting one or more factors in registers, said registers being defined for each of the plurality of classes;
(6) wrapping, or facilitating the wrapping, by one or more computer processors, one or more values of the registers from the plurality of classes by means of an enumeration;
(7) organizing, or facilitating the organizing, by one or more computer processors, the enumeration and the bit strings into a knapsack; and
(8) performing an exponentiation, or facilitating the performing of an exponentiation, by one or more computer processors, in a group to obtain a hash value.

2. A non-transitory computer readable medium storing instructions and data to create a hash value, the computer readable medium comprising:
(1) said instructions and data for configuring one or more computer processors to:
(a) represent, or facilitate the representation of, an initial sequence of bits as a set of polynomials constructed to a fixed-degree;
(b) transform, or facilitate the transformation of, the set of polynomials by masking;
(c) partition, or facilitate the partition of, partitioning the transformed set of polynomials into a plurality of classes;
(d) form, or facilitate the formation of, forming the a bit string during the partitioning, said partitioning involving separated partitions;
(e) for each of the plurality of classes, factor, of facilitate the factoring of, each polynomial of the set of polynomials transformed into the plurality of classes and so as to define a set of irreducible polynomials and collect one or more factors in registers, said registers being defined for each of the plurality of classes;
(f) wrap, or facilitate the wrapping of, one or more values of the registers from the plurality of classes by means of an enumeration;
(g) organize, or facilitate the organization of, the enumeration and the bit strings into a knapsack; and
(h) perform, or facilitate the performance of, an exponentiation in a group to obtain a hash value.