我在 Haskell 中编写了新版本的 PBKDF2 算法。它通过了RFC 6070中列出的几乎所有 HMAC-SHA-1 测试向量,但效率不高。如何改进代码?
当我在测试向量上运行它时,第三种情况(见下文)永远不会完成(我让它在 2010 Macbook Pro 上运行超过 1/2 小时)。
我相信这foldl'
是我的问题。性能会foldr
更好,还是我需要使用可变数组?
{-# LANGUAGE BangPatterns #-}
{- Copyright 2013, G. Ralph Kuntz, MD. All rights reserved. LGPL License. -}
module Crypto where
import Codec.Utils (Octet)
import qualified Data.Binary as B (encode)
import Data.Bits (xor)
import qualified Data.ByteString.Lazy.Char8 as C (pack)
import qualified Data.ByteString.Lazy as L (unpack)
import Data.List (foldl')
import Data.HMAC (hmac_sha1)
import Text.Bytedump (dumpRaw)
-- Calculate the PBKDF2 as a hexadecimal string
pbkdf2
:: ([Octet] -> [Octet] -> [Octet]) -- pseudo random function (HMAC)
-> Int -- hash length in bytes
-> String -- password
-> String -- salt
-> Int -- iterations
-> Int -- derived key length in bytes
-> String
pbkdf2 prf hashLength password salt iterations keyLength =
let
passwordOctets = stringToOctets password
saltOctets = stringToOctets salt
totalBlocks =
ceiling $ (fromIntegral keyLength :: Double) / fromIntegral hashLength
blockIterator message acc =
foldl' (\(a, m) _ ->
let !m' = prf passwordOctets m
in (zipWith xor a m', m')) (acc, message) [1..iterations]
in
dumpRaw $ take keyLength $ foldl' (\acc block ->
acc ++ fst (blockIterator (saltOctets ++ intToOctets block)
(replicate hashLength 0))) [] [1..totalBlocks]
where
intToOctets :: Int -> [Octet]
intToOctets i =
let a = L.unpack . B.encode $ i
in drop (length a - 4) a
stringToOctets :: String -> [Octet]
stringToOctets = L.unpack . C.pack
-- Calculate the PBKDF2 as a hexadecimal string using HMAC and SHA-1
pbkdf2HmacSha1
:: String -- password
-> String -- salt
-> Int -- iterations
-> Int -- derived key length in bytes
-> String
pbkdf2HmacSha1 =
pbkdf2 hmac_sha1 20
第三个测试向量
Input:
P = "password" (8 octets)
S = "salt" (4 octets)
c = 16777216
dkLen = 20
Output:
DK = ee fe 3d 61 cd 4d a4 e4
e9 94 5b 3d 6b a2 15 8c
26 34 e9 84 (20 octets)