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