MD5算法分析与实现

概述

MD5(Message Digest 5) 是由 R.Rivest 设计的,它实现对任意长度的字符串进行运算,最终得出一个 128bit(即 32 个十六进制位) 长的消息摘要。除了 32 个十六进制位的长度以外,还有一种只有 16 个十六进制位长度的计算结果,本质上是从 32 个十六进制位结果中掐头去尾得到的(去除前 8 个十六进制位和后 8 个十六进制位)

算法实现过程

数据填充

MD5 处理数据是按照一个分组 512bit 来处理的,且最终要处理的数据最后 64bit 用来存储原始字符串的二进制 bit 长度。因此在长度填充这一步,我们需要通过填充数据使得填充后的消息长度(bit数)满足比 512 的倍数仅小 64。即 长度 ≡ 448 mod 512,或可以表达为 N*512+R, R 为余数

当 R < 448 时,需要填充到 448 bit
当 R > 448 时,需要填充 512bit-R+448 bit
当 R = 448 时,仍然要填上一个 512bit 分组

填充的形式是先填充一个 bit 1,后面再根据要求填充 n 个 bit 0。 (1 <= n <= 512)

添加长度信息

经过数据填充之后,还需要添加原文的二进制数据长度信息(原文的 bit 数),共 64bit (8 Bytes),若原文二进制数据长度大于 2^64bit,则只使用低 64bit 位(字节遵循 little-endian 编码)

定义参数和操作

MD5 有 4 个被称为链接变量的整数参数,在寄存器中的默认值为

A=0x01234567
B=0x89abcdef
C=0xfedcba98
D=0x76543210

考虑到小端字节序的影响,在实际的实现中常会定义成

A=0x67452301
B=0xefcdab89
C=0x98badcfe
D=0x10325476

同时 MD5 定义了四种非线性操作函数

F(X,Y,Z) = (X&Y)|((~X)&Z)
G(X,Y,Z) = (X&Z)|(Y&(~Z))
H(X,Y,Z) = X^Y^Z
I(X,Y,Z) = Y^(X|(~Z))

在上面的四种函数的基础上,生成四个重要的计算函数。我们令

a = A
b = B
c = C
d = D

FF(a, b, c, d, M[j], s, ti) 表示 a = b + ((a + F(b, c, d) + Mj + ti) <<< s)
GG(a, b, c, d, M[j], s, ti) 表示 a = b + ((a + G(b, c, d) + Mj + ti) <<< s)
HH(a, b, c, d, M[j], s, ti) 表示 a = b + ((a + H(b, c, d) + Mj + ti) <<< s)
II(a, b, c, d, M[j], s, ti) 表示 a = b + ((a + I(b, c, d) + Mj + ti) <<< s)

其中M[j]表示消息的第j个子分组(从0到15),一个子分组是一个分组 512bit 中的 32bit 即双字
<<< 表示无符号左移,常数 ti 是 4294967296*abs(sin(i)) 的整数部分,i 取值从 1 到 64,单位是弧度

循环计算

每次循环执行 64 次操作,64 次操作中每个计算函数执行 16 次,共循环 n 次,n 为 512bit 分组个数

第一轮循环计算

FF(a,b,c,d,M[0],7,0xd76aa478);
FF(d,a,b,c,M[1],12,0xe8c7b756);
FF(c,d,a,b,M[2],17,0x242070db);
FF(b,c,d,a,M[3],22,0xc1bdceee);
FF(a,b,c,d,M[4],7,0xf57c0faf);
FF(d,a,b,c,M[5],12,0x4787c62a);
FF(c,d,a,b,M[6],17,0xa8304613);
FF(b,c,d,a,M[7],22,0xfd469501) ;
FF(a,b,c,d,M[8],7,0x698098d8) ;
FF(d,a,b,c,M[9],12,0x8b44f7af) ;
FF(c,d,a,b,M[10],17,0xffff5bb1) ;
FF(b,c,d,a,M[11],22,0x895cd7be) ;
FF(a,b,c,d,M[12],7,0x6b901122) ;
FF(d,a,b,c,M[13],12,0xfd987193) ;
FF(c,d,a,b,M[14],17,0xa679438e) ;
FF(b,c,d,a,M[15],22,0x49b40821);

