Scrypt 不止是加密算法,也是莱特币的挖矿算法

优雅.jpg

在密码学中,scrypt(念作“ess crypt”)是Colin Percival于2009年所发明的金钥推衍函数,当初设计用在他所创立的Tarsnap服务上。设计时考虑到大规模的客制硬件攻击而刻意设计需要大量内存运算。2016年,scrypt算法发布在RFC 7914。scrypt的简化版被用在数个密码货币的工作量证明(Proof-of-Work)上。

Scrypt不仅计算所需时间长,而且占用的内存也多,使得并行计算多个摘要异常困难,因此利用rainbow table进行暴力攻击更加困难。Scrypt 没有在生产环境中大规模应用,并且缺乏仔细的审察和广泛的函数库支持。但是,Scrypt 在算法层面只要没有破绽,它的安全性应该高于PBKDF2和bcrypt。

Scrypt 官网地址: https://www.tarsnap.com/scrypt.html

Scrypt 算法 Java 的实现

    /**
     * Pure Java implementation of the <a href="http://www.tarsnap.com/scrypt/scrypt.pdf">scrypt</a>.
     *
     * @param password
     *            Password.
     * @param salt
     *            Salt.
     * @param cost
     *            Overall CPU/MEM cost parameter. 2^15 for testing, but 2^20 recommended.
     * @param blocksize
     *            Block size for each mixing loop (memory usage).
     * @param parallel
     *            Parallelization to control the number of independent mixing loops.
     * @param length
     *            Intended length of the derived key.
     *
     * @return The derived key.
     *
     * @throws NoSuchAlgorithmException
     *             when HMAC_SHA256 is not available.
     * @throws IllegalArgumentException
     *             when parameters invalid
     */
    protected static byte[] scrypt(byte[] password, byte[] salt, int cost, int blocksize, int parallel, int length)
            throws GeneralSecurityException {
        if (cost < 2 || (cost & (cost - 1)) != 0) throw new IllegalArgumentException("Cost must be a power of 2 greater than 1");
        if (cost > Integer.MAX_VALUE / 128 / blocksize) throw new IllegalArgumentException("Parameter cost is too large");
        if (blocksize > Integer.MAX_VALUE / 128 / parallel) throw new IllegalArgumentException("Parameter blocksize is too large");

        Mac mac = Mac.getInstance("HmacSHA256");
        mac.init(new SecretKeySpec(password, "HmacSHA256"));

        byte[] key = new byte[length];

        byte[] b1 = new byte[128 * blocksize * parallel];
        byte[] xy = new byte[256 * blocksize];
        byte[] v1 = new byte[128 * blocksize * cost];

        pbkdf2(mac, salt, 1, b1, parallel * 128 * blocksize);

        for (int i = 0; i < parallel; i++) {
            smix(b1, i * 128 * blocksize, blocksize, cost, v1, xy);
        }

        pbkdf2(mac, b1, 1, key, length);

        return key;
    }

    private static void smix(byte[] b1, int bi, int round, int cpu, byte[] v1, byte[] xy) {
        int xi = 0;
        int yi = 128 * round;

        System.arraycopy(b1, bi, xy, xi, 128 * round);

        for (int i = 0; i < cpu; i++) {
            System.arraycopy(xy, xi, v1, i * (128 * round), 128 * round);
            blockMixSalsa8(xy, xi, yi, round);
        }

        for (int i = 0; i < cpu; i++) {
            int j = integerify(xy, xi, round) & (cpu - 1);
            blockxor(v1, j * (128 * round), xy, xi, 128 * round);
            blockMixSalsa8(xy, xi, yi, round);
        }

        System.arraycopy(xy, xi, b1, bi, 128 * round);
    }

    private static void blockMixSalsa8(byte[] by, int bi, int yi, int round) {

        byte[] x1 = new byte[64];
        System.arraycopy(by, bi + (2 * round - 1) * 64, x1, 0, 64);

        for (int i = 0; i < 2 * round; i++) {
            blockxor(by, i * 64, x1, 0, 64);
            salsa(x1);
            System.arraycopy(x1, 0, by, yi + (i * 64), 64);
        }

        for (int i = 0; i < round; i++) {
            System.arraycopy(by, yi + (i * 2) * 64, by, bi + (i * 64), 64);
        }

        for (int i = 0; i < round; i++) {
            System.arraycopy(by, yi + (i * 2 + 1) * 64, by, bi + (i + round) * 64, 64);
        }
    }

    private static int r1(int left, int right) {
        return (left << right) | (left >>> (32 - right));
    }

    private static void salsa(byte[] b1) {

        int[] base32 = new int[16];
        for (int i = 0; i < 16; i++) {
            base32[i] = (b1[i * 4 + 0] & 0xff) << 0;
            base32[i] |= (b1[i * 4 + 1] & 0xff) << 8;
            base32[i] |= (b1[i * 4 + 2] & 0xff) << 16;
            base32[i] |= (b1[i * 4 + 3] & 0xff) << 24;
        }

        int[] x1 = new int[16];
        System.arraycopy(base32, 0, x1, 0, 16);

        for (int i = 8; i > 0; i -= 2) {
            x1[4] ^= r1(x1[0] + x1[12], 7);
            x1[8] ^= r1(x1[4] + x1[0], 9);
            x1[12] ^= r1(x1[8] + x1[4], 13);
            x1[0] ^= r1(x1[12] + x1[8], 18);
            x1[9] ^= r1(x1[5] + x1[1], 7);
            x1[13] ^= r1(x1[9] + x1[5], 9);
            x1[1] ^= r1(x1[13] + x1[9], 13);
            x1[5] ^= r1(x1[1] + x1[13], 18);
            x1[14] ^= r1(x1[10] + x1[6], 7);
            x1[2] ^= r1(x1[14] + x1[10], 9);
            x1[6] ^= r1(x1[2] + x1[14], 13);
            x1[10] ^= r1(x1[6] + x1[2], 18);
            x1[3] ^= r1(x1[15] + x1[11], 7);
            x1[7] ^= r1(x1[3] + x1[15], 9);
            x1[11] ^= r1(x1[7] + x1[3], 13);
            x1[15] ^= r1(x1[11] + x1[7], 18);
            x1[1] ^= r1(x1[0] + x1[3], 7);
            x1[2] ^= r1(x1[1] + x1[0], 9);
            x1[3] ^= r1(x1[2] + x1[1], 13);
            x1[0] ^= r1(x1[3] + x1[2], 18);
            x1[6] ^= r1(x1[5] + x1[4], 7);
            x1[7] ^= r1(x1[6] + x1[5], 9);
            x1[4] ^= r1(x1[7] + x1[6], 13);
            x1[5] ^= r1(x1[4] + x1[7], 18);
            x1[11] ^= r1(x1[10] + x1[9], 7);
            x1[8] ^= r1(x1[11] + x1[10], 9);
            x1[9] ^= r1(x1[8] + x1[11], 13);
            x1[10] ^= r1(x1[9] + x1[8], 18);
            x1[12] ^= r1(x1[15] + x1[14], 7);
            x1[13] ^= r1(x1[12] + x1[15], 9);
            x1[14] ^= r1(x1[13] + x1[12], 13);
            x1[15] ^= r1(x1[14] + x1[13], 18);
        }

        for (int i = 0; i < 16; ++i) {
            base32[i] = x1[i] + base32[i];
        }

        for (int i = 0; i < 16; i++) {
            b1[i * 4 + 0] = (byte) (base32[i] >> 0 & 0xff);
            b1[i * 4 + 1] = (byte) (base32[i] >> 8 & 0xff);
            b1[i * 4 + 2] = (byte) (base32[i] >> 16 & 0xff);
            b1[i * 4 + 3] = (byte) (base32[i] >> 24 & 0xff);
        }
    }

    private static void blockxor(byte[] s1, int si, byte[] d1, int di, int length) {
        for (int i = 0; i < length; i++) {
            d1[di + i] ^= s1[si + i];
        }
    }

    private static int integerify(byte[] b1, int bi, int round) {
        bi += (2 * round - 1) * 64;
        int n = (b1[bi + 0] & 0xff) << 0;
        n |= (b1[bi + 1] & 0xff) << 8;
        n |= (b1[bi + 2] & 0xff) << 16;
        n |= (b1[bi + 3] & 0xff) << 24;

        return n;
    }

    /**
     * Implementation of PBKDF2 (RFC2898).
     *
     * @param mac
     *            Pre-initialized {@link Mac} instance to use.
     * @param salt
     *            Salt.
     * @param iterations
     *            Iteration count.
     * @param key
     *            Byte array that derived key will be placed in.
     * @param length
     *            Intended length, in octets, of the derived key.
     *
     * @throws GeneralSecurityException
     *             If key length is too long
     */
    protected static void pbkdf2(Mac mac, byte[] salt, int iterations, byte[] key, int length) throws GeneralSecurityException {
        int len = mac.getMacLength();

        byte[] u1 = new byte[len];
        byte[] t1 = new byte[len];
        byte[] block = new byte[salt.length + 4];

        int limit = (int) Math.ceil((double) length / len);
        int r = length - (limit - 1) * len;

        System.arraycopy(salt, 0, block, 0, salt.length);

        for (int i = 1; i <= limit; i++) {
            block[salt.length + 0] = (byte) (i >> 24 & 0xff);
            block[salt.length + 1] = (byte) (i >> 16 & 0xff);
            block[salt.length + 2] = (byte) (i >> 8 & 0xff);
            block[salt.length + 3] = (byte) (i >> 0 & 0xff);

            mac.update(block);
            mac.doFinal(u1, 0);
            System.arraycopy(u1, 0, t1, 0, len);

            for (int j = 1; j < iterations; j++) {
                mac.update(u1);
                mac.doFinal(u1, 0);

                for (int k = 0; k < len; k++) {
                    t1[k] ^= u1[k];
                }
            }

            System.arraycopy(t1, 0, key, (i - 1) * len, (i == limit ? r : len));
        }
    }

