比如现在一个人的六位纯数字密码用了rsa公钥加密传输给伺服器，被我中间截获。我得到了密文，即使不知道解密的私钥，但我熟悉他六位数密码设置习惯，又已知公钥，是否可以用公钥尝试加密他所有可能的六位数密码，用得到的密文再与截获的密文进行匹配，一样是否代表就猜中他的密码了？

先上结论: 教科书里的RSA确实存在题主所说的问题. 这也是为什么: 在现实中, 我们不应当用教科书中的RSA, 而是应该用RSA-OAEP这一类随机化填充之后的RSA加密演算法.

引子: 题主的问题涉及了现代密码学中一个非常有趣的, 也很基础问题: 为什么教科书中RSA的one-way安全是不够的, 为什么我们进一步地在公钥加密中定义了语义安全, 其背后的逻辑究竟是什么. 以上这些虽然是密码学中非常非常基础的内容. 但在实际中, 很多人对这些问题都会有不同程度的不了解, 甚至是误解, 以至于产生了很多RSA用法的错误示范; 在这方面, 鹅厂的程序员尤其突出, 贡献出一系列反面案例 (When Textbook RSA is Used to Protect the Privacy of Hundreds of Millions of Users).

话不多说, 开始认真答题.

不得不说答主的直觉是非常正确的: 因为教科书上的RSA 是确定性演算法, 这就意味著对于给定的公钥, 如果有两个同样的明文输入, 经过加密后, 一定会有相同的秘文输出; 而两个不同的明文输入, 经过加密, 则会有不同的秘文输出. 咋看之下问题不大, 因为RSA假设保证了在没有私钥的情况下, 攻击者无法直接从秘文反算回明文, 这也就是我们所说的one-way安全. (one-way这个词描述了rsa加密这个陷门函数的特点, 只有当解密者手握私钥这一陷门, 才能从密文反算出明文, 否则rsa加密就像其他one-way函数一样, 不存在有效演算法从输出反推出输入, 比如密码学hash函数)

但是, 教科书中RSA的一个天然隐患, 就是题主指出的: 如果明文空间的熵很低很低, 那岂不是可以用字典攻击等暴力破击手段来猜测明文. 可见one-way安全在有些场景下, 会出大问题. (用行话说, 这种暴力破解可以被建模成选择明文攻击. 在公钥加密演算法下, 敌手可以轻松实现这种攻击. 因为公钥对所有人可见, 攻击者永远可以拿著公钥, 自己去选择各种不同的明文, 并不断地做加密, 直到碰到相同的密文, 表明破解成功, 找到了原始明文.)

那我们就进一步思考问题出现在哪里? 直觉很简单: 虽然攻击者无法从秘文单方向的反算回明文, 但秘文其实仍然"泄露"了很多有关明文的信息. 可以想像一个例子: 假设使用教科书的RSA加密, 我们在明文空间中按照明文的分布规律抽样, 然后再加密, 攻击者会拿到一堆秘文, 这些秘文至少会泄露出明文空间的原有分布规律.

既然清楚了问题的本源是one-way安全不够强, 那我们需要一种更强的安全, 要有多强? 语义安全: 除了消息的长度, 关于明文的信息一点也不从秘文中泄露出去; 当然了, 这里我们只考虑多项式演算法的攻击者. 也就是说, 多项式时间内的攻击者虽然看到了一堆秘文, 然而它什么也没得到, 只觉得这些是一堆随机生成的定长比特串.

如何做到语义安全, 让秘文看起来是随机杂乱的? 非常简单: 在明文中进行随机化的填充. 比如, RSA的一个变种RSA-OAEP: 在明文的尾部填充一些随机比特, 给随机寓言机输入这些随机比特, 再把随机寓言机吐出的随机数拿来, 完美地"掩盖"原有的明文, 这样对"掩盖"之后的明文再加密, 输出的秘文也因之随机化. 解密时, 可以再利用随机寓言机和填充的随机比特重现"覆盖"在明文上的随机数, 并将之去除, 得到原始明文.

