0%

密码学课程设计之综合实验

发表于 更新于 分类于
本文字数： 4.7k 阅读时长 ≈ 4 分钟

Alice想要通过公共信道给Bob传输一份秘密文件（文件很大），又知道，很多人和机构想得到这份文件。如果你是Alice，你应该怎么做？请设计一个方案，并编程实现。

思路

审题：
首先注意到秘密文件很大，这时候就需要比较各种加密算法的效率。

1

我只写了DES和RC4，所以就是比较DES和RC4的运算速度，看表可以看出，RC4的速度比DES快10倍，那就选RC4对秘密文件进行加密。

RC4属于对称密码，对称密码的密钥分发是需要通过安全信道，题目说“很多人和机构都想得到这份文件”，说明，这个信道肯定是不安全的，所以我们需要对分发的密钥进行加密传输，这个时候使用公钥密码体制对密钥进行加密。

公钥密码体制选择RSA

流程

大致流程就是

1
2
3
4
5
6
7
Alice随机生成两个大素数p和q，计算出RSA的公钥{e,n}，私钥{d,n}
Alice将公钥{e,n}发送给Bob
Bob选择一个符合安全性要求的RC4密钥k，并使用RSA的公钥对k加密生成密文c2,传给Alice
Alice使用私钥{d,n}对c2进行解密，得到RC4密钥k
Alice使用k对秘密文件进行RC4加密，生成密文c1
Alice通过不安全信道，将密文c1传输给Bob
Bob拿到密文c1后，密钥k对密文c1进行解密，从而完成安全传输

生成密钥

先用RSA随机生成两个大素数p和q。

1
2
p=create_prime()
q=create_prime()

计算公钥{e,n}，私钥{d,n}。

1
2
3
4
n=p*q
fn=(p-1)*(q-1)
e=E(fn)
d=D(e,fn)

Bob选取RC4密钥k进行RSA加密

1
2
3
k = "LGDISTHEBEST"
c2=RSA_encrypt(e,n,int(str2bin(k),2))
c2=str(c2)

Alice解密密钥k

1
2
3
4
k2=RSA_decrypt(d,n,int(k1))
k2=str(k2)
m=bin(int(k2, 10)).replace("0b", "0")
q=bin2str(m)

Alice使用k对文件进行RC4加密

1
f4.write(RC4Encrypt(c1,q))

Bob使用k对文件解密

1
f6.write(RC4Decrypt(message,k))

注意事项

这个程序改了好久，对RC4密钥k加密解密那里卡了好久！

一开始，我想到是字符串k转成二进制，然后直接用RSA加解密，但是一想不对呀，这想法也太离谱了，一个二进制字符串也太大了！突然就想到可以先将二进制再转换成十进制，然后用RSA加密，传输的是加密得到的十进制数，解密的时候解出来是十进制，再转成二进制，最后转成字符串,就得到最初约定好的RC4密钥k！！！

也就是说
$$
字符串K{\Longrightarrow}二进制K{\Longrightarrow}十进制K{\Longrightarrow}RSA加密
$$

$$
RSA解密{\Longrightarrow}十进制K{\Longrightarrow}二进制K{\Longrightarrow}字符串K
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#字符串转化为二进制
def str2bin(message):
    x = ""
    for i in message:
        tmp = bin(ord(i))[2:]
        for j in range(0,8-len(tmp)):
            tmp = '0'+ tmp 
        x += tmp
    return x

#二进制转化为字符串
def bin2str(s):
    res = ''
    for i in range(0, len(s),8):
        x = s[i:i+8]
        x = int(x,2)
        res += chr(x)
    return res

最后这个综合实验终于改完了！！！

完整代码

RC4.py

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
#-*- coding:utf-8 -*-
import base64
def RC4(text,key):
    ## 将0到255的互不重复的元素装入S盒。
    lk = len(key)
    S = [0] * 256#S数组S
    T=''#临时向量T
    for i in range(256) :
        S[i] = i#S赋初值
        T += key[i%lk]#T赋初值，填充满T
    ## 根据密钥打乱S盒
    j = 0
    for i in range(256):
        j = (j+S[i]+ord(T[i]))%256
        S[i],S[j] = S[j],S[i]
    ## 生成伪随机数，构造密文
    i = j = 0
    ans = ""
    for x in text:
        i = (i+1)%256
        j = (j+S[i])%256
        S[i],S[j] = S[j],S[i]
        t = (S[i]+S[j])%256
        k = S[t]
        #加密时，将k与明文异或；解密时，k与密文异或
        ans += chr(ord(x)^k)
    return ans
# RC4加密: 明文转成base64编码的密文
def RC4Encrypt(message,key):
    return base64.b64encode(RC4(message,key))
# RC4解密: base64编码的密文转成明文
def RC4Decrypt(cipher,key):
    return RC4(base64.b64decode(cipher),key)

