CS

HTTPS(Hypertext Transfer Protocol Secure)译为超文本传输安全协议，也称为HTTP over TLS，HTTP over SSL或HTTP Secure，它对HTTP协议进行的扩展，用于在计算机网络上进行安全通信。其主要目的是对站点服务器进行身份认证，保护交换数据的隐私与完整性。 SSL/TLS协议 HTTP协议位于TCP/IP四层模型最高层的应用层。HTTPS是在HTTP所在的应用层加入一个子层，位于HTTP子层之下，传输层之上。 根据RFC: TLS协议的主要目的是为两个通信应用间提供隐私与数据完整性。该协议主要由两层组成：TLS Record协议和TLS Handshake协议。在某个稳定的传输协议（如TCP）之上，在最底层是TLS Record协议。 TLS Record协议所提供的连接安全性有两个基本属性： 连接是私有的。 对称加密用于数据加密（例如AES, RC4等），每个连接都会生成唯一的对称加密秘钥，并且该秘钥是基于另一个协议（例如TLS Handshake协议）经过协商后的秘钥得来的。Record协议也可以不使用加密。 连接是可靠的。 消息传输包含一个使用一个使用秘钥的MAC的消息完整性检查。安全哈希函数（例如，SHA-1等）用于MAC计算。Record协议可以不使用MAC进行运行，但这种情况通常仅使用在这种模式下，即另一个协议将Record协议作为协商安全参数的传输器。 TLS Record协议用于封装更高层级的协议。其中一个就是TLS Handshake协议，它允许服务器和客户端对彼此进行认证并且在应用层协议传输和接收数据的第一个字节前协商一个加密算法以及要使用的秘钥。 TLS Handshake协议提供的连接安全性有三个基本性质： 对等端的身份可以使用非对称加密或公钥密码学（如，RSA，DSA等）进行认证，这种认证是可选的，但一般需要对等端至少一方进行认证。 对共享秘钥的协商是安全的：协商的秘钥是不能被窃听者获取的，并且对任意未认证的连接都不能获取到秘钥，即使攻击者位于连接的中间。 协商是可靠的：没有攻击者能够修改协商通信内容并且不被通信方发现。 TLS的一项优点是它是与应用协议独立的，更高层级的协议可以透明地置于TLS协议之上。TLS标准并没有指定什么协议可以使用TLS来添加安全性，如何初始化TLS握手以及如何解释认证证书交换的决定留给TLS之上的协议的设计者和实现者。 HTTPS连接的建立与加密通信 在实现中，SSL/TLS子层作为HTTP子层和传输层的中间层，对套接字接口进行了一层封装，用于建立安全连接与通信。会话状态的加密参数是通过TLS握手协议来生成的，当一个TLS客户端和服务端首次开始进行通信时，它们在一个协议版本上达成一致、选择密码学算法、可选地对对方进行认证，并使用公钥加密技术来生成共享秘钥。 它包含如下步骤： 交换hello消息来对算法达成一致，交换随机值并进行恢复会话的检查 交换必要的机密参数，运行客户端和服务端对预主密钥（premaster secret）达成一致 交换证书和密码学信息，允许客户端和服务端对彼此进行认证 从预主密钥（premaster secret）生成一个主密钥并交换随机值 为Record层提供安全参数 允许客户端和服务端确认它们的对等端计算出相同的安全参数并且握手没有被攻击者干预 TLS握手的完整步骤如下所示（其中带*表示可选的或根据情况进行发送的消息，并不总是会发送）： Client Server ClientHello --------> ServerHello Certificate* ServerKeyExchange* CertificateRequest* <-------- ServerHelloDone Certificate* ClientKeyExchange CertificateVerify* [ChangeCipherSpec] Finished --------> [ChangeCipherSpec] <-------- Finished Application Data <-------> Application Data 可以使用openssl提供的工具来查看这一步骤的实际数据交换情况：...

