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次「下一狀態演算法」中的操作，同時並不輸出金鑰。

下一狀態演算法[編輯]

本節內容使用X_i表示上一狀態的第X個暫存器中的第i位，使用Xⁱ表示當前狀態的第X個暫存器中的第i位，使用i^j表示i、j兩位的邏輯異或，使用i&j表示i、j兩位的邏輯與，使用:=表示賦值。各個暫存器的第一位以1標記。s表示金鑰流。

s:=s+((C₁₀₉&C₁₁₀)^C₁₁₁^C₆₆)^((A₉₁&A₉₂)^A₉₃^A₆₆)^((B₈₂&B₈₃)^B₈₄^B₆₉)

將所有暫存器向右移1位,丟棄最後一位,並將空出的首位按照下述規則填充:

A¹:=A₆₉^((C₁₀₉&C₁₁₀)^C₁₁₁^C₆₆)

B¹:=B₇₈^((A₉₁&A₉₂)^A₉₃^A₆₆)

C¹:=C₈₇^((B₈₂&B₈₃)^B₈₄^B₆₉)

實現[編輯]

下面是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個針對硬件優化的獲勝演算法之一。

連結[編輯]

Trivium在eSTREAM上的介紹（頁面存檔備份，存於互聯網檔案館）
eSTREAM的實現（頁面存檔備份，存於互聯網檔案館）