Java构建HashCode相同字符串算法

import java.math.BigDecimal;  
import java.util.Random;  

/**
“中间相遇法”是生日攻击的一种变形，它不比较Hash值，而是比较链中的中间变量。这种攻击主要适用于攻击具有分组链结构的Hash方案。中间相遇攻击的基本原理为：将消息分成两部分，对伪造消息的第一部分从初试值开始逐步向中间阶段产生r1个变量；对伪造消息的第二部分从Hash结果开始逐步退回中间阶段产生r2个变量。在中间阶段有一个匹配的概率与生日攻击成功的概率一样。
*/  
public class HashCollide {  
  
    /** 
     * 拼凑字符的起始值(最后实际值可能为 collideCharBase +- mulBase) 
     */  
    private int collideCharBase;  
  
    /** 
     * 中间变量 
     */  
    private BigDecimal collideCharBase_decimal;  
  
    /** 
     * 中间变量 
     */  
    private BigDecimal mulBase_decimal_pow;  
  
    /** 
     * 拼凑字符串长度 
     */  
    private int collideCharLength;  
  
    /** 
     * hash算法中采用的乘积值 (hash' = hash * mulBase + char[i]) 
     */  
    private long mulBase;  
  
    /** 
     * 中间变量 
     */  
    private BigDecimal mulBase_decimal;  
  
    /** 
     * 中间变量 
     */  
    private long mulBase_desc;  
  
    /** 
     * 中间变量 
     */  
    private BigDecimal mulBase_desc_decimal;  
  
    /** 
     * 2的轮回... 
     */  
    private final long INT_ROUTE_NUMBER = 2l << 32;  
  
    /** 
     * 还是2的轮回... 
     */  
    private final BigDecimal DECIMAL_ROUTE_NUMBER = new BigDecimal(  
            INT_ROUTE_NUMBER);  
  
    /** 
     * 不知道干啥的,好奇怪 
     */  
    private final Random random = new Random(System.nanoTime());  
  
    /** 
     * 测试你的char数组能吧srcHash变成什么样子 
     *  
     * @param srcHash 
     * @param collide 
     * @return 
     */  
    public int hashCodeTest(int srcHash, char collide[]) {  
        int h = srcHash;  
        int len = collide.length;  
        for (int i = 0; i < len; i++) {  
            h = (int) mulBase * h + collide[i];  
        }  
        return h;  
    }  
  
    /** 
     * 根据这个类构造时设置的参数输出hash 
     *  
     * @param srcString 
     * @return 
     */  
    public int hashCodeTest(String srcString) {  
        char[] chars = srcString.toCharArray();  
  
        int h = 0;  
        int len = chars.length;  
        for (int i = 0; i < len; i++) {  
            h = (int) mulBase * h + chars[i];  
        }  
        return h;  
    }  
  
    /** 
     * 将一个decimal的值通过取余转换成一个属于int范围的long 
     *  
     * @param data 
     * @return 
     */  
    private long fixDecimal(BigDecimal data) {  
        // 求余数  
        BigDecimal sub = data.divideToIntegralValue(DECIMAL_ROUTE_NUMBER  
                .multiply(DECIMAL_ROUTE_NUMBER));  
  
        // 可能为负数,修正为long类型之后再次求余  
        long val = data.subtract(sub).longValue();  
        val += INT_ROUTE_NUMBER;  
        val = val % INT_ROUTE_NUMBER;  
  
        if (val < 0) // val应该不会小于0  
            val += INT_ROUTE_NUMBER;  
        return val;  
    }  
  
    /** 
     * 把val转换为正序的char数组,用以表示一个n位k进制数据 
     *  
     * @param val 
     * @return 
     */  
    private char[] offsetToArray(long val) {  
        char[] stk = new char[collideCharLength];  
        int pos = 0;  
  
        while (val != 0) { // 进制转换,得到反序列  
            stk[pos++] = (char) (val % (mulBase) + collideCharBase);  
            val = val / mulBase;  
        }  
  
        int fillZero = collideCharLength - pos; // 补零的个数  
        char[] collides = new char[collideCharLength];  
        int i = 0;  
        while (i < fillZero) { // 高位补零  
            collides[i++] = (char) collideCharBase;  
        }  
  
        while (i < collideCharLength) { // 逐位反向输出  
            collides[i] = stk[pos - i + fillZero - 1]; // pos - ( i - fillZero )  
            ++i;  
        }  
  
        return collides;  
    }  
  
