【网络安全】【密码学】【北京航空航天大学】实验七、流密码【Python实现】

实验七、流密码

实验目的

1、 了解常用的流密码算法，并对其进行实现；

2、 了解常用的伪随机数生成算法，并对其进行实现；

原理简介

流密码（Stream Cipher）也称为序列密码，它是对称密码算法的一种。流密码具有实现简单、便于硬件实施、加解密处理速度快、没有或只有有限的错误传播等特点，因此在实际应用中，特别是专用或机密机构中保持着优势，典型的应用领域包括无线通信、外交通信等。

实验步骤

一、编程实现BBS伪随机数生成算法

1、算法原理

BBS(Blum Blum Shub)算法是最简单有效的伪随机数算法，算法具体步骤如下：
（1）首先选择两个大素数p和q，满足p≡q≡3(mod 4)；
（2）选择另外一个与n互素的随机整数s；
（3）计算种子x0 = s^2 mod n;
（4）计算位序列，第i个伪随机位是xi的最低位，这里xi = xi-1^2 mod n.
BBS伪随机数发生器也被称为密码安全伪随机发生器（CSPRBG）,能经受住续位测试。

2、算法流程

Python实现：

PrimeTest.py内容：

import random


def MillerRabin(n):
    k = 0
    q = n - 1
    while q & 1 == 0:
        q >>= 1
        k += 1
    a = random.randint(2, n - 1)
    if pow(a, q, n) == 1:
        return True
    for i in range(k):
        if pow(a, pow(2, i) * q, n) == n - 1:
            return True
    return False


def PrimeTest(p, n):
    for i in range(n):
        if not MillerRabin(p):
            return False
    return True


# 测试代码
n = int(eval(input()))
result = PrimeTest(n, 100)
print(result)

BBS.py内容：

from PrimeTest import *


def getBigPrime():  # 生成介于0和pow(2,n)-1之间的随机大质数，且保证其模4余3
    n = random.randint(0, 3) + 8  # n是下面p的比特位数
    while True:
        p = random.randint(0, (pow(2, n) - 1))
        p = 4 * p + 3
        if PrimeTest(p, 1):
            break
    return p


def BBS(num):  # num是想得到的rbs串的比特位数
    rbs = ''
    p = getBigPrime()
    q = getBigPrime()
    while p == q:
        q = getBigPrime()
    print('p = ', p)
    print('q = ', q)
    n = p * q
    s_num = random.randint(0, 3) + 8  # 随机数s的比特位数
    s = random.randint(0, (pow(2, s_num) - 1))
    x = pow(s, 2, n)
    for i in range(num):
        x = pow(x, 2, n)
        rbs = rbs + str(x & 1)  # 取x的二进制最低位
    return rbs


print(getBigPrime())
print(BBS(10))

3、测试样例及运行截图：

使用随机大素数p和q生成长度为10bits的随机序列如下：

使用随机大素数p和q生成长度为20bits的随机序列如下：

使用随机大素数p和q生成长度为100bits的随机序列如下：

4、总结：

（1）、注意p和q的限制条件，即p≡q≡3(mod 4)；
（2）、每个循环取的是最低有效位；
（3）、BBS被称为密码安全伪随机位发生器（CSPRBG）.它能经受住续位测试；
（4）、BBS的安全性是基于对n的因子分解的困难性上的，即给定n，我们不能确定它的素因子p和q。

二、编程实现RC4流密码算法

1、算法原理

RC4算法是一种流密码算法，其密钥长度可变，且面向字节操作。算法使用的主要变量：
密钥流Ks、状态数组S、临时数组T、密钥K。RC4算法的流程如下：
（1）、用0~255初始化S，用密钥K初始化T。
（2）、用T产生S的初始置换。
（3）、用S产生密钥流。

2、算法流程

Python实现：

s = bytearray()
t = bytearray()


