scrypt

Scrypt的發明者是Colin Percival,一開始是要給Tarsnap線上儲存服務使用。

虛擬貨幣Litecoin(萊特幣)也是採用SCRYPT,而知名度較高的Bitcoin(比特幣)是採用SHA256。SCRYPT的目的是提高硬體計算所需要的資源,也就是需要較大量的記憶體,提高純硬體計算晶片的製作難度,但今年(2014)還是被人做出來了,沒有做不出來的東西,有沒有做的價值而已。

在Android 4.4以後,原來使用PBKDF2的全磁碟加密密碼儲存機制(Full Disk Encryption)改為scrypt。

簡單一點想,就是頭先用PBKDF2跑一次,中間再弄亂,尾巴再來一次PBKDF2。

 

演算法 scrypt(Passphrase,Salt,N,p,dkLen)

先定義一些變數

  • hLen: 由 HMAC_SHA256() 產生的雜湊值長度,因為使用HMAC搭配SHA256 來跑PBKDF2, 所以長度為32
  • dkLen: 金鑰的期望長度; 小於等於 (232− 1) * 32 的正整數
  • N: CPU/memory 成本參數,其中N是2的指數且 –1 < N <=  2(128 * r / 8)
  • r: 區塊大小
  • p: 平行參數,是個小於等於 (232− 1) * 32 / (128*r) 的正整數

Function scrypt(Passphrase,Salt,N,p,dkLen)

(B0 … Bp−1) ← PBKDF2(Passphrase, Salt, 1, p * 128 * r)

for i = 0 to p-1 do

B[i] ← scryptROMix(r, Bi, N) //每個位元都丟去處理

end for

Output ← PBKDF2(Passphrase, B0 || B1 … Bp−1, 1, dkLen)

 

Function scryptROMix (r, B, N)

  • r: 區塊大小
  • B: 長度是128 * r
  • N跟前面的定義一樣
  • 輸出為128 * r 個位元組

X ← B

for i = 0 to N − 1 do

Vi ← X  //先把X存起來, 後面要用

X ← scryptBlockMix(X)

end for

for i = 0 to N − 1 do

j ← Integerify(X) mod N

// Integerify (B[0] … B[2 * r – 1])定義為以little-endian 解譯的結果

X ← scryptBlockMix(X ⊕ Vj) //先算出 j 再得出 Vj

end for

Output ← X

 

Function scryptBlockMix(B)

輸入是Input vector of 2 * r 64-octet blocks B[0], …, B[2 * r – 1],輸出也是 2 * r 64-octet blocks

X = B[2 * r – 1]  //X是最後一個元素

for i = 0 to 2r − 1 do

X = H(X ⊕ Bi) //H表示雜湊函數, RFC草案是用salsa演算法

Yi = X

end for  //每跑一次, X的內容都不同 è 相依性以避免平行化

Output ← (Y0, Y2, … , Y2r−2, Y1, Y3, … , Y2r−1)

//先放偶, 再放奇, 長度是2r

 

全部展開就是

B[0] || B[1] || … || B[p – 1] = PBKDF2-HMAC-SHA256 (P, S, 1, p * 128 * r)

for i = 0 to p – 1 do

X = B[i]

for i = 0 to N – 1 do

V[i] = X

Z = B[2 * r – 1]

for i = 0 to 2 * r – 1 do

Y[i] = H(Z xor B[i])

end for

X = (Y[0], Y[2], …, Y[2 * r – 2], Y[1], Y[3], …, Y[2 * r – 1])

end for

for i = 0 to N – 1 do

j = Integerify (X) mod N

K=X xor V[j]

Z = K[2 * r – 1]

for i = 0 to 2 * r – 1 do

Y[i] = H(Z xor K[i])

end for

X = (Y[0], Y[2], …, Y[2 * r – 2], Y[1], Y[3], …, Y[2 * r – 1])

end for

B[i] = X

end for

DK = PBKDF2-HMAC-SHA256 (P, B[0] || B[1] || … || B[p – 1], 1, dkLen)

Leave a Reply

你的電子郵件位址並不會被公開。 必要欄位標記為 *