1

Megaを試すための単純なクライアント アプリを作成していますが、RSA の使用方法に頭を悩ませています。たとえば、セッション ID の復号化を考えてみましょう。これは、ログインするために最初に行う必要があることの 1 つです。

API は、次の RSA データを提供します。

  • p (1024 ビット)
  • q (1024 ビット)
  • d (2044 ビット)
  • u (1024 ビット)

そもそも、「u」が何の略なのかわかりません。コードから計算されていることがわかりますmodinverse(p, q)-これは一般にqInverseと呼ばれるものですか?

これは、私が以前に使用したものよりも秘密鍵の RSA データがかなり少ないため、どうすればよいかよくわかりません。ただし、RSACryptoServiceProvider によって使用される RSA データの一部は、最適化のために事前に計算されたデータにすぎないことを理解しなければならないので、残りは必要ないのではないでしょうか?

このデータを使用して、サイトの JavaScript は次の関数でセッション ID を復号化します。

// Compute m**d mod p*q for RSA private key operations.

function RSAdecrypt(m, d, p, q, u)
{
 var xp = bmodexp(bmod(m,p), bmod(d,bsub(p,[1])), p);
 var xq = bmodexp(bmod(m,q), bmod(d,bsub(q,[1])), q);

 var t=bsub(xq,xp);
 if(t.length==0)
 {
  t=bsub(xp,xq);
  t=bmod(bmul(t, u), q);
  t=bsub(q,t);
 }
 else
 {
  t=bmod(bmul(t, u), q);
 } 
 return badd(bmul(t,p), xp);
}

RSACryptoServiceProvider を使用して .NET でこれを実行したいのですが、4 つのデータを渡すと (u == qInverse と仮定)、インポート中にキーが拒否され、「Bad data」例外が発生します。

データに対してさらに何かを行う必要がありますか? この状況で RSACryptoServiceProvider を使用できますか?

私がテストしているパラメーターと暗号化されたデータの例は次のとおりです。

 var p = Convert.FromBase64String("1AkMwy3SPbJtL/k2RUPNztBQKow0NX9LVr5/73+zR3cuwgUToYkVefKdzlTgeri9CAVUq/+jU6o+P7sUpPUN+V97quZa00m3GSIdonRMdaMrDDH5aHnkQgOsCjLJDWXU6+TQBqLumR3XMSat3VO09Dps+6NcMc+uMi5atC3tb+0=");
 var q = Convert.FromBase64String("qtnlmPbATJajNdihw1K6cwSormySATp7g75vYfilYx6RXN3xpNCZR/i8zFbx/lDh+n1a2rdHy1nWyuaD3UmE26d1xUkmsPDfBc72WXt88UqWE/gF7NJjtgTxS2Ui+2GGKUCloi5UA/pOI7R5TBvGI8zna00SH78bctyE0dcAcwM=");
 var d = Convert.FromBase64String("CFL4QPQ8zLzrf2bUzCVX8S2/eALzo/P2cvQsW9lft7uelHYfC1CvHP+z4RvQgXABpgT8YTdU+sgdMHrhHT1vxeUaDRkcQv9lV0IP6YtAcD+gk5jDQkXk4ruYztTUF3v4u8rlMuZ8kAKKWKw+JH6grLWD/vXjMv2RybxPqq3fKI6VJaj/Y/ZnDjD5HrQmJopnCbOrZrPysNb/rGrN3ad9ysaZwBvQtIE0/tQvmL+lsI+PfF9oGKeHkciIo0D4N2abOKT2fiazNm1U9LnrQih687ge0aeAlP2OO8c0h/nbEkMbNg83n1GGEt3DNojIWbT5uHaj12M6G81leS77mfLvSQ==");
 var u = Convert.FromBase64String("CNlUzgCf6Ymd/qeWiv3ScCIXYCwjP3SNLHxRgozIbNg2JEKpJn2M3vO72qLI+FT34xckaAGIcKWMkmpoaKy6PYF4jsAz2atLEClLimbMEPvpWxK7b/I5yvXMT7i2r5hr0OjjplL0wFQYL1IS2M8DTrL99rd9zXCoCWg5Tax6zQM=");

 var encryptedData = Convert.FromBase64String("CABt/Qp7ZODvweEk5RY9JNMXoyFfUwMnc53zbP5jB4jnwWXibLLvjc+Dv5CwQAtUYRme+vRd80++178BiWl0YSOKKhQaDQKoeOUONn3KbZVWyCtyWyQZNtASPoQfizay/Dw3yP5BKsJmDpEv47awdEZzh8IqTcTKeQbpHFL+3uL5EjIENpxMh15rJUsY9w+jq6Yax+379tq67EPMUON0aYkRQ3k1Rsp9fOL6qrgoqOPmOc0cIQgx76t6SFB9LmDySkyBhtK+vcEkdn9GwzZqc6n/Jqt9K8a+mbBv3K7eO3Pa37SDncsaxEzlyLwQ2om1+bK2QwauSQl+7QwQS1a9Ejb9");

 var rsa = new RSACryptoServiceProvider();

 // Throws exception saying "Bad data"
 rsa.ImportParameters(new RSAParameters
 {
      D = d,
      P = p,
      Q = q,
      InverseQ = u
  });

