golang - RC4源码阅读笔记
文章目录前言库使用RC4算法源码阅读总结前言这学期在上现代密码的课, 掌握常见的几个加解密算法是基本要求, 于是一开始我打算用golang手撸一遍几个常见密码算法, 既可以提高go的熟练度, 又可以加深密码算法的理解, 一举两得, 不过后来想想, 读源码是基本功, 亲自实现算法比较费时间(我现在最缺的就是时间), 所以换了个思路, 把go的源码库的密码算法实现读明白也是一种不错的码力训练.业界不是
前言
这学期在上现代密码的课, 掌握常见的几个加解密算法是基本要求, 于是一开始我打算用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)]
消除边界检查
参考
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
所有评论(0)