计算机安全总结

2019年01月08日 699点热度 0人点赞 0条评论

RSA算法

概述

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

  1. 随机生成两个大的质数$p$和$q$
  2. 计算$n=p\times q$,计算欧拉函数$\phi(n)$
  3. 随机生成一个数字$e$,满足条件$1<e<\phi(n)$,且$e$和$\phi(n)$互质
  4. 求解$e$关于$\phi(n)$模的乘法逆元$d=e^{-1}\;mod\;\phi(n)$
  5. 公钥对$(e,n)$,私钥对$(d,n)$
  6. 加密:$C=M^e\;mod\;n$
  7. 解密:$M=C^d\;mod\;n$

费马小定理

对于整数$a$,若$p$是质数,则一定有$a^p\;mod\;p=x$,或者表示为$a^{p-1}\;mod\;p=1$,反之不一定成立,即费马小定理是$p$是质数的必要不充分条件

二次探测定理

若$p$是质数,且$a^2\equiv1(mod\;p)$,那么$a\equiv \pm1(mod\;p)$

欧拉函数

$\phi(n)$表示小于等于$n$的自然数中与$n$互质的数的个数

代码

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

$miller\_rabin(a,p)$函数的实现:首先使用费马小定理来排除合数,然后使用二次探测定理,将$p-1$分解成$2^k\cdot t$的形式,若$p$是质数,那么对于整数$a$,则一定满足条件$a^{2^k\cdot t}\equiv 1(mod\;p)$。然后计算$a^t\;mod\;p$,然后对$a^t$不断平方,继续判断,若$\exists a\in N^*,\;\forall 0\leq r\leq k-1$,有条件$a^{2^r\cdot d}\not\equiv 1(mod\;p)$生理,那么$p$一定不是质数。过程中需要用到快速模幂函数$fast\_pow\_mod(a,b,c)$来计算$a^b\;mod\;c$。对于$miller\_rabin(a,p)$函数的正确性,我们使用$macOS$自带的$openssl\;prime$命令来进行检测和判断。

生成$p$和$q$以后,接着计算$\phi(n)$,由于$p$和$q$都是质数,可以利用欧拉函数的性质,即$\phi(n)=\phi(p)\times \phi(q)=(p-1)\times(q-1)$

对于模的乘法逆元:若$e\cdot d\equiv 1(mod\;\phi(n))$,则$d=e^{-1}\;mod\;\phi(n)$,这里调用函数$multiplicative\_inverse(a, b)$使用扩展欧几里德算法来实现。

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

"""
@project: Computer-Security
@author: sam
@file rsa.py
@ide: PyCharm
@time: 2018-12-24 10:14:31
@blog: https://jiahaoplus.com
"""
from random import randint
from math import floor, log, gcd


def multiplicative_inverse(a, b):
    """Solve Multiplicative Inverse
    a * x === 1 (mod b)
    :param a:
    :param b:
    :return: x
    """
    r1, r2 = b, a
    t1, t2 = 0, 1
    while r2 > 0:
        q = r1 // r2
        r = r1 - q * r2
        r1 = r2
        r2 = r

        t = t1 - q * t2
        t1 = t2
        t2 = t

    if t1 < 0:
        t1 = t1 + b

    return t1


def fast_pow_mod(a, b, c):
    """Fast Power Mod Method
    :param a:
    :param b:
    :param c:
    :return: (a ^ b) mod c
    """
    result = 1
    while b != 0:
        if b & 1:
            result = (result * a) % c
        b >>= 1
        a = (a * a) % c
    return result


def miller_rabin(a, p):
    """Miller Rabin Method
    :param a:
    :param p:
    :return: Boolean
    """
    if p == 1:
        return False
    if p == 2:
        return True

    # Fermat's Little Theorem
    # If p is prime, for all integer a, a ^ (p - 1) mod p == 1
    # To exclude composite number
    if fast_pow_mod(a, p - 1, p) != 1:
        return False

    # Decomposition p - 1 into (2 ^ k) * t
    k = int(floor(log(p - 1, 2)))
    t = 1
    while k > 0:
        t = (p - 1) // (2 ** k)
        if (p - 1) % (2 ** k) == 0 and t % 2 == 1:
            break
        k = k - 1

    # Quadratic Detection Theorem
    # Solve a ^ ((2 ^ k) * t) mod p
    tmp = fast_pow_mod(a, t, p)
    for i in range(k):
        # Check whether tmp equals p - 1 or 1
        if tmp == p - 1 or tmp == 1:
            return True
        tmp = (tmp ** 2) % p

    if tmp == 1:
        return True

    return False