第二轮循环计算

GG(a,b,c,d,M[1],5,0xf61e2562);
GG(d,a,b,c,M[6],9,0xc040b340);
GG(c,d,a,b,M[11],14,0x265e5a51);
GG(b,c,d,a,M[0],20,0xe9b6c7aa) ;
GG(a,b,c,d,M[5],5,0xd62f105d) ;
GG(d,a,b,c,M[10],9,0x02441453) ;
GG(c,d,a,b,M[15],14,0xd8a1e681);
GG(b,c,d,a,M[4],20,0xe7d3fbc8) ;
GG(a,b,c,d,M[9],5,0x21e1cde6) ;
GG(d,a,b,c,M[14],9,0xc33707d6) ;
GG(c,d,a,b,M[3],14,0xf4d50d87) ;
GG(b,c,d,a,M[8],20,0x455a14ed);
GG(a,b,c,d,M[13],5,0xa9e3e905);
GG(d,a,b,c,M[2],9,0xfcefa3f8) ;
GG(c,d,a,b,M[7],14,0x676f02d9) ;
GG(b,c,d,a,M[12],20,0x8d2a4c8a);

第三轮循环计算

HH(a,b,c,d,M[5],4,0xfffa3942);
HH(d,a,b,c,M[8],11,0x8771f681);
HH(c,d,a,b,M[11],16,0x6d9d6122);
HH(b,c,d,a,M[14],23,0xfde5380c) ;
HH(a,b,c,d,M[1],4,0xa4beea44) ;
HH(d,a,b,c,M[4],11,0x4bdecfa9) ;
HH(c,d,a,b,M[7],16,0xf6bb4b60) ;
HH(b,c,d,a,M[10],23,0xbebfbc70);
HH(a,b,c,d,M[13],4,0x289b7ec6);
HH(d,a,b,c,M[0],11,0xeaa127fa);
HH(c,d,a,b,M[3],16,0xd4ef3085);
HH(b,c,d,a,M[6],23,0x04881d05);
HH(a,b,c,d,M[9],4,0xd9d4d039);
HH(d,a,b,c,M[12],11,0xe6db99e5);
HH(c,d,a,b,M[15],16,0x1fa27cf8) ;
HH(b,c,d,a,M[2],23,0xc4ac5665);

第四轮循环计算

II(a,b,c,d,M[0],6,0xf4292244) ;
II(d,a,b,c,M[7],10,0x432aff97) ;
II(c,d,a,b,M[14],15,0xab9423a7);
II(b,c,d,a,M[5],21,0xfc93a039) ;
II(a,b,c,d,M[12],6,0x655b59c3) ;
II(d,a,b,c,M[3],10,0x8f0ccc92) ;
II(c,d,a,b,M[10],15,0xffeff47d);
II(b,c,d,a,M[1],21,0x85845dd1) ;
II(a,b,c,d,M[8],6,0x6fa87e4f) ;
II(d,a,b,c,M[15],10,0xfe2ce6e0);
II(c,d,a,b,M[6],15,0xa3014314) ;
II(b,c,d,a,M[13],21,0x4e0811a1);
II(a,b,c,d,M[4],6,0xf7537e82) ;
II(d,a,b,c,M[11],10,0xbd3af235);
II(c,d,a,b,M[2],15,0x2ad7d2bb);
II(b,c,d,a,M[9],21,0xeb86d391);

最后输出 A B C D 的值拼接在一起即是最终答案(要注意字节序问题)

算法实现

RFC 1321

md5.h

/* MD5.H - header file for MD5C.C
 */

/* Copyright (C) 1991-2, RSA Data Security, Inc. Created 1991. All
rights reserved.

License to copy and use this software is granted provided that it
is identified as the "RSA Data Security, Inc. MD5 Message-Digest
Algorithm" in all material mentioning or referencing this software
or this function.

License is also granted to make and use derivative works provided
that such works are identified as "derived from the RSA Data
Security, Inc. MD5 Message-Digest Algorithm" in all material
mentioning or referencing the derived work.

RSA Data Security, Inc. makes no representations concerning either
the merchantability of this software or the suitability of this
software for any particular purpose. It is provided "as is"
without express or implied warranty of any kind.

Rivest                                                          [Page 8]
RFC 1321              MD5 Message-Digest Algorithm            April 1992

These notices must be retained in any copies of any part of this
documentation and/or software.
 */

