关于密码学:密码学系列之加密货币中的scrypt算法

138次阅读

共计 2107 个字符，预计需要花费 6 分钟才能阅读完成。

为了抵挡明码破解，科学家们想出了很多种办法，比方对明码进行混同加盐操作，对明码进行模式变换和组合。然而这些算法逐步被一些特制的 ASIC 处理器战胜，这些 ASIC 处理器不做别的，就是专门来破解你的明码或者进行 hash 运算。

最有名的当然是比特币了，它应用的是为人诟病的 POW 算法，谁的算力高，谁就能够挖矿，这样就导致了大量无意义的矿机的产生，这些矿机什么都不能干，就算是用来算 hash 值。后果节约了大量的电力。

普通人更是别想退出这个只有巨头能力领有的赛道，如果你想用一个一般的 PC 机来挖矿，那么我预计你挖到矿的几率可能跟被陨石砸中差不多。

为了抵挡这种 CPU 为主的明码加密形式，科学家们创造了很多其余的算法，比方须要占用大量内存的算法，因为内存不像 CPU 能够疯狂提速，所以限度了很多暴力破解的场景，明天要将的 scrypt 算法就是其中一种，该算法被利用到很多新的加密货币挖矿体系中，用以示意他们挖矿程序的公平性。

scrypt 是一种明码衍生算法，它是由 Colin Percival 创立的。应用 scrypt 算法来生成衍生 key，须要用到大量的内存。scrypt 算法在 2016 年作为 RFC 7914 规范公布。

明码衍生算法次要作用就是依据初始化的主明码来生成系列的衍生明码。这种算法次要是为了抵挡暴力破解的攻打。通过减少明码生成的复杂度，同时也减少了暴力破解的难度。

然而和下面提到的起因一样，之前的 password-based KDF，比方 PBKDF2 尽管进步了明码生成的遍历次数，然而它应用了很少的内存空间。所以很容易被简略的 ASIC 机器破解。scrypt 算法就是为了解决这样的问题呈现的。

scrypt 算法会生成十分大的伪随机数序列，这个随机数序列会被用在后续的 key 生成过程中，所以一般来说须要一个 RAM 来进行存储。这就是 scrypt 算法须要大内存的起因。

接下咱们详细分析一下 scrypt 算法，规范的 Scrypt 算法须要输出 8 个参数，如下所示：

Passphrase: 要被 hash 的输出明码
Salt: 对密码保护的盐，避免彩虹表攻打
CostFactor (N): CPU/memory cost 参数，必须是 2 的指数 (比方: 1024)
BlockSizeFactor (r): blocksize 参数
ParallelizationFactor (p): 并行参数
DesiredKeyLen (dkLen): 输入的衍生的 key 的长度
hLen: hash 函数的输入长度
MFlen: Mix 函数的输入长度

这个函数的输入就是 DerivedKey。

首先咱们须要生成一个 expensiveSalt。首先失去 blockSize：

blockSize = 128*BlockSizeFactor

而后应用 PBKDF2 生成 p 个 blockSize，将这 p 个 block 组合成一个数组：

[B0...Bp−1] = PBKDF2HMAC-SHA256(Passphrase, Salt, 1, blockSize*ParallelizationFactor)

应用 ROMix 对失去的 block 进行混合：

   for i ← 0 to p-1 do
      Bi ← ROMix(Bi, CostFactor)

将 B 组合成新的 expensiveSalt：

expensiveSalt ← B0∥B1∥B2∥ ... ∥Bp-1

接下来应用 PBKDF2 和新的 salt 生成最终的衍生 key：

return PBKDF2HMAC-SHA256(Passphrase, expensiveSalt, 1, DesiredKeyLen);

上面是 ROMix 函数的伪代码：

Function ROMix(Block, Iterations)

   Create Iterations copies of X
   X ← Block
   for i ← 0 to Iterations−1 do
      Vi ← X
      X ← BlockMix(X)

   for i ← 0 to Iterations−1 do
      j ← Integerify(X) mod Iterations 
      X ← BlockMix(X xor Vj)

   return X

其中 BlockMix 的伪代码如下：

Function BlockMix(B):

    The block B is r 128-byte chunks (which is equivalent of 2r 64-byte chunks)
    r ← Length(B) / 128;

    Treat B as an array of 2r 64-byte chunks
    [B0...B2r-1] ← B

    X ← B2r−1
    for i ← 0 to 2r−1 do
        X ← Salsa20/8(X xor Bi)  // Salsa20/8 hashes from 64-bytes to 64-bytes
        Yi ← X

    return ← Y0∥Y2∥...∥Y2r−2 ∥ Y1∥Y3∥...∥Y2r−1

Scrypt 被用在很多新的 POW 的虚构货币中，比方 Tenebrix、Litecoin 和 Dogecoin。感兴趣的敌人能够关注一下。