HeyGap's_Blog

Be a positive learner

0%

Math Knowledge Summary

发表于 更新于 分类于
总结一下计算机中的数学相关内容，便于后续调用

[0] 目录

  1. 数学算法

  2. 密码学

    1. Stream Cipher

    2. Block Cipher

[1] MATH

[1-1] 模乘

[1-1-1] 蒙哥马利算法

按照笔算的思维，计算模乘需要进行一次乘法，再进行一次除法。但除法对计算来说不是很友好，我们希望减少除法的次数（其实除法模块就是乘法/加法/减法的组合），因此我们可以使用蒙哥马利模乘(MMF)，蒙哥马利模乘就是一次乘法+两次蒙哥马利约简(REDC)

假设我们要计算 $a*b \mod N$，

，$aR^{-1} = REDC(x)$，R 满足GCD

而蒙哥马利模乘其实就是，下文将记 x 的蒙哥马利约简为 REDC(x)

[1] Stream Cipher

[1-1] RC4

[1-1-1] 基本原理

加密: 明文与 keystream 异或得到密文

密文: 密文与 keystream 异或得到明文

keystream 与明文等长

由于 RC4 采取逐位异或的加密方式，只要我们知道了密文和key，只需要放到 cyberchef 里再加密一次就能得到原文

[1-1-2] 生成密钥流（keystream）

RC4 的密钥流生成由两部分组成：

  1. KSA（the Key-Scheduling Algorithm）

  2. PRGA（the Pseudo-Random Generation Algorithm）

KSA: 利用key生成S盒

1
2
3
4
5
6
7
8
9
10
11
12
13
int i = 0;
int j = 0;
char T[SBOX_LEN] = {0};

for (i = 0; i < SBOX_LEN; i++) {
    Sbox[i] = i;
    T[i] = key[ i % key_length ];
}

for (i = 0; i < SBOX_LEN; i++) {
    j = (j + Sbox[i] + T[i]) % SBOX_LEN;
    swap(&Sbox[i], &Sbox[j]);
}

PRGA: 利用S盒生成密钥流

1
2
3
4
5
6
7
8
9
10
11
int i = 0;
int j = 0;
int t = 0;

for (int k = 0; k < data_len; k++) {
    i = (i + 1) % SBOX_LEN;
    j = (j + Sbox[i]) % SBOX_LEN;
    swap(&Sbox[i], &Sbox[j]);
    t = (Sbox[i] + Sbox[j]) % SBOX_LEN;
    puc_key_stream[k] = Sbox[t];
}

[1-1-3] 完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include<stdio.h>
#include<string.h>
 
#define SBOX_LEN 256
 
#define rc4_encrypt rc4_crypt
#define rc4_decrypt rc4_crypt
 
static inline void swap_uchar(unsigned char *puc_x, unsigned char *puc_y)
{
    *puc_x = *puc_x ^ *puc_y;
    *puc_y = *puc_x ^ *puc_y;
    *puc_x = *puc_x ^ *puc_y;
}
 
void hexdump(unsigned char *puc_data, int length)
{
    int i = 0;
 
    for (i = 0; i < length; i++) {
        printf("%02X", puc_data[i]);
        if (i && (i + 1) % 16 == 0) {
            putchar('\n');
        }
    }
    printf("\n");
}
 
/**
 * 利用Key生成S盒
 * the Key-Scheduling Algorithm
 */
static void rc4_ksa(unsigned char *puc_sbox, unsigned char *puc_key, int key_length)
{
    int i = 0;
    int j = 0;
    char tmp[SBOX_LEN] = {0};
 
    for (i = 0; i < SBOX_LEN; i++) {
        puc_sbox[i] = i;
        tmp[i] = puc_key[i % key_length];
    }
 
    for (i = 0; i < SBOX_LEN; i++) {
        j = (j + puc_sbox[i] + tmp[i]) % SBOX_LEN;
        swap_uchar(&puc_sbox[i], &puc_sbox[j]); //交换puc_sbox[i]和puc_sbox[j]
    }
}
 