補遺 2 月 2 日

リンクされた StackOverflow の回答を掘り下げて、不足しているコンポーネントを生成する方法を決定したと思うポイントに到達しました。しかし、今では「Bad key」という例外が発生して困っています。

欠落しているコンポーネントを生成するために使用しているコードを書きます - おそらくどこかでエラーを見つけることができますか?

InverseQ と D も手動で計算しましたが、値は入力データの値と一致しています。以下は、q、p、および e のみに基づいて必要なデータを生成するための関数です。

private static RSAParameters CalculateRsaParameters(BigInteger p, BigInteger q, BigInteger e)
{
    var modulus = BigInteger.Multiply(p, q);

    var phi = BigInteger.Multiply(BigInteger.Subtract(p, BigInteger.One), BigInteger.Subtract(q, BigInteger.One));

    BigInteger x, y;
    // From http://www.codeproject.com/Articles/60108/BigInteger-Library
    // Returns 1 with my test data.
    ExtendedEuclidGcd(e, phi, out x, out y);

    var d = BigInteger.Remainder(x, phi);

    var dp = BigInteger.Remainder(d, BigInteger.Subtract(p, BigInteger.One));
    var dq = BigInteger.Remainder(d, BigInteger.Subtract(q, BigInteger.One));

    BigInteger x2, y2;
    // Returns 1 with my test data.
    ExtendedEuclidGcd(q, p, out x2, out y2);

    // y2 since it matched the pre-generated inverseQ data I had and x2 was some negative value, so it did not seem to fit. I have no idea what the logic behind which to pick really is.
    var qInverse = BigInteger.Remainder(y2, p);

    return new RSAParameters
    {
        D = ToBigEndianByteArray(d, 256),
        DP = ToBigEndianByteArray(dp, 128),
        DQ = ToBigEndianByteArray(dq, 128),
        InverseQ = ToBigEndianByteArray(qInverse, 128),
        Exponent = ToBigEndianByteArray(e, 1),
        Modulus = ToBigEndianByteArray(modulus, 256),
        P = ToBigEndianByteArray(p, 128),
        Q = ToBigEndianByteArray(q, 128)
    };
}

私の入力データは次のとおりです。

e = 17
p = 148896287039501678969147386479458178246000691707699594019852371996225136011987881033904404601666619814302065310828663028471342954821076961960815187788626496609581811628527023262215778397482476920164511192915070597893567835708908996890192512834283979142025668876250608381744928577381330716218105191496818716653
q = 119975764355551220778509708561576785383941026741388506773912560292606151764383332427604710071170171329268379604135341015979284377183953677973647259809025842247294479469402755370769383988530082830904396657573472653613365794770434467132057189606171325505138499276437937752474437953713231209677228298628994462467

そして、これが私が生成された構造をどのように利用するかです:

var rsa = new RSACryptoServiceProvider(2048);
rsa.ImportParameters(CalculateRsaParameters(p, q, e));