CA 证书颁发机构（CA, Certificate Authorities）根据认证操作规则 (CPS) 授权颁发、暂停、更新或取消证书的实体。在其颁发的所有证书和 CRL 中都可通过识别名称来识别 CA。证书颁发机构必须公布其公钥，或者如果该证书颁发机构隶属一级证书颁发机构，则由更高级的 CA 提供证书证明其公钥的合法性。 数字证书（Digital Certificates）是可进行验证的包含身份证明的小的数据文件，它可以帮助网站、个人、设备来代表他们真实可信的在线身份（可信是因为CA已经对身份进行了验证）。CA在互联网上的操作以及如何进行透明可信的事务中扮演了关键角色。每年，证书机构都会颁发上百万的数字证书，它们用于保护信息，加密数以十亿计的事务，并确保安全的通信。 如何保证CA可信 浏览器、操作系统和移动设备会运行一个已授权的CA成员资格程序，其中一个CA必须满足详细的标准才能够被接受作为其中一员。一旦所接受的CA能够颁发直接被浏览器信任的证书，随后，人们和设备就可以依赖该证书进行工作。仅有少量经过授权的CA，从私有公司到政府机构都有，并且CA运作的越久，就会有越多的浏览器和设备信任该CA颁发的证书。 在颁发一个数字证书前，CA会对申请者的身份进行一些检查。这些检查与所申请的证书类型相关，例如，一个对域名所有权进行验证的SSL证书（Domain Validated (DV SSL) Certificates）会将已经验证了所有权的域名包含到证书中。而一个可扩展SSL(Extended Validation SSL)会包含公司相关的额外信息，这些信息由CA通过许多公司检查进行验证。 证书有许多种类型，不仅仅是支持SSL，还可以用于对人员和设备进行认证，对代码和文档添加合法性证明等。 PKI与信任层级 浏览器和设备通过在其根证书库（Root Store）中接受根证书（Root Certificate）来信任一个CA，这个根证书库本质上是一个预先安装在浏览器或设备上的已信任CA数据库。Windows、Apple、Mozilla以及一般的移动媒介都运行自己的根证书库。 各CA使用这些预安装的根证书来办法中介根证书和终端实体数字证书。CA接收证书请求，验证申请者，颁发证书，并对依赖于该证书的任何人发布已颁发证书的持续的有效性状态。 CA通常会创建一些中介CA（ICA，Intermediate CA）,用于办法终端实体证书，如SSL证书，这称为一个信任层次。 遵循最佳安全实践，CA不应该直接从发布给媒介的根证书来颁发数字证书，而应该通过一个或多个ICA。 CA是如何运作的 作为互联网中一个可信任的锚点，CA具有重大的责任。因此，在满足可审计的需求下运行一个CA是一个复杂的任务。一个CA基础设施由大量运作元素，硬件、软件、政策框架以及实践声明、审计、安保基础设施和人员组成。总体上，这些元素称为一个可信任的PKI(Public Key Infrastructure)。 SSL与TLS SSL(Secure Socket Layers)是指安全套接字层，它是一项标准技术，用于确保互联网连接安全。 TLS(Transport Layer Security)指传输层安全，它是SSL的升级版。 历史简介 SSL和TLS都是加密协议，用于提供服务器、设备、应用在网络上的认证和数据加密。SSL是先于TLS设计出的，最初它是由网景公司于1995年首先公布的，最初的版本是SSL2.0（SSL1.0从未公开发布）。在修正若干缺陷后，1996年版本2.0迅速被SSL3.0所取代。 TLS在1999年作为基于SSL3.0的一个新版本被发布，根据RFC2246： 该协议和SSL3.0没有十分巨大的差别，但已有的差别就足以使得两者不能进行互操作。 SSL2.0和SSL3.0分别在2011和2015年已经被IETF废弃，因此现在应该使用TLS协议。 SSL和TLS采用不同的加密方式。 SSL和TLS仅仅指客端和服务器端进行的握手，握手并没有进行任何加密，它仅仅是对需要共享的秘钥和加密类型上达成一致。 SSL/TLS证书 SSL证书是数字证书的一种，它用于将一个网站服务器的所有者详情和加密秘钥进行绑定。在浏览器和持有SSL证书的服务器之间，这些秘钥用于在SSL/TLS协议中激活一个安全会话。为了让浏览器相信一个SSL证书，并在不引起安全性警告的前提下建立SSL/TLS会话，SSL证书必须包含网站的域名，并且由可信任的CA颁发，并且没有过期。 SSL证书的功能 因此SSL证书主要有两个功能： 认证与验证 SSL证书中包含有关于一个人、商业或站点的身份的特定细节的可靠性信息。其中CA颁发的扩展验证SSL证书对申请人的审查标准最为严格，因此它是最值得信赖的SSL证书。 数据加密 SSL证书也可以进行加密，也就意味着通过网络交换的敏感信息不回被第三者窃取并破译出。 其用途举例如下： 保障站点和用户浏览器通信的安全 保障企业内网内部通信的安全 保障通过网络进行的邮件通信的安全 保障通过因特网或内网进行的服务器间通信的安全 保障移动设备收发信息的安全 SSL证书的类型 目前有如下几种不同类型的证书： 自签发证书 主要用于内部使用的非CA颁发的证书。如果在外部使用，因为其不具备可信任的身份认证能力，不能用于辨别伪造的服务器。 域名验证证书 可以快速进行颁发的入门级SSL证书。对申请人的验证中唯一需要确认的是其对域名的所有权。 完全认证证书...

