前言

这学期在上现代密码的课, 掌握常见的几个加解密算法是基本要求, 于是一开始我打算用golang手撸一遍几个常见密码算法, 既可以提高go的熟练度, 又可以加深密码算法的理解, 一举两得, 不过后来想想, 读源码是基本功, 亲自实现算法比较费时间(我现在最缺的就是时间), 所以换了个思路, 把go的源码库的密码算法实现读明白也是一种不错的码力训练.
业界不是默认提高代码能力最快的方法是读优秀的开源代码么, 所以这个决定应该不会太差(虽然没有亲自写代码体会更深刻); 我的一个师兄花了3个月把Hadoop的30w行代码读了一遍, 还写了个几万行的系统, 突然感觉代码能力训练确实不能偷工减料啊…

库使用

先直观感受一下RC4包的使用

package main

import (
	"crypto/rc4"
	"fmt"
)

func main() {
	key := []byte("RC4_key")
	plaintext := []byte("data_should_be_array_of_bytes")

	// encryption
	ciphertext := make([]byte, len(plaintext))
	fmt.Printf("plaintext:%s \n", plaintext)
	cipher1, _ := rc4.NewCipher(key)
	cipher1.XORKeyStream(ciphertext, plaintext)
	fmt.Printf("ciphertext:%s \n", ciphertext)

	// decryption
	plaintext_dec := make([]byte, len(ciphertext))
	cipher2, _ := rc4.NewCipher(key) // remember to new a cipher for the same initial
	cipher2.XORKeyStream(plaintext_dec, ciphertext)
	fmt.Printf("plaintext decrypted:%s \n", plaintext_dec)
}

RC4算法

RC4一种流密码算法, 起初是1987, Ron Rivest为了RSA security设计的非公开算法, 后来1994年, 算法被匿名上传到互联网被迫转为公开算法.
RC4的实现其实很简单
先看符号表

符号	意义
K	可变长key
S	state vector用于置换bit
T	temporary vector由K生成

初始化, S的元素按递增顺序排列, T由K生成, 不足的部分用K循环填充

/* Initialization */
for i = 0 to 255 do
	S[i] = i;
	T[i] = K[i mod keylen];

S的初始化, 用T的元素对S的元素进行伪随机化

/* Initial Permutation of S */
j = 0;
for i = 0 to 255 do
	j = (j + S[i] + T[i]) mod 256;
	Swap (S[i], S[j]);

流密钥生成, 这里的k是用于和下一个plaintext的byte异或或者用于和下一个ciphertext的byte异或的密钥, 逐字节异或就是加解密

/* Stream Generation */
i, j = 0;
while (true)
	i = (i + 1) mod 256;
	j = (j + S[i]) mod 256;
	Swap (S[i], S[j]);
	t = (S[i] + S[j]) mod 256;
	k = S[t];

源码阅读

源码参考
https://cs.opensource.google/go/go/+/refs/tags/go1.17.2:src/crypto/rc4/rc4.go

Cipher结构, 主要是256uint32类型的数组保存s, 以及uint8类型的i, j作为数组下标用于permutation操作

// A Cipher is an instance of RC4 using a particular key.
type Cipher struct {
	s    [256]uint32
	i, j uint8
}

创建函数, 先判断key长度是否符合要求范围1-256, 然后是初始化s, 循环使用key对s进行伪随机化(位置换), 这里没有直接mod 256, 但是是利用变量类型进行mod 256, uint8(c.s[i]) + key[i%k]是对uint8类型进行计算的, 所以进位会被忽略掉, 自然实现了mod 256. return的类型是*Cipher是指向Cipher结构的指针, 所以return &c.
此外, swap的功能直接跟python一样, 连续赋值实现(是这么叫叭大概)
c.s[i], c.s[j] = c.s[j], c.s[i]

