RSA Short Key Attachment

Question

Given the following RSA keys, how to determine what p and q values ​​are?

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

Answer 1

Your teacher gave you:

Public key: (10142789312725007.5)

which means

 n = 10142789312725007 e = 5 

where n is the module and e is the public indicator.

In addition, you are provided

Private key: (10142789312725007, 8114231289041741)

means that

  d = 8114231289041741 

where d is the decryption rate, which should remain secret.

You can "break" the RSA by knowing how to determine the "n" in its "p" and "q" simple factors:

 n = p * q 

The easiest way is probably to check all the odd numbers starting just below the square root of n:

 Floor[Sqrt[10142789312725007]] = 100711415 

You will get the first factor in 4 attempts:

 10142789312725007 mod 100711415 = 100711367 10142789312725007 mod 100711413 = 100711373 10142789312725007 mod 100711411 = 100711387 10142789312725007 mod 100711409 = 0 <-- Winner since it evenly divides n 

So we have

  p = 100711409 

Now,

  q = n / p = 10142789312725007 / 100711409 = 100711423 

Why is it important? This is because d is a special number such that

 d = e^-1 mod phi(n) = e^-1 mod (p-1)*(q-1) 

We can check it out.

 d * e = 40571156445208705 = 1 mod 10142789111302176 

This is important because if you have text message m , then ciphertext

 c = m^e mod n 

and you will decrypt it with

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

For example, I can “encrypt” message 123456789 using your teacher’s public key:

 m = 123456789 

This will give me the following ciphertext:

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

(Note that "e" in practice should be much larger, because for small values ​​of "m" you do not even exceed n)

Anyway, now we have "c" and can cancel it with "d"

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

Obviously, you cannot calculate "7487844069764171 ^ 8114231289041741" directly, because it has 128,808,202,574,088,302 digits, so you should use the modular exponentiality trick.

In the "real world" n is obviously much more. If you want to see a real-world example of how HTTPS uses RSA under covers with 617-digit n and e from 65537, see my blog post “ The first few milliseconds of an HTTPS connection .

Answer 2

Here's a relatively easy way to look at it (and one that is manual). If you had fully defined the number, then the highest factor you would need to consider is sqrt (N):

 sqrt(10142789312725007) = 100711415.9999997567 

The first stroke below this is 100711409, just 6 below sqrt (N).

 10142789312725007 / 100711409 = 100711423 

therefore, these are two factors of N. Your professor did this quite easily - the trick is to admit that no one will choose a small p or q, so starting your check from the bottom (like someone posted in a python script) is a bad idea. If this is practical by hand, large p and q should lie near sqrt (N).

Answer 3

There are various fast algorithms for solving the factoring problem n taking into account n , e and d . You can find a good description of one of these algorithms in the Applied Cryptography Reference, Chapter 8 , section 8.2.2. You can find these chapters on the Internet for free download here .

Answer 4

Wolframalpha tells me that factors 100711409 and 100711423

I just wrote a naive Python script to pounce on it. As Amdfan noted, starting from the top is a better approach:

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

This can be greatly improved, but it still works without a problem. You can improve it by simply checking the factors, but for small values ​​like yours, that should be enough.

Answer 5

The RSA definition tells you that the module is n = pq . You know n , so you just need to find two numbers p and q that are multiplied by n . You know that p and q are primary, so this is the main factorization problem.

You can solve this problem by brute force for relatively small numbers, but the overall security of the RSA depends on the fact that this problem is insoluble at all.

Answer 6

Here is the Java implementation of the fast factorization method from the Applied Cryptography Reference Chapter 8 , Section 8.2.2 (thanks to GregS for finding it):

 /** * 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; } } 

Typical output

 100711423 100711409 (3ms) 

Answer 7

These two articles may be helpful.

• Andrej Dujella - Wiener attack variant on RSA
• Andrey Dujella - Continuation of the Faction and RSA with a small secret indicator

I came to them when I was doing basic research on the continuation of fractions.

Answer 8

The algorithm for this is (and this will work for any example, and not just this small one, which can easily be easily taken into account by any computer):

ed - 1 is a multiple of phi (n) = (p-1) (q-1), so at least a multiple of 4. ed - 1 can be calculated as 40571156445208704, which is 2 ^ 7 * 316962159728193, and we call s = 7 and t = 316962159728193. (in general, any even number is a power of 2 times with an odd number). Now select a in [2, n-1] in random order and calculate the sequence

a ^ t (mod n), a ^ (2t) (mod n), a ^ (4t) (mod n) .. until no more than a ^ ((2 ^ 7) * t) (mod n ), where the latter is guaranteed 1, by construction e and d. Now we are looking for the first 1 in this sequence. Before it will be either +1 or -1 (the trivial root of 1, mod n), and we repeat with another a or some number x, which is not equal to +1 or -1 mod n. In the latter case, gcd (x-1, n) is a nontrivial divisor of n and, therefore, p or q, and we do. It can be shown that random a will work with a probability of about 0.5, so we need several attempts, but not very many in general.

Answer 9

I suggest you read about Quadratic Sieve . If you implement it yourself, it is definitely worth it. If you understand the principles, you have already received something.

Answer 10

Sorry for the necromancy, but a friend asked me about it, and pointing to it here, I realized that I really do not like the answers. After factoring the module and getting the primes (p and q), you need to find the total that is (p-1) * (q-1).

Now, to find the private exponent, you will find that the inverse is public exponent mod the totient.

public_exponent * private_exponent = 1 mod totient

And now you have your secret key, it's easy. All of this, with the exception of factorization, can be done almost instantly for huge integers.

I wrote the code:

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

The factorization factor used is stupid, but short, so there is a grain of salt. In this particular example, the code runs almost instantly, but this is largely because the teacher in question presented an example that uses two prime numbers in a string, which is not really possible for RSA.

If you want to cut out my silly iterative search, you can add some real factorization algorithm and factor keys, probably up to about 256 bits in a reasonable amount of time.

Answer 11

You need to expand the module so that the first parameter of the public key is 10142789312725007. They will do brute force (check every odd number from 3 to sqrt (n) if this is a factor), although there are more complex / faster algorithms.

Since the number is too large to fit into a regular integer (even 64-bit), you may need a number library that supports integers with an arbitrary number. For C, there is GMP and MPIR (more Windows-friendly). For PHP, there is Bignum. Python comes with a built-in - the built-in integer data type already has an arbitrary length.

Answer 12

There are many bad assumptions about factorizing large semisimple numbers that go into brute force or sifting, none of which are required to factorize semisimple. 64 bit takes 1 - 2 seconds on my computer, and 256 bit is usually less than 2 days