HeyGap's_Blog

Be a positive learner

0%

Math Knowledge Summary

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

[0] 目录

  1. 数学算法

    1. [模乘]

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

  2. 密码学

    1. Stream Cipher

    2. Block Cipher

[1] MATH

[1-1] 模乘

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

蒙哥马利算法能够提高类似模幂运算的速度而实现的，主要是因为蒙哥马利算法巧妙地避免了大量模运算（除法），极大地降低了运算时间，下面介绍如何减少x*y mod N的模运算数目。

首先，蒙哥马利算法引入了REDC函数，该函数以大数T，模数N，模数N的逆元的负数N'和整数R（如果N为素数，R一般选取\(2^{n\_bit}\)，这样就可以在整除前提下用移位运算代替除法运算，也就是将下面代码第三行的整除运算换成移位运算）作为输入，在不使用模运算的情况下输出\(TR^{-1} mod N\)。该函数减少了模运算的数目，同时将T的蒙哥马利形式恢复成了普通形式。该函数的低效版python实现如下：

1
2
3
4
5
6
def REDC(R, N, N_inverse, T):
    m = ((T % R) * N_inverse) % R
    t = (T + m * N) // R
    if t >= N:
        return t - N
    return t

可以看到m的预计算使得t处于(0,2N)之间，我们可以用一次比较和一次减法代替模运算。如果想要进一步提升效率，可以将m提出这个函数放入查找表中，进一步减少模运算的数目。

接下来介绍大数T的蒙哥马利形式：假设我们有模数N，大整数T。其实T的蒙哥马利形式\(\overline{T}\)就是TR.其中 R ，且R与模数N互素，这样我们可以通过REDC函数来恢复T mod N。

假设我们有模数N，大数a和大数b，蒙哥马利模乘就是：先将a和b转化为蒙哥马利形式，然后计算\(\overline{a} * \overline{b}\)，也就是\(a*b*R^2\)，最后求解\(\overline{c} = REDC(\overline{a} * \overline{b})\)即可求得乘积c的蒙哥马利形式。我们可以将\(\overline{c}\)再丢进REDC函数即可获得c，也可以用\(\overline{c}\)进行之后的运算。

到目前为止，除了预计算m和求R的模逆元需要几次模运算外，所有运算均不涉及模运算，还保证了所有乘法运算都维持在modN的量级进行。

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
def extended_gcd(a, b):
    if a == 0:
        return b, 0, 1
    gcd, x1, y1 = extended_gcd(b % a, a)
    x = y1 - (b // a) * x1
    y = x1
    return gcd, x, y

def mod_inverse(a, m):
    gcd, x, y = extended_gcd(a, m)
    if gcd != 1:
        raise ValueError("Inverse doesn't exist")
    else:
        return x % m
    
def calc_n_bit(N):
    n_bit = 0
    while N > 0:
        N >>= 1
        n_bit += 1
    return n_bit
        
# 找到满足 N*N_inverse = -1 modR 的 N_inverse
def find_N_inverse(N, R):
    N_inv =  mod_inverse(N, R)
    N_inverse = (R - N_inv) % R
    return N_inverse
    
# 计算 TR^{-1} mod N，也就是把 T 的蒙哥马利形式转换回普通形式
def REDC(R, N, N_inverse, T):
    n_bit = calc_n_bit(N)
    m = ((T % R) * N_inverse) % R
    # print("t:" ,(T + m * N) / R)
    t = (T + m * N) >> n_bit
    if t >= N:
        return t - N
    return t

# 将 T 的普通形式转换为蒙哥马利形式
def convert_to_montgomery(R, N, T):
    return (T * R) % N

# 计算 T1 * T2 的蒙哥马利形式
def montgomery_multiply(T1, T2, N, R):
    product = T1 * T2
    N_inv = find_N_inverse(N, R)
    return REDC(R, N, N_inv, product)

if __name__ == "__main__":
    N = 2**4096 - 1
    n_bit = calc_n_bit(N)
    R = 1 << n_bit
    T1 = 231735531420147883
    T2 = 8270984215581679609
    # mont_T1 = T1 * R mod N
    mont_T1 = convert_to_montgomery(R, N, T1)
    # mont_T2 = T2 * R mod N
    mont_T2 = convert_to_montgomery(R, N, T2)
    print("montgomery_multiply: ", REDC(R, N, find_N_inverse(N, R), montgomery_multiply(mont_T1, mont_T2, N, R)))

[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-------------