下面是 Scrypt 算法的调用。

package com.cv4j.blockchain.study.scrypt;

import java.io.UnsupportedEncodingException;
import java.security.GeneralSecurityException;

/**
 * Created by tony on 2018/8/5.
 */
public class Test {

    public static void main(String[] args) {

        byte[] password = new byte[0];
        try {
            password = "123456".getBytes("UTF-8");
        } catch (UnsupportedEncodingException e) {
            e.printStackTrace();
        }

        byte[] salt = new byte[0];
        try {
            salt = "abcdefg".getBytes("UTF-8");
        } catch (UnsupportedEncodingException e) {
            e.printStackTrace();
        }

        long start = System.currentTimeMillis();

        byte[] scrypt = new byte[0];
        try {
            scrypt = Scrypt.scrypt(password,salt,131072,8,1,32);
        } catch (GeneralSecurityException e) {
            e.printStackTrace();
        }

        String str = HashUtils.encodeBase64(scrypt);

        long end = System.currentTimeMillis();
        System.out.println("加密后的值:"+str);
        System.out.println("花费时间:"+(end-start)+" ms");
    }
}

下面的代码实现了真正的加密

scrypt = Scrypt.scrypt(password,salt,131072,8,1,32);

加密后的字节数组还需要使用 Base64 进行 encode。

