ModpDES
实验内容
在作业三的基础上，把明文、密文、密钥的取值范围从任意64bit数据改为从0到p-1之间的整数，其中p是一个小于2^64的素数。密文应在密文空间内均匀分布。 在满足以上要求的前提下，测速。速度越快越好。
算法结构
加密算法
满足中间结果在模p的范围内且可逆的F函数的实现：
$F(R,roundKey)=R^{-1}*c+roundKey\mod p$
$F$ 函数的结果与左部 $L$ 进行模加运算，在解密时采用模减运算：
$L’=L+F\mod p$
解密算法
与加密算法唯一不同的地方在于 $F$ 函数的结果与 $L$ 之间是模减运算，即：
$L’=L-F\mod p$
算法实现
采用了 GNU MP 进行高精度运算，且可以很方便任意指定 p 的范围。
p 的选取
p 需要为素数，采用随机数 + 素性检测的方法生成大素数 p：
1
2
3
4
5
6
7
8
9
10
11
void get_prime(mpz_t p, gmp_randstate_t state) {
mpz_rrandomb(p, state, PRIME_LENGTH);
while (!(mpz_millerrabin(p, PRIME_LENGTH))) {
gmp_randclear(state);
GMP_SEED++;
init_random_state(state);
mpz_rrandomb(p, state, PRIME_LENGTH);
}
gmp_randclear(state);
GMP_SEED++;
}
其中 $p < 2^{PRIME_LENGTH}$，设置 PRIME_LENGTH 为 64，也可以设置为 1024，那么就会生成最大 1024 位素数。
密钥生成
密钥生成采用随机数生成算法，不严谨地随机生成 ROUNDS 个轮密钥，随机数不超过 p。
1
2
3
4
5
6
7
8
9
10
void init_des_key(des_key *key, mpz_t p, gmp_randstate_t state) {
mpz_init(key->p);
for (int i = 0; i < ROUNDS; i++) mpz_init(key->roundkey[i]);
mpz_set(key->p, p);
for (int i = 0; i < ROUNDS; i++) {
init_random_state(state);
GMP_SEED++;
mpz_urandomm(key->roundkey[i], state, key->p);
}
}
显然算法的重点不在这里，也可以采取 DES 密钥生成策略生成密钥然后对 p 取模。由于上次实验设计的框架和本次不一致，方便起见采用随机数生成生成密钥。
加密算法
加密算法在前文中有详细介绍。左部和右部通过对 p 进行除法提取。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void des_encrypt(mpz_t cipher, mpz_t plain, des_key *key) {
mpz_t left, right, tmp;
mpz_inits(left, right, tmp, NULL);
mpz_divmod(left, right, plain, key->p);
for (int round = 0; round < ROUNDS; round++) {
if (mpz_cmp_ui(right, 0) != 0)
mpz_invert(tmp, right, key->p);
else
mpz_set_ui(tmp, 0);
mpz_add(tmp, tmp, key->roundkey[round]);
mpz_mod(tmp, tmp, key->p);
mpz_add(left, tmp, left);
mpz_mod(left, left, key->p);
if (round != ROUNDS - 1)
mpz_swap(left, right);
}
mpz_mul(cipher, left, key->p);
mpz_add(cipher, cipher, right);
}
采用了 GNU MP，使得代码十分简洁，默认 c = 1。
解密算法
解密算法在前文中有详细介绍。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void des_decrypt(mpz_t decrypt, mpz_t cipher, des_key *key) {
mpz_t left, right, tmp;
mpz_inits(left, right, tmp, NULL);
mpz_divmod(left, right, cipher, key->p);
for (int round = 0; round < ROUNDS; round++) {
if (mpz_cmp_ui(right, 0) != 0)
mpz_invert(tmp, right, key->p);
else
mpz_set_ui(tmp, 0);
mpz_add(tmp, tmp, key->roundkey[ROUNDS - round - 1]);
mpz_mod(tmp, tmp, key->p);
mpz_sub(left, left, tmp);
mpz_mod(left, left, key->p);
if (round != ROUNDS - 1)
mpz_swap(left, right);
}
mpz_mul(decrypt, left, key->p);
mpz_add(decrypt, decrypt, right);
}
测试以及测速
测试代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void test() {
mpz_t cipher, plain, decrypt;
mpz_t p;
gmp_randstate_t state;
des_key key;
mpz_inits(cipher, plain, decrypt, p, NULL);
printf("generating prime p (0 < p < 2^64)...\n");
init_random_state(state);
get_prime(p, state);
gmp_printf("p: %Zd\n", p);
gmp_printf("generating des round key...\n");
init_des_key(&key, p, state);
gmp_printf("generate successful\n");
mpz_set_ui(plain, 151654);
gmp_printf("plain : %Zd\n", plain);
des_encrypt(cipher, plain, &key);
gmp_printf("cipher : %Zd\n", cipher);
des_decrypt(decrypt, cipher, &key);
gmp_printf("decrypt: %Zd\n", decrypt);
}
测速代码（仅测试加密速率）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void speed_test() {
mpz_t cipher, plain, decrypt;
mpz_t p;
gmp_randstate_t state;
des_key key;
mpz_inits(cipher, plain, decrypt, p, NULL);
init_random_state(state);
get_prime(p, state);
init_des_key(&key, p, state);
mpz_set_ui(plain, 151654);
int loops = 100000;
clock_t s = clock();
for (int i = 0; i < loops; i++)
des_encrypt(cipher, plain, &key);
clock_t e = clock();
double duration = (double)(e - s) / CLOCKS_PER_SEC;
printf("encryt duration: %f, speed: %f Mb/s\n", duration, PRIME_LENGTH * loops / duration);
}
64位
通过算法生成 p 为：
1
p = 18446739675663041537;
加密文本为：
1
plain = 151654;
测试情况如下：
测速情况如下（仅测试加密速率）：
1024 位
修改 PRIME_LENGTH 为 1024：
生成素数 p 为：
1
p = 179769313486231590772930519078902473361797697894230657273430081150904629026231992356050709088708968036843881357819903401413021769568042490967592189401527550685296299704105256828626581384655961225634853109792929171318130310013549960126406630992433575970987465685771520777644415753672756745104477155689978920959;
测试结果如下：
加解密正常。
测速结果如下：