动态规划（Dynamic programming）通常用来解决最优化问题，在这类问题中，通过做出一组选择来达到最优解。在做出每个选择的同时，通常会生成与原问题形式相同的子问题。当多于一个选择子集都生成相同的子问题时，动态规划技术通常就会很有效，其关键技术就是对每个这样的子问题都保存其解，当重复出现时即可便重复求解。 动态规划与分治方法相似，都是通过组合子问题的解来求解原问题，分治法将问题划分为不相交的子问题，递归地求解子问题，再将它们组合起来求出原问题的解。与之相反，动态规划应用于子问题重叠的情况，即不同的子问题具有公共的子子问题（子问题的求解是递归进行的，将其划分为更小的子子问题）。 实现方法 与朴素递归算法之所以效率很低，是因为它反复求解相同的子问题。因此，动态规划方法仔细安排求解顺序，对每个子问题只求解一次，并将结果保存下来，如果随后再次需要此子问题的解，只需查找保存的结果，而不必重新计算。因此，动态规划方法是通过额外的空间来换取时间，是典型的时空权衡（time-memory trade-off）的例子。并且时间上的节约可能是非常巨大的，可能将一个指数时间的解转化为一个多项式时间的解。动态规划有两种等价的实现方法，分别是带备忘的自顶向下法和自底向上法。 带备忘的自顶向下法(top-down with memoization) 此方法仍按自然的递归形式编写过程，但过程会保存每个子问题的解（通常保存在一个数组或散列表中)。当需要一个子问题的解时，过程首先检查是否已经保存过此解。如果是则直接返回保存的值，从而节省了计算时间，否则，按通常的方式计算这个子问题。 自底向上法(bottom-up method) 这种方法一般需要恰当定义子问题“规模”的概念，使得任何子问题的求解都只依赖于“更小的”子问题的求解。因而可以将子问题按规模排序，按由小至大的顺序进行求解。当求解某个大问题时，它所依赖的那些更小的子问题都已经求解完毕，结果已经保存。么个子问题只需求解一次，当我们求解它时，它所有的前提子问题都已经求解完成。 两种方法得到的算法具有相同的渐进运行时间，仅有的差异是在某些特殊情况下，自顶向下的方法并未真正递归地考察所有可能的子问题。由于没有频繁递归函数调用的开销，自底向上方法的时间复杂度函数通常具有更小的系数。 子问题图 在思考一个动态规划问题时，应该弄清楚所涉及的子问题和子问题之间的依赖关系。问题的子问题图准确第表达了这些信息。它是一个有向图，每个顶点对应一个子问题，若求解子问题x的最优解时需要直接用到子问题y的最优解，那么在子问题图中就有一条从子问题x的顶点到子问题y的顶点的有向边。 自底向上的动态规划方法处理子问题图中顶点的顺序为：对于一个给定的子问题x，在求解它之前求解邻接到它的子问题y。即自底向上动态规划算法是按“逆拓扑序（reserve topological sort）”来处理子问题图中的顶点。类似，可以用“深度优先搜索”来描述自顶向下动态规划算法处理子问题的顺序。