完整的 Scrypt Java 版本已经放到github上。 github地址:https://github.com/fengzhizi715/blockchain_study

Scrypt 算法 C 的实现

#include <errno.h>
#include <stdlib.h>
#include <inttypes.h>

#include <jni.h>
#include "crypto_scrypt.h"

jbyteArray JNICALL Java_io_merculet_scrypt_util_SignUtils_scryptN(JNIEnv *env, jclass cls, jbyteArray passwd, jbyteArray salt,
                           jint N, jint r, jint p, jint dkLen)
{
    jint Plen = (*env)->GetArrayLength(env, passwd);
    jint Slen = (*env)->GetArrayLength(env, salt);
    jbyte *P = (*env)->GetByteArrayElements(env, passwd, NULL);
    jbyte *S = (*env)->GetByteArrayElements(env, salt,   NULL);
    uint8_t *buf = malloc(sizeof(uint8_t) * dkLen);
    jbyteArray DK = NULL;

    if (P == NULL || S == NULL || buf == NULL) goto cleanup;

    if (crypto_scrypt((uint8_t *) P, Plen, (uint8_t *) S, Slen, N, r, p, buf, dkLen)) {
        jclass e = (*env)->FindClass(env, "java/lang/IllegalArgumentException");
        char *msg;
        switch (errno) {
            case EINVAL:
                msg = "N must be a power of 2 greater than 1";
                break;
            case EFBIG:
            case ENOMEM:
                msg = "Insufficient memory available";
                break;
            default:
                msg = "Memory allocation failed";
        }
        (*env)->ThrowNew(env, e, msg);
        goto cleanup;
    }

    DK = (*env)->NewByteArray(env, dkLen);
    if (DK == NULL) goto cleanup;

    (*env)->SetByteArrayRegion(env, DK, 0, dkLen, (jbyte *) buf);

    cleanup:

    if (P) (*env)->ReleaseByteArrayElements(env, passwd, P, JNI_ABORT);
    if (S) (*env)->ReleaseByteArrayElements(env, salt,   S, JNI_ABORT);
    if (buf) free(buf);

    return DK;
}

