基于公钥体制的加密和数字签名实现

实验二基于公钥体制的加密和数字签名实现

实验内容

实现一个基于公钥算法的数字签名系统。以 RSA 为例，具体要求如下：

能够对指定字符串（或其消息摘要）进行签名形成签名文，对签名文进行解密并与源字符串进行比对，验证其正确性；
必须输出签名有关的各项参数：如公钥、私钥，通过乘积构成大整数的两个素数等；
实现一个较完善的系统。

实验目的

目前，一般通过加密与解密、身份确认、数字签名等方法来保证信息存储与传输的安全。本实验的目的是使学生能够深入掌握公钥加解密算法、数字签名的基本原理，从而对密码学的公钥密码体制加解密、数字签名与身份认证、密钥管理等相关知识的系统应用有深入的理解。

实验原理

1976 年，美国学者 Diffie 和 Hellman 为解决信息公开传送和密钥管理问题，提出一种新的密钥交换协议，允许在不安全的媒体上的通讯双方交换信息，安全地达成一致的密钥，这就是“公开密钥系统”。相对于“对称加密算法”，这种方法也叫做“非对称加密算法”。与对称加密算法不同，非对称加密算法需要两个密钥：公开密钥(publickey)和私有密钥 (privatekey)。公开密钥与私有密钥是一对，如果用公开密钥对数据进行加密，只有用对应的私有密钥才能解密；如果用私有密钥对数据进行加密，那么只有用对应的公开密钥才能解密。因为加密和解密使用的是两个不同的密钥，所以这种算法叫作非对称加密算法。非对称加密算法实现机密信息交换的基本过程是：甲方生成一对密钥并将其中的一把作为公用密钥向其它方公开；得到该公用密钥的乙方使用该密钥对机密信息进行加密后发送给甲方；甲方再用自己保存的另一把专用密钥对加密后的信息进行解密。甲方只能用其专用密钥解密由其公用密钥加密后的任何信息。非对称加密算法的保密性比较好，它消除了最终用户交换密钥的需要，但加密和解密花费时间长、速度慢，不适合于对文件加密而只适用于对少量数据进行加密。

公钥密码算法介绍

使用公开密钥对文件进行加密传输的实际过程包括四步:

发送方生成一个自己的私有密钥并用接收方的公开密钥对自己的私有密钥进行加密，然后通过网络传输到接收方；
发送方对需要传输的文件用自己的私有密钥进行加密，然后通过网络把加密后的文件传输到接收方；
接收方用自己的公开密钥进行解密后得到发送方的私有密钥；
接受方用发送方的私有密钥对文件进行解密得到文件的明文形式。

因为只有接收方才拥有自己的公开密钥，所以即使其他人得到了经过加密的发送方的私有密钥，也因为无法进行解密而保证了私有密钥的安全性，从而也保证了传输文件的安全性。实际上，上述在文件传输过程中实现了两个加密解密过程：文件本身的加密和解密与私有密钥的加密解密，这分别通过私有密钥和公开密钥来实现。

私钥数字签名技术

对文件进行加密只解决了传送信息的保密问题，而防止他人对传输的文件进行破坏，以及如何确定发信人的身份还需要采取其它的手段，这一手段就是数字签名。在电子商务安全保密系统中，数字签名技术有着特别重要的地位，在电子商务安全服务中的源鉴别、完整性服务、不可否认服务中，都要用到数字签名技术。在电子商务中，完善的数字签名应具备签字方不能抵赖、他人不能伪造、在公证人面前能够验证真伪的能力。

实现数字签名有很多方法，目前数字签名采用较多的是公钥加密技术，如基于 RSA Date Security 公司的 PKCS(Public Key Cryptography Standards)、Digital Signature Algorithm、 x.509、PGP(Pretty Good Privacy)。1994 年美国标准与技术协会公布了数字签名标准而使公钥加密技术广泛应用。公钥加密系统采用的是非对称加密算法。

目前的数字签名是建立在公共密钥体制基础上，它是公用密钥加密技术的另一类应用。它的主要方式是，报文的发送方从报文文本中生成一个 128 位的散列值(或报文摘要)。发送方用自己的私人密钥对这个散列值进行加密来形成发送方的数字签名。然后，这个数字签名将作为报文的附件和报文一起发送给报文的接收方。报文的接收方首先从接收到的原始报文中计算出 128 位的散列值(或报文摘要)，接着再用发送方的公用密钥来对报文附加的数字签名进行解密。如果两个散列值相同，那么接收方就能确认该数字签名是发送方的。通过数字签名能够实现对原始报文的鉴别。

数字签名与书面文件签名有相同之处。采用数字签名，也能确认以下两点：第一，信息是由签名者发送的；第二，信息自签发后到收到为止未曾作过任何修改。这样数字签名就可用来防止电子信息因易被修改而有人作伪，或冒用别人名义发送信息，或发出(收到) 信件后又加以否认等情况发生。应用广泛的数字签名方法主要有三种，即：RSA 签名、DSS 签名和 Hash 签名。这三种算法可单独使用，也可综合在一起使用。数字签名是通过密码算法对数据进行加、解密变换实现的，用 DES 算法、RSA 算法都可实现数字签名。但三种技术或多或少都有缺陷，或者没有成熟的标准。

