# 破解短的RSA密钥

``Public Key: (10142789312725007, 5) Private Key: (10142789312725007, 8114231289041741)` `

` `n = 10142789312725007 e = 5` `

` ` d = 8114231289041741` `

` `n = p * q` `

` `Floor[Sqrt[10142789312725007]] = 100711415` `

` `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 = e^-1 mod phi(n) = e^-1 mod (p-1)*(q-1)` `

` `d * e = 40571156445208705 = 1 mod 10142789111302176` `

` `c = m^e mod n` `

` `m = c^d = (m^e)^d = (m^(e*d)) = (m^(e*e^-1)) = m^1 (mod n)` `

` `m = 123456789` `

` `c = m^e mod n = 123456789^5 mod 10142789312725007 = 7487844069764171` `

（请注意，在实践中“e”应该大得多，因为对于“m”的小值，你甚至不会超过n）

` `m = c^d mod n = 7487844069764171^8114231289041741 mod 10142789312725007 = 123456789` `

` `sqrt(10142789312725007) = 100711415.9999997567` `

` `10142789312725007 / 100711409 = 100711423` `

Wolframalpha告诉我，因素是100711409和100711423

` `p = 10142789312725007 for i in xrange(int(p**0.5+2), 3, -2): if p%i == 0: print i print p/i break` `

RSA的定义告诉你模数`n = pq` 。 你知道`n`所以你只需要find两个乘数`p``q`来产生`n` 。 你知道`p``q`是素数，所以这是主要的因式分解问题。

` `/** * 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小秘密指数

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左右的概率工作，所以我们需要一些尝试，但总的来说不是很多。

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); }` `