在 Android 中调用 Scrypt 算法。

        byte[] password = new byte[0];
        try {
            password = "123456".getBytes("UTF-8");
        } catch (UnsupportedEncodingException e) {
            e.printStackTrace();
        }

        byte[] salt = new byte[0];
        try {
            salt = "abcdefg".getBytes("UTF-8");
        } catch (UnsupportedEncodingException e) {
            e.printStackTrace();
        }

        byte[] scrypt = SignUtils.scryptN(password,salt,131072,8,1,32);

        String str = HashUtils.encodeBase64(scrypt);

其中,SignUtils 是通过 JNI 来调用 C 的代码。

public class SignUtils {

    // Used to load the 'native-lib' library on application startup.
    static {
        System.loadLibrary("scrypt");
    }

    public static native byte[] scryptN(byte[] password, byte[] salt, int cost, int blocksize, int parallel, int length);
}

另外,需要注意的是在 Android 中,Base64 的工具类略有不同。

import android.util.Base64;

/**
 * Created by tony on 2018/8/1.
 */
public final class HashUtils {

    /**
     * Decodes a Base64 string to a byte array.
     *
     * @param string
     *            (in Base64)
     * @return Base64 decoded byte array
     * @see <a href="https://en.wikipedia.org/wiki/Base64">https://en.wikipedia.org/wiki/Base64</a>
     */
    public static byte[] decodeBase64(String string) {
        return Base64.decode(string.getBytes(), Base64.DEFAULT);
    }

    /**
     * Encodes a byte array into a Base64 string.
     *
     * @param array
     *            (byte array)
     * @return Base64 encoded string
     * @see <a href="https://en.wikipedia.org/wiki/Base64">https://en.wikipedia.org/wiki/Base64</a>
     */
    public static String encodeBase64(byte[] array) {
        return new String(Base64.encode(array, Base64.DEFAULT));
    }
}

完整的 Scrypt C 版本已经放到github上,方便在 App 中进行调用。 github地址:https://github.com/fengzhizi715/Scrypt_jni

总结

上面整理了 Scrypt 的两种实现方式,如果对于安全性要求很高的密码,可以采用 Scrypt 算法。该算法唯一的缺点就是慢。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏跟着阿笨一起玩NET

ZPL打印中文信息

  相信各位在实际的项目中,需要开发打条码模块的也会有不少,很多同行肯定也一直觉得斑马打印机很不错,但是ZPL打印中文字符很麻烦。如果购买字体卡,或者通过COD...

4571
来自专栏Spark生态圈

[Spark SQL] 源码解析之Optimizer

optimizer 以及之后的模块都只会在触发了action操作后才会执行。优化器是用来将Resolved LogicalPlan转化为optimized Lo...

1042
来自专栏函数式编程语言及工具

Akka(8): 分布式运算:Remoting-远程查找式

  Akka是一种消息驱动运算模式,它实现跨JVM程序运算的方式是通过能跨JVM的消息系统来调动分布在不同JVM上ActorSystem中的Actor进行运算,...

4369
来自专栏24K纯开源

RegQueryValueEx正确使用方法

      项目中需要读取注册表中的HKEY_CLASSES_ROOT主键下一个子键的值,看了看MSDN的说明,有RegOpenKeyEx和RegQueryVa...

2758
来自专栏猿人谷

du熊学斐波那契I

du熊学斐波那契I Time Limit : 2000/1000ms (C/Other)   Memory Limit : 65535/32768K (C/Ot...

19210
来自专栏小筱月

java 开发 face++ 人脸特征识别系统

首先要在 face++ 注册一个账号,并且创建一个应用,拿到 api key 和 api secret;

3101
来自专栏个人分享

Hive metastore源码阅读(一)

  不要问我为什么,因为爱,哈哈哈哈。。。进入正题,最近做项目顺带学习了下hive metastore的源码,进行下知识总结。

2801
来自专栏王磊的博客

javascript数字格式化通用类——accounting.js使用

简介 accounting.js 是一个非常小的JavaScript方法库用于对数字,金额和货币进行格式化。并提供可选的Excel风格列渲染。它没有依赖任何JS...

6426
来自专栏木宛城主

PowerShell 获取Site Collection下被签出的文件

由于权限的设置,当文件被签出时导致别人不可见了,这对校验文件个数的人来说着实是件烦恼的事。幸好利用PowerShell,可以获取Site Collection下...

2027
来自专栏码匠的流水账

聊聊jesque的WorkerImpl与WorkerPool

Resque是一个使用redis来创建后台任务的ruby组件。而jesque是其java版本。通常用来做延时队列。

751

扫码关注云+社区

领取腾讯云代金券