def check_prime(p, k=8):
    """Check whether p is prime or not
    :param p: number
    :param k: Check times(default 8)
    :return: Boolean
    """
    if k < 0:
        k = 8

    while k > 0:
        a = randint(1, p - 1)
        if not miller_rabin(a, p):
            return False
        k = k - 1
    return True


def generate_big_prime(length=1024):
    """Generate a big prime number
    :param length: default 1024
    :return:
    """
    while True:
        num = randint(0, 1 << length)
        if num % 2 == 0:
            num = num + 1
        if check_prime(num):
            return num


def generate_key():
    """Generate RSA KEY
    :return: rsa_key('private_key', 'public_key')
    """
    p = generate_big_prime()
    q = generate_big_prime()
    n = p * q
    phi = (p - 1) * (q - 1)

    while True:
        e = randint(2, phi)
        if gcd(e, phi) == 1:
            break

    d = multiplicative_inverse(e, phi)

    key = {'public': [e, n], 'private': [d, n]}
    return key


def encryption(message, public_key):
    """Encryption
    :param message:
    :param public_key:
    :return: C = M ^ e mod n
    """
    result = fast_pow_mod(message, public_key[0], public_key[1])
    return result


def decryption(message, private_key):
    """Decryption
    :param message:
    :param private_key:
    :return: M = C ^ d mod n
    """
    result = fast_pow_mod(message, private_key[0], private_key[1])
    return result


def transform_string_to_int(message):
    """Transform Text to Int
    Transform String to Bytes, then to the Hex, finally to Int
    :param message: String
    :return: Int
    """
    return int(message.encode().hex(), 16)


def transform_int_to_string(message):
    """Transform Int to Text
    Transform Int to Hex, then to Bytes, finally to String
    :param message: Int
    :return: String
    """
    return bytes.fromhex(hex(message)[2:]).decode()


if __name__ == '__main__':
    print('Generating RSA KEY...')
    rsa_key = generate_key()
    print('Finished')
    while True:
        M = transform_string_to_int(input('Please input message : '))
        C = encryption(M, rsa_key['public'])
        print('After encryption data :', C)
        M = transform_int_to_string(decryption(C, rsa_key['private']))
        print('After decryption data :', M)
        print('--------------------------------')

MD5算法

概述

  1. 如果信息的长度(bit)mod 512的结果不等于448,那么需要对信息进行填充,使其长度mod 512的结果等于448,填充方法是填充一个1和若干个0,填充完毕后,信息的长度应该为$512\cdot N+448$(bit)
  2. 剩下的64位用来填充原信息的长度,这64位直接加到第一步结果的后面,如果原本信息的长度大于$2^{64}$,那么省略高位,直接将低64位进行填充,填充过后的总的长度应该是$(N+1)\cdot 512$
  3. MD5的哈希结果长度为128bit,按每32位分成4组,这4组的结果由4个初始值不断演变所得到,其中初始值分别为$A=0x67452301$,$B=0xefcdba89$,$C=0x98badcfe$,$D=0x10325476$
  4. 对每一个512bit长的分组进行四轮循环,再将每个512bit分成16个小组,每组32bit(4个字节),共要用到四种线性函数,这里不列举了
  5. 所有循环结束后,就会生成4组32位长的哈希值,将他们转换为字符串后再拼接即可

代码

这里先判断加密对象是字符串还是文件,若是字符串使用$encode()$函数转成即可,若是文件直接调用$read()$读取二进制数据。然后调用函数$divide\_group$进行分组,调用$trans()$函数进行处理。然后我先是处理了前面整512位的分组,待前面的处理完后再对余项进行填充和二次处理,在进行轮换运算时会用到常数项$t_i$,计算方法为$hex(floor(abs(sin(i)))\times 2^{32})$,处理完余项后调用函数$get\_hash\_hex\_string()$将$result$中的32位长度的A、B、C、D转成对应的16进制字符串再拼接即可。

"""
@project: Computer-Security
@author: sam
@file md5.py
@ide: PyCharm
@time: 2018-12-24 16:57:28
@blog: https://jiahaoplus.com
"""
# Initialization Constants
from math import floor, sin

A = 0x67452301
B = 0xefcdab89
C = 0x98badcfe
D = 0x10325476

S = [[7, 12, 17, 22],
     [5, 9, 14, 20],
     [4, 11, 16, 23],
     [6, 10, 15, 21]]

