RSA安全性的相关问题

语义安全性 Semantic Security

除了信息论安全、密码学健壮,我们还需要讨论算法的语义安全性。假设攻击者只具有有限的计算资源,语义安全性指在已知密文的情况下无法获得明文的信息。

基于游戏的证明(定义)

攻击者可以选择两个长度相同的明文m_0m_1交给挑战者进行加密,挑战者从两个明文中选择其一进行加密,然后攻击者根据加密后的数据判断哪一个明文被加密。

W_0W_1分别表示猜错和猜对,则攻击者的优势为:

Advantage [A, E] \coloneqq |Pr[W_0] - Pr[W_1]|

当对于所有高效的算法A,攻击者的优势Advantage[A, E]的值几乎为0(negligible),也即Pr[W_0] \thickapprox Pr[W_1]的时候,称加密方法E是语义安全的。

RSA的语义安全性

考虑RSA的语义安全性证明:攻击者可以对两个明文m_0m_1都进行加密,因为公钥是公开的,从而得到对应的密文x_0x_1。此时把x_0x_1x_b进行对比就可以知道挑战者对哪个明文进行了加密操作。

因此,传统RSA不具有语义安全性。导致这种缺陷的原因是,其加密算法具有确定性(deterministic),我们需要一种非确定性加密方案(例如概率加密)来解决这个问题。一种简单的思路是在加密前给明文添加随机数。

继续阅读“RSA安全性的相关问题”

密码学健壮的系统与RSA

Cryptographically Strong Systems

密码学健壮的系统:
使用复杂的数学问题设计密码系统,使破解密码系统的难度和求解此类数学问题的难度一样大。

数学秘密:用于解密、签名等等
素数在许多密码系统(尤其是非对称密码系统)中发挥重要作用

假设

因数分解假设(Factorization)
n = p \cdot q
已知n,难以找到p和q两个素数(当p、q足够大时难以暴力破解)
n是密钥对的公开部分。

此外还应该有一些特殊的属性:
例如模m同余:
a \equiv b \mod m

RSA算法中计算模反元素即找到与e同余的一个数

继续阅读“密码学健壮的系统与RSA”