blocks|key|790921|text|type|unstyled|depth|inlineStyleRanges|entityRanges|data|entityMap^0^^$0|@$1|2|3|-4|4|5|6|B|7|@]|8|@]|9|$]]]|A|$]]

The main conceptual trick here is the one used over and over in cryptography proofs, known as "reduction". Suppose that you have a problem $A$, which is assumed to be a "hard problem". You want to show that another problem $B$ is also a "hard problem". To do that, you imagine that you have some machine or system that can solve $B$; and from that machine or system, you build a solver for problem $A$; that new solver uses the solver for $B$ as an elementary block box. If you can do that, i.e. solve $A$ as long as you have access to a solver for $B$, then this shows that solving $B$ must be hard: an easy solver for $B$, used in your construction, will become an easy solver for $A$, which contradicts the hypothesis of $A$ being a hard problem.

I'll take an example with square roots modulo a big non-prime integer. This is an example meant to explain how a problem $A$ is reduced into a problem $B$, and vice versa. To follow this example, you don't need to fully understand the details of the involved algebra; what matters here is that we make solvers for some problems based on solvers for other problems.

Suppose that you have $n = pq$, where $p$ and $q$ are two unknown and big prime integers; you only have their product $n$. Finding $p$ and $q$ from $n$ is a hard problem; it is called <a href="https://en.wikipedia.org/wiki/Integer_factorization" rel="nofollow noreferrer">integer factorization</a>, and mathematicians have looked for efficient ways to do that for more than 2500 years, and they still don't know how to do it for large integers (current record is for a 768-bit integer $n$). This integer factorization is the problem $A$. We assume that it is hard.

Now consider the problem $B$: from an integer $x$ such that $1 &lt; x &lt; n$, find an integer $y$ such that $y^2 = x \bmod n$. This is basically finding a square root of $x$ modulo $n$; about 1/4th of integers $x$ in the $1..n-1$ range admit square roots, and if $x$ has a square root, then it will (usually) have four distinct square roots. We want to show that, in all generality, $B$ is a hard problem.

Suppose, then, that you have some system $S$ that can find a square root for any input $x$ (for any $x$ that has square roots, that is). We can then build a new system, that uses $S$, and can be used to factor $n$. It works in the following way:

<ul>
<li>Generate a random value $k$ in the $q$ to $n-1$ range.</li>
<li>Compute $t = k^2 \bmod n$.</li>
<li>Invoke the system $S$ on $t$. We build that $t$ as a square, thus it has square roots, and we already know two of them, which are $k$ and $n-k$. The system $S$ will return one of the four square roots of $t$; let's call it $u$.</li>
<li>If $u = k$ or $u = n-k$, we were unlucky. This happens half of the time. Start again with a new random $k$.</li>
<li>Otherwise, compute the <a href="https://en.wikipedia.org/wiki/Greatest_common_divisor" rel="nofollow noreferrer">Greatest Common Divisor</a> of $n$ and $u+k$. This GCD will be either $p$ or $q$ with very high probability.</li>
</ul>

This algorithm shows how to factor a big integer $n$, provided that a square root extractor (system $S$) modulo $n$ is made available. Since integer factorization is hard, this should not be feasible.

The same concept works in the other direction in that case. What the algorithm above shows is that extracting square roots modulo $n$ cannot be easier than factorizing $n$. In the other direction, we can show that factorizing $n$ cannot be easier than extracting square roots modulo $n$: suppose that you have a machine or system $F$ that can factor big integers. Now, given an integer $n$ and an input $x$ for which you are challenged with finding a square root, you can do the following:

<ul>
<li>Call $F$ on the integer $n$ to get its factors $p$ and $q$.</li>
<li>Compute the square roots $y_p$ and $y_q$ of $x$ modulo $p$ and $q$, respectively. Modulo a prime, square root extraction is easily done with the <a href="https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm" rel="nofollow noreferrer">Tonelli-Shanks algorithm</a>.</li>
<li>Recombine $y_p$ and $y_q$ into a square root $y$ for $x$ modulo $n$, using the <a href="https://en.wikipedia.org/wiki/Chinese_remainder_theorem" rel="nofollow noreferrer">Chinese Remainder Theorem</a>.</li>
</ul>

