Berechnen Primzahlen p und q aus private exponent (d), public exponent (e) und der modulus (n)

Wie berechne ich die p-und q-Parameter von e (publickey), d (privatekey) und E-Modul?

Ich habe BigInteger Schlüssel in der hand kann ich kopieren und einfügen in den code. Ein publickey, ein privatekey und ein E-Modul.

Brauche ich zur Berechnung der RSA-Parameter p und q ab. Aber ich vermute, es ist eine Bibliothek für das, was ich war nicht in der Lage zu finden mit google. Irgendwelche Ideen? Danke.

Diese nicht brute-force, da bin ich nicht nach dem privaten Schlüssel. Ich habe nur ein legacy-system, das speichert einen öffentlichen, einen privaten Schlüssel und ein E-Modul und die ich brauche, um Sie in c# zur Verwendung mit RSACryptoServiceProvider.

So kommt es auf die Berechnung von (p+q) von

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;

    }

aber das scheint nicht zu funktionieren. Erkennen Sie das problem?

5 Stunden später... 🙂

Ok. Wie kann ich wählen Sie eine zufällige Zahl aus Zn* (http://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n) in C#?

Bitte Wort in dieser Frage klarer zu sehen. Sie haben zwei BigInteger Schlüssel, und Sie Sie nutzen wollen, zu tun, was?
Hmmmmm... knopfaugen auf
Vermeiden Sie die "HILFE" - Ding, das hässliche und nicht gebraucht.

InformationsquelleAutor |

c#cryptography rsa

6

Lassen Sie uns davon ausgehen, dass e ist klein (das ist der häufigste Fall; die Traditionelle öffentliche exponent 65537). Lassen Sie uns auch annehmen, dass ed = 1 mod phi(n), wo phi(n) = (p-1)(q-1) (dies ist nicht notwendigerweise der Fall; der RSA-Anforderungen sind, dass ed = 1 mod lcm(p-1,q-1) und phi(n) ist nur ein Vielfaches von lcm(p-1,q-1)).

Jetzt haben Sie ed = k*phi(n)+1 für einige ganze Zahl k. Da d ist kleiner als phi(n), wissen Sie, dass k < e. So dass Sie nur eine kleine Anzahl von k zu versuchen. Eigentlich phi(n) ist in der Nähe n (die Differenz wird auf die Reihenfolge der sqrt(n); in anderen Worten, wenn aufgeschrieben, in bits, die Obere Hälfte der phi(n) ist identisch mit n), so kann man berechnen k' mit: k'=round(T/n). k' ist sehr nah an k (d.h. |k'-k| <= 1), solange die Größe der e ist nicht mehr als die Hälfte der Größe der n.

Gegeben k, Sie leicht phi(n) = (ed-1)/k. So kommt es, dass:

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

Somit erhalten Sie p+q = n + 1 - phi(n). Sie haben auch pq. Es ist Zeit, sich zu erinnern, dass für alle reellen zahlen eine und b, eine und b sind die beiden Lösungen der quadratischen Gleichung X²-(a+b)X+ab. So, da p+q und pq, p und q sind, die durch Lösung der quadratischen Gleichung:

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

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

Im Allgemeinen Fall e und d haben können beliebige Größen (evtl. größer als n), weil alle, die RSA benötigt wird, dass ed = 1 mod (p-1) und ed = 1 mod (q-1). Es ist eine generische (und schnelle) Methode, die ein bisschen aussieht wie der Miller-Rabin primality test. Es ist beschrieben in der Handbook of Applied Cryptography (Kapitel 8, Abschnitt 8.2.2, Seite 287). Diese Methode ist konzeptionell ein bisschen komplexer (es umfasst die modularen Errichtung in die Stufe), kann aber einfacher zu implementieren (weil es keine Quadratwurzel).
- die von einem Angriffe in dem Buch ist die eine in Bezug auf die von Ihnen vorgeschlagene Lösung?
- es scheint mir nicht praktisch lösbar ist. Ich muss erkennen k sicher...
InformationsquelleAutor Thomas Pornin

Gibt es ein Verfahren zum wiederherstellen p und q von n, e und d beschrieben in NIST Special Publication 800-56B R1 Empfehlung für die Pair-Wise Key-Einrichtung Systeme unter Verwendung der Integer-Faktorisierung Kryptographie in Anhang C.

Die Schritte, die beteiligt sind:

Lassen k = de – 1. Wenn k ungerade ist, dann gehen Sie zu Schritt 4.
Schreiben k als k = 2^tr, wobei r die größte ungerade ganze Zahl dividiert k, und t ≥ 1. Oder in einfacheren Worten, Sie teilen k wiederholt durch 2, bis eine ungerade Zahl.
Für i = 1 zu 100 tun:
1. Generieren einer zufälligen Ganzzahl g im Bereich [0, n−1].
2. Lassen y = g^r mod n
3. Wenn y = 1 oder y = n – 1,, dann gehen Sie zu Schritt 3.1 (d.h. wiederholen Sie diese Schleife).
4. Für j = 1 zu t – 1 tun:
  1. Lassen x = y² mod n
  2. Wenn x = 1, gehen Sie zu (äußeren) Schritt 5.
  3. Wenn x = n – 1,, gehen Sie zu Schritt 3.1.
  4. Lassen y = x.
5. Lassen x = y² mod n
6. Wenn x = 1, gehen Sie zu (äußeren) Schritt 5.
7. Weiter
Ausgabe der "prime Faktoren nicht gefunden" und Stoppt.
Lassen p = GCD(y – 1, n) und lassen q = n/p
Ausgabe (p, q), wie den Primfaktoren.

Ich schrieb vor kurzem eine Implementierung in Java. Nicht direkt hilfreich für C#, die ich realisieren, aber vielleicht kann er einfach portiert:

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

Dieser code verwendet ein paar Helfer Definitionen/Methoden:

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

!bi.testBit(0)
Ah ja, das ist schon ein bisschen kürzer als meine aktuellen test. Vielen Dank für den Hinweis.
Ich glücklich verheiratet, diesen code mit Wiener Angriffs-code, hoffe du verzeihst mir 🙂

InformationsquelleAutor

Habe ich angepasst, die Java-code von Duncan in C#, falls es jemanden interessiert:

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

Diese nutzt die standard-System.Numerik.BigInteger-Klasse.

Getestet wurde dies durch die folgenden 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);

InformationsquelleAutor

Implementiert habe ich die Methode beschrieben von Thomas Pornin.

Den BigInteger Klasse Chew Keong TAN C# - version (check-codeproject Kommentare für 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");
    }

InformationsquelleAutor

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.