# [abs(sin(x)) * (2 ^ 32)]
t = [int(hex(floor(abs(sin(i + 1)) * (2 ** 32))), 16) for i in range(64)]

result = [A, B, C, D]

convert_to_hex = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f']


def F(x, y, z):
    """F(x, y, z) = (x & y) | ((~x) & z)
    :param x: Byte
    :param y: Byte
    :param z: Byte
    :return: Byte
    """
    return (x & y) | ((~x) & z)


def G(x, y, z):
    """G(x, y, z) = (x & z) | (y & (~Z))
    :param x: Byte 
    :param y: Byte 
    :param z: Byte 
    :return: Byte
    """
    return (x & z) | (y & (~z))


def H(x, y, z):
    """H(x, y, z) = x ^ y ^ z
    :param x: Byte 
    :param y: Byte 
    :param z: Byte 
    :return: Byte
    """
    return x ^ y ^ z


def I(x, y, z):
    """I(x, y, z) = y ^ (x | (~z))
    :param x: Byte 
    :param y: Byte 
    :param z: Byte 
    :return: Byte
    """
    return y ^ (x | (~z))


def FF(a, b, c, d, x, s, ac):
    """
    :param a: Byte 
    :param b: Byte 
    :param c: Byte 
    :param d: Byte 
    :param x: Byte 
    :param s: Byte 
    :param ac: Int
    :return: Byte
    """
    a += (F(b, c, d) & 0xffffffff) + x + ac
    a = ((a & 0xffffffff) << s | (a & 0xffffffff) >> (32 - s))
    a += b
    return a & 0xffffffff


def GG(a, b, c, d, x, s, ac):
    """
    :param a: Byte 
    :param b: Byte 
    :param c: Byte 
    :param d: Byte 
    :param x: Byte 
    :param s: Byte 
    :param ac: Int
    :return: Byte
    """
    a += (G(b, c, d) & 0xffffffff) + x + ac
    a = ((a & 0xffffffff) << s | (a & 0xffffffff) >> (32 - s))
    a += b
    return a & 0xffffffff


def HH(a, b, c, d, x, s, ac):
    """
    :param a: Byte 
    :param b: Byte 
    :param c: Byte 
    :param d: Byte 
    :param x: Byte 
    :param s: Byte 
    :param ac: Int
    :return: Byte
    """
    a += (H(b, c, d) & 0xffffffff) + x + ac
    a = ((a & 0xffffffff) << s | (a & 0xffffffff) >> (32 - s))
    a += b
    return a & 0xffffffff


def II(a, b, c, d, x, s, ac):
    """
    :param a: Byte 
    :param b: Byte 
    :param c: Byte 
    :param d: Byte 
    :param x: Byte 
    :param s: Byte 
    :param ac: Int
    :return: Byte
    """
    a += (I(b, c, d) & 0xffffffff) + x + ac
    a = ((a & 0xffffffff) << s | (a & 0xffffffff) >> (32 - s))
    a += b
    return a & 0xffffffff


