1/* rsa_e_f4.c
2**
3** Copyright 2012, 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
28#include "mincrypt/rsa.h"
29#include "mincrypt/sha.h"
30
31// a[] -= mod
32static void subM(const RSAPublicKey* key,
33                 uint32_t* a) {
34  int64_t A = 0;
35  int i;
36  for (i = 0; i < key->len; ++i) {
37    A += (uint64_t)a[i] - key->n[i];
38    a[i] = (uint32_t)A;
39    A >>= 32;
40  }
41}
42
43// return a[] >= mod
44static int geM(const RSAPublicKey* key,
45               const uint32_t* a) {
46  int i;
47  for (i = key->len; i;) {
48    --i;
49    if (a[i] < key->n[i]) return 0;
50    if (a[i] > key->n[i]) return 1;
51  }
52  return 1;  // equal
53}
54
55// montgomery c[] += a * b[] / R % mod
56static void montMulAdd(const RSAPublicKey* key,
57                       uint32_t* c,
58                       const uint32_t a,
59                       const uint32_t* b) {
60  uint64_t A = (uint64_t)a * b[0] + c[0];
61  uint32_t d0 = (uint32_t)A * key->n0inv;
62  uint64_t B = (uint64_t)d0 * key->n[0] + (uint32_t)A;
63  int i;
64
65  for (i = 1; i < key->len; ++i) {
66    A = (A >> 32) + (uint64_t)a * b[i] + c[i];
67    B = (B >> 32) + (uint64_t)d0 * key->n[i] + (uint32_t)A;
68    c[i - 1] = (uint32_t)B;
69  }
70
71  A = (A >> 32) + (B >> 32);
72
73  c[i - 1] = (uint32_t)A;
74
75  if (A >> 32) {
76    subM(key, c);
77  }
78}
79
80// montgomery c[] = a[] * b[] / R % mod
81static void montMul(const RSAPublicKey* key,
82                    uint32_t* c,
83                    const uint32_t* a,
84                    const uint32_t* b) {
85  int i;
86  for (i = 0; i < key->len; ++i) {
87    c[i] = 0;
88  }
89  for (i = 0; i < key->len; ++i) {
90    montMulAdd(key, c, a[i], b);
91  }
92}
93
94// In-place public exponentiation.
95// Input and output big-endian byte array in inout.
96static void modpowF4(const RSAPublicKey* key,
97                     uint8_t* inout) {
98  uint32_t a[RSANUMWORDS];
99  uint32_t aR[RSANUMWORDS];
100  uint32_t aaR[RSANUMWORDS];
101  uint32_t* aaa = aaR;  // Re-use location.
102  int i;
103
104  // Convert from big endian byte array to little endian word array.
105  for (i = 0; i < key->len; ++i) {
106    uint32_t tmp =
107      (inout[((key->len - 1 - i) * 4) + 0] << 24) |
108      (inout[((key->len - 1 - i) * 4) + 1] << 16) |
109      (inout[((key->len - 1 - i) * 4) + 2] << 8) |
110      (inout[((key->len - 1 - i) * 4) + 3] << 0);
111    a[i] = tmp;
112  }
113
114  montMul(key, aR, a, key->rr);  // aR = a * RR / R mod M
115  for (i = 0; i < 16; i += 2) {
116    montMul(key, aaR, aR, aR);  // aaR = aR * aR / R mod M
117    montMul(key, aR, aaR, aaR);  // aR = aaR * aaR / R mod M
118  }
119  montMul(key, aaa, aR, a);  // aaa = aR * a / R mod M
120
121  // Make sure aaa < mod; aaa is at most 1x mod too large.
122  if (geM(key, aaa)) {
123    subM(key, aaa);
124  }
125
126  // Convert to bigendian byte array
127  for (i = key->len - 1; i >= 0; --i) {
128    uint32_t tmp = aaa[i];
129    *inout++ = tmp >> 24;
130    *inout++ = tmp >> 16;
131    *inout++ = tmp >> 8;
132    *inout++ = tmp >> 0;
133  }
134}
135
136// Expected PKCS1.5 signature padding bytes, for a keytool RSA signature.
137// Has the 0-length optional parameter encoded in the ASN1 (as opposed to the
138// other flavor which omits the optional parameter entirely). This code does not
139// accept signatures without the optional parameter.
140/*
141static const uint8_t padding[RSANUMBYTES] = {
1420x00,0x01,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0x00,0x30,0x21,0x30,0x09,0x06,0x05,0x2b,0x0e,0x03,0x02,0x1a,0x05,0x00,0x04,0x14,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
143};
144*/
145
146// SHA-1 of PKCS1.5 signature padding for 2048 bit, as above.
147// At the location of the bytes of the hash all 00 are hashed.
148static const uint8_t kExpectedPadShaRsa2048[SHA_DIGEST_SIZE] = {
149  0xdc, 0xbd, 0xbe, 0x42, 0xd5, 0xf5, 0xa7, 0x2e, 0x6e, 0xfc,
150  0xf5, 0x5d, 0xaf, 0x9d, 0xea, 0x68, 0x7c, 0xfb, 0xf1, 0x67
151};
152
153// Verify a 2048 bit RSA e=65537 PKCS1.5 signature against an expected
154// SHA-1 hash.  Returns 0 on failure, 1 on success.
155int RSA_e_f4_verify(const RSAPublicKey* key,
156                    const uint8_t* signature,
157                    const int len,
158                    const uint8_t* sha) {
159  uint8_t buf[RSANUMBYTES];
160  int i;
161
162  if (key->len != RSANUMWORDS) {
163    return 0;  // Wrong key passed in.
164  }
165
166  if (len != sizeof(buf)) {
167    return 0;  // Wrong input length.
168  }
169
170  if (key->exponent != 65537) {
171      return 0;  // Wrong exponent.
172  }
173
174  for (i = 0; i < len; ++i) {  // Copy input to local workspace.
175    buf[i] = signature[i];
176  }
177
178  modpowF4(key, buf);  // In-place exponentiation.
179
180  // Xor sha portion, so it all becomes 00 iff equal.
181  for (i = len - SHA_DIGEST_SIZE; i < len; ++i) {
182    buf[i] ^= *sha++;
183  }
184
185  // Hash resulting buf, in-place.
186  SHA(buf, len, buf);
187
188  // Compare against expected hash value.
189  for (i = 0; i < SHA_DIGEST_SIZE; ++i) {
190    if (buf[i] != kExpectedPadShaRsa2048[i]) {
191      return 0;
192    }
193  }
194
195  return 1;  // All checked out OK.
196}
197