public RSAKeyPair(BigInteger e, BigInteger d, BigInteger n, BigInteger u, BigInteger p, BigInteger q)
 {
     _publickey = new RSAPublicKey(e, n);
     _d = d;
     _u = u;
     _p = p;
     _q = q;
 }

        public static DSAKeyPair GenerateNew(int bits, Rng random)
        {
            BigInteger one = new BigInteger(1);
            BigInteger[] pq = findRandomStrongPrime(bits, 160, random);
            BigInteger p = pq[0], q = pq[1];
            BigInteger g = findRandomGenerator(q, p, random);

            BigInteger x;
            do {
                x = BigInteger.GenerateRandom(q.BitCount());
            } while ((x < one) || (x > q));

            BigInteger y = g.ModPow(x, p);

            return new DSAKeyPair(p, g, q, y, x);
        }

        /// <summary>
        /// Read SSH1 private key parameters.
        /// </summary>
        /// <param name="passphrase">passphrase for decrypt the key file</param>
        /// <param name="modulus">private key parameter is set</param>
        /// <param name="publicExponent">private key parameter is set</param>
        /// <param name="privateExponent">private key parameter is set</param>
        /// <param name="primeP">private key parameter is set</param>
        /// <param name="primeQ">private key parameter is set</param>
        /// <param name="crtCoefficient">private key parameter is set</param>
        /// <exception cref="SSHException">failed to parse</exception>
        public void LoadSSH1PrivateKey(
            string passphrase,
            out BigInteger modulus,
            out BigInteger publicExponent,
            out BigInteger privateExponent,
            out BigInteger primeP,
            out BigInteger primeQ,
            out BigInteger crtCoefficient)
        {
            PrivateKeyFileFormat format = ProbeFormat();

            ISSH1PrivateKeyLoader loader;
            if (format == PrivateKeyFileFormat.SSH1)
                loader = new SSH1PrivateKeyLoader(keyFile, keyFilePath);
            else
                throw new SSHException(Strings.GetString("UnsupportedPrivateKeyFormat"));

            loader.Load(passphrase, out modulus, out publicExponent, out privateExponent, out primeP, out primeQ, out crtCoefficient);
        }

        /// <summary>
        /// Read SSH1 private key parameters.
        /// </summary>
        /// <param name="passphrase">passphrase for decrypt the key file</param>
        /// <param name="modulus">private key parameter</param>
        /// <param name="publicExponent">private key parameter</param>
        /// <param name="privateExponent">private key parameter</param>
        /// <param name="primeP">private key parameter</param>
        /// <param name="primeQ">private key parameter</param>
        /// <param name="crtCoefficient">private key parameter</param>
        /// <param name="comment">comment</param>
        /// <exception cref="SSHException">failed to parse</exception>
        public void Load(
                            string passphrase,
                            out BigInteger modulus,
                            out BigInteger publicExponent,
                            out BigInteger privateExponent,
                            out BigInteger primeP,
                            out BigInteger primeQ,
                            out BigInteger crtCoefficient,
                            out string comment)
        {
            if (keyFile == null)
                throw new SSHException("A key file is not loaded yet");
            byte[] hdr = Encoding.ASCII.GetBytes(PrivateKeyFileHeader.SSH1_HEADER);
            if (!ByteArrayUtil.ByteArrayStartsWith(keyFile, hdr))
                throw new SSHException(Strings.GetString("NotValidPrivateKeyFile"));

            SSH1DataReader reader = new SSH1DataReader(keyFile);
            reader.Read(hdr.Length);

            byte[] cipher = reader.Read(2); //first 2 bytes indicates algorithm and next 8 bytes is space
            reader.Read(8);

            modulus = reader.ReadMPInt();
            publicExponent = reader.ReadMPInt();
            comment = reader.ReadString();
            byte[] prvt = reader.GetRemainingDataView().GetBytes();
            //必要なら復号
            CipherAlgorithm algo = (CipherAlgorithm)cipher[1];
            if (algo != 0) {
                Cipher c = CipherFactory.CreateCipher(SSHProtocol.SSH1, algo, SSH1PassphraseToKey(passphrase));
                c.Decrypt(prvt, 0, prvt.Length, prvt, 0);
            }

            SSH1DataReader prvtreader = new SSH1DataReader(prvt);
            byte[] mark = prvtreader.Read(4);
            if (mark[0] != mark[2] || mark[1] != mark[3])
                throw new SSHException(Strings.GetString("WrongPassphrase"));

            privateExponent = prvtreader.ReadMPInt();
            crtCoefficient = prvtreader.ReadMPInt();
            primeP = prvtreader.ReadMPInt();
            primeQ = prvtreader.ReadMPInt();
        }

        /// <summary>
        /// Read integer.
        /// </summary>
        /// <param name="bigint">BigInteger instance will be stored if succeeded.</param>
        /// <returns>true if succeeded.</returns>
        public bool ReadInteger(out BigInteger bigint)
        {
            BERTagInfo tagInfo = new BERTagInfo();
            if (ReadTagInfo(ref tagInfo)
                && tagInfo.IsConstructed == false
                && tagInfo.TagNumber == TAG_INTEGER
                && tagInfo.Length != LENGTH_INDEFINITE
                && tagInfo.Length > 0) {

                byte[] buff = new byte[tagInfo.Length];
                int len = strm.Read(buff, 0, tagInfo.Length);
                if (len == tagInfo.Length) {
                    bigint = new BigInteger(buff);
                    return true;
                }
            }

            bigint = null;
            return false;
        }

 /// <summary>
 /// Constructor
 /// </summary>
 public CurveEd25519()
 {
     _curveName = "edwards25519";
     _publicKeyAlgorithm = PublicKeyAlgorithm.ED25519;
     _p = new BigInteger(BigIntegerConverter.ParseHex(
             // 2^255 - 19
             "7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffed"
         ));
     _d = BigInteger.Parse(
             "37095705934669439343138083508754565189542113879843219016388785533085940283555"
         );
     _bx = BigInteger.Parse(
             "15112221349535400772501151409588531511454012693041857206046113283949847762202"
         );
     _by = BigInteger.Parse(
             "46316835694926478169428394003475163141307993866256225615783033603165251855960"
         );
     _l = new BigInteger(BigIntegerConverter.ParseHex(
             // 2^252 + 0x14def9dea2f79cd65812631a5cf5d3ed
             "1000000000000000000000000000000014def9dea2f79cd65812631a5cf5d3ed"
         ));
 }

 public RSAPublicKey(BigInteger exp, BigInteger mod)
 {
     _e = exp;
     _n = mod;
 }

        /// <summary>
        /// Extract an message from the encoded message (EM) described in PKCS#1
        /// </summary>
        /// <param name="input">encoded message bits</param>
        /// <param name="type">type number (1 or 2)</param>
        /// <returns>message bits</returns>
        public static BigInteger StripPKCS1Pad(BigInteger input, int type)
        {
            byte[] strip = input.GetBytes();
            int stripLen = strip.Length;

            int i = 0;
            while (true) {
                if (i >= stripLen) {
                    throw new ArgumentException("Invalid EM format");
                }
                if (strip[i] != 0) {
                    break;
                }
                i++;
            }

            if (strip[i] != type) {
                throw new ArgumentException(String.Format("Invalid PKCS1 padding {0}", type));
            }
            i++;

            int padLen = 0;
            while (true) {
                if (i >= stripLen) {
                    throw new ArgumentException("Invalid EM format");
                }
                byte b = strip[i];
                if (b == 0) {
                    break;
                }
                if (type == 1 && b != 0xff) {
                    throw new ArgumentException("Invalid PKCS1 padding");
                }
                padLen++;
                i++;
            }

            if (padLen < 8) {
                throw new ArgumentException("Invalid PKCS1 padding");
            }

            i++;    // skip 0x00
            if (i >= stripLen) {
                throw new ArgumentException("Invalid PKCS1 padding, corrupt data");
            }

            byte[] val = new byte[stripLen - i];
            Buffer.BlockCopy(strip, i, val, 0, val.Length);
            return new BigInteger(val);
        }

        // Tests signature verification using test vectors from NIST CAVP.
        // http://csrc.nist.gov/groups/STM/cavp/digital-signatures.html
        internal static void TestSignatureVerification() {
            using (var reader = new System.IO.StreamReader(@"186-3ecdsatestvectors\SigVer.rsp")) {
                EllipticCurve curve = null;
                byte[] msg = null;
                BigInteger qx = null;
                BigInteger qy = null;
                BigInteger r = null;
                BigInteger s = null;
                string result = null;
                int testCount = 0;

                while (true) {
                    string line = reader.ReadLine();
                    if (line == null) {
                        break;
                    }
                    var match = System.Text.RegularExpressions.Regex.Match(line, @"\[([-\w]+),(SHA-\d+)\]");
                    if (match.Success) {
                        string curveName = "nist" + match.Groups[1].Value.ToLowerInvariant().Replace("-", "");
                        curve = FindByName(curveName);
                        if (curve != null) {
                            using (var hashFunc = ECDSAHashAlgorithmChooser.Choose(curve)) {
                                var hashName = "SHA-" + hashFunc.HashSize.ToString();
                                if (hashName == match.Groups[2].Value) {
                                    Debug.WriteLine("Test " + curve.CurveName);
                                }
                                else {
                                    // hash function doesn't match
                                    curve = null;
                                }
                            }
                        }
                        msg = null;
                        qx = qy = r = s = null;
                        result = null;
                        testCount = 0;
                        continue;
                    }

                    if (line.StartsWith("Msg = ") && curve != null) {
                        msg = BigIntegerConverter.ParseHex(line.Substring(6).Trim());
                        continue;
                    }

                    if (line.StartsWith("Qx = ") && curve != null) {
                        qx = new BigInteger(BigIntegerConverter.ParseHex(line.Substring(5).Trim()));
                        continue;
                    }

                    if (line.StartsWith("Qy = ") && curve != null) {
                        qy = new BigInteger(BigIntegerConverter.ParseHex(line.Substring(5).Trim()));
                        continue;
                    }

                    if (line.StartsWith("R = ") && curve != null) {
                        r = new BigInteger(BigIntegerConverter.ParseHex(line.Substring(4).Trim()));
                        continue;
                    }

                    if (line.StartsWith("S = ") && curve != null) {
                        s = new BigInteger(BigIntegerConverter.ParseHex(line.Substring(4).Trim()));
                        continue;
                    }

                    if (line.StartsWith("Result = ") && curve != null) {
                        result = line.Substring(9, 1);

                        if (msg != null && qx != null && qy != null && r != null && s != null) {
                            var pk = new ECDSAPublicKey(curve, new ECPoint(qx, qy));
                            var buf = new SSH2DataWriter();
                            buf.WriteBigInteger(r);
                            buf.WriteBigInteger(s);
                            var sig = buf.ToByteArray();
                            string verRes;
                            try {
                                pk.Verify(sig, msg);
                                verRes = "P";
                            }
                            catch (VerifyException) {
                                verRes = "F";
                            }
                            if (verRes != result) {
                                throw new Exception("verification result doesn't match");
                            }
                            ++testCount;
                            Debug.WriteLine("Pass #{0}", testCount);
                        }

                        msg = null;
                        qx = qy = r = s = null;
                        result = null;
                    }
                }
            }
        }

        private BigInteger SignCore(BigInteger input, BigInteger pe, BigInteger qe)
        {
            BigInteger p2 = (input % _p).ModPow(pe, _p);
            BigInteger q2 = (input % _q).ModPow(qe, _q);

            if (p2 == q2)
                return p2;

            BigInteger k;
            if (q2 > p2) {
                k = (q2 - p2) % _q;
            }
            else {
                // add multiple of _q greater than _p
                BigInteger d = _q + (_p / _q) * _q;
                k = (d + q2 - p2) % _q;
            }
            k = (k * _u) % _q;

            BigInteger result = k * _p + p2;

            return result;
        }

 public DSAPublicKey(BigInteger p, BigInteger g, BigInteger q, BigInteger y)
 {
     _p = p;
     _g = g;
     _q = q;
     _y = y;
 }

 public DSAKeyPair(BigInteger p, BigInteger g, BigInteger q, BigInteger y, BigInteger x)
 {
     _publickey = new DSAPublicKey(p, g, q, y);
     _x = x;
 }

        /// <summary>
        /// Point dooubling over the curve
        /// </summary>
        private bool PointDouble(
                BigInteger.ModulusRing ring,
                ECPoint p1,
                out ECPoint p3) {

            if (p1 is ECPointAtInfinity) {
                p3 = p1;
                return true;
            }

            if (p1.Y == 0) {
                p3 = new ECPointAtInfinity();
                return true;
            }

            // x3 = {(3 * x1^2 + a)/(2 * y1)}^2 - (2 * x1)
            // y3 = {(3 * x1^2 + a)/(2 * y1)} * (x1 - x3) - y1

            try {
                BigInteger x1 = p1.X;
                BigInteger y1 = p1.Y;

                BigInteger x1_2 = ring.Multiply(x1, x1);
                BigInteger lambda = ring.Multiply(x1_2 + x1_2 + x1_2 + a, (y1 + y1).ModInverse(p));
                BigInteger x3 = ring.Difference(ring.Multiply(lambda, lambda), x1 + x1);
                BigInteger y3 = ring.Difference(ring.Multiply(lambda, ring.Difference(x1, x3)), y1);
                p3 = new ECPoint(x3, y3);
                return true;
            }
            catch (Exception) {
                p3 = null;
                return false;
            }
        }

        private static BigInteger findRandomGenerator(BigInteger order, BigInteger modulo, Rng random)
        {
            BigInteger one = new BigInteger(1);
            BigInteger aux = modulo - new BigInteger(1);
            BigInteger t = aux % order;
            BigInteger generator;

            if (AsUInt64(t) != 0) {
                return null;
            }

            t = aux / order;

            while (true) {
                generator = BigInteger.GenerateRandom(modulo.BitCount());
                generator = generator % modulo;
                generator = generator.ModPow(t, modulo);
                if (generator != one)
                    break;
            }

            aux = generator.ModPow(order, modulo);

            if (aux != one) {
                return null;
            }

            return generator;
        }

 /// <summary>
 /// Calculate point multiplication
 /// </summary>
 /// <param name="k1">scalar</param>
 /// <param name="k2">scalar</param>
 /// <param name="t">point</param>
 /// <param name="infinityToNull">
 /// if result was point-at-infinity, and this parameter was true,
 /// null is returned instead of <see cref="ECPointAtInfinity"/>.
 /// </param>
 /// <returns>point on the curve, point at infinity, or null if failed</returns>
 public override ECPoint PointMul(BigInteger k1, BigInteger k2, ECPoint t, bool infinityToNull) {
     BigInteger.ModulusRing ring = new BigInteger.ModulusRing(p);
     BigInteger k = ring.Multiply(k1, k2);
     return PointMul(k, t, infinityToNull);
 }

        /// <summary>
        /// Point addition over the curve
        /// </summary>
        private bool PointAdd(
                BigInteger.ModulusRing ring,
                ECPoint p1,
                ECPoint p2,
                out ECPoint p3) {

            if (p1 is ECPointAtInfinity) {
                p3 = p2;
                return true;
            }
            if (p2 is ECPointAtInfinity) {
                p3 = p1;
                return true;
            }

            if (p1.X == p2.X) {
                if (p1.Y == p2.Y) {
                    return PointDouble(ring, p1, out p3);
                }
                else {
                    p3 = new ECPointAtInfinity();
                    return true;
                }
            }

            // x3 = {(y2 - y1)/(x2 - x1)}^2 - (x1 + x2)
            // y3 = {(y2 - y1)/(x2 - x1)} * (x1 - x3) - y1

            try {
                BigInteger x1 = p1.X;
                BigInteger y1 = p1.Y;
                BigInteger x2 = p2.X;
                BigInteger y2 = p2.Y;

                BigInteger lambda = ring.Multiply(ring.Difference(y2, y1), ring.Difference(x2, x1).ModInverse(p));
                BigInteger x3 = ring.Difference(ring.Multiply(lambda, lambda), x1 + x2);
                BigInteger y3 = ring.Difference(ring.Multiply(lambda, ring.Difference(x1, x3)), y1);
                p3 = new ECPoint(x3, y3);
                return true;
            }
            catch (Exception) {
                p3 = null;
                return false;
            }
        }

 /// <summary>
 /// Validate if the point satisfies the equation of the elliptic curve.
 /// </summary>
 /// <param name="x">value of X</param>
 /// <param name="y">value of Y</param>
 /// <returns>true if the values satisfy.</returns>
 public override bool ValidatePoint(BigInteger x, BigInteger y) {
     if (x == 0 || x >= p || y == 0 || y >= p) {
         return false;
     }
     BigInteger y2 = (y * y) % p;
     BigInteger fx = ((x * x + a) * x + b) % p;
     return y2 == fx;
 }

 /// <summary>
 /// Constructor
 /// </summary>
 /// <param name="algorithm">public key algorithm which uses this curve</param>
 /// <param name="curveName">curve name</param>
 /// <param name="p">odd prime</param>
 /// <param name="a">curve parameter</param>
 /// <param name="b">curve parameter</param>
 /// <param name="G">base point</param>
 /// <param name="n">order n of G</param>
 /// <param name="h">cofactor</param>
 public EllipticCurveFp(
         PublicKeyAlgorithm algorithm, string curveName,
         BigInteger p, BigInteger a, BigInteger b, ECPoint G, BigInteger n, BigInteger h) {
     this._algorithm = algorithm;
     this._curveName = curveName;
     this.p = p;
     this.a = a;
     this.b = b;
     this.G = G;
     this.n = n;
     this.h = h;
 }

        // Tests point-multiplication using test vectors
        // http://point-at-infinity.org/ecc/nisttv
        internal static void TestPointMultiplication() {
            using (var reader = new System.IO.StreamReader(@"nisttv")) {
                EllipticCurve curve = null;
                string ks = null;
                BigInteger k = null;
                BigInteger x = null;
                BigInteger y = null;
                int testCount = 0;

                while (true) {
                    string line = reader.ReadLine();
                    if (line == null) {
                        break;
                    }
                    var match = System.Text.RegularExpressions.Regex.Match(line, @"Curve:\s+(\w+)");
                    if (match.Success) {
                        string curveName = "nist" + match.Groups[1].Value.ToLowerInvariant();
                        curve = FindByName(curveName);
                        if (curve != null) {
                            Debug.WriteLine("Test " + curve.CurveName);
                        }
                        ks = null;
                        k = x = y = null;
                        testCount = 0;
                        continue;
                    }

                    if (line.StartsWith("k = ") && curve != null) {
                        ks = line.Substring(4).Trim();
                        k = BigInteger.Parse(ks);
                        continue;
                    }

                    if (line.StartsWith("x = ") && curve != null) {
                        x = new BigInteger(BigIntegerConverter.ParseHex(line.Substring(4).Trim()));
                        continue;
                    }

                    if (line.StartsWith("y = ") && curve != null) {
                        y = new BigInteger(BigIntegerConverter.ParseHex(line.Substring(4).Trim()));

                        if (k != null && x != null) {
                            ECPoint p = curve.PointMul(k, curve.BasePoint, true);
                            if (p == null || p is ECPointAtInfinity) {
                                throw new Exception("test failed");
                            }
                            if (p.X != x) {
                                throw new Exception("test failed: X doesn't match");
                            }
                            if (p.Y != y) {
                                throw new Exception("test failed: Y doesn't match");
                            }
                            ++testCount;
                            Debug.WriteLine("Pass #{0} : {1}", testCount, ks);
                        }

                        k = x = y = null;
                    }
                }
            }
        }

        // Tests public key validation using test vectors from NIST CAVP.
        // http://csrc.nist.gov/groups/STM/cavp/digital-signatures.html
        internal static void TestPKV() {
            using (var reader = new System.IO.StreamReader(@"186-3ecdsatestvectors\PKV.rsp")) {
                EllipticCurve curve = null;
                string qxs = null;
                BigInteger qx = null;
                BigInteger qy = null;
                string result = null;
                int testCount = 0;

                while (true) {
                    string line = reader.ReadLine();
                    if (line == null) {
                        break;
                    }
                    var match = System.Text.RegularExpressions.Regex.Match(line, @"\[([-\w]+)\]");
                    if (match.Success) {
                        string curveName = "nist" + match.Groups[1].Value.ToLowerInvariant().Replace("-", "");
                        curve = FindByName(curveName);
                        if (curve != null) {
                            Debug.WriteLine("Test " + curve.CurveName);
                        }
                        qx = qy = null;
                        qxs = null;
                        result = null;
                        testCount = 0;
                        continue;
                    }

                    if (line.StartsWith("Qx = ") && curve != null) {
                        qxs = line.Substring(5).Trim();
                        qx = new BigInteger(BigIntegerConverter.ParseHex(qxs));
                        continue;
                    }

                    if (line.StartsWith("Qy = ") && curve != null) {
                        qy = new BigInteger(BigIntegerConverter.ParseHex(line.Substring(5).Trim()));
                        continue;
                    }

                    if (line.StartsWith("Result = ") && curve != null) {
                        result = line.Substring(9, 1);

                        if (qx != null && qy != null) {
                            var pk = new ECDSAPublicKey(curve, new ECPoint(qx, qy));
                            string r = pk.IsValid() ? "P" : "F";
                            if (r != result) {
                                throw new Exception("validation result doesn't match");
                            }
                            ++testCount;
                            Debug.WriteLine("Pass #{0} : {1}", testCount, qxs);
                        }

                        qx = qy = null;
                        qxs = null;
                        result = null;
                    }
                }
            }
        }