このImportParameters呼び出しは、「Bad key」という例外をスローします。私は何を間違っていますか？

Q と P を入れ替えるとどうなりますか?

どうやら、RSACryptoServiceProvider にデータを受け入れさせるようです! しかし、これは正確にはどういう意味ですか？

ExtendedEuclidGcd生成コードで使用しなければならなかった方法からアイデアを得ました。2 つのインスタンスに異なる出力を使用しなければならないことが非常に面倒だったので、この実験を行いました。

一つu != qInverseは、これは正しいですか？私は元の JavaScript 関数の数学を理解していないので、その意味がわかりません。元の u 値は、実際には QInverse ではなく、内部のショートカットであると推測できますか?

さらなるテスト (つまり、データの実際の復号化) が続きます。一度行われた新しい展開で質問を編集します。

このパラメーター セットでは復号化に失敗します

私が持っている暗号化されたテスト データは (base64 エンコード) です。

/TYSvVZLEAztfglJrgZDtrL5tYnaELzI5UzEGsudg7Tf2nM73q7cb7CZvsYrfasm/6lzajbDRn92JMG9vtKGgUxK8mAufVBIeqvvMQghHM055uOoKLiq+uJ8fcpGNXlDEYlpdONQzEPsutr2++3HGqarow/3GEsla16HTJw2BDIS+eLe/lIc6QZ5ysRNKsKHc0Z0sLbjL5EOZsIqQf7INzz8sjaLH4Q+EtA2GSRbcivIVpVtyn02DuV4qAINGhQqiiNhdGmJAb/Xvk/zXfT6nhlhVAtAsJC/g8+N77Js4mXB54gHY/5s851zJwNTXyGjF9MkPRblJOHB7+Bkewr9bQ==
or
bf0Ke2Tg78HhJOUWPSTTF6MhX1MDJ3Od82z+YweI58Fl4myy743Pg7+QsEALVGEZnvr0XfNPvte/AYlpdGEjiioUGg0CqHjlDjZ9ym2VVsgrclskGTbQEj6EH4s2svw8N8j+QSrCZg6RL+O2sHRGc4fCKk3EynkG6RxS/t7i+RIyBDacTIdeayVLGPcPo6umGsft+/bauuxDzFDjdGmJEUN5NUbKfXzi+qq4KKjj5jnNHCEIMe+rekhQfS5g8kpMgYbSvr3BJHZ/RsM2anOp/yarfSvGvpmwb9yu3jtz2t+0g53LGsRM5ci8ENqJtfmytkMGrkkJfu0MEEtWvRI2/Q==

バイト順がわからないため、2 つの選択肢を示します。両方の文字列で同じデータです。

これらの両方の復号化は失敗し、最初のケースでは「不正なデータ」と「このコマンドを処理するのに十分なストレージがありません」という例外が表示されます。2 番目のケース (MSDN の主張は、キーが暗号化されたデータと一致しないことを意味している可能性があります)。PKCS パディングが使用されていることを RSACryptoServiceProvider に伝えていますが、OAEP も試しました (パディングのデコードに失敗したというエラーが発生しました)。

元の JavaScript は問題なくデータを復号化しますが、"p" と "q" は私のものと入れ替わっています。

現在、私の質問は次のとおりです。

  • P と Q の切り替えは有効な操作ですか?
  • 私の推論は有効ですか、それともどこかで間違いを犯しましたか?
  • テスト データを正常に復号化するには、次に何をすればよいですか?
4

2 に答える 2

2

RsaParameters には 8 つのフィールドがあります。秘密鍵を作成するときに、それらをすべて初期化する必要があると思います。

http://msdn.microsoft.com/en-us/library/system.security.cryptography.rsaparameters.aspxをご覧ください。

于 2013-01-29T06:03:05.443 に答える
0

.NET BigInteger および RSA パラメータを使用する際につまずく可能性のある落とし穴がいくつかあります。おそらくあなたに影響を与えているのは、エンディアンと先行ゼロ抑制の2つです。

