网络安全导论 实验5B Hash函数与工作量证明

实验5BHash函数与工作量证明一、实验目的掌握Hash函数的构造方法。掌握如何在Java中调用安全Hash函数。体会求解Hash原像的难度与工作量。二、实验准备1、Hash函数的构造准则：简单、均匀。分段叠加法、迭代法、伪随机数法等是最基本的构造方法。如何构造一个“好”的Hash函数具有很强的技术性和实践性，这里的“好”是指构造简单并且产生的碰撞少。2、已知哈希函数H、一个值v、以及目标范围T，寻找x，使得H(v||x)∈T。如果哈希函数H的输出为n比特，那么输出值可以是任何一个0~2n-1范围内的值，可以定义T为0~2k

(k<n)范围内的值。目标范围T的大小决定了解这个谜题的求解难度。如果T包含所有n比特长的串，即k=n,那么求解等价于计算一次哈希值；如果T只包含一个元素，即k=1，则这个求解是最难的，相当于给定一个哈希值，找出其中的一个原像。一般的，k越小，求解花费的时间越长。求解上述问题便形成了工作量证明，工作量证明可以用于对付垃圾邮件发送者、拒绝服务攻击以及设计密码货币的共识算法。三、实验内容1、键盘任意输入一行字符串，分别按照如下方法计算其hash值，给出完整的java程序。（1）publiclongDJBHash(Stringstr)

{longhash=5381;

for(inti=0;i<str.length();i++)

{hash=((hash<<5)+hash)+str.charAt(i);

}

returnhash;

}publiclongSDBMHash(Stringstr)

{

longhash=0;

for(inti=0;i<str.length();i++)

{hash=str.charAt(i)+(hash<<6)+(hash<<16)-hash;

}

returnhash;

}2、参照如下代码，调用已经集成的Hash算法的java.security.MessageDigest类，给出“thisisatest”的消息摘要。importjava.io.UnsupportedEncodingException;

importjava.security.MessageDigest;

importjava.security.NoSuchAlgorithmException;publicclassSha256{

/*利用java原生的类实现SHA256报文摘要

*/

publicstaticStringgetSHA256(Stringstr){

MessageDigestmessageDigest;

Stringencodestr="";

try{

messageDigest=MessageDigest.getInstance("SHA-256");

messageDigest.update(str.getBytes("UTF-8"));

encodestr=byte2Hex(messageDigest.digest());

}catch(NoSuchAlgorithmExceptione){

e.printStackTrace();

}catch(UnsupportedEncodingExceptione){

e.printStackTrace();

}

returnencodestr;

}

/*将byte转为16进制

*/

privatestaticStringbyte2Hex(byte[]bytes){

StringBufferstringBuffer=newStringBuffer();

Stringtemp=null;

for(inti=0;i<bytes.length;i++){

temp=Integer.toHexString(bytes[i]&0xFF);

if(temp.length()==1){

//1得到一位的进行补0操作

stringBuffer.append("0");

}

stringBuffer.append(temp);

}

returnstringBuffer.toString();

}}3、工作量证明

使用SHA—256,按照如下步骤，找出一个满足条件的x。要求写出完整的java代码，给出程序的运行时间。步骤1、d=1，

v=你的学号或姓名步骤2、

从x=1出发，增加x的值并转化为对应的串x，直到HASH（v||x）<SHR(2n-1,d*4)

，这里

SHR(h,k)表示对无符号数h右移k位；

d是以16进制位表示的前缀0的个数）

步骤3、记下这时的x的值步骤4、取d=2,3，重复2~4次。四、实验报告1、通过实验回答下列问题（1）给出实验1和2的完整程序和实验结果实验1：第一部分：代码截图：运行结果：第二部分：代码截图：运行结果：实验2：代码截图：运行结果：解释实验3中d的作用。实验中d的数值由1变为2-4的作用为：随着d的增加，要找到x使得HASH（v||x）<SHR(2n-1,d*4)变得越困难，程序的计算量就不断增大，求得的x值有很大概率会一直增加，所花费的时间也会相应地上升。随着d的增大，hash值的范围越来越小，从而导致要寻找的x落入hash值范围越来越难，从而提高程序工作量。2、问答题（1）Hash函数的构造方法有哪些？密码用的安全Hash函数有哪些要求？哈希函数构造主要有以下几种：1：直接寻址法；2：取模法；3：数字分析法；4：折叠法；5：平方取中法；6：除留余数法；7：随机数法。密码学哈希函数H应满足如下的要求：(1)压缩：x任意长，H(x)固定长；(2)容易从x计算出H(x)；(3)抗原像攻击：已知y∈Y，要找出x∈X，使得H(x)=y是困难的；(4)抗第二原像攻击：已知x∈X，找出另一个x'∈X，使得H(x')=H(x)是困难的；(5)抗碰撞性：找出任意两个不同的x,x'∈X，使得H(x)=H(x')是困难的。（2）为什么基于哈希函数的谜题问题可以用于设计对付垃圾邮件的发送和拒绝服务攻击这样的系统？在上述哈希函数构造的谜题问题中可以发现，当d的值很小时，并不会给计算机造成太大的计算负担，而随着d的增加，计算机的计算负担不断上升，工作量大幅度上升甚至影响系统的正常运行。基于以上原理，可以这样设计一个对付垃圾邮件的发送和拒绝服务攻击的系统：当一台计算机要发送某些消息（例如邮件、SYN请求等）时，消息系统要求发送方计算出一个满足一定范围的哈希值，并且规定：（1）在计算完成之前不允许发送方发送消息；（2）在一定的周期内，发送方首次要求发送消息，系统要求哈希值