Trivium (密码) - 维基百科,自由的百科全书
Trivium密码是一种对称密钥同步序列密码算法。它的设计目的是在计算能力有限的硬件上高效实现安全加密,同时兼顾软件实现效率。
结构
[编辑]Trivium的标准输入为一个80位的密码和一个80位的起始向量(IV)。和大部分同步序列密码算法一样,Trivium的核心组件是一个密码学安全的伪随机数生成器(CSPRNG)。通过将密码和起始向量加载到该伪随机数生成器中,Trivium算法将计算出所需的密钥流。然后,通过将明文位依次与密文位进行异或操作,计算并输出密文。
Trivium伪随机数生成器可以看作由三个线性反馈移位寄存器组成。它们的长度分别是93、84和111位。寄存器和寄存器之间通过非线性逻辑连接。通过Trivium加密共分为2个阶段。
热身阶段
[编辑]- 将80位的密钥加载到寄存器A的左边,并将寄存器A的剩余位以0填充。
- 将80位的IV加载到寄存器B的左边,并将寄存器B的剩余位以0填充。
- 将寄存器C的最后三位以1填充,并将寄存器C的剩余位以0填充。
- 重复1152次“下一状态算法”中的操作,同时并不输出密钥。
下一状态算法
[编辑]本节内容使用Xi表示上一状态的第X个寄存器中的第i位,使用Xi表示当前状态的第X个寄存器中的第i位,使用i^j表示i、j两位的逻辑异或,使用i&j表示i、j两位的逻辑与,使用:=表示赋值。各个寄存器的第一位以1标记。s表示密钥流。
s:=s+((C109&C110)^C111^C66)^((A91&A92)^A93^A66)^((B82&B83)^B84^B69)
将所有寄存器向右移1位,丢弃最后一位,并将空出的首位按照下述规则填充:
- A1:=A69^((C109&C110)^C111^C66)
- B1:=B78^((A91&A92)^A93^A66)
- C1:=C87^((B82&B83)^B84^B69)
实现
[编辑]下面是Trivium使用的CSPRNG的typescript实现(這是CSPRNG部分,而不是整個密碼):
type Bit = 0|1 type Register = Bit[] /** * @param p 长为80的数组,每个元素为0或1 * @param iv 长为80的数组,每个元素为0或1 * @param l 正常数字,表示希望函数生成的密钥流的长度 */ function getKeyStream(p: Register, iv: Register, l: number): Register { l=l+1152; const a:Register=[], b:Register=[], c:Register=[], k:Register=[]; for(let i=0;i<80;i++) { a[i]=p[i]; } for(let i=80;i<93;i++) { a[i]=0; } for(let i=0;i<80;i++) { b[i]=iv[i]; } for(let i=80;i<84;i++) { b[i]=0; } for(let i=0;i<108;i++) { c[i]=0; } for(let i=108;i<111;i++) { c[i]=1; } for(let i=0;i<l;i++) { const ra=mod2((a[90]&a[91])+a[92]+a[65]); const rb=mod2((b[81]&b[82])+b[83]+b[68]); const rc=mod2((c[108]&c[109])+c[110]+c[65]); k[i]=mod2(ra+rb+rc); const ia=mod2(a[68]+rc); const ib=mod2(b[77]+ra); const ic=mod2(c[86]+rb); rightShift(a,ia); rightShift(b,ib); rightShift(c,ic); } return subArray(k,1152); } function mod2(x: number): Bit { return x%2 as Bit } function rightShift(reg: Register, incoming: Bit): Register { let l=reg.length-1; if(l<0){return reg;} for (let i=l; i>0; i--) { reg[i]=reg[i-1]; } reg[0]=incoming; return reg; } function subArray(arr_in: Register, a: number): Register { var arr_out: Register = []; for (let i=a; i<arr_in.length; i++) { arr_out[i-a]=arr_in[i]; } return arr_out; }
使用全零的密鑰和一全零向量的輸入后,其生成的前100位密碼學安全的僞隨機數是:
1101011000111011001100010001100000010000011010101100000110010001100011000110110101010101011000010000
性能
[编辑]Trivium算法在設計之初就是完全出於硬件效率考慮。由於采用了綫性反饋移位寄存器和簡單的AND函數,其硬件實現效率很高。然而,針對位的密集操作導致其軟件實現效率低下。
地位
[编辑]歐洲eSTREAM計劃的獲勝算法共7個,其中3個針對硬件優化,4個針對軟件優化。Trivium是3個針對硬件優化的獲勝算法之一。