    /** 
     * 根据hash的src和target生成一组序列，使原串后面附加序列字符后的hash与target相同 
     *  
     * @param src 
     * @param target 
     * @param collideCharBase 
     * @param n 
     * @return 
     */  
    private char[] genCollisionArray(int src, int target) {  
        long hx = mulBase_desc * src + collideCharBase;  
        BigDecimal halfCal = mulBase_decimal_pow.multiply(new BigDecimal(hx)) // 中间变量  
                .subtract(collideCharBase_decimal);  
        BigDecimal left = halfCal.divide(mulBase_desc_decimal); // 依然是中间变量  
        BigDecimal fix = new BigDecimal(target).subtract(left); // 还是中间变量,不过这次是修正数据  
  
        long fixedDecimal = fixDecimal(fix);  
  
        return offsetToArray(fixedDecimal);  
    }  
  
    /** 
     * 构造函数 
     *  
     * @param collideCharBase 
     *            拼凑字符的起始值(最后实际值可能为 collideCharBase +- mulBase) 
     * @param collideCharLength 
     *            拼凑字符串长度 
     * @param mulBase 
     *            hash算法中采用的乘积值 (hash' = hash * mulBase + char[i]) 
     */  
    public HashCollide(int collideCharBase, int collideCharLength, int mulBase) {  
        this.mulBase = mulBase;  
        this.mulBase_decimal = new BigDecimal(mulBase);  
        this.mulBase_desc = mulBase - 1;  
        this.mulBase_desc_decimal = new BigDecimal(mulBase - 1);  
  
        this.mulBase_decimal_pow = mulBase_decimal.pow(collideCharLength);  
  
        this.collideCharBase = collideCharBase;  
        this.collideCharBase_decimal = new BigDecimal(collideCharBase);  
        this.collideCharLength = collideCharLength;  
  
    }  
  
    /** 
     * ... 
     *  
     * @param source 
     * @param targetHash 
     * @return 
     */  
    public String collide(String source, int targetHash) {  
        int hashSrc = source.hashCode();  
        char[] collide = this.genCollisionArray(hashSrc, targetHash);  
        return source.concat(new String(collide));  
    }  
  
    /** 
     * ... 
     *  
     * @return 
     */  
    public String randomString(int length) {  
        char[] chars = new char[length];  
        for (int i = 0; i < length; ++i) {  
            chars[i] = (char) (50 + random.nextInt(32 + 26 + 15));  
        }  
        return new String(chars);  
    }  
  
    public static void main(String[] args) {  
  
    	System.out.println("NH]n;<pFEP2R4DYDw4Fsg^Z[gTHIx=e4H:hSEVtfR^SqsP]y[gK_:gIgvZccbUmj".hashCode());
    	System.out.println("W@3Lb=SIr`\\h?KT5?ayLtd37y]x=\\Pcibr4O4SaKubhJ_M`lqEbjk;5ycYmZp^cm".hashCode());

    	System.out.println("====================");
    	
    	HashCollide collide = new HashCollide(85, 7, 31);  
    	
    	for (int i = 0; i < 10000; ++i) {  
    		
    		String a = collide.randomString(57);  
    		String b = collide.collide(a, 912366222);  
    		System.out.println(b);  
    		
    		if (b.hashCode() != 912366222) {  
    			System.err.println("ERROR :: src = " + a);  
    			System.err.println("ERROR :: dst = " + b); 
    			System.exit(1);  
    		}
    	}
    	  
    }  

JDK String.hashCode()

  

 /**
     * Returns a hash code for this string. The hash code for a
     * <code>String</code> object is computed as
     * <blockquote><pre>
     * s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
     * </pre></blockquote>
     * using <code>int</code> arithmetic, where <code>s[i]</code> is the
     * <i>i</i>th character of the string, <code>n</code> is the length of
     * the string, and <code>^</code> indicates exponentiation.
     * (The hash value of the empty string is zero.)
     *
     * @return  a hash code value for this object.
     */
    public int hashCode() {
	int h = hash;
	if (h == 0) {
	    int off = offset;
	    char val[] = value;
	    int len = count;

            for (int i = 0; i < len; i++) {
                h = 31*h + val[off++]; //31 上文构造方法参数mulBase
            }
            hash = h;
        }
        return h;
    }

评论

1 楼 yzjdt 2019-05-24  

请问一下，这个代码我看了半天，也debug研究了一下，为什么collideCharLength（拼凑字符串的长度），一定不能小于7呢？