Thus, if you can factor integers, you can extract square roots. Therefore, integer factorization cannot be easier to do than extracting square roots: whenever you find an efficient way to factor integers, the algorithm above can be used to turn that into an equally efficient way to extract square roots.

Since integer factorization is not harder than extracting square roots, and extracting square roots is not harder than integer factorization, then both problems are equivalent. In particular, they must be either both hard, or both easy (in practice, as far as we know, they are both hard).

<hr />

Now back you your problem of hash functions. You have a given hash function $H$, and it is assumed to be collision-resistant. This means that the "problem $A$" is about finding a collision for $H$: find $m$ and $m'$ such that $m \neq m'$ but $H(m) = H(m')$. The exercise supposes that problem $A$ is hard.

Now, problem $B$ is about the collision resistance of $G$: you are challenged with finding $m$ and $m'$ such that $m \neq m'$, but $G(m) = G(m')$. The goal of the exercise is to show that $G$ is collision-resistant, i.e. that problem $B$ is hard.

Therefore, the way to do it is to make a reduction: you first suppose that you have a solver for $B$, i.e. a way to make a collision for the hash function $G$. You want to show how you can use such a solver in order to make a solution for problem $A$, i.e. finding a collision for the hash function $H$. By describing such a method, you show that finding a collision for $G$ cannot be easier than finding a collision for $H$. Since $H$ was supposed to be collision-resistant, it follows that $G$ is also collision-resistant.

All you have to do, therefore, is to find out how a collision for $G$ can be turned into a collision for $H$ (and that I leave as an exercise, because the whole point is to have you find it by yourself).

Problem: Hash functions derived from another hash function (4 marks) Suppose that $H:\{0,1\}^* \rightarrow \{0,1\}^n$ is a collision resistant hash function. Define a new hash function by $G:\{0,1\}^* \rightarrow \{0,1\}^n$ such that $G(x) = H(H(x)).$ Prove tht $G$ is also collision resistant

<hr>

I'm trying to figure out how to solve this, apparently, it's hashing the hash value itself. So G has two rounds of hashing the original message x. I tried searching for the relationship properties that I could use to achieve this

<ul>
<li>Collision resistance implies 2nd-preimage resistance </li>
<li>If the output values of are uniformly distributed, then collision resistance implies preimage resistance </li>
<li>If the output values of are uniformly distributed, then 2nd-preimage resistance implies preimage resistance </li>
<li>Preimage resistance does not imply 2nd-preimage resistance </li>
<li>2nd-preimage resistance does not imply collision resistance</li>
</ul>

But I didn't find anything I could use, I'm really having trouble, so I'd appreciate any help.

How to derive a hash function from another hash function?

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云AI代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

功能1上新10个字符

功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符。

功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符。

功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符

功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符

功能4上新

文章&问答评论现已支持表情

全新交互，全新视觉，新增快捷键、悬浮工具栏、高亮块等功能并同时优化现有功能，全面提升创作效率和体验

社区富文本编辑器全新改版！诚邀体验～ 

精选全网热门MCP server，让你的AI更好用 🚀

💥开发者 MCP广场重磅上线！

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

社区新版编辑器体验调研

问题：派生自另一个哈希函数(4个标记)的<#>Hash函数，假设H:\{0,1\}^* \rightarrow \{0,1\}^n是一个抗碰撞的散列函数。通过G:\{0,1\}^* \rightarrow \{0,1\}^n定义一个新的哈希函数，这样G(x) = H(H(x)).就可以证明tht G也是抗碰撞的。我试着想办法解决这个问题，很明显，它本身就是哈希值。因此G有两轮哈希原始消息x。碰撞阻

问如何从另一个哈希函数派生哈希函数？
EN

回答 1

Cryptography用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问如何从另一个哈希函数派生哈希函数？EN