System.Numerics.BigIntegerToByteArray()クラスは、.NET 4.0 以降で使用可能になり、そのメソッドとnew BigInteger(byte [])コンストラクターにリテ エンディアン形式を使用します。

残念ながら、このRSAParameters構造では、バイト配列フ​​ィールドがビッグ エンディアン順であることが想定されています。考慮しなければならないもう 1 つの非互換性もあります。ASystem.Numerics.BigIntegerは正または負のいずれかであり、ToByteArray()メソッドは 2 の補数表現の変形を使用してこれを説明します。事実上、これは、バイト配列表現が上位バイト >= 128 を持つ正の BigInteger には、最上位位置に追加のゼロ バイトが配置されることを意味します。ただし、RSAParameterフィールドはすべて正であると想定されるため、先行ゼロは「Bad Data」CryptographicException で無償で拒否されます。これらの先頭のゼロは、発生した場所で削除する必要があります。

以下は、これらの操作を示す簡単なコード フラグメントの例です。

    static BigInteger ExtGCD(BigInteger a, BigInteger b, out BigInteger lastx, out BigInteger lasty)
    {
        var x = BigInteger.Zero;
        lastx = BigInteger.One;
        var y = BigInteger.One;
        lasty = BigInteger.Zero;
        while (!b.IsZero)
        {
            BigInteger remainder;
            BigInteger q = BigInteger.DivRem(a, b, out remainder);
            a = b;
            b = remainder;
            var t = x;
            x = lastx - q * x;
            lastx = t;
            t = y;
            y = lasty - q * y;
            lasty = t;
        }

        return a;
    }

    static BigInteger inverse(BigInteger a, BigInteger n)
    {
        BigInteger d, x, y;
        d = ExtGCD(a, n, out x, out y);
        if (d.IsOne)
        {
            // Always return the least positive value
            return (x + n) % n;
        }
        else
        {
            throw new ArgumentException("the arguments must be relatively prime, i.e. their gcd must be 1");
        }
    }

    static byte[] ToByteArrayBE(BigInteger b)
    {
        var x = b.ToByteArray(); // x is little-endian
        Array.Reverse(x);        // now it is big-endian
        if (x[0] == 0)
        {
            var newarray = new byte[x.Length - 1];
            Array.Copy(x, 1, newarray, 0, newarray.Length);
            return newarray;
        } else
        {
            return x;
        }
    }
    static RSAParameters CalculateRsaParameters(BigInteger p, BigInteger q, BigInteger e)
    {
        // Given p, q, and e (the RSA encryption exponent) compute the remaining parameters

        var phi = (p - 1) * (q - 1);

        var d = inverse(e, phi);
        var dp = d % (p - 1);
        var dq = d % (q - 1);
        var qInv = inverse(q, p);

        var RsaParams = new RSAParameters
        {
            Modulus = ToByteArrayBE(p * q),
            Exponent = ToByteArrayBE(e),
            P = ToByteArrayBE(p),
            Q = ToByteArrayBE(q),
            D = ToByteArrayBE(d),
            DP = ToByteArrayBE(dp),
            DQ = ToByteArrayBE(dq),
            InverseQ = ToByteArrayBE(qInv)
        };
        return RsaParams;
    }

    static void Main(string[] args)
    {
        BigInteger p = BigInteger.Parse("148896287039501678969147386479458178246000691707699594019852371996225136011987881033904404601666619814302065310828663028471342954821076961960815187788626496609581811628527023262215778397482476920164511192915070597893567835708908996890192512834283979142025668876250608381744928577381330716218105191496818716653");
        BigInteger q = BigInteger.Parse("119975764355551220778509708561576785383941026741388506773912560292606151764383332427604710071170171329268379604135341015979284377183953677973647259809025842247294479469402755370769383988530082830904396657573472653613365794770434467132057189606171325505138499276437937752474437953713231209677228298628994462467");
        BigInteger e = new BigInteger(17);
        RSAParameters RsaParams = CalculateRsaParameters(p, q, e);
        var Rsa = new RSACryptoServiceProvider();
        Rsa.ImportParameters(RsaParams);
    }
}
于 2013-02-03T16:34:34.383 に答える