source: core/c/jbigi/jbigi/src/jbigi.c @ 0848e34

Last change on this file since 0848e34 was 0848e34, checked in by dev <dev@…>, 5 years ago

Replaced 0 with NULL to fix miscompilation on windows.

  • Property mode set to 100644
File size: 12.9 KB
Line 
1#include <stdio.h>
2#include <gmp.h>
3#include "jbigi.h"
4
5/******** prototypes */
6
7void convert_j2mp(JNIEnv* env, jbyteArray jvalue, mpz_t* mvalue);
8void convert_mp2j(JNIEnv* env, mpz_t mvalue, jbyteArray* jvalue);
9
10/*
11 * Versions:
12 *
13 * 1: Original version, with nativeModPow() and nativeDoubleValue()
14 *
15 * 2: (I2P 0.8.7)
16 *    Removed nativeDoubleValue()
17 *
18 * 3: (I2P 0.9.18)
19 *    Added:
20 *      nativeJbigiVersion()
21 *      nativeGMPMajorVersion()
22 *      nativeGMPMinorVersion()
23 *      nativeGMPPatchVersion()
24 *      nativeModInverse()
25 *      nativeModPowCT()
26 *    Support negative base value in modPow()
27 *    Throw ArithmeticException for bad arguments in modPow()
28 *
29 */
30#define JBIGI_VERSION 3
31
32/*****************************************
33 *****Native method implementations*******
34 *****************************************/
35
36/* since version 3 */
37JNIEXPORT jint JNICALL Java_net_i2p_util_NativeBigInteger_nativeJbigiVersion
38        (JNIEnv* env, jclass cls) {
39    return (jint) JBIGI_VERSION;
40}
41
42/* since version 3 */
43JNIEXPORT jint JNICALL Java_net_i2p_util_NativeBigInteger_nativeGMPMajorVersion
44        (JNIEnv* env, jclass cls) {
45    return (jint) __GNU_MP_VERSION;
46}
47
48/* since version 3 */
49JNIEXPORT jint JNICALL Java_net_i2p_util_NativeBigInteger_nativeGMPMinorVersion
50        (JNIEnv* env, jclass cls) {
51    return (jint) __GNU_MP_VERSION_MINOR;
52}
53
54/* since version 3 */
55JNIEXPORT jint JNICALL Java_net_i2p_util_NativeBigInteger_nativeGMPPatchVersion
56        (JNIEnv* env, jclass cls) {
57    return (jint) __GNU_MP_VERSION_PATCHLEVEL;
58}
59
60/******** nativeModPow() */
61/*
62 * Class:     net_i2p_util_NativeBigInteger
63 * Method:    nativeModPow
64 * Signature: ([B[B[B)[B
65 *
66 * From the javadoc:
67 *
68 * calculate (base ^ exponent) % modulus.
69 * @param jbase big endian twos complement representation of the base
70 *             Negative values allowed as of version 3
71 * @param jexp big endian twos complement representation of the exponent
72 *             Must be greater than or equal to zero.
73 *             As of version 3, throws java.lang.ArithmeticException if < 0.
74 * @param jmod big endian twos complement representation of the modulus
75 *             Must be greater than zero.
76 *             As of version 3, throws java.lang.ArithmeticException if <= 0.
77 *             Prior to version 3, crashed the JVM if <= 0.
78 * @return big endian twos complement representation of (base ^ exponent) % modulus
79 * @throws java.lang.ArithmeticException if jmod is <= 0
80 */
81
82JNIEXPORT jbyteArray JNICALL Java_net_i2p_util_NativeBigInteger_nativeModPow
83        (JNIEnv* env, jclass cls, jbyteArray jbase, jbyteArray jexp, jbyteArray jmod) {
84        /* 1) Convert base, exponent, modulus into the format libgmp understands
85         * 2) Call libgmp's modPow.
86         * 3) Convert libgmp's result into a big endian twos complement number.
87         */
88
89        mpz_t mbase;
90        mpz_t mexp;
91        mpz_t mmod;
92        jbyteArray jresult;
93
94        convert_j2mp(env, jmod,  &mmod);
95        if (mpz_sgn(mmod) <= 0) {
96            mpz_clear(mmod);
97            jclass exc = (*env)->FindClass(env, "java/lang/ArithmeticException");
98            (*env)->ThrowNew(env, exc, "Modulus must be positive");
99            return 0;
100        }
101
102        // disallow negative exponents to avoid divide by zero exception if no inverse exists
103        convert_j2mp(env, jexp,  &mexp);
104        if (mpz_sgn(mexp) < 0) {
105            mpz_clears(mmod, mexp, NULL);
106            jclass exc = (*env)->FindClass(env, "java/lang/ArithmeticException");
107            (*env)->ThrowNew(env, exc, "Exponent cannot be negative");
108            return 0;
109        }
110
111        convert_j2mp(env, jbase, &mbase);
112 
113        /* Perform the actual powmod. We use mmod for the result because it is
114         * always at least as big as the result.
115         */
116        mpz_powm(mmod, mbase, mexp, mmod);
117
118        convert_mp2j(env, mmod, &jresult);
119
120        mpz_clears(mbase, mexp, mmod, NULL);
121
122        return jresult;
123}
124
125/******** nativeModPowCT() */
126/*
127 * Class:     net_i2p_util_NativeBigInteger
128 * Method:    nativeModPowCT
129 * Signature: ([B[B[B)[B
130 *
131 * Constant time version of nativeModPow()
132 *
133 * From the javadoc:
134 *
135 * calculate (base ^ exponent) % modulus.
136 * @param jbase big endian twos complement representation of the base
137 *             Negative values allowed.
138 * @param jexp big endian twos complement representation of the exponent
139 *             Must be positive.
140 * @param jmod big endian twos complement representation of the modulus
141 *             Must be positive and odd.
142 * @return big endian twos complement representation of (base ^ exponent) % modulus
143 * @throws java.lang.ArithmeticException if jmod or jexp is <= 0, or jmod is even.
144 * @since version 3
145 */
146
147JNIEXPORT jbyteArray JNICALL Java_net_i2p_util_NativeBigInteger_nativeModPowCT
148        (JNIEnv* env, jclass cls, jbyteArray jbase, jbyteArray jexp, jbyteArray jmod) {
149
150        mpz_t mbase;
151        mpz_t mexp;
152        mpz_t mmod;
153        jbyteArray jresult;
154
155        convert_j2mp(env, jmod,  &mmod);
156        if (mpz_sgn(mmod) <= 0) {
157            mpz_clear(mmod);
158            jclass exc = (*env)->FindClass(env, "java/lang/ArithmeticException");
159            (*env)->ThrowNew(env, exc, "Modulus must be positive");
160            return 0;
161        }
162        // disallow even modulus as specified in the GMP docs
163        if (mpz_odd_p(mmod) == 0) {
164            mpz_clear(mmod);
165            jclass exc = (*env)->FindClass(env, "java/lang/ArithmeticException");
166            (*env)->ThrowNew(env, exc, "Modulus must be odd");
167            return 0;
168        }
169
170        // disallow negative or zero exponents as specified in the GMP docs
171        convert_j2mp(env, jexp,  &mexp);
172        if (mpz_sgn(mexp) <= 0) {
173            mpz_clears(mmod, mexp, NULL);
174            jclass exc = (*env)->FindClass(env, "java/lang/ArithmeticException");
175            (*env)->ThrowNew(env, exc, "Exponent must be positive");
176            return 0;
177        }
178
179        convert_j2mp(env, jbase, &mbase);
180 
181        mpz_powm_sec(mmod, mbase, mexp, mmod);
182
183        convert_mp2j(env, mmod, &jresult);
184
185        mpz_clears(mbase, mexp, mmod, NULL);
186
187        return jresult;
188}
189
190/******** nativeModInverse() */
191/*
192 * Class:     net_i2p_util_NativeBigInteger
193 * Method:    nativeModInverse
194 * Signature: ([B[B)[B
195 *
196 * From the javadoc:
197 *
198 * calculate (base ^ -1) % modulus.
199 * @param jbase big endian twos complement representation of the base
200 *             Negative values allowed
201 * @param jmod big endian twos complement representation of the modulus
202 *             Zero or Negative values will throw a java.lang.ArithmeticException
203 * @return big endian twos complement representation of (base ^ exponent) % modulus
204 * @throws java.lang.ArithmeticException if jbase and jmod are not coprime or jmod is <= 0
205 * @since version 3
206 */
207
208JNIEXPORT jbyteArray JNICALL Java_net_i2p_util_NativeBigInteger_nativeModInverse
209        (JNIEnv* env, jclass cls, jbyteArray jbase, jbyteArray jmod) {
210
211        mpz_t mbase;
212        mpz_t mexp;
213        mpz_t mmod;
214        mpz_t mgcd;
215        jbyteArray jresult;
216
217        convert_j2mp(env, jmod,  &mmod);
218
219        if (mpz_sgn(mmod) <= 0) {
220            mpz_clear(mmod);
221            jclass exc = (*env)->FindClass(env, "java/lang/ArithmeticException");
222            (*env)->ThrowNew(env, exc, "Modulus must be positive");
223            return 0;
224        }
225
226        convert_j2mp(env, jbase, &mbase);
227        mpz_init_set_si(mexp, -1);
228 
229        /* We must protect the jvm by doing a gcd test first.
230         * If the arguments are not coprime, GMP will throw a divide by zero
231         * and crash the JVM.
232         * We could test in Java using BigInteger.gcd() but it is almost as slow
233         * as the Java modInverse() itself, thus defeating the point.
234         * Unfortunately, this almost doubles our time here too.
235         */
236        mpz_init(mgcd);
237        mpz_gcd(mgcd, mbase, mmod);
238        if (mpz_cmp_si(mgcd, 1) != 0) {
239            mpz_clears(mbase, mexp, mmod, mgcd, NULL);
240            jclass exc = (*env)->FindClass(env, "java/lang/ArithmeticException");
241            (*env)->ThrowNew(env, exc, "Not coprime in nativeModInverse()");
242            return 0;
243        }
244
245        /* Perform the actual powmod. We use mmod for the result because it is
246         * always at least as big as the result.
247         */
248        mpz_powm(mmod, mbase, mexp, mmod);
249
250        convert_mp2j(env, mmod, &jresult);
251
252        mpz_clears(mbase, mexp, mmod, mgcd, NULL);
253
254        return jresult;
255}
256
257/******** nativeNeg() */
258/* since version 3 */
259/*
260 * Class:     net_i2p_util_NativeBigInteger
261 * Method:    nativeNeg
262 * Signature: ([B)[B
263 *
264 * For testing of the conversion functions only!
265 *
266 * calculate n mod d
267 * @param n big endian twos complement representation
268 * @return big endian twos complement representation of -n
269 */
270
271/****
272JNIEXPORT jbyteArray JNICALL Java_net_i2p_util_NativeBigInteger_nativeNeg
273        (JNIEnv* env, jclass cls, jbyteArray jn) {
274
275        mpz_t mn;
276        jbyteArray jresult;
277
278        convert_j2mp(env, jn,  &mn);
279 
280        // result to mn
281        mpz_neg(mn, mn);
282
283        convert_mp2j(env, mn, &jresult);
284
285        mpz_clear(mn);
286
287        return jresult;
288}
289****/
290
291/******************************
292 *****Conversion methods*******
293 ******************************/
294
295/*Luckily we can use GMP's mpz_import() and mpz_export() functions to convert from/to
296 *BigInteger.toByteArray() representation.
297 */
298
299/******** convert_j2mp() */
300/*
301 * Initializes the GMP value with enough preallocated size, and converts the
302 * Java value into the GMP value. The value that mvalue points to should be
303 * uninitialized
304 *
305 * As of version 3, negative values are correctly converted.
306 */
307
308void convert_j2mp(JNIEnv* env, jbyteArray jvalue, mpz_t* mvalue)
309{
310        jsize size;
311        jbyte* jbuffer;
312        mpz_t mask;
313
314        size = (*env)->GetArrayLength(env, jvalue);
315        jbuffer = (*env)->GetByteArrayElements(env, jvalue, NULL);
316
317        mpz_init2(*mvalue, sizeof(jbyte) * 8 * size); //preallocate the size
318
319        /* void mpz_import(
320         *   mpz_t rop, size_t count, int order, int size, int endian,
321         *   size_t nails, const void *op);
322         *
323         * order = 1
324         *   order can be 1 for most significant word first or -1 for least
325         *   significant first.
326         * endian = 1
327         *   Within each word endian can be 1 for most significant byte first,
328         *   -1 for least significant first.
329         * nails = 0
330         *   The most significant nails bits of each word are skipped, this can
331         *   be 0 to use the full words.
332         */
333        mpz_import(*mvalue, size, 1, sizeof(jbyte), 1, 0, (void*)jbuffer);
334        if (jbuffer[0] < 0) {
335            // ones complement, making a negative number
336            mpz_com(*mvalue, *mvalue);
337            // construct the mask needed to get rid of the new high bit
338            mpz_init_set_ui(mask, 1);
339            mpz_mul_2exp(mask, mask, size * 8);
340            mpz_sub_ui(mask, mask, 1);
341            // mask off the high bits, making a postive number (the magnitude, off by one)
342            mpz_and(*mvalue, *mvalue, mask);
343            // release the mask
344            mpz_clear(mask);
345            // add one to get the correct magnitude
346            mpz_add_ui(*mvalue, *mvalue, 1);
347            // invert to a negative number
348            mpz_neg(*mvalue, *mvalue);
349        }
350        (*env)->ReleaseByteArrayElements(env, jvalue, jbuffer, JNI_ABORT);
351}
352
353/******** convert_mp2j() */
354/*
355 * Converts the GMP value into the Java value; Doesn't do anything else.
356 * Pads the resulting jbyte array with 0, so the twos complement value is always
357 * positive.
358 *
359 * As of version 3, negative values are correctly converted.
360 */
361
362void convert_mp2j(JNIEnv* env, mpz_t mvalue, jbyteArray* jvalue)
363{
364        // size_t not jsize to work with 64bit CPUs (do we need to update this
365        // elsewhere, and/or adjust memory alloc sizes?)
366        size_t size; 
367        jbyte* buffer;
368        jboolean copy;
369        int i;
370        int neg;
371
372        copy = JNI_FALSE;
373
374        neg = mpz_sgn(mvalue) < 0;
375        if (neg) {
376            // add 1...
377            // have to do this before we calculate the size!
378            mpz_add_ui(mvalue, mvalue, 1);
379        }
380
381        /* sizeinbase() + 7 => Ceil division */
382        size = (mpz_sizeinbase(mvalue, 2) + 7) / 8 + sizeof(jbyte);
383        *jvalue = (*env)->NewByteArray(env, size);
384
385        buffer = (*env)->GetByteArrayElements(env, *jvalue, &copy);
386        buffer[0] = 0x00;
387
388        if (!neg) {
389            mpz_export((void*)&buffer[1], NULL, 1, sizeof(jbyte), 1, 0, mvalue);
390        } else {
391            mpz_export((void*)&buffer[1], NULL, 1, sizeof(jbyte), 1, 0, mvalue);
392            // ... and invert the bits
393            // This could be done all in mpz, the reverse of the above
394            for (i = 0; i <= size; i++) {
395                buffer[i] = ~buffer[i];
396            }
397        }
398
399        /* mode has (supposedly) no effect if elems is not a copy of the
400         * elements in array
401         */
402        (*env)->ReleaseByteArrayElements(env, *jvalue, buffer, 0);
403        //mode has (supposedly) no effect if elems is not a copy of the elements in array
404}
Note: See TracBrowser for help on using the repository browser.