3

Haskell で PBKDF2 アルゴリズムの新しいバージョンを作成しました。RFC 6070にリストされている HMAC-SHA-1 テスト ベクトルのほぼすべてに合格しますが、あまり効率的ではありません。コードを改善するにはどうすればよいですか?

テスト ベクトルで実行すると、3 番目のケース (以下を参照) が終了しません (2010 Macbook Pro で 0.5 時間以上実行したままにしました)。

これ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

3 番目のテスト ベクトル

 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)
4

1 に答える 1

3

私の MacBookPro では、約 16 分で完了することができました。

% time Crypto-Main
eefe3d61cd4da4e4e9945b3d6ba2158c2634e984                          
./Crypto-Main  1027.30s user 15.34s system 100% cpu 17:22.61 total

フォールドの厳密さを変更することにより：

let
  -- ...
  blockIterator message acc = foldl' (zipWith' xor) acc ms
    where ms = take iterations . tail $ iterate (prf passwordOctets) message
          zipWith' f as bs = let cs = zipWith f as bs in sum cs `seq` cs
in
  dumpRaw $ take keyLength $ foldl' (\acc block ->
    acc ++ blockIterator (saltOctets ++ intToOctets block)
                    (replicate hashLength 0)) [] [1..totalBlocks]

それぞれの完全な評価を強制する方法に注意してくださいzipWith xor。WHNFを計算する sum csには、 の各要素の正確な値を知る必要がありますcs。

これにより、既存のコードが実行しようとしていたと思われるサンクのチェーンが構築されなくなりますがfoldl'、アキュムレータを WHNF に強制するだけで失敗します。アキュムレータはペアだったので、WHNF はちょうど(_thunk, _another_thunk)で、中間のサンクは強制されませんでした。

于 2013-09-11T15:22:55.343 に答える