RSA 算法中数字签名技术实际上是通过一个哈希函数来实现的。数字签名的特点是它代表了文件的特征，文件如果发生改变，数字签名的值也将发生变化。不同的文件将得到不同的数字签名。一个最简单的哈希函数是把文件的二进制码相累加，取最后的若干位。哈希函数对发送数据的双方都是公开的。

DSS 数字签名是由美国国家标准化研究院和国家安全局共同开发的。由于它是由美国政府颁布实施的，主要用于与美国政府做生意的公司，其他公司则较少使用，它只是一个签名系统，而且美国政府不提倡使用任何削弱政府窃听能力的加密软件，认为这才符合美国的国家利益。

Hash 签名是最主要的数字签名方法，也称之为数字摘要法(Digital Digest)或数字指纹法(Digital Finger Print)。它与 RSA 数字签名是单独的签名不同，该数字签名方法是将数字签名与要发送的信息紧密联系在一起，它更适合于电子商务活动。将一个商务合同的个体内容与签名结合在一起，比合同和签名分开传递，更增加了可信度和安全性。数字摘要(Digital Digest)加密方法亦称安全 Hash 编码法(SHA:Secure Hash Algorithm)或 MD5(MD Standard For Message Digest)，由 RonRivest 所设计。该编码法采用单向 Hash 函数将需加密的明文“摘要”成一串 128bit 的密文，这一串密文亦称为数字指纹(Finger Print)，它有固定的长度，且不同的明文摘要必定一致。这样这串摘要可成为验证明文是否是“真身”的“指纹”。

只有加入数字签名及验证才能真正实现在公开网络上的安全传输。加入数字签名和验证的文件传输过程如下：

发送方首先用哈希函数从原文得到数字签名，然后采用公开密钥体系用发送方的私有密钥对数字签名进行加密，并把加密后的数字签名附加在要发送的原文后面；
发送方选择一个秘密密钥对文件进行加密，并把加密后的文件通过网络传输到接收方；
发送方用接收方的公开密钥对密秘密钥进行加密，并通过网络把加密后的秘密密钥传输到接收方；
接受方使用自己的私有密钥对密钥信息进行解密，得到秘密密钥的明文；
接收方用秘密密钥对文件进行解密，得到经过加密的数字签名；
接收方用发送方的公开密钥对数字签名进行解密，得到数字签名的明文；
接收方用得到的原文明文和哈希函数重新计算数字签名，并与解密后的数字签名进行对比。如果两个数字签名是相同的，说明文件在传输过程中没有被破坏。

设计分析

RSA 签名程序涉及很多个数学运算步骤，程序可以分成若干个模块。

模加运算、模乘运算和模幂运算模块
1. 模加运算 $(a+b)\mod n$ 等价于 $(a\mod n +b\mod n)\mod n$
2. 模乘运算及计算两个数的乘积然后取模。为了避免大数相乘造成的溢出，根据求模运算的性质，优化算法，其中 $ab\mod n$ 等价于 $(a\mod n)(b\mod n)\mod n$
3. 模幂运算就是计算一个数的 n 次幂，然后进行取模运算。这里编程可以使用一些数学技巧，另外同样要考虑避免大数相乘造成溢出的问题。(可参考教材P121)
素性测试算法:Solovay-Strassen素性测试算法、Miller-Rabin素性测试算法或其他检测方法
大数的加法与减法运算
求最大公约数可利用欧几里德的辗转相除法
随机数的产生(可参照教材 7 .2 节)
计算私钥
密钥的管理(可参照教材第7章)
签名消息摘要的生成(可利用MD5、SHA-1算法或其他算法，参考教材第8章)
签名与验证过程

实验步骤

import random
import hashlib

def rabin_miller(num):
    s = num - 1
    t = 0
    while s % 2 == 0:
        s = s // 2
        t += 1
    for trials in range(5):
        a = random.randrange(2, num - 1)
        v = pow(a, s, num)
        if v != 1:
            i = 0
            while v != (num - 1):
                if i == t - 1:
                    return False
                else:
                    i = i + 1
                    v = (v ** 2) % num
    return True

def is_prime(num):
    # 排除0,1和负数
    if num < 2:
        return False
    # 创建小素数的列表,可以大幅加快速度
    small_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]
    # 如果是小素数,那么直接返回true
    if num in small_primes:
        return True
    # 如果大数是这些小素数的倍数,那么就是合数,返回false
    for prime in small_primes:
        if num % prime == 0:
            return False
    # 如果这样没有分辨出来,就一定是大整数,那么就调用rabin算法
    return rabin_miller(num)

# 得到随机大素数,默认位数为1024
def get_prime(key_size):
    while True:
        num = random.randrange(2**(key_size-1), 2**key_size)
        if is_prime(num):
            return num