#include "global.h"

/* MD5 context. */
typedef struct {
  UINT4 state[4];                                   /* state (ABCD) */
  UINT4 count[2];        /* number of bits, modulo 2^64 (lsb first) */
  unsigned char buffer[64];                         /* input buffer */
} MD5_CTX;

void MD5Init PROTO_LIST ((MD5_CTX *));
void MD5Update PROTO_LIST
  ((MD5_CTX *, unsigned char *, unsigned int));
void MD5Final PROTO_LIST ((unsigned char [16], MD5_CTX *));

void MD5Print PROTO_LIST((unsigned char digest[16]));

global.h

/* GLOBAL.H - RSAREF types and constants
 */

/* PROTOTYPES should be set to one if and only if the compiler supports
  function argument prototyping.
The following makes PROTOTYPES default to 0 if it has not already 
  been defined with C compiler flags.
 */


#ifndef PROTOTYPES
#define PROTOTYPES 0
#endif

/* POINTER defines a generic pointer type */
typedef unsigned char *POINTER;

/* UINT2 defines a two byte word */
typedef unsigned short int UINT2;

/* UINT4 defines a four byte word */
typedef unsigned long int UINT4;

/* PROTO_LIST is defined depending on how PROTOTYPES is defined above.
If using PROTOTYPES, then PROTO_LIST returns the list, otherwise it
  returns an empty list.
 */
#if PROTOTYPES
#define PROTO_LIST(list) list
#else
#define PROTO_LIST(list) ()
#endif

md5.c

/* MD5C.C - RSA Data Security, Inc., MD5 message-digest algorithm
 */

 /* Copyright (C) 1991-2, RSA Data Security, Inc. Created 1991. All
 rights reserved.

 License to copy and use this software is granted provided that it
 is identified as the "RSA Data Security, Inc. MD5 Message-Digest
 Algorithm" in all material mentioning or referencing this software
 or this function.

 License is also granted to make and use derivative works provided
 that such works are identified as "derived from the RSA Data
 Security, Inc. MD5 Message-Digest Algorithm" in all material
 mentioning or referencing the derived work.

 RSA Data Security, Inc. makes no representations concerning either
 the merchantability of this software or the suitability of this
 software for any particular purpose. It is provided "as is"
 without express or implied warranty of any kind.

 These notices must be retained in any copies of any part of this
 documentation and/or software.
  */

#include "global.h"
#include "md5.h"
#include <stdio.h>

  /* Constants for MD5Transform routine.*/

#define S11 7
#define S12 12
#define S13 17
#define S14 22
#define S21 5
#define S22 9
#define S23 14
#define S24 20
#define S31 4
#define S32 11
#define S33 16
#define S34 23
#define S41 6
#define S42 10
#define S43 15
#define S44 21

static void MD5Transform PROTO_LIST((UINT4[4], unsigned char[64]));
static void Encode PROTO_LIST((unsigned char *, UINT4 *, unsigned int));
static void Decode PROTO_LIST((UINT4 *, unsigned char *, unsigned int));
static void MD5_memcpy PROTO_LIST((POINTER, POINTER, unsigned int));
static void MD5_memset PROTO_LIST((POINTER, int, unsigned int));

static unsigned char PADDING[64] = {
  0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
};

/* F, G, H and I are basic MD5 functions.
 */
#define F(x, y, z) (((x) & (y)) | ((~x) & (z)))
#define G(x, y, z) (((x) & (z)) | ((y) & (~z)))
#define H(x, y, z) ((x) ^ (y) ^ (z))
#define I(x, y, z) ((y) ^ ((x) | (~z)))

 /* ROTATE_LEFT rotates x left n bits.
  */
#define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n))))

  /* FF, GG, HH, and II transformations for rounds 1, 2, 3, and 4.
  Rotation is separate from addition to prevent recomputation.*/
