Skip to content

amao-blog/SM3

master
Switch branches/tags

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?
Code

Latest commit

 

Git stats

Files

Permalink
Failed to load latest commit information.
Type
Name
Latest commit message
Commit time
 
 
 
 

一、SM3算法介绍

SM3是国家密码管理局编制的商用算法,它是一种杂凑算法,可以应用于数字签名、验证等密码应用中。其计算方法、计算步骤和运算实例可以在国家商用密码管理办公室官网查看。

该算法的输入是一个长度 L 比特的消息m,其中 L < 2^64 ,经过填充、迭代压缩后,生成一个256比特的输出。

二、算法步骤

2.1 填充长度

假设消息m 的长度为 L 比特。首先将比特“1”添加到消息的末尾,再添加k 个“0”, k是满足L + 1 + k ≡ 448 mod 512 的最小的非负整数。然后再添加一个64位比特串,该比特串是长度L的二进制表示。填充后的消息m′的比特长度为512的倍数。

在具体的实现过程中,首先获取消息超过512比特整数倍部分的长度L。由于在最后一个分组分组中,要将1个比特位“1”添加到消息的末尾,并且要添加64比特来存储消息的长度。

L <= 512-(64+1)时,可以直接填充比特位“1”、 512-(64+1)个比特位“0”、64位的消息长度,;当 L > 512-(64+1)时,最后一个512比特的分组不够填充,需要再添加一个512位的分组,此时填充的“0”的个数为k=512-L-1+(512-64)

2.2 迭代压缩

在迭代的过程中,首先对填充后的消息m′按512比特进行分组。然后对每一个分组进行迭代压缩。迭代方式如下:

FOR i=0 TO n-1
    V (i+1) = CF (V (i) , B (i) )
ENDFOR

上述算法中,n是填充后消息分组的个数,即有多少个消息分组,就迭代多少次。Vi是256位的向量,V0为初始值IV,即前一个分组计算完后的结果Vi会当作下一个分组的参数传入CF函数中,此即是密码学中扩散原则,即原始消息的任意比特位的变化都会造成结果产生大的改变。

CF压缩函数中,需要用到的参数有向量V (i)B(i)、常量TjWjWj′。其中WjWj′是对512比特的消息分组进行扩展后产生的132个字。由于消息分组有多个,Wj和Wj′也对应有多个。在具体实现时,要在CF函数中对每一个消息分组进行消息扩展计算。

在迭代完最后一个消息分组后,CF函数返回的值Vn就是最终的计算结果。

三、实现过程

3.1 创建项目

打开Eclipse创建项目SM3,在项目SM3中创建类SM3。创建完成后目录结构如下所示:

3.2 定义算法中的常量、函数

算法中需要用到函数FFj、GGj、P0、P1、常量Tj等,以及原始消息、填充后的消息定义如下:

// 字符集
private String charset = "ISO-8859-1";
	
// 要哈希的字符串
private String message = "abc";
	
// 填充后的字符串
private String PaddingMessage;
	
 

// 获取常量T0和T1
private int T(int j){
	if(j <= 15){
		return 0x79cc4519;
	}else{
		return 0x7a879d8a;
	}
}
	
// 布尔函数 FF
private int FF(int X, int Y, int Z, int j)
{
	int result = 0;
	if(j >= 0 &&j <= 15)
	{
		result = X ^ Y ^ Z;
	}else if(j >= 16 && j <= 63)
	{
		result = (X & Y) | (X & Z) | (Y & Z);
	}
		return result;
	}
	
// 布尔函数GG
private int GG(int X, int Y, int Z, int j)
{
	int result = 0;
	if(j >= 0 &&j <= 15)
	{
		result = X ^ Y ^ Z;
	}else
	{
		result = (X & Y) | (~X & Z);
	}
	return result;
}
	
// 置换函数P0
private int P0(int X)
{
	return X ^ (CircleLeftShift(X, 9)) ^ CircleLeftShift(X, 17);
}

