密碼學系列之:加密貨币中的scrypt算法

​​簡介​​

​​scrypt算法​​

​​scrypt算法詳解​​

​​scrypt的使用​​

簡介

為了抵禦密碼破解，科學家們想出了很多種方法，比如對密碼進行混淆加鹽操作，對密碼進行模式變換群組合。但是這些算法逐漸被一些特制的ASIC處理器打敗，這些ASIC處理器不做别的，就是專門來破解你的密碼或者進行hash運算。

最有名的當然是比特币了，它使用的是為人诟病的POW算法，誰的算力高，誰就可以挖礦，這樣就導緻了大量無意義的礦機的産生，這些礦機什麼都不能幹，就算是用來算hash值。結果浪費了大量的電力。

普通人更是别想加入這個隻有巨頭才能擁有的賽道，如果你想用一個普通的PC機來挖礦，那麼我估計你挖到礦的幾率可能跟被隕石砸中差不多。

為了抵禦這種CPU為主的密碼加密方式，科學家們發明了很多其他的算法，比如需要占用大量記憶體的算法，因為記憶體不像CPU可以瘋狂提速，是以限制了很多暴力破解的場景，今天要将的scrypt算法就是其中一種，該算法被應用到很多新的加密貨币挖礦體系中，用以表示他們挖礦程式的公平性。

scrypt算法

scrypt是一種密碼衍生算法，它是由Colin Percival建立的。使用scrypt算法來生成衍生key，需要用到大量的記憶體。scrypt算法在2016年作為RFC 7914标準釋出。

密碼衍生算法主要作用就是根據初始化的主密碼來生成系列的衍生密碼。這種算法主要是為了抵禦暴力破解的攻擊。通過增加密碼生成的複雜度，同時也增加了暴力破解的難度。

但是和上面提到的原因一樣，之前的password-based KDF，比如PBKDF2雖然提高了密碼生成的周遊次數，但是它使用了很少的記憶體空間。是以很容易被簡單的ASIC機器破解。scrypt算法就是為了解決這樣的問題出現的。

scrypt算法詳解

scrypt算法會生成非常大的僞随機數序列，這個随機數序列會被用在後續的key生成過程中，是以一般來說需要一個RAM來進行存儲。這就是scrypt算法需要大記憶體的原因。

接下我們詳細分析一下scrypt算法，标準的Scrypt算法需要輸入8個參數，如下所示：

Passphrase: 要被hash的輸入密碼

Salt: 對密碼保護的鹽，防止彩虹表攻擊

CostFactor (N): CPU/memory cost 參數，必須是2的指數(比如: 1024)

BlockSizeFactor ®: blocksize 參數

ParallelizationFactor §: 并行參數

DesiredKeyLen (dkLen): 輸出的衍生的key的長度

hLen: hash函數的輸出長度

MFlen: Mix函數的輸出長度

這個函數的輸出就是DerivedKey。

首先我們需要生成一個expensiveSalt。首先得到blockSize：

然後使用PBKDF2生成p個blockSize，将這p個block組合成一個數組：

使用ROMix對得到的block進行混合：

将B組合成新的expensiveSalt：

接下來使用PBKDF2和新的salt生成最終的衍生key：

下面是ROMix函數的僞代碼：

其中BlockMix的僞代碼如下：

scrypt的使用

Scrypt被用在很多新的POW的虛拟貨币中，比如Tenebrix、 Litecoin 和 Dogecoin。感興趣的朋友可以關注一下。