首页 > 其他分享 >52 Things: Number 20: How are Merkle-Damgaard style hash functions constructed?

52 Things: Number 20: How are Merkle-Damgaard style hash functions constructed?

时间:2024-04-11 23:33:33浏览次数:38  
标签:function Damgaard style 20 函数 MD Merkle hash compression

52 Things: Number 20: How are Merkle-Damgaard style hash functions constructed?

52件事:第20件:Merkle-Damgaard风格的散列函数是如何构建的?

  This is the latest in a series of blog posts to address the list of '52 Things Every PhD Student Should Know' to do Cryptography: a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year. To finish the basic schemes section, we look at one of the most popular hash function designs...
这是一系列博客文章中的最新一篇,旨在解决“每个博士生都应该知道的52件事”做密码学:这是一组问题,旨在让博士生在第一年结束时了解他们应该知道什么。为了完成基本方案部分,我们来看看最流行的哈希函数设计之一。。。
  A Merkle-Damgaard (MD) hash function is a hash function built by extending the domain of a collision-resistant compression function that preserves the collision resistance. This means we can take a small (and fixed) width compression function, prove it is secure and then use it to make a variable length hash function.  Whilst other methods for building hash functions exist, MD is by far the most "popular" (well, most frequently used at least!), with examples including MD5,SHA1 and SHA2. So, time to break those terms down:
Merkle-Damgaard(MD)散列函数是通过扩展保持碰撞阻力的抗碰撞压缩函数的域而构建的散列函数。这意味着我们可以使用一个小(固定)宽度的压缩函数,证明它是安全的,然后使用它来生成一个可变长度的哈希函数。虽然存在其他构建哈希函数的方法,但MD是迄今为止最“流行”的(嗯,至少是最频繁使用的!),示例包括MD5、SHA1和SHA2。所以,是时候分解这些术语了:  

Secure Hash Function? 安全散列函数?

Traditionally, a secure hash function h should be:
传统上,安全散列函数 h 应该是:
  • Pre-image resistant: given h(x), it is hard to find x.
    抗预镜像:给定 h(x) ,很难找到 x 。
  • Second pre-image resistance: given x, it is hard to find y such that h(x)=h(y).
    第二个预镜像阻力:给定 x ,很难找到 y 这样的 h(x)=h(y) 。
  • Collision Resistance: It is hard to find x,y such that h(x)=h(y).
    抗碰撞性:很难找到 x,y 这样的 h(x)=h(y) 。
If a hash function is collision then clearly it must be second pre-image resistant, so it is this [collision resistance] that we will focus on.
如果一个哈希函数是冲突的,那么很明显它必须是第二个图像前的抗冲突函数,所以我们将重点关注这个[抗冲突]。

Compression Function 压缩功能

compression function f:{0,1}n×{0,1}r→{0,1}n is a function that, as the name suggest, compresses n+b-bits worth of input into an n-bit output. As you might expect, a collision resistant compression function is a compression function that is collision resistant. So, it can be thought of as a fixed input length hash function, but what happens if we want our hash function to be secure for any input length?
压缩函数 f:{0,1}n×{0,1}r→{0,1}n 是一个函数,顾名思义,它将 n+b 比特的输入压缩为 n 比特的输出。正如您所期望的,抗碰撞压缩函数是一种抗碰撞的压缩函数。因此,它可以被认为是一个固定输入长度的哈希函数,但如果我们希望我们的哈希函数对任何输入长度都是安全的,会发生什么?

The MD hash function construction
MD散列函数的构造