RSA.py

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
#-*- coding:utf-8 -*-
import random
import math

#Miller-Rabin测试：不断选取不超过n-1的基b(s次)，
#计算是否每次都有bn-1 ≡ 1(mod n)，若每次都成立则n是素数，否则为合数。
#Miller_Rabin算法
def miller_rabin(a,n):
    temp=n-1
    j=0
    while temp&1==0:
        temp=temp>>1
        j+=1
    x=fast_mod(a,temp,n)
    if x==1 or x==n-1:
        return True
    while j:
        x=fast_mod(x,2,n)
        if x==n-1:
            return True
        j-=1
    return False

  #判断是否为素数
def is_prime(n):
    times=100
    if n==2:
        return True
    if n<2 or n%2==0:
        return False
    i=1
    while i<=times:
        a=random.randint(1,n-2)+1
        if miller_rabin(a,n)==False:
            return False
        i+=1
    return True


#模重复平方计算法
def fast_mod(b,n,m):
    a=1
    while n!=0:
        temp=n&1
        n=n>>1
        if temp==1:
            a=(a*b)%m
        b=(b*b)%m
    return a

#生成素数
def create_prime():
    while True:
        #p=random.randrange(1<<64,1<<128,3)
        p=random.randrange(1<<512,1<<1024,3)
        if(is_prime(p)):
            return p

#生成公钥，随机得到小素数，（e，Φ（n）)=1
def E(fn):
    while True:
        e=random.randint(1<<16,fn)
        temp=e
        t=fn
        d=1
        while d!=0:
           d=t%temp
           t=temp
           temp=d
        if t==1:
            return e

#计算私钥,e求逆，欧几里得扩展算法
def D(e,fn):
    r1,r2=e,fn
    s1,s2=1,0
    t1,t2=0,1
    while(r2 > 0):
        q=r1//r2
        r= r1-q*r2
        r1=r2
        r2=r
        s=s1-q*s2
        s1=s2
        s2=s
        t=t1-q*t2
        t1=t2
        t2=t
    return s1%fn

#RSA加密
def RSA_encrypt(e,n,plaintext):
    return fast_mod(plaintext,e,n)

#RSA解密
def RSA_decrypt(d,n,ciphertext):
    return fast_mod(ciphertext,d,n)

存在的问题

缺少身份认证机制

1

因为可能存在中间人 Eve ，Bob 首先要验证通信对方是不是 Alice，所以需要再写一个数字签名（保证消息的完整性、不可抵赖性）

基于RSA和MD5的数字签名

签名算法

对应RSA密码体制中的解密过程

设待签名的消息为m，则签名者A先利用一个安全的Hash函数 h 来产生一个消息摘要 h(m)，然后签名者用自己的私钥计算签名 s ≡ h(m)d mod n ，将 (s,m) 发送给消息接收者 B。 

1
2
3
4
5
def Sign(m,d,n):
    H = MD5(m)
    H = str2Num(H)
    s = RSA_decrypt(d,n,H)
    return s

验证算法

对应RSA密码体制中的加密过程

签名接收者B收到消息m和签名s后，先利用A使用的Hash函数h来产生一个消息摘要h(m)，然后检验同余式 h(m) ≡ se mod n是否成立。若成立，则说明签名有效，否则签名无效。 

1
2
3
4
5
6
def Ver(m,s,n,e):
    H = MD5(m)
    H = str2Num(H)
    H= fast_mod(H,1,n)##H要对n取模！！！
    H1 = RSA_encrypt(e,n,s)
    return H == H1

注意点

验证算法中，求出消息Hash值以后，进行验证的时候要对n取模！！！

完整代码

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
#-*- coding:utf-8 -*-
from MD5 import *
from RSA import *

# str to num
def str2Num(s):
    x = ""
    for i in s:
        tmp = bin(ord(i))[2:]
        for j in range(0,8-len(tmp)):
            tmp = '0'+ tmp 
        x += tmp
    x = int(x,2)
    return x

# num to str
def num2Str(n):
    ans = '{:x}'.format(n).decode('hex')
    return ans

# Signature
def Sign(m,d,n):
    H = MD5(m)
    H = str2Num(H)
    s = RSA_decrypt(d,n,H)
    return s

# Verification
def Ver(m,s,n,e):
    H = MD5(m)
    H = str2Num(H)
    H= fast_mod(H,1,n)##H要对n取模！！！
    H1 = RSA_encrypt(e,n,s)
    return H == H1

if __name__ == "__main__":
    m="ame"
    p=create_prime()
    q=create_prime()
    n=p*q
    fn=(p-1)*(q-1)
    e=E(fn)
    d=D(e,fn)
    s = Sign(m,d,n)
    v = Ver(m,s,n,e)
    if v:
        print "签名正确！".decode('utf-8').encode('gbk')
    else:
        print "验证失败".decode('utf-8').encode('gbk')