Salsa序列算法分析研究

劉鶯迎

（河南牧業(yè)經(jīng)濟(jì)學(xué)院，鄭州 450001）

1 引言

Salsa20算法屬于序列密碼算法[1]。序列密碼，也稱流密碼，是密碼學(xué)的重要分支，它利用初始密鑰產(chǎn)生一條密鑰流序列，與明文簡單異或進(jìn)行加密。Salsa20算法是歐洲著名密碼計(jì)劃eSTREAM[2]的入選算法。該計(jì)劃旨在征集軟件或者硬件性能優(yōu)于AES的序列密碼算法。Salsa20算法[3]是由美國學(xué)者Daniel J.Bernstein提出的序列密碼算法。于2005年5月提交作為eSTREAM候選算法，同時(shí)提供了算法的速度，安全性分析以及設(shè)計(jì)原則介紹[4]。經(jīng)過三輪的算法評(píng)估，最終Salsa20/12算法成功入選，它在軟件組中排名第二，另外它支持的密鑰長度為256比特或者是128比特（比較傾向于256比特）。

2 算法實(shí)現(xiàn)

Salsa20算法的基本處理單位為32比特字，最基本的函數(shù)為quarterround函數(shù)，采用的運(yùn)算為模232的整數(shù)加法，異或和循環(huán)移位運(yùn)算的復(fù)合，軟件處理速度非常快。Salsa20算法的核心是輸入輸出都是512比特的hash函數(shù)。這512比特輸入以32比特字為單位排成一個(gè)4階方陣，初始矩陣用密鑰，IV，nonce和常數(shù)值進(jìn)行填充。填充后對(duì)該矩陣用quarterround函數(shù)交替進(jìn)行10次列變換和10次行變換，得到的矩陣與原矩陣模232加輸出密鑰流序列。

3 算法混淆效果分析

通過以上對(duì)Salsa20算法結(jié)構(gòu)的介紹以及實(shí)現(xiàn)過程，可以發(fā)現(xiàn)其混淆效果很好。這里通過模擬實(shí)驗(yàn)構(gòu)造所需輸入對(duì)分析一下Salsa20算法的混淆效果究竟如何。為說明Salsa20算法的混淆效果極佳，這里構(gòu)造兩個(gè)輸入矩陣，它們只在一個(gè)字的一個(gè)比特上有差分。并在此基礎(chǔ)上分析這一個(gè)比特在不同位置上所發(fā)生的混淆效果有什么不同。通過模擬實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)，在Salsa20算法的16個(gè)字輸入差分當(dāng)中，僅僅有一個(gè)字存在一個(gè)非零比特，就可以使得三輪輪函數(shù)作用后此非零比特?cái)U(kuò)散到16個(gè)字的所有比特。

在這里把一次運(yùn)算后兩個(gè)狀態(tài)在同一個(gè)位置出現(xiàn)的不同比特記作“活躍比特”。以上只對(duì)輸入差分做了4輪Salsa20算法輪函數(shù)作用，混淆效果就已經(jīng)如此巨大，接下來的16輪輪函數(shù)作用后還將有更多的活躍比特。

4 5輪Salsa20截?cái)嗖罘止?/h2>

本節(jié)考慮的是Paul Crowley等簡化至5輪的Salsa20的截?cái)嗖罘止艏捌涓倪M(jìn)[5][6]，其主要思路是：先是對(duì)n輪差分進(jìn)行反向分析，得到n-2輪差分特征，然后按一定方法對(duì)密鑰進(jìn)行窮舉，以達(dá)到密鑰恢復(fù)的效果。

5 差分鏈的驗(yàn)證與計(jì)算

對(duì)于任何算法，進(jìn)行差分攻擊時(shí)最重要的一步就是尋找高概率差分鏈，這一步往往需要耗費(fèi)很大的資源。根據(jù)ARX密碼的模加差分概率計(jì)算方法[7]，可以對(duì)各論文中出現(xiàn)的3輪差分鏈進(jìn)行理論概率計(jì)算，然后進(jìn)行大數(shù)據(jù)模擬實(shí)驗(yàn)驗(yàn)證差分鏈的輸入輸出正確性和差分概率正確性。

假設(shè)三輪差分鏈表示為以下形式：

6 結(jié)束語

本文對(duì)Salsa20算法進(jìn)行了深入探究，主要工作包括對(duì)Salsa20算法結(jié)構(gòu)的介紹與分析、對(duì)算法特性的分析，對(duì)Salsa20算法的Python語言編程實(shí)現(xiàn)、對(duì)5輪Salsa20算法的差分攻擊，以及對(duì)攻擊算法復(fù)雜度的分析，最后是對(duì)現(xiàn)有差分鏈的驗(yàn)證和差分鏈概率的計(jì)算。

本文主要有以下幾個(gè)重點(diǎn)內(nèi)容：第一點(diǎn)是在深入分析Salsa20算法的各組成函數(shù)以及對(duì)其擴(kuò)展函數(shù)和加密函數(shù)的前提下，對(duì)其進(jìn)行了Python語言的編程實(shí)現(xiàn)以及對(duì)其安全性進(jìn)行了一定的分析。第二點(diǎn)是對(duì)Salsa20算法進(jìn)行了5輪的截?cái)嗖罘止簦▽?duì)差分鏈選擇標(biāo)準(zhǔn)的判斷、在Paul Crowley提出的關(guān)于Salsa20算法差分攻擊的基礎(chǔ)上進(jìn)行了改進(jìn)和優(yōu)化，并且提出了具體的分析算法，同時(shí)進(jìn)行了算法的復(fù)雜度分析。第三點(diǎn)是對(duì)現(xiàn)有差分鏈進(jìn)行了有效的驗(yàn)證，并且對(duì)這些差分鏈進(jìn)行了理論概率的計(jì)算，最后通過模擬實(shí)驗(yàn)判斷了它們是否符合高概率的條件。