526互联

密码学SAT入门006——关于安全哈希算法SHA-1的学习

发布时间 2023-03-28 15:52:21作者: 海阔凭鱼跃越

 

  电子科技大学《密码学原理》慕课截图——感谢聂旭云、廖永建、熊虎等几位老师的讲解
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 
   
  算法code
 

SHA-1.alg program encodes SHA-1 hash algorithm witch transform one message block (512 bits) into 160-bit hash value.
The translation of this program results in SHA-1_1.cnf CNF-formula.
The original message (512 bits) is encoded with variables number 1 .. 512.
The hash value (160 bits) is encoded with variables number 22372 .. 22531.

To construct a cryptanalysis problem one needs to add to this CNF known hash value via unit clauses.
Preimage for the hash value is the assignment of first 512 variables that can be extracted from the satisfying assignment of the CNF.
  
  1 // ������� 512-������ ���� ������, ������� �� 32-������ ���������
  2 __in bit M[16][32];
  3 
  4 __out bit Hash[5][32];
  5 
  6 bit W[80][32];
  7 
  8 // �������������� ���������� ���������
  9 bit A[32] = 0x67452301;
 10 bit B[32] = 0xEFCDAB89;
 11 bit C[32] = 0x98BADCFE;
 12 bit D[32] = 0x10325476;
 13 bit E[32] = 0xC3D2E1F0;
 14 
 15 bit F(bit X[32], bit Y[32], bit Z[32])
 16 {
 17     return (X&Y) | (!X&Z);
 18 }
 19 
 20 bit G(bit X[32], bit Y[32], bit Z[32])
 21 {
 22     return X ^ Y ^ Z;
 23 }
 24 
 25 bit H(bit X[32], bit Y[32], bit Z[32])
 26 {
 27     return (X&Y) | (X&Z) | (Y&Z);
 28 }
 29 
 30 void main()
 31 {
 32     int i;
 33     for(i = 0; i < 16; i = i + 1)
 34     {
 35         W[i] = M[i];
 36     }
 37 
 38     for(i = 16; i < 80; i = i + 1)
 39     {
 40         __mem bit t[32] = (W[i - 3] ^ W[i - 8] ^ W[i - 14] ^ W[i - 16]) <<< 1;
 41         W[i] = t;
 42     }
 43 
 44     bit a[32] = A;
 45     bit b[32] = B;
 46     bit c[32] = C;
 47     bit d[32] = D;
 48     bit e[32] = E;
 49 
 50     // Round 1
 51     for(i = 0; i < 20; i = i + 1)
 52     {
 53         bit t[32] = sum(sum(sum(sum(a <<< 5, F(b, c, d), 32), e, 32), 0x5A827999, 32), W[i], 32);
 54         e = d;
 55         d = c;
 56         c = (b <<< 30);
 57         b = a;
 58         a = t;
 59     }
 60 
 61     // Round 2
 62     for(i = 20; i < 40; i = i + 1)
 63     {
 64         bit t[32] = sum(sum(sum(sum(a <<< 5, G(b, c, d), 32), e, 32), 0x6ED9EBA1, 32), W[i], 32);
 65         e = d;
 66         d = c;
 67         c = (b <<< 30);
 68         b = a;
 69         a = t;
 70     }
 71 
 72     // Round 3
 73     for(i = 40; i < 60; i = i + 1)
 74     {
 75         bit t[32] = sum(sum(sum(sum(a <<< 5, H(b, c, d), 32), e, 32), 0x8F1BBCDC, 32), W[i], 32);
 76         e = d;
 77         d = c;
 78         c = (b <<< 30);
 79         b = a;
 80         a = t;
 81     }
 82 
 83     // Round 4
 84     for(i = 60; i < 80; i = i + 1)
 85     {
 86         bit t[32] = sum(sum(sum(sum(a <<< 5, G(b, c, d), 32), e, 32), 0xCA62C1D6, 32), W[i], 32);
 87         e = d;
 88         d = c;
 89         c = (b <<< 30);
 90         b = a;
 91         a = t;
 92     }
 93 
 94     A = sum(A, a, 32);
 95     B = sum(B, b, 32);
 96     C = sum(C, c, 32);
 97     D = sum(D, d, 32);
 98     E = sum(E, e, 32);
 99     
100     // ����� ��������� ������ 512-������� �����    
101     
102     Hash[0] = A;
103     Hash[1] = B;
104     Hash[2] = C;
105     Hash[3] = D;
106     Hash[4] = E;
107 
108 }
sha-1code

 
  对应cnf的头部截图如下：