/**
 * 利用S盒生成密钥流
 * The pseudo-random generation algorithm(PRGA)
 */
static void rc4_prga(unsigned char *puc_sbox, unsigned char *puc_key_stream, unsigned long ul_data_length)
{
    int i = 0;
    int j = 0;
    int t = 0;
    unsigned long k = 0;
 
    for (k = 0; k < ul_data_length; k++) {
        i = (i + 1) % SBOX_LEN;
        j = (j + puc_sbox[i]) % SBOX_LEN;
        swap_uchar(&puc_sbox[i], &puc_sbox[j]);
        t = (puc_sbox[i] + puc_sbox[j]) % SBOX_LEN;
        /* 为了更清晰理解rc4算法流程，此处保存keystream，不直接进行XOR运算 */
        puc_key_stream[k] = puc_sbox[t];
    }
}
 
/* 加解密 */
void rc4_crypt(unsigned char *puc_data, unsigned char *puc_key_stream, unsigned long ul_data_length)
{
    unsigned long i = 0;
 
    /* 把PRGA算法放在加解密函数中可以不需要保存keystream */
    for (i = 0; i < ul_data_length; i++) {
        puc_data[i] ^= puc_key_stream[i];
    }
}
 
int main(int argc, char *argv[])
{
    unsigned char sbox[SBOX_LEN] = {0};
    char key[SBOX_LEN] = {"HeyGap"}; //秘钥内容随便定义
    char data[512] = "HeyGap";
    unsigned char puc_keystream[512] = {0};
    unsigned long ul_data_length = strlen(data);
 
    printf("key=%s, length=%d\n\n", key, strlen(key));
    printf("Raw data string:%s\n", data);
    printf("Raw data hex:\n");
    hexdump(data, ul_data_length);
 
    /* 生成S-box */
    rc4_ksa(sbox, (unsigned char *)key, strlen(key));
 
    /* 生成keystream并保存,S-box也会被更改 */
    rc4_prga(sbox, puc_keystream, ul_data_length);
 
    printf("S-box final status:\n");
    hexdump(sbox, sizeof(sbox));
 
    printf("key stream:\n");
    hexdump(puc_keystream, ul_data_length);
 
    /* 加密 */
    rc4_encrypt((unsigned char*)data, puc_keystream, ul_data_length);
 
    printf("cipher hexdump:\n");
    hexdump(data, ul_data_length);
 
    /* 解密 */
    rc4_decrypt((unsigned char*)data, puc_keystream, ul_data_length);
 
    printf("decypt data:%s\n", data);
 
    return 0;
}

[2] Block Cipher

[2-1] Tea/xTea/xxTea

[2-1-1] Tea decrypt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<iostream>
using namespace std;
uint32_t key[4] = {1234,2341,3412,4123};
uint32_t delta = 0xDEADBEEF;

void tea_decrypt(uint32_t *encrypted) {
    uint32_t sum = 0;
    uint32_t enc_tmp1 = encrypted[0],enc_tmp2 = encrypted[1];
    for(int i=0;i<32;i++) {
        sum += delta;
    }
    for(int i=0;i<32;i++) {
        enc_tmp2 -= (sum + enc_tmp1) ^ (16 * enc_tmp1 + key[2]) ^ (32 * enc_tmp1 + key[3]);
        enc_tmp1 -= (sum + enc_tmp2) ^ (16 * enc_tmp2 + key[0]) ^ (32 * enc_tmp2 + key[1]);
        sum -= delta;
    }
    encrypted[0] = enc_tmp1;
    encrypted[1] = enc_tmp2;
}

int main() {
    unsigned char encflag[] = {
        0
    };
    tea_decrypt((uint32_t *)encflag+0);
    tea_decrypt((uint32_t *)encflag+2);
    tea_decrypt((uint32_t *)encflag+4);
    tea_decrypt((uint32_t *)encflag+6);
    cout<<(char *)encflag<<endl;

    system("pause");
    return 0;
}

[2-1-2] xTea decrypt

[2-1-3] xxTea decrypt

-------------文章就到这里啦！感谢您的阅读XD-------------