#define FF(a, b, c, d, x, s, ac) { \
 (a) += F ((b), (c), (d)) + (x) + (UINT4)(ac); \
 (a) = ROTATE_LEFT ((a), (s)); \
 (a) += (b); \
}
#define GG(a, b, c, d, x, s, ac) { \
 (a) += G ((b), (c), (d)) + (x) + (UINT4)(ac); \
 (a) = ROTATE_LEFT ((a), (s)); \
 (a) += (b); \
  }
#define HH(a, b, c, d, x, s, ac) { \
 (a) += H ((b), (c), (d)) + (x) + (UINT4)(ac); \
 (a) = ROTATE_LEFT ((a), (s)); \
 (a) += (b); \
  }
#define II(a, b, c, d, x, s, ac) { \
 (a) += I ((b), (c), (d)) + (x) + (UINT4)(ac); \
 (a) = ROTATE_LEFT ((a), (s)); \
 (a) += (b); \
  }

/* MD5 initialization. Begins an MD5 operation, writing a new context.
 */
void MD5Init(MD5_CTX *context)
//MD5_CTX *context;                                        /* context */
{
    context->count[0] = context->count[1] = 0;
    /* Load magic initialization constants.*/
    context->state[0] = 0x67452301;
    context->state[1] = 0xefcdab89;
    context->state[2] = 0x98badcfe;
    context->state[3] = 0x10325476;
}

/* MD5 block update operation. Continues an MD5 message-digest
  operation, processing another message block, and updating the
  context.
 */
void MD5Update(MD5_CTX *context, unsigned char *input, unsigned int inputLen)
//MD5_CTX *context;                                        /* context */
//unsigned char *input;                                /* input block */
//unsigned int inputLen;                     /* length of input block */
{
    unsigned int i, index, partLen;

    /* Compute number of bytes mod 64 */
    index = (unsigned int)((context->count[0] >> 3) & 0x3F);

    /* Update number of bits */
    if ((context->count[0] += ((UINT4)inputLen << 3))
    < ((UINT4)inputLen << 3))
        context->count[1]++;
    context->count[1] += ((UINT4)inputLen >> 29);

    partLen = 64 - index;

    /* Transform as many times as possible.*/
    if (inputLen >= partLen) {
        MD5_memcpy
        ((POINTER)&context->buffer[index], (POINTER)input, partLen);
        MD5Transform(context->state, context->buffer);

        for (i = partLen; i + 63 < inputLen; i += 64)
            MD5Transform(context->state, &input[i]);

        index = 0;
    }
    else
        i = 0;

    /* Buffer remaining input */
    MD5_memcpy
    ((POINTER)&context->buffer[index], (POINTER)&input[i],
        inputLen - i);
}

/* MD5 finalization. Ends an MD5 message-digest operation, writing the
  the message digest and zeroizing the context.
 */
void MD5Final(unsigned char digest[16], MD5_CTX *context)
//unsigned char digest[16];                         /* message digest */
//MD5_CTX *context;                                       /* context */
{
    unsigned char bits[8];
    unsigned int index, padLen;

    /* Save number of bits */
    Encode(bits, context->count, 8);

    /* Pad out to 56 mod 64.*/
    index = (unsigned int)((context->count[0] >> 3) & 0x3f);
    padLen = (index < 56) ? (56 - index) : (120 - index);
    MD5Update(context, PADDING, padLen);

    /* Append length (before padding) */
    MD5Update(context, bits, 8);
    /* Store state in digest */
    Encode(digest, context->state, 16);

    /* Zeroize sensitive information.*/
    MD5_memset((POINTER)context, 0, sizeof(*context));
}

/* MD5 basic transformation. Transforms state based on block.
 */
