首页 > 代码库 > Java密码学原型算法实现——第一部分：标准Hash算法

Java密码学原型算法实现——第一部分：标准Hash算法

2024-07-16 04:39:01   224人阅读

题注

从博客中看出来我是个比较钟爱Java的应用密码学研究者。虽然C在密码学中有不可替代的优势：速度快，但是，Java的可移植性使得开发人员可以很快地将代码移植到各个平台，这比C实现要方便的多。尤其是Android平台的出现，Java的应用也就越来越广。因此，我本人在密码学研究过程中实际上也在逐渐使用和封装一些知名的Java密码学库，主要是方便自己使用。

Java JDK实际上自带了密码学库，支持几乎所有通用密码学原型的实现。然而，自带密码库有几个缺点：第一，由于版权问题，其并不支持全部的密码学原型，如256位的AES加密等等。第二，Java JDK的使用并非特别的方便。因此，我现在基本上在使用另一个知名的Java密码学库：Bouncy Castle，其官方网址为：http://www.bouncycastle.org/java.html。

但是，现在网上对于Bouncy Castle的介绍实在是有点少，而且每个人写的代码都不太一样，绝大多数人共享的代码只是为了个人使用，复用性并不是很强。因此，我现在在逐渐编写一些复用性比较强的封装，从而方便在自己设计的公钥加密、签名等体制中调用。

第一部分的实现是标准Hash算法。这一实现使用的是Java JDK，但是使用了Bouncy Castle的工具库实现Byte和String的一些转换。

一些Util封装

在进入正题前，我先介绍一下自己引用或者实现的一些Util封装，这些封装会方便我进行下一步的实现。不管使用的方便与否，各位看官凑合着看，凑合着用，如果有任何可以改进的地方还请给我发邮件，我的邮箱是footman_900217@126.com。

In.java

这个In.java，包括下面的Out.java、StdIn.java以及StdOut.java都是从Princeton的算法公开课中使用的库函数。他们对Java的原始输入输出进行了进一步的封装，我个人认为非常好用。当然了，在实现过程中大家也可以使用JDK自带的函数库。Princeton的开发者们实际上对于其库函数封装了一个统一的jar文件，称为stdlib.jar。大家可以直接在工程中引用这个jar文件，或者下载源代码并放置在工程中。我是选择了后者，这主要是为了方便工程向Android中的移植，避免了jar文件引用过程中可能出现的一些错误。所有的源代码可以从下面的链接中下载到：http://algs4.cs.princeton.edu/home/。为了方便使用，在此我附上代码，但是注意这些代码的原始版权为Princeton大学。

import java.io.BufferedInputStream;
import java.io.File;
import java.io.IOException;
import java.io.InputStream;
import java.net.Socket;
import java.net.URL;
import java.net.URLConnection;
import java.util.Locale;
import java.util.Scanner;


