基于NFSR和S盒的国产流密码算法Bagua

0x0 Bagua算法简介

流密码算法Bagua是面向5G数据通信、面向硬件设计的密码算法。它是由国内知名密码专家学者谭林、朱宣勇、戚文峰共同设计的密码算法，发表在2020年国际信息安全与密码会议上(Inscrypt 2020)。该算法是基于Galois结构的非线性反馈移位寄存器的同步流密码算法。该算法的设计理念来源于流密码算法Trivium，遵从分组密码算法的“混淆+扩散”的设计原则：Bagua算法由8个非线性反馈移位寄存器(总共有625级寄存器)和一个S盒组成，S盒是8进8出的，起到混淆的作用，8个线性变换起到扩散的作用，每轮S盒和线性变换的输人都是从8个非线性反馈移位寄存器中抽取。Bagua是面向硬件的，根据应用场景可以自主选择1-32拍并行运算，支持128／256比特的密钥长度，初始化向量IV长为128比特。算法分为初始化阶段和工作阶段，初始化阶段的作用是使得密钥充分混淆和扩散，工作阶段开始生成密钥流，密钥流与明文序列异或即得到密文。

0x1 初始化过程

Bagua使用128比特初始向量IV=(v0，v1，…，v127)，并且可以支持128比特和256比特两种长度的密钥。为了统一密钥装载，对于128比特密钥长度的版本，复制这串密钥得到一个256比特的元组，并将其记为K=(k0，k1，…，k255)。

在初始化的过程中，密钥和初始向量是以如下的方式装载的：

当密钥和初始向量装载完成后，对于128／256比特密钥长度的版本，Bagua算法在初始化阶段运行960／1600轮。初始化完成之后，算法进入工作阶段，每拍输出1比特，输出函数定义为：

0x2 状态更新过程

Bagua的主要组件是8个非线性反馈移位寄存器和1个8X8的S盒，将前4个非线性反馈移位寄存器的状态表示为(u313，u312，…，u1)，将后4个非线性反馈移位寄存器的状态表示为(d312，d311，…，d1)。从上到下、从左至右所对应的级数分别为：68、73、79、93和89、87、71、65。8个非线性反馈移位寄存器的更新方式如下：

扩散层的8个线性布尔函数如下所示：

Bagua的混淆层采用的是一个8进8出的可逆S盒，将它记为:

它由4个不同的4进4出的S盒和一个轻量级的线性变换构成。S盒如图所示：

S1和S2的输人分别记为(u281，u211，u136，u55)和(d275，d188，d103，d34)，S3和S4的的输人分别记为(n1，n8，n2，n7)和(n3，n6，n4，n5)。L(x)=L·x表示的是线性变换，其中L是一个8阶二元矩阵，具体表示如下：

从代数的角度来看，8比特的S盒可以看成是一个向量值布尔函数，每个分支的代数正规型的代数次数都是6，项数分别为91项、98项、103项、99项、99项、96项、114项和110项。

Bagua的结构

Bagua的S盒

0x3 密钥流输出过程

初始化过程执行完毕，开始输出密钥流。内部状态每更新1拍，输出1比特的密钥。密钥生成函数如下图：

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