def trans(groups):
    """
    :param groups: Byte[]
    :return:
    """
    a, b, c, d = result
    # Round 1
    a = FF(a, b, c, d, groups[0], S[0][0], t[0])
    d = FF(d, a, b, c, groups[1], S[0][1], t[1])
    c = FF(c, d, a, b, groups[2], S[0][2], t[2])
    b = FF(b, c, d, a, groups[3], S[0][3], t[3])

    a = FF(a, b, c, d, groups[4], S[0][0], t[4])
    d = FF(d, a, b, c, groups[5], S[0][1], t[5])
    c = FF(c, d, a, b, groups[6], S[0][2], t[6])
    b = FF(b, c, d, a, groups[7], S[0][3], t[7])

    a = FF(a, b, c, d, groups[8], S[0][0], t[8])
    d = FF(d, a, b, c, groups[9], S[0][1], t[9])
    c = FF(c, d, a, b, groups[10], S[0][2], t[10])
    b = FF(b, c, d, a, groups[11], S[0][3], t[11])

    a = FF(a, b, c, d, groups[12], S[0][0], t[12])
    d = FF(d, a, b, c, groups[13], S[0][1], t[13])
    c = FF(c, d, a, b, groups[14], S[0][2], t[14])
    b = FF(b, c, d, a, groups[15], S[0][3], t[15])

    # Round 2
    a = GG(a, b, c, d, groups[1], S[1][0], t[16])
    d = GG(d, a, b, c, groups[6], S[1][1], t[17])
    c = GG(c, d, a, b, groups[11], S[1][2], t[18])
    b = GG(b, c, d, a, groups[0], S[1][3], t[19])

    a = GG(a, b, c, d, groups[5], S[1][0], t[20])
    d = GG(d, a, b, c, groups[10], S[1][1], t[21])
    c = GG(c, d, a, b, groups[15], S[1][2], t[22])
    b = GG(b, c, d, a, groups[4], S[1][3], t[23])

    a = GG(a, b, c, d, groups[9], S[1][0], t[24])
    d = GG(d, a, b, c, groups[14], S[1][1], t[25])
    c = GG(c, d, a, b, groups[3], S[1][2], t[26])
    b = GG(b, c, d, a, groups[8], S[1][3], t[27])

    a = GG(a, b, c, d, groups[13], S[1][0], t[28])
    d = GG(d, a, b, c, groups[2], S[1][1], t[29])
    c = GG(c, d, a, b, groups[7], S[1][2], t[30])
    b = GG(b, c, d, a, groups[12], S[1][3], t[31])

    # Round 3
    a = HH(a, b, c, d, groups[5], S[2][0], t[32])
    d = HH(d, a, b, c, groups[8], S[2][1], t[33])
    c = HH(c, d, a, b, groups[11], S[2][2], t[34])
    b = HH(b, c, d, a, groups[14], S[2][3], t[35])

    a = HH(a, b, c, d, groups[1], S[2][0], t[36])
    d = HH(d, a, b, c, groups[4], S[2][1], t[37])
    c = HH(c, d, a, b, groups[7], S[2][2], t[38])
    b = HH(b, c, d, a, groups[10], S[2][3], t[39])

    a = HH(a, b, c, d, groups[13], S[2][0], t[40])
    d = HH(d, a, b, c, groups[0], S[2][1], t[41])
    c = HH(c, d, a, b, groups[3], S[2][2], t[42])
    b = HH(b, c, d, a, groups[6], S[2][3], t[43])

    a = HH(a, b, c, d, groups[9], S[2][0], t[44])
    d = HH(d, a, b, c, groups[12], S[2][1], t[45])
    c = HH(c, d, a, b, groups[15], S[2][2], t[46])
    b = HH(b, c, d, a, groups[2], S[2][3], t[47])

    # Round 4
    a = II(a, b, c, d, groups[0], S[3][0], t[48])
    d = II(d, a, b, c, groups[7], S[3][1], t[49])
    c = II(c, d, a, b, groups[14], S[3][2], t[50])
    b = II(b, c, d, a, groups[5], S[3][3], t[51])

    a = II(a, b, c, d, groups[12], S[3][0], t[52])
    d = II(d, a, b, c, groups[3], S[3][1], t[53])
    c = II(c, d, a, b, groups[10], S[3][2], t[54])
    b = II(b, c, d, a, groups[1], S[3][3], t[55])

    a = II(a, b, c, d, groups[8], S[3][0], t[56])
    d = II(d, a, b, c, groups[15], S[3][1], t[57])
    c = II(c, d, a, b, groups[6], S[3][2], t[58])
    b = II(b, c, d, a, groups[13], S[3][3], t[59])

    a = II(a, b, c, d, groups[4], S[3][0], t[60])
    d = II(d, a, b, c, groups[11], S[3][1], t[61])
    c = II(c, d, a, b, groups[2], S[3][2], t[62])
    b = II(b, c, d, a, groups[9], S[3][3], t[63])

    result[0] += a
    result[1] += b
    result[2] += c
    result[3] += d
    result[0] &= 0xffffffff
    result[1] &= 0xffffffff
    result[2] &= 0xffffffff
    result[3] &= 0xffffffff


