文章目录

  • 一、加密算法
    • 1. 对称加密
    • 2. 非对称加密
    • 3. 哈希算法
  • 二、数据结构与算法
    • 1. 链表
    • 2. 栈
    • 3. 堆
    • 4. Trie树

一、加密算法

1. 对称加密

加密过程的每一步都是可逆的
加密和解密用的是同一组密钥
异或是最简单的对称加密算法

// XOR 异或运算，要求plain和key的长度相同func XOR(plain string, key []byte) string {bPlain := []byte(plain)bCipher := make([]byte, len(key))for i, k := range key {bCipher[i] = k ^ bPlain[i]}cipher := string(bCipher)return cipher}

DES（Data Encryption Standard）数据加密标准，是目前最为流行的加密算法之一
对原始数据（明文）进行分组，每组64位，最后一组不足64位时按一定规则填充，每一组上单独施加DES算法
DES子密钥生成
初始密钥64位，实际有效位56位，每隔7位有一个校验位，根据初始密钥生成16个48位的子密钥

N取值从1到16，N和x有固定的映射表

DES加密过程

L1, R1 = f(L0, R0, K1)，依此循环，得到L16和R16
S盒替换，输入48位，输出32位，各分为8组，输入每组6位，输出每组4位，分别在每组上施加S盒替换，一共8个S盒

CBC加密过程

分组模式，CBC（Cipher Block Chaining ）密文分组链接模式，将当前明文分组与前一个密文分组进行异或运算，然后再进行加密
其他分组模式还有ECB, CTR, CFR, OFB

