基于LFSR和NFSR的流密码算法Grain v1

0x0简介

Grain算法是由瑞典的 Hell,Johansson 和瑞士的 Meier 共同设计的一种面向硬件实现的流密码算法。Grain算法面向硬件实现，具有运行速度快、安全性高、灵活输出密钥流等优点，并已成为eSTREAM(欧洲流密码算法计划)的７个优胜算法之一。

Grain算法共有三个版本：Grain v0、Grain v1和Grain-128，这三个版本的结构基本相同，其中Grain v0和Grain v1的LFSR和NFSR均为80位，内部状态变量为160位；而Grain-128的LFSR和NFSR均为128位，其内部状态变量为256位。本文介绍到的是Grain v1算法。

0x1 Grain v1算法模型

Grain v1算法面向比特，其密钥K长度为80比特，表示为(k0，k1，...，k79)，初始向量IV长度为64比特，表示为(IV0，IV1，...，IV63)。Grain v1结构由三个部分组成，包括线性反馈移位寄存器LFSR、非线性反馈移位寄存器NFSR和非线性布尔过滤函数h(x)，其中LFSR表示为(s0，s1，...．，s78，s79)，NFSR表示为(b0，b1，...b78，b79)。LFSR的更新函数f(x)和NFSR的更新函数g(x)以及过滤函数h(x)和密钥流输出函数表示如下所示：

0x1.1 LFSR

0x1.2 NFSR

0x1.3 过滤函数

0x1.4 密钥流输出函数

0x2初始化(不输出密钥)

把80bit的密钥Ｋ＝（k0,k1,...,k79）依次填充到NFSR的内部状态；把64bit的初始量IV＝(iv0,iv1,...,iv63)填充到LFSR的前64位，而LFSR的后16位用全1填充。然后运行160轮，将得到的密钥流比特反作用于两个移位寄存器的更新，最终完成初始化阶段。

Grain v1算法初始化结构图

0x3密钥生成(输出密钥)

算法初始化过程执行完毕之后，每更新一轮，输出1bit的密钥。具体实现过程如下图所示。

Grain v1算法密钥输出结构图

[招生]科锐逆向工程师培训(2024年11月15日实地，远程教学同时开班, 第51期)