// 置换函数P1
private int P1(int X)
{
	return X ^ (CircleLeftShift(X, 15)) ^ CircleLeftShift(X, 23);
}

在上述函数定义中,用到的CircleLeftShift函数用于实现循环左移,它的两个参数分别是要移位的32位int型数据和循环左移的位数。在循环左移中,循环左移k位,相当于将二进制位最左边的k位移动到最右边。

3.2 调试方法编写

在课本的运算示例中,每一步运算的中间结果都有。在编写算法时,每写一步都要与课本上的中间结果对照,以确定当前得到的中间结果是否正确。由于算法运行的中间结果都是二进制形式,为方便查看,编写了dump方法用于将中间结果显示为16进制的形式。如将填充后的消息打印出来的dump方法如下:

private void dump()
	{
		System.out.println("========开始打印========");
		try{
			byte bts[] = this.PaddingMessage.getBytes(this.charset);		
			for(int i = 0; i < bts.length; i ++)
			{
				if(i%16 != 0 && i%2 == 0 && i != 0){
					System.out.print("  ");
				}
				if(i%16 == 0 && i != 0){
					System.out.println();
				}
				System.out.printf("%02x", bts[i]);
			}
		}catch(Exception e){
			System.out.println("Error Catch");
		}
		System.out.println("\n========结束打印========");
}

在输入消息为“abc”的情况下,打印填充后的消息的十六进制形式如下所示:
其中开头的616263是字母abc对应的ASCII码,80是填充消息时附加的比特位1,该比特位与后面填充的比特位0,构成了二进制1000 0000,所以对应的十六进制是80。最后的18也是十六进制形式,对应的十进制是24,表示消息的长度是24位。

由于在使用Java编写SM3算法时,计算的中间结果有字符串、整型数组等多种类型,为方便查看对应数据的十六进制形式,编写了多个dump方法,用于打印各种类型的数据。

/* 将字符串输出为16进制形式 */
private static void dump(String str)

/* 将整型数组输出为16进制形式 */
private static void dump(int nums[])

3.3 遇到的错误及解决方案

3.3.1. 循环左移计算结果偶尔不正确

在Java中,只有按位左移<<操作符,按位左移溢出的比特位直接丢弃,而SM3算法需要的循环左移需要将溢出的比特位存储到操作数最右边。

在实现循环左移时,假设要移位的32位比特位的数据为Y,则循环左移位可以分为三步:
①把Y按位左移k位的值赋值为l,此时l最右边的k位为0;
②把Y按位右移(32-k)位的值赋值为r,此时r左边的(32-k)位为0;
③将l和r进行按位或运算,即得到循环左移后的结果。
例如将0x1234 5678按位左移8位,则Y左移8位得到 l=0x3456 7800,Y右移32-8=24位得到r=0x0000 0012,最后将l和r进行按位或运算得到最终结果0x34567812

循环左移的实现过程如下:

// 将x循环左移N位
   private static int CircleLeftShift(int x, int N)
   {
   	return (x << N) | (x >> (32 - N));
   }

在使用此方法进行按位左移时,发现偶尔计算出来的结果与预期不符合。经过调试,发现是在按位右移时没有得到预期的结果,导致最终循环左移结果出错。具体原因及分析如下:

按位左移是直接在右边补0,而按位右移分为两种情况,一种是逻辑右移(有符号移位),一种是算术右移(无符号移位)。

逻辑右移是当最高位为0是,说明这是一个正数,右移时在最左边补0;当最高位为1时,说明这是一个负数,负数在计算机中以补码形式存储,所以逻辑右移时在最左边补1

而算术左移在移位时忽略符号位,即无论最高位是0还是1,都往最左边补0

在SM3算法中,需要的是算术右移。而在Java的语法中,>>是逻辑右移,>>>是算术右移。最初使用逻辑右移,导致循环左移最高位为1的数时运算结果与期望值不符。
修改后的循环左移方法如下:

