expspeed.c revision 296465 
1/* unused */
2
3/* crypto/bn/expspeed.c */
4/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
5 * All rights reserved.
6 *
7 * This package is an SSL implementation written
8 * by Eric Young (eay@cryptsoft.com).
9 * The implementation was written so as to conform with Netscapes SSL.
10 *
11 * This library is free for commercial and non-commercial use as long as
12 * the following conditions are aheared to.  The following conditions
13 * apply to all code found in this distribution, be it the RC4, RSA,
14 * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
15 * included with this distribution is covered by the same copyright terms
16 * except that the holder is Tim Hudson (tjh@cryptsoft.com).
17 *
18 * Copyright remains Eric Young's, and as such any Copyright notices in
19 * the code are not to be removed.
20 * If this package is used in a product, Eric Young should be given attribution
21 * as the author of the parts of the library used.
22 * This can be in the form of a textual message at program startup or
23 * in documentation (online or textual) provided with the package.
24 *
25 * Redistribution and use in source and binary forms, with or without
26 * modification, are permitted provided that the following conditions
27 * are met:
28 * 1. Redistributions of source code must retain the copyright
29 *    notice, this list of conditions and the following disclaimer.
30 * 2. Redistributions in binary form must reproduce the above copyright
31 *    notice, this list of conditions and the following disclaimer in the
32 *    documentation and/or other materials provided with the distribution.
33 * 3. All advertising materials mentioning features or use of this software
34 *    must display the following acknowledgement:
35 *    "This product includes cryptographic software written by
36 *     Eric Young (eay@cryptsoft.com)"
37 *    The word 'cryptographic' can be left out if the rouines from the library
38 *    being used are not cryptographic related :-).
39 * 4. If you include any Windows specific code (or a derivative thereof) from
40 *    the apps directory (application code) you must include an acknowledgement:
41 *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
42 *
43 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
44 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
45 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
46 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
47 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
48 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
49 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
50 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
51 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
52 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
53 * SUCH DAMAGE.
54 *
55 * The licence and distribution terms for any publically available version or
56 * derivative of this code cannot be changed.  i.e. this code cannot simply be
57 * copied and put under another distribution licence
58 * [including the GNU Public Licence.]
59 */
60
61/* most of this code has been pilfered from my libdes speed.c program */
62
63#define BASENUM 5000
64#define NUM_START 0
65
66/*
67 * determine timings for modexp, modmul, modsqr, gcd, Kronecker symbol,
68 * modular inverse, or modular square roots
69 */
70#define TEST_EXP
71#undef TEST_MUL
72#undef TEST_SQR
73#undef TEST_GCD
74#undef TEST_KRON
75#undef TEST_INV
76#undef TEST_SQRT
77#define P_MOD_64 9              /* least significant 6 bits for prime to be
78                                 * used for BN_sqrt timings */
79
80#if defined(TEST_EXP) + defined(TEST_MUL) + defined(TEST_SQR) + defined(TEST_GCD) + defined(TEST_KRON) + defined(TEST_INV) +defined(TEST_SQRT) != 1
81# error "choose one test"
82#endif
83
84#if defined(TEST_INV) || defined(TEST_SQRT)
85# define C_PRIME
86static void genprime_cb(int p, int n, void *arg);
87#endif
88
89#undef PROG
90#define PROG bnspeed_main
91
92#include <stdio.h>
93#include <stdlib.h>
94#include <signal.h>
95#include <string.h>
96#include <openssl/crypto.h>
97#include <openssl/err.h>
98#include <openssl/rand.h>
99
100#if !defined(OPENSSL_SYS_MSDOS) && (!defined(OPENSSL_SYS_VMS) || defined(__DECC)) && !defined(OPENSSL_SYS_MACOSX)
101# define TIMES
102#endif
103
104#ifndef _IRIX
105# include <time.h>
106#endif
107#ifdef TIMES
108# include <sys/types.h>
109# include <sys/times.h>
110#endif
111
112/*
113 * Depending on the VMS version, the tms structure is perhaps defined. The
114 * __TMS macro will show if it was.  If it wasn't defined, we should undefine
115 * TIMES, since that tells the rest of the program how things should be
116 * handled.  -- Richard Levitte
117 */
118#if defined(OPENSSL_SYS_VMS_DECC) && !defined(__TMS)
119# undef TIMES
120#endif
121
122#ifndef TIMES
123# include <sys/timeb.h>
124#endif
125
126#if defined(sun) || defined(__ultrix)
127# define _POSIX_SOURCE
128# include <limits.h>
129# include <sys/param.h>
130#endif
131
132#include <openssl/bn.h>
133#include <openssl/x509.h>
134
135/* The following if from times(3) man page.  It may need to be changed */
136#ifndef HZ
137# ifndef CLK_TCK
138#  ifndef _BSD_CLK_TCK_         /* FreeBSD hack */
139#   define HZ   100.0
140#  else                         /* _BSD_CLK_TCK_ */
141#   define HZ ((double)_BSD_CLK_TCK_)
142#  endif
143# else                          /* CLK_TCK */
144#  define HZ ((double)CLK_TCK)
145# endif
146#endif
147
148#undef BUFSIZE
149#define BUFSIZE ((long)1024*8)
150int run = 0;
151
152static double Time_F(int s);
153#define START   0
154#define STOP    1
155
156static double Time_F(int s)
157{
158    double ret;
159#ifdef TIMES
160    static struct tms tstart, tend;
161
162    if (s == START) {
163        times(&tstart);
164        return (0);
165    } else {
166        times(&tend);
167        ret = ((double)(tend.tms_utime - tstart.tms_utime)) / HZ;
168        return ((ret < 1e-3) ? 1e-3 : ret);
169    }
170#else                           /* !times() */
171    static struct timeb tstart, tend;
172    long i;
173
174    if (s == START) {
175        ftime(&tstart);
176        return (0);
177    } else {
178        ftime(&tend);
179        i = (long)tend.millitm - (long)tstart.millitm;
180        ret = ((double)(tend.time - tstart.time)) + ((double)i) / 1000.0;
181        return ((ret < 0.001) ? 0.001 : ret);
182    }
183#endif
184}
185
186#define NUM_SIZES       7
187#if NUM_START > NUM_SIZES
188# error "NUM_START > NUM_SIZES"
189#endif
190static int sizes[NUM_SIZES] = { 128, 256, 512, 1024, 2048, 4096, 8192 };
191
192static int mul_c[NUM_SIZES] =
193    { 8 * 8 * 8 * 8 * 8 * 8, 8 * 8 * 8 * 8 * 8, 8 * 8 * 8 * 8, 8 * 8 * 8,
194    8 * 8, 8, 1
195};
196
197/*
198 * static int sizes[NUM_SIZES]={59,179,299,419,539};
199 */
200
201#define RAND_SEED(string) { const char str[] = string; RAND_seed(string, sizeof str); }
202
203void do_mul_exp(BIGNUM *r, BIGNUM *a, BIGNUM *b, BIGNUM *c, BN_CTX *ctx);
204
205int main(int argc, char **argv)
206{
207    BN_CTX *ctx;
208    BIGNUM *a, *b, *c, *r;
209
210#if 1
211    if (!CRYPTO_set_mem_debug_functions(0, 0, 0, 0, 0))
212        abort();
213#endif
214
215    ctx = BN_CTX_new();
216    a = BN_new();
217    b = BN_new();
218    c = BN_new();
219    r = BN_new();
220
221    while (!RAND_status())
222        /* not enough bits */
223        RAND_SEED("I demand a manual recount!");
224
225    do_mul_exp(r, a, b, c, ctx);
226    return 0;
227}
228
229void do_mul_exp(BIGNUM *r, BIGNUM *a, BIGNUM *b, BIGNUM *c, BN_CTX *ctx)
230{
231    int i, k;
232    double tm;
233    long num;
234
235    num = BASENUM;
236    for (i = NUM_START; i < NUM_SIZES; i++) {
237#ifdef C_PRIME
238# ifdef TEST_SQRT
239        if (!BN_set_word(a, 64))
240            goto err;
241        if (!BN_set_word(b, P_MOD_64))
242            goto err;
243#  define ADD a
244#  define REM b
245# else
246#  define ADD NULL
247#  define REM NULL
248# endif
249        if (!BN_generate_prime(c, sizes[i], 0, ADD, REM, genprime_cb, NULL))
250            goto err;
251        putc('\n', stderr);
252        fflush(stderr);
253#endif
254
255        for (k = 0; k < num; k++) {
256            if (k % 50 == 0) {  /* Average over num/50 different choices of
257                                 * random numbers. */
258                if (!BN_pseudo_rand(a, sizes[i], 1, 0))
259                    goto err;
260
261                if (!BN_pseudo_rand(b, sizes[i], 1, 0))
262                    goto err;
263
264#ifndef C_PRIME
265                if (!BN_pseudo_rand(c, sizes[i], 1, 1))
266                    goto err;
267#endif
268
269#ifdef TEST_SQRT
270                if (!BN_mod_sqr(a, a, c, ctx))
271                    goto err;
272                if (!BN_mod_sqr(b, b, c, ctx))
273                    goto err;
274#else
275                if (!BN_nnmod(a, a, c, ctx))
276                    goto err;
277                if (!BN_nnmod(b, b, c, ctx))
278                    goto err;
279#endif
280
281                if (k == 0)
282                    Time_F(START);
283            }
284#if defined(TEST_EXP)
285            if (!BN_mod_exp(r, a, b, c, ctx))
286                goto err;
287#elif defined(TEST_MUL)
288            {
289                int i = 0;
290                for (i = 0; i < 50; i++)
291                    if (!BN_mod_mul(r, a, b, c, ctx))
292                        goto err;
293            }
294#elif defined(TEST_SQR)
295            {
296                int i = 0;
297                for (i = 0; i < 50; i++) {
298                    if (!BN_mod_sqr(r, a, c, ctx))
299                        goto err;
300                    if (!BN_mod_sqr(r, b, c, ctx))
301                        goto err;
302                }
303            }
304#elif defined(TEST_GCD)
305            if (!BN_gcd(r, a, b, ctx))
306                goto err;
307            if (!BN_gcd(r, b, c, ctx))
308                goto err;
309            if (!BN_gcd(r, c, a, ctx))
310                goto err;
311#elif defined(TEST_KRON)
312            if (-2 == BN_kronecker(a, b, ctx))
313                goto err;
314            if (-2 == BN_kronecker(b, c, ctx))
315                goto err;
316            if (-2 == BN_kronecker(c, a, ctx))
317                goto err;
318#elif defined(TEST_INV)
319            if (!BN_mod_inverse(r, a, c, ctx))
320                goto err;
321            if (!BN_mod_inverse(r, b, c, ctx))
322                goto err;
323#else                           /* TEST_SQRT */
324            if (!BN_mod_sqrt(r, a, c, ctx))
325                goto err;
326            if (!BN_mod_sqrt(r, b, c, ctx))
327                goto err;
328#endif
329        }
330        tm = Time_F(STOP);
331        printf(
332#if defined(TEST_EXP)
333                  "modexp %4d ^ %4d %% %4d"
334#elif defined(TEST_MUL)
335                  "50*modmul %4d %4d %4d"
336#elif defined(TEST_SQR)
337                  "100*modsqr %4d %4d %4d"
338#elif defined(TEST_GCD)
339                  "3*gcd %4d %4d %4d"
340#elif defined(TEST_KRON)
341                  "3*kronecker %4d %4d %4d"
342#elif defined(TEST_INV)
343                  "2*inv %4d %4d mod %4d"
344#else                           /* TEST_SQRT */
345                  "2*sqrt [prime == %d (mod 64)] %4d %4d mod %4d"
346#endif
347                  " -> %8.6fms %5.1f (%ld)\n",
348#ifdef TEST_SQRT
349                  P_MOD_64,
350#endif
351                  sizes[i], sizes[i], sizes[i], tm * 1000.0 / num,
352                  tm * mul_c[i] / num, num);
353        num /= 7;
354        if (num <= 0)
355            num = 1;
356    }
357    return;
358
359 err:
360    ERR_print_errors_fp(stderr);
361}
362
363#ifdef C_PRIME
364static void genprime_cb(int p, int n, void *arg)
365{
366    char c = '*';
367
368    if (p == 0)
369        c = '.';
370    if (p == 1)
371        c = '+';
372    if (p == 2)
373        c = '*';
374    if (p == 3)
375        c = '\n';
376    putc(c, stderr);
377    fflush(stderr);
378    (void)n;
379    (void)arg;
380}
381#endif
382