SSH协议体系结构解读.doc

SSH协议体系结构解读1、概念 SSH的英文全称为Secure Shell，是IETF（Internet Engineering Task Force）的Network Working Group所制定的一族协议，其目的是要在非安全网络上提供安全的远程登录和其他安全网络服务。如需要SSH的详细信息请参考（SSH Communications Security Corporation的网站）和（开放源码的OpenSSH组织的网站）。 2、基本框架 SSH协议框架中最主要的部分是三个协议：传输层协议、用户认证协议和连接协议。同时SSH协议框架中还为许多高层的网络安全应用协议提供扩展的支持。它们之间的层次关系可以用如下图1来表示： 图1 SSH协议的层次结构示意图在SSH的协议框架中，传输层协议（The Transport Layer Protocol）提供服务器认证，数据机密性，信息完整性 等的支持；用户认证协议（The User Authentication Protocol） 则为服务器提供客户端的身份鉴别；连接协议（The Connection Protocol） 将加密的信息隧道复用成若干个逻辑通道，提供给更高层的应用协议使用；各种高层应用协议可以相对地独立于SSH基本体系之外，并依靠这个基本框架，通过连接协议使用SSH的安全机制。 3、主机密钥机制 对于SSH这样以提供安全通讯为目标的协议，其中必不可少的就是一套完备的密钥机制。由于SSH协议是面向互联网网络中主机之间的互访与信息交换，所以主机密钥成为基本的密钥机制。也就是说，SSH协议要求每一个使用本协议的主机都必须至少有一个自己的主机密钥对，服务方通过对客户方主机密钥的认证之后，才能允许其连接请求。一个主机可以使用多个密钥，针对不同的密钥算法而拥有不同的密钥，但是至少有一种是必备的，即通过DSS算法产生的密钥。关于DSS算法，请参考FIPS-186。 SSH协议关于主机密钥认证的管理方案有两种，如下图2所示： 图2 SSH主机密钥管理认证方案示意图每一个主机都必须有自己的主机密钥，密钥可以有多对，每一对主机密钥对包括公开密钥和私有密钥。在实际应用过程中怎样使用这些密钥，并依赖它们来实现安全特性呢？如上图所示，SSH协议框架中提出了两种方案。 在第一种方案中，主机将自己的公用密钥分发给相关的客户机，客户机在访问主机时则使用该主机的公开密钥来加密数据，主机则使用自己的私有密钥来解密数据，从而实现主机密钥认证，确定客户机的可靠身份。在图2（a）中可以看到，用户从主机A上发起操作，去访问，主机B和主机C，此时，A成为客户机，它必须事先配置主机B和主机C的公开密钥，在访问的时候根据主机名来查找相应的公开密钥。对于被访问主机（也就是服务器端）来说则只要保证安全地存储自己的私有密钥就可以了。 在第二种方案中，存在一个密钥认证中心，所有系统中提供服务的主机都将自己的公开密钥提交给认证中心，而任何作为客户机的主机则只要保存一份认证中心的公开密钥就可以了。在这种模式下，客户机在访问服务器主机之前，还必须向密钥认证中心请求认证，认证之后才能够正确地连接到目的主机上。 很显然，第一种方式比较容易实现，但是客户机关于密钥的维护却是个麻烦事，因为每次变更都必须在客户机上有所体现；第二种方式比较完美地解决管理维护问题，然而这样的模式对认证中心的要求很高，在互联网络上要实现这样的集中认证，单单是权威机构的确定就是个大麻烦，有谁能够什么都能说了算呢？但是从长远的发展来看，在企业应用和商业应用领域，采用中心认证的方案是必要的。 另外，SSH协议框架中还允许对主机密钥的一个折中处理，那就是首次访问免认证。首次访问免认证是指，在某客户机第一次访问主机时，主机不检查主机密钥，而向该客户都发放一个公开密钥的拷贝，这样在以后的访问中则必须使用该密钥，否则会被认为非法而拒绝其访问。 4、字符集和数据类型 SSH协议为了很好地支持全世界范围的扩展应用，在字符集和信息本地化方面作了灵活的处理。首先，SSH协议规定，其内部算法标识、协议名字等必须采用US-ASCII字符集，因为这些信息将被协议本身直接处理，而且不会用来作为用户的显示信息。其次，SSH协议指定了通常情况下的统一字符集为ISO 10646标准下的UTF-8格式，详细请参考RFC-2279。另外，对于信息本地化的应用，协议规定了必须使用一个专门的域来记录语言标记（Language Tag）。对于大多数用来显示给用户的信息，使用什么样的字符集主要取决于用户的终端系统，也就是终端程序及其操作系统环境，因而对此SSH协议框架中没有作硬性规定，而由具体实现协议的程序来自由掌握。 除了在字符、编码方面的灵活操作外，SSH协议框架中还对数据类型作了规定，提供了七种方便实用的种类，包括字节类型、布尔类型、无符号的32位整数类型、无符号的64位整数类型、字符串类型、多精度整数类型以及名字表类型。下面分别解释说明之： （1）字节类型（byte） 一个字节（byte）代表一个任意的8字位值（octet）RFC-1700。有时候固定长度的数据就用一个字节数组来表示，写成byten的形式，其中n是数组中的字节数量。 （2）布尔类型（boolean） 一个布尔值（boolean）占用一个字节的存储空间。数值0表示“假”（FALSE），数值1表示“真”（TRUE）。所有非零的数值必须被解释成“真”，但在实际应用程序中是不能给布尔值存储0和1意外的数值。 （3）无符号的32位整数类型（unit32） 一个32字位的无符号整型数值，由按照降序存储的四个字节构成（降序即网络字节序，高位在前，低位在后）。例如，有一个数值为63828921，它的十六进制表示为0x03CDF3B9，在实际存储时就是03 CD F3 B9，具体存储结构的地址分配如图3。 图3 无符号32位整数类型的典型存储格式（4）无符号的64位整数类型（unit64） 一个64字位的无符号整型数值，由按照降序存储的八个字节构成，其具体存储结构与32位整数类似，可以比照图3。 （5）字符串类型（string） 字符串类型就是任意长度的二进制序列。字符串中可以包含任意的二进制数据，包括空字符（null）和8位字符。字符串的前四个字节是一个unit32数值，表示该字符串的长度（也就是随后有多少个字节），unit32之后的零个或者多个字节的数据就是字符串的值。字符串类型不需要用空字符来表示结束。 字符串也被用来存储文本数据。这种情况下，内部名字使用US-ASCII字符，可能对用户显示的文本信息则使用ISO-10646 UTF-8编码。一般情况字符串中不应当存储表示结束的空字符（null）。 在图4中举例说明字符串“My ABC”的存储结构： 图4 字符串类型的典型存储格式从图4中可以很明显地看出，字符串类型所占用的长度为4个字节加上实际的字符个数（字节数），即使没有任何字符的字符串也要占用四个字节。这种结构与Pascal语言中的字符串存储方式类似。 （6）多精度整数类型（mpint） 多精度的整数类型实际上是一个字符串，其数据部分采用二进制补码格式的整数，数据部分每个字节8位，高位在前，低位在后。如果是负数，其数据部分的第一字节最高位为1。如果恰巧一个正数的最高位是1时，它的数据部分必须加一个字节0x00作为前导。需要注意的是，额外的前导字节如果数值为0或者255时就不能被包括在整数数值内。数值0则必须被存储成一个长度为零的字符串（string）。多精度整数在具体运算时还是要遵循正常的整数运算法则的。其存储格式通过图5的若干示例来说明： 图5 多精度整数类型的典型存储格式（7）名字表类型（name-list） 名字表（name-list）是一个由一系列以逗号分隔的名字组成的字符串（string）。在存储方式上与字符串一样，名字表前四个字节是一个unit32型整数以表示其长度（随后的字节数目，类似于字符串类型），其后跟随着由逗号分隔开的一系列名字，可以是0个或者多个。一个名字则必须具有非零长度，而且不能包含逗号，因为逗号是名字之间的分隔符。在使用时，上下文关系可以对名字表中的名字产生额外的限制，比如，一个名字表中的名字都必须是有效的算法标识，或者都是语言标记等。名字表中名字是否与顺序相关，也要取决于该名字表所在的上下文关系。与字符串类型一样，无论是单个的名字，还是整个名字表，都不需要使用空字符作为结束。如下图6： 图6 名字表的典型存储格式SSH协议框架中拥有对这些数据类型的支持，将对协议、算法的处理带来极大的便利。 5、命名规则及消息编码 SSH协议在使用到特定的哈希算法，加密算法，完整性算法，压缩算法，以及密钥交换算法和其他协议时都利用名字来区分，所以SSH协议框架中很重要的一个部分就是命名规则的限定。无论是SSH协议框架中所必备的算法或者协议，还是今后具体应用实现SSH协议时增加的算法或者协议，都必须遵循一个统一的命名规则。 SSH协议框架对命名规则有一个基本原则：所有算法标识符必须是不超过64个字符的非空、可打印US-ASCII字符串；名字必须是大小写敏感的。 具体的算法命名有两种格式： （1）不包含符号的名字都是为IETF标准（RFC文档）保留的。比如，“3des-cbc”，“sha-1”，“hmac-sha1”，“zlib”（注意：引号不是名字的一部分)。在没有事先注册之前，这种格式的名字是不能使用的。当然IETF的所有注册的名字中也不能包含符号或者逗号。 （2）任何人都可以使用“namedomainname”的格式命名自定义的算法，比如“”。在符号之前部分的具体格式没有限定，不过这部分中必须使用除符号和逗号之外的US-ASCII字符。在符号之后的部分则必须是一个完全合法的Internet域名（参考RFC-1034），个人域名和组织域名均可。至于局部名字空间的管理则是由各个域自行负责的。 SSH协议框架中另一个主要的标准化规则就是消息编码，基本规定在表1中详述： 表1 SSH协议框架中的编码范围原则6、SSH协议的可扩展能力 SSH协议框架中设计了大量可扩展的冗余能力，比如用户自定义算法、客户自定义密钥规则、高层扩展功能性应用协议等，在本文中将不一一赘述。值得一提的是，这些扩展大多遵循IANA（Internet Assigned Numbers Authority）的有关规定，特别是在重要的部分，象命名规则和消息编码方面。关于IANA的标准及组织情况请访问该组织的官方网站：。 协议浅析第一部分：协议概览整个通讯过程中，经过下面几个阶段协商实现认证连接。第一阶段:由客户端向服务器发出 TCP 连接请求。TCP 连接建立后，客户端进入等待，服务器向客户端发送第一个报文，宣告自己的版本号，包括协议版本号和软件版本号。协议版本号由主版本号和次版本号两部分组成。它和软件版本号一起构成形如：SSH-.-n的字符串。其中软件版本号字符串的最大长度为40个字节，仅供调试使用。客户端接到报文后，回送一个报文，内容也是版本号。客户端响应报文里的协议版本号这样来决定：当与客户端相比服务器的版本号较低时，如果客户端有特定的代码来模拟，则它发送较低的版本号；如果它不能，则发送自己的版本号。当与客户端相比服务器的版本号较高时，客户端发送自己的较低的版本号。按约定，如果协议改变后与以前的相兼容，主协议版本号不变；如果不相兼容，则主主协议版本号升高。服务器接到客户端送来的协议版本号后，把它与自己的进行比较，决定能否与客户端一起工作。如果不能，则断开TCP 连接；如果能，则按照二进制数据包协议发送第一个二进制数据包，双方以较低的协议版本来一起工作。到此为止，这两个报文只是简单的字符串，你我等凡人直接可读。第二阶段:协商解决版本问题后，双方就开始采用二进制数据包进行通讯。由服务器向客户端发送第一个包，内容为自己的 RSA主机密钥(host key)的公钥部分、RSA服务密钥(server key)的公钥部分、支持的加密方法、支持的认证方法、次协议版本标志、以及一个 64 位的随机数(cookie)。这个包没有加密，是明文发送的。客户端接收包后，依据这两把密钥和被称为cookie的 64 位随机数计算出会话号(session id)和用于加密的会话密钥(session key)。随后客户端回送一个包给服务器，内容为选用的加密方法、cookie的拷贝、客户端次协议版本标志、以及用服务器的主机密钥的公钥部分和服务密钥的公钥部分进行加密的用于服务器计算会话密钥的32 字节随机字串。除这个用于服务器计算会话密钥的 32字节随机字串外，这个包的其他内容都没有加密。之后，双方的通讯就是加密的了，服务器向客户端发第二个包（双方通讯中的第一个加密的包）证实客户端的包已收到。第三阶段:双方随后进入认证阶段。可以选用的认证的方法有：(1) /.rhosts 或 /etc/hosts.equiv 认证（缺省配置时不容许使用它）;(2) 用 RSA 改进的 /.rhosts 或 /etc/hosts.equiv 认证；(3) RSA 认证；(4) 口令认证。如果是使用 /.rhosts 或 /etc/hosts.equiv 进行认证，客户端使用的端口号必须小于1024。认证的第一步是客户端向服务器发 SSH_CMSG_USER 包声明用户名，服务器检查该用户是否存在，确定是否需要进行认证。如果用户存在，并且不需要认证，服务器回送一个SSH_SMSG_SUCCESS 包，认证完成。否则，服务器会送一个 SSH_SMSG_FAILURE 包，表示或是用户不存在，或是需要进行认证。注意，如果用户不存在，服务器仍然保持读取从客户端发来的任何包。除了对类型为 SSH_MSG_DISCONNECT、SSH_MSG_IGNORE 以及 SSH_MSG_DEBUG 的包外，对任何类型的包都以 SSH_SMSG_FAILURE 包。用这种方式，客户端无法确定用户究竟是否存在。如果用户存在但需要进行认证，进入认证的第二步。客户端接到服务器发来的 SSH_SMSG_FAILURE 包后，不停地向服务器发包申请用各种不同的方法进行认证，直到时限已到服务器关闭连接为止。时限一般设定为 5 分钟。对任何一个申请，如果服务器接受，就以 SSH_SMSG_SUCCESS 包回应；如果不接受，或者是无法识别，则以 SSH_SMSG_FAILURE 包回应。第四阶段:认证完成后，客户端向服务器提交会话请求。服务器则进行等待，处理客户端的请求。在这个阶段，无论什么请求只要成功处理了，服务器都向客户端回应 SSH_SMSG_SUCCESS包；否则回应 SSH_SMSG_FAILURE 包，这表示或者是服务器处理请求失败，或者是不能识别请求。会话请求分为这样几类：申请对数据传送进行压缩、申请伪终端、启动 X11、TCP/IP 端口转发、启动认证代理、运行 shell、执行命令。到此为止，前面所有的报文都要求 IP 的服务类型(TOS)使用选项 IPTOS_THROUGHPUT。第五阶段:会话申请成功后，连接进入交互会话模式。在这个模式下，数据在两个方向上双向传送。此时，要求 IP 的服务类型(TOS)使用 IPTOS_LOWDELAY 选项。当服务器告知客户端自己的退出状态时，交互会话模式结束。（注意：进入交互会话模式后，加密被关闭。在客户端向服务器发送新的会话密钥后，加密重新开始。用什么方法加密由客户端决定。）第二部分：数据包格式和加密类型二进制数据包协议：包 = 包长域(4字节:u_int32_t) + 填充垫(1-7字节)+ 包类型域(1字节：u_char) + 数据域+ 校验和域(4字节)加密部分 = 填充垫 + 包类型 + 数据 + 校验和包长 = 1(包类型) + 数据字节长度 + 4(校验和)数据包压缩：如果支持压缩，包类型域和数据域用 gzip 压缩算法进行压缩。压缩时在两个数据传送方向的任何一个上，包的压缩部分(类型域+数据域)被构造得象是它连在一起，形成一个连续的数据流。在两个数据传送方向上，压缩是独立进行的。数据包加密:现时支持的数据加密方法有这样几种：SSH_CIPHER_NONE 0 不进行加密SSH_CIPHER_IDEA 1 IDEA 加密法（CFB模式）SSH_CIPHER_DES 2 DES 加密法（CBC模式）SSH_CIPHER_3DES 3 3DES 加密法（CBC模式）SSH_CIPHER_ARCFOUR 5 Arcfour加密法)SSH_CIPHER_BLOWFISH 6 Blowfish 加密法协议的所有具体实现都要求支持3DES。DES 加密：从会话密钥中取前8个字节，每个字只用高7位，忽略最低位，这样构成56位的密钥供加密使用。加密时使用CBC 模式，初使矢量被初始化为全零。3DES 加密：3DES 是 DES 的变体，它三次独立地使用 CBC 模式的DES 加密法，每一次的初始矢量都是独立的。第一次用DES 加密法对数据进行加密；第二次对第一次加密的结果用 DES 加密法进行解密；第三次再对第二次解密的结用 DES 加密法进行加密。注意：第二次解密的结果并不就是被加密的数据，因为三次使用的密钥和初始矢量都是分别不同的。与上面的 DES 加密采用的方法类似，第一次从会话密钥中取起始的前8个字节生成加密密钥，第二次取下一个紧跟着的8个字节，第三次取再下一个紧跟着的8个字节。三次使用的初始矢量都初始化为零。IDEA 加密：加密密钥取自会话密钥的前16个字节，使用 CFB 模式。初始矢量初始化为全零。RC4 加密：会话密钥的前16个字节被服务器用作加密密钥，紧接着的下一个16字节被客户端用作加密密钥。结果是两个数据流方向上有两个独立的129位密钥。这种加密算法非常快。第二部分：密钥的交换和加密的启动在服务器端有一个主机密钥文件，它的内容构成是这样的：1. 私钥文件格式版本字符串；2. 加密类型（1 个字节）；3. 保留字（4 个字节）；4. 4 个字节的无符号整数；5. mp 型整数；6. mp 型整数；7. 注解字符串的长度；8. 注解字符串；9. 校验字（4 个字节）；10. mp 型整数；11. mp 型整数；12. mp 型整数；13. mp 型整数；其中 4、5、6 三个字段构成主机密钥的公钥部分；10、11、12、13 四个字段构成主机密钥的私钥部分。9、10、11、12、13 五个字段用字段 2 的加密类型标记的加密方法进行了加密。4 个字节的校验字交叉相等，即第一个字节与第三个字节相等，第二个字节与第四个字节相等。在服务器读取这个文件时进行这种交叉相等检查，如果不满足这个条件，则报错退出。服务器程序运行的第一步，就是按照上面的字段划分读取主机密钥文件。随后生成一个随机数，再调用函数void rsa_generate_key(RSAPrivateKey *prv,RSAPublicKey *pub, RandomState *state,unsigned int bits)；生成服务密钥，服务密钥也由公钥和私钥两部分组成。上面的这个函数第一个指针参数指向服务密钥的私钥部分，第二个指向公钥部分。然后把主机密钥的公钥部分和服务密钥的公钥部分发送给客户端。在等到客户端回应的包后，服务器用自己的主机密钥的私钥部分和服务密钥的私钥部分解密得到客户端发来的 32 字节随机字串。然后计算自己的会话号，并用会话号的前 16字节 xor 客户端发来的 32 字节随机字串的前 16 字节，把它作为自己的会话密钥。注意，服务器把8个字节的 cookie、主机密钥的公钥部分、和服务密钥的公钥部分作为参数来计算自己的会话号。再来看客户端。客户端启动后的第一步骤也是读取主机密钥。然后等待服务器主机密钥、服务密钥、和 8个字节的cookie。注意，服务器发送来的只是主机密钥和服务密钥的公钥部分。接到包后，客户端立即把从服务器端收到cookie、主机密钥、和服务密钥作为参数计算出会话号。从上面可以看出，服务器和客户端各自计算出的会话号实际是一样的。随后，客户端检查用户主机列表和系统主机列表，查看从服务器收到的主机密钥是否在列表中。如果不在列表中，则把它加入列表中。然后就生成 32 字节的随机字串，这个32 字节的随机字串就是客户端的会话密钥。客户端用 16字节的会话密钥 xor 它的前 16 字节，把结果用服务器的主机密钥和服务密钥进行双重加密后发送给服务器。产生 32字节随机字串时，随机数种子由两部分组成，其中一部分从系统随机数种子文件中得到，这样来避免会话密钥被猜出。从上面服务器和客户端各自计算会话密钥的过程可以看出，服务器和客户端计算出的会话密钥是一样的。上面的这几步，总结起来就要交换确定会话密钥，因为无论是 des、idea、3des、arcfour、还是 blowfish 都是对称加密方法，只有一把密钥，双方都知道了会话密钥才能启动加密。但会话密钥不能在网络上明文传送，否则加密就失去意义了。于是使用 RSA 公钥体系对会话密钥进行加密。RSA 公钥体系的办法是用公钥加密私钥解密，它依据这样的数学定理：若 p、q 是相异的两个质数，整数 r 和 m 满足rm = 1 (mod (p-1)(q-1)a 是任意的整数，整数 b、c 满足 b = am (mod pq),c = br (mod pq)。则c = a (mod pq)。具体实现是这样的：(1) 找三个正整数 p、q、r，其中 p、q 是相异的质数，r 是与(p-1)、(q-1)互质的数。这三个数 p、q、r就是私钥(private key)。(2) 再找一个正整数 m 满足 rm = 1 (mod(p-1)(q-1)。计算 n = pq，m、n 就是公钥(public key)。(3) 被加密对象 a 看成是正整数，设 a = n，将 a 表示成 s (s n，通常取 s = 2t) 进制的，然后对每一位分别编码。(4) 加密：计算 b = am (mod n) (0 = b n)，b 为加密结果。(5) 解密：计算 c = br (mod n) (0 = c q);mpz_init(&prv-p);mpz_init(&prv-e);mpz_init(&prv-d);mpz_init(&prv-u);mpz_init(&prv-n);mpz_init(&test);mpz_init(&aux);/* 计算质数 p、q 的位数 */pbits = bits / 2;qbits = bits - pbits;retry0:fprintf(stderr, Generating p: );/* 生成随机质数 p */rsa_random_prime(&prv-p, state, pbits);retry:fprintf(stderr, Generating q: );/* 生成随机质数 q */rsa_random_prime(&prv-q, state, qbits);/* 判断是否 p = q，如果是返回重新生成 */ret = mpz_cmp(&prv-p, &prv-q);if (ret = 0)fprintf(stderr,Generated the same prime twice!n);goto retry;if (ret 0)mpz_set(&aux, &prv-p);mpz_set(&prv-p, &prv-q);mpz_set(&prv-q, &aux);/* 确定 p、q 是否很接近 */mpz_sub(&aux, &prv-q, &prv-p);mpz_div_2exp(&test, &prv-q, 10);if (mpz_cmp(&aux, &test) p, &prv-q);if (mpz_cmp_ui(&aux, 1) != 0)fprintf(stderr,The primes are not relatively prime!n);goto retry;/* 从质数 p、q 导出私钥 */fprintf(stderr, Computing the keys.n);derive_rsa_keys(&prv-n, &prv-e, &prv-d,&prv-u, &prv-p, &prv-q, 5);prv-bits = bits;/* 从质数 p、q 导出公钥 */pub-bits = bits;mpz_init_set(&pub-n, &prv-n);mpz_init_set(&pub-e, &prv-e);/* 测试公钥和密钥是否有效 */fprintf(stderr, Testing the keys.n);rsa_random_integer(&test, state, bits);mpz_mod(&test, &test, &pub-n); /* must be less than n. */rsa_private(&aux, &test, prv);rsa_public(&aux, &aux, pub);if (mpz_cmp(&aux, &test) != 0)fprintf(stderr,* private+public failed to decrypt.n);goto retry0;rsa_public(&aux, &test, pub);rsa_private(&aux, &aux, prv);if (mpz_cmp(&aux, &test) != 0)fprintf(stderr,* public+private failed to decrypt.n);goto retry0;mpz_clear(&aux);mpz_clear(&test);fprintf(stderr, Key generation complete.n);_在上面的函数成一对密钥时，首先调用函数_void rsa_random_prime(MP_INT *ret, RandomState *state,unsigned int bits)MP_INT start, aux;unsigned int num_primes;int *moduli;long difference;mpz_init(&start);mpz_init(&aux);retry:/* 挑出一个随机的足够大的整数 */rsa_random_integer(&start, state, bits);/* 设置最高的两位 */mpz_set_ui(&aux, 3);mpz_mul_2exp(&aux, &aux, bits - 2);mpz_ior(&start, &start, &aux);/* 设置最低的两位为奇数 */mpz_set_ui(&aux, 1);mpz_ior(&start, &start, &aux);/* 启动小质数的 moduli 数 */moduli = malloc(MAX_PRIMES_IN_TABLE * sizeof(moduli0);if (moduli = NULL)printf(stderr, Cannt get memory for modulin);exit(1);if (bits 0x70000000)fprintf(stderr, rsa_random_prime: failed to find a prime, retrying.n);if (moduli != NULL)free(moduli);elseexit(1);goto retry;/* 检查它是否是小质数的乘积 */for (i = 0; i = small_primesi)modulii -= small_primesi;if (modulii + difference = 0)break;if (i num_primes)continue; /* Multiple of a known prime. */* 检查通过 */fprintf(stderr, .);/* Compute the number in question. */mpz_add_ui(ret, &start, difference);/* Perform the fermat test for witness 2.This means: it is not prime if 2n mod n != 2. */mpz_set_ui(&aux, 2);mpz_powm(&aux, &aux, ret, ret);if (mpz_cmp_ui(&aux, 2) = 0)/* Passed the fermat test for witness 2. */fprintf(stderr, +);/* Perform a more tests. These are probably unnecessary. */if (mpz_probab_prime_p(ret, 20)break; /* It is a prime with probability 1 - 2-40. */* Found a (probable) prime. It is in ret. */fprintf(stderr, + (distance %ld)n, difference);/* Free the small prime moduli; they are no longer needed. */if (moduli != NULL)free(moduli);elseexit(1);/* Sanity check: does it still have the high bit set (we might havewrapped around)? */mpz_div_2exp(&aux, ret, bits - 1);if (mpz_get_ui(&aux) != 1)fprintf(stderr,rsa_random_prime: high bit not set, retrying.n);goto retry;mpz_clear(&start);mpz_clear(&aux);_随机产生一对大质数(p,q)。这对随机大质数要符合的条件是p 必须小于 q。然后调用下面的函数来生成公钥和私钥对的其他组员：static void derive_rsa_keys(MP_INT *n, MP_INT *e, MP_INT *d, MP_INT *u,MP_INT *p, MP_INT *q,unsigned int ebits)MP_INT p_minus_1, q_minus_1, aux, phi, G, F;assert(mpz_cmp(p, q) = 0)fprintf(stderr, Warning: G=);mpz_out_str(stdout, 10, &G);fprintf(stderr, is large (many spare key sets); key may be bad!n);/* F = phi / G; the number of relative primenumbers per spare key set. */mpz_div(&F, &phi, &G);/* Find a suitable e (the public exponent). */mpz_set_ui(e, 1);mpz_mul_2exp(e, e, ebits);mpz_sub_ui(e, e, 1); /*make lowest bit 1, and substract 2.*/* Keep adding 2 until it is relatively primeto (p-1)(q-1). */dompz_add_ui(e, e, 2);mpz_gcd(&aux, e, &phi);while (mpz_cmp_ui(&aux, 1) != 0);/* d is the multiplicative inverse of e, mod F.Could also be mod (p-1)(q-1); however, we try tochoose the smal