图论问题渗透整个计算机科学，解决图论问题的相关算法对计算机科学领域至关重要。最基本的是对图的遍历与搜索，不过首先要讨论的是如何将图表示为可用的数据结构。 图的表示 算法导论中介绍了图的两种常用表示方法，分别是邻接链表和邻接矩阵，在面向对象编程中，还有一种常用表示方法，即对象和指针（引用），也有称为边列表（edge list）。 根据图的定义，有向图和无向图均由一个顶点集合和这个顶点集合$V$中顶点间是否连接以及是否有向所构成的一个边集合$E$组成，定义图为顶点集和相应边集的二元组\(G = (V, E)\)，对图的三种表示形式只是对这一定义在编程语言或者说是内存中的表示形式。其中对象和指针（边列表）表示方法是最接近原始的定义的，即顶点集合与边集合。 将图的n个顶点使用0到n-1的序号进行编号，下面分别对三种表示方法进行描述，并比较其在如下几个方面的不同： 内存占用 判断两个顶点是否相连(即连接这两个顶点的边是否存在)的时间复杂度 寻找一个顶点的所有邻居顶点 对象指针（边列表） 对象指针 Set<Vertex> vertexSet = new HashSet(); Set<Edge> edgeSet = new HashSet(); Vertex a = new Vertex(0); Vertex b = new Vertex(1); Vertex c = new Vertex(2); Vertex d = new Vertex(3); vertexSet.add(Arrays.asList({})); edgeSet.addAll(Arrays.asList({new Edge(a, b), new Edge(a, c), new Edge(a, d), new Edge(b, a), new Edge(c, a), new Edge(c, d), new Edge(d, a), new Edge(d, c)})); 边列表 边列表中的每个元素表示两个相邻顶点构成的边，其中顶点用其序号给出。 int[][] edgeList = {{0, 1}, {0, 2}, {0, 3}, {1, 0}, {2, 0}, {2, 3}, {3, 0}, {3, 2}}; 邻接链表 邻接链表中第$i$个元素包含与顶点$v[i]$相邻的其它顶点的序号：...

在二叉搜索树的讨论中可以得出各种查询以及插入、删除操作的时间复杂度上界为$O(h)$，其中$h$为树的高度，即树的叶子节点的最大深度。 因此树的高度很大程度上决定了动态集合操作的时间复杂度。对于一个包含确定数量元素的二叉搜索树，我们希望得到一棵较为“平衡”的二叉树，即后代结点能够较均匀分布在一个祖先结点的两颗子树中，这样相对于元素总量，其高度是一个较小的值。因此，可以将平衡的度量认为是树高h与结点总量n的比率$\frac{h}{n}$，即结点对树高的平均贡献率。 考察树的第i层的$k_i$个结点，有： $$ n = \sum\limits_{i=0}^h k_i, \space k_i \leq 2^i $$ 如果树中有大量不平衡的结点，那么每个第i层的结点越少，会导致树高$h$越大。 红黑树及其性质 红黑树是平衡二叉搜索树的一种，可以保证最坏情况下动态集合操作的时间复杂度为$O(\lg n)$，它在每个结点上增加一个存储位来表示结点颜色，可以是RED或BLACK，通过对任一条从根到叶子结点的路径上各个结点的颜色进行约束，可以确保没有一条路径会比其它路径长出2倍，因而是近似于平衡的。 一棵红黑树中的每个结点包含5个属性，color，key，left，right和p，如果一个结点没有子结点或父结点，这改结点相应指针属性的值为NIL，可以把这些NIL视为指向二叉搜索树的叶结点（外部结点）的指针，而把带关键字的结点视为树的内部结点。 一棵红黑树是满足下面红黑性质的二叉搜索树： 每个结点是红色的或黑色的 根结点是黑色的 每个叶结点（NIL）是黑色的 如果一个结点是红色的，则它的两个子结点都是黑色的 对每个结点，从该结点到所有后代叶结点的简单路径上，均包含相同数目的黑色结点 从某个结点x出发(不含该结点)到达一个叶结点的任意一条简单路径上的黑色结点个数称为该结点的黑高(black height)，定义红黑树的黑高为其根结点的黑高。 红黑树动态集合操作 对不修改树的数据结构的操作，如遍历、查询、最大、最小、前驱、后继一类操作对红黑树和普通二叉搜索树都是一样的，对于插入与删除操作，红黑树需要进行额外的变换，不仅改变数据结构，也需要改变结点的颜色以保证红黑树的性质。 旋转 对于数据结构的修改，可以通过旋转来完成，它是能保持二叉搜索树的性质的局部操作。主要有两种旋转方式，分别为左旋和右旋。 插入 首先采用稍作修改的普通二叉搜索树插入方法将新的结点插入到树中，为了保证红黑树的性质，还需要对结点进行着色和旋转操作。 删除 首先采用进行了一定修改的普通的二叉搜索树删除方法将给定结点z从树T中删除，其中需要维持一个结点y为从树中删除的结点或移至树内的结点，并记录y的初始颜色，如果y的初始颜色为黑色，那么需要进行着色和旋转操作来恢复红黑性质。此外还要跟踪移动到结点y原来位置的x结点，因为它也有可能破坏红黑树性质。