Вычислите простые числа p и q из частного показателя (d), общего показателя (e) и модуля (n) - PullRequest
Новая
       13

Вычислите простые числа p и q из частного показателя (d), общего показателя (e) и модуля (n)

8 голосов
/ 27 мая 2010

Как рассчитать параметры p и q из e (publickey), d (privatekey) и модуля?

У меня под рукой ключи BigInteger, я могу скопировать вставку в код. Один открытый ключ, один закрытый ключ и модуль.

Мне нужно рассчитать параметры RSA p и q из этого. Но я подозреваю, что есть библиотека, которую я не смог найти в Google. Есть идеи? Спасибо.

Это не должно быть грубой силой, так как я не за закрытым ключом. У меня просто есть устаревшая система, в которой хранится пара открытого и закрытого ключей и модуль, и мне нужно перенести их в c # для использования с RSACryptoServiceProvider.

Итак, все сводится к вычислению (p + q) на 

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;

    }

но это не похоже на работу. Вы можете определить проблему?

5 часов спустя ...:)

Ok. Как я могу выбрать случайное число из Zn * (http://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n) в C #?

Ответы [ 4 ]

6 голосов
/ 27 мая 2010

Предположим, что e мало (это обычный случай; традиционный открытый показатель равен 65537). Давайте также предположим, что ed = 1 mod phi (n) , где phi (n) = (p-1) (q-1) (это не обязательно так: требования RSA состоят в том, что ed = 1 mod lcm (p-1, q-1) и phi (n) является только кратный lcm (p-1, q-1) ).

Теперь у вас есть ed = k * phi (n) + 1 для некоторого целого числа k . Так как d меньше, чем фи (n) , вы знаете, что k . Таким образом, у вас есть только небольшое количество k , чтобы попробовать. На самом деле, phi (n) близко к n (разница составляет порядка sqrt (n) ; другими словами, при записи в битах верхняя половина phi (n) идентична верхней части n ), поэтому вы можете вычислить k ' с помощью: k' = round ( ред / п) . k ' очень близко к k (то есть | k'-k | <= 1 </em>) до размера e не более половины размера n .

Учитывая k , вы легко получаете phi (n) = (ed-1) / k . Так получилось, что:

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

Таким образом, вы получите p + q = n + 1 - фи (n) . У вас также есть pq . Пришло время вспомнить, что для всех действительных чисел a и b , a и b являются двумя решениями квадратного уравнения * 1 079 * Х 2 - (а + б) Х + абы * * тысяча восемьдесят-два. Итак, данные p + q и pq , p и q получены путем решения квадратного уравнения:

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

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

В общем случае e и d могут иметь произвольные размеры (возможно, больше, чем n ), потому что все, что нужно RSA, - это ed = 1 mod (p-1) и ed = 1 mod (q-1) . Существует универсальный (и быстрый) метод, который немного похож на тест первичности Миллера-Рабина. Это описано в Справочнике по прикладной криптографии (глава 8, раздел 8.2.2, стр. 287). Этот метод концептуально немного сложнее (он требует модульного возведения в степень), но его может быть проще реализовать (поскольку квадратного корня нет).

5 голосов
/ 03 февраля 2015

Существует процедура восстановления p и q из n , e и d , описанная в Специальная публикация NIST 800-56B R1 Рекомендация для схем установления парных ключей с использованием целочисленной криптографии в Приложении C.

Шаги:

  1. Пусть k = de - 1 . Если k нечетно, перейдите к шагу 4.
  2. Запишите k как k = 2 t r , где r - наибольшее нечетное целое число, делящее k , и t ≥ 1 . Или, проще говоря, делите k несколько раз на 2, пока не достигнете нечетного числа.
  3. Для i = 1 до 100 сделать:
    1. Генерирует случайное целое число g в диапазоне [0, n-1].
    2. Let y = g r mod n
    3. Если y = 1 или y = n - 1 , то перейдите к шагу 3.1 (т.е. повторите этот цикл).
    4. Для j = 1 до т - 1 сделать:
      1. Пусть x = y 2 mod n
      2. Если x = 1 , перейдите к (внешнему) шагу 5.
      3. Если x = n - 1 , перейдите к шагу 3.1.
      4. Пусть y = x .
    5. Пусть x = y 2 mod n
    6. Если x = 1 , перейдите к (внешнему) шагу 5.
    7. Продолжить
  4. Выведите «простые факторы не найдены» и остановитесь.
  5. Пусть p = GCD (y - 1, n) и пусть q = n / p
  6. Вывод (p, q) в качестве основных факторов.

Я недавно написал реализацию на Java. Я не понимаю, насколько это полезно для C #, но, возможно, его легко перенести: 

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

Этот код использует несколько вспомогательных определений / методов: 

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 голосов
/ 07 сентября 2015

Я адаптировал Java-код, предоставленный Duncan в C #, если кому-то интересно: 

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

Используется стандартный класс System.Numerics.BigInteger.

Это было проверено следующим модульным тестом: 

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);
1 голос
/ 24 апреля 2015

Я реализовал метод , описанный Томасом Порниным.

Класс BigInteger является версией Chew Keong TAN на C # (проверьте комментарии проекта кода для исправления ошибок) 

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