9

How do I calculate the p and q parameters from e (publickey), d (privatekey) and modulus?

I have BigInteger keys at hand I can copy paste into code. One publickey, one privatekey and a modulus.

I need to calculate the RSA parameters p and q from this. But I suspect there is a library for that which I was unable to find with google. Any ideas? Thanks.

This does not have to be brute force, since I'm not after the private key. I just have a legacy system which stores a public, private key pair and a modulus and I need to get them into c# to use with RSACryptoServiceProvider.


So it comes down to calculating (p+q) by

public BigInteger _pPlusq()
    {
        int k = (this.getExponent() * this.getD() / this.getModulus()).IntValue();

        BigInteger phiN = (this.getExponent() * this.getD() - 1) / k;

        return phiN - this.getModulus() - 1;

    }

but this doesn't seem to work. Can you spot the problem?


5 hours later... :)

Ok. How can I select a random number out of Zn* (http://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n) in C#?

2
  • Please word this question more clearly. You have two BigInteger keys and you want to use them to do what? May 27, 2010 at 13:17
  • Avoid the "HELP" thing, its ugly and not needed. May 27, 2010 at 20:06

4 Answers 4

10

Let's assume that e is small (that's the common case; the Traditional public exponent is 65537). Let's also suppose that ed = 1 mod phi(n), where phi(n) = (p-1)(q-1) (this is not necessarily the case; the RSA requirements are that ed = 1 mod lcm(p-1,q-1) and phi(n) is only a multiple of lcm(p-1,q-1)).

Now you have ed = k*phi(n)+1 for some integer k. Since d is smaller than phi(n), you know that k < e. So you only have a small number of k to try. Actually, phi(n) is close to n (the difference being on the order of sqrt(n); in other words, when written out in bits, the upper half of phi(n) is identical to that of n) so you can compute k' with: k'=round(ed/n). k' is very close to k (i.e. |k'-k| <= 1) as long as the size of e is no more than half the size of n.

Given k, you easily get phi(n) = (ed-1)/k. It so happens that:

phi(n) = (p-1)(q-1) = pq - (p+q) + 1 = n + 1 - (p+q)

Thus, you get p+q = n + 1 - phi(n). You also have pq. It is time to remember that for all real numbers a and b, a and b are the two solutions of the quadratic equation X2-(a+b)X+ab. So, given p+q and pq, p and q are obtained by solving the quadratic equation:

p = ((p+q) + sqrt((p+q)2 - 4*pq))/2

q = ((p+q) - sqrt((p+q)2 - 4*pq))/2

In the general case, e and d may have arbitrary sizes (possibly greater than n), because all that RSA needs is that ed = 1 mod (p-1) and ed = 1 mod (q-1). There is a generic (and fast) method which looks a bit like the Miller-Rabin primality test. It is described in the Handbook of Applied Cryptography (chapter 8, section 8.2.2, page 287). That method is conceptually a bit more complex (it involves modular exponentiation) but may be simpler to implement (because there is no square root).

1
  • which one of the attacs in the book is the one related to your proposed solution?
    – panny
    May 29, 2010 at 12:03
10

There is a procedure to recover p and q from n, e and d described in NIST Special Publication 800-56B R1 Recommendation for Pair-Wise Key Establishment Schemes Using Integer Factorization Cryptography in Appendix C.

The steps involved are:

  1. Let k = de – 1. If k is odd, then go to Step 4.
  2. Write k as k = 2tr, where r is the largest odd integer dividing k, and t ≥ 1. Or in simpler terms, divide k repeatedly by 2 until you reach an odd number.
  3. For i = 1 to 100 do:
    1. Generate a random integer g in the range [0, n−1].
    2. Let y = gr mod n
    3. If y = 1 or y = n – 1, then go to Step 3.1 (i.e. repeat this loop).
    4. For j = 1 to t – 1 do:
      1. Let x = y2 mod n
      2. If x = 1, go to (outer) Step 5.
      3. If x = n – 1, go to Step 3.1.
      4. Let y = x.
    5. Let x = y2 mod n
    6. If x = 1, go to (outer) Step 5.
    7. Continue
  4. Output “prime factors not found” and stop.
  5. Let p = GCD(y – 1, n) and let q = n/p
  6. Output (p, q) as the prime factors.

I recently wrote an implementation in Java. Not directly useful for C# I realise, but perhaps it can be easily ported:

// Step 1: Let k = de – 1. If k is odd, then go to Step 4
BigInteger k = d.multiply(e).subtract(ONE);
if (isEven(k)) {

    // Step 2 (express k as (2^t)r, where r is the largest odd integer
    // dividing k and t >= 1)
    BigInteger r = k;
    BigInteger t = ZERO;

    do {
        r = r.divide(TWO);
        t = t.add(ONE);
    } while (isEven(r));

    // Step 3
    Random random = new Random();
    boolean success = false;
    BigInteger y = null;

    step3loop: for (int i = 1; i <= 100; i++) {

        // 3a
        BigInteger g = getRandomBi(n, random);

        // 3b
        y = g.modPow(r, n);

        // 3c
        if (y.equals(ONE) || y.equals(n.subtract(ONE))) {
            // 3g
            continue step3loop;
        }

        // 3d
        for (BigInteger j = ONE; j.compareTo(t) <= 0; j = j.add(ONE)) {
            // 3d1
            BigInteger x = y.modPow(TWO, n);

            // 3d2
            if (x.equals(ONE)) {
                success = true;
                break step3loop;
            }

            // 3d3
            if (x.equals(n.subtract(ONE))) {
                // 3g
                continue step3loop;
            }

            // 3d4
            y = x;
        }

        // 3e
        BigInteger x = y.modPow(TWO, n);
        if (x.equals(ONE)) {

            success = true;
            break step3loop;

        }

        // 3g
        // (loop again)
    }

    if (success) {
        // Step 5
        p = y.subtract(ONE).gcd(n);
        q = n.divide(p);
        return;
    }
}

// Step 4
throw new RuntimeException("Prime factors not found");

This code uses a few helper definitions/methods:

private static final BigInteger ONE = BigInteger.ONE;
private static final BigInteger TWO = BigInteger.valueOf(2);
private static final BigInteger ZERO = BigInteger.ZERO;

private static boolean isEven(BigInteger bi) {
    return bi.mod(TWO).equals(ZERO);
}

private static BigInteger getRandomBi(BigInteger n, Random rnd) {
    // From http://stackoverflow.com/a/2290089
    BigInteger r;
    do {
        r = new BigInteger(n.bitLength(), rnd);
    } while (r.compareTo(n) >= 0);
    return r;
}
2
  • @MaartenBodewes Ah yes, that's quite a bit more succinct than my current even test. Thanks for pointing that out. May 26, 2015 at 5:40
  • I happily married this code with Wiener attack code, hope you don't mind :) May 26, 2015 at 16:47
3

I've adapted the Java code provided by Duncan in C#, if anyone is interested:

    public static void RecoverPQ(
        BigInteger n,
        BigInteger e,
        BigInteger d,
        out BigInteger p,
        out BigInteger q
        )
    {
        int nBitCount = (int)(BigInteger.Log(n, 2)+1);

        // Step 1: Let k = de – 1. If k is odd, then go to Step 4
        BigInteger k = d * e - 1;
        if (k.IsEven)
        {
            // Step 2 (express k as (2^t)r, where r is the largest odd integer
            // dividing k and t >= 1)
            BigInteger r = k;
            BigInteger t = 0;

            do
            {
                r = r / 2;
                t = t + 1;
            } while (r.IsEven);

            // Step 3
            var rng = new RNGCryptoServiceProvider();
            bool success = false;
            BigInteger y = 0;

            for (int i = 1; i <= 100; i++) {

                // 3a
                BigInteger g;
                do
                {
                    byte[] randomBytes = new byte[nBitCount / 8 + 1]; // +1 to force a positive number
                    rng.GetBytes(randomBytes);
                    randomBytes[randomBytes.Length - 1] = 0;
                    g = new BigInteger(randomBytes);
                } while (g >= n);

                // 3b
                y = BigInteger.ModPow(g, r, n);

                // 3c
                if (y == 1 || y == n-1) {
                    // 3g
                    continue;
                }

                // 3d
                BigInteger x;
                for (BigInteger j = 1; j < t; j = j + 1) {
                    // 3d1
                    x = BigInteger.ModPow(y, 2, n);

                    // 3d2
                    if (x == 1) {
                        success = true;
                        break;
                    }

                    // 3d3
                    if (x == n-1) {
                        // 3g
                        continue;
                    }

                    // 3d4
                    y = x;
                }

                // 3e
                x = BigInteger.ModPow(y, 2, n);
                if (x == 1) {

                    success = true;
                    break;

                }

                // 3g
                // (loop again)
            }

            if (success) {
                // Step 5
                p = BigInteger.GreatestCommonDivisor((y - 1), n);
                q = n / p;
                return;
            }
        }
        throw new Exception("Cannot compute P and Q");
    }

This uses the standard System.Numerics.BigInteger class.

This was tested by the following unit test:

BigInteger n = BigInteger.Parse("9086945041514605868879747720094842530294507677354717409873592895614408619688608144774037743497197616416703125668941380866493349088794356554895149433555027");
BigInteger e = 65537;
BigInteger d = BigInteger.Parse("8936505818327042395303988587447591295947962354408444794561435666999402846577625762582824202269399672579058991442587406384754958587400493169361356902030209");
BigInteger p;
BigInteger q;
RecoverPQ(n, e, d, out p, out q);
Assert.AreEqual(n, p * q);
2

I implemented the method described by Thomas Pornin.

The BigInteger class is Chew Keong TAN's C# version (check codeproject comments for bug fixes)

    /// EXAMPLE (Hex Strings)
    /// N(MODULUS) = "DB2CB41E112BACFA2BD7C3D3D7967E84FB9434FC261F9D090A8983947DAF8488D3DF8FBDCC1F92493585E134A1B42DE519F463244D7ED384E26D516CC7A4FF7895B1992140043AACADFC12E856B202346AF8226B1A882137DC3C5A57F0D2815C1FCD4BB46FA9157FDFFD79EC3A10A824CCC1EB3CE0B6B4396AE236590016BA69"
    /// D(PRIVATE EXPONENT) = "18B44A3D155C61EBF4E3261C8BB157E36F63FE30E9AF28892B59E2ADEB18CC8C8BAD284B9165819CA4DEC94AA06B69BCE81706D1C1B668EB128695E5F7FEDE18A908A3011A646A481D3EA71D8A387D474609BD57A882B182E047DE80E04B4221416BD39DFA1FAC0300641962ADB109E28CAF50061B68C9CABD9B00313C0F46ED"
    /// E(PUBLIC EXPONENT) = "010001"
    /// RESULTS: 
    /// DP = "899324E9A8B70CA05612D8BAE70844BBF239D43E2E9CCADFA11EBD43D0603FE70A63963FE3FFA38550B5FEB3DA870D2677927B91542D148FA4BEA6DCD6B2FF57"
    /// DQ = "E43C98265BF97066FC078FD464BFAC089628765A0CE18904F8C15318A6850174F1A4596D3E8663440115D0EEB9157481E40DCA5EE569B1F7F4EE30AC0439C637"
    /// INVERSEQ = "395B8CF3240C325B0F5F86A05ABCF0006695FAB9235589A56759ECBF2CD3D3DFDE0D6F16F0BE5C70CEF22348D2D09FA093C01D909D25BC1DB11DF8A4F0CE552"
    /// P = "ED6CF6699EAC99667E0AFAEF8416F902C00B42D6FFA2C3C18C7BE4CF36013A91F6CF23047529047660DE14A77D13B74FF31DF900541ED37A8EF89340C623759B"
    /// Q = "EC52382046AA660794CC1A907F8031FDE1A554CDE17E8AA216AEDC92DB2E58B0529C76BD0498E00BAA792058B2766C40FD7A9CC2F6782942D91471905561324B"

    public static RSACryptoServiceProvider CreateRSAPrivateKey(string mod, string privExponent, string pubExponent)
    {
        var rsa = new RSACryptoServiceProvider
        {
            PersistKeyInCsp = false
        };
        var n = new BigInteger(mod, 16);
        var d = new BigInteger(privExponent, 16);
        var e = new BigInteger(pubExponent, 16);

        var zero = new BigInteger(0);
        var one = new BigInteger(1);
        var two = new BigInteger(2);
        var four = new BigInteger(4);


        BigInteger de = e*d;
        BigInteger modulusplus1 = n + one;
        BigInteger deminus1 = de - one;
        BigInteger p = zero;
        BigInteger q = zero;

        BigInteger kprima = de/n;

        var ks = new[] {kprima, kprima - one, kprima + one};

        bool bfound = false;
        foreach (BigInteger k in ks)
        {
            BigInteger fi = deminus1/k;
            BigInteger pplusq = modulusplus1 - fi;
            BigInteger delta = pplusq*pplusq - n*four;

            BigInteger sqrt = delta.sqrt();
            p = (pplusq + sqrt)/two;
            if (n%p != zero) continue;
            q = (pplusq - sqrt)/two;
            bfound = true;
            break;
        }

        if (bfound)
        {
            BigInteger dp = d%(p - one);
            BigInteger dq = d%(q - one);

            BigInteger inverseq = q.modInverse(p);

            var pars = new RSAParameters
            {
                D = d.getBytes(),
                DP = dp.getBytes(),
                DQ = dq.getBytes(),
                Exponent = e.getBytes(),
                Modulus = n.getBytes(),
                P = p.getBytes(),
                Q = q.getBytes(),
                InverseQ = inverseq.getBytes()
            };
            rsa.ImportParameters(pars);
            return rsa;
        }

        throw new CryptographicException("Error generating the private key");
    }

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.