// NewCipher creates and returns a new Cipher. The key argument should be the
// RC4 key, at least 1 byte and at most 256 bytes.
func NewCipher(key []byte) (*Cipher, error) {
	k := len(key)
	if k < 1 || k > 256 {
		return nil, KeySizeError(k)
	}
	var c Cipher
	for i := 0; i < 256; i++ {
		c.s[i] = uint32(i)
	}
	var j uint8 = 0
	for i := 0; i < 256; i++ {
		j += uint8(c.s[i]) + key[i%k]
		c.s[i], c.s[j] = c.s[j], c.s[i]
	}
	return &c, nil
}

reset函数, 将s数组每个元素和i, j都赋值为0
而且注释里说了, reset不保证key从内存中抹去(这里会有安全性问题么?..

// Reset zeros the key data and makes the Cipher unusable.
//
// Deprecated: Reset can't guarantee that the key will be entirely removed from
// the process's memory.
func (c *Cipher) Reset() {
	for i := range c.s {
		c.s[i] = 0
	}
	c.i, c.j = 0, 0
}

XORkeystream函数, 函数接收的都是[]byte类型参数
先处理边界, src == 0则直接返回, 然后用subtle.inexactOverlap()查看buffer内存是否合理

// XORKeyStream sets dst to the result of XORing src with the key stream.
// Dst and src must overlap entirely or not at all.
func (c *Cipher) XORKeyStream(dst, src []byte) {
	if len(src) == 0 {
		return
	}
	if subtle.InexactOverlap(dst[:len(src)], src) {
		panic("crypto/rc4: invalid buffer overlap")
	}
	i, j := c.i, c.j
	_ = dst[len(src)-1]
	dst = dst[:len(src)] // eliminate bounds check from loop
	for k, v := range src {
		i += 1
		x := c.s[i]
		j += uint8(x)
		y := c.s[j]
		c.s[i], c.s[j] = y, x
		dst[k] = v ^ uint8(c.s[uint8(x+y)])
	}
	c.i, c.j = i, j
}

这里用了个_ = dst[len(src)-1]确定dst数组的长大于等于src, dst = dst[:len(src)]然后将dst缩为src的长, 省掉边界检测(一个小trick). 之后这一段, 就是按流key生成结合按 byte 异或 src 得到 dst

	for k, v := range src {
		i += 1
		x := c.s[i]
		j += uint8(x)
		y := c.s[j]
		c.s[i], c.s[j] = y, x
		dst[k] = v ^ uint8(c.s[uint8(x+y)])
	}

对比一下理论算法

/* Stream Generation */
i, j = 0;
while (true)
	i = (i + 1) mod 256;
	j = (j + S[i]) mod 256;
	Swap (S[i], S[j]);
	t = (S[i] + S[j]) mod 256;
	k = S[t];

最后两行的实现, 源码中用一行完成了
c.s[uint8(x+y)]即S[(S[i] + S[j]) mod 256], 生成当前byte的key, 然后直接和src的当前byte, 也就是v异或然后赋值给dst的当前byte, 完成当前byte的加(解)密

另外, 看看subtle的函数, 这里会调用unsafe模块, 涉及到内存检查的接口, 大概意思是检查内存下标是否合理

// InexactOverlap reports whether x and y share memory at any non-corresponding
// index. The memory beyond the slice length is ignored. Note that x and y can
// have different lengths and still not have any inexact overlap.
//
// InexactOverlap can be used to implement the requirements of the crypto/cipher
// AEAD, Block, BlockMode and Stream interfaces.
func InexactOverlap(x, y []byte) bool {
	if len(x) == 0 || len(y) == 0 || &x[0] == &y[0] {
		return false
	}
	return AnyOverlap(x, y)
}

总结

这样源码就读完了, RC4总体来说不算复杂, go的库实现也用到了一些tricks
(1) mod 256, 可以用uint8类型的计算来替代
(2) swap, 可以连续赋值实现
(3) 用_ = dst[len(src) - 1]判断dst的长度是否>=src
(4) 用 dst = dst[:len(src)]消除边界检查

参考

cryptography and network security 5th