从观感上看, RSA-OAEP这一过程"模拟"了对称加密中的一次一密(one-time pad), 等效于在每一次加密中都在使用一个全新生成的密钥. 从结果上来看, 此时再对一个明文进行多次加密, 产生的秘文们将会是不同的 (伪随机的). 选择明文攻击者对这样具有语义安全的加密, 就会彻底摊手, 表示一脸蒙蔽.

综上: 教科书中的RSA只是one-way安全的, 在现实中, 我们不应当采用教科书中的RSA, 而是应当使用随机化的, 具有语义安全的RSA变种, 比如RSA-OAEP.

这要看RSA是怎么实现的了。

如果实现是这样的

# e, n代表公钥
e = xxxx
n = xxxxxxxxxxx

m = b123456
m = int.from_bytes(m, big)
c = pow(m, e, n)
c = c.to_bytes((c.bit_length() + 7) // 8, big)

# 密文c发送给伺服器
send(c)

这是最纯粹的RSA实现，但是这个很显然就可以做到你所说的选择明文攻击。通过遍历明文空间得到明文。

但是事实上现在RSA实现基本上是这样的

# e, n代表公钥
e = xxxx
n = xxxxxxxxxx

# prefix 是一种约定，用来检测解密是否正确
prefix = bxffxffxffxff........
m = b123456
m = int.from_bytes(prefix + random_bytes(...) + m, big)
c = pow(m, e, n)
c = c.to_bytes((c.bit_length() + 7) // 8, big)

# 密文c发送给伺服器
send(c)

这种实现中因为有随机数，所以真正加密的明文是每次都不一样的，哪怕用户给的消息都是一样的。这样遍历明文空间来得到明文的方法就失效了。

事实上rsa很少原来做加密反而用来做认证更多。题主所说的是认证机制不是加密。

rsa用来做加密时，要加入填充的，密文空间要比明文空间大得多，稀疏得多

可以，这个相当于是彩虹表攻击。你穷举了所有的明文和密文对，自然明文和密文就透明了。只是一般没有那么小的明文或者密文空间。

一般情况我们不用公钥加密演算法加密我们要传输的信息，因为公钥加密的过程是确定公开的，当明文本身不在一个足够大的空间随机分布时就会很不安全。此外，公钥加密一般很费时间。

我们一般用公钥加密演算法传递一个对称加密演算法的密钥，这个密钥足够长且随机分布无法枚举攻破，然后用安全的对称加密演算法比如AES去加密明文。

如果只是用RSA加密的话，可以的。

但是有些情况下并不是用RSA来加密数据。

比如HTTPS。它有个密钥协商的过程，会协商出一个session key用来加密数据。而session key是随机的，一般会使用对称加密。

可以啊。

这就是所谓的暴力破解，俗称挨个放血（划掉划掉），挨个尝试。

不过我看你有个HTTPS的标签在这，那就不能这么个玩法了。SSL协议的话，用RSA交换的其实是AES的密匙。一般256位就是32个位元组，还是随机的。

而你想要的6位密码则是是用这个AES加密的。

这就非常坑爹了，当然你也可以猜猜试一试，万一运气好呢？

首先需要知道在rsa演算法中，对于2048的rsa密钥来说，明文输入长度必须是256位元组才能加密，对于不足256位元组的明文数据则必须要通过填充到256位元组，再进行加密操作。

（以上实际使用中的处理，虽然理论上可以加密比256长短的数据，但是实际应用中很少直接那样用）

问题中提到的虽然密码只有六个位元组，但是实际加密的时候都会填充到256位元组，实际使用中通常采用的填充方法对于每次填充的数据都是随机的。也就是说同样的六位密码，两次加密出来的结果是不一样的。

所以要穷举密码的话，并不是穷举完所有的六位的密码就能撞到，而是要穷举完所有的256位元组（不仅仅是可见字元，还包括各种不可见字元）的密码才有可能撞到。而如果使用当前的计算能力完成这个穷举过程，至少需要千年万年级别的时间。这也是2048的rsa安全的一个必要条件。

你试一下就知道了，商用非对称rsa，sm2，同一个明文加密的结果都不相同。

推荐阅读：
相关文章