破解短的RSA密钥
鉴于以下RSA密钥，如何确定p和q的值是什么？
Public Key: (10142789312725007, 5) Private Key: (10142789312725007, 8114231289041741) 你的老师给你：
公钥：（10142789312725007，5）
意思是
n = 10142789312725007 e = 5
其中n是模数， e是公开指数。
另外，你给
私钥：（10142789312725007,8114231289041741）
意思是
d = 8114231289041741
其中d是应该保密的解密指数。
你可以通过知道如何将“n”分解为它的“p”和“q”素因子来“打破”RSA：
n = p * q
最简单的方法可能是检查从n的平方根开始的所有奇数：
Floor[Sqrt[10142789312725007]] = 100711415
你会得到4次尝试的第一个因素：
10142789312725007 mod 100711415 = 100711367 10142789312725007 mod 100711413 = 100711373 10142789312725007 mod 100711411 = 100711387 10142789312725007 mod 100711409 = 0 <-- Winner since it evenly divides n
所以我们有
p = 100711409
现在，
q = n / p = 10142789312725007 / 100711409 = 100711423
为什么这很重要？ 这是因为d是一个特殊的数字
d = e^-1 mod phi(n) = e^-1 mod (p-1)*(q-1)
我们可以validation这一点
d * e = 40571156445208705 = 1 mod 10142789111302176
这很重要，因为如果你有一个明文消息m，那么密文是
c = m^e mod n
你解密它
m = c^d = (m^e)^d = (m^(e*d)) = (m^(e*e^-1)) = m^1 (mod n)
例如，我可以使用老师的公钥“encryption”123456789消息：
m = 123456789
这会给我下面的密文：
c = m^e mod n = 123456789^5 mod 10142789312725007 = 7487844069764171
（请注意，在实践中“e”应该大得多，因为对于“m”的小值，你甚至不会超过n）
无论如何，现在我们有“C”，可以扭转它与“D”
m = c^d mod n = 7487844069764171^8114231289041741 mod 10142789312725007 = 123456789
显然，你不能直接计算“7487844069764171 ^ 8114231289041741”，因为它有128,808,202,574,088,302个数字，所以你必须使用模幂运算技巧。
在“现实世界”中， n显然要大得多。 如果你想看一个真正的例子，HTTPS如何使用RSA在617位n和65537的e的掩护下，请参阅我的博客文章“ HTTPS连接的第一个毫秒 ”。
这是一个相对简单的方法来看待它（和一个手工可行的）。 如果你要完全分解数字，那么你需要考虑的最高因素是sqrt（N）：
sqrt(10142789312725007) = 100711415.9999997567
下面的第一个素数是100711409，比sqrt（N）低6。
10142789312725007 / 100711409 = 100711423
因此这些是N的两个因素。你的教授让它变得很容易 – 诀窍是认识到没有人会select一个小的 p或q，所以从底部开始你的检查（就像有人发布的python脚本）是一个坏主意。 如果手工实用，大p和q必须靠近sqrt（N）。
有各种快速algorithm来解决给定n ， e和d的因式分解问题。 您可以在“应用密码学手册” 第8章第8.2.2节中find对这种algorithm的很好的描述。 你可以在这里在线免费下载这些章节。
Wolframalpha告诉我，因素是100711409和100711423
我只写了一个天真的Python脚本来强制它。 正如amdfan指出的，从顶端开始是一个更好的方法：
p = 10142789312725007 for i in xrange(int(p**0.5+2), 3, -2): if p%i == 0: print i print p/i break
这可以大大改善，但仍然没有问题。 你可以通过testingprimfactors来改善它，但对于像你这样的小值，这应该就足够了。
RSA的定义告诉你模数n = pq 。 你知道n所以你只需要find两个乘数p和q来产生n 。 你知道p和q是素数，所以这是主要的因式分解问题。
你可以通过蛮力来解决这个问题，但是RSA的整体安全性依赖于这个问题一般难以解决的事实。
下面是应用密码术手册第8章第8.2.2节（感谢GregSfind它）的快速分解方法的Java实现：
/** * Computes the factors of n given d and e. * Given are the public RSA key (n,d) * and the corresponding private RSA key (n,e). */ public class ComputeRsaFactors { /** * Executes the program. * * @param args The command line arguments. */ public static void main(String[] args) { final BigInteger n = BigInteger.valueOf(10142789312725007L); final BigInteger d = BigInteger.valueOf(5); final BigInteger e = BigInteger.valueOf(8114231289041741L); final long t0 = System.currentTimeMillis(); final BigInteger kTheta = d.multiply(e).subtract(BigInteger.ONE); final int exponentOfTwo = kTheta.getLowestSetBit(); final Random random = new Random(); BigInteger factor = BigInteger.ONE; do { final BigInteger a = nextA(n, random); for (int i = 1; i <= exponentOfTwo; i++) { final BigInteger exponent = kTheta.shiftRight(i); final BigInteger power = a.modPow(exponent, n); final BigInteger gcd = n.gcd(power.subtract(BigInteger.ONE)); if (!factor.equals(BigInteger.ONE)) { break; } } } while (factor.equals(BigInteger.ONE)); final long t1 = System.currentTimeMillis(); System.out.printf("%s %s (%dms)\n", factor, n.divide(factor), t1 - t0); } private static BigInteger nextA(final BigInteger n, final Random random) { BigInteger r; do { r = new BigInteger(n.bitLength(), random); } while (r.signum() == 0 || r.compareTo(n) >= 0); return r; } }
典型的输出是
100711423 100711409 (3ms)
这两篇论文可能会有用
- Andrej Dujella – 维纳对RSA的一个变种
- Andrej Dujella – 继续分数和RSA小秘密指数
当我对连续分数进行一些基础研究的时候遇见了他们。
这样做的algorithm是（这将适用于任何示例，不仅这个小的可以由任何计算机轻松分解）：
ed – 1是phi（n）=（p-1）（q-1）的倍数，所以至less是4的倍数。ed – 1可以计算为40571156445208704，等于2 ^ 7 * 316962159728193，我们呼叫s = 7和t = 316962159728193（一般：任何偶数是奇数的2倍的幂）。 现在随机select一个[2，n-1]，然后计算序列
（mod n），a ^（2t）（mod n），a ^（4t）（mod n）…直到最多a ^（（2 ^ 7）* t）（mod n）最后一个保证是1，由e和d的build设。 我们现在看这个序列中的第一个。 前一个将是+1或-1（一个平凡的根1，mod n），我们用不同的a或者不等于+1或者-1 mod n的一些数字x来重做。 在后一种情况下，gcd（x-1，n）是n的一个不平凡除数，所以p或q，我们就完成了。 可以certificate随机a将以0.5左右的概率工作，所以我们需要一些尝试，但总的来说不是很多。
对不起，我有一个朋友问我这个问题，然后指着他，我意识到我真的不喜欢任何答案。 将因子分解并得到素数（p和q）后，需要find总数，即（p-1）*（q-1）。
现在，要find私有指数，你可以find公开指数mod的逆matrix。
public_exponent * private_exponent = 1 mod totient
现在你有你的私钥，那很容易。 除了因式分解以外，所有这些都可以对于巨大的整数几乎立即完成。
我写了一些代码：
// tinyrsa.c // // apt-get install libgmp-dev // yum install gmp-devel // // gcc tinyrsa.c -o tinyrsa -lm -lgmp #include<stdio.h> #include<gmp.h> int main() { // declare some multi-precision integers mpz_t pub_exp, priv_exp, modulus, totient, fac_p, fac_q, next_prime; mpz_init_set_str(pub_exp,"5",10); mpz_init_set_str(modulus,"10142789312725007",10); mpz_init(priv_exp); mpz_init(totient); mpz_init(fac_p); mpz_init(fac_q); // now we factor the modulus (the hard part) mpz_init(next_prime); mpz_sqrt(next_prime,modulus); unsigned long removed=0; while(!removed) { mpz_nextprime(next_prime,next_prime); removed=mpz_remove(fac_p,modulus,next_prime); } mpz_remove(fac_q,modulus,fac_p); // we now have p and q // the totient is (p-1)*(q-1) mpz_t psub, qsub; mpz_init(psub); mpz_init(qsub); mpz_sub_ui(psub,fac_p,1); mpz_sub_ui(qsub,fac_q,1); mpz_mul(totient,psub,qsub); // inverse of the public key, mod the totient.. mpz_invert(priv_exp,pub_exp,totient); gmp_printf("private exponent:\n%Zd\n",priv_exp); }
我使用的分解algorithm是愚蠢的，但简洁，所以在那里的盐。 在这个特定的例子中，代码几乎立即运行，但这很大程度上是因为有问题的教师提供了一个使用两个素数的例子，这对于RSA来说并不现实。
如果你想削减我愚蠢的迭代search，你可以把一些真正的分解algorithm，并在合理的时间内将密钥可能高达约256位。
我build议你阅读二次筛 。 如果你自己实现一个，这肯定值得信任。 如果你明白原则，你已经获得了一些东西。
你需要分解模数，这是公钥的第一个参数，10142789312725007.蛮力会做（检查每个奇数3到sqrt（n），如果它是一个因素），虽然更复杂/快速的algorithm存在。
由于数字太大而不适合传统的整数（甚至是64位），因此您可能需要一个支持任意长度整数的数字库。 对于C，有GMP和MPIR（对Windows更友好）。 对于PHP，有Bignum。 Python带有一个内置的 – 内置的整数数据types已经是任意长度的。
有大量的半素数分解的拙劣的猜测，这些分解化为粗暴的或筛选的，都不是要求分解半素数的。 我的电脑上64位需要1-2秒，而256位一般不到2天
