rsa_e_3.c 6.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202
  1. /* rsa_e_3.c
  2. **
  3. ** Copyright 2008, The Android Open Source Project
  4. **
  5. ** Redistribution and use in source and binary forms, with or without
  6. ** modification, are permitted provided that the following conditions are met:
  7. ** * Redistributions of source code must retain the above copyright
  8. ** notice, this list of conditions and the following disclaimer.
  9. ** * Redistributions in binary form must reproduce the above copyright
  10. ** notice, this list of conditions and the following disclaimer in the
  11. ** documentation and/or other materials provided with the distribution.
  12. ** * Neither the name of Google Inc. nor the names of its contributors may
  13. ** be used to endorse or promote products derived from this software
  14. ** without specific prior written permission.
  15. **
  16. ** THIS SOFTWARE IS PROVIDED BY Google Inc. ``AS IS'' AND ANY EXPRESS OR
  17. ** IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
  18. ** MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
  19. ** EVENT SHALL Google Inc. BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  20. ** SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  21. ** PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
  22. ** OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
  23. ** WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
  24. ** OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
  25. ** ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  26. */
  27. #include "mincrypt/rsa.h"
  28. #include "mincrypt/sha.h"
  29. /* a[] -= mod */
  30. static void subM(const RSAPublicKey *key, uint32_t *a) {
  31. int64_t A = 0;
  32. int i;
  33. for (i = 0; i < key->len; ++i) {
  34. A += (uint64_t)a[i] - key->n[i];
  35. a[i] = (uint32_t)A;
  36. A >>= 32;
  37. }
  38. }
  39. /* return a[] >= mod */
  40. static int geM(const RSAPublicKey *key, const uint32_t *a) {
  41. int i;
  42. for (i = key->len; i;) {
  43. --i;
  44. if (a[i] < key->n[i]) return 0;
  45. if (a[i] > key->n[i]) return 1;
  46. }
  47. return 1; /* equal */
  48. }
  49. /* montgomery c[] += a * b[] / R % mod */
  50. static void montMulAdd(const RSAPublicKey *key,
  51. uint32_t* c,
  52. const uint32_t a,
  53. const uint32_t* b) {
  54. uint64_t A = (uint64_t)a * b[0] + c[0];
  55. uint32_t d0 = (uint32_t)A * key->n0inv;
  56. uint64_t B = (uint64_t)d0 * key->n[0] + (uint32_t)A;
  57. int i;
  58. for (i = 1; i < key->len; ++i) {
  59. A = (A >> 32) + (uint64_t)a * b[i] + c[i];
  60. B = (B >> 32) + (uint64_t)d0 * key->n[i] + (uint32_t)A;
  61. c[i - 1] = (uint32_t)B;
  62. }
  63. A = (A >> 32) + (B >> 32);
  64. c[i - 1] = (uint32_t)A;
  65. if (A >> 32) {
  66. subM(key, c);
  67. }
  68. }
  69. /* montgomery c[] = a[] * b[] / R % mod */
  70. static void montMul(const RSAPublicKey *key,
  71. uint32_t* c,
  72. const uint32_t* a,
  73. const uint32_t* b) {
  74. int i;
  75. for (i = 0; i < key->len; ++i) {
  76. c[i] = 0;
  77. }
  78. for (i = 0; i < key->len; ++i) {
  79. montMulAdd(key, c, a[i], b);
  80. }
  81. }
  82. /* In-place public exponentiation.
  83. ** Input and output big-endian byte array in inout.
  84. */
  85. static void modpow3(const RSAPublicKey *key,
  86. uint8_t* inout) {
  87. uint32_t a[RSANUMWORDS];
  88. uint32_t aR[RSANUMWORDS];
  89. uint32_t aaR[RSANUMWORDS];
  90. uint32_t *aaa = aR; /* Re-use location. */
  91. int i;
  92. /* Convert from big endian byte array to little endian word array. */
  93. for (i = 0; i < key->len; ++i) {
  94. uint32_t tmp =
  95. (inout[((key->len - 1 - i) * 4) + 0] << 24) |
  96. (inout[((key->len - 1 - i) * 4) + 1] << 16) |
  97. (inout[((key->len - 1 - i) * 4) + 2] << 8) |
  98. (inout[((key->len - 1 - i) * 4) + 3] << 0);
  99. a[i] = tmp;
  100. }
  101. montMul(key, aR, a, key->rr); /* aR = a * RR / R mod M */
  102. montMul(key, aaR, aR, aR); /* aaR = aR * aR / R mod M */
  103. montMul(key, aaa, aaR, a); /* aaa = aaR * a / R mod M */
  104. /* Make sure aaa < mod; aaa is at most 1x mod too large. */
  105. if (geM(key, aaa)) {
  106. subM(key, aaa);
  107. }
  108. /* Convert to bigendian byte array */
  109. for (i = key->len - 1; i >= 0; --i) {
  110. uint32_t tmp = aaa[i];
  111. *inout++ = tmp >> 24;
  112. *inout++ = tmp >> 16;
  113. *inout++ = tmp >> 8;
  114. *inout++ = tmp >> 0;
  115. }
  116. }
  117. /* Expected PKCS1.5 signature padding bytes, for a keytool RSA signature.
  118. ** Has the 0-length optional parameter encoded in the ASN1 (as opposed to the
  119. ** other flavor which omits the optional parameter entirely). This code does not
  120. ** accept signatures without the optional parameter.
  121. */
  122. static const uint8_t padding[RSANUMBYTES - SHA_DIGEST_SIZE] = {
  123. 0x00,0x01,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,
  124. 0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,
  125. 0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,
  126. 0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,
  127. 0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,
  128. 0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,
  129. 0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,
  130. 0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,
  131. 0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,
  132. 0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,
  133. 0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,
  134. 0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,
  135. 0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,
  136. 0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,
  137. 0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,
  138. 0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,
  139. 0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0x00,
  140. 0x30,0x21,0x30,0x09,0x06,0x05,0x2b,0x0e,0x03,0x02,0x1a,0x05,0x00,
  141. 0x04,0x14
  142. };
  143. /* Verify a 2048 bit RSA e=3 PKCS1.5 signature against an expected SHA-1 hash.
  144. ** Returns 0 on failure, 1 on success.
  145. */
  146. int RSA_e_3_verify(const RSAPublicKey *key,
  147. const uint8_t *signature,
  148. const int len,
  149. const uint8_t *sha) {
  150. uint8_t buf[RSANUMBYTES];
  151. int i;
  152. if (key->len != RSANUMWORDS) {
  153. return 0; /* Wrong key passed in. */
  154. }
  155. if (len != sizeof(buf)) {
  156. return 0; /* Wrong input length. */
  157. }
  158. if (key->exponent != 3) {
  159. return 0; // Wrong exponent.
  160. }
  161. for (i = 0; i < len; ++i) {
  162. buf[i] = signature[i];
  163. }
  164. modpow3(key, buf);
  165. /* Check pkcs1.5 padding bytes. */
  166. for (i = 0; i < (int) sizeof(padding); ++i) {
  167. if (buf[i] != padding[i]) {
  168. return 0;
  169. }
  170. }
  171. /* Check sha digest matches. */
  172. for (; i < len; ++i) {
  173. if (buf[i] != *sha++) {
  174. return 0;
  175. }
  176. }
  177. return 1;
  178. }