/**
 *  <i>Input</i>. This class provides methods for reading strings
 *  and numbers from standard input, file input, URL, and socket.
 *  <p>
 *  The Locale used is: language = English, country = US. This is consistent
 *  with the formatting conventions with Java floating-point literals,
 *  command-line arguments (via <tt>Double.parseDouble()</tt>)
 *  and standard output (via <tt>System.out.print()</tt>). It ensures that
 *  standard input works the number formatting used in the textbook.
 *  <p>
 *  For additional documentation, see <a href=http://www.mamicode.com/"http://introcs.cs.princeton.edu/31datatype">Section 3.1 of>

Out.java
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.net.Socket;
import java.util.Locale;

/**
 *  This class provides methods for writing strings and numbers to
 *  various output streams, including standard output, file, and sockets.
 *  <p>
 *  For additional documentation, see
 *  <a href=http://www.mamicode.com/"http://introcs.cs.princeton.edu/31datatype">Section 3.1 of>

StdIn.java
import java.io.BufferedInputStream;
import java.util.Locale;
import java.util.Scanner;

/**
 *  <i>Standard input</i>. This class provides methods for reading strings
 *  and numbers from standard input.
 *  <p>
 *  The Locale used is: language = English, country = US. This is consistent
 *  with the formatting conventions with Java floating-point literals,
 *  command-line arguments (via <tt>Double.parseDouble()</tt>)
 *  and standard output (via <tt>System.out.print()</tt>). It ensures that
 *  standard input works with the input files used in the textbook.
 *  <p>
 *  For additional documentation, see <a href=http://www.mamicode.com/"http://introcs.cs.princeton.edu/15inout">Section 1.5 of>

StdOut.java
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.UnsupportedEncodingException;
import java.util.Locale;

/**
 *  <i>Standard output</i>. This class provides methods for writing strings
 *  and numbers to standard output.
 *  <p>
 *  For additional documentation, see <a href=http://www.mamicode.com/"http://introcs.cs.princeton.edu/15inout">Section 1.5 of>

Timer.java
Timer.java主要是为了方便测试算法运行的时间。我简单地撰写了一个java文件进行测试，测试精读大概是纳秒级别的。在此需要提醒一下大家，System.nanoTime()返回的时间精度是非常高的，而System.currentTimeMillis()这个函数返回的结果精度只是毫秒级的，用于测试时间非常不精确，所以建议大家使用nanoTime()进行时间的测试。这个java文件还包括了一个nowTime()函数，用于返回当前的系统时间。这在我个人的开发中有一些用途。因为也属于时间函数，因此放在了Timer.java中。
import java.text.SimpleDateFormat;
import java.util.Date;

public class Timer {
	public enum FORMAT{
		SECOND, MILLI_SECOND, MICRO_SECOND, NANO_SECOND,
	}
	
	public static final int DEFAULT_MAX_NUM_TIMER = 10;
	public final int MAX_NUM_TIMER;
	
	private long[] timeRecorder;
	private boolean[] isTimerStart;
	private FORMAT[] outFormat;
	
	public static String nowTime() {
		SimpleDateFormat df = new SimpleDateFormat("yyyy-MM-dd-HH-mm-ss");// 设置日期格式
		return df.format(new Date());
	}
	
	public Timer(){
		this.MAX_NUM_TIMER = DEFAULT_MAX_NUM_TIMER;
		this.timeRecorder = new long[MAX_NUM_TIMER];
		this.isTimerStart = new boolean[MAX_NUM_TIMER];
		this.outFormat = new FORMAT[MAX_NUM_TIMER];
		
		//set default format as millisecond
		for (int i=0; i<outFormat.length; i++){
			outFormat[i] = FORMAT.MILLI_SECOND;
		}
	}
	
	public Timer(int max_num_timer){
		this.MAX_NUM_TIMER = max_num_timer;
		this.timeRecorder = new long[MAX_NUM_TIMER];
		this.isTimerStart = new boolean[MAX_NUM_TIMER];
		this.outFormat = new FORMAT[MAX_NUM_TIMER];
		
		//set default format as millisecond
		for (int i=0; i<outFormat.length; i++){
			outFormat[i] = FORMAT.MILLI_SECOND;
		}
	}
	
	public void setFormat(int num, FORMAT format){
		//Ensure num less than MAX_NUM_TIMER
		assert(num >=0 && num < MAX_NUM_TIMER);
		
		this.outFormat[num] = format;
	}
	
	public void start(int num) {
		//Ensure the timer now stops.
		assert(!isTimerStart[num]);
		//Ensure num less than MAX_NUM_TIMER
		assert(num >=0 && num < MAX_NUM_TIMER);
		
		isTimerStart[num] = true;
		timeRecorder[num] = System.nanoTime();
	}
	
	public double stop(int num) {
		//Ensure the timer now starts.
		assert(isTimerStart[num]);
		//Ensure num less than MAX_NUM_TIMER
		assert(num >=0 && num < MAX_NUM_TIMER);
		
		long result = System.nanoTime() - timeRecorder[num];
		isTimerStart[num] = false;
		
		switch(outFormat[num]){
		case SECOND:
			return (double) result / 1000000000L;
		case MILLI_SECOND:
			return (double) result / 1000000L;
		case MICRO_SECOND:
			return (double) result / 1000L;
		case NANO_SECOND:
			return (double) result;
		default:
			return (double) result / 1000000L;
		}
	}
}


Hash函数介绍
Hash函数是将任意长的子串M映射成一个较短的定长输出子串H的函数，这个函数一般用h或者hash表示。我们要求h(M)必须易于计算，称H=h(M)为M的Hash值。h函数是一个多对一的映射，一般为了安全性，我们要求很难从H求出原来的M，或者从H求出一个M‘，使得h(M)=h(M‘)。但是，我们可以验证任意给定子串M‘是否与M具有相同的Hash值。
Hash函数可以按照是否有密钥作为输入分为两大类。一类有密钥控制，即函数定义为h(k, M)；另一类没有密钥控制，任何人都可以计算，即函数定义为h(M)。因此，h(k, M)只有拥有密钥的人可以计算，所以其一般具有身份认证功能；h(M)任何人都可以计算，因而不具有身份认证的功能，只用于检测接收数据的完整性，或者验证输入的内容是否为原始输入的内容。
对于第一类Hash函数，在此我并不涉及，因为其函数一般来说是通过第二类Hash函数与单钥加密函数合并实现的，因此我把单钥加密函数以及第二类Hash函数作为密码学原型函数，而把第一类Hash函数看做他们的一种扩展。对于第二类Hash函数，比较知名的，或者说大家都知道的有MD5，SHA1等等。但是实际上，MD5和SHA1已经被认为并不安全，攻破的人正是清华大学著名的密码学家王小云老师。因此，在这里我也不涉及MD5，SHA1的实现，而涉及到的是SHA256，SHA384，SHA512的实现。说句题外话，我有幸与王小云老师有过三面之缘，王小云老师确实是一个典型的数学家，有着非常严谨的思维，她的团队现在致力于Lattice有限域结构的研究。如果看官有兴趣读王小云老师的博士，可以联系她，她人很nice的~
在密码学中，Hash函数需要满足如下形式：
  • 混合变换（Mixing Transformation）。对于任意的输入x，输出的杂凑至h(x)应当与区间[0, 2^{|h|}]中均匀的二进制串在计算上是不可区分的。通俗点说，就是h(x)的输出应该遍布于区间[0, 2^{|h|}]，输出值与这个区间中任意数相等的概率都一样。不过现在设计的算法很难做到这一点，所以上述定义说的是计算上不可区分。
  • 抗碰撞攻击（Collision Resistance）。找两个输入x和y，且x \neq y，使得h(x)=h(y)，这在计算上应当是不可行的。为了使这个假设成立，要求h的输出空间应当足够大。一般来说要求为128位，典型的值为160位或者256位。比如MD5的输出是128位，SHA1的输出是160位，而SHA256顾名思义其输出长度是256位。
  • 抗原像攻击（Pre-image Resistance）。已知一个Hash值h，找一个输入x，使得h=h(x)，这在计算上是不可行的。这个假设同样要求h的输出空间足够大。如果一个Hash不能抗原像攻击，我们认为这个Hash函数彻底不安全了，不能再使用。
  • 有效性（Practical Efficiency）。给定一个输入x，h(x)的计算可以在关于x的长度规模的低阶多项式时间内完成。也就是说，对于任意的输入x，计算h(x)是非常快的。
一般来说，应用典型的生日攻击（birthday attack，http://zh.wikipedia.org/wiki/%E7%94%9F%E6%97%A5%E5%95%8F%E9%A1%8C），我们可以将hash的安全常数降低一半。比如对于MD5，我们可以有1/2的概率，以2^80的计算量，找到一组数x和y，使得h(x)=h(y)，这就使得Hash函数不满足抗碰撞攻击。这种攻击对于任何Hash函数都是可行的。因此，一般来说Hash函数的安全常数是其输出长度的一半。如果一个Hash函数被证明其可以在比安全常数低的运算下能够找到碰撞，我们则称这个算法是不安全的。王小云老师的结果是，对于MD5算法，其甚至已经不能抗原像攻击。而对于SHA1算法，其安全性已经降低到69，已经不安全。
Hash函数的Java实现
其实Hash函数的实现比较简单。不过为了具有重用性，我们要求写出的函数既能够对任意byte[]数组进行Hash，也能够对于任意的InputStream进行Hash。针对不同的算法，我写了一个封装，其class名称为GeneralHash（这是为了后面的GroupHash实现而区分），源代码如下：
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;

import org.bouncycastle.util.encoders.Hex;

import cn.edu.buaa.crypto.util.StdOut;

public class GeneralHash {
	public enum HashMode{
		SHA256,
		SHA384,
		SHA512,
	}
	
	private static final int DEFAULT_BLOCK_SIZE = 1024;
	
	public static byte[] Hash(HashMode hashMode, byte[] message){
		MessageDigest md = null;
		try{
			switch(hashMode){
			case SHA256:
				md = MessageDigest.getInstance("SHA-256");
				break;
			case SHA384:
				md = MessageDigest.getInstance("SHA-384");
				break;
			case SHA512:
				md = MessageDigest.getInstance("SHA-512");
				break;
			default:
				//Default Hash is SHA256
				md = MessageDigest.getInstance("SHA-256");
				break;
			}
		} catch (NoSuchAlgorithmException e) {
			e.printStackTrace();
		}
		md.update(message);
		return md.digest();
	}
	
	public static byte[] Hash(HashMode hashMode, InputStream in){
		MessageDigest md = null;
		try{
			switch(hashMode){
			case SHA256:
				md = MessageDigest.getInstance("SHA-256");
				break;
			case SHA384:
				md = MessageDigest.getInstance("SHA-384");
				break;
			case SHA512:
				md = MessageDigest.getInstance("SHA-512");
				break;
			default:
				//Default Hash is SHA256
				md = MessageDigest.getInstance("SHA-256");
				break;
			}
			int inL;
			byte[] b = new byte[DEFAULT_BLOCK_SIZE];
			while ((inL = in.read(b)) != -1) {  
			    md.update(b, 0, inL);  
			}
		} catch (IOException e) {
			e.printStackTrace();
		} catch (NoSuchAlgorithmException e) {
			e.printStackTrace();
		}
		return md.digest();
	}
}

测试函数如下。测试函数也反映出我写的这个class如何使用，大家可以参考一下。
	private static void Test_Hash_String(){
		String message1 = "TestGeneralHash-1";
		String message2 = "TestGeneralHash-2";
		byte[] byte256 = GeneralHash.Hash(HashMode.SHA256, message1.getBytes());
		String sha256 = new String(Hex.encode(byte256));
		StdOut.println("SHA256, message = " + message1);
		StdOut.println("Result = " + sha256 + ", length = " + byte256.length);
		//Hash result for the same value should be equal
		byte[] byte256_1 = GeneralHash.Hash(HashMode.SHA256, message1.getBytes());
		String sha256_1 = new String(Hex.encode(byte256_1));
		StdOut.println("SHA256, message = " + message1);
		StdOut.println("Result = " + sha256_1 + ", length = " + byte256_1.length);
		assert(sha256.equals(sha256_1));
		//Hash result for different values should be distinct
		byte[] byte256_2 = GeneralHash.Hash(HashMode.SHA256, message2.getBytes());
		String sha256_2 = new String(Hex.encode(byte256_2));
		StdOut.println("SHA256, message = " + message2);
		StdOut.println("Result = " + sha256_2 + ", length = " + byte256_2.length);
		StdOut.println();
		assert(!sha256.equals(sha256_2));
		
		byte[] byte384 = GeneralHash.Hash(HashMode.SHA384, message1.getBytes());
		String sha384 = new String(Hex.encode(byte384));
		StdOut.println("SHA384, message = " + message1);
		StdOut.println("Result = " + sha384 + ", length = " + byte384.length);
		//Hash result for the same value should be equal
		byte[] byte384_1 = GeneralHash.Hash(HashMode.SHA384, message1.getBytes());
		String sha384_1 = new String(Hex.encode(byte384_1));
		StdOut.println("SHA384, message = " + message1);
		StdOut.println("Result = " + sha384_1 + ", length = " + byte384_1.length);
		assert(sha384.equals(sha384_1));
		//Hash result for different values should be distinct
		byte[] byte384_2 = GeneralHash.Hash(HashMode.SHA384, message2.getBytes());
		String sha384_2 = new String(Hex.encode(byte384_2));
		StdOut.println("SHA384, message = " + message2);
		StdOut.println("Result = " + sha384_2 + ", length = " + byte384_2.length);
		StdOut.println();
		assert(!sha384.equals(sha384_2));
		
		byte[] byte512 = GeneralHash.Hash(HashMode.SHA512, message1.getBytes());
		String sha512 = new String(Hex.encode(byte512));
		StdOut.println("SHA512, message = " + message1);
		StdOut.println("Result = " + sha512 + ", length = " + byte512.length);
		//Hash result for the same value should be equal
		byte[] byte512_1 = GeneralHash.Hash(HashMode.SHA512, message1.getBytes());
		String sha512_1 = new String(Hex.encode(byte512_1));
		StdOut.println("SHA512, message = " + message1);
		StdOut.println("Result = " + sha512_1 + ", length = " + byte512_1.length);
		assert(sha512.equals(sha512_1));
		//Hash result for different values should be distinct
		byte[] byte512_2 = GeneralHash.Hash(HashMode.SHA512, message2.getBytes());
		String sha512_2 = new String(Hex.encode(byte512_2));
		StdOut.println("SHA512, message = " + message2);
		StdOut.println("Result = " + sha512_2 + ", length = " + byte512_2.length);
		StdOut.println();
		assert(!sha512.equals(sha512_2));
	}
	
	private static void Test_Hash_File(){
		try {
			File fileIn = new File("docs1.5on.zip");
			FileInputStream in;
			
			in = new FileInputStream(fileIn);
			byte[] byte256 = GeneralHash.Hash(HashMode.SHA256, in);
			String sha256 = new String(Hex.encode(byte256));
			StdOut.println("File SHA256 = " + sha256 + ", length = " + byte256.length);
			in.close();
			
			in = new FileInputStream(fileIn);
			byte[] byte384 = GeneralHash.Hash(HashMode.SHA384, in);
			String sha384 = new String(Hex.encode(byte384));
			StdOut.println("File SHA384 = " + sha384 + ", length = " + byte384.length);
			in.close();
			
			in = new FileInputStream(fileIn);
			byte[] byte512 = GeneralHash.Hash(HashMode.SHA512, in);
			String sha512 = new String(Hex.encode(byte512));
			StdOut.println("File SHA512 = " + sha512 + ", length = " + byte512.length);
			in.close();
			
		}  catch (FileNotFoundException e) {
			e.printStackTrace();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}
	
	public static void main(String[] args){
		Test_Hash_String();
		Test_Hash_File();
	}


联系
我们