# 欧几里得算法求两个数字的最大公约数
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)
# 扩展欧几里得
def ext_gcd(a, b):
    if b == 0:
        x1 = 1
        y1 = 0
        x = x1
        y = y1
        r = a
        return r, x, y
    else:
        r, x1, y1 = ext_gcd(b, a % b)
        x = y1
        y = x1 - (a // b ) * y1
        return r, x, y        
# 使用快速幂取模计算法进行加密解密
def power(a, b, c):
    s = 1
    a %= c
    while b != 0:
        if b % 2 == 1:
            s = (s * a) % c
        b = b // 2
        a = (a * a) % c
    return s
# 生成RSA公钥私钥
def gen_key(p, q):
    n = p * q
    fn = (p - 1) * (q - 1) # 欧拉函数
    b = fn
    e = get_prime(16)
    j = gcd(e,b)
    while j != 1:
        e = get_prime(16)
        j = gcd(e,b)
    a = e
    b = fn
    r, x, y = ext_gcd(a, b)
    while x <=0: 
        x += fn #将负逆元转正
    d = x

    print("生成的公钥e为:\n", e)
    print("生成的私钥d为:\n", d)
    return (n, e), (n, d)
# 加密 m是被加密的信息 加密成为c
def encrypt(m, pubkey):
  n = pubkey[0]
  e = pubkey[1]
  c = power(m, e, n)
  return c
# 解密 c是密文，解密为明文m
def decrypt(c, selfkey):
  n = selfkey[0]
  d = selfkey[1]
  m = power(c, d, n)
  return m

def main():
    # RSA秘钥生成
    pubkey = []
    selfkey = []
    # 公钥私钥中用到的两个1024位大素数p,q
    p = get_prime(1024)
    q = get_prime(1024)
    print("随机取两个1024位的大素数分别为:")
    print("p:\n", p)
    print("q:\n", q)
    pubkey, selfkey = gen_key(p, q)

    # 数字签名
    print("请您输入要加密的明文:")
    mstr = input('')
    m = bytes(mstr, encoding = "utf8")
    md = hashlib.md5()
    md.update(m)
    # 用MD5算法生成消息摘要hm
    hm = int(md.hexdigest(), 16)
    print("Alice生成的消息摘要为:\n", hm)
    # 计算签名
    # Alice用自己的私钥计算签名s
    s = encrypt(hm, selfkey)
    print("Alice计算出的签名s为:\n", s)
    # Alice将(m, s)发送个Bob

    # Bob验证签名是否有效
    flag = True
    # Bob用公钥计算出消息摘要
    res = decrypt(s, pubkey)
    print("Bob计算出的消息摘要为:\n", res)
    if res == hm:
        flag =True
    else:
        flag = False
    # 将验证结果输出
    if flag == True:
        print("Alice的签名 有效")
    else:
        print("Alice的签名 无效")

if __name__ == "__main__":
    main()

随机取两个1024位的大素数分别为:
p:
 126840546322120293706358756821908489630070790079046472804746119073768334625490365235083022536479566981823190933258178790509366579533832001267306165107863085881113761435350873546230365271035747675885320413506208387435237682844409604996551723798124453562497393425348367844145601028559043967964302680971669417377
q:
 110015871372188294328891465519179826099958495864993626451841666624000747692567617935532732521379526898233104333486259881137351638956572103832908054241130064173209828070415271883177555779056193787850518343659717024191559503731469891829587545767457582829392810068943226121265300923506971384737838641826181989599
生成的公钥e为:
 54577
生成的私钥d为:
 3281705918126775852692348898803114863540750647926630044204586914660706149456768281569130750667346570555934119342673867092098064435249876860547572956022377064444798811206959277759287586946639818291955407734521878630206331887209471238218063789272705556490071412119825560783998889227538682005647903885805057246879198124743114781119068432094351227696489713393373313433102696886587463273541350691093986481934401983300987621909796401685796870740690103302888975489490339535236596526002227721518911073270181461161399921797239518350782039246018477078364494201792334417597634696152185622777340387672322847655316392815975809553
请您输入要加密的明文:
in 55!W !
Alice生成的消息摘要为:
 207778089911345749567590398469007700519
Alice计算出的签名s为:
 12585735280468047095842933579143691342646624427994934537433451418153230312809211508585728071860779031205364878831339603978791995981921969862944737508430134213997245255632702656148806137341048229980087430200635237062508178960663278740046275554238836208862907502133506206749972830158437627039346045841002990565884315551692930428183962150017923662389847110983789961789305955882143474639303881910489273058955868066332712344789616974144364651369622467170638614242424478995954708716854902165675072789205161605561668310657919000641024952567270776112319505307371319697520961070355399235340852078916948151059417240082551980633
Bob计算出的消息摘要为:
 207778089911345749567590398469007700519
Alice的签名 有效

思考题

查阅资料，了解一些其他的公钥密码体制，如 ElGamal 公约密码体制、Diffie-Hellman密钥协商方案(基于求解离散对数的难解问题)、椭圆曲线密码体制(基于椭圆曲线离散对数的难解问题)等，认识它们的基本原理和实现机制。
查阅资料，进一步了解其他签名方案如 DSA 算法，分析这些签名方案的基本原理和实现机制等，以及它们与 RSA 的区别和联系。

实验总结

熟悉了RSA公钥密码体制并实现了数字签名的生成和验证。