Databases
StackOverflow2013
Postsdbo
POHow do I use RSACryptoServiceProvider to decrypt, given that I only have p, q, d and u?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POHow do I use RSACryptoServiceProvider to decrypt, given that I only have p, q, d and u?
    primarykey
    data
    text
    <p>I am creating a simple client app to experiment with <a href="http://mega.co.nz" rel="nofollow">Mega</a> and I am having trouble wrapping my head around the way RSA is used. Let's take, for example, the decryption of the session ID - this is one of the first things that must be done in order to log in.</p> <p>The API provides me the following RSA data:</p> <ul> <li>p (1024 bits)</li> <li>q (1024 bits)</li> <li>d (2044 bits)</li> <li>u (1024 bits)</li> </ul> <p>To start with, I do not know what "u" stands for. I see from code that it is calculated by <code>modinverse(p, q)</code> - is this what is commonly referred to as qInverse?</p> <p>This is considerably less RSA data for a private key than I have used previously, so I am not quite sure what to make of it. However, I am given to understand that some of the RSA data used by RSACryptoServiceProvider is just pre-calculated data for optimization purposes, so perhaps the rest is not needed?</p> <p>Using this data, the site's JavaScript decrypts the session ID with the following function:</p> <pre><code>// 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); } </code></pre> <p>I would like to do this in .NET using RSACryptoServiceProvider but if I give it the 4 pieces of data I have (assuming u == qInverse), the key is rejected during import with a "Bad data" exception.</p> <p>Should I be doing something more to the data? Is RSACryptoServiceProvider usable in this situation at all?</p> <p>Example of the parameters and encrypted data I am testing with follows.</p> <pre><code> 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 }); </code></pre> <p><strong>Addendum February 2</strong></p> <p>I have dug around in the linked StackOverflow answers and have reached the point where I think I have determined how to generate the missing component. However, now I am getting a "Bad key" exception, which has me stumped.</p> <p>I will write the code I am using to generate the missing components - perhaps you can spot an error somewhere?</p> <p>I have also calculated InverseQ and D manually and the values match those in my input data. Below is my function for generating the required data based only on q, p and e.</p> <pre><code>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) }; } </code></pre> <p>My input data is:</p> <pre><code>e = 17 p = 148896287039501678969147386479458178246000691707699594019852371996225136011987881033904404601666619814302065310828663028471342954821076961960815187788626496609581811628527023262215778397482476920164511192915070597893567835708908996890192512834283979142025668876250608381744928577381330716218105191496818716653 q = 119975764355551220778509708561576785383941026741388506773912560292606151764383332427604710071170171329268379604135341015979284377183953677973647259809025842247294479469402755370769383988530082830904396657573472653613365794770434467132057189606171325505138499276437937752474437953713231209677228298628994462467 </code></pre> <p>And here is how I make use of the generated structure:</p> <pre><code>var rsa = new RSACryptoServiceProvider(2048); rsa.ImportParameters(CalculateRsaParameters(p, q, e)); </code></pre> <p>The <code>ImportParameters</code> call throws an exception saying "Bad key". What am I doing wrong?</p> <p><strong>What happens if I switch Q and P?</strong></p> <p>Apparently, it makes RSACryptoServiceProvider accept the data! But what does this mean exactly?</p> <p>I got the idea from the way I had to use <code>ExtendedEuclidGcd</code> in my generation code. Having to use different outputs for the two instances bothered me a lot, so I performed this experiment.</p> <p>One thing is that <code>u != qInverse</code> - is this correct? I do not understand the math in the original JavaScript function, so I am not sure what the implications are. Am I right in guessing that the u value in the original is in fact some internal shortcut and not QInverse?</p> <p>Further testing to follow (i.e. actual decryption of data). I will edit the question with any new developments once made.</p> <p><strong>Decryption fails with this parameter set</strong></p> <p>The encrypted test data I have is (base64-encoded):</p> <pre><code>/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== </code></pre> <p>Two alternatives given since I am not sure of the byte order. It is the same data in both strings.</p> <p>Decryption of both of these fails with an exception saying "Bad data" in the first case and "Not enough storage is available to process this command." in the second case (which MSDN claims might mean that the key does not match the encrypted data). I am telling RSACryptoServiceProvider that PKCS padding is used, though I also experimented with OAEP (which just gave an error about failing to decode padding).</p> <p>The original JavaScript decrypts the data without a problem, though its "p" and "q" are switched around from mine.</p> <p>Right now, my questions are:</p> <ul> <li>Is the P and Q switch-around a valid operation to do?</li> <li>Is my reasoning valid or have I made a mistake somewhere?</li> <li>What should I do next to successfully decrypt my test data?</li> </ul>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USSander
    1. USSander
    plurals
    1. PL
      singulars
      1. LTLinked
    2. PL
      singulars
      1. LTLinked
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POHow do I use RSACryptoServiceProvider to decrypt, given that I only have p, q, d and u?
      1. USzsp500
      1. VTFavorite
    1. COYou need to calculate the remaining parameters. See: http://stackoverflow.com/questions/14229040/how-to-calculate-d-for-rsa-encryption-from-p-q-and-e
      singulars
      1. POHow do I use RSACryptoServiceProvider to decrypt, given that I only have p, q, d and u?
      1. USCodesInChaos
    2. COYou are missing the 'e' parameter. It is apparently 17.
      singulars
      1. POHow do I use RSACryptoServiceProvider to decrypt, given that I only have p, q, d and u?
      1. USJames K Polk
    3. CO@GregS I think you put it here nicely: http://stackoverflow.com/questions/14192335/mapping-rsa-encryption-parameters-from-crt-chinese-remainder-theorem-to-net-f/14195667#14195667
      singulars
      1. POHow do I use RSACryptoServiceProvider to decrypt, given that I only have p, q, d and u?
      1. USMaarten Bodewes
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload