1/*-
2 * Copyright (c) 1991, 1993
3 *      Dave Safford.  All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 *    notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 *    notice, this list of conditions and the following disclaimer in the
12 *    documentation and/or other materials provided with the distribution.
13 * 3. Neither the name of the University nor the names of its contributors
14 *    may be used to endorse or promote products derived from this software
15 *    without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27 * SUCH DAMAGE.
28 *
29 */
30
31/* public key routines */
32/* functions:
33	genkeys(char *public, char *secret)
34	common_key(char *secret, char *public, desData *deskey)
35        pk_encode(char *in, *out, DesData *deskey);
36        pk_decode(char *in, *out, DesData *deskey);
37      where
38	char public[HEXKEYBYTES + 1];
39	char secret[HEXKEYBYTES + 1];
40 */
41
42#include <sys/time.h>
43#include <openssl/des.h>
44#include <fcntl.h>
45#include <stdio.h>
46#include <stdlib.h>
47#include <string.h>
48
49#include "mp.h"
50#include "pk.h"
51
52static void adjust(char keyout[HEXKEYBYTES+1], char *keyin);
53
54/*
55 * Choose top 128 bits of the common key to use as our idea key.
56 */
57static void
58extractideakey(MINT *ck, IdeaData *ideakey)
59{
60        MINT *a;
61        MINT *z;
62        short r;
63        int i;
64        short base = (1 << 8);
65        char *k;
66
67        z = mp_itom(0);
68        a = mp_itom(0);
69        mp_madd(ck, z, a);
70        for (i = 0; i < ((KEYSIZE - 128) / 8); i++) {
71                mp_sdiv(a, base, a, &r);
72        }
73        k = (char *)ideakey;
74        for (i = 0; i < 16; i++) {
75                mp_sdiv(a, base, a, &r);
76                *k++ = r;
77        }
78	mp_mfree(z);
79        mp_mfree(a);
80}
81
82/*
83 * Choose middle 64 bits of the common key to use as our des key, possibly
84 * overwriting the lower order bits by setting parity.
85 */
86static void
87extractdeskey(MINT *ck, DesData *deskey)
88{
89        MINT *a;
90        MINT *z;
91        short r;
92        int i;
93        short base = (1 << 8);
94        char *k;
95
96        z = mp_itom(0);
97        a = mp_itom(0);
98        mp_madd(ck, z, a);
99        for (i = 0; i < ((KEYSIZE - 64) / 2) / 8; i++) {
100                mp_sdiv(a, base, a, &r);
101        }
102        k = (char *)deskey;
103        for (i = 0; i < 8; i++) {
104                mp_sdiv(a, base, a, &r);
105                *k++ = r;
106        }
107	mp_mfree(z);
108        mp_mfree(a);
109}
110
111/*
112 * get common key from my secret key and his public key
113 */
114void
115common_key(char *xsecret, char *xpublic, IdeaData *ideakey, DesData *deskey)
116{
117        MINT *public;
118        MINT *secret;
119        MINT *common;
120	MINT *modulus = mp_xtom(HEXMODULUS);
121
122        public = mp_xtom(xpublic);
123        secret = mp_xtom(xsecret);
124        common = mp_itom(0);
125        mp_pow(public, secret, modulus, common);
126        extractdeskey(common, deskey);
127        extractideakey(common, ideakey);
128	DES_set_odd_parity(deskey);
129        mp_mfree(common);
130        mp_mfree(secret);
131        mp_mfree(public);
132	mp_mfree(modulus);
133}
134
135/*
136 * Generate a seed
137 */
138static void
139getseed(char *seed, int seedsize)
140{
141	arc4random_buf(seed, seedsize);
142}
143
144/*
145 * Generate a random public/secret key pair
146 */
147void
148genkeys(char *public, char *secret)
149{
150        size_t i;
151
152#       define BASEBITS (8*sizeof(short) - 1)
153#       define BASE (1 << BASEBITS)
154
155        MINT *pk = mp_itom(0);
156        MINT *sk = mp_itom(0);
157        MINT *tmp;
158        MINT *base = mp_itom((short)BASE);
159        MINT *root = mp_itom(PROOT);
160        MINT *modulus = mp_xtom(HEXMODULUS);
161        short r;
162        unsigned short seed[KEYSIZE/BASEBITS + 1];
163        char *xkey;
164
165        getseed((char *)seed, sizeof(seed));
166        for (i = 0; i < KEYSIZE/BASEBITS + 1; i++) {
167                r = seed[i] % BASE;
168                tmp = mp_itom(r);
169                mp_mult(sk, base, sk);
170                mp_madd(sk, tmp, sk);
171                mp_mfree(tmp);
172        }
173        tmp = mp_itom(0);
174        mp_mdiv(sk, modulus, tmp, sk);
175        mp_mfree(tmp);
176        mp_pow(root, sk, modulus, pk);
177        xkey = mp_mtox(sk);
178        adjust(secret, xkey);
179        xkey = mp_mtox(pk);
180        adjust(public, xkey);
181        mp_mfree(sk);
182        mp_mfree(base);
183        mp_mfree(pk);
184        mp_mfree(root);
185        mp_mfree(modulus);
186}
187
188/*
189 * Adjust the input key so that it is 0-filled on the left
190 */
191static void
192adjust(char keyout[HEXKEYBYTES+1], char *keyin)
193{
194        char *p;
195        char *s;
196
197        for (p = keyin; *p; p++)
198                ;
199        for (s = keyout + HEXKEYBYTES; p >= keyin; p--, s--) {
200                *s = *p;
201        }
202        while (s >= keyout) {
203                *s-- = '0';
204        }
205}
206
207static char hextab[17] = "0123456789ABCDEF";
208
209/* given a DES key, cbc encrypt and translate input to terminated hex */
210void
211pk_encode(char *in, char *out, DesData *key)
212{
213	char buf[256];
214	DesData i;
215	DES_key_schedule k;
216	int l,op,deslen;
217
218	memset(&i,0,sizeof(i));
219	memset(buf,0,sizeof(buf));
220	deslen = ((strlen(in) + 7)/8)*8;
221	DES_key_sched(key, &k);
222	DES_cbc_encrypt(in, buf, deslen, &k, &i, DES_ENCRYPT);
223	for (l=0,op=0;l<deslen;l++) {
224		out[op++] = hextab[(buf[l] & 0xf0) >> 4];
225		out[op++] = hextab[(buf[l] & 0x0f)];
226	}
227	out[op] = '\0';
228}
229
230/* given a DES key, translate input from hex and decrypt */
231void
232pk_decode(char *in, char *out, DesData *key)
233{
234	char buf[256];
235	DesData i;
236	DES_key_schedule k;
237	int n1,n2,op;
238	size_t l;
239
240	memset(&i,0,sizeof(i));
241	memset(buf,0,sizeof(buf));
242	for (l=0,op=0;l<strlen(in)/2;l++,op+=2) {
243		if (in[op] > '9')
244			n1 = in[op] - 'A' + 10;
245		else
246			n1 = in[op] - '0';
247		if (in[op+1] > '9')
248			n2 = in[op+1] - 'A' + 10;
249		else
250			n2 = in[op+1] - '0';
251		buf[l] = n1*16 +n2;
252	}
253	DES_key_sched(key, &k);
254	DES_cbc_encrypt(buf, out, strlen(in) / 2, &k, &i, DES_DECRYPT);
255	out[strlen(in)/2] = '\0';
256}
257