如何在RSA中加密大于N的数字？

Question

这里有一个例子：

我们设定 p = 11，q = 5，那么 N = p*q = 55。接着选择加密指数 e = 3，所以 d = e^-1 mod (p-1)(q-1) = 27。

如果我想加密 x=13，那么 x^e=13^3=52 mod 55。

我知道如何加密一个小于 N 的数字，但如果数字大于 N，该怎么加密呢？

我知道如果 X 大于 N，我们应该把 X 拆分成几个部分，然后分别加密，但我不知道 RSA 是怎么拆分的。

附加问题：

如何在 IOS 或 Python 上用 RSA 加密一个文件？

Answer 1

RSA算法其实并不处理消息的分解，它只是对固定大小的整数进行加密。这种加密算法被称为块密码，因为它是以固定大小的“块”来加密消息的。

如何获取这些块，通常并不是块密码本身规定的。所以，你需要自己决定怎么把消息分割开。将一个整数分解成固定大小块的一种方法是把它转换成基数N，然后分别加密每一位数字。

需要注意的是，你不能把每一位数字独立加密，因为那样不安全。实际上，这样做就相当于使用单字母密码。块密码有不同的操作模式，你可以用来安全地加密多个块。你可以去维基百科页面了解这些模式。

Answer 2

你不应该用RSA来加密长消息。

正确的方法是使用混合加密：

• 首先生成一个随机的AES密钥，用AES来加密实际的数据。最好使用一种认证模式，比如AES-GCM。
• 然后用RSA加密这个AES密钥。这个密钥（126到256位）足够小，可以放在一个RSA块里。例如，使用小而且相对弱的1024位RSA密钥，你大约有500到700位可以用来加密实际的数据（剩下的部分是用来填充的）。

• 最终的密文包含了RSA加密的AES密钥和用AES加密的文件。

  为了安全起见，这里一定要使用填充，特别是OAEP。其他大多数填充方式，包括流行的PKCS#1v1.5填充，都是不安全的。

不要试图把文件分成块，然后用RSA加密。因为没有标准的方法可以这样做，这其实是个坏主意。