// 将x循环左移N位
	private static int CircleLeftShift(int x, int N)
	{
		return (x << N) | (x >>> (32 - N));
	}

3.3.2. 填充消息时附加比特位1结果不对

根据算法的计算步骤,填充消息时,首先在消息后面附上一个比特位1。在实现算法时,由于用户输入的都是以字节为单位的字符串,所以1之后填充的0的个数k肯定是符合7+8*Z的,其中Z为非负整数。所以可以附加一个比特位“1”的操作可以转化为附加二进制1000 0000。实现代码如下:

padding += (byte)0x80;	// 先填充一个“1000 0000”

其中padding是一个字符串类型的数据,用于存储附加的数据。填充完比特位1、k个0以及消息长度后,将填充后的消息打印出来,如下:

测试时输入的消息依旧是abc,理论上得到的是6162 6380 0000 0000 .....,将消息c63后的十六进制位2d 3132 38与ASCII表对照,发现是-128。原因很明确,byte类型的0x80表示的数正是-128。而将-128与字符串padding进行 +=操作时,byte类型的数据被转换成字符串-128,所以得到上图的结果。

既然不能直接将byte类型的数据与字符串相连接,那可以尝试使用new String(byte[] bytes[])方法将一个byte数组转换成字符串。修改代码如下:

byte a[] = { (byte) 0x80 };
   padding += new String(a); // 先填充一个“1000 0000”

再次运行后结果还是不正确,如下图所示:

结果显示原本的0x80变成了0x3f。经过测试发现,0x01最后会得到0x010x02会得到0x020x7f也会得到0x7f,只有当大于0x7f是结果才会不正确,而且得到的都是0x3f

在网上搜索之后,得出错误的原因:ASCII是每个字节对应一个字符,一个字节的表示范围是-128127,而ASCII只对0127这个范围进行了编码。也就是每个字节最大值是0x7f,用二进制表示就是最高位为0。上面的0x80的二进制位是1000 0000,最高位是1,不在ASCII编码的范围之内。Java使用的是Unicode字符集,当进行将0x80转换成字符时,Java在Unicode代码页中查询不到对应的字符,Java会默认返回一个0x3f。所以上面试验中,小于0x80的byte可以正确转换成字符串,而大于等于0x80的byte数据将会返回0x3f.

解决方法是将byte数组转化成字符串时设置编码为“ISO-8859-1”。ISO-8859-1是按字节编码的,并且它对0~255的空间都进行了编码,所在在转换时它能够正确的将0x80转换为字符串。实现代码如下:

byte a[] = {(byte)0x80};
padding += new String(a, charset);

其中第二个参数charset是在最前面定义的字符集,它是一个字符串“ISO-8859-1”。再次运行并打印填充后的消息,发现结果跟预期一致:

3.3.3. 迭代时结果出错

在进行迭代的时候,导出了迭代前的数据,包括Wj,Wj′等,都与课本上的示例一样。说明迭代前的步骤已经正确的完成。迭代后的结果却不正确,说明错误出现在迭代这里。将中间结果ABCDEFGH导出后与课本上的对照,发现最开始出错的位置是G0,而G0之前的A-F都是正确的。
课本上的:

实验中的:

查看课本上的算法G赋值的位置,算法如下:

G ← F <<< 9

此时怀疑移位算法是否编写正确,经过手算移位算法后,发现结果和实验中的显示的一样。对照国家密码管理局发布《SM3密码杂凑算法》发现,课本上的算法不对,正确的移位数应该是19,即:

G ← F <<< 19

修改为正确的移位数后再次运行,发现结果与课本上的一致,SM3密码算法完成。哈希结果如下:
66c7f0f462eeedd9d1f2d46bdc10e4e24167c4875cf2f7a2297da02b8f4ba8e0

About

密码学作业、课程设计:国产加密算法SM3的java实现

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages