计算机安全总结

type

status

date

slug

summary

RSA算法

概述

RSA算法可以分为3个部分：生成密钥、加密和解密，过程如下：

随机生成两个大的质数和

计算，计算欧拉函数

随机生成一个数字，满足条件，且和互质

求解关于模的乘法逆元

公钥对，私钥对

加密：

解密：

费马小定理

对于整数，若是质数，则一定有，或者表示为，反之不一定成立，即费马小定理是是质数的必要不充分条件。

二次探测定理

若是质数，且，那么

欧拉函数

表示小于等于的自然数中与互质的自然数的个数

代码

首先使用函数generate_big_prime()来生成大质数和，这里默认生成长度为1024位的大数，然后调用函数miller_rabin(a,p)来判断是否是质数，默认随机生成8个不同的来进行检测。

函数的实现：首先使用费马小定理来排除合数，然后使用二次探测定理，将分解成的形式，若是质数，那么对于整数，则一定满足条件。然后计算，然后对不断平方，继续判断，若，有条件成立，那么一定不是质数。过程中需要用到快速模幂函数fast_pow_mod(a,b,c)来计算。对于miller_rabin(a,p)函数的正确性，我们使用macOS自带的openssl prime命令来进行检测和判断。

生成和以后，接着计算，由于和都是质数，可以利用欧拉函数的性质，即

对于模的乘法逆元：若，则，这里调用函数multiplicative_inverse(a,b)使用扩展欧几里德算法来实现。

现在我们获取了公钥对和私钥对，然后开始加密，由于加密的信息通常为文本形式，我们这里调用函数transform_string_to_int(message)先将字符串转换成字节，然后再转成整数即可，解密的时候逆向操作即可，将整数转成字节再转成字符串即可。

MD5算法

概述

如果信息的长度（bit）mod 512的结果不等于448，那么需要对信息进行填充，使其长度mod 512的结果等于448，填充方法是填充一个1和若干个0，填充完毕后，信息的长度应该为（bit）

剩下的64位用来填充原信息的长度，这64位直接加到第一步结果的后面，如果原本信息的长度大于，那么省略高位，直接将低64位进行填充，填充过后的总的长度应该是

MD5的哈希结果长度为128bit，按每32位分成4组，这4组的结果由4个初始值不断演变所得到，其中初始值分别为A=0x67452301，B=0xefcdba89，C=0x98badcfe，D=0x10325476

对每一个512bit长的分组进行四轮循环，再将每个512bit分成16个小组，每组32bit（4个字节），共要用到四种线性函数，这里不列举了

所有循环结束后，就会生成4组32位长的哈希值，将他们转换为字符串后再拼接即可

代码

这里先判断加密对象是字符串还是文件，若是字符串使用encode()函数转成即可，若是文件直接调read()读取二进制数据。然后调用函数divide_group进行分组，调用trans()函数进行处理。然后我先是处理了前面整512位的分组，待前面的处理完后再对余项进行填充和二次处理，在进行轮换运算时会用到常数项，计算方法为，处理完余项后调用函数get_hash_hex_string()将结果中的32位长度的A、B、C、D转成对应的16进制字符串再拼接即可。