从 RSA 算法中的模数确定密钥的位长度的问题
Problem determining the bit length of a key from the modulus in the RSA algorithm
这里有两个 64 位（有符号）整数
p = 13776308150928489016
q = 16488138731131959619
和他们的产品
n = 112488352363349635896748360565917156710
产品的位长是floor ((log2 n) + 1)或127。
现在这里是另外两个 64 位整数
p = 13275629912622491628
q = 16290498985329101221
和他们的产品
n = 179030914337714357408535416678431567970
但是这次位长是floor ((log2 n) + 1)或者128.
原因是第一个整数中有一个前导零，这使得 space 需要在内存中表示整数小一点。
这样导致的问题是我无法准确确定密钥的位长。例如，这是一个非常短的 RSA 密钥对：
Public key : 7, 8371846783263706079
Private key : 2989945277626202443, 8371846783263706079
模数（8371846783263706079）是63位，我要的是64。为了克服这个问题，我考虑了以下解决方案：
- 四舍五入到最接近的 2^n
- 与密钥一起存储密钥大小（以位为单位）
- 添加某种填充以确保所有整数占用相同 space（不确定这在实践中如何工作）
哪一个是正确的解决方案？
正如@r3mainer 指出的那样，这里需要的数学——inequalities——并不奇怪。至于教程说的，嗯，他们只是教程，他们试图尽可能地简化，所以他们遗漏了一些细节。
您观察到的是：
你想要两个素数 p 和 q 具有相同的位长 k 并且它们的乘积 N 具有 2k 的位长。
根据位长k的定义，我们有以下不等式：
1) 2(k-1) <= p, q < 2k.
然而，当我们将p和q相乘时，我们发现了一个问题：
2) 2(2k - 2) <= N < 22k
这意味着 N=p*q 的位长可能最终为 2k-1 或 2k，但我们不想要 2k-1。
在你的例子中k=64。
要修复它，我们需要将 p 和 q 的下限收紧到以下值：
3) sqrt(2(2k-1)) <= p, q < 2k.
考虑到所有结果都是整数，我们应用上限函数并最终得到
4) 上限(sqrt(2(2k-1))) <= p, q < 2k.
对于 k=64，计算结果为：
13043817825332782213 <= p, q < 264
一个更简单的公式是使边界动态化，如下所示：
首先找到任意大小的p。那么我们要
2(2k - 1) <= p*q < 22k, 所以
5) (2(2k - 1))/ p <= q < (22k)/p 将执行技巧.
对于 RSA，我们实际上确实希望两个素数都足够大且具有熵，但又不会彼此靠得太近。我们可以通过选择 p 的长度为 k-1 或 k-2 并应用 5).
来做到这一点
这里有两个 64 位（有符号）整数
p = 13776308150928489016
q = 16488138731131959619
和他们的产品
n = 112488352363349635896748360565917156710
产品的位长是floor ((log2 n) + 1)或127。
现在这里是另外两个 64 位整数
p = 13275629912622491628
q = 16290498985329101221
和他们的产品
n = 179030914337714357408535416678431567970
但是这次位长是floor ((log2 n) + 1)或者128.
原因是第一个整数中有一个前导零，这使得 space 需要在内存中表示整数小一点。
这样导致的问题是我无法准确确定密钥的位长。例如，这是一个非常短的 RSA 密钥对：
Public key : 7, 8371846783263706079
Private key : 2989945277626202443, 8371846783263706079
模数（8371846783263706079）是63位，我要的是64。为了克服这个问题，我考虑了以下解决方案：
- 四舍五入到最接近的 2^n
- 与密钥一起存储密钥大小（以位为单位）
- 添加某种填充以确保所有整数占用相同 space（不确定这在实践中如何工作）
哪一个是正确的解决方案？
正如@r3mainer 指出的那样，这里需要的数学——inequalities——并不奇怪。至于教程说的，嗯，他们只是教程，他们试图尽可能地简化，所以他们遗漏了一些细节。
您观察到的是：
你想要两个素数 p 和 q 具有相同的位长 k 并且它们的乘积 N 具有 2k 的位长。
根据位长k的定义，我们有以下不等式：
1) 2(k-1) <= p, q < 2k.
然而，当我们将p和q相乘时，我们发现了一个问题：
2) 2(2k - 2) <= N < 22k
这意味着 N=p*q 的位长可能最终为 2k-1 或 2k，但我们不想要 2k-1。
在你的例子中k=64。
要修复它，我们需要将 p 和 q 的下限收紧到以下值：
3) sqrt(2(2k-1)) <= p, q < 2k.
考虑到所有结果都是整数，我们应用上限函数并最终得到
4) 上限(sqrt(2(2k-1))) <= p, q < 2k.
对于 k=64，计算结果为：
13043817825332782213 <= p, q < 264
一个更简单的公式是使边界动态化，如下所示：
首先找到任意大小的p。那么我们要
2(2k - 1) <= p*q < 22k, 所以
5) (2(2k - 1))/ p <= q < (22k)/p 将执行技巧.
对于 RSA，我们实际上确实希望两个素数都足够大且具有熵，但又不会彼此靠得太近。我们可以通过选择 p 的长度为 k-1 或 k-2 并应用 5).
来做到这一点