Perl中的非对称加密

2001年9月26日，作者：Benjamin Trott 和 Vipul Ved Prakash

简介

对称加密允许Alice在网络中与Bob交换秘密消息，但这需要他们共享一个密钥。如果Alice和Bob不住在交通便利的地区，或者由于各种原因无法面对面交流，他们别无选择，只能通过网络共享密钥。然而，这却带来一个问题。网络不安全，Eve可以系统地嗅探Alice和Bob之间的流量，并获取他们通过网络共享的任何密钥，无需破解对称密码即可读取所有后续加密的通信。

在公共网络早期，Witfield Diffie 和 Martin Hellman，当时是斯坦福数学系的研究人员，正在与这一基本问题作斗争——如何使两个互不相识的人在不安全的网络上启动安全通信。他们的工作最终形成了一篇开创性的论文，题为“密码学的新方向”，为后来被称为非对称加密的基础奠定了基础。非对称加密不仅为上述启动问题提供了一种优雅的解决方案，同时解决了数字隐私的多个其他问题，包括不可伪造的签名和非否认。

在这篇文章中，我们将探讨非对称加密的各种方法以及提供这些方法现成实现的Perl模块。

陷门单向函数

非对称加密的核心是陷门单向函数的概念。单向函数在一个方向上容易计算，但在相反方向上几乎不可能计算。例如，打破鸡蛋就是一个单向函数。陷门单向函数与单向函数非常相似，只是在某些“陷门”信息可用时可以轻易逆转。

在一个非对称加密系统中，每个用户有两个密钥：一个公钥，其他人用它来加密发往该用户的消息，以及一个用于解密用公钥加密的消息的私钥。（因此，非对称加密也常被称为公钥加密。）用户小心翼翼地保护私钥，而其公钥则被随意分发到世界各地。与通常为一定长度的随机数的对称密钥不同，非对称密钥是具有特殊数学性质的数量，这些数量是通过密钥生成算法计算得出的。

要使用公钥加密向Bob发送私密消息，Alice首先获取他的公钥。由于Bob的公钥的知识并不能使Eve解密使用该公钥加密的消息，因此公钥交换可以在不安全的网络上进行。然后，Alice使用这个密钥加密她的消息。加密操作包括在消息上计算陷门单向函数（在容易的方向上），使用公钥生成密文。一旦生成，Alice将密文发送给Bob。

为了恢复明文，鲍勃和爱娃（从线路上嗅探到密文副本的人）必须反转陷阱门单射函数。鲍勃使用陷阱门信息和他的私钥来轻松解密和阅读信息。另一方面，没有陷阱门信息的爱娃面临的任务比拼一个破碎的鸡蛋更难。

RSA

当迪菲和赫尔曼提出了他们的非对称加密理论和陷阱门单射函数理论时，他们并没有建议特定的陷阱门单射函数。里维斯、沙米尔和阿德尔曼，当时是麻省理工学院的教授，是第一个设计出围绕素数乘积分解难度猜想设计的函数的人。他们的加密系统RSA经受了多年的密码分析，现在是使用最广泛的一种公钥加密系统。

以下是RSA的工作方式：要生成RSA密钥对，鲍勃选择两个大素数p和q（每个1024位/308位长）并计算它们的乘积，

    n = pq

