ARTS(09)

1 Algorithm

最小栈
实现一个最小栈,使操作Push, Pop, TopGetMin的时间复杂度都是 $O(1)$。
除了保存元素的数组,还需要增加一个数组,用来保存最小值,其中mins[i]=min(elemens[0:i])

type MinStack struct {
    elements []int
    mins []int
    size int
}
func Constructor() *MinStack {
    return &MinStack {
        elements: make([]int, 0),
        mins : make([]int, 0),
        size: 0,
    }
}
func (m *MinStack) Push(x int) {
    m.elements = append(m.elements, x)
    if m.size == 0 {
        m.mins = append(m.mins, x)
    }else{
        if x > m.mins[m.size-1]{
            m.mins = append(m.mins, m.mins[m.size - 1])
        }else{
            m.mins = append(m.mins, x)
        }
    }
    m.size ++ 
}
func (m *MinStack) Pop(){
    m.size -- 
    m.elements = m.elemens[:m.size]
    m. mins = m.mins[:m.size]
}
func (m *MinStack) Top() int {
    return m.elements[m.size-1]
}
func (m *MinStack) GetMin() int {
    return m.mins[m.size - 1]
}

2 Review

How does HTTPS actually work?
HTTPS是如何工作的?
HTTPS 协议是在标准 HTTP 协议上增加了 SSL/TSL 层,它能够有效的包含你的客户端和服务器之间通信的时候被中间人攻击,保证传输数据的安全性。

2.1 什么是 HTTPS

HTTPS 协议是在 HTTP 协议上,使用加密层,客户端和服务器端仍然使用相同的 HTTP 协议, 而在 SSL 层的终端分别作了加密和解密工作。SSL 层主要有两个目的

  • 确保客户端和服务端连接的对象是各自以为的对象;
  • 确保客户端和服务端发送的内容是各自想要发送的内容。

使用 SSL 层加密最巧妙的一点是:即使发送的内容被中间截获,它也不能解密出发送的内容,获取原始发送方的内容。

2.2 SSL 层连接如何建立

TCP 协议一样,SSL 层连接通过握手的方式创建连接,主要完成以下三个目标

  • 来保证客户端与正确的服务端连接(对服务端而言也是同样的);
  • 保证双方使用的同一套加密解密算法;
  • 双方交换上述的加密解密算法必要的 key;

一旦握手完成,双方开始根据协定好的加密算法发送数据,使用协定好的 key 进行解密。整个过程可分为三个阶段:

  1. Hello: 首先客户端发送类似 ClientHello 消息, 它包含了服务端所需的全部信息,比如多种加密解密算法,支持的最大 SSL 版本号,服务端在接受到消息后, 也会发回类似 ServerHello 消息,它包含的选择的提供的加密算法其中一个和选择使用SSL版本号;
  2. 证书交换: 接下来服务端开始*证明*自己身份,它会发送一个SSL证书,它包含服务端的相关属性和用来验证证书有效期的public key, 客户端既可以隐式的信任这些证书,也可以借助第三方证书机构Certificate Authorities (CAs)来信任这些证书。在其他一些特殊的应用中,服务端也要客户端提供类似证书来保证客户端;
  3. Key 交换:客户端和服务端在发送数据的时候加密和解密使用的是对称加密算法, 也就是用同一个key来进行加密和解密过程。这个用户对称加密的key是通过服务端非对称加密算法提供的public key进行加密,服务端在接收到加密后内容,通过private key进行解密后,获得用于对称加密的key

握手结束后,客户端和服务端知道了连接的是正确对象,接下来就是用约定好的加密算法和加密key对发送和接受的数据进行加密和解密。只有双方知道如何解密全部信息,类似第三方人攻击等截获数据都无法获得真正发送的数据。

2.3 证书

2.3.1 信任

在最底层的,SSL 证书是简单的文本文件,任何都可以创建一个SSL证书来伪造一份服务端的证书。如何这样做的话,上述的全部过程都是无用功。所以有两种可行的方案来保证你信任证书:

  1. 有一系列可信任的整数列表;
  2. 能够证明证书是值得信任的方式。

第一种方案,在浏览器中安装一些从CAs中获取的信任证书;第二种方案似乎可行,通过一些CAs来验证SSL证书的有效性,那么这个就涉及到数字签名。

2.3.2 数字签名

在之前握手的第三阶段,客户端通过附属在证书中public key对接下来对称加密的key进行加密,服务端使用private key进行解密获得key.
反过来也是一样的,一个证书可以被权威机构进行签名, 也就是说权威机构使用private key对证书进行加密,任何客户端使用该机构的public key记性解密,来判断它的结果是否与预期相符合。由于只有权威机构能够使用private key进行加密,也就保证了证书的签名的唯一性。

2.3.3 自签名

既然所有的 CA 的证书都是自签名的,用它来验证其他证书的正确性。这个工作是由所有的浏览器和操作系统的提供商只信任一些机构的CA证书。

2.3.4 该信任谁呢?

SSL 证书是公开的,也就是说任何人都可以拥有它,即是攻击者拥有证书,而且截获了发送给服务端的内容,只要它没有服务端的private key,就不会解密出任何发送的原始内容。但是一旦攻击者拥有证书包含的public key对应的private key,问题就会出现。

2.4 小结

HTTPS并非是无法破解的,目前已经有一些对SSL/TSL层攻击的方法,但是它提供了非常棒的方法来保护发送的数据,尽管其他人看到发送的内容。还有一些细节没有提到,比如:握手消息的数据格式和顺序;加密算法的选择和key的选择,不同加密的参数等等。但是请注意,HTTPS只保证数据发送到目的地是安全的,但是它不保证XSS或者数据库泄露等等。

3 Tips

  • 在软件设计中,开启单独线程起监控服务,需要考虑运行状态宕机的可能性;
  • 在shell命令中,使用Ctrl+Z可以暂停某一项任务;使用bg可以将该任务在后台执行;使用fg + [ID]将任务从后台调度到前台执行。

4 Share

我们为什么要写作,假设我们每天写 500 字的内容,那么一年下来将会写下 18W 字的内容,所以每个人都需要保持写作的习惯。这样才能有效的积累自己的体系。

Comments
Write a Comment