The MD construction provides a method for extending the domain of a fixed length compression function into a variable input length hash function. Using a compression function f as above, we are going to use the n-bit value as our internal state, and feed in r-bits each iteration (it's quite common to set r=n). To do this, we begin with an initial value (IV) and split the message M up into blocks of r bits M=M0M1⋯Mm, and then simply iterate the construction by setting:
MD结构提供了一种将固定长度压缩函数的域扩展为可变输入长度散列函数的方法。使用上面的压缩函数 f ,我们将使用 n 比特值作为内部状态,并在每次迭代中输入 r 比特(设置 r=n 是很常见的)。要做到这一点,我们从初始值(IV)开始,将消息#4分解为 r 比特 M=M0M1⋯Mm 的块,然后通过设置简单地迭代构建:
S0:=IV;i=0,…,m−1:Si+1=f(Si,Mi);h(M):=Sm
Confused? Perhaps the the following diagram will help:
困惑的也许下图会有所帮助:
Diagram of the MD construction (from Wikipedia)
MD结构图(来自维基百科)
The most important thing about the MD-construction is that if the compression function is collision resistant, then so is the overall construction (as proven by Merkle). This gives us a secure method for building hash functions out of a smaller, easier studied primitives.
MD结构最重要的一点是,如果压缩功能是抗碰撞的,那么整体结构也是如此(正如Merkle所证明的)。这为我们提供了一种安全的方法,可以用更小、更容易研究的基元构建哈希函数。

Length Extension 长度延伸

You might notice that the diagram has an extra stage that my description didn't: the "finalisation" stage. This is to prevent length extension attacks. For an example, if N is a single block (ie N∈{0,1}r) if the attacker knows h(M)=x, then he can very easily calculate h(M||N), because h(M||N)=f(M,N). So, some form of finalisation function has to be used to break this relationship.
你可能会注意到,这个图表有一个我描述中没有的额外阶段:“最终确定”阶段。这是为了防止长度扩展攻击。例如,如果 N 是单个块(即 N∈{0,1}r ),如果攻击者知道 h(M)=x ,那么他可以非常容易地计算 h(M||N) ,因为#4。因此,必须使用某种形式的最终确定函数来打破这种关系。

标签:function,Damgaard,style,20,函数,MD,Merkle,hash,compression
From: https://www.cnblogs.com/3cH0-Nu1L/p/18106102

相关文章

  • 2024年3月文章一览
    2024年3月编程人总共更新了12篇文章:1.2024年2月文章一览2.ProgrammingAbstractionsinC阅读笔记:p308-p3113.ProgrammingAbstractionsinC阅读笔记:p312-p3264.ProgrammingAbstractionsinC阅读笔记:p327-p3305.ProgrammingAbstractionsinC阅读笔记:p331-p3376.《自动......
  • vite+xlsx-style表格导出样式设置报错
    项目是vite+vue3,前端表格导出,使用xlsx可以导出基本表格,但是想要设置表格样式,引入xlsx-style,安装依赖,后引入报错引用import { utils } from "xlsx"import { write } from "xlsx-style"Couldnotresolve"./cptable"node_modules/xlsx-style/dist/cpexce......
  • Maya 2019.2 Mtoa 无法正常加载并报错
    事件起因:在开始安装Maya2019.2时自动安装的Mtoa的版本为5.3.1,但是在插件管理器里无法启用插件,于是乎去网上下了一个低的版本5.1.1,虽然可以使用但是渲染出来的东西不能用;于是乎我又去网上下载了同样的5.3.1的独立安装包,然后安装破解(注意,这里有个坑,后续揭晓为什么),但是并无......
  • #6912. 「梦熊省选难度挑战赛 2023」奇迹之夜
    #6912.「梦熊省选难度挑战赛2023」奇迹之夜树形dp调的好折磨。距离小于交通范围\(L\)的一定是举办聚会,所以可以预处理出\(g_i\)表示深度小于\(i\)的都开聚会的总人气和。其次可以建聚会时一定也能建日常活动,所以直接\(w_i=\max(w_i,m_i)\),方便转移。对于大于等于\(......
  • 地铁 2033 重制版全成就攻略
    汉化教程:https://www.bilibili.com/video/BV1J14y1m7Ys/?spm_id_from=333.337.search-card.all.click&vd_source=cab44df4107f3ff939a34437ecc16887全成就:1.Tank(坦克)Kill10Enemiesinarowwithouttakinganydamage.在不受任何伤害的情况下连续杀死10个敌人。2.De......
  • 2024.04.11 树上问题回顾
    2024.04.11树上问题回顾P2015二叉苹果树树形背包板子题。需要注意的是,枚举儿子\(v\)的选择数量\(k\)时,一定要先转移\(k=0\)的情况,否则就会用新状态来重复更新新状态,违背\(0/1\)背包的思路。#include<bits/stdc++.h>usingnamespacestd;template<typenameT>in......
  • 2024/4/11
    今天大盘低开高走下午又低走,收红出上影线,这个反弹时之前预见的--市场连续下跌且到3000附件,又反弹的需求,高开低走且缩量,说明市场信心不足,调整大概率没有到位今天要批评一下自己,昨天明确说了大盘没有企稳,不要开仓,但是今天一反弹,尤其时工程机械汽车板块 东方电气快速拉升,因为前面......
  • Java基础学习 | 2024年4月11日
    变量1.类变量(静态变量):前面用static修饰,表示所有子类都共用同一个属性值,可以直接用类名来访问静态变量,也可以通过实例名来访问静态变量。即无论创建多少个类实例,静态变量在内存中只有一份拷贝,被所有实例共享。举例:点击查看代码publicclassMyClass{publicstaticintc......
  • 2024.4.11
    2024.4.11【虚怀若谷,戒骄戒躁。】Thursday三月初三<theme=oi-"language">这个好东西叫pb_ds!!!#include<bits/extc++.h>usingnamespace__gnu_cxx;usingnamespace__gnu_pbds;堆操作/数据结构配对堆二叉堆左偏树二项堆斐波那契堆代码pairing_heap_t......
  • P9352 [JOI 2023 Final] Cat Exercise
    P9352[JOI2023Final]CatExercise树形dp+trick+并查集若我们以当前猫在的位置\(u\)为根,那么猫的下一步移动就会走到其中一个子树中。猫只有在我们把障碍放到当前的位置时才会移动,所以一定无法回到\(u\)点。要指定进入某个子树,只需要把其他子树都堵住即可。考虑树形dp......