然后，他选择一个小于e的随机数C，它比C_(p-1)(q-1)小且与C_(p-1)(q-1)互质，

    1 < e < (p-1)(q-1)
    gcd(e, ((p-1)(q-1)) = 1

最后，他使用扩展欧几里得算法计算，

    ed = 1 mod (p-1)(q-1)

(n,e)成为他的公钥，而d是密钥。

当Alice得到Bob的公钥后，她用这个公钥加密她的信息。为了这样做，她将信息转换为介于1和n之间的数字m，并计算

    c = (m ^ e) mod n

c是密文；Alice将其发送给Bob，Bob计算

    m = (c ^ d) mod n

从而恢复原始的m。他将m转换回文本形式并阅读信息。

一直在这段时间里嗅探Alice和Bob之间流量的爱娃，拥有Bob的公钥(n,e)和Alice的加密信息c。要解密c，她必须知道d的值。如果爱娃知道p和q，她就可以计算d并解密信息。但要发现p和q，她必须分解n，根据已知的分解算法和当前的计算技术水平，这被认为是难以处理的。

Crypt::RSA

如果你想知道Perl在这其中的作用，那么答案就在这里。通过CPAN上的扩展模块，Perl提供了几个非对称加密系统的有效、安全和DWIM实现。Crypt::RSA包提供了一个全面的RSA实现。

以下是Alice如何使用Crypt::RSA向Bob发送RSA加密信息

Bob生成2048位密钥对

    $rsa = new Crypt::RSA;
    ($public, $private) = $rsa->keygen( Size => 2048 )

他将公钥$public发送给Alice，可能通过电子邮件，Alice用此加密她的信息（存储在$message中的字符串）

    my $c = $rsa->encrypt( Message => $message, Key => $public );

Alice将密文$c发送给Bob，Bob用他的私钥$private解密以恢复原始信息

    $message = $rsa->decrypt( Ciphertext => $c, Key => $private );

通常，Alice和Bob使用Crypt::RSA进行安全交换不需要四行代码或更多。然而，了解Crypt::RSA在这四行代码下面做了什么以及如何使其有所不同是有教育意义的。

Crypt::RSA被构建为一个模块集合，它封装了RSA加密系统的不同方面。Crypt::RSA本身是集合中其他模块的便捷前端，它位于用户和其他模块之间，并预处理数据以满足双方的需求。

Crypt::RSA的一个职责是将文本转换为数字并将其转换回来。由于RSA算法在小于n的数字上工作，因此明文首先转换为小于n的数字列表，然后在加密后转换回文本，并将这些数字连接起来形成最终的密文。在解密时执行同样的过程。

Crypt::RSA 的加密模块还执行一个名为“填充”的过程。已知，如前节所述的教科书式 RSA，容易受到已知明文攻击。也就是说，如果爱丽丝被强制加密已知文本的某些数量，那么她可以恢复 p 和 q，而不需要分解 n。为了防止这种攻击，明文块必须以特殊的方式用随机数据填充。

多年来，一个名为 PKCS #1 的填充标准已被广泛使用。Crypt::RSA 不仅实现了 PKCS #1，还实现了较新的标准 OAEP。OAEP 提供了明文感知加密的概念，适用于不需要与较旧的 PKCS #1 应用程序进行互操作的应用程序。Crypt::RSA 默认使用 OAEP 填充。然而，可以通过在 new() 中传递参数来指定使用 PKCS #1，如下所示

    $rsa = new Crypt::RSA ( ES => 'PKCS1v15 )

ES 代表“加密方案”，PKCS1v15 代表 RFC 2437 中描述的 PKCS #1 标准版本 1.5。

数字签名和非抵赖性

加密只提供了数字隐私解决方案的一半。在线世界中的身份是可变的，并且可以轻易地伪造；这需要使用签名机制来确保人们是他们所说的那样。当你收到一条消息时，你如何真正知道发件人是他或她所声称的那样？这条消息可能是由其他人编写的；或者它可能在传输过程中被拦截、修改，然后转交给您。

数字签名为您提供了确定消息是否合法的工具。您可以使用数字签名来检测传输中的消息篡改，并确定消息是否真正来自所声明的发件人。这种签名是不可伪造的保证，既保证了消息的真实作者，也保证了其有效性。这种概念称为非抵赖性，也延伸到相反的方向：由于数字签名提供了发送者已签署数据的绝对证据，发送者不能随后否认已签署该数据。从逻辑上讲，一旦作者签署了他的作品，他就既不能否认签名的有效性，也不能否认作品的作者身份。

要对消息进行数字签名，就是将个人私钥应用于该消息。数字签名使用与加密和解密消息相同的公钥和私钥；然而，与发送者使用接收者的公钥加密消息相比，在签名时，发送者使用她的私钥签名消息。这是因为某些门函数也充当门函数。一旦私钥将消息打乱，生成的签名只能通过匹配的公钥来解密。如果消息的接收者持有该公钥的副本，他/她就可以确定是否使用私钥签署了消息。

以下是一个示例

爱丽丝希望向鲍勃发送消息，并希望鲍勃能够验证她发送了消息，并且在传输过程中消息没有被修改。在编写消息后，爱丽丝使用她的私钥“签名”该消息，然后将消息和签名发送给鲍勃。这个签名是根据消息中的数据计算的，使得它对爱丽丝的私钥和消息是唯一的。换句话说，这个特定的签名只能由爱丽丝的私钥生成。

为了验证签名，鲍勃使用爱丽丝的公钥副本来解密签名；如果他产生了原始信息，他知道信息没有被篡改。同时，如果艾娃正在监听网络流量并嗅探到爱丽丝的消息副本，她可以轻松修改它并发送给鲍勃；但是一旦她修改了原始信息，签名就不再匹配信息。当鲍勃收到带有原始签名的修改后的信息时，他的验证尝试将会失败，他会知道信息已被篡改。艾娃无法“修复”签名以使其与修改后的信息匹配，因为这需要拥有爱丽丝的私钥——只有爱丽丝才能访问这个密钥。因此，可以保证爱丽丝的身份和作者。

以下是爱丽丝如何使用Crypt::RSA签名她的消息

    $private = new Crypt::RSA::Key::Private(
                  Filename => "keys/alice.private",
                  Password => 'alice's passphrase'
               );
    $rsa = new Crypt::RSA;
    $signature = $rsa->sign ( Message => $message, Key => $private );

爱丽丝从磁盘文件中读取她的私钥。私钥通常以加密形式（使用对称加密）存储以提供额外的安全性，因此在使用之前必须进行解密。爱丽丝提供了一个密码来解密密钥，并在$private中读取密钥。然后她使用Crypt::RSA的sign()方法对消息进行签名，并将$signature和$message发送给鲍勃。鲍勃使用Alice的公钥通过Crypt:RSA的verify()方法验证签名。

    $public = new Crypt::RSA::Key::Public(
                  Filename => "keys/alice.public",
              );
    $rsa->verify( Message => $message, Signature => $signature,
                  Key => $public ) ||
                  die "Signature doesn't verify!\n";

需要注意的是，sign()计算消息的摘要并对其签名，而不是对原始消息签名。这通常是现实世界应用程序生成数字签名的方式。对整个消息进行签名既昂贵又不会比签名摘要提供任何好处。

Diffie-Hellman密钥协商

密钥协商是指两个当事人达成共享加密密钥的过程，而不将密钥暴露给潜在的入侵者。密钥协商协议与公钥加密协议不同，因为它们不是用于加密通信的；相反，它们用于协商一个秘密，该秘密可以用作使用对称加密的通信。在Rivest、Shamir和Aldeman发布他们的RSA论文后不久，Diffie & Hellman发布了一个后来被称为Diffie-Hellman密钥协商的密钥协商协议。

以下是它是如何工作的

为了开始密钥交换，爱丽丝和鲍勃选择一个属性p和一个属性g；这些属性的价值由双方共享，通常由一个中央机构计算，而不是由任意一方计算。然后每个当事人计算一个随机的私钥整数x，其中x的长度最多为(p中的位数)-1。然后每个当事人根据g、x和p计算一个公钥y；确切值是

    y = g^x mod p

当事人交换这些公钥。

共享密钥是通过交换的公钥、私钥和p生成的。如果鲍勃的公钥表示为y_Bob，那么爱丽丝使用以下公式计算共享密钥

    secret = y_Bob^x mod p

涉及的数学原理确保双方将生成相同的共享密钥。在计算了共享密钥——再次强调，该密钥从未通过不安全的网络传递——爱丽丝和鲍勃可以使用该密钥加密他们的通信；在这次会话期间，双方之间的所有未来消息都可以使用共享密钥进行对称加密。

更多信息可以在PKCS #3（Diffie-Hellman密钥协商标准）中找到。

可以在Crypt::DH中找到Diffie-Hellman密钥协商的Perl实现。要使用Crypt::DH，爱丽丝和鲍勃必须提前就p和g的值达成一致。例如，使用Diffie-Hellman的SSH-2协议使用g的值为2，而g的值为

      FFFFFFFF FFFFFFFF C90FDAA2 2168C234 C4C6628B 80DC1CD1
      29024E08 8A67CC74 020BBEA6 3B139B22 514A0879 8E3404DD
      EF9519B3 CD3A431B 302B0A6D F25F1437 4FE1356D 6D51C245
      E485B576 625E7EC6 F44C42E9 A637ED6B 0BFF5CB6 F406B7ED
      EE386BFB 5A899FA5 AE9F2411 7C4B1FE6 49286651 ECE65381
      FFFFFFFF FFFFFFFF

对于p。我们开始使用Crypt::DH，通过用p和g的选定值初始化一个Crypt::DH对象

    use Crypt::DH;
    my $dh = Crypt::DH->new;
    $dh->p($p);
    $dh->g($g);

然后，每个参与者生成一个公钥和一个私钥

    $dh->generate_keys;

生成密钥后，Alice必须将她的公钥发送给Bob，Bob也必须将他的公钥发送给Alice，通过网络。一旦Alice收到Bob的公钥，她就可以使用该公钥和自己的私钥生成共享密钥

    my $shared_secret = $dh->compute_key( $bob_public_key );

这个共享密钥是一个大整数。通常，这个大整数被线性化为一个八位字节串，用作Alice和Bob之间对称加密的密钥。由于双方都生成了相同的共享密钥，Alice能够解密Bob使用共享密钥加密的消息，反之亦然。

数字签名算法

DSA是数字签名算法，是一种由美国政府开发，用作数字签名标准的算法。在其创建之时，RSA正威胁着成为事实上的标准：例如，微软和莲花公司已经将其包含在他们的产品中。RSA提供了签名和加密两种功能，这让政府感到担忧：一个普通公民可能能够确保他们的个人通信安全，防止政府特工在网络上和电话线路上窃听，这对国家安全局（NSA）来说非常可怕。因此，政府推动了DSA的标准化，这是一个仅提供数字签名的算法，不能加密消息。

政府希望将密码学控制权从私人公司RSA数据安全公司手中交回到国家安全局手中。因此，他们推动DSA作为一个免费的标准，作为受许可限制的RSA的替代品；DSA不受RSA许可限制，因为它基于Tehar Elgamal发布的数字签名算法，而不是RSA算法。许多观点认为DSA是一个比RSA低劣的标准：它难以实现，数学上更复杂，签名验证比RSA慢（尽管签名更快）。更重要的是，DSA密钥的位数最大限制为1024位。尽管有这些担忧——或许，正因为如此——DSA被选为政府标准。

以下是DSA的工作原理

为了开始生成新的DSA密钥对，Alice生成一个大素数q（可以从用户提供的种子或从随机八位字节串生成），其中

    2^159 < q < 2^160

然后使用相同的种子构造一个素数p，使得q整除p-1，

    2^(bits-1) < p < 2^(bits)

其中bits是密钥的位数；位数可以从512位到1024位。

选择一个数g，使得

    g = h^((p-1)/q) mod p

其中h是大于1小于p-1的任何整数。一个典型的h值是2。

最后，生成两个数x和y，分别代表密钥的私钥部分和公钥部分。x是一个随机生成的整数，使得x大于0且小于q；y按以下方式推导：

    y = g^x mod p

DSA公钥由p、q、g和y的值组成；私钥由这些值和x的值组成。DSA签名由两个值组成，即r和s，通过将私DSA密钥应用于消息的SHA-1哈希值生成。要验证消息，验证者使用原始消息和发送者的公钥，通过数学方法从s的值回溯到最后一个值v；如果v等于r，则签名有效。否则，它无效。

Perl和Crypt::DSA，DSA的纯Perl实现，使得使用DSA进行数字签名变得非常简单。Alice生成一个新的DSA密钥

    use Crypt::DSA;
    my $dsa = Crypt::DSA->new;
    my $key = $dsa->keygen( Size => 512 );

将此密钥的公开部分发送给鲍勃后，她使用自己的私钥对其消息（存储在$message中的字符串）进行签名

    my $sig = $dsa->sign( Message => $message, Key => $key );

然后她将签名$sig和消息$message发送给鲍勃，鲍勃使用爱丽丝的公钥来验证签名

    my $valid = $dsa->verify( Signature => $sig, Message => $message,
                              Key => $alice_pub_key );

如果$valid为true，则签名$sig是有效的。

与此同时，如果伊芙已经嗅探了网络流量以截获发送给鲍勃的消息和签名，那么她可以修改消息$message；但为了重新生成签名$sig，伊芙必须能够访问爱丽丝的私钥。由于伊芙没有这个密钥，签名将不会与消息匹配，签名验证将失败。

施诺尔

与DH和DSA一样，施诺尔是另一个基于离散对数问题难度的签名算法。施诺尔于1991年由克劳斯-彼得·施诺尔专为智能卡使用而设计。施诺尔既是一种签名方案，也是一种交互式身份验证方案，它广泛使用查找表来生成签名，从而最大限度地减少签名计算设备上的计算工作量。Crypt::Schnorr::AuthSign模块提供了一个施诺尔的Perl实现。有关使用信息，我们建议读者查阅模块的POD文档。

未来文章

这结束了关于Perl非对称加密的三个系列文章的第一部分。第二部分将讨论现实世界中的非对称加密：SSH、PGP和SSL等系统和协议，这些都是你每天使用的非对称加密应用。除了讨论这些应用外，我们还将探讨现实世界密码学系统设计中的计算和安全约束。第三部分将讨论非对称加密的构建块，它将涵盖一些有趣的主题，如素数生成、位域/缓冲区操作、大数数学和数论，所有这些在Perl中都有全面实现。