--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/jdk/src/share/native/sun/security/ec/ecp_256.c Tue Aug 11 16:52:26 2009 +0100
@@ -0,0 +1,451 @@
+/* *********************************************************************
+ *
+ * Sun elects to have this file available under and governed by the
+ * Mozilla Public License Version 1.1 ("MPL") (see
+ * http://www.mozilla.org/MPL/ for full license text). For the avoidance
+ * of doubt and subject to the following, Sun also elects to allow
+ * licensees to use this file under the MPL, the GNU General Public
+ * License version 2 only or the Lesser General Public License version
+ * 2.1 only. Any references to the "GNU General Public License version 2
+ * or later" or "GPL" in the following shall be construed to mean the
+ * GNU General Public License version 2 only. Any references to the "GNU
+ * Lesser General Public License version 2.1 or later" or "LGPL" in the
+ * following shall be construed to mean the GNU Lesser General Public
+ * License version 2.1 only. However, the following notice accompanied
+ * the original version of this file:
+ *
+ * Version: MPL 1.1/GPL 2.0/LGPL 2.1
+ *
+ * The contents of this file are subject to the Mozilla Public License Version
+ * 1.1 (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * Software distributed under the License is distributed on an "AS IS" basis,
+ * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
+ * for the specific language governing rights and limitations under the
+ * License.
+ *
+ * The Original Code is the elliptic curve math library for prime field curves.
+ *
+ * The Initial Developer of the Original Code is
+ * Sun Microsystems, Inc.
+ * Portions created by the Initial Developer are Copyright (C) 2003
+ * the Initial Developer. All Rights Reserved.
+ *
+ * Contributor(s):
+ * Douglas Stebila <douglas@stebila.ca>
+ *
+ * Alternatively, the contents of this file may be used under the terms of
+ * either the GNU General Public License Version 2 or later (the "GPL"), or
+ * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
+ * in which case the provisions of the GPL or the LGPL are applicable instead
+ * of those above. If you wish to allow use of your version of this file only
+ * under the terms of either the GPL or the LGPL, and not to allow others to
+ * use your version of this file under the terms of the MPL, indicate your
+ * decision by deleting the provisions above and replace them with the notice
+ * and other provisions required by the GPL or the LGPL. If you do not delete
+ * the provisions above, a recipient may use your version of this file under
+ * the terms of any one of the MPL, the GPL or the LGPL.
+ *
+ *********************************************************************** */
+/*
+ * Copyright 2007 Sun Microsystems, Inc. All rights reserved.
+ * Use is subject to license terms.
+ */
+
+#pragma ident "%Z%%M% %I% %E% SMI"
+
+#include "ecp.h"
+#include "mpi.h"
+#include "mplogic.h"
+#include "mpi-priv.h"
+#ifndef _KERNEL
+#include <stdlib.h>
+#endif
+
+/* Fast modular reduction for p256 = 2^256 - 2^224 + 2^192+ 2^96 - 1. a can be r.
+ * Uses algorithm 2.29 from Hankerson, Menezes, Vanstone. Guide to
+ * Elliptic Curve Cryptography. */
+mp_err
+ec_GFp_nistp256_mod(const mp_int *a, mp_int *r, const GFMethod *meth)
+{
+ mp_err res = MP_OKAY;
+ mp_size a_used = MP_USED(a);
+ int a_bits = mpl_significant_bits(a);
+ mp_digit carry;
+
+#ifdef ECL_THIRTY_TWO_BIT
+ mp_digit a8=0, a9=0, a10=0, a11=0, a12=0, a13=0, a14=0, a15=0;
+ mp_digit r0, r1, r2, r3, r4, r5, r6, r7;
+ int r8; /* must be a signed value ! */
+#else
+ mp_digit a4=0, a5=0, a6=0, a7=0;
+ mp_digit a4h, a4l, a5h, a5l, a6h, a6l, a7h, a7l;
+ mp_digit r0, r1, r2, r3;
+ int r4; /* must be a signed value ! */
+#endif
+ /* for polynomials larger than twice the field size
+ * use regular reduction */
+ if (a_bits < 256) {
+ if (a == r) return MP_OKAY;
+ return mp_copy(a,r);
+ }
+ if (a_bits > 512) {
+ MP_CHECKOK(mp_mod(a, &meth->irr, r));
+ } else {
+
+#ifdef ECL_THIRTY_TWO_BIT
+ switch (a_used) {
+ case 16:
+ a15 = MP_DIGIT(a,15);
+ case 15:
+ a14 = MP_DIGIT(a,14);
+ case 14:
+ a13 = MP_DIGIT(a,13);
+ case 13:
+ a12 = MP_DIGIT(a,12);
+ case 12:
+ a11 = MP_DIGIT(a,11);
+ case 11:
+ a10 = MP_DIGIT(a,10);
+ case 10:
+ a9 = MP_DIGIT(a,9);
+ case 9:
+ a8 = MP_DIGIT(a,8);
+ }
+
+ r0 = MP_DIGIT(a,0);
+ r1 = MP_DIGIT(a,1);
+ r2 = MP_DIGIT(a,2);
+ r3 = MP_DIGIT(a,3);
+ r4 = MP_DIGIT(a,4);
+ r5 = MP_DIGIT(a,5);
+ r6 = MP_DIGIT(a,6);
+ r7 = MP_DIGIT(a,7);
+
+ /* sum 1 */
+ MP_ADD_CARRY(r3, a11, r3, 0, carry);
+ MP_ADD_CARRY(r4, a12, r4, carry, carry);
+ MP_ADD_CARRY(r5, a13, r5, carry, carry);
+ MP_ADD_CARRY(r6, a14, r6, carry, carry);
+ MP_ADD_CARRY(r7, a15, r7, carry, carry);
+ r8 = carry;
+ MP_ADD_CARRY(r3, a11, r3, 0, carry);
+ MP_ADD_CARRY(r4, a12, r4, carry, carry);
+ MP_ADD_CARRY(r5, a13, r5, carry, carry);
+ MP_ADD_CARRY(r6, a14, r6, carry, carry);
+ MP_ADD_CARRY(r7, a15, r7, carry, carry);
+ r8 += carry;
+ /* sum 2 */
+ MP_ADD_CARRY(r3, a12, r3, 0, carry);
+ MP_ADD_CARRY(r4, a13, r4, carry, carry);
+ MP_ADD_CARRY(r5, a14, r5, carry, carry);
+ MP_ADD_CARRY(r6, a15, r6, carry, carry);
+ MP_ADD_CARRY(r7, 0, r7, carry, carry);
+ r8 += carry;
+ /* combine last bottom of sum 3 with second sum 2 */
+ MP_ADD_CARRY(r0, a8, r0, 0, carry);
+ MP_ADD_CARRY(r1, a9, r1, carry, carry);
+ MP_ADD_CARRY(r2, a10, r2, carry, carry);
+ MP_ADD_CARRY(r3, a12, r3, carry, carry);
+ MP_ADD_CARRY(r4, a13, r4, carry, carry);
+ MP_ADD_CARRY(r5, a14, r5, carry, carry);
+ MP_ADD_CARRY(r6, a15, r6, carry, carry);
+ MP_ADD_CARRY(r7, a15, r7, carry, carry); /* from sum 3 */
+ r8 += carry;
+ /* sum 3 (rest of it)*/
+ MP_ADD_CARRY(r6, a14, r6, 0, carry);
+ MP_ADD_CARRY(r7, 0, r7, carry, carry);
+ r8 += carry;
+ /* sum 4 (rest of it)*/
+ MP_ADD_CARRY(r0, a9, r0, 0, carry);
+ MP_ADD_CARRY(r1, a10, r1, carry, carry);
+ MP_ADD_CARRY(r2, a11, r2, carry, carry);
+ MP_ADD_CARRY(r3, a13, r3, carry, carry);
+ MP_ADD_CARRY(r4, a14, r4, carry, carry);
+ MP_ADD_CARRY(r5, a15, r5, carry, carry);
+ MP_ADD_CARRY(r6, a13, r6, carry, carry);
+ MP_ADD_CARRY(r7, a8, r7, carry, carry);
+ r8 += carry;
+ /* diff 5 */
+ MP_SUB_BORROW(r0, a11, r0, 0, carry);
+ MP_SUB_BORROW(r1, a12, r1, carry, carry);
+ MP_SUB_BORROW(r2, a13, r2, carry, carry);
+ MP_SUB_BORROW(r3, 0, r3, carry, carry);
+ MP_SUB_BORROW(r4, 0, r4, carry, carry);
+ MP_SUB_BORROW(r5, 0, r5, carry, carry);
+ MP_SUB_BORROW(r6, a8, r6, carry, carry);
+ MP_SUB_BORROW(r7, a10, r7, carry, carry);
+ r8 -= carry;
+ /* diff 6 */
+ MP_SUB_BORROW(r0, a12, r0, 0, carry);
+ MP_SUB_BORROW(r1, a13, r1, carry, carry);
+ MP_SUB_BORROW(r2, a14, r2, carry, carry);
+ MP_SUB_BORROW(r3, a15, r3, carry, carry);
+ MP_SUB_BORROW(r4, 0, r4, carry, carry);
+ MP_SUB_BORROW(r5, 0, r5, carry, carry);
+ MP_SUB_BORROW(r6, a9, r6, carry, carry);
+ MP_SUB_BORROW(r7, a11, r7, carry, carry);
+ r8 -= carry;
+ /* diff 7 */
+ MP_SUB_BORROW(r0, a13, r0, 0, carry);
+ MP_SUB_BORROW(r1, a14, r1, carry, carry);
+ MP_SUB_BORROW(r2, a15, r2, carry, carry);
+ MP_SUB_BORROW(r3, a8, r3, carry, carry);
+ MP_SUB_BORROW(r4, a9, r4, carry, carry);
+ MP_SUB_BORROW(r5, a10, r5, carry, carry);
+ MP_SUB_BORROW(r6, 0, r6, carry, carry);
+ MP_SUB_BORROW(r7, a12, r7, carry, carry);
+ r8 -= carry;
+ /* diff 8 */
+ MP_SUB_BORROW(r0, a14, r0, 0, carry);
+ MP_SUB_BORROW(r1, a15, r1, carry, carry);
+ MP_SUB_BORROW(r2, 0, r2, carry, carry);
+ MP_SUB_BORROW(r3, a9, r3, carry, carry);
+ MP_SUB_BORROW(r4, a10, r4, carry, carry);
+ MP_SUB_BORROW(r5, a11, r5, carry, carry);
+ MP_SUB_BORROW(r6, 0, r6, carry, carry);
+ MP_SUB_BORROW(r7, a13, r7, carry, carry);
+ r8 -= carry;
+
+ /* reduce the overflows */
+ while (r8 > 0) {
+ mp_digit r8_d = r8;
+ MP_ADD_CARRY(r0, r8_d, r0, 0, carry);
+ MP_ADD_CARRY(r1, 0, r1, carry, carry);
+ MP_ADD_CARRY(r2, 0, r2, carry, carry);
+ MP_ADD_CARRY(r3, -r8_d, r3, carry, carry);
+ MP_ADD_CARRY(r4, MP_DIGIT_MAX, r4, carry, carry);
+ MP_ADD_CARRY(r5, MP_DIGIT_MAX, r5, carry, carry);
+ MP_ADD_CARRY(r6, -(r8_d+1), r6, carry, carry);
+ MP_ADD_CARRY(r7, (r8_d-1), r7, carry, carry);
+ r8 = carry;
+ }
+
+ /* reduce the underflows */
+ while (r8 < 0) {
+ mp_digit r8_d = -r8;
+ MP_SUB_BORROW(r0, r8_d, r0, 0, carry);
+ MP_SUB_BORROW(r1, 0, r1, carry, carry);
+ MP_SUB_BORROW(r2, 0, r2, carry, carry);
+ MP_SUB_BORROW(r3, -r8_d, r3, carry, carry);
+ MP_SUB_BORROW(r4, MP_DIGIT_MAX, r4, carry, carry);
+ MP_SUB_BORROW(r5, MP_DIGIT_MAX, r5, carry, carry);
+ MP_SUB_BORROW(r6, -(r8_d+1), r6, carry, carry);
+ MP_SUB_BORROW(r7, (r8_d-1), r7, carry, carry);
+ r8 = -carry;
+ }
+ if (a != r) {
+ MP_CHECKOK(s_mp_pad(r,8));
+ }
+ MP_SIGN(r) = MP_ZPOS;
+ MP_USED(r) = 8;
+
+ MP_DIGIT(r,7) = r7;
+ MP_DIGIT(r,6) = r6;
+ MP_DIGIT(r,5) = r5;
+ MP_DIGIT(r,4) = r4;
+ MP_DIGIT(r,3) = r3;
+ MP_DIGIT(r,2) = r2;
+ MP_DIGIT(r,1) = r1;
+ MP_DIGIT(r,0) = r0;
+
+ /* final reduction if necessary */
+ if ((r7 == MP_DIGIT_MAX) &&
+ ((r6 > 1) || ((r6 == 1) &&
+ (r5 || r4 || r3 ||
+ ((r2 == MP_DIGIT_MAX) && (r1 == MP_DIGIT_MAX)
+ && (r0 == MP_DIGIT_MAX)))))) {
+ MP_CHECKOK(mp_sub(r, &meth->irr, r));
+ }
+#ifdef notdef
+
+
+ /* smooth the negatives */
+ while (MP_SIGN(r) != MP_ZPOS) {
+ MP_CHECKOK(mp_add(r, &meth->irr, r));
+ }
+ while (MP_USED(r) > 8) {
+ MP_CHECKOK(mp_sub(r, &meth->irr, r));
+ }
+
+ /* final reduction if necessary */
+ if (MP_DIGIT(r,7) >= MP_DIGIT(&meth->irr,7)) {
+ if (mp_cmp(r,&meth->irr) != MP_LT) {
+ MP_CHECKOK(mp_sub(r, &meth->irr, r));
+ }
+ }
+#endif
+ s_mp_clamp(r);
+#else
+ switch (a_used) {
+ case 8:
+ a7 = MP_DIGIT(a,7);
+ case 7:
+ a6 = MP_DIGIT(a,6);
+ case 6:
+ a5 = MP_DIGIT(a,5);
+ case 5:
+ a4 = MP_DIGIT(a,4);
+ }
+ a7l = a7 << 32;
+ a7h = a7 >> 32;
+ a6l = a6 << 32;
+ a6h = a6 >> 32;
+ a5l = a5 << 32;
+ a5h = a5 >> 32;
+ a4l = a4 << 32;
+ a4h = a4 >> 32;
+ r3 = MP_DIGIT(a,3);
+ r2 = MP_DIGIT(a,2);
+ r1 = MP_DIGIT(a,1);
+ r0 = MP_DIGIT(a,0);
+
+ /* sum 1 */
+ MP_ADD_CARRY(r1, a5h << 32, r1, 0, carry);
+ MP_ADD_CARRY(r2, a6, r2, carry, carry);
+ MP_ADD_CARRY(r3, a7, r3, carry, carry);
+ r4 = carry;
+ MP_ADD_CARRY(r1, a5h << 32, r1, 0, carry);
+ MP_ADD_CARRY(r2, a6, r2, carry, carry);
+ MP_ADD_CARRY(r3, a7, r3, carry, carry);
+ r4 += carry;
+ /* sum 2 */
+ MP_ADD_CARRY(r1, a6l, r1, 0, carry);
+ MP_ADD_CARRY(r2, a6h | a7l, r2, carry, carry);
+ MP_ADD_CARRY(r3, a7h, r3, carry, carry);
+ r4 += carry;
+ MP_ADD_CARRY(r1, a6l, r1, 0, carry);
+ MP_ADD_CARRY(r2, a6h | a7l, r2, carry, carry);
+ MP_ADD_CARRY(r3, a7h, r3, carry, carry);
+ r4 += carry;
+
+ /* sum 3 */
+ MP_ADD_CARRY(r0, a4, r0, 0, carry);
+ MP_ADD_CARRY(r1, a5l >> 32, r1, carry, carry);
+ MP_ADD_CARRY(r2, 0, r2, carry, carry);
+ MP_ADD_CARRY(r3, a7, r3, carry, carry);
+ r4 += carry;
+ /* sum 4 */
+ MP_ADD_CARRY(r0, a4h | a5l, r0, 0, carry);
+ MP_ADD_CARRY(r1, a5h|(a6h<<32), r1, carry, carry);
+ MP_ADD_CARRY(r2, a7, r2, carry, carry);
+ MP_ADD_CARRY(r3, a6h | a4l, r3, carry, carry);
+ r4 += carry;
+ /* diff 5 */
+ MP_SUB_BORROW(r0, a5h | a6l, r0, 0, carry);
+ MP_SUB_BORROW(r1, a6h, r1, carry, carry);
+ MP_SUB_BORROW(r2, 0, r2, carry, carry);
+ MP_SUB_BORROW(r3, (a4l>>32)|a5l,r3, carry, carry);
+ r4 -= carry;
+ /* diff 6 */
+ MP_SUB_BORROW(r0, a6, r0, 0, carry);
+ MP_SUB_BORROW(r1, a7, r1, carry, carry);
+ MP_SUB_BORROW(r2, 0, r2, carry, carry);
+ MP_SUB_BORROW(r3, a4h|(a5h<<32),r3, carry, carry);
+ r4 -= carry;
+ /* diff 7 */
+ MP_SUB_BORROW(r0, a6h|a7l, r0, 0, carry);
+ MP_SUB_BORROW(r1, a7h|a4l, r1, carry, carry);
+ MP_SUB_BORROW(r2, a4h|a5l, r2, carry, carry);
+ MP_SUB_BORROW(r3, a6l, r3, carry, carry);
+ r4 -= carry;
+ /* diff 8 */
+ MP_SUB_BORROW(r0, a7, r0, 0, carry);
+ MP_SUB_BORROW(r1, a4h<<32, r1, carry, carry);
+ MP_SUB_BORROW(r2, a5, r2, carry, carry);
+ MP_SUB_BORROW(r3, a6h<<32, r3, carry, carry);
+ r4 -= carry;
+
+ /* reduce the overflows */
+ while (r4 > 0) {
+ mp_digit r4_long = r4;
+ mp_digit r4l = (r4_long << 32);
+ MP_ADD_CARRY(r0, r4_long, r0, 0, carry);
+ MP_ADD_CARRY(r1, -r4l, r1, carry, carry);
+ MP_ADD_CARRY(r2, MP_DIGIT_MAX, r2, carry, carry);
+ MP_ADD_CARRY(r3, r4l-r4_long-1,r3, carry, carry);
+ r4 = carry;
+ }
+
+ /* reduce the underflows */
+ while (r4 < 0) {
+ mp_digit r4_long = -r4;
+ mp_digit r4l = (r4_long << 32);
+ MP_SUB_BORROW(r0, r4_long, r0, 0, carry);
+ MP_SUB_BORROW(r1, -r4l, r1, carry, carry);
+ MP_SUB_BORROW(r2, MP_DIGIT_MAX, r2, carry, carry);
+ MP_SUB_BORROW(r3, r4l-r4_long-1,r3, carry, carry);
+ r4 = -carry;
+ }
+
+ if (a != r) {
+ MP_CHECKOK(s_mp_pad(r,4));
+ }
+ MP_SIGN(r) = MP_ZPOS;
+ MP_USED(r) = 4;
+
+ MP_DIGIT(r,3) = r3;
+ MP_DIGIT(r,2) = r2;
+ MP_DIGIT(r,1) = r1;
+ MP_DIGIT(r,0) = r0;
+
+ /* final reduction if necessary */
+ if ((r3 > 0xFFFFFFFF00000001ULL) ||
+ ((r3 == 0xFFFFFFFF00000001ULL) &&
+ (r2 || (r1 >> 32)||
+ (r1 == 0xFFFFFFFFULL && r0 == MP_DIGIT_MAX)))) {
+ /* very rare, just use mp_sub */
+ MP_CHECKOK(mp_sub(r, &meth->irr, r));
+ }
+
+ s_mp_clamp(r);
+#endif
+ }
+
+ CLEANUP:
+ return res;
+}
+
+/* Compute the square of polynomial a, reduce modulo p256. Store the
+ * result in r. r could be a. Uses optimized modular reduction for p256.
+ */
+mp_err
+ec_GFp_nistp256_sqr(const mp_int *a, mp_int *r, const GFMethod *meth)
+{
+ mp_err res = MP_OKAY;
+
+ MP_CHECKOK(mp_sqr(a, r));
+ MP_CHECKOK(ec_GFp_nistp256_mod(r, r, meth));
+ CLEANUP:
+ return res;
+}
+
+/* Compute the product of two polynomials a and b, reduce modulo p256.
+ * Store the result in r. r could be a or b; a could be b. Uses
+ * optimized modular reduction for p256. */
+mp_err
+ec_GFp_nistp256_mul(const mp_int *a, const mp_int *b, mp_int *r,
+ const GFMethod *meth)
+{
+ mp_err res = MP_OKAY;
+
+ MP_CHECKOK(mp_mul(a, b, r));
+ MP_CHECKOK(ec_GFp_nistp256_mod(r, r, meth));
+ CLEANUP:
+ return res;
+}
+
+/* Wire in fast field arithmetic and precomputation of base point for
+ * named curves. */
+mp_err
+ec_group_set_gfp256(ECGroup *group, ECCurveName name)
+{
+ if (name == ECCurve_NIST_P256) {
+ group->meth->field_mod = &ec_GFp_nistp256_mod;
+ group->meth->field_mul = &ec_GFp_nistp256_mul;
+ group->meth->field_sqr = &ec_GFp_nistp256_sqr;
+ }
+ return MP_OKAY;
+}