1 /*
2 Name: rsamath.c
3 Purpose: Implements part of PKCS#1, v. 2.1, June 14, 2002 (RSA Labs)
4 Author: M. J. Fromberger
5
6 Copyright (C) 2002-2008 Michael J. Fromberger, All Rights Reserved.
7
8 Permission is hereby granted, free of charge, to any person obtaining a copy
9 of this software and associated documentation files (the "Software"), to deal
10 in the Software without restriction, including without limitation the rights
11 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
12 copies of the Software, and to permit persons to whom the Software is
13 furnished to do so, subject to the following conditions:
14
15 The above copyright notice and this permission notice shall be included in
16 all copies or substantial portions of the Software.
17
18 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
19 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
20 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
21 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
22 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
23 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
24 SOFTWARE.
25 */
26
27 #include "rsamath.h"
28
29 #include <limits.h>
30 #include <string.h>
31
32 static mp_result s_rsa_transform(mp_int msg, mp_int exp, mp_int mod,
33 mp_int out);
34
35 /* Convert integer to octet string, per PKCS#1 v.2.1 */
rsa_i2osp(mp_int z,unsigned char * out,int len)36 mp_result rsa_i2osp(mp_int z, unsigned char *out, int len) {
37 int excess_len = mp_int_binary_len(z);
38
39 if (excess_len < len) return MP_RANGE;
40
41 memset(out, 0, len);
42
43 excess_len -= len;
44 mp_int_to_binary(z, out + excess_len, len);
45
46 return MP_OK;
47 }
48
49 /* Convert octet string to integer, per PKCS#1 v.2.1 */
rsa_os2ip(mp_int z,unsigned char * in,int len)50 mp_result rsa_os2ip(mp_int z, unsigned char *in, int len) {
51 return mp_int_read_binary(z, in, len);
52 }
53
54 /* Primitive RSA encryption operation */
rsa_rsaep(mp_int msg,mp_int exp,mp_int mod,mp_int cipher)55 mp_result rsa_rsaep(mp_int msg, mp_int exp, mp_int mod, mp_int cipher) {
56 return s_rsa_transform(msg, exp, mod, cipher);
57 }
58
59 /* Primitive RSA decryption operation */
rsa_rsadp(mp_int cipher,mp_int exp,mp_int mod,mp_int msg)60 mp_result rsa_rsadp(mp_int cipher, mp_int exp, mp_int mod, mp_int msg) {
61 return s_rsa_transform(cipher, exp, mod, msg);
62 }
63
64 /* Primitive RSA signing operation */
rsa_rsasp(mp_int msg,mp_int exp,mp_int mod,mp_int signature)65 mp_result rsa_rsasp(mp_int msg, mp_int exp, mp_int mod, mp_int signature) {
66 return s_rsa_transform(msg, exp, mod, signature);
67 }
68
69 /* Primitive RSA verification operation */
rsa_rsavp(mp_int signature,mp_int exp,mp_int mod,mp_int msg)70 mp_result rsa_rsavp(mp_int signature, mp_int exp, mp_int mod, mp_int msg) {
71 return s_rsa_transform(signature, exp, mod, msg);
72 }
73
74 /* Compute the maximum length in bytes a message can have using PKCS#1
75 v.1.5 encoding with the given modulus */
rsa_max_message_len(mp_int mod)76 int rsa_max_message_len(mp_int mod) {
77 int num_bits = mp_int_count_bits(mod);
78 int num_bytes = num_bits / CHAR_BIT;
79
80 if (num_bytes < 11) {
81 return 0; /* at least eleven bytes are required for padding */
82 } else {
83 return num_bytes - 11;
84 }
85 }
86
rsa_pkcs1v15_encode(unsigned char * buf,int msg_len,int buf_len,int tag,random_f filler)87 mp_result rsa_pkcs1v15_encode(unsigned char *buf, int msg_len, int buf_len,
88 int tag, random_f filler) {
89 /* Make sure there is enough space for the encoded output */
90 if (msg_len > (buf_len - 11)) return MP_RANGE;
91
92 int msg_start = buf_len - msg_len;
93 int pad_len = msg_start - 3;
94
95 /* Move message to top of buffer -- these might overlap, so we rely
96 on the semantics of memmove() here */
97 memmove(buf + msg_start, buf, msg_len);
98
99 /* Set initial bytes as required by the specification */
100 buf[0] = 0x00;
101 buf[1] = (unsigned char)tag;
102
103 /* Fill with random padding. We'll just assume the filler function
104 does the right thing and only writes the requested number of
105 nonzero bytes */
106 (filler)(buf + 2, pad_len);
107
108 /* Write separator between pad and message body */
109 buf[msg_start - 1] = 0x00;
110
111 return MP_OK;
112 }
113
rsa_pkcs1v15_decode(unsigned char * buf,int buf_len,int tag,int * msg_len)114 mp_result rsa_pkcs1v15_decode(unsigned char *buf, int buf_len, int tag,
115 int *msg_len) {
116 /* Make sure the buffer is syntactically valid */
117 if (buf_len < 11 || buf[0] != 0x00 || buf[1] != (unsigned char)tag)
118 return MP_UNDEF;
119
120 /* Figure out how many bytes of random padding there are */
121 int i = 2;
122 int pad_len = 0;
123 while (buf[i++] != '\0') ++pad_len;
124
125 int data_start = i;
126 int data_len = buf_len - data_start;
127
128 /* Shift the message to the front of the buffer */
129 memmove(buf, buf + data_start, data_len);
130
131 /* Zero out the rest of the buffer */
132 memset(buf + data_len, 0, pad_len + 3);
133
134 *msg_len = data_len;
135
136 return MP_OK;
137 }
138
s_rsa_transform(mp_int msg,mp_int exp,mp_int mod,mp_int out)139 static mp_result s_rsa_transform(mp_int msg, mp_int exp, mp_int mod,
140 mp_int out) {
141 if (mp_int_compare_zero(msg) < 0 || mp_int_compare(msg, mod) >= 0) {
142 return MP_RANGE;
143 }
144
145 return mp_int_exptmod(msg, exp, mod, out);
146 }
147
148 /* Here there be dragons */
149