def generate_md5(input_text, input_type='string'):
    """Generate MD5
    :param input_text: String
    :param input_type: ('string', 'file')
    :return: MD4 Hex
    """
    global result
    result = [A, B, C, D]  # Initialize result
    input_bytes = ''

    if input_type == 'string':  # If input is string or text
        input_bytes = input_text.encode()  # Transform String to bytes
    elif input_type == 'file':  # If input is file
        file = open(input_text, 'rb')   # Read bytes
        input_bytes = file.read()
        file.close()

    byte_len = len(input_bytes)  # Get length
    group_count = byte_len // 64  # Get number of groups, each group 512bits(64 bytes)

    for i in range(group_count):
        groups = div_group(input_bytes, i * 64)
        trans(groups)  # Handle each group

    rest = byte_len % 64  # Get the rest message
    tmp_bytes = list(range(64))
    if rest <= 56:  # If rest <= 448bits(56 bytes)
        for i in range(rest):
            tmp_bytes[i] = input_bytes[byte_len - rest + i]  # Copy the rest bits
        if rest < 56:  # If rest < 56
            tmp_bytes[rest] = 1 << 7  # Append 10000000
            for i in range(1, 56 - rest):  # The rest append zero
                tmp_bytes[rest + i] = 0

        # Append the length of message
        tmp_len = byte_len << 3
        for i in range(8):
            tmp_bytes[56 + i] = tmp_len & 0xff
            tmp_len >>= 8

        # Handle the rest
        groups = div_group(tmp_bytes, 0)
        trans(groups)
    else:
        # If rest > 448bits(56 bytes)
        for i in range(rest):
            tmp_bytes[i] = input_bytes[byte_len - rest + i]  # Copy the rest bits
        tmp_bytes[rest] = 1 << 7  # Append 10000000
        for i in range(rest + 1, 64):  # The rest append zero
            tmp_bytes[i] = 0
        # Handle the first rest
        groups = div_group(tmp_bytes, 0)
        trans(groups)

        for i in range(56):  # Continue appending zero
            tmp_bytes[i] = 0

        # Append the length of message
        tmp_len = byte_len << 3
        for i in range(8):
            tmp_bytes[56 + i] = tmp_len & 0xff
            tmp_len >>= 8

        # Handle the rest
        groups = div_group(tmp_bytes, 0)
        trans(groups)

    return get_hash_hex_string()


def get_hash_hex_string():
    """Convert Hash value to Hex String
    :return: Hex String
    """
    result_string = ''
    for i in range(4):
        # For each 32bits group, get 8 hex characters
        for _ in range(4):
            tmp = result[i] & 0x0f  # Get the last 4bits
            str = convert_to_hex[tmp]  # Convert to hex
            result[i] >>= 4  # Get the next last 4bits
            tmp = result[i] & 0x0f  # Convert to hex
            result_string += convert_to_hex[tmp] + str  # Append to result_string
            result[i] >>= 4  # Get the next last bits

    return result_string


def div_group(input_bytes, index):
    """
    :param input_bytes: Byte[]
    :param index: Int
    :return: Byte[]
    """
    # Divide each 512bits(64 bytes) group to 16 smaller groups
    # Each smaller groups has 32bits(4 bytes)
    tmp = list(range(16))
    for i in range(16):
        tmp[i] = (eliminate_negative(input_bytes[4 * i + index]) |
                  (eliminate_negative(input_bytes[4 * i + index + 1])) << 8 |
                  (eliminate_negative(input_bytes[4 * i + index + 2])) << 16 |
                  (eliminate_negative(input_bytes[4 * i + index + 3])) << 24)
    return tmp


def eliminate_negative(b):
    """Eliminate the negative symbol
    :param b: Byte
    :return: Byte
    """
    if b < 0:
        return b & 0x7F + 128
    else:
        return b


if __name__ == '__main__':
    # d41d8cd98f00b204e9800998ecf8427e
    print('md5(\'\') =', generate_md5(''))
    # 0cc175b9c0f1b6a831c399e269772661
    print('md5(\'a\') =', generate_md5('a'))
    # 900150983cd24fb0d6963f7d28e17f72
    print('md5(\'abc\') =', generate_md5('abc'))
    # f96b697d7cb7938d525a2f31aaf161d0
    print('md5(\'message digest\') =', generate_md5('message digest'))
    # c3fcd3d76192e4007dfb496cca67e13b
    print('md5(\'abcdefghijklmnopqrstuvwxyz\') =', generate_md5('abcdefghijklmnopqrstuvwxyz'))
    # d174ab98d277d9f5a5611c2c9f419d9f
    print('md5(\'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789\') =',
          generate_md5('ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789'))
    # 57edf4a22be3c955ac49da2e2107b67a
    print('md5(\'12345678901234567890123456789012345678901234567890123456789012345678901234567890\') =',
          generate_md5('12345678901234567890123456789012345678901234567890123456789012345678901234567890'))
    # 28c73204143916e0a9492b492249d6dd
    print('md5(\'rsa.py\') =', generate_md5('rsa.py', 'file'))
    # 37b10ee05fb7f0a91915aa9ddf50173b
    print('md5(\'a.out\') =', generate_md5('a.out', 'file'))

Plus

文章评论