def initKSA(sourcekey):
    global s, t
    sourcekey = bytearray.fromhex(sourcekey)
    keylen = len(sourcekey)
    for i in range(256):
        s = bytearray(s) + bytearray([i])
        t = bytearray(t) + bytearray(sourcekey[i % keylen])
    # initiate S and T finished.
    # INITIAL PERMUTATION
    j = 0
    for i in range(256):
        j = (j + s[i] + t[i]) % 256
        temp = s[i]
        s[i] = s[j]
        s[j] = temp


def generateKey(len):
    global s, t
    KeyStream = bytearray()
    i = 0
    j = 0
    for _ in range(len):
        i = (i + 1) % 256
        j = (j + s[i]) % 256
        temp = s[i]
        s[i] = s[j]
        s[j] = temp
        t = (s[i] + s[j]) % 256
        KeyStream = KeyStream + bytearray([s[t]])
    return KeyStream


if __name__ == '__main__':
    initKSA('8c711bb563c668f6d61f758b8dc8cc76a682ece88034f77a90f8f5d8')
    m = bytearray.fromhex('d02a80213b7c368822a519761bfd32d6ecc22a')
    Keystream = generateKey(len(m))
    c = bytearray()
    for i in range(len(m)):
        c = c + bytearray([Keystream[i] ^ m[i]])
    print(c.hex())

    initKSA('680fec38f5681bc86b4fd5a182350a9b853d0086b35130')
    m = bytearray.fromhex('e3be2b4829402d5711a16a74ca12fa4877464a5fbcf309cc45452cc24eabbbcbfc994374d3f452ffcde9ed50bac72d30fa207e2e25')
    Keystream = generateKey(len(m))
    c = bytearray()
    for i in range(len(m)):
        c = c + bytearray([Keystream[i] ^ m[i]])
    print(c.hex())

    initKSA('37e12365d9cab785db06289caadcdededc9896df46eb536b04c9588f755a008d3c09')
    m = bytearray.fromhex('b26ec1178bd763e8aea49f2882496d1d4b05d1ea3e4eefd2346288deb4b0314b7d')
    Keystream = generateKey(len(m))
    c = bytearray()
    for i in range(len(m)):
        c = c + bytearray([Keystream[i] ^ m[i]])
    print(c.hex())

3、测试样例及截图

测试点1：
密钥：8c711bb563c668f6d61f758b8dc8cc76a682ece88034f77a90f8f5d8
明文：d02a80213b7c368822a519761bfd32d6ecc22a
密文：0e320960984b6bb2a8a307114c93a0bb2bd855

测试点2：
密钥：680fec38f5681bc86b4fd5a182350a9b853d0086b35130
明文：
e3be2b4829402d5711a16a74ca12fa4877464a5fbcf309cc45452cc24eabbbcbfc994374d3f452ffcde9ed50bac72d30fa207e2e25
密文：
ed48abeebb23771ec85def2dcf0ecea3c2093f79b1ec73a553e57612389acc2a0ca022e2492620b18a18416330e888c5154c7a635b

测试点3：
密钥：37e12365d9cab785db06289caadcdededc9896df46eb536b04c9588f755a008d3c09
明文：26ec1178bd763e8aea49f2882496d1bd4b05d1ea3e4eefd2346288deb4b0314b7d
密文：cee74b4936104636da3e8852253c48a68f9113268787d534bd4d1659d8cb0a52fb

运行截图：

4、总结
（1）、RC4算法不对明文进行分组处理，而是以字节流的方式依次加密明文中的每个字节，解密时再依次对密文中的字节进行解密。
（2）、RC4加、解密的步骤完全一样，输入明文得到密文，输入密文得到明文。
（3）、在设计流密码时，应注意：
1、密文的周期要长；
2、密钥流应该尽可能地接近真正随机字节流地特征；
3、为了防御穷举攻击，密钥应该足够长，目前最短应该为128位（16字节）。

思考题

思考RC4算法中什么样的密钥属于弱密钥。
答：考虑j = (j + S[i] + T[i]) mod 256，取(j + T[i]) ≡ 0 (mod 256)，即T[i] = [0,0,255,254,…,2]。在这样地情况下，S的初始化存在无效置换问题，S完全不会被置换。攻击者可通过统计分析破解密文。RC4的弱密钥K包括：