首页 > 其他分享 >利用Pollard rho进行哈希碰撞(Polladr rho method to fing collision)

利用Pollard rho进行哈希碰撞(Polladr rho method to fing collision)

时间:2023-07-19 19:34:17浏览次数:32  
标签:Polladr collision 碰撞 Pollard 哈希 rho method 指针

项目实现:implement the Rho method of reduced SM3
实验内容:该实验设计f函数为\(f: H(x)\),即\(W_i = H(W_{i - 1})\)(除第一次输入信息\(m\)外,f函数输入输出均为256bit)
Polladr rho method to fing collision:利用了生日悖论,使碰撞的复杂度降到\(O(\sqrt n)\)级别,同时能有效避免内存过大
其思想是:利用\(f\)函数随机游走,构造出随机序列,可以发现,该序列发展到一定程度,会得到与之前相同的元素,形成环。因此可以应用到哈希函数中。
如何找环?如何找到进入环的元素(即找到哈希碰撞)?可以通过Floyd判圈法,规定两个指针,其中一个按照序列一步一步走,另外一个两步两步走。当两者相遇时,即找到了一个环,此时找到进入环的元素的两个前驱,即可找到一对碰撞。
如何找到刚进入环的元素?定义两个指针,一个指向初始信息\(m\),另外一个指向上一步两个指针相遇的点\(h\),两个指针都是一步一步走,最后相遇的点即为第一次进入环的点。
值得注意的是,要避免信息\(m\)在环上,因此初始值要大于256bit

标签:Polladr,collision,碰撞,Pollard,哈希,rho,method,指针
From: https://www.cnblogs.com/tpgzy/p/17566533.html

相关文章

  • Pollard-Rho 分解算法学习笔记
    Pollard-Rho分解算法Pollard-Rho算法是一种用于快速找到\(n\)的一个非平凡约数的方法。生日悖论在不少于\(23\)个人中至少有两人生日相同的概率已经大于\(50\%\)。更一般的形式,随机选取在\(\left[1,N\right]\)范围内的整数,期望到第\(O(\sqrt{N})\)个出现重复。用下面的方......
  • [atAGC062D]Walk Around Neighborhood
    记\(D=\max_{1\lei\len}d_{i}\),则无解当且仅当\(2D>\sum_{i=1}^{n}d_{i}\)结论:\(\forall(x,y),\exists(X,Y),\begin{cases}|X|+|Y|=R\\|x-X|+|y-Y|=d\end{cases}\)当且仅当\(|r-R|\led\ler+R\)(其中\(r=|x|+|y|\))必要性:根据\(|a|-|b|\le|a-b|\le|a|+|b......
  • 【阅读笔记】Anchored Neighborhood Regression for Fast Example-Based uper Resolut
    论文信息[AnchoredNeighborhoodRegressionforFastExample-BaseduperResolution]-TIMOFTER,2013,IEEEInternationalConferenceonComputerVision前置内容邻域嵌入(NeighborEmbedding,NE)是“样本-样本”映射,在训练样本中寻找测试样本的相似邻居特征样本,计算量略大。......
  • pollard_rho大数分解Java版
    代码:importjava.math.BigInteger;importjava.security.SecureRandom;classPollardRho{privatefinalstaticBigIntegerZERO=newBigInteger("0");privatefinalstaticBigIntegerONE=newBigInteger("1");privatefina......
  • Atcoder Grand Contest 062 D - Walk Around Neighborhood
    csy/bxwjz/bx首先将\(a\)排序,如果\(\sum\limits_{i=1}^{n-1}a_i<a_n\)显然就是\(-1\),否则必然有解。先发现一个trivial的事情,就是答案一定位于\([\dfrac{a_n}{2},a_n]\)中,这是因为我们判掉无解的条件之后,我们必然可以用前面的步数走到以\((a_n,0),(0,a_n),(-a_n,0),(......
  • May 2022-Neighborhood Mixup Experience Replay: Local Convex Interpolation for Im
    摘要:经验回放在提高深度强化学习智能体的样本效率方面起着至关重要的作用。经验回放的最新进展建议使用Mixup-2018,通过合成样本生成进一步提高样本效率。在这种技术的基础上,提出了邻域混合经验回放(NMER),一种基于几何的回放缓冲区,用状态-动作空间中最近邻的转换进行插值。NMER仅......
  • SEDCN:Structure enhanced deep clustering network via a weighted neighbourhood a
    论文阅读08-SEDCN:Structureenhanceddeepclusteringnetworkviaaweightedneighbourhoodauto-encoder论文信息论文地址:Structureenhanceddeepclusteringnetworkviaaweightedneighbourhoodauto-encoder-ScienceDirect代码地址:m22453/sedcn-nn(github.com)1.......
  • C: print rhombus
     #include<stdio.h>#include"math.h"#include"stdlib.h"#include"unistd.h"intmain(void){inth,line,t;scanf("%i",&h);for(intv=h......
  • Qt-Qt之剪切板、热键应用(QClipboard、RegisterHotKey)
     .pro1QT+=coregui23greaterThan(QT_MAJOR_VERSION,4):QT+=widgets45CONFIG+=c++1167#Thefollowingdefinemakesyourcompi......
  • Pollard-Rho 算法总结
    \(\gcd(|x_i-x_j|,n)\)暴力枚举\(i,j\)复杂度过高,于是构造伪随机函数,根据伪随机函数的性质枚举一个\(j-i=d\)相当于判掉所有距离为\(d\)的\(i',j'\),但枚举的\(i\)......