static void MD5Transform(UINT4 state[4], unsigned char block[64])
//UINT4 state[4];
//unsigned char block[64];
{
    UINT4 a = state[0], b = state[1], c = state[2], d = state[3], x[16];

    Decode(x, block, 64);

    /* Round 1 */
    FF(a, b, c, d, x[0], S11, 0xd76aa478); /* 1 */
    FF(d, a, b, c, x[1], S12, 0xe8c7b756); /* 2 */
    FF(c, d, a, b, x[2], S13, 0x242070db); /* 3 */
    FF(b, c, d, a, x[3], S14, 0xc1bdceee); /* 4 */
    FF(a, b, c, d, x[4], S11, 0xf57c0faf); /* 5 */
    FF(d, a, b, c, x[5], S12, 0x4787c62a); /* 6 */
    FF(c, d, a, b, x[6], S13, 0xa8304613); /* 7 */
    FF(b, c, d, a, x[7], S14, 0xfd469501); /* 8 */
    FF(a, b, c, d, x[8], S11, 0x698098d8); /* 9 */
    FF(d, a, b, c, x[9], S12, 0x8b44f7af); /* 10 */
    FF(c, d, a, b, x[10], S13, 0xffff5bb1); /* 11 */
    FF(b, c, d, a, x[11], S14, 0x895cd7be); /* 12 */
    FF(a, b, c, d, x[12], S11, 0x6b901122); /* 13 */
    FF(d, a, b, c, x[13], S12, 0xfd987193); /* 14 */
    FF(c, d, a, b, x[14], S13, 0xa679438e); /* 15 */
    FF(b, c, d, a, x[15], S14, 0x49b40821); /* 16 */

   /* Round 2 */
    GG(a, b, c, d, x[1], S21, 0xf61e2562); /* 17 */
    GG(d, a, b, c, x[6], S22, 0xc040b340); /* 18 */
    GG(c, d, a, b, x[11], S23, 0x265e5a51); /* 19 */
    GG(b, c, d, a, x[0], S24, 0xe9b6c7aa); /* 20 */
    GG(a, b, c, d, x[5], S21, 0xd62f105d); /* 21 */
    GG(d, a, b, c, x[10], S22, 0x2441453); /* 22 */
    GG(c, d, a, b, x[15], S23, 0xd8a1e681); /* 23 */
    GG(b, c, d, a, x[4], S24, 0xe7d3fbc8); /* 24 */
    GG(a, b, c, d, x[9], S21, 0x21e1cde6); /* 25 */
    GG(d, a, b, c, x[14], S22, 0xc33707d6); /* 26 */
    GG(c, d, a, b, x[3], S23, 0xf4d50d87); /* 27 */
    GG(b, c, d, a, x[8], S24, 0x455a14ed); /* 28 */
    GG(a, b, c, d, x[13], S21, 0xa9e3e905); /* 29 */
    GG(d, a, b, c, x[2], S22, 0xfcefa3f8); /* 30 */
    GG(c, d, a, b, x[7], S23, 0x676f02d9); /* 31 */
    GG(b, c, d, a, x[12], S24, 0x8d2a4c8a); /* 32 */

    /* Round 3 */
    HH(a, b, c, d, x[5], S31, 0xfffa3942); /* 33 */
    HH(d, a, b, c, x[8], S32, 0x8771f681); /* 34 */
    HH(c, d, a, b, x[11], S33, 0x6d9d6122); /* 35 */
    HH(b, c, d, a, x[14], S34, 0xfde5380c); /* 36 */
    HH(a, b, c, d, x[1], S31, 0xa4beea44); /* 37 */
    HH(d, a, b, c, x[4], S32, 0x4bdecfa9); /* 38 */
    HH(c, d, a, b, x[7], S33, 0xf6bb4b60); /* 39 */
    HH(b, c, d, a, x[10], S34, 0xbebfbc70); /* 40 */
    HH(a, b, c, d, x[13], S31, 0x289b7ec6); /* 41 */
    HH(d, a, b, c, x[0], S32, 0xeaa127fa); /* 42 */
    HH(c, d, a, b, x[3], S33, 0xd4ef3085); /* 43 */
    HH(b, c, d, a, x[6], S34, 0x4881d05); /* 44 */
    HH(a, b, c, d, x[9], S31, 0xd9d4d039); /* 45 */
    HH(d, a, b, c, x[12], S32, 0xe6db99e5); /* 46 */
    HH(c, d, a, b, x[15], S33, 0x1fa27cf8); /* 47 */
    HH(b, c, d, a, x[2], S34, 0xc4ac5665); /* 48 */

    /* Round 4 */
    II(a, b, c, d, x[0], S41, 0xf4292244); /* 49 */
    II(d, a, b, c, x[7], S42, 0x432aff97); /* 50 */
    II(c, d, a, b, x[14], S43, 0xab9423a7); /* 51 */
    II(b, c, d, a, x[5], S44, 0xfc93a039); /* 52 */
    II(a, b, c, d, x[12], S41, 0x655b59c3); /* 53 */
    II(d, a, b, c, x[3], S42, 0x8f0ccc92); /* 54 */
    II(c, d, a, b, x[10], S43, 0xffeff47d); /* 55 */
    II(b, c, d, a, x[1], S44, 0x85845dd1); /* 56 */
    II(a, b, c, d, x[8], S41, 0x6fa87e4f); /* 57 */
    II(d, a, b, c, x[15], S42, 0xfe2ce6e0); /* 58 */
    II(c, d, a, b, x[6], S43, 0xa3014314); /* 59 */
    II(b, c, d, a, x[13], S44, 0x4e0811a1); /* 60 */
    II(a, b, c, d, x[4], S41, 0xf7537e82); /* 61 */
    II(d, a, b, c, x[11], S42, 0xbd3af235); /* 62 */
    II(c, d, a, b, x[2], S43, 0x2ad7d2bb); /* 63 */
    II(b, c, d, a, x[9], S44, 0xeb86d391); /* 64 */

    state[0] += a;
    state[1] += b;
    state[2] += c;
    state[3] += d;

    /* Zeroize sensitive information.*/
    MD5_memset((POINTER)x, 0, sizeof(x));
}