func DesEncryptCBC(text string, key []byte) (string, error) {src := []byte(text)block, err := des.NewCipher(key) // 用des创建一个加密器cipherif err != nil {return "", err}blockSize := block.BlockSize() // 分组的大小，blockSize=8src = common.ZeroPadding(src, blockSize) // 填充out := make([]byte, len(src)) // 密文和明文的长度一致encrypter := cipher.NewCBCEncrypter(block, key) // CBC分组模式加密encrypter.CryptBlocks(out, src)return hex.EncodeToString(out), nil}func DesDecryptCBC(text string, key []byte) (string, error) {src, err := hex.DecodeString(text) // 转成[]byteif err != nil {return "", err}block, err := des.NewCipher(key)if err != nil {return "", err} out := make([]byte, len(src)) // 密文和明文的长度一致encrypter := cipher.NewCBCDecrypter(block, key) // CBC分组模式解密encrypter.CryptBlocks(out, src)out = common.ZeroUnPadding(out) // 反填充return string(out), nil}

AES（Advanced Encryption Standard）高级加密标准，旨在取代DES

2. 非对称加密

  • 使用公钥加密，使用私钥解密
  • 公钥和私钥不同
  • 公钥可以公布给所有人
  • 私钥只有自己保存
  • 相比于对称加密，运算速度非常慢

对称加密和非对称加密结合使用的案例：
小明要给小红传输机密文件，他俩先交换各自的公钥，然后：

  • 小明生成一个随机的AES口令，然后用小红的公钥通过RSA加密这个口令，并发给小红
  • 小红用自己的RSA私钥解密得到AES口令
  • 双方使用这个共享的AES口令用AES加密通信

RSA是三个发明人名字的缩写：Ron Rivest，Adi Shamir，Leonard Adleman，密钥越长，越难破解，目前768位的密钥还无法破解（至少没人公开宣布），因此可以认为1024位的RSA密钥基本安全，2048位的密钥极其安全，RSA的算法原理主要用到了数论
RSA加密过程：

  • 随机选择两个不相等的质数p和q：p=61, q=53
  • 计算p和q的乘积n：n=3233
  • 计算n的欧拉函数φ(n) = (p-1)(q-1)： φ(n) =3120
  • 随机选择一个整数e，使得1< e < φ(n)，且e与φ(n) 互质：e=17
  • 计算e对于φ(n)的模反元素d，即求解e*d+ φ(n)*y=1：d=2753, y=-15
  • 将n和e封装成公钥，n和d封装成私钥：公钥=(3233，17)，公钥=(3233，2753)
// RSA加密func RsaEncrypt(origData []byte) ([]byte, error) {// 解密pem格式的公钥block, _ := pem.Decode(publicKey)if block == nil {return nil, errors.New("public key error")}// 解析公钥pubInterface, err := x509.ParsePKIXPublicKey(block.Bytes) // 目前的数字证书一般都是基于ITU（国际电信联盟）制定的X.509标准if err != nil {return nil, err}// 类型断言pub := pubInterface.(*rsa.PublicKey)// 加密return rsa.EncryptPKCS1v15(rand.Reader, pub, origData)}// RSA解密func RsaDecrypt(ciphertext []byte) ([]byte, error) {// 解密block, _ := pem.Decode(privateKey)if block == nil {return nil, errors.New("private key error!")}// 解析PKCS1格式的私钥priv, err := x509.ParsePKCS1PrivateKey(block.Bytes)if err != nil {return nil, err}// 解密return rsa.DecryptPKCS1v15(rand.Reader, priv, ciphertext)}

ECC（Elliptic Curve Cryptography）椭圆曲线加密算法，相比RSA，ECC可以使用更短的密钥，来实现与RSA相当或更高的安全
定义了椭圆曲线上的加法和二倍运算，椭圆曲线依赖的数学难题是：k为正整数，P是椭圆曲线上的点（称为基点）, k*P=Q , 已知Q和P，很难计算出k

func genPrivateKey() (*ecies.PrivateKey, error) {pubkeyCurve := elliptic.P256() // 初始化椭圆曲线// 随机挑选基点,生成私钥p, err := ecdsa.GenerateKey(pubkeyCurve, rand.Reader) // 用golang标准库生成公私钥对if err != nil {return nil, err} else {return ecies.ImportECDSA(p), nil // 转换成以太坊的公私钥对}}// ECCEncrypt 椭圆曲线加密func ECCEncrypt(plain string, pubKey *ecies.PublicKey) ([]byte, error) {src := []byte(plain)return ecies.Encrypt(rand.Reader, pubKey, src, nil, nil)}// ECCDecrypt 椭圆曲线解密func ECCDecrypt(cipher []byte, prvKey *ecies.PrivateKey) (string, error) {if src, err := prvKey.Decrypt(cipher, nil, nil); err != nil {return "", err} else {return string(src), nil}}

3. 哈希算法

哈希函数的基本特征：

  • 输入可以是任意长度
  • 输出是固定长度
  • 根据输入很容易计算出输出
  • 根据输出很难计算出输入（几乎不可能）
  • 两个不同的输入几乎不可能得到相同的输出

SHA（Secure Hash Algorithm） 安全散列算法，是一系列密码散列函数，有多个不同安全等级的版本：SHA-1,SHA-224,SHA-256,SHA-384,SHA-512，其作用是防伪装，防窜扰，保证信息的合法性和完整性
sha-1算法大致过程：

  • 填充，使得数据长度对512求余的结果为448
  • 在信息摘要后面附加64bit，表示原始信息摘要的长度
  • 初始化h0到h4，每个h都是32位
  • h0到h4历经80轮复杂的变换
  • 把h0到h4拼接起来，构成160位，返回
func Sha1(data string) string {sha1 := sha1.New()sha1.Write([]byte(data))return hex.EncodeToString(sha1.Sum(nil))}

MD5（Message-Digest Algorithm 5）信息-摘要算法5，算法流程跟SHA-1大体相似，MD5的输出是128位，比SHA-1短了32位，MD5相对易受密码分析的攻击，但运算速度比SHA-1快

func Md5(data string) string {md5 := md5.New()md5.Write([]byte(data))return hex.EncodeToString(md5.Sum(nil))}

哈希函数的应用场景

  • 用户密码的存储
  • 文件上传/下载完整性校验
  • mysql大字段的快速对比

数字签名


比特币中验证交易记录的真实性用的就是数字签名，先hash再用私钥加密的原因是：非对称加密计算量比较大，先hash可以把原始数据转一条很短的信息，提高计算效率

二、数据结构与算法

1. 链表

链表的一个应用案例，LRU（Least Recently Used，最近最少使用）缓存淘汰的总体思路：缓存的key放到链表中，头部的元素表示最近刚使用

  • 如果命中缓存，从链表中找到对应的key，移到链表头部
  • 如果没命中缓存：
    • 如果缓存容量没超，放入缓存，并把key放到链表头部
    • 如果超出缓存容量，删除链表尾部元素，再把key放到链表头部

ring的应用：基于滑动窗口的统计，比如最近100次接口调用的平均耗时、最近10笔订单的平均值、最近30个交易日股票的最高点；ring的容量即为滑动窗口的大小，把待观察变量按时间顺序不停地写入ring即可

package mainimport ("container/ring""fmt")func TraverseRing(ring *ring.Ring) {// 通过Do()来遍历ring，内部实际上调用了Next()而非Prev()ring.Do(func(i interface{}) {fmt.Printf("%v ", i)})fmt.Println()}func main() {ring := ring.New(5) // 必须指定长度，各元素被初始化为nilring2 := ring.Prev()for i := 0; i < 3; i++ {ring.Value = iring = ring.Next()}for i := 0; i < 3; i++ {ring2.Value = iring2 = ring2.Prev()}TraverseRing(ring)TraverseRing(ring2) // ring和ring2当前所在的指针位置不同，所以遍历出来的顺序也不同}

2. 栈

栈是一种先进后出的数据结构，push把元素压入栈底，pop弹出栈顶的元素，编程语言的编译系统也用到了栈的思想

go自带的List已经包含了栈的功能，这里实现一个线程安全的栈

type (node struct {value interface{}prev*node}MyStack struct {top*nodelength intlock *sync.RWMutex})func NewMyStack() *MyStack {return &MyStack{nil, 0, &sync.RWMutex{}}}func (stack *MyStack) Push(value interface{}) {stack.lock.Lock()defer stack.lock.Unlock()n := &node{value, stack.top}stack.top = nstack.length++}func (stack *MyStack) Pop() interface{} {stack.lock.Lock()defer stack.lock.Unlock()if stack.length == 0 {return nil}n := stack.topstack.top = n.prevstack.length--return n.value}func (stack *MyStack) Peak() interface{} {stack.lock.RLock()defer stack.lock.RUnlock()if stack.length == 0 {return nil}return stack.top.value}func (stack *MyStack) Len() int {return stack.length}func (stack *MyStack) Empty() bool {return stack.Len() == 0}

3. 堆

堆是一棵二叉树，大根堆即任意节点的值都大于等于其子节点，反之为小根堆
用数组来表示堆，下标为 i 的结点的父结点下标为(i-1)/2，其左右子结点分别为 (2i + 1)、(2i + 2)

构建堆

package mainimport "fmt"// AdjustTraingle 如果只是修改slice里的元素，不需要传slice的指针；如果要往slice里append或让slice指向新的子切片，则需要传slice指针func AdjustTraingle(arr []int, parent int) {left := 2 * parent + 1if left >= len(arr) {return}right := 2 * parent + 2minIndex := parentminValue := arr[minIndex]if arr[left] < minValue {minValue = arr[left]minIndex = left}if right < len(arr) {if arr[right] < minValue {minValue = arr[right]minIndex = right}}if minIndex != parent {arr[minIndex], arr[parent] = arr[parent], arr[minIndex]// 递归，每当有元素调整下来时，要对以它为父节点的三角形区域进行调整AdjustTraingle(arr, minIndex)}}func ReverseAdjust(arr []int) {n := len(arr)if n <= 1 {return}lastIndex := n / 2 * 2fmt.Println(lastIndex)// 逆序检查每一个三角形区域for i := lastIndex; i > 0; i -= 2 {right := iparent := (right - 1) / 2fmt.Println(parent)AdjustTraingle(arr, parent)}}func buildHeap() {arr := []int{62, 40, 20, 30, 15, 10, 49}ReverseAdjust(arr)fmt.Println(arr)}

每当有元素调整下来时，要对以它为父节点的三角形区域进行调整

插入元素

删除堆顶

下面讲几个堆的应用
堆排序：

  • 构建堆O(N)
  • 不断地删除堆顶O(NlogN)

求集合中最大的K个元素：

  • 用集合的前K个元素构建小根堆
  • 逐一遍历集合的其他元素，如果比堆顶小直接丢弃；否则替换掉堆顶，然后向下调整堆

把超时的元素从缓存中删除：

  • 按key的到期时间把key插入小根堆中
  • 周期扫描堆顶元素，如果它的到期时间早于当前时刻，则从堆和缓存中删除，然后向下调整堆

Golang中的container/heap实现了小根堆，但需要自己定义一个类，实现以下接口：

  • Len() int
  • Less(i, j int) bool
  • Swap(i, j int)
  • Push(x interface{})
  • Pop() x interface{}
type Item struct {Valuestringpriority int // 优先级，数字越大，优先级越高}type PriorityQueue []*Itemfunc (pq PriorityQueue) Len() int {return len(pq)}func (pq PriorityQueue) Less(i, j int) bool {// Golang默认提供的是小根堆，而优先队列是大根堆，所以这里要反着定义Lessreturn pq[i].priority > pq[j].priority}func (pq PriorityQueue) Swap(i, j int) {pq[i], pq[j] = pq[j], pq[i]}// 往slice里append，需要传slice指针func (pq *PriorityQueue) Push(x interface{}) {item := x.(*Item)*pq = append(*pq, item)}// 让slice指向新的子切片，需要传slice指针func (pq *PriorityQueue) Pop() interface{} {old := *pqn := len(old)item := old[n-1] // 数组最后一个元素*pq = old[0 : n-1] // 去掉最一个元素return item}

4. Trie树

Trie树又叫字典权
现有term集合：{分散，分散精力，分散投资，分布式，工程，工程师}，把它们放到Trie树里如下图：

Trie树的根节点是总入口，不存储字符；对于英文，第个节点有26个子节点，子节点可以存到数组里；中文由于汉字很多，用数组存子节点太浪费内存，可以用map存子节点；从根节点到叶节点的完整路径是一个term，从根节点到某个中间节点也可能是一个term，即一个term可能是另一个term的前缀；上图中红圈表示从根节点到本节点是一个完整的term

package mainimport "fmt"type TrieNode struct {Word rune // 当前节点存储的字符。byte只能表示英文字符，rune可以表示任意字符Children map[rune]*TrieNode // 孩子节点，用一个map存储Term string}type TrieTree struct {root *TrieNode}// add 把words[beginIndex:]插入到Trie树中func (node *TrieNode) add(words []rune, term string, beginIndex int) {// words已经遍历完了if beginIndex >= len(words) {node.Term = termreturn}if node.Children == nil {node.Children = make(map[rune]*TrieNode)}word := words[beginIndex] // 把这个word放到node的子节点中if child, exists := node.Children[word]; !exists {newNode := &TrieNode{Word: word}node.Children[word] = newNodenewNode.add(words, term, beginIndex+1) // 递归} else {child.add(words, term, beginIndex+1) // 递归}}// walk words[0]就是当前节点上存储的字符，按照words的指引顺着树往下走，最终返回words最后一个字符对应的节点func (node *TrieNode) walk(words []rune, beginIndex int) *TrieNode {if beginIndex == len(words)-1 {return node}beginIndex += 1word := words[beginIndex]if child, exists := node.Children[word]; exists {return child.walk(words, beginIndex)} else {return nil}}// traverseTerms 遍历一个node下面所有的term，注意要传数组的指针，才能真正修改这个数组func (node *TrieNode) traverseTerms(terms *[]string) {if len(node.Term) > 0 {*terms = append(*terms, node.Term)}for _, child := range node.Children {child.traverseTerms(terms)}}func (tree *TrieTree) AddTerm(term string) {if len(term) <= 1 {return}words := []rune(term)if tree.root == nil {tree.root = new(TrieNode)}tree.root.add(words, term, 0)}func (tree *TrieTree) Retrieve(prefix string) []string {if tree.root == nil || len(tree.root.Children) == 0 {return nil}words := []rune(prefix)firstWord := words[0]if child, exists := tree.root.Children[firstWord]; exists {end := child.walk(words, 0)if end == nil {return nil} else {terms := make([]string, 0, 100)end.traverseTerms(&terms)return terms}} else {return nil}}func main() {tree := new(TrieTree)tree.AddTerm("分散")tree.AddTerm("分散精力")tree.AddTerm("分散投资")tree.AddTerm("分布式")tree.AddTerm("工程")tree.AddTerm("工程师")terms := tree.Retrieve("分散")fmt.Println(terms)terms = tree.Retrieve("人工")fmt.Println(terms)}