序列密码(Trivium)

❝
出师一表真名世，千载谁堪伯仲间！-- 陆游
❞

$QS_{D}QCZ6HFL1Y[{(B7AZG.jpg$

Trivium

❝
Trivium密码是一种对称密钥同步序列密码算法。它的设计目的是在计算能力有限的硬件上高效实现安全加密，同时兼顾软件实现效率。
❞

Trivium加密过程(此图参考自深入浅出密码学一书)

1W`8%DEJLXOAD4[L2`Q%DX0.png

加密过程

初始化

将80位的密钥key放到寄存器A前面80位
将80位的初始化向量iv放到寄存器B前面80位
除了放置密钥的位和寄存器C最后3位，所有寄存器其余位置置0

热身阶段

在这一个阶段，循环 4 * 288 = 1152 次密钥生成算法（注：这一阶段不进行任何输出）, 其目的是为了充分随机化密码，也确保密钥序列同时取决于k和IV。

加密阶段

后续就可以连续调用密钥生成算法，也就是说从1153位开始生成的stream，即可作为密钥序列。

密钥流生成算法

for i = 1 to N do
    t1 ← s66 + s93
    t2 ← s162 + s177
    t3 ← s243 + s288
    zi ← t1 + t2 + t3
    t1 ← t1 + s91 · s92 + s171
    t2 ← t2 + s175 · s176 + s264
    t3 ← t3 + s286 · s287 + s69
    (s1, s2, . . . , s93) ← (t3, s1, . . . , s92)
    (s94, s95, . . . , s177) ← (t1, s94, . . . , s176)
    (s178, s279, . . . , s288) ← (t2, s178, . . . , s287)
end for

需要注意，这里的运算都是基于GF(2)上的运算。

算法实现

依然采用Rust实现

use std::iter::repeat;
pub struct Trivium {
    lfsr_a: [u32; 3],
    lfsr_b: [u32; 3],
    lfsr_c: [u32; 4],
}
fn u8to32_be(p: &[u8; 4]) -> u32 {
    return ((p[0] as u32) << 24 | ((p[1] as u32) << 16) | ((p[2] as u32) << 8) | p[3] as u32) as u32;
}
fn revert_u32(p: u32) -> u32 {
    return p << 24 | ((p << 8) & 0x00ff0000) | ((p >> 8) & 0x0000ff00) | p >> 24;
}
fn s64(p: &[u32], b: u32) -> u32 {
    return p[1] << (b - 64) | p[2] >> (96 - b);
}
fn s96(p: &[u32], b: u32) -> u32 {
    return p[2] << (b - 96) | p[3] >> (128 - b);
}
fn rotate_lfsr_3(p: &mut [u32; 3], t: u32) {
    p[2] = p[1];
    p[1] = p[0];
    p[0] = t;
}
fn rotate_lfsr_4(p: &mut [u32; 4], t: u32) {
    p[3] = p[2];
    p[2] = p[1];
    p[1] = p[0];
    p[0] = t;
}
impl Trivium {
    pub fn init(key: [u8; 10], iv: [u8; 10]) -> Trivium {
        let mut trivium = Trivium {
            lfsr_a: [0; 3],
            lfsr_b: [0; 3],
            lfsr_c: [0; 4],
        };
        trivium.lfsr_a[0] = u8to32_be(&[key[0], key[1], key[2], key[3]]);
        trivium.lfsr_a[1] = u8to32_be(&[key[4], key[5], key[6], key[7]]);
        trivium.lfsr_a[2] = u8to32_be(&[key[8], key[9], 0, 0]);
        trivium.lfsr_b[0] = u8to32_be(&[iv[0], iv[1], iv[2], iv[3]]);
        trivium.lfsr_b[1] = u8to32_be(&[iv[4], iv[5], iv[6], iv[7]]);
        trivium.lfsr_b[2] = u8to32_be(&[iv[8], iv[9], 0, 0]);
        trivium.lfsr_c[0] = 0;
        trivium.lfsr_c[1] = 0;
        trivium.lfsr_c[2] = 0;
        trivium.lfsr_c[3] = 0x000e0000;
        // Initialization: 1142
        for _ in 0..36 {
            let mut t1 = s64(&trivium.lfsr_a, 66) ^ s64(&trivium.lfsr_a, 93);
            let mut t2 = s64(&trivium.lfsr_b, 69) ^ s64(&trivium.lfsr_b, 84);
            let mut t3 = s64(&trivium.lfsr_c, 66) ^ s96(&trivium.lfsr_c, 111);
            t1 ^= (s64(&trivium.lfsr_a, 91) & s64(&trivium.lfsr_a, 92)) ^ s64(&trivium.lfsr_b, 78);
            t2 ^= (s64(&trivium.lfsr_b, 82) & s64(&trivium.lfsr_b, 83)) ^ s64(&trivium.lfsr_c, 87);
            t3 ^= (s96(&trivium.lfsr_c, 109) & s96(&trivium.lfsr_c, 110)) ^ s64(&trivium.lfsr_a, 69);
            // Rotate LFSRs
            rotate_lfsr_3(&mut trivium.lfsr_a, t3);
            rotate_lfsr_3(&mut trivium.lfsr_b, t1);
            rotate_lfsr_4(&mut trivium.lfsr_c, t2);
        }
        return trivium;
    }
    fn generate_key_stream(&mut self, output: &mut [u32]) {
        for i in output.iter_mut() {
            let mut t1 = s64(&self.lfsr_a, 66) ^ s64(&self.lfsr_a, 93);
            let mut t2 = s64(&self.lfsr_b, 69) ^ s64(&self.lfsr_b, 84);
            let mut t3 = s64(&self.lfsr_c, 66) ^ s96(&self.lfsr_c, 111);
            *i = revert_u32(t1 ^ t2 ^ t3);
            t1 ^= (s64(&self.lfsr_a, 91) & s64(&self.lfsr_a, 92)) ^ s64(&self.lfsr_b, 78);
            t2 ^= (s64(&self.lfsr_b, 82) & s64(&self.lfsr_b, 83)) ^ s64(&self.lfsr_c, 87);
            t3 ^= (s96(&self.lfsr_c, 109) & s96(&self.lfsr_c, 110)) ^ s64(&self.lfsr_a, 69);
            // Rotate LFSRs
            rotate_lfsr_3(&mut self.lfsr_a, t3);
            rotate_lfsr_3(&mut self.lfsr_b, t1);
            rotate_lfsr_4(&mut self.lfsr_c, t2);
        }
    }
    fn crypt(&mut self, input: &[u8], output: &mut [u8]) {
        let mut key_stream: Vec<u32> = repeat(0).take(output.len() / 4 + 1).collect();
        self.generate_key_stream(&mut key_stream);
        for (i, (j, k)) in input.iter().zip(output.iter_mut()).enumerate() {
            *k = *j ^ (match i % 4 {
                0 => key_stream[i / 4] >> 24,
                1 => key_stream[i / 4] >> 16,
                2 => key_stream[i / 4] >> 8,
                3 => key_stream[i / 4],
                _ => panic!() // 正常应该不会匹配到这里，但是吧这个不写编译不过，也许会有更优雅的方案。
            }) as u8;
        }
    }
}
#[cfg(test)]
mod tests {
    use crate::trivium::{Trivium};
    use std::iter::repeat;
    #[test]
    fn test() {
        let mut trivium = Trivium::init([0; 10], [255; 10]);
        let plaintext = "plaintext";
        let mut result: Vec<u8> = repeat(0).take(plaintext.len()).collect();
        trivium.crypt(plaintext.as_bytes(), &mut result);
        println!("{:?}", result);
        let mut trivium = Trivium::init([0; 10], [255; 10]);
        let mut output: Vec<u8> = repeat(0).take(plaintext.len()).collect();
        trivium.crypt(&result, &mut output);
        println!("{:?}", output);
    }
}

❝
代码仅供参考学习使用(简单的实现)，未经过严格测试，请不要直接用于生产用途，避免造成损失
❞

算法应用

Trivium算法在设计之初就是完全出于硬件效率考虑。由于采用了线性反馈移位寄存器和简单的AND函数，其硬件实现效率很高。下面来具体应用一下这个算法，看一下编译之后这个算法有什么特征，下面写一个简单的例子，这里采取ndk的实现，所以先来用c++实现一下Trivium算法吧，代码写的比较low, 请大佬们海涵。

#define HIGH_MASK 0xFFFF0000
uint32_t u8to32(const uint8_t *p) {
    return (p[0] << 24) | (p[1] << 16) | (p[2] << 8) | p[3];
}
uint32_t revert_u32(uint32_t p) {
    return p << 24 | ((p << 8) & 0x00ff0000) | ((p >> 8) & 0x0000ff00) | p >> 24;
}
uint32_t s64(uint32_t *p, int b) {
    return p[1] << (b - 64) | p[2] >> (96 - b);
}
uint32_t s96(uint32_t *p, int b) {
    return p[2] << (b - 96) | p[3] >> (128 - b);
}
void rotate_lfsr_3(uint32_t *p, int t) {
    p[2] = p[1];
    p[1] = p[0];
    p[0] = t;
}
void rotate_lfsr_4(uint32_t *p, int t) {
    p[3] = p[2];
    p[2] = p[1];
    p[1] = p[0];
    p[0] = t;
}
Trivium::Trivium(uint8_t *key, uint8_t *iv) {
    this->lfsr_a[0] = u8to32(key);
    this->lfsr_a[1] = u8to32(key + 4);
    this->lfsr_a[2] = u8to32(key + 8) & HIGH_MASK;
    this->lfsr_b[0] = u8to32(iv);
    this->lfsr_b[1] = u8to32(iv + 4);
    this->lfsr_b[2] = u8to32(iv + 8) & HIGH_MASK;
    this->lfsr_c[0] = 0;
    this->lfsr_c[1] = 0;
    this->lfsr_c[2] = 0;
    this->lfsr_c[3] = 0x000E0000;
    // Initialization: 1142
    for (int i = 0; i < 36; ++i) {
        this->generateKeyStream();
    }
}
uint32_t Trivium::generateKeyStream() {
    uint32_t t1, t2, t3, output;
    t1 = s64(this->lfsr_a, 66) ^ s64(this->lfsr_a, 93);
    t2 = s64(this->lfsr_b, 69) ^ s64(this->lfsr_b, 84);
    t3 = s64(this->lfsr_c, 66) ^ s96(this->lfsr_c, 111);
    output = revert_u32(t1 ^ t2 ^ t3);
    t1 ^= (s64(this->lfsr_a, 91) & s64(this->lfsr_a, 92)) ^ s64(this->lfsr_b, 78);
    t2 ^= (s64(this->lfsr_b, 82) & s64(this->lfsr_b, 83)) ^ s64(this->lfsr_c, 87);
    t3 ^= (s96(this->lfsr_c, 109) & s96(this->lfsr_c, 110)) ^ s64(this->lfsr_a, 69);
    rotate_lfsr_3(this->lfsr_a, t3);
    rotate_lfsr_3(this->lfsr_b, t1);
    rotate_lfsr_4(this->lfsr_c, t2);
    return output;
}
void Trivium::encrypt(char *input, char output[]) {
    size_t count = ceil(strlen(input) / 4.0);
    int ptr = 0;
    for (int i = 0; i < count; ++i) {
        uint32_t stream = this->generateKeyStream();
        output[ptr] = input[ptr] ^ (stream >> 24);
        output[ptr + 1] = input[ptr + 1] ^ (stream >> 16);
        output[ptr + 2] = input[ptr + 2] ^ (stream >> 8);
        output[ptr + 3] = input[ptr + 3] ^ stream;
        ptr += 4;
    }
}

然后简单实现一个jni的方法，这里我偷懒了，没有对密钥长度和初始化向量的长度进行一个校验，这里要求是80bit。

extern "C"
JNIEXPORT jbyteArray JNICALL
Java_com_littleq_cryptography_MainActivity_trivium(
        JNIEnv *env,
        jobject thiz,
        jbyteArray key,
        jbyteArray iv,
        jbyteArray content) {
    size_t key_size = env->GetArrayLength(key);
    size_t iv_size = env->GetArrayLength(iv);
    size_t content_size = env->GetArrayLength(content);
    auto *key_dst = (jbyte *) malloc(key_size * sizeof(jbyte));
    auto *iv_dst = (jbyte *) malloc(iv_size * sizeof(jbyte));
    auto *content_dst = (jbyte *) malloc(content_size * sizeof(jbyte));
    env->GetByteArrayRegion(key, 0, key_size, key_dst);
    env->GetByteArrayRegion(iv, 0, iv_size, iv_dst);
    env->GetByteArrayRegion(content, 0, content_size, content_dst);
    uint8_t _key[10] = {0};
    uint8_t _iv[10] = {0};
    for (int i = 0; i < key_size; ++i) {
        _key[i] = key_dst[i];
        _iv[i] = iv_dst[i];
    }
    auto *trivium = new Trivium(_key, _iv);
    char output[9] = {0};
    trivium->encrypt(reinterpret_cast<char *>(content_dst), output);
    jbyteArray byteArray = env->NewByteArray(content_size);
    env->SetByteArrayRegion(byteArray, 0, content_size, (jbyte *) output);
    return byteArray;
}

Java 层代码如下, 这里仅仅贴出核心的代码：

public class MainActivity extends AppCompatActivity {
    // ...
    @Override
    protected void onCreate(Bundle savedInstanceState) {
        // ...
        byte[] key = new byte[]{0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0};
        byte[] iv = new byte[]{-1, -1, -1, -1, -1, -1, -1, -1, -1, -1};
        byte[] output = this.trivium(key, iv, "plaintext".getBytes());
        for (byte b : output) {
            Log.i("LQ", String.valueOf(b & 0xFF)); // 输出一下结果
        }
    }
    public native byte[] trivium(byte[] key, byte[] iv, byte[] content);
}