/* Encodes input (UINT4) into output (unsigned char). Assumes len is
  a multiple of 4.
 */
static void Encode(unsigned char *output, UINT4 *input, unsigned int len)
//unsigned char *output;
//UINT4 *input;
//unsigned int len;
{
    unsigned int i, j;

    for (i = 0, j = 0; j < len; i++, j += 4) {
        output[j] = (unsigned char)(input[i] & 0xff);
        output[j + 1] = (unsigned char)((input[i] >> 8) & 0xff);
        output[j + 2] = (unsigned char)((input[i] >> 16) & 0xff);
        output[j + 3] = (unsigned char)((input[i] >> 24) & 0xff);
    }
}

/* Decodes input (unsigned char) into output (UINT4). Assumes len is
  a multiple of 4.
 */
static void Decode(UINT4 *output, unsigned char *input, unsigned int len)
//UINT4 *output;
//unsigned char *input;
//unsigned int len;
{
    unsigned int i, j;

    for (i = 0, j = 0; j < len; i++, j += 4)
        output[i] = ((UINT4)input[j]) | (((UINT4)input[j + 1]) << 8) |
        (((UINT4)input[j + 2]) << 16) | (((UINT4)input[j + 3]) << 24);
}

/* Note: Replace "for loop" with standard memcpy if possible.
 */

static void MD5_memcpy(POINTER output, POINTER input, unsigned int len)
//POINTER output;
//POINTER input;
//unsigned int len;
{
    unsigned int i;

    for (i = 0; i < len; i++)
        output[i] = input[i];
}

/* Note: Replace "for loop" with standard memset if possible.
 */
static void MD5_memset(POINTER output, int value, unsigned int len)
//POINTER output;
//int value;
//unsigned int len;
{
    unsigned int i;

    for (i = 0; i < len; i++)
        ((char *)output)[i] = (char)value;
}


void MD5Print(unsigned char digest[16])
{
    unsigned int i;

    for (i = 0; i < 16; i++)
        printf("%02x", digest[i]);
}

m.c

#include "md5.h"
#include "global.h"
#include <string.h>

int main()
{
    MD5_CTX context;
    unsigned char digest[16];
    unsigned int len = strlen("12345678901234567890123456789012345678901234567890123456789012345678901234567890");

    MD5Init(&context);
    MD5Update(&context, (unsigned char *)"12345678901234567890123456789012345678901234567890123456789012345678901234567890", len);
    MD5Final(digest, &context);

    MD5Print(digest);

    return 0;
}


Python hashlib

import hashlib

md5 = hashlib.md5()
md5.update(b'abc')

md5.digest()
md5.hexdigest() # 128 bit
md5.hexdigest()[8:24] # 64 bit

参考资料

[1] RFC 1321

Be the first to reply

发表评论

电子邮件地址不会被公开。 必填项已用*标注

20 − 3 =