计算机安全之密码安全从 Hash 到 MD5

字符串哈希就是把一个字符串变成 long long 存起来, 然后对 1e9 + 7 取模, $b[i] = s[i]*{131}^{s.length() - 1 - i}$ ,sum[i] 存的是 b[i] 的前缀和

如果出现哈希冲突的话我们需要采取的措施是算出这个字符串的两个哈希值然后进行比较如果说 131 是 base1 那么需要定义 base2 值为 313

以下是实现代码

#include <bits/stdc++.h>
using namespace std;

long long mod = 1e9 + 7;
long long base1 = 131LL, base2 = 313LL;
const int maxn = 1e5 + 10;
char s[maxn];

int main() {
    scanf("%s", s);
    int len = strlen(s);

    long long hash1 = 0, hash2 = 0;
    for(int i = 0; i < len; i ++) {
        hash1 = hash1 * base1 % mod;
        hash1 = (hash1 + s[i]) % mod;

        hash2 = hash2 * base2 % mod;
        hash2 = (hash2 + s[i]) % mod;
    }

    printf("%lld %lld
", hash1, hash2);

    return 0;
}

但是这种哈希的办法还是很容易被破解因为哈希出来的值的种类有限所以很容易被破解那么这个时候我们可以选择一种更为复杂的算法对我们的密码进行加密于是就有了 MD5 算法

string password；

算法思想：要使得 password.length() % 512 == 448 所以在长度不够的时候要对字符串进行填充注意是在字符串后面进行填充第一位填充为 1 其余用 0 填充在填充之后再在填充好的字符串后加上原密码串如果此时消息长度大于 $2^64$ 取低位的 64 位的值

数据处理：需要用到的四个常数 A:0x67452301 B:0x0EFCDAB89 C:0x98BADCFE D:0x10325476

需要用到的四个函数：① 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))

把消息分以 512 位为一分组进行处理，每一个分组进行 4 轮变换，以上面所说 4 个常数为起始变量进行计算，重新输出 4 个变量，以这 4 个变量再进行下一分组的运算，如果已经是最后一个分组，则这 4 个变量为最后的结果，即MD5值。

代码实现：

#include <bits/stdc++.h>
using namespace std;

#define shift(x, n) (((x) << (n)) | ((x) >> (32-(n))))
#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)))
#define A 0x67452301
#define B 0xefcdab89
#define C 0x98badcfe
#define D 0x10325476

unsigned int strlength;
unsigned int atemp;
unsigned int btemp;
unsigned int ctemp;
unsigned int dtemp;

const unsigned int k[]={
        0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee,
        0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501, 0x698098d8,
        0x8b44f7af, 0xffff5bb1, 0x895cd7be, 0x6b901122, 0xfd987193,
        0xa679438e, 0x49b40821, 0xf61e2562, 0xc040b340, 0x265e5a51,
        0xe9b6c7aa, 0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8,
        0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed, 0xa9e3e905,
        0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a, 0xfffa3942, 0x8771f681,
        0x6d9d6122, 0xfde5380c, 0xa4beea44, 0x4bdecfa9, 0xf6bb4b60,
        0xbebfbc70, 0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x04881d05,
        0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665, 0xf4292244,
        0x432aff97, 0xab9423a7, 0xfc93a039, 0x655b59c3, 0x8f0ccc92,
        0xffeff47d, 0x85845dd1, 0x6fa87e4f, 0xfe2ce6e0, 0xa3014314,
        0x4e0811a1, 0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391};

const unsigned int s[]={7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7,
        12, 17, 22, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20,
        4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 6, 10,
        15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21};
const char str16[] = "0123456789abcdef";

void mainLoop(unsigned int M[]) {
    unsigned int f, g;
    unsigned int a = atemp;
    unsigned int b = btemp;
    unsigned int c = ctemp;
    unsigned int d = dtemp;
    for(unsigned int i = 0; i < 64; i ++) {
        if(i < 16) {
            f = F(b, c, d);
            g = i;
        } else if (i < 32) {
            f = G(b, c, d);
            g = (5 * i + 1) % 16;
        } else if(i < 48) {
            f = H(b, c, d);
            g = (3 * i + 5) % 16;
        } else {
            f = I(b, c, d);
            g = (7 * i) % 16;
        }
        unsigned int tmp = d;
        d = c;
        c = b;
        b = b + shift((a + f + k[i] + M[g]), s[i]);
        a = tmp;
    }
    atemp = a + atemp;
    btemp = b + btemp;
    ctemp = c + ctemp;
    dtemp = d + dtemp;
}

unsigned int* add(string str) {
    unsigned int num = ((str.length() + 8) / 64) + 1;
    unsigned int *strByte = new unsigned int[num * 16];
    strlength = num * 16;
    for (unsigned int i = 0; i < num * 16; i ++)
        strByte[i] = 0;
    for (unsigned int i = 0; i < str.length(); i ++) {
        strByte[i >> 2] |= (str[i]) << ((i % 4) * 8);
    }
    strByte[str.length() >> 2] |= 0x80 << (((str.length() % 4)) * 8);

    strByte[num * 16 - 2] = str.length() * 8;
    return strByte;
}
string changeHex(int a) {
    int b;
    string str1;
    string str = "";
    for(int i = 0; i < 4; i ++) {
        str1 = "";
        b = ((a >> i * 8) % (1 << 8)) & 0xff;
        for (int j = 0; j < 2; j ++) {
            str1.insert(0, 1, str16[b % 16]);
            b = b / 16;
        }
        str += str1;
    }
    return str;
}

string getMD5(string source) {
    atemp = A;
    btemp = B;
    ctemp = C;
    dtemp = D;
    unsigned int *strByte = add(source);
    for(unsigned int i = 0; i < strlength / 16; i ++) {
        unsigned int num[16];
        for(unsigned int j = 0; j < 16; j ++)
            num[j] = strByte[i * 16 + j];
        mainLoop(num);
    }
    return changeHex(atemp).append(changeHex(btemp)).append(changeHex(ctemp)).append(changeHex(dtemp));
}

int main() {
    string ss;
    cin >> ss;
    string s = getMD5(ss);
    cout << s << endl << endl << endl;
    return 0;
}

　　　　　　　　　　　　　　　　　That's All

计算机安全之密码安全 从 Hash 到 MD5

计算机安全之密码安全从 Hash 到 MD5