RSA 来构造一个散列函数。将输入 m 分为 k 个分组,即 m=m1m2…mk,RSA 公钥为(e,n),定义散列函数如下: 112.jpg 其中 h1=m1,最后一个分组的输出 hk 为输出的散列码。试问如此构造的散列函数安全吗?为什么?
时间: 2023-06-02 22:04:07 浏览: 72
这个问题是属于技术问题,我可以回答。这种构造散列函数的方式是不安全的,因为它容易受到针对 RSA 的攻击。具体来说,攻击者可能会利用 RSA 的特殊性质来找到两个不同的消息 m 和 m',使得它们对应的散列码相同。这被称为 RSA 散列碰撞攻击。因此,我们需要使用更加安全的散列函数来保护数据的完整性和保密性。
相关问题
用公钥密码体制RSA来构造一个Hash函数。将消息m分成k组,即,固定一个RSA密钥(e, n)并定义如下一个Hash函数:,,其中,最后一个分组的输出即是Hash值。试找出上述Hash的一个碰撞。
首先,我们需要定义一个消息m和另一个与m不同的消息m'。为了方便,我们假设m和m'的长度相同。
假设m的k个分组依次为m1, m2, ..., mk,而m'的k个分组依次为m'1, m'2, ..., m'k。
根据Hash函数的定义,我们可以得到:
h = ((...((m1^e mod n)^m2 mod n)^...)^mk mod n)
同样地,对于m',我们可以得到:
h' = ((...((m'1^e mod n)^m'2 mod n)^...)^m'k mod n)
我们需要构造m和m',使得h = h'。
我们可以选择一个分组mi,并将其替换为mi',即m'中对应的分组。此时,Hash函数的计算过程中,mi和mi'的计算结果相同,因此对于除了mi和mi'之外的分组,Hash值不变。而对于mi和mi',它们的计算结果相同,因此最终的Hash值也相同。
因此,我们找到了一个碰撞,即将m中的一个分组替换为m'中相应的分组,可以得到相同的Hash值,从而证明这个Hash函数不是强度碰撞性的。
需要注意的是,实际应用中,我们不能直接使用RSA作为Hash函数,因为RSA的计算量比较大,会影响性能。通常,我们会使用专门的Hash函数,例如SHA-1、SHA-256等。
在RSA算法中n=119,e=5,m=19密文,公钥,私钥各为多少
根据RSA算法的加密和解密公式:
加密:$c = m^e \bmod n$
解密:$m = c^d \bmod n$
其中,n是两个大素数p和q的乘积,e是公钥,d是私钥,满足以下条件:
1. $n = p \times q$
2. $(p-1) \times (q-1)$与e互质
3. $d \equiv e^{-1} \bmod (p-1) \times (q-1)$
将n=119进行因数分解,得到p=7,q=17。根据公式3,需要计算e在模(p-1)×(q-1)下的逆元,即:
$(p-1) \times (q-1) = 6 \times 16 = 96$
由于5和96互质,因此e=5是一个合法的公钥。
接下来,需要计算私钥d,满足$d \equiv 5^{-1} \bmod 96$。根据扩展欧几里得算法,可以得到:
$$
\begin{aligned}
& 96 = 5 \times 19 + 1 \\
\Rightarrow & 1 = 96 - 5 \times 19 \\
\end{aligned}
$$
因此,$d \equiv 1 \bmod 96$,即d=1+96k,其中k为任意整数。为了方便计算,我们可以取k=1,此时d=97。
因此,加密公钥为(n,e)=(119,5),私钥为(n,d)=(119,97)。
将明文m=19代入加密公式,得到:
$c = 19^5 \bmod 119 = 12$
因此,密文为12。
将密文c=12代入解密公式,得到:
$m = 12^{97} \bmod 119 = 19$
因此,原始明文为19。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)