Hannes Tschofenig / Mbed 2 deprecated aes-gcm-test-program

Example program to test AES-GCM functionality. Used for a workshop

Dependencies:   mbed

SSL/library/bignum.c@0:796d0f61a05b, 2018-09-27 (annotated)

Committer:
HannesTschofenig
Date:
Thu Sep 27 06:34:22 2018 +0000
Revision:
0:796d0f61a05b
Example AES-GCM test program

Who changed what in which revision?

UserRevisionLine numberNew contents of line
HannesTschofenig 0:796d0f61a05b 1 /*
HannesTschofenig 0:796d0f61a05b 2 * Multi-precision integer library
HannesTschofenig 0:796d0f61a05b 3 *
HannesTschofenig 0:796d0f61a05b 4 * Copyright (C) 2006-2014, Brainspark B.V.
HannesTschofenig 0:796d0f61a05b 5 *
HannesTschofenig 0:796d0f61a05b 6 * This file is part of PolarSSL (http://www.polarssl.org)
HannesTschofenig 0:796d0f61a05b 7 * Lead Maintainer: Paul Bakker <polarssl_maintainer at polarssl.org>
HannesTschofenig 0:796d0f61a05b 8 *
HannesTschofenig 0:796d0f61a05b 9 * All rights reserved.
HannesTschofenig 0:796d0f61a05b 10 *
HannesTschofenig 0:796d0f61a05b 11 * This program is free software; you can redistribute it and/or modify
HannesTschofenig 0:796d0f61a05b 12 * it under the terms of the GNU General Public License as published by
HannesTschofenig 0:796d0f61a05b 13 * the Free Software Foundation; either version 2 of the License, or
HannesTschofenig 0:796d0f61a05b 14 * (at your option) any later version.
HannesTschofenig 0:796d0f61a05b 15 *
HannesTschofenig 0:796d0f61a05b 16 * This program is distributed in the hope that it will be useful,
HannesTschofenig 0:796d0f61a05b 17 * but WITHOUT ANY WARRANTY; without even the implied warranty of
HannesTschofenig 0:796d0f61a05b 18 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
HannesTschofenig 0:796d0f61a05b 19 * GNU General Public License for more details.
HannesTschofenig 0:796d0f61a05b 20 *
HannesTschofenig 0:796d0f61a05b 21 * You should have received a copy of the GNU General Public License along
HannesTschofenig 0:796d0f61a05b 22 * with this program; if not, write to the Free Software Foundation, Inc.,
HannesTschofenig 0:796d0f61a05b 23 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
HannesTschofenig 0:796d0f61a05b 24 */
HannesTschofenig 0:796d0f61a05b 25 /*
HannesTschofenig 0:796d0f61a05b 26 * This MPI implementation is based on:
HannesTschofenig 0:796d0f61a05b 27 *
HannesTschofenig 0:796d0f61a05b 28 * http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf
HannesTschofenig 0:796d0f61a05b 29 * http://www.stillhq.com/extracted/gnupg-api/mpi/
HannesTschofenig 0:796d0f61a05b 30 * http://math.libtomcrypt.com/files/tommath.pdf
HannesTschofenig 0:796d0f61a05b 31 */
HannesTschofenig 0:796d0f61a05b 32
HannesTschofenig 0:796d0f61a05b 33 #if !defined(POLARSSL_CONFIG_FILE)
HannesTschofenig 0:796d0f61a05b 34 #include "polarssl/config.h"
HannesTschofenig 0:796d0f61a05b 35 #else
HannesTschofenig 0:796d0f61a05b 36 #include POLARSSL_CONFIG_FILE
HannesTschofenig 0:796d0f61a05b 37 #endif
HannesTschofenig 0:796d0f61a05b 38
HannesTschofenig 0:796d0f61a05b 39 #if defined(POLARSSL_BIGNUM_C)
HannesTschofenig 0:796d0f61a05b 40
HannesTschofenig 0:796d0f61a05b 41 #include "polarssl/bignum.h"
HannesTschofenig 0:796d0f61a05b 42 #include "polarssl/bn_mul.h"
HannesTschofenig 0:796d0f61a05b 43
HannesTschofenig 0:796d0f61a05b 44 #if defined(POLARSSL_PLATFORM_C)
HannesTschofenig 0:796d0f61a05b 45 #include "polarssl/platform.h"
HannesTschofenig 0:796d0f61a05b 46 #else
HannesTschofenig 0:796d0f61a05b 47 #define polarssl_printf printf
HannesTschofenig 0:796d0f61a05b 48 #define polarssl_malloc malloc
HannesTschofenig 0:796d0f61a05b 49 #define polarssl_free free
HannesTschofenig 0:796d0f61a05b 50 #endif
HannesTschofenig 0:796d0f61a05b 51
HannesTschofenig 0:796d0f61a05b 52 #include <stdlib.h>
HannesTschofenig 0:796d0f61a05b 53
HannesTschofenig 0:796d0f61a05b 54 #define ciL (sizeof(t_uint)) /* chars in limb */
HannesTschofenig 0:796d0f61a05b 55 #define biL (ciL << 3) /* bits in limb */
HannesTschofenig 0:796d0f61a05b 56 #define biH (ciL << 2) /* half limb size */
HannesTschofenig 0:796d0f61a05b 57
HannesTschofenig 0:796d0f61a05b 58 /*
HannesTschofenig 0:796d0f61a05b 59 * Convert between bits/chars and number of limbs
HannesTschofenig 0:796d0f61a05b 60 */
HannesTschofenig 0:796d0f61a05b 61 #define BITS_TO_LIMBS(i) (((i) + biL - 1) / biL)
HannesTschofenig 0:796d0f61a05b 62 #define CHARS_TO_LIMBS(i) (((i) + ciL - 1) / ciL)
HannesTschofenig 0:796d0f61a05b 63
HannesTschofenig 0:796d0f61a05b 64 /*
HannesTschofenig 0:796d0f61a05b 65 * Initialize one MPI
HannesTschofenig 0:796d0f61a05b 66 */
HannesTschofenig 0:796d0f61a05b 67 void mpi_init( mpi *X )
HannesTschofenig 0:796d0f61a05b 68 {
HannesTschofenig 0:796d0f61a05b 69 if( X == NULL )
HannesTschofenig 0:796d0f61a05b 70 return;
HannesTschofenig 0:796d0f61a05b 71
HannesTschofenig 0:796d0f61a05b 72 X->s = 1;
HannesTschofenig 0:796d0f61a05b 73 X->n = 0;
HannesTschofenig 0:796d0f61a05b 74 X->p = NULL;
HannesTschofenig 0:796d0f61a05b 75 }
HannesTschofenig 0:796d0f61a05b 76
HannesTschofenig 0:796d0f61a05b 77 /*
HannesTschofenig 0:796d0f61a05b 78 * Unallocate one MPI
HannesTschofenig 0:796d0f61a05b 79 */
HannesTschofenig 0:796d0f61a05b 80 void mpi_free( mpi *X )
HannesTschofenig 0:796d0f61a05b 81 {
HannesTschofenig 0:796d0f61a05b 82 if( X == NULL )
HannesTschofenig 0:796d0f61a05b 83 return;
HannesTschofenig 0:796d0f61a05b 84
HannesTschofenig 0:796d0f61a05b 85 if( X->p != NULL )
HannesTschofenig 0:796d0f61a05b 86 {
HannesTschofenig 0:796d0f61a05b 87 memset( X->p, 0, X->n * ciL );
HannesTschofenig 0:796d0f61a05b 88 polarssl_free( X->p );
HannesTschofenig 0:796d0f61a05b 89 }
HannesTschofenig 0:796d0f61a05b 90
HannesTschofenig 0:796d0f61a05b 91 X->s = 1;
HannesTschofenig 0:796d0f61a05b 92 X->n = 0;
HannesTschofenig 0:796d0f61a05b 93 X->p = NULL;
HannesTschofenig 0:796d0f61a05b 94 }
HannesTschofenig 0:796d0f61a05b 95
HannesTschofenig 0:796d0f61a05b 96 /*
HannesTschofenig 0:796d0f61a05b 97 * Enlarge to the specified number of limbs
HannesTschofenig 0:796d0f61a05b 98 */
HannesTschofenig 0:796d0f61a05b 99 int mpi_grow( mpi *X, size_t nblimbs )
HannesTschofenig 0:796d0f61a05b 100 {
HannesTschofenig 0:796d0f61a05b 101 t_uint *p;
HannesTschofenig 0:796d0f61a05b 102
HannesTschofenig 0:796d0f61a05b 103 if( nblimbs > POLARSSL_MPI_MAX_LIMBS )
HannesTschofenig 0:796d0f61a05b 104 return( POLARSSL_ERR_MPI_MALLOC_FAILED );
HannesTschofenig 0:796d0f61a05b 105
HannesTschofenig 0:796d0f61a05b 106 if( X->n < nblimbs )
HannesTschofenig 0:796d0f61a05b 107 {
HannesTschofenig 0:796d0f61a05b 108 if( ( p = (t_uint *) polarssl_malloc( nblimbs * ciL ) ) == NULL )
HannesTschofenig 0:796d0f61a05b 109 return( POLARSSL_ERR_MPI_MALLOC_FAILED );
HannesTschofenig 0:796d0f61a05b 110
HannesTschofenig 0:796d0f61a05b 111 memset( p, 0, nblimbs * ciL );
HannesTschofenig 0:796d0f61a05b 112
HannesTschofenig 0:796d0f61a05b 113 if( X->p != NULL )
HannesTschofenig 0:796d0f61a05b 114 {
HannesTschofenig 0:796d0f61a05b 115 memcpy( p, X->p, X->n * ciL );
HannesTschofenig 0:796d0f61a05b 116 memset( X->p, 0, X->n * ciL );
HannesTschofenig 0:796d0f61a05b 117 polarssl_free( X->p );
HannesTschofenig 0:796d0f61a05b 118 }
HannesTschofenig 0:796d0f61a05b 119
HannesTschofenig 0:796d0f61a05b 120 X->n = nblimbs;
HannesTschofenig 0:796d0f61a05b 121 X->p = p;
HannesTschofenig 0:796d0f61a05b 122 }
HannesTschofenig 0:796d0f61a05b 123
HannesTschofenig 0:796d0f61a05b 124 return( 0 );
HannesTschofenig 0:796d0f61a05b 125 }
HannesTschofenig 0:796d0f61a05b 126
HannesTschofenig 0:796d0f61a05b 127 /*
HannesTschofenig 0:796d0f61a05b 128 * Resize down as much as possible,
HannesTschofenig 0:796d0f61a05b 129 * while keeping at least the specified number of limbs
HannesTschofenig 0:796d0f61a05b 130 */
HannesTschofenig 0:796d0f61a05b 131 int mpi_shrink( mpi *X, size_t nblimbs )
HannesTschofenig 0:796d0f61a05b 132 {
HannesTschofenig 0:796d0f61a05b 133 t_uint *p;
HannesTschofenig 0:796d0f61a05b 134 size_t i;
HannesTschofenig 0:796d0f61a05b 135
HannesTschofenig 0:796d0f61a05b 136 /* Actually resize up in this case */
HannesTschofenig 0:796d0f61a05b 137 if( X->n <= nblimbs )
HannesTschofenig 0:796d0f61a05b 138 return( mpi_grow( X, nblimbs ) );
HannesTschofenig 0:796d0f61a05b 139
HannesTschofenig 0:796d0f61a05b 140 for( i = X->n - 1; i > 0; i-- )
HannesTschofenig 0:796d0f61a05b 141 if( X->p[i] != 0 )
HannesTschofenig 0:796d0f61a05b 142 break;
HannesTschofenig 0:796d0f61a05b 143 i++;
HannesTschofenig 0:796d0f61a05b 144
HannesTschofenig 0:796d0f61a05b 145 if( i < nblimbs )
HannesTschofenig 0:796d0f61a05b 146 i = nblimbs;
HannesTschofenig 0:796d0f61a05b 147
HannesTschofenig 0:796d0f61a05b 148 if( ( p = (t_uint *) polarssl_malloc( i * ciL ) ) == NULL )
HannesTschofenig 0:796d0f61a05b 149 return( POLARSSL_ERR_MPI_MALLOC_FAILED );
HannesTschofenig 0:796d0f61a05b 150
HannesTschofenig 0:796d0f61a05b 151 memset( p, 0, i * ciL );
HannesTschofenig 0:796d0f61a05b 152
HannesTschofenig 0:796d0f61a05b 153 if( X->p != NULL )
HannesTschofenig 0:796d0f61a05b 154 {
HannesTschofenig 0:796d0f61a05b 155 memcpy( p, X->p, i * ciL );
HannesTschofenig 0:796d0f61a05b 156 memset( X->p, 0, X->n * ciL );
HannesTschofenig 0:796d0f61a05b 157 polarssl_free( X->p );
HannesTschofenig 0:796d0f61a05b 158 }
HannesTschofenig 0:796d0f61a05b 159
HannesTschofenig 0:796d0f61a05b 160 X->n = i;
HannesTschofenig 0:796d0f61a05b 161 X->p = p;
HannesTschofenig 0:796d0f61a05b 162
HannesTschofenig 0:796d0f61a05b 163 return( 0 );
HannesTschofenig 0:796d0f61a05b 164 }
HannesTschofenig 0:796d0f61a05b 165
HannesTschofenig 0:796d0f61a05b 166 /*
HannesTschofenig 0:796d0f61a05b 167 * Copy the contents of Y into X
HannesTschofenig 0:796d0f61a05b 168 */
HannesTschofenig 0:796d0f61a05b 169 int mpi_copy( mpi *X, const mpi *Y )
HannesTschofenig 0:796d0f61a05b 170 {
HannesTschofenig 0:796d0f61a05b 171 int ret;
HannesTschofenig 0:796d0f61a05b 172 size_t i;
HannesTschofenig 0:796d0f61a05b 173
HannesTschofenig 0:796d0f61a05b 174 if( X == Y )
HannesTschofenig 0:796d0f61a05b 175 return( 0 );
HannesTschofenig 0:796d0f61a05b 176
HannesTschofenig 0:796d0f61a05b 177 if( Y->p == NULL )
HannesTschofenig 0:796d0f61a05b 178 {
HannesTschofenig 0:796d0f61a05b 179 mpi_free( X );
HannesTschofenig 0:796d0f61a05b 180 return( 0 );
HannesTschofenig 0:796d0f61a05b 181 }
HannesTschofenig 0:796d0f61a05b 182
HannesTschofenig 0:796d0f61a05b 183 for( i = Y->n - 1; i > 0; i-- )
HannesTschofenig 0:796d0f61a05b 184 if( Y->p[i] != 0 )
HannesTschofenig 0:796d0f61a05b 185 break;
HannesTschofenig 0:796d0f61a05b 186 i++;
HannesTschofenig 0:796d0f61a05b 187
HannesTschofenig 0:796d0f61a05b 188 X->s = Y->s;
HannesTschofenig 0:796d0f61a05b 189
HannesTschofenig 0:796d0f61a05b 190 MPI_CHK( mpi_grow( X, i ) );
HannesTschofenig 0:796d0f61a05b 191
HannesTschofenig 0:796d0f61a05b 192 memset( X->p, 0, X->n * ciL );
HannesTschofenig 0:796d0f61a05b 193 memcpy( X->p, Y->p, i * ciL );
HannesTschofenig 0:796d0f61a05b 194
HannesTschofenig 0:796d0f61a05b 195 cleanup:
HannesTschofenig 0:796d0f61a05b 196
HannesTschofenig 0:796d0f61a05b 197 return( ret );
HannesTschofenig 0:796d0f61a05b 198 }
HannesTschofenig 0:796d0f61a05b 199
HannesTschofenig 0:796d0f61a05b 200 /*
HannesTschofenig 0:796d0f61a05b 201 * Swap the contents of X and Y
HannesTschofenig 0:796d0f61a05b 202 */
HannesTschofenig 0:796d0f61a05b 203 void mpi_swap( mpi *X, mpi *Y )
HannesTschofenig 0:796d0f61a05b 204 {
HannesTschofenig 0:796d0f61a05b 205 mpi T;
HannesTschofenig 0:796d0f61a05b 206
HannesTschofenig 0:796d0f61a05b 207 memcpy( &T, X, sizeof( mpi ) );
HannesTschofenig 0:796d0f61a05b 208 memcpy( X, Y, sizeof( mpi ) );
HannesTschofenig 0:796d0f61a05b 209 memcpy( Y, &T, sizeof( mpi ) );
HannesTschofenig 0:796d0f61a05b 210 }
HannesTschofenig 0:796d0f61a05b 211
HannesTschofenig 0:796d0f61a05b 212 /*
HannesTschofenig 0:796d0f61a05b 213 * Conditionally assign X = Y, without leaking information
HannesTschofenig 0:796d0f61a05b 214 * about whether the assignment was made or not.
HannesTschofenig 0:796d0f61a05b 215 * (Leaking information about the respective sizes of X and Y is ok however.)
HannesTschofenig 0:796d0f61a05b 216 */
HannesTschofenig 0:796d0f61a05b 217 int mpi_safe_cond_assign( mpi *X, const mpi *Y, unsigned char assign )
HannesTschofenig 0:796d0f61a05b 218 {
HannesTschofenig 0:796d0f61a05b 219 int ret = 0;
HannesTschofenig 0:796d0f61a05b 220 size_t i;
HannesTschofenig 0:796d0f61a05b 221
HannesTschofenig 0:796d0f61a05b 222 /* make sure assign is 0 or 1 */
HannesTschofenig 0:796d0f61a05b 223 assign = ( assign != 0 );
HannesTschofenig 0:796d0f61a05b 224
HannesTschofenig 0:796d0f61a05b 225 MPI_CHK( mpi_grow( X, Y->n ) );
HannesTschofenig 0:796d0f61a05b 226
HannesTschofenig 0:796d0f61a05b 227 X->s = X->s * (1 - assign) + Y->s * assign;
HannesTschofenig 0:796d0f61a05b 228
HannesTschofenig 0:796d0f61a05b 229 for( i = 0; i < Y->n; i++ )
HannesTschofenig 0:796d0f61a05b 230 X->p[i] = X->p[i] * (1 - assign) + Y->p[i] * assign;
HannesTschofenig 0:796d0f61a05b 231
HannesTschofenig 0:796d0f61a05b 232 for( ; i < X->n; i++ )
HannesTschofenig 0:796d0f61a05b 233 X->p[i] *= (1 - assign);
HannesTschofenig 0:796d0f61a05b 234
HannesTschofenig 0:796d0f61a05b 235 cleanup:
HannesTschofenig 0:796d0f61a05b 236 return( ret );
HannesTschofenig 0:796d0f61a05b 237 }
HannesTschofenig 0:796d0f61a05b 238
HannesTschofenig 0:796d0f61a05b 239 /*
HannesTschofenig 0:796d0f61a05b 240 * Conditionally swap X and Y, without leaking information
HannesTschofenig 0:796d0f61a05b 241 * about whether the swap was made or not.
HannesTschofenig 0:796d0f61a05b 242 * Here it is not ok to simply swap the pointers, which whould lead to
HannesTschofenig 0:796d0f61a05b 243 * different memory access patterns when X and Y are used afterwards.
HannesTschofenig 0:796d0f61a05b 244 */
HannesTschofenig 0:796d0f61a05b 245 int mpi_safe_cond_swap( mpi *X, mpi *Y, unsigned char swap )
HannesTschofenig 0:796d0f61a05b 246 {
HannesTschofenig 0:796d0f61a05b 247 int ret, s;
HannesTschofenig 0:796d0f61a05b 248 size_t i;
HannesTschofenig 0:796d0f61a05b 249 t_uint tmp;
HannesTschofenig 0:796d0f61a05b 250
HannesTschofenig 0:796d0f61a05b 251 if( X == Y )
HannesTschofenig 0:796d0f61a05b 252 return( 0 );
HannesTschofenig 0:796d0f61a05b 253
HannesTschofenig 0:796d0f61a05b 254 /* make sure swap is 0 or 1 */
HannesTschofenig 0:796d0f61a05b 255 swap = ( swap != 0 );
HannesTschofenig 0:796d0f61a05b 256
HannesTschofenig 0:796d0f61a05b 257 MPI_CHK( mpi_grow( X, Y->n ) );
HannesTschofenig 0:796d0f61a05b 258 MPI_CHK( mpi_grow( Y, X->n ) );
HannesTschofenig 0:796d0f61a05b 259
HannesTschofenig 0:796d0f61a05b 260 s = X->s;
HannesTschofenig 0:796d0f61a05b 261 X->s = X->s * (1 - swap) + Y->s * swap;
HannesTschofenig 0:796d0f61a05b 262 Y->s = Y->s * (1 - swap) + s * swap;
HannesTschofenig 0:796d0f61a05b 263
HannesTschofenig 0:796d0f61a05b 264
HannesTschofenig 0:796d0f61a05b 265 for( i = 0; i < X->n; i++ )
HannesTschofenig 0:796d0f61a05b 266 {
HannesTschofenig 0:796d0f61a05b 267 tmp = X->p[i];
HannesTschofenig 0:796d0f61a05b 268 X->p[i] = X->p[i] * (1 - swap) + Y->p[i] * swap;
HannesTschofenig 0:796d0f61a05b 269 Y->p[i] = Y->p[i] * (1 - swap) + tmp * swap;
HannesTschofenig 0:796d0f61a05b 270 }
HannesTschofenig 0:796d0f61a05b 271
HannesTschofenig 0:796d0f61a05b 272 cleanup:
HannesTschofenig 0:796d0f61a05b 273 return( ret );
HannesTschofenig 0:796d0f61a05b 274 }
HannesTschofenig 0:796d0f61a05b 275
HannesTschofenig 0:796d0f61a05b 276 /*
HannesTschofenig 0:796d0f61a05b 277 * Set value from integer
HannesTschofenig 0:796d0f61a05b 278 */
HannesTschofenig 0:796d0f61a05b 279 int mpi_lset( mpi *X, t_sint z )
HannesTschofenig 0:796d0f61a05b 280 {
HannesTschofenig 0:796d0f61a05b 281 int ret;
HannesTschofenig 0:796d0f61a05b 282
HannesTschofenig 0:796d0f61a05b 283 MPI_CHK( mpi_grow( X, 1 ) );
HannesTschofenig 0:796d0f61a05b 284 memset( X->p, 0, X->n * ciL );
HannesTschofenig 0:796d0f61a05b 285
HannesTschofenig 0:796d0f61a05b 286 X->p[0] = ( z < 0 ) ? -z : z;
HannesTschofenig 0:796d0f61a05b 287 X->s = ( z < 0 ) ? -1 : 1;
HannesTschofenig 0:796d0f61a05b 288
HannesTschofenig 0:796d0f61a05b 289 cleanup:
HannesTschofenig 0:796d0f61a05b 290
HannesTschofenig 0:796d0f61a05b 291 return( ret );
HannesTschofenig 0:796d0f61a05b 292 }
HannesTschofenig 0:796d0f61a05b 293
HannesTschofenig 0:796d0f61a05b 294 /*
HannesTschofenig 0:796d0f61a05b 295 * Get a specific bit
HannesTschofenig 0:796d0f61a05b 296 */
HannesTschofenig 0:796d0f61a05b 297 int mpi_get_bit( const mpi *X, size_t pos )
HannesTschofenig 0:796d0f61a05b 298 {
HannesTschofenig 0:796d0f61a05b 299 if( X->n * biL <= pos )
HannesTschofenig 0:796d0f61a05b 300 return( 0 );
HannesTschofenig 0:796d0f61a05b 301
HannesTschofenig 0:796d0f61a05b 302 return ( X->p[pos / biL] >> ( pos % biL ) ) & 0x01;
HannesTschofenig 0:796d0f61a05b 303 }
HannesTschofenig 0:796d0f61a05b 304
HannesTschofenig 0:796d0f61a05b 305 /*
HannesTschofenig 0:796d0f61a05b 306 * Set a bit to a specific value of 0 or 1
HannesTschofenig 0:796d0f61a05b 307 */
HannesTschofenig 0:796d0f61a05b 308 int mpi_set_bit( mpi *X, size_t pos, unsigned char val )
HannesTschofenig 0:796d0f61a05b 309 {
HannesTschofenig 0:796d0f61a05b 310 int ret = 0;
HannesTschofenig 0:796d0f61a05b 311 size_t off = pos / biL;
HannesTschofenig 0:796d0f61a05b 312 size_t idx = pos % biL;
HannesTschofenig 0:796d0f61a05b 313
HannesTschofenig 0:796d0f61a05b 314 if( val != 0 && val != 1 )
HannesTschofenig 0:796d0f61a05b 315 return POLARSSL_ERR_MPI_BAD_INPUT_DATA;
HannesTschofenig 0:796d0f61a05b 316
HannesTschofenig 0:796d0f61a05b 317 if( X->n * biL <= pos )
HannesTschofenig 0:796d0f61a05b 318 {
HannesTschofenig 0:796d0f61a05b 319 if( val == 0 )
HannesTschofenig 0:796d0f61a05b 320 return ( 0 );
HannesTschofenig 0:796d0f61a05b 321
HannesTschofenig 0:796d0f61a05b 322 MPI_CHK( mpi_grow( X, off + 1 ) );
HannesTschofenig 0:796d0f61a05b 323 }
HannesTschofenig 0:796d0f61a05b 324
HannesTschofenig 0:796d0f61a05b 325 X->p[off] &= ~( (t_uint) 0x01 << idx );
HannesTschofenig 0:796d0f61a05b 326 X->p[off] |= (t_uint) val << idx;
HannesTschofenig 0:796d0f61a05b 327
HannesTschofenig 0:796d0f61a05b 328 cleanup:
HannesTschofenig 0:796d0f61a05b 329
HannesTschofenig 0:796d0f61a05b 330 return( ret );
HannesTschofenig 0:796d0f61a05b 331 }
HannesTschofenig 0:796d0f61a05b 332
HannesTschofenig 0:796d0f61a05b 333 /*
HannesTschofenig 0:796d0f61a05b 334 * Return the number of least significant bits
HannesTschofenig 0:796d0f61a05b 335 */
HannesTschofenig 0:796d0f61a05b 336 size_t mpi_lsb( const mpi *X )
HannesTschofenig 0:796d0f61a05b 337 {
HannesTschofenig 0:796d0f61a05b 338 size_t i, j, count = 0;
HannesTschofenig 0:796d0f61a05b 339
HannesTschofenig 0:796d0f61a05b 340 for( i = 0; i < X->n; i++ )
HannesTschofenig 0:796d0f61a05b 341 for( j = 0; j < biL; j++, count++ )
HannesTschofenig 0:796d0f61a05b 342 if( ( ( X->p[i] >> j ) & 1 ) != 0 )
HannesTschofenig 0:796d0f61a05b 343 return( count );
HannesTschofenig 0:796d0f61a05b 344
HannesTschofenig 0:796d0f61a05b 345 return( 0 );
HannesTschofenig 0:796d0f61a05b 346 }
HannesTschofenig 0:796d0f61a05b 347
HannesTschofenig 0:796d0f61a05b 348 /*
HannesTschofenig 0:796d0f61a05b 349 * Return the number of most significant bits
HannesTschofenig 0:796d0f61a05b 350 */
HannesTschofenig 0:796d0f61a05b 351 size_t mpi_msb( const mpi *X )
HannesTschofenig 0:796d0f61a05b 352 {
HannesTschofenig 0:796d0f61a05b 353 size_t i, j;
HannesTschofenig 0:796d0f61a05b 354
HannesTschofenig 0:796d0f61a05b 355 for( i = X->n - 1; i > 0; i-- )
HannesTschofenig 0:796d0f61a05b 356 if( X->p[i] != 0 )
HannesTschofenig 0:796d0f61a05b 357 break;
HannesTschofenig 0:796d0f61a05b 358
HannesTschofenig 0:796d0f61a05b 359 for( j = biL; j > 0; j-- )
HannesTschofenig 0:796d0f61a05b 360 if( ( ( X->p[i] >> ( j - 1 ) ) & 1 ) != 0 )
HannesTschofenig 0:796d0f61a05b 361 break;
HannesTschofenig 0:796d0f61a05b 362
HannesTschofenig 0:796d0f61a05b 363 return( ( i * biL ) + j );
HannesTschofenig 0:796d0f61a05b 364 }
HannesTschofenig 0:796d0f61a05b 365
HannesTschofenig 0:796d0f61a05b 366 /*
HannesTschofenig 0:796d0f61a05b 367 * Return the total size in bytes
HannesTschofenig 0:796d0f61a05b 368 */
HannesTschofenig 0:796d0f61a05b 369 size_t mpi_size( const mpi *X )
HannesTschofenig 0:796d0f61a05b 370 {
HannesTschofenig 0:796d0f61a05b 371 return( ( mpi_msb( X ) + 7 ) >> 3 );
HannesTschofenig 0:796d0f61a05b 372 }
HannesTschofenig 0:796d0f61a05b 373
HannesTschofenig 0:796d0f61a05b 374 /*
HannesTschofenig 0:796d0f61a05b 375 * Convert an ASCII character to digit value
HannesTschofenig 0:796d0f61a05b 376 */
HannesTschofenig 0:796d0f61a05b 377 static int mpi_get_digit( t_uint *d, int radix, char c )
HannesTschofenig 0:796d0f61a05b 378 {
HannesTschofenig 0:796d0f61a05b 379 *d = 255;
HannesTschofenig 0:796d0f61a05b 380
HannesTschofenig 0:796d0f61a05b 381 if( c >= 0x30 && c <= 0x39 ) *d = c - 0x30;
HannesTschofenig 0:796d0f61a05b 382 if( c >= 0x41 && c <= 0x46 ) *d = c - 0x37;
HannesTschofenig 0:796d0f61a05b 383 if( c >= 0x61 && c <= 0x66 ) *d = c - 0x57;
HannesTschofenig 0:796d0f61a05b 384
HannesTschofenig 0:796d0f61a05b 385 if( *d >= (t_uint) radix )
HannesTschofenig 0:796d0f61a05b 386 return( POLARSSL_ERR_MPI_INVALID_CHARACTER );
HannesTschofenig 0:796d0f61a05b 387
HannesTschofenig 0:796d0f61a05b 388 return( 0 );
HannesTschofenig 0:796d0f61a05b 389 }
HannesTschofenig 0:796d0f61a05b 390
HannesTschofenig 0:796d0f61a05b 391 /*
HannesTschofenig 0:796d0f61a05b 392 * Import from an ASCII string
HannesTschofenig 0:796d0f61a05b 393 */
HannesTschofenig 0:796d0f61a05b 394 int mpi_read_string( mpi *X, int radix, const char *s )
HannesTschofenig 0:796d0f61a05b 395 {
HannesTschofenig 0:796d0f61a05b 396 int ret;
HannesTschofenig 0:796d0f61a05b 397 size_t i, j, slen, n;
HannesTschofenig 0:796d0f61a05b 398 t_uint d;
HannesTschofenig 0:796d0f61a05b 399 mpi T;
HannesTschofenig 0:796d0f61a05b 400
HannesTschofenig 0:796d0f61a05b 401 if( radix < 2 || radix > 16 )
HannesTschofenig 0:796d0f61a05b 402 return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
HannesTschofenig 0:796d0f61a05b 403
HannesTschofenig 0:796d0f61a05b 404 mpi_init( &T );
HannesTschofenig 0:796d0f61a05b 405
HannesTschofenig 0:796d0f61a05b 406 slen = strlen( s );
HannesTschofenig 0:796d0f61a05b 407
HannesTschofenig 0:796d0f61a05b 408 if( radix == 16 )
HannesTschofenig 0:796d0f61a05b 409 {
HannesTschofenig 0:796d0f61a05b 410 n = BITS_TO_LIMBS( slen << 2 );
HannesTschofenig 0:796d0f61a05b 411
HannesTschofenig 0:796d0f61a05b 412 MPI_CHK( mpi_grow( X, n ) );
HannesTschofenig 0:796d0f61a05b 413 MPI_CHK( mpi_lset( X, 0 ) );
HannesTschofenig 0:796d0f61a05b 414
HannesTschofenig 0:796d0f61a05b 415 for( i = slen, j = 0; i > 0; i--, j++ )
HannesTschofenig 0:796d0f61a05b 416 {
HannesTschofenig 0:796d0f61a05b 417 if( i == 1 && s[i - 1] == '-' )
HannesTschofenig 0:796d0f61a05b 418 {
HannesTschofenig 0:796d0f61a05b 419 X->s = -1;
HannesTschofenig 0:796d0f61a05b 420 break;
HannesTschofenig 0:796d0f61a05b 421 }
HannesTschofenig 0:796d0f61a05b 422
HannesTschofenig 0:796d0f61a05b 423 MPI_CHK( mpi_get_digit( &d, radix, s[i - 1] ) );
HannesTschofenig 0:796d0f61a05b 424 X->p[j / (2 * ciL)] |= d << ( (j % (2 * ciL)) << 2 );
HannesTschofenig 0:796d0f61a05b 425 }
HannesTschofenig 0:796d0f61a05b 426 }
HannesTschofenig 0:796d0f61a05b 427 else
HannesTschofenig 0:796d0f61a05b 428 {
HannesTschofenig 0:796d0f61a05b 429 MPI_CHK( mpi_lset( X, 0 ) );
HannesTschofenig 0:796d0f61a05b 430
HannesTschofenig 0:796d0f61a05b 431 for( i = 0; i < slen; i++ )
HannesTschofenig 0:796d0f61a05b 432 {
HannesTschofenig 0:796d0f61a05b 433 if( i == 0 && s[i] == '-' )
HannesTschofenig 0:796d0f61a05b 434 {
HannesTschofenig 0:796d0f61a05b 435 X->s = -1;
HannesTschofenig 0:796d0f61a05b 436 continue;
HannesTschofenig 0:796d0f61a05b 437 }
HannesTschofenig 0:796d0f61a05b 438
HannesTschofenig 0:796d0f61a05b 439 MPI_CHK( mpi_get_digit( &d, radix, s[i] ) );
HannesTschofenig 0:796d0f61a05b 440 MPI_CHK( mpi_mul_int( &T, X, radix ) );
HannesTschofenig 0:796d0f61a05b 441
HannesTschofenig 0:796d0f61a05b 442 if( X->s == 1 )
HannesTschofenig 0:796d0f61a05b 443 {
HannesTschofenig 0:796d0f61a05b 444 MPI_CHK( mpi_add_int( X, &T, d ) );
HannesTschofenig 0:796d0f61a05b 445 }
HannesTschofenig 0:796d0f61a05b 446 else
HannesTschofenig 0:796d0f61a05b 447 {
HannesTschofenig 0:796d0f61a05b 448 MPI_CHK( mpi_sub_int( X, &T, d ) );
HannesTschofenig 0:796d0f61a05b 449 }
HannesTschofenig 0:796d0f61a05b 450 }
HannesTschofenig 0:796d0f61a05b 451 }
HannesTschofenig 0:796d0f61a05b 452
HannesTschofenig 0:796d0f61a05b 453 cleanup:
HannesTschofenig 0:796d0f61a05b 454
HannesTschofenig 0:796d0f61a05b 455 mpi_free( &T );
HannesTschofenig 0:796d0f61a05b 456
HannesTschofenig 0:796d0f61a05b 457 return( ret );
HannesTschofenig 0:796d0f61a05b 458 }
HannesTschofenig 0:796d0f61a05b 459
HannesTschofenig 0:796d0f61a05b 460 /*
HannesTschofenig 0:796d0f61a05b 461 * Helper to write the digits high-order first
HannesTschofenig 0:796d0f61a05b 462 */
HannesTschofenig 0:796d0f61a05b 463 static int mpi_write_hlp( mpi *X, int radix, char **p )
HannesTschofenig 0:796d0f61a05b 464 {
HannesTschofenig 0:796d0f61a05b 465 int ret;
HannesTschofenig 0:796d0f61a05b 466 t_uint r;
HannesTschofenig 0:796d0f61a05b 467
HannesTschofenig 0:796d0f61a05b 468 if( radix < 2 || radix > 16 )
HannesTschofenig 0:796d0f61a05b 469 return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
HannesTschofenig 0:796d0f61a05b 470
HannesTschofenig 0:796d0f61a05b 471 MPI_CHK( mpi_mod_int( &r, X, radix ) );
HannesTschofenig 0:796d0f61a05b 472 MPI_CHK( mpi_div_int( X, NULL, X, radix ) );
HannesTschofenig 0:796d0f61a05b 473
HannesTschofenig 0:796d0f61a05b 474 if( mpi_cmp_int( X, 0 ) != 0 )
HannesTschofenig 0:796d0f61a05b 475 MPI_CHK( mpi_write_hlp( X, radix, p ) );
HannesTschofenig 0:796d0f61a05b 476
HannesTschofenig 0:796d0f61a05b 477 if( r < 10 )
HannesTschofenig 0:796d0f61a05b 478 *(*p)++ = (char)( r + 0x30 );
HannesTschofenig 0:796d0f61a05b 479 else
HannesTschofenig 0:796d0f61a05b 480 *(*p)++ = (char)( r + 0x37 );
HannesTschofenig 0:796d0f61a05b 481
HannesTschofenig 0:796d0f61a05b 482 cleanup:
HannesTschofenig 0:796d0f61a05b 483
HannesTschofenig 0:796d0f61a05b 484 return( ret );
HannesTschofenig 0:796d0f61a05b 485 }
HannesTschofenig 0:796d0f61a05b 486
HannesTschofenig 0:796d0f61a05b 487 /*
HannesTschofenig 0:796d0f61a05b 488 * Export into an ASCII string
HannesTschofenig 0:796d0f61a05b 489 */
HannesTschofenig 0:796d0f61a05b 490 int mpi_write_string( const mpi *X, int radix, char *s, size_t *slen )
HannesTschofenig 0:796d0f61a05b 491 {
HannesTschofenig 0:796d0f61a05b 492 int ret = 0;
HannesTschofenig 0:796d0f61a05b 493 size_t n;
HannesTschofenig 0:796d0f61a05b 494 char *p;
HannesTschofenig 0:796d0f61a05b 495 mpi T;
HannesTschofenig 0:796d0f61a05b 496
HannesTschofenig 0:796d0f61a05b 497 if( radix < 2 || radix > 16 )
HannesTschofenig 0:796d0f61a05b 498 return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
HannesTschofenig 0:796d0f61a05b 499
HannesTschofenig 0:796d0f61a05b 500 n = mpi_msb( X );
HannesTschofenig 0:796d0f61a05b 501 if( radix >= 4 ) n >>= 1;
HannesTschofenig 0:796d0f61a05b 502 if( radix >= 16 ) n >>= 1;
HannesTschofenig 0:796d0f61a05b 503 n += 3;
HannesTschofenig 0:796d0f61a05b 504
HannesTschofenig 0:796d0f61a05b 505 if( *slen < n )
HannesTschofenig 0:796d0f61a05b 506 {
HannesTschofenig 0:796d0f61a05b 507 *slen = n;
HannesTschofenig 0:796d0f61a05b 508 return( POLARSSL_ERR_MPI_BUFFER_TOO_SMALL );
HannesTschofenig 0:796d0f61a05b 509 }
HannesTschofenig 0:796d0f61a05b 510
HannesTschofenig 0:796d0f61a05b 511 p = s;
HannesTschofenig 0:796d0f61a05b 512 mpi_init( &T );
HannesTschofenig 0:796d0f61a05b 513
HannesTschofenig 0:796d0f61a05b 514 if( X->s == -1 )
HannesTschofenig 0:796d0f61a05b 515 *p++ = '-';
HannesTschofenig 0:796d0f61a05b 516
HannesTschofenig 0:796d0f61a05b 517 if( radix == 16 )
HannesTschofenig 0:796d0f61a05b 518 {
HannesTschofenig 0:796d0f61a05b 519 int c;
HannesTschofenig 0:796d0f61a05b 520 size_t i, j, k;
HannesTschofenig 0:796d0f61a05b 521
HannesTschofenig 0:796d0f61a05b 522 for( i = X->n, k = 0; i > 0; i-- )
HannesTschofenig 0:796d0f61a05b 523 {
HannesTschofenig 0:796d0f61a05b 524 for( j = ciL; j > 0; j-- )
HannesTschofenig 0:796d0f61a05b 525 {
HannesTschofenig 0:796d0f61a05b 526 c = ( X->p[i - 1] >> ( ( j - 1 ) << 3) ) & 0xFF;
HannesTschofenig 0:796d0f61a05b 527
HannesTschofenig 0:796d0f61a05b 528 if( c == 0 && k == 0 && ( i + j + 3 ) != 0 )
HannesTschofenig 0:796d0f61a05b 529 continue;
HannesTschofenig 0:796d0f61a05b 530
HannesTschofenig 0:796d0f61a05b 531 *(p++) = "0123456789ABCDEF" [c / 16];
HannesTschofenig 0:796d0f61a05b 532 *(p++) = "0123456789ABCDEF" [c % 16];
HannesTschofenig 0:796d0f61a05b 533 k = 1;
HannesTschofenig 0:796d0f61a05b 534 }
HannesTschofenig 0:796d0f61a05b 535 }
HannesTschofenig 0:796d0f61a05b 536 }
HannesTschofenig 0:796d0f61a05b 537 else
HannesTschofenig 0:796d0f61a05b 538 {
HannesTschofenig 0:796d0f61a05b 539 MPI_CHK( mpi_copy( &T, X ) );
HannesTschofenig 0:796d0f61a05b 540
HannesTschofenig 0:796d0f61a05b 541 if( T.s == -1 )
HannesTschofenig 0:796d0f61a05b 542 T.s = 1;
HannesTschofenig 0:796d0f61a05b 543
HannesTschofenig 0:796d0f61a05b 544 MPI_CHK( mpi_write_hlp( &T, radix, &p ) );
HannesTschofenig 0:796d0f61a05b 545 }
HannesTschofenig 0:796d0f61a05b 546
HannesTschofenig 0:796d0f61a05b 547 *p++ = '\0';
HannesTschofenig 0:796d0f61a05b 548 *slen = p - s;
HannesTschofenig 0:796d0f61a05b 549
HannesTschofenig 0:796d0f61a05b 550 cleanup:
HannesTschofenig 0:796d0f61a05b 551
HannesTschofenig 0:796d0f61a05b 552 mpi_free( &T );
HannesTschofenig 0:796d0f61a05b 553
HannesTschofenig 0:796d0f61a05b 554 return( ret );
HannesTschofenig 0:796d0f61a05b 555 }
HannesTschofenig 0:796d0f61a05b 556
HannesTschofenig 0:796d0f61a05b 557 #if defined(POLARSSL_FS_IO)
HannesTschofenig 0:796d0f61a05b 558 /*
HannesTschofenig 0:796d0f61a05b 559 * Read X from an opened file
HannesTschofenig 0:796d0f61a05b 560 */
HannesTschofenig 0:796d0f61a05b 561 int mpi_read_file( mpi *X, int radix, FILE *fin )
HannesTschofenig 0:796d0f61a05b 562 {
HannesTschofenig 0:796d0f61a05b 563 t_uint d;
HannesTschofenig 0:796d0f61a05b 564 size_t slen;
HannesTschofenig 0:796d0f61a05b 565 char *p;
HannesTschofenig 0:796d0f61a05b 566 /*
HannesTschofenig 0:796d0f61a05b 567 * Buffer should have space for (short) label and decimal formatted MPI,
HannesTschofenig 0:796d0f61a05b 568 * newline characters and '\0'
HannesTschofenig 0:796d0f61a05b 569 */
HannesTschofenig 0:796d0f61a05b 570 char s[ POLARSSL_MPI_RW_BUFFER_SIZE ];
HannesTschofenig 0:796d0f61a05b 571
HannesTschofenig 0:796d0f61a05b 572 memset( s, 0, sizeof( s ) );
HannesTschofenig 0:796d0f61a05b 573 if( fgets( s, sizeof( s ) - 1, fin ) == NULL )
HannesTschofenig 0:796d0f61a05b 574 return( POLARSSL_ERR_MPI_FILE_IO_ERROR );
HannesTschofenig 0:796d0f61a05b 575
HannesTschofenig 0:796d0f61a05b 576 slen = strlen( s );
HannesTschofenig 0:796d0f61a05b 577 if( slen == sizeof( s ) - 2 )
HannesTschofenig 0:796d0f61a05b 578 return( POLARSSL_ERR_MPI_BUFFER_TOO_SMALL );
HannesTschofenig 0:796d0f61a05b 579
HannesTschofenig 0:796d0f61a05b 580 if( s[slen - 1] == '\n' ) { slen--; s[slen] = '\0'; }
HannesTschofenig 0:796d0f61a05b 581 if( s[slen - 1] == '\r' ) { slen--; s[slen] = '\0'; }
HannesTschofenig 0:796d0f61a05b 582
HannesTschofenig 0:796d0f61a05b 583 p = s + slen;
HannesTschofenig 0:796d0f61a05b 584 while( --p >= s )
HannesTschofenig 0:796d0f61a05b 585 if( mpi_get_digit( &d, radix, *p ) != 0 )
HannesTschofenig 0:796d0f61a05b 586 break;
HannesTschofenig 0:796d0f61a05b 587
HannesTschofenig 0:796d0f61a05b 588 return( mpi_read_string( X, radix, p + 1 ) );
HannesTschofenig 0:796d0f61a05b 589 }
HannesTschofenig 0:796d0f61a05b 590
HannesTschofenig 0:796d0f61a05b 591 /*
HannesTschofenig 0:796d0f61a05b 592 * Write X into an opened file (or stdout if fout == NULL)
HannesTschofenig 0:796d0f61a05b 593 */
HannesTschofenig 0:796d0f61a05b 594 int mpi_write_file( const char *p, const mpi *X, int radix, FILE *fout )
HannesTschofenig 0:796d0f61a05b 595 {
HannesTschofenig 0:796d0f61a05b 596 int ret;
HannesTschofenig 0:796d0f61a05b 597 size_t n, slen, plen;
HannesTschofenig 0:796d0f61a05b 598 /*
HannesTschofenig 0:796d0f61a05b 599 * Buffer should have space for (short) label and decimal formatted MPI,
HannesTschofenig 0:796d0f61a05b 600 * newline characters and '\0'
HannesTschofenig 0:796d0f61a05b 601 */
HannesTschofenig 0:796d0f61a05b 602 char s[ POLARSSL_MPI_RW_BUFFER_SIZE ];
HannesTschofenig 0:796d0f61a05b 603
HannesTschofenig 0:796d0f61a05b 604 n = sizeof( s );
HannesTschofenig 0:796d0f61a05b 605 memset( s, 0, n );
HannesTschofenig 0:796d0f61a05b 606 n -= 2;
HannesTschofenig 0:796d0f61a05b 607
HannesTschofenig 0:796d0f61a05b 608 MPI_CHK( mpi_write_string( X, radix, s, (size_t *) &n ) );
HannesTschofenig 0:796d0f61a05b 609
HannesTschofenig 0:796d0f61a05b 610 if( p == NULL ) p = "";
HannesTschofenig 0:796d0f61a05b 611
HannesTschofenig 0:796d0f61a05b 612 plen = strlen( p );
HannesTschofenig 0:796d0f61a05b 613 slen = strlen( s );
HannesTschofenig 0:796d0f61a05b 614 s[slen++] = '\r';
HannesTschofenig 0:796d0f61a05b 615 s[slen++] = '\n';
HannesTschofenig 0:796d0f61a05b 616
HannesTschofenig 0:796d0f61a05b 617 if( fout != NULL )
HannesTschofenig 0:796d0f61a05b 618 {
HannesTschofenig 0:796d0f61a05b 619 if( fwrite( p, 1, plen, fout ) != plen ||
HannesTschofenig 0:796d0f61a05b 620 fwrite( s, 1, slen, fout ) != slen )
HannesTschofenig 0:796d0f61a05b 621 return( POLARSSL_ERR_MPI_FILE_IO_ERROR );
HannesTschofenig 0:796d0f61a05b 622 }
HannesTschofenig 0:796d0f61a05b 623 else
HannesTschofenig 0:796d0f61a05b 624 polarssl_printf( "%s%s", p, s );
HannesTschofenig 0:796d0f61a05b 625
HannesTschofenig 0:796d0f61a05b 626 cleanup:
HannesTschofenig 0:796d0f61a05b 627
HannesTschofenig 0:796d0f61a05b 628 return( ret );
HannesTschofenig 0:796d0f61a05b 629 }
HannesTschofenig 0:796d0f61a05b 630 #endif /* POLARSSL_FS_IO */
HannesTschofenig 0:796d0f61a05b 631
HannesTschofenig 0:796d0f61a05b 632 /*
HannesTschofenig 0:796d0f61a05b 633 * Import X from unsigned binary data, big endian
HannesTschofenig 0:796d0f61a05b 634 */
HannesTschofenig 0:796d0f61a05b 635 int mpi_read_binary( mpi *X, const unsigned char *buf, size_t buflen )
HannesTschofenig 0:796d0f61a05b 636 {
HannesTschofenig 0:796d0f61a05b 637 int ret;
HannesTschofenig 0:796d0f61a05b 638 size_t i, j, n;
HannesTschofenig 0:796d0f61a05b 639
HannesTschofenig 0:796d0f61a05b 640 for( n = 0; n < buflen; n++ )
HannesTschofenig 0:796d0f61a05b 641 if( buf[n] != 0 )
HannesTschofenig 0:796d0f61a05b 642 break;
HannesTschofenig 0:796d0f61a05b 643
HannesTschofenig 0:796d0f61a05b 644 MPI_CHK( mpi_grow( X, CHARS_TO_LIMBS( buflen - n ) ) );
HannesTschofenig 0:796d0f61a05b 645 MPI_CHK( mpi_lset( X, 0 ) );
HannesTschofenig 0:796d0f61a05b 646
HannesTschofenig 0:796d0f61a05b 647 for( i = buflen, j = 0; i > n; i--, j++ )
HannesTschofenig 0:796d0f61a05b 648 X->p[j / ciL] |= ((t_uint) buf[i - 1]) << ((j % ciL) << 3);
HannesTschofenig 0:796d0f61a05b 649
HannesTschofenig 0:796d0f61a05b 650 cleanup:
HannesTschofenig 0:796d0f61a05b 651
HannesTschofenig 0:796d0f61a05b 652 return( ret );
HannesTschofenig 0:796d0f61a05b 653 }
HannesTschofenig 0:796d0f61a05b 654
HannesTschofenig 0:796d0f61a05b 655 /*
HannesTschofenig 0:796d0f61a05b 656 * Export X into unsigned binary data, big endian
HannesTschofenig 0:796d0f61a05b 657 */
HannesTschofenig 0:796d0f61a05b 658 int mpi_write_binary( const mpi *X, unsigned char *buf, size_t buflen )
HannesTschofenig 0:796d0f61a05b 659 {
HannesTschofenig 0:796d0f61a05b 660 size_t i, j, n;
HannesTschofenig 0:796d0f61a05b 661
HannesTschofenig 0:796d0f61a05b 662 n = mpi_size( X );
HannesTschofenig 0:796d0f61a05b 663
HannesTschofenig 0:796d0f61a05b 664 if( buflen < n )
HannesTschofenig 0:796d0f61a05b 665 return( POLARSSL_ERR_MPI_BUFFER_TOO_SMALL );
HannesTschofenig 0:796d0f61a05b 666
HannesTschofenig 0:796d0f61a05b 667 memset( buf, 0, buflen );
HannesTschofenig 0:796d0f61a05b 668
HannesTschofenig 0:796d0f61a05b 669 for( i = buflen - 1, j = 0; n > 0; i--, j++, n-- )
HannesTschofenig 0:796d0f61a05b 670 buf[i] = (unsigned char)( X->p[j / ciL] >> ((j % ciL) << 3) );
HannesTschofenig 0:796d0f61a05b 671
HannesTschofenig 0:796d0f61a05b 672 return( 0 );
HannesTschofenig 0:796d0f61a05b 673 }
HannesTschofenig 0:796d0f61a05b 674
HannesTschofenig 0:796d0f61a05b 675 /*
HannesTschofenig 0:796d0f61a05b 676 * Left-shift: X <<= count
HannesTschofenig 0:796d0f61a05b 677 */
HannesTschofenig 0:796d0f61a05b 678 int mpi_shift_l( mpi *X, size_t count )
HannesTschofenig 0:796d0f61a05b 679 {
HannesTschofenig 0:796d0f61a05b 680 int ret;
HannesTschofenig 0:796d0f61a05b 681 size_t i, v0, t1;
HannesTschofenig 0:796d0f61a05b 682 t_uint r0 = 0, r1;
HannesTschofenig 0:796d0f61a05b 683
HannesTschofenig 0:796d0f61a05b 684 v0 = count / (biL );
HannesTschofenig 0:796d0f61a05b 685 t1 = count & (biL - 1);
HannesTschofenig 0:796d0f61a05b 686
HannesTschofenig 0:796d0f61a05b 687 i = mpi_msb( X ) + count;
HannesTschofenig 0:796d0f61a05b 688
HannesTschofenig 0:796d0f61a05b 689 if( X->n * biL < i )
HannesTschofenig 0:796d0f61a05b 690 MPI_CHK( mpi_grow( X, BITS_TO_LIMBS( i ) ) );
HannesTschofenig 0:796d0f61a05b 691
HannesTschofenig 0:796d0f61a05b 692 ret = 0;
HannesTschofenig 0:796d0f61a05b 693
HannesTschofenig 0:796d0f61a05b 694 /*
HannesTschofenig 0:796d0f61a05b 695 * shift by count / limb_size
HannesTschofenig 0:796d0f61a05b 696 */
HannesTschofenig 0:796d0f61a05b 697 if( v0 > 0 )
HannesTschofenig 0:796d0f61a05b 698 {
HannesTschofenig 0:796d0f61a05b 699 for( i = X->n; i > v0; i-- )
HannesTschofenig 0:796d0f61a05b 700 X->p[i - 1] = X->p[i - v0 - 1];
HannesTschofenig 0:796d0f61a05b 701
HannesTschofenig 0:796d0f61a05b 702 for( ; i > 0; i-- )
HannesTschofenig 0:796d0f61a05b 703 X->p[i - 1] = 0;
HannesTschofenig 0:796d0f61a05b 704 }
HannesTschofenig 0:796d0f61a05b 705
HannesTschofenig 0:796d0f61a05b 706 /*
HannesTschofenig 0:796d0f61a05b 707 * shift by count % limb_size
HannesTschofenig 0:796d0f61a05b 708 */
HannesTschofenig 0:796d0f61a05b 709 if( t1 > 0 )
HannesTschofenig 0:796d0f61a05b 710 {
HannesTschofenig 0:796d0f61a05b 711 for( i = v0; i < X->n; i++ )
HannesTschofenig 0:796d0f61a05b 712 {
HannesTschofenig 0:796d0f61a05b 713 r1 = X->p[i] >> (biL - t1);
HannesTschofenig 0:796d0f61a05b 714 X->p[i] <<= t1;
HannesTschofenig 0:796d0f61a05b 715 X->p[i] |= r0;
HannesTschofenig 0:796d0f61a05b 716 r0 = r1;
HannesTschofenig 0:796d0f61a05b 717 }
HannesTschofenig 0:796d0f61a05b 718 }
HannesTschofenig 0:796d0f61a05b 719
HannesTschofenig 0:796d0f61a05b 720 cleanup:
HannesTschofenig 0:796d0f61a05b 721
HannesTschofenig 0:796d0f61a05b 722 return( ret );
HannesTschofenig 0:796d0f61a05b 723 }
HannesTschofenig 0:796d0f61a05b 724
HannesTschofenig 0:796d0f61a05b 725 /*
HannesTschofenig 0:796d0f61a05b 726 * Right-shift: X >>= count
HannesTschofenig 0:796d0f61a05b 727 */
HannesTschofenig 0:796d0f61a05b 728 int mpi_shift_r( mpi *X, size_t count )
HannesTschofenig 0:796d0f61a05b 729 {
HannesTschofenig 0:796d0f61a05b 730 size_t i, v0, v1;
HannesTschofenig 0:796d0f61a05b 731 t_uint r0 = 0, r1;
HannesTschofenig 0:796d0f61a05b 732
HannesTschofenig 0:796d0f61a05b 733 v0 = count / biL;
HannesTschofenig 0:796d0f61a05b 734 v1 = count & (biL - 1);
HannesTschofenig 0:796d0f61a05b 735
HannesTschofenig 0:796d0f61a05b 736 if( v0 > X->n || ( v0 == X->n && v1 > 0 ) )
HannesTschofenig 0:796d0f61a05b 737 return mpi_lset( X, 0 );
HannesTschofenig 0:796d0f61a05b 738
HannesTschofenig 0:796d0f61a05b 739 /*
HannesTschofenig 0:796d0f61a05b 740 * shift by count / limb_size
HannesTschofenig 0:796d0f61a05b 741 */
HannesTschofenig 0:796d0f61a05b 742 if( v0 > 0 )
HannesTschofenig 0:796d0f61a05b 743 {
HannesTschofenig 0:796d0f61a05b 744 for( i = 0; i < X->n - v0; i++ )
HannesTschofenig 0:796d0f61a05b 745 X->p[i] = X->p[i + v0];
HannesTschofenig 0:796d0f61a05b 746
HannesTschofenig 0:796d0f61a05b 747 for( ; i < X->n; i++ )
HannesTschofenig 0:796d0f61a05b 748 X->p[i] = 0;
HannesTschofenig 0:796d0f61a05b 749 }
HannesTschofenig 0:796d0f61a05b 750
HannesTschofenig 0:796d0f61a05b 751 /*
HannesTschofenig 0:796d0f61a05b 752 * shift by count % limb_size
HannesTschofenig 0:796d0f61a05b 753 */
HannesTschofenig 0:796d0f61a05b 754 if( v1 > 0 )
HannesTschofenig 0:796d0f61a05b 755 {
HannesTschofenig 0:796d0f61a05b 756 for( i = X->n; i > 0; i-- )
HannesTschofenig 0:796d0f61a05b 757 {
HannesTschofenig 0:796d0f61a05b 758 r1 = X->p[i - 1] << (biL - v1);
HannesTschofenig 0:796d0f61a05b 759 X->p[i - 1] >>= v1;
HannesTschofenig 0:796d0f61a05b 760 X->p[i - 1] |= r0;
HannesTschofenig 0:796d0f61a05b 761 r0 = r1;
HannesTschofenig 0:796d0f61a05b 762 }
HannesTschofenig 0:796d0f61a05b 763 }
HannesTschofenig 0:796d0f61a05b 764
HannesTschofenig 0:796d0f61a05b 765 return( 0 );
HannesTschofenig 0:796d0f61a05b 766 }
HannesTschofenig 0:796d0f61a05b 767
HannesTschofenig 0:796d0f61a05b 768 /*
HannesTschofenig 0:796d0f61a05b 769 * Compare unsigned values
HannesTschofenig 0:796d0f61a05b 770 */
HannesTschofenig 0:796d0f61a05b 771 int mpi_cmp_abs( const mpi *X, const mpi *Y )
HannesTschofenig 0:796d0f61a05b 772 {
HannesTschofenig 0:796d0f61a05b 773 size_t i, j;
HannesTschofenig 0:796d0f61a05b 774
HannesTschofenig 0:796d0f61a05b 775 for( i = X->n; i > 0; i-- )
HannesTschofenig 0:796d0f61a05b 776 if( X->p[i - 1] != 0 )
HannesTschofenig 0:796d0f61a05b 777 break;
HannesTschofenig 0:796d0f61a05b 778
HannesTschofenig 0:796d0f61a05b 779 for( j = Y->n; j > 0; j-- )
HannesTschofenig 0:796d0f61a05b 780 if( Y->p[j - 1] != 0 )
HannesTschofenig 0:796d0f61a05b 781 break;
HannesTschofenig 0:796d0f61a05b 782
HannesTschofenig 0:796d0f61a05b 783 if( i == 0 && j == 0 )
HannesTschofenig 0:796d0f61a05b 784 return( 0 );
HannesTschofenig 0:796d0f61a05b 785
HannesTschofenig 0:796d0f61a05b 786 if( i > j ) return( 1 );
HannesTschofenig 0:796d0f61a05b 787 if( j > i ) return( -1 );
HannesTschofenig 0:796d0f61a05b 788
HannesTschofenig 0:796d0f61a05b 789 for( ; i > 0; i-- )
HannesTschofenig 0:796d0f61a05b 790 {
HannesTschofenig 0:796d0f61a05b 791 if( X->p[i - 1] > Y->p[i - 1] ) return( 1 );
HannesTschofenig 0:796d0f61a05b 792 if( X->p[i - 1] < Y->p[i - 1] ) return( -1 );
HannesTschofenig 0:796d0f61a05b 793 }
HannesTschofenig 0:796d0f61a05b 794
HannesTschofenig 0:796d0f61a05b 795 return( 0 );
HannesTschofenig 0:796d0f61a05b 796 }
HannesTschofenig 0:796d0f61a05b 797
HannesTschofenig 0:796d0f61a05b 798 /*
HannesTschofenig 0:796d0f61a05b 799 * Compare signed values
HannesTschofenig 0:796d0f61a05b 800 */
HannesTschofenig 0:796d0f61a05b 801 int mpi_cmp_mpi( const mpi *X, const mpi *Y )
HannesTschofenig 0:796d0f61a05b 802 {
HannesTschofenig 0:796d0f61a05b 803 size_t i, j;
HannesTschofenig 0:796d0f61a05b 804
HannesTschofenig 0:796d0f61a05b 805 for( i = X->n; i > 0; i-- )
HannesTschofenig 0:796d0f61a05b 806 if( X->p[i - 1] != 0 )
HannesTschofenig 0:796d0f61a05b 807 break;
HannesTschofenig 0:796d0f61a05b 808
HannesTschofenig 0:796d0f61a05b 809 for( j = Y->n; j > 0; j-- )
HannesTschofenig 0:796d0f61a05b 810 if( Y->p[j - 1] != 0 )
HannesTschofenig 0:796d0f61a05b 811 break;
HannesTschofenig 0:796d0f61a05b 812
HannesTschofenig 0:796d0f61a05b 813 if( i == 0 && j == 0 )
HannesTschofenig 0:796d0f61a05b 814 return( 0 );
HannesTschofenig 0:796d0f61a05b 815
HannesTschofenig 0:796d0f61a05b 816 if( i > j ) return( X->s );
HannesTschofenig 0:796d0f61a05b 817 if( j > i ) return( -Y->s );
HannesTschofenig 0:796d0f61a05b 818
HannesTschofenig 0:796d0f61a05b 819 if( X->s > 0 && Y->s < 0 ) return( 1 );
HannesTschofenig 0:796d0f61a05b 820 if( Y->s > 0 && X->s < 0 ) return( -1 );
HannesTschofenig 0:796d0f61a05b 821
HannesTschofenig 0:796d0f61a05b 822 for( ; i > 0; i-- )
HannesTschofenig 0:796d0f61a05b 823 {
HannesTschofenig 0:796d0f61a05b 824 if( X->p[i - 1] > Y->p[i - 1] ) return( X->s );
HannesTschofenig 0:796d0f61a05b 825 if( X->p[i - 1] < Y->p[i - 1] ) return( -X->s );
HannesTschofenig 0:796d0f61a05b 826 }
HannesTschofenig 0:796d0f61a05b 827
HannesTschofenig 0:796d0f61a05b 828 return( 0 );
HannesTschofenig 0:796d0f61a05b 829 }
HannesTschofenig 0:796d0f61a05b 830
HannesTschofenig 0:796d0f61a05b 831 /*
HannesTschofenig 0:796d0f61a05b 832 * Compare signed values
HannesTschofenig 0:796d0f61a05b 833 */
HannesTschofenig 0:796d0f61a05b 834 int mpi_cmp_int( const mpi *X, t_sint z )
HannesTschofenig 0:796d0f61a05b 835 {
HannesTschofenig 0:796d0f61a05b 836 mpi Y;
HannesTschofenig 0:796d0f61a05b 837 t_uint p[1];
HannesTschofenig 0:796d0f61a05b 838
HannesTschofenig 0:796d0f61a05b 839 *p = ( z < 0 ) ? -z : z;
HannesTschofenig 0:796d0f61a05b 840 Y.s = ( z < 0 ) ? -1 : 1;
HannesTschofenig 0:796d0f61a05b 841 Y.n = 1;
HannesTschofenig 0:796d0f61a05b 842 Y.p = p;
HannesTschofenig 0:796d0f61a05b 843
HannesTschofenig 0:796d0f61a05b 844 return( mpi_cmp_mpi( X, &Y ) );
HannesTschofenig 0:796d0f61a05b 845 }
HannesTschofenig 0:796d0f61a05b 846
HannesTschofenig 0:796d0f61a05b 847 /*
HannesTschofenig 0:796d0f61a05b 848 * Unsigned addition: X = |A| + |B| (HAC 14.7)
HannesTschofenig 0:796d0f61a05b 849 */
HannesTschofenig 0:796d0f61a05b 850 int mpi_add_abs( mpi *X, const mpi *A, const mpi *B )
HannesTschofenig 0:796d0f61a05b 851 {
HannesTschofenig 0:796d0f61a05b 852 int ret;
HannesTschofenig 0:796d0f61a05b 853 size_t i, j;
HannesTschofenig 0:796d0f61a05b 854 t_uint *o, *p, c;
HannesTschofenig 0:796d0f61a05b 855
HannesTschofenig 0:796d0f61a05b 856 if( X == B )
HannesTschofenig 0:796d0f61a05b 857 {
HannesTschofenig 0:796d0f61a05b 858 const mpi *T = A; A = X; B = T;
HannesTschofenig 0:796d0f61a05b 859 }
HannesTschofenig 0:796d0f61a05b 860
HannesTschofenig 0:796d0f61a05b 861 if( X != A )
HannesTschofenig 0:796d0f61a05b 862 MPI_CHK( mpi_copy( X, A ) );
HannesTschofenig 0:796d0f61a05b 863
HannesTschofenig 0:796d0f61a05b 864 /*
HannesTschofenig 0:796d0f61a05b 865 * X should always be positive as a result of unsigned additions.
HannesTschofenig 0:796d0f61a05b 866 */
HannesTschofenig 0:796d0f61a05b 867 X->s = 1;
HannesTschofenig 0:796d0f61a05b 868
HannesTschofenig 0:796d0f61a05b 869 for( j = B->n; j > 0; j-- )
HannesTschofenig 0:796d0f61a05b 870 if( B->p[j - 1] != 0 )
HannesTschofenig 0:796d0f61a05b 871 break;
HannesTschofenig 0:796d0f61a05b 872
HannesTschofenig 0:796d0f61a05b 873 MPI_CHK( mpi_grow( X, j ) );
HannesTschofenig 0:796d0f61a05b 874
HannesTschofenig 0:796d0f61a05b 875 o = B->p; p = X->p; c = 0;
HannesTschofenig 0:796d0f61a05b 876
HannesTschofenig 0:796d0f61a05b 877 for( i = 0; i < j; i++, o++, p++ )
HannesTschofenig 0:796d0f61a05b 878 {
HannesTschofenig 0:796d0f61a05b 879 *p += c; c = ( *p < c );
HannesTschofenig 0:796d0f61a05b 880 *p += *o; c += ( *p < *o );
HannesTschofenig 0:796d0f61a05b 881 }
HannesTschofenig 0:796d0f61a05b 882
HannesTschofenig 0:796d0f61a05b 883 while( c != 0 )
HannesTschofenig 0:796d0f61a05b 884 {
HannesTschofenig 0:796d0f61a05b 885 if( i >= X->n )
HannesTschofenig 0:796d0f61a05b 886 {
HannesTschofenig 0:796d0f61a05b 887 MPI_CHK( mpi_grow( X, i + 1 ) );
HannesTschofenig 0:796d0f61a05b 888 p = X->p + i;
HannesTschofenig 0:796d0f61a05b 889 }
HannesTschofenig 0:796d0f61a05b 890
HannesTschofenig 0:796d0f61a05b 891 *p += c; c = ( *p < c ); i++; p++;
HannesTschofenig 0:796d0f61a05b 892 }
HannesTschofenig 0:796d0f61a05b 893
HannesTschofenig 0:796d0f61a05b 894 cleanup:
HannesTschofenig 0:796d0f61a05b 895
HannesTschofenig 0:796d0f61a05b 896 return( ret );
HannesTschofenig 0:796d0f61a05b 897 }
HannesTschofenig 0:796d0f61a05b 898
HannesTschofenig 0:796d0f61a05b 899 /*
HannesTschofenig 0:796d0f61a05b 900 * Helper for mpi subtraction
HannesTschofenig 0:796d0f61a05b 901 */
HannesTschofenig 0:796d0f61a05b 902 static void mpi_sub_hlp( size_t n, t_uint *s, t_uint *d )
HannesTschofenig 0:796d0f61a05b 903 {
HannesTschofenig 0:796d0f61a05b 904 size_t i;
HannesTschofenig 0:796d0f61a05b 905 t_uint c, z;
HannesTschofenig 0:796d0f61a05b 906
HannesTschofenig 0:796d0f61a05b 907 for( i = c = 0; i < n; i++, s++, d++ )
HannesTschofenig 0:796d0f61a05b 908 {
HannesTschofenig 0:796d0f61a05b 909 z = ( *d < c ); *d -= c;
HannesTschofenig 0:796d0f61a05b 910 c = ( *d < *s ) + z; *d -= *s;
HannesTschofenig 0:796d0f61a05b 911 }
HannesTschofenig 0:796d0f61a05b 912
HannesTschofenig 0:796d0f61a05b 913 while( c != 0 )
HannesTschofenig 0:796d0f61a05b 914 {
HannesTschofenig 0:796d0f61a05b 915 z = ( *d < c ); *d -= c;
HannesTschofenig 0:796d0f61a05b 916 c = z; i++; d++;
HannesTschofenig 0:796d0f61a05b 917 }
HannesTschofenig 0:796d0f61a05b 918 }
HannesTschofenig 0:796d0f61a05b 919
HannesTschofenig 0:796d0f61a05b 920 /*
HannesTschofenig 0:796d0f61a05b 921 * Unsigned subtraction: X = |A| - |B| (HAC 14.9)
HannesTschofenig 0:796d0f61a05b 922 */
HannesTschofenig 0:796d0f61a05b 923 int mpi_sub_abs( mpi *X, const mpi *A, const mpi *B )
HannesTschofenig 0:796d0f61a05b 924 {
HannesTschofenig 0:796d0f61a05b 925 mpi TB;
HannesTschofenig 0:796d0f61a05b 926 int ret;
HannesTschofenig 0:796d0f61a05b 927 size_t n;
HannesTschofenig 0:796d0f61a05b 928
HannesTschofenig 0:796d0f61a05b 929 if( mpi_cmp_abs( A, B ) < 0 )
HannesTschofenig 0:796d0f61a05b 930 return( POLARSSL_ERR_MPI_NEGATIVE_VALUE );
HannesTschofenig 0:796d0f61a05b 931
HannesTschofenig 0:796d0f61a05b 932 mpi_init( &TB );
HannesTschofenig 0:796d0f61a05b 933
HannesTschofenig 0:796d0f61a05b 934 if( X == B )
HannesTschofenig 0:796d0f61a05b 935 {
HannesTschofenig 0:796d0f61a05b 936 MPI_CHK( mpi_copy( &TB, B ) );
HannesTschofenig 0:796d0f61a05b 937 B = &TB;
HannesTschofenig 0:796d0f61a05b 938 }
HannesTschofenig 0:796d0f61a05b 939
HannesTschofenig 0:796d0f61a05b 940 if( X != A )
HannesTschofenig 0:796d0f61a05b 941 MPI_CHK( mpi_copy( X, A ) );
HannesTschofenig 0:796d0f61a05b 942
HannesTschofenig 0:796d0f61a05b 943 /*
HannesTschofenig 0:796d0f61a05b 944 * X should always be positive as a result of unsigned subtractions.
HannesTschofenig 0:796d0f61a05b 945 */
HannesTschofenig 0:796d0f61a05b 946 X->s = 1;
HannesTschofenig 0:796d0f61a05b 947
HannesTschofenig 0:796d0f61a05b 948 ret = 0;
HannesTschofenig 0:796d0f61a05b 949
HannesTschofenig 0:796d0f61a05b 950 for( n = B->n; n > 0; n-- )
HannesTschofenig 0:796d0f61a05b 951 if( B->p[n - 1] != 0 )
HannesTschofenig 0:796d0f61a05b 952 break;
HannesTschofenig 0:796d0f61a05b 953
HannesTschofenig 0:796d0f61a05b 954 mpi_sub_hlp( n, B->p, X->p );
HannesTschofenig 0:796d0f61a05b 955
HannesTschofenig 0:796d0f61a05b 956 cleanup:
HannesTschofenig 0:796d0f61a05b 957
HannesTschofenig 0:796d0f61a05b 958 mpi_free( &TB );
HannesTschofenig 0:796d0f61a05b 959
HannesTschofenig 0:796d0f61a05b 960 return( ret );
HannesTschofenig 0:796d0f61a05b 961 }
HannesTschofenig 0:796d0f61a05b 962
HannesTschofenig 0:796d0f61a05b 963 /*
HannesTschofenig 0:796d0f61a05b 964 * Signed addition: X = A + B
HannesTschofenig 0:796d0f61a05b 965 */
HannesTschofenig 0:796d0f61a05b 966 int mpi_add_mpi( mpi *X, const mpi *A, const mpi *B )
HannesTschofenig 0:796d0f61a05b 967 {
HannesTschofenig 0:796d0f61a05b 968 int ret, s = A->s;
HannesTschofenig 0:796d0f61a05b 969
HannesTschofenig 0:796d0f61a05b 970 if( A->s * B->s < 0 )
HannesTschofenig 0:796d0f61a05b 971 {
HannesTschofenig 0:796d0f61a05b 972 if( mpi_cmp_abs( A, B ) >= 0 )
HannesTschofenig 0:796d0f61a05b 973 {
HannesTschofenig 0:796d0f61a05b 974 MPI_CHK( mpi_sub_abs( X, A, B ) );
HannesTschofenig 0:796d0f61a05b 975 X->s = s;
HannesTschofenig 0:796d0f61a05b 976 }
HannesTschofenig 0:796d0f61a05b 977 else
HannesTschofenig 0:796d0f61a05b 978 {
HannesTschofenig 0:796d0f61a05b 979 MPI_CHK( mpi_sub_abs( X, B, A ) );
HannesTschofenig 0:796d0f61a05b 980 X->s = -s;
HannesTschofenig 0:796d0f61a05b 981 }
HannesTschofenig 0:796d0f61a05b 982 }
HannesTschofenig 0:796d0f61a05b 983 else
HannesTschofenig 0:796d0f61a05b 984 {
HannesTschofenig 0:796d0f61a05b 985 MPI_CHK( mpi_add_abs( X, A, B ) );
HannesTschofenig 0:796d0f61a05b 986 X->s = s;
HannesTschofenig 0:796d0f61a05b 987 }
HannesTschofenig 0:796d0f61a05b 988
HannesTschofenig 0:796d0f61a05b 989 cleanup:
HannesTschofenig 0:796d0f61a05b 990
HannesTschofenig 0:796d0f61a05b 991 return( ret );
HannesTschofenig 0:796d0f61a05b 992 }
HannesTschofenig 0:796d0f61a05b 993
HannesTschofenig 0:796d0f61a05b 994 /*
HannesTschofenig 0:796d0f61a05b 995 * Signed subtraction: X = A - B
HannesTschofenig 0:796d0f61a05b 996 */
HannesTschofenig 0:796d0f61a05b 997 int mpi_sub_mpi( mpi *X, const mpi *A, const mpi *B )
HannesTschofenig 0:796d0f61a05b 998 {
HannesTschofenig 0:796d0f61a05b 999 int ret, s = A->s;
HannesTschofenig 0:796d0f61a05b 1000
HannesTschofenig 0:796d0f61a05b 1001 if( A->s * B->s > 0 )
HannesTschofenig 0:796d0f61a05b 1002 {
HannesTschofenig 0:796d0f61a05b 1003 if( mpi_cmp_abs( A, B ) >= 0 )
HannesTschofenig 0:796d0f61a05b 1004 {
HannesTschofenig 0:796d0f61a05b 1005 MPI_CHK( mpi_sub_abs( X, A, B ) );
HannesTschofenig 0:796d0f61a05b 1006 X->s = s;
HannesTschofenig 0:796d0f61a05b 1007 }
HannesTschofenig 0:796d0f61a05b 1008 else
HannesTschofenig 0:796d0f61a05b 1009 {
HannesTschofenig 0:796d0f61a05b 1010 MPI_CHK( mpi_sub_abs( X, B, A ) );
HannesTschofenig 0:796d0f61a05b 1011 X->s = -s;
HannesTschofenig 0:796d0f61a05b 1012 }
HannesTschofenig 0:796d0f61a05b 1013 }
HannesTschofenig 0:796d0f61a05b 1014 else
HannesTschofenig 0:796d0f61a05b 1015 {
HannesTschofenig 0:796d0f61a05b 1016 MPI_CHK( mpi_add_abs( X, A, B ) );
HannesTschofenig 0:796d0f61a05b 1017 X->s = s;
HannesTschofenig 0:796d0f61a05b 1018 }
HannesTschofenig 0:796d0f61a05b 1019
HannesTschofenig 0:796d0f61a05b 1020 cleanup:
HannesTschofenig 0:796d0f61a05b 1021
HannesTschofenig 0:796d0f61a05b 1022 return( ret );
HannesTschofenig 0:796d0f61a05b 1023 }
HannesTschofenig 0:796d0f61a05b 1024
HannesTschofenig 0:796d0f61a05b 1025 /*
HannesTschofenig 0:796d0f61a05b 1026 * Signed addition: X = A + b
HannesTschofenig 0:796d0f61a05b 1027 */
HannesTschofenig 0:796d0f61a05b 1028 int mpi_add_int( mpi *X, const mpi *A, t_sint b )
HannesTschofenig 0:796d0f61a05b 1029 {
HannesTschofenig 0:796d0f61a05b 1030 mpi _B;
HannesTschofenig 0:796d0f61a05b 1031 t_uint p[1];
HannesTschofenig 0:796d0f61a05b 1032
HannesTschofenig 0:796d0f61a05b 1033 p[0] = ( b < 0 ) ? -b : b;
HannesTschofenig 0:796d0f61a05b 1034 _B.s = ( b < 0 ) ? -1 : 1;
HannesTschofenig 0:796d0f61a05b 1035 _B.n = 1;
HannesTschofenig 0:796d0f61a05b 1036 _B.p = p;
HannesTschofenig 0:796d0f61a05b 1037
HannesTschofenig 0:796d0f61a05b 1038 return( mpi_add_mpi( X, A, &_B ) );
HannesTschofenig 0:796d0f61a05b 1039 }
HannesTschofenig 0:796d0f61a05b 1040
HannesTschofenig 0:796d0f61a05b 1041 /*
HannesTschofenig 0:796d0f61a05b 1042 * Signed subtraction: X = A - b
HannesTschofenig 0:796d0f61a05b 1043 */
HannesTschofenig 0:796d0f61a05b 1044 int mpi_sub_int( mpi *X, const mpi *A, t_sint b )
HannesTschofenig 0:796d0f61a05b 1045 {
HannesTschofenig 0:796d0f61a05b 1046 mpi _B;
HannesTschofenig 0:796d0f61a05b 1047 t_uint p[1];
HannesTschofenig 0:796d0f61a05b 1048
HannesTschofenig 0:796d0f61a05b 1049 p[0] = ( b < 0 ) ? -b : b;
HannesTschofenig 0:796d0f61a05b 1050 _B.s = ( b < 0 ) ? -1 : 1;
HannesTschofenig 0:796d0f61a05b 1051 _B.n = 1;
HannesTschofenig 0:796d0f61a05b 1052 _B.p = p;
HannesTschofenig 0:796d0f61a05b 1053
HannesTschofenig 0:796d0f61a05b 1054 return( mpi_sub_mpi( X, A, &_B ) );
HannesTschofenig 0:796d0f61a05b 1055 }
HannesTschofenig 0:796d0f61a05b 1056
HannesTschofenig 0:796d0f61a05b 1057 /*
HannesTschofenig 0:796d0f61a05b 1058 * Helper for mpi multiplication
HannesTschofenig 0:796d0f61a05b 1059 */
HannesTschofenig 0:796d0f61a05b 1060 static
HannesTschofenig 0:796d0f61a05b 1061 #if defined(__APPLE__) && defined(__arm__)
HannesTschofenig 0:796d0f61a05b 1062 /*
HannesTschofenig 0:796d0f61a05b 1063 * Apple LLVM version 4.2 (clang-425.0.24) (based on LLVM 3.2svn)
HannesTschofenig 0:796d0f61a05b 1064 * appears to need this to prevent bad ARM code generation at -O3.
HannesTschofenig 0:796d0f61a05b 1065 */
HannesTschofenig 0:796d0f61a05b 1066 __attribute__ ((noinline))
HannesTschofenig 0:796d0f61a05b 1067 #endif
HannesTschofenig 0:796d0f61a05b 1068 void mpi_mul_hlp( size_t i, t_uint *s, t_uint *d, t_uint b )
HannesTschofenig 0:796d0f61a05b 1069 {
HannesTschofenig 0:796d0f61a05b 1070 t_uint c = 0, t = 0;
HannesTschofenig 0:796d0f61a05b 1071
HannesTschofenig 0:796d0f61a05b 1072 #if defined(MULADDC_HUIT)
HannesTschofenig 0:796d0f61a05b 1073 for( ; i >= 8; i -= 8 )
HannesTschofenig 0:796d0f61a05b 1074 {
HannesTschofenig 0:796d0f61a05b 1075 MULADDC_INIT
HannesTschofenig 0:796d0f61a05b 1076 MULADDC_HUIT
HannesTschofenig 0:796d0f61a05b 1077 MULADDC_STOP
HannesTschofenig 0:796d0f61a05b 1078 }
HannesTschofenig 0:796d0f61a05b 1079
HannesTschofenig 0:796d0f61a05b 1080 for( ; i > 0; i-- )
HannesTschofenig 0:796d0f61a05b 1081 {
HannesTschofenig 0:796d0f61a05b 1082 MULADDC_INIT
HannesTschofenig 0:796d0f61a05b 1083 MULADDC_CORE
HannesTschofenig 0:796d0f61a05b 1084 MULADDC_STOP
HannesTschofenig 0:796d0f61a05b 1085 }
HannesTschofenig 0:796d0f61a05b 1086 #else /* MULADDC_HUIT */
HannesTschofenig 0:796d0f61a05b 1087 for( ; i >= 16; i -= 16 )
HannesTschofenig 0:796d0f61a05b 1088 {
HannesTschofenig 0:796d0f61a05b 1089 MULADDC_INIT
HannesTschofenig 0:796d0f61a05b 1090 MULADDC_CORE MULADDC_CORE
HannesTschofenig 0:796d0f61a05b 1091 MULADDC_CORE MULADDC_CORE
HannesTschofenig 0:796d0f61a05b 1092 MULADDC_CORE MULADDC_CORE
HannesTschofenig 0:796d0f61a05b 1093 MULADDC_CORE MULADDC_CORE
HannesTschofenig 0:796d0f61a05b 1094
HannesTschofenig 0:796d0f61a05b 1095 MULADDC_CORE MULADDC_CORE
HannesTschofenig 0:796d0f61a05b 1096 MULADDC_CORE MULADDC_CORE
HannesTschofenig 0:796d0f61a05b 1097 MULADDC_CORE MULADDC_CORE
HannesTschofenig 0:796d0f61a05b 1098 MULADDC_CORE MULADDC_CORE
HannesTschofenig 0:796d0f61a05b 1099 MULADDC_STOP
HannesTschofenig 0:796d0f61a05b 1100 }
HannesTschofenig 0:796d0f61a05b 1101
HannesTschofenig 0:796d0f61a05b 1102 for( ; i >= 8; i -= 8 )
HannesTschofenig 0:796d0f61a05b 1103 {
HannesTschofenig 0:796d0f61a05b 1104 MULADDC_INIT
HannesTschofenig 0:796d0f61a05b 1105 MULADDC_CORE MULADDC_CORE
HannesTschofenig 0:796d0f61a05b 1106 MULADDC_CORE MULADDC_CORE
HannesTschofenig 0:796d0f61a05b 1107
HannesTschofenig 0:796d0f61a05b 1108 MULADDC_CORE MULADDC_CORE
HannesTschofenig 0:796d0f61a05b 1109 MULADDC_CORE MULADDC_CORE
HannesTschofenig 0:796d0f61a05b 1110 MULADDC_STOP
HannesTschofenig 0:796d0f61a05b 1111 }
HannesTschofenig 0:796d0f61a05b 1112
HannesTschofenig 0:796d0f61a05b 1113 for( ; i > 0; i-- )
HannesTschofenig 0:796d0f61a05b 1114 {
HannesTschofenig 0:796d0f61a05b 1115 MULADDC_INIT
HannesTschofenig 0:796d0f61a05b 1116 MULADDC_CORE
HannesTschofenig 0:796d0f61a05b 1117 MULADDC_STOP
HannesTschofenig 0:796d0f61a05b 1118 }
HannesTschofenig 0:796d0f61a05b 1119 #endif /* MULADDC_HUIT */
HannesTschofenig 0:796d0f61a05b 1120
HannesTschofenig 0:796d0f61a05b 1121 t++;
HannesTschofenig 0:796d0f61a05b 1122
HannesTschofenig 0:796d0f61a05b 1123 do {
HannesTschofenig 0:796d0f61a05b 1124 *d += c; c = ( *d < c ); d++;
HannesTschofenig 0:796d0f61a05b 1125 }
HannesTschofenig 0:796d0f61a05b 1126 while( c != 0 );
HannesTschofenig 0:796d0f61a05b 1127 }
HannesTschofenig 0:796d0f61a05b 1128
HannesTschofenig 0:796d0f61a05b 1129 /*
HannesTschofenig 0:796d0f61a05b 1130 * Baseline multiplication: X = A * B (HAC 14.12)
HannesTschofenig 0:796d0f61a05b 1131 */
HannesTschofenig 0:796d0f61a05b 1132 int mpi_mul_mpi( mpi *X, const mpi *A, const mpi *B )
HannesTschofenig 0:796d0f61a05b 1133 {
HannesTschofenig 0:796d0f61a05b 1134 int ret;
HannesTschofenig 0:796d0f61a05b 1135 size_t i, j;
HannesTschofenig 0:796d0f61a05b 1136 mpi TA, TB;
HannesTschofenig 0:796d0f61a05b 1137
HannesTschofenig 0:796d0f61a05b 1138 mpi_init( &TA ); mpi_init( &TB );
HannesTschofenig 0:796d0f61a05b 1139
HannesTschofenig 0:796d0f61a05b 1140 if( X == A ) { MPI_CHK( mpi_copy( &TA, A ) ); A = &TA; }
HannesTschofenig 0:796d0f61a05b 1141 if( X == B ) { MPI_CHK( mpi_copy( &TB, B ) ); B = &TB; }
HannesTschofenig 0:796d0f61a05b 1142
HannesTschofenig 0:796d0f61a05b 1143 for( i = A->n; i > 0; i-- )
HannesTschofenig 0:796d0f61a05b 1144 if( A->p[i - 1] != 0 )
HannesTschofenig 0:796d0f61a05b 1145 break;
HannesTschofenig 0:796d0f61a05b 1146
HannesTschofenig 0:796d0f61a05b 1147 for( j = B->n; j > 0; j-- )
HannesTschofenig 0:796d0f61a05b 1148 if( B->p[j - 1] != 0 )
HannesTschofenig 0:796d0f61a05b 1149 break;
HannesTschofenig 0:796d0f61a05b 1150
HannesTschofenig 0:796d0f61a05b 1151 MPI_CHK( mpi_grow( X, i + j ) );
HannesTschofenig 0:796d0f61a05b 1152 MPI_CHK( mpi_lset( X, 0 ) );
HannesTschofenig 0:796d0f61a05b 1153
HannesTschofenig 0:796d0f61a05b 1154 for( i++; j > 0; j-- )
HannesTschofenig 0:796d0f61a05b 1155 mpi_mul_hlp( i - 1, A->p, X->p + j - 1, B->p[j - 1] );
HannesTschofenig 0:796d0f61a05b 1156
HannesTschofenig 0:796d0f61a05b 1157 X->s = A->s * B->s;
HannesTschofenig 0:796d0f61a05b 1158
HannesTschofenig 0:796d0f61a05b 1159 cleanup:
HannesTschofenig 0:796d0f61a05b 1160
HannesTschofenig 0:796d0f61a05b 1161 mpi_free( &TB ); mpi_free( &TA );
HannesTschofenig 0:796d0f61a05b 1162
HannesTschofenig 0:796d0f61a05b 1163 return( ret );
HannesTschofenig 0:796d0f61a05b 1164 }
HannesTschofenig 0:796d0f61a05b 1165
HannesTschofenig 0:796d0f61a05b 1166 /*
HannesTschofenig 0:796d0f61a05b 1167 * Baseline multiplication: X = A * b
HannesTschofenig 0:796d0f61a05b 1168 */
HannesTschofenig 0:796d0f61a05b 1169 int mpi_mul_int( mpi *X, const mpi *A, t_sint b )
HannesTschofenig 0:796d0f61a05b 1170 {
HannesTschofenig 0:796d0f61a05b 1171 mpi _B;
HannesTschofenig 0:796d0f61a05b 1172 t_uint p[1];
HannesTschofenig 0:796d0f61a05b 1173
HannesTschofenig 0:796d0f61a05b 1174 _B.s = 1;
HannesTschofenig 0:796d0f61a05b 1175 _B.n = 1;
HannesTschofenig 0:796d0f61a05b 1176 _B.p = p;
HannesTschofenig 0:796d0f61a05b 1177 p[0] = b;
HannesTschofenig 0:796d0f61a05b 1178
HannesTschofenig 0:796d0f61a05b 1179 return( mpi_mul_mpi( X, A, &_B ) );
HannesTschofenig 0:796d0f61a05b 1180 }
HannesTschofenig 0:796d0f61a05b 1181
HannesTschofenig 0:796d0f61a05b 1182 /*
HannesTschofenig 0:796d0f61a05b 1183 * Division by mpi: A = Q * B + R (HAC 14.20)
HannesTschofenig 0:796d0f61a05b 1184 */
HannesTschofenig 0:796d0f61a05b 1185 int mpi_div_mpi( mpi *Q, mpi *R, const mpi *A, const mpi *B )
HannesTschofenig 0:796d0f61a05b 1186 {
HannesTschofenig 0:796d0f61a05b 1187 int ret;
HannesTschofenig 0:796d0f61a05b 1188 size_t i, n, t, k;
HannesTschofenig 0:796d0f61a05b 1189 mpi X, Y, Z, T1, T2;
HannesTschofenig 0:796d0f61a05b 1190
HannesTschofenig 0:796d0f61a05b 1191 if( mpi_cmp_int( B, 0 ) == 0 )
HannesTschofenig 0:796d0f61a05b 1192 return( POLARSSL_ERR_MPI_DIVISION_BY_ZERO );
HannesTschofenig 0:796d0f61a05b 1193
HannesTschofenig 0:796d0f61a05b 1194 mpi_init( &X ); mpi_init( &Y ); mpi_init( &Z );
HannesTschofenig 0:796d0f61a05b 1195 mpi_init( &T1 ); mpi_init( &T2 );
HannesTschofenig 0:796d0f61a05b 1196
HannesTschofenig 0:796d0f61a05b 1197 if( mpi_cmp_abs( A, B ) < 0 )
HannesTschofenig 0:796d0f61a05b 1198 {
HannesTschofenig 0:796d0f61a05b 1199 if( Q != NULL ) MPI_CHK( mpi_lset( Q, 0 ) );
HannesTschofenig 0:796d0f61a05b 1200 if( R != NULL ) MPI_CHK( mpi_copy( R, A ) );
HannesTschofenig 0:796d0f61a05b 1201 return( 0 );
HannesTschofenig 0:796d0f61a05b 1202 }
HannesTschofenig 0:796d0f61a05b 1203
HannesTschofenig 0:796d0f61a05b 1204 MPI_CHK( mpi_copy( &X, A ) );
HannesTschofenig 0:796d0f61a05b 1205 MPI_CHK( mpi_copy( &Y, B ) );
HannesTschofenig 0:796d0f61a05b 1206 X.s = Y.s = 1;
HannesTschofenig 0:796d0f61a05b 1207
HannesTschofenig 0:796d0f61a05b 1208 MPI_CHK( mpi_grow( &Z, A->n + 2 ) );
HannesTschofenig 0:796d0f61a05b 1209 MPI_CHK( mpi_lset( &Z, 0 ) );
HannesTschofenig 0:796d0f61a05b 1210 MPI_CHK( mpi_grow( &T1, 2 ) );
HannesTschofenig 0:796d0f61a05b 1211 MPI_CHK( mpi_grow( &T2, 3 ) );
HannesTschofenig 0:796d0f61a05b 1212
HannesTschofenig 0:796d0f61a05b 1213 k = mpi_msb( &Y ) % biL;
HannesTschofenig 0:796d0f61a05b 1214 if( k < biL - 1 )
HannesTschofenig 0:796d0f61a05b 1215 {
HannesTschofenig 0:796d0f61a05b 1216 k = biL - 1 - k;
HannesTschofenig 0:796d0f61a05b 1217 MPI_CHK( mpi_shift_l( &X, k ) );
HannesTschofenig 0:796d0f61a05b 1218 MPI_CHK( mpi_shift_l( &Y, k ) );
HannesTschofenig 0:796d0f61a05b 1219 }
HannesTschofenig 0:796d0f61a05b 1220 else k = 0;
HannesTschofenig 0:796d0f61a05b 1221
HannesTschofenig 0:796d0f61a05b 1222 n = X.n - 1;
HannesTschofenig 0:796d0f61a05b 1223 t = Y.n - 1;
HannesTschofenig 0:796d0f61a05b 1224 MPI_CHK( mpi_shift_l( &Y, biL * (n - t) ) );
HannesTschofenig 0:796d0f61a05b 1225
HannesTschofenig 0:796d0f61a05b 1226 while( mpi_cmp_mpi( &X, &Y ) >= 0 )
HannesTschofenig 0:796d0f61a05b 1227 {
HannesTschofenig 0:796d0f61a05b 1228 Z.p[n - t]++;
HannesTschofenig 0:796d0f61a05b 1229 MPI_CHK( mpi_sub_mpi( &X, &X, &Y ) );
HannesTschofenig 0:796d0f61a05b 1230 }
HannesTschofenig 0:796d0f61a05b 1231 MPI_CHK( mpi_shift_r( &Y, biL * (n - t) ) );
HannesTschofenig 0:796d0f61a05b 1232
HannesTschofenig 0:796d0f61a05b 1233 for( i = n; i > t ; i-- )
HannesTschofenig 0:796d0f61a05b 1234 {
HannesTschofenig 0:796d0f61a05b 1235 if( X.p[i] >= Y.p[t] )
HannesTschofenig 0:796d0f61a05b 1236 Z.p[i - t - 1] = ~0;
HannesTschofenig 0:796d0f61a05b 1237 else
HannesTschofenig 0:796d0f61a05b 1238 {
HannesTschofenig 0:796d0f61a05b 1239 /*
HannesTschofenig 0:796d0f61a05b 1240 * The version of Clang shipped by Apple with Mavericks around
HannesTschofenig 0:796d0f61a05b 1241 * 2014-03 can't handle 128-bit division properly. Disable
HannesTschofenig 0:796d0f61a05b 1242 * 128-bits division for this version. Let's be optimistic and
HannesTschofenig 0:796d0f61a05b 1243 * assume it'll be fixed in the next minor version (next
HannesTschofenig 0:796d0f61a05b 1244 * patchlevel is probably a bit too optimistic).
HannesTschofenig 0:796d0f61a05b 1245 */
HannesTschofenig 0:796d0f61a05b 1246 #if defined(POLARSSL_HAVE_UDBL) && \
HannesTschofenig 0:796d0f61a05b 1247 ! ( defined(__x86_64__) && defined(__APPLE__) && \
HannesTschofenig 0:796d0f61a05b 1248 defined(__clang_major__) && __clang_major__ == 5 && \
HannesTschofenig 0:796d0f61a05b 1249 defined(__clang_minor__) && __clang_minor__ == 0 )
HannesTschofenig 0:796d0f61a05b 1250 t_udbl r;
HannesTschofenig 0:796d0f61a05b 1251
HannesTschofenig 0:796d0f61a05b 1252 r = (t_udbl) X.p[i] << biL;
HannesTschofenig 0:796d0f61a05b 1253 r |= (t_udbl) X.p[i - 1];
HannesTschofenig 0:796d0f61a05b 1254 r /= Y.p[t];
HannesTschofenig 0:796d0f61a05b 1255 if( r > ((t_udbl) 1 << biL) - 1)
HannesTschofenig 0:796d0f61a05b 1256 r = ((t_udbl) 1 << biL) - 1;
HannesTschofenig 0:796d0f61a05b 1257
HannesTschofenig 0:796d0f61a05b 1258 Z.p[i - t - 1] = (t_uint) r;
HannesTschofenig 0:796d0f61a05b 1259 #else
HannesTschofenig 0:796d0f61a05b 1260 /*
HannesTschofenig 0:796d0f61a05b 1261 * __udiv_qrnnd_c, from gmp/longlong.h
HannesTschofenig 0:796d0f61a05b 1262 */
HannesTschofenig 0:796d0f61a05b 1263 t_uint q0, q1, r0, r1;
HannesTschofenig 0:796d0f61a05b 1264 t_uint d0, d1, d, m;
HannesTschofenig 0:796d0f61a05b 1265
HannesTschofenig 0:796d0f61a05b 1266 d = Y.p[t];
HannesTschofenig 0:796d0f61a05b 1267 d0 = ( d << biH ) >> biH;
HannesTschofenig 0:796d0f61a05b 1268 d1 = ( d >> biH );
HannesTschofenig 0:796d0f61a05b 1269
HannesTschofenig 0:796d0f61a05b 1270 q1 = X.p[i] / d1;
HannesTschofenig 0:796d0f61a05b 1271 r1 = X.p[i] - d1 * q1;
HannesTschofenig 0:796d0f61a05b 1272 r1 <<= biH;
HannesTschofenig 0:796d0f61a05b 1273 r1 |= ( X.p[i - 1] >> biH );
HannesTschofenig 0:796d0f61a05b 1274
HannesTschofenig 0:796d0f61a05b 1275 m = q1 * d0;
HannesTschofenig 0:796d0f61a05b 1276 if( r1 < m )
HannesTschofenig 0:796d0f61a05b 1277 {
HannesTschofenig 0:796d0f61a05b 1278 q1--, r1 += d;
HannesTschofenig 0:796d0f61a05b 1279 while( r1 >= d && r1 < m )
HannesTschofenig 0:796d0f61a05b 1280 q1--, r1 += d;
HannesTschofenig 0:796d0f61a05b 1281 }
HannesTschofenig 0:796d0f61a05b 1282 r1 -= m;
HannesTschofenig 0:796d0f61a05b 1283
HannesTschofenig 0:796d0f61a05b 1284 q0 = r1 / d1;
HannesTschofenig 0:796d0f61a05b 1285 r0 = r1 - d1 * q0;
HannesTschofenig 0:796d0f61a05b 1286 r0 <<= biH;
HannesTschofenig 0:796d0f61a05b 1287 r0 |= ( X.p[i - 1] << biH ) >> biH;
HannesTschofenig 0:796d0f61a05b 1288
HannesTschofenig 0:796d0f61a05b 1289 m = q0 * d0;
HannesTschofenig 0:796d0f61a05b 1290 if( r0 < m )
HannesTschofenig 0:796d0f61a05b 1291 {
HannesTschofenig 0:796d0f61a05b 1292 q0--, r0 += d;
HannesTschofenig 0:796d0f61a05b 1293 while( r0 >= d && r0 < m )
HannesTschofenig 0:796d0f61a05b 1294 q0--, r0 += d;
HannesTschofenig 0:796d0f61a05b 1295 }
HannesTschofenig 0:796d0f61a05b 1296 r0 -= m;
HannesTschofenig 0:796d0f61a05b 1297
HannesTschofenig 0:796d0f61a05b 1298 Z.p[i - t - 1] = ( q1 << biH ) | q0;
HannesTschofenig 0:796d0f61a05b 1299 #endif
HannesTschofenig 0:796d0f61a05b 1300 }
HannesTschofenig 0:796d0f61a05b 1301
HannesTschofenig 0:796d0f61a05b 1302 Z.p[i - t - 1]++;
HannesTschofenig 0:796d0f61a05b 1303 do
HannesTschofenig 0:796d0f61a05b 1304 {
HannesTschofenig 0:796d0f61a05b 1305 Z.p[i - t - 1]--;
HannesTschofenig 0:796d0f61a05b 1306
HannesTschofenig 0:796d0f61a05b 1307 MPI_CHK( mpi_lset( &T1, 0 ) );
HannesTschofenig 0:796d0f61a05b 1308 T1.p[0] = (t < 1) ? 0 : Y.p[t - 1];
HannesTschofenig 0:796d0f61a05b 1309 T1.p[1] = Y.p[t];
HannesTschofenig 0:796d0f61a05b 1310 MPI_CHK( mpi_mul_int( &T1, &T1, Z.p[i - t - 1] ) );
HannesTschofenig 0:796d0f61a05b 1311
HannesTschofenig 0:796d0f61a05b 1312 MPI_CHK( mpi_lset( &T2, 0 ) );
HannesTschofenig 0:796d0f61a05b 1313 T2.p[0] = (i < 2) ? 0 : X.p[i - 2];
HannesTschofenig 0:796d0f61a05b 1314 T2.p[1] = (i < 1) ? 0 : X.p[i - 1];
HannesTschofenig 0:796d0f61a05b 1315 T2.p[2] = X.p[i];
HannesTschofenig 0:796d0f61a05b 1316 }
HannesTschofenig 0:796d0f61a05b 1317 while( mpi_cmp_mpi( &T1, &T2 ) > 0 );
HannesTschofenig 0:796d0f61a05b 1318
HannesTschofenig 0:796d0f61a05b 1319 MPI_CHK( mpi_mul_int( &T1, &Y, Z.p[i - t - 1] ) );
HannesTschofenig 0:796d0f61a05b 1320 MPI_CHK( mpi_shift_l( &T1, biL * (i - t - 1) ) );
HannesTschofenig 0:796d0f61a05b 1321 MPI_CHK( mpi_sub_mpi( &X, &X, &T1 ) );
HannesTschofenig 0:796d0f61a05b 1322
HannesTschofenig 0:796d0f61a05b 1323 if( mpi_cmp_int( &X, 0 ) < 0 )
HannesTschofenig 0:796d0f61a05b 1324 {
HannesTschofenig 0:796d0f61a05b 1325 MPI_CHK( mpi_copy( &T1, &Y ) );
HannesTschofenig 0:796d0f61a05b 1326 MPI_CHK( mpi_shift_l( &T1, biL * (i - t - 1) ) );
HannesTschofenig 0:796d0f61a05b 1327 MPI_CHK( mpi_add_mpi( &X, &X, &T1 ) );
HannesTschofenig 0:796d0f61a05b 1328 Z.p[i - t - 1]--;
HannesTschofenig 0:796d0f61a05b 1329 }
HannesTschofenig 0:796d0f61a05b 1330 }
HannesTschofenig 0:796d0f61a05b 1331
HannesTschofenig 0:796d0f61a05b 1332 if( Q != NULL )
HannesTschofenig 0:796d0f61a05b 1333 {
HannesTschofenig 0:796d0f61a05b 1334 MPI_CHK( mpi_copy( Q, &Z ) );
HannesTschofenig 0:796d0f61a05b 1335 Q->s = A->s * B->s;
HannesTschofenig 0:796d0f61a05b 1336 }
HannesTschofenig 0:796d0f61a05b 1337
HannesTschofenig 0:796d0f61a05b 1338 if( R != NULL )
HannesTschofenig 0:796d0f61a05b 1339 {
HannesTschofenig 0:796d0f61a05b 1340 MPI_CHK( mpi_shift_r( &X, k ) );
HannesTschofenig 0:796d0f61a05b 1341 X.s = A->s;
HannesTschofenig 0:796d0f61a05b 1342 MPI_CHK( mpi_copy( R, &X ) );
HannesTschofenig 0:796d0f61a05b 1343
HannesTschofenig 0:796d0f61a05b 1344 if( mpi_cmp_int( R, 0 ) == 0 )
HannesTschofenig 0:796d0f61a05b 1345 R->s = 1;
HannesTschofenig 0:796d0f61a05b 1346 }
HannesTschofenig 0:796d0f61a05b 1347
HannesTschofenig 0:796d0f61a05b 1348 cleanup:
HannesTschofenig 0:796d0f61a05b 1349
HannesTschofenig 0:796d0f61a05b 1350 mpi_free( &X ); mpi_free( &Y ); mpi_free( &Z );
HannesTschofenig 0:796d0f61a05b 1351 mpi_free( &T1 ); mpi_free( &T2 );
HannesTschofenig 0:796d0f61a05b 1352
HannesTschofenig 0:796d0f61a05b 1353 return( ret );
HannesTschofenig 0:796d0f61a05b 1354 }
HannesTschofenig 0:796d0f61a05b 1355
HannesTschofenig 0:796d0f61a05b 1356 /*
HannesTschofenig 0:796d0f61a05b 1357 * Division by int: A = Q * b + R
HannesTschofenig 0:796d0f61a05b 1358 */
HannesTschofenig 0:796d0f61a05b 1359 int mpi_div_int( mpi *Q, mpi *R, const mpi *A, t_sint b )
HannesTschofenig 0:796d0f61a05b 1360 {
HannesTschofenig 0:796d0f61a05b 1361 mpi _B;
HannesTschofenig 0:796d0f61a05b 1362 t_uint p[1];
HannesTschofenig 0:796d0f61a05b 1363
HannesTschofenig 0:796d0f61a05b 1364 p[0] = ( b < 0 ) ? -b : b;
HannesTschofenig 0:796d0f61a05b 1365 _B.s = ( b < 0 ) ? -1 : 1;
HannesTschofenig 0:796d0f61a05b 1366 _B.n = 1;
HannesTschofenig 0:796d0f61a05b 1367 _B.p = p;
HannesTschofenig 0:796d0f61a05b 1368
HannesTschofenig 0:796d0f61a05b 1369 return( mpi_div_mpi( Q, R, A, &_B ) );
HannesTschofenig 0:796d0f61a05b 1370 }
HannesTschofenig 0:796d0f61a05b 1371
HannesTschofenig 0:796d0f61a05b 1372 /*
HannesTschofenig 0:796d0f61a05b 1373 * Modulo: R = A mod B
HannesTschofenig 0:796d0f61a05b 1374 */
HannesTschofenig 0:796d0f61a05b 1375 int mpi_mod_mpi( mpi *R, const mpi *A, const mpi *B )
HannesTschofenig 0:796d0f61a05b 1376 {
HannesTschofenig 0:796d0f61a05b 1377 int ret;
HannesTschofenig 0:796d0f61a05b 1378
HannesTschofenig 0:796d0f61a05b 1379 if( mpi_cmp_int( B, 0 ) < 0 )
HannesTschofenig 0:796d0f61a05b 1380 return POLARSSL_ERR_MPI_NEGATIVE_VALUE;
HannesTschofenig 0:796d0f61a05b 1381
HannesTschofenig 0:796d0f61a05b 1382 MPI_CHK( mpi_div_mpi( NULL, R, A, B ) );
HannesTschofenig 0:796d0f61a05b 1383
HannesTschofenig 0:796d0f61a05b 1384 while( mpi_cmp_int( R, 0 ) < 0 )
HannesTschofenig 0:796d0f61a05b 1385 MPI_CHK( mpi_add_mpi( R, R, B ) );
HannesTschofenig 0:796d0f61a05b 1386
HannesTschofenig 0:796d0f61a05b 1387 while( mpi_cmp_mpi( R, B ) >= 0 )
HannesTschofenig 0:796d0f61a05b 1388 MPI_CHK( mpi_sub_mpi( R, R, B ) );
HannesTschofenig 0:796d0f61a05b 1389
HannesTschofenig 0:796d0f61a05b 1390 cleanup:
HannesTschofenig 0:796d0f61a05b 1391
HannesTschofenig 0:796d0f61a05b 1392 return( ret );
HannesTschofenig 0:796d0f61a05b 1393 }
HannesTschofenig 0:796d0f61a05b 1394
HannesTschofenig 0:796d0f61a05b 1395 /*
HannesTschofenig 0:796d0f61a05b 1396 * Modulo: r = A mod b
HannesTschofenig 0:796d0f61a05b 1397 */
HannesTschofenig 0:796d0f61a05b 1398 int mpi_mod_int( t_uint *r, const mpi *A, t_sint b )
HannesTschofenig 0:796d0f61a05b 1399 {
HannesTschofenig 0:796d0f61a05b 1400 size_t i;
HannesTschofenig 0:796d0f61a05b 1401 t_uint x, y, z;
HannesTschofenig 0:796d0f61a05b 1402
HannesTschofenig 0:796d0f61a05b 1403 if( b == 0 )
HannesTschofenig 0:796d0f61a05b 1404 return( POLARSSL_ERR_MPI_DIVISION_BY_ZERO );
HannesTschofenig 0:796d0f61a05b 1405
HannesTschofenig 0:796d0f61a05b 1406 if( b < 0 )
HannesTschofenig 0:796d0f61a05b 1407 return POLARSSL_ERR_MPI_NEGATIVE_VALUE;
HannesTschofenig 0:796d0f61a05b 1408
HannesTschofenig 0:796d0f61a05b 1409 /*
HannesTschofenig 0:796d0f61a05b 1410 * handle trivial cases
HannesTschofenig 0:796d0f61a05b 1411 */
HannesTschofenig 0:796d0f61a05b 1412 if( b == 1 )
HannesTschofenig 0:796d0f61a05b 1413 {
HannesTschofenig 0:796d0f61a05b 1414 *r = 0;
HannesTschofenig 0:796d0f61a05b 1415 return( 0 );
HannesTschofenig 0:796d0f61a05b 1416 }
HannesTschofenig 0:796d0f61a05b 1417
HannesTschofenig 0:796d0f61a05b 1418 if( b == 2 )
HannesTschofenig 0:796d0f61a05b 1419 {
HannesTschofenig 0:796d0f61a05b 1420 *r = A->p[0] & 1;
HannesTschofenig 0:796d0f61a05b 1421 return( 0 );
HannesTschofenig 0:796d0f61a05b 1422 }
HannesTschofenig 0:796d0f61a05b 1423
HannesTschofenig 0:796d0f61a05b 1424 /*
HannesTschofenig 0:796d0f61a05b 1425 * general case
HannesTschofenig 0:796d0f61a05b 1426 */
HannesTschofenig 0:796d0f61a05b 1427 for( i = A->n, y = 0; i > 0; i-- )
HannesTschofenig 0:796d0f61a05b 1428 {
HannesTschofenig 0:796d0f61a05b 1429 x = A->p[i - 1];
HannesTschofenig 0:796d0f61a05b 1430 y = ( y << biH ) | ( x >> biH );
HannesTschofenig 0:796d0f61a05b 1431 z = y / b;
HannesTschofenig 0:796d0f61a05b 1432 y -= z * b;
HannesTschofenig 0:796d0f61a05b 1433
HannesTschofenig 0:796d0f61a05b 1434 x <<= biH;
HannesTschofenig 0:796d0f61a05b 1435 y = ( y << biH ) | ( x >> biH );
HannesTschofenig 0:796d0f61a05b 1436 z = y / b;
HannesTschofenig 0:796d0f61a05b 1437 y -= z * b;
HannesTschofenig 0:796d0f61a05b 1438 }
HannesTschofenig 0:796d0f61a05b 1439
HannesTschofenig 0:796d0f61a05b 1440 /*
HannesTschofenig 0:796d0f61a05b 1441 * If A is negative, then the current y represents a negative value.
HannesTschofenig 0:796d0f61a05b 1442 * Flipping it to the positive side.
HannesTschofenig 0:796d0f61a05b 1443 */
HannesTschofenig 0:796d0f61a05b 1444 if( A->s < 0 && y != 0 )
HannesTschofenig 0:796d0f61a05b 1445 y = b - y;
HannesTschofenig 0:796d0f61a05b 1446
HannesTschofenig 0:796d0f61a05b 1447 *r = y;
HannesTschofenig 0:796d0f61a05b 1448
HannesTschofenig 0:796d0f61a05b 1449 return( 0 );
HannesTschofenig 0:796d0f61a05b 1450 }
HannesTschofenig 0:796d0f61a05b 1451
HannesTschofenig 0:796d0f61a05b 1452 /*
HannesTschofenig 0:796d0f61a05b 1453 * Fast Montgomery initialization (thanks to Tom St Denis)
HannesTschofenig 0:796d0f61a05b 1454 */
HannesTschofenig 0:796d0f61a05b 1455 static void mpi_montg_init( t_uint *mm, const mpi *N )
HannesTschofenig 0:796d0f61a05b 1456 {
HannesTschofenig 0:796d0f61a05b 1457 t_uint x, m0 = N->p[0];
HannesTschofenig 0:796d0f61a05b 1458 unsigned int i;
HannesTschofenig 0:796d0f61a05b 1459
HannesTschofenig 0:796d0f61a05b 1460 x = m0;
HannesTschofenig 0:796d0f61a05b 1461 x += ( ( m0 + 2 ) & 4 ) << 1;
HannesTschofenig 0:796d0f61a05b 1462
HannesTschofenig 0:796d0f61a05b 1463 for( i = biL; i >= 8; i /= 2 )
HannesTschofenig 0:796d0f61a05b 1464 x *= ( 2 - ( m0 * x ) );
HannesTschofenig 0:796d0f61a05b 1465
HannesTschofenig 0:796d0f61a05b 1466 *mm = ~x + 1;
HannesTschofenig 0:796d0f61a05b 1467 }
HannesTschofenig 0:796d0f61a05b 1468
HannesTschofenig 0:796d0f61a05b 1469 /*
HannesTschofenig 0:796d0f61a05b 1470 * Montgomery multiplication: A = A * B * R^-1 mod N (HAC 14.36)
HannesTschofenig 0:796d0f61a05b 1471 */
HannesTschofenig 0:796d0f61a05b 1472 static void mpi_montmul( mpi *A, const mpi *B, const mpi *N, t_uint mm,
HannesTschofenig 0:796d0f61a05b 1473 const mpi *T )
HannesTschofenig 0:796d0f61a05b 1474 {
HannesTschofenig 0:796d0f61a05b 1475 size_t i, n, m;
HannesTschofenig 0:796d0f61a05b 1476 t_uint u0, u1, *d;
HannesTschofenig 0:796d0f61a05b 1477
HannesTschofenig 0:796d0f61a05b 1478 memset( T->p, 0, T->n * ciL );
HannesTschofenig 0:796d0f61a05b 1479
HannesTschofenig 0:796d0f61a05b 1480 d = T->p;
HannesTschofenig 0:796d0f61a05b 1481 n = N->n;
HannesTschofenig 0:796d0f61a05b 1482 m = ( B->n < n ) ? B->n : n;
HannesTschofenig 0:796d0f61a05b 1483
HannesTschofenig 0:796d0f61a05b 1484 for( i = 0; i < n; i++ )
HannesTschofenig 0:796d0f61a05b 1485 {
HannesTschofenig 0:796d0f61a05b 1486 /*
HannesTschofenig 0:796d0f61a05b 1487 * T = (T + u0*B + u1*N) / 2^biL
HannesTschofenig 0:796d0f61a05b 1488 */
HannesTschofenig 0:796d0f61a05b 1489 u0 = A->p[i];
HannesTschofenig 0:796d0f61a05b 1490 u1 = ( d[0] + u0 * B->p[0] ) * mm;
HannesTschofenig 0:796d0f61a05b 1491
HannesTschofenig 0:796d0f61a05b 1492 mpi_mul_hlp( m, B->p, d, u0 );
HannesTschofenig 0:796d0f61a05b 1493 mpi_mul_hlp( n, N->p, d, u1 );
HannesTschofenig 0:796d0f61a05b 1494
HannesTschofenig 0:796d0f61a05b 1495 *d++ = u0; d[n + 1] = 0;
HannesTschofenig 0:796d0f61a05b 1496 }
HannesTschofenig 0:796d0f61a05b 1497
HannesTschofenig 0:796d0f61a05b 1498 memcpy( A->p, d, (n + 1) * ciL );
HannesTschofenig 0:796d0f61a05b 1499
HannesTschofenig 0:796d0f61a05b 1500 if( mpi_cmp_abs( A, N ) >= 0 )
HannesTschofenig 0:796d0f61a05b 1501 mpi_sub_hlp( n, N->p, A->p );
HannesTschofenig 0:796d0f61a05b 1502 else
HannesTschofenig 0:796d0f61a05b 1503 /* prevent timing attacks */
HannesTschofenig 0:796d0f61a05b 1504 mpi_sub_hlp( n, A->p, T->p );
HannesTschofenig 0:796d0f61a05b 1505 }
HannesTschofenig 0:796d0f61a05b 1506
HannesTschofenig 0:796d0f61a05b 1507 /*
HannesTschofenig 0:796d0f61a05b 1508 * Montgomery reduction: A = A * R^-1 mod N
HannesTschofenig 0:796d0f61a05b 1509 */
HannesTschofenig 0:796d0f61a05b 1510 static void mpi_montred( mpi *A, const mpi *N, t_uint mm, const mpi *T )
HannesTschofenig 0:796d0f61a05b 1511 {
HannesTschofenig 0:796d0f61a05b 1512 t_uint z = 1;
HannesTschofenig 0:796d0f61a05b 1513 mpi U;
HannesTschofenig 0:796d0f61a05b 1514
HannesTschofenig 0:796d0f61a05b 1515 U.n = U.s = (int) z;
HannesTschofenig 0:796d0f61a05b 1516 U.p = &z;
HannesTschofenig 0:796d0f61a05b 1517
HannesTschofenig 0:796d0f61a05b 1518 mpi_montmul( A, &U, N, mm, T );
HannesTschofenig 0:796d0f61a05b 1519 }
HannesTschofenig 0:796d0f61a05b 1520
HannesTschofenig 0:796d0f61a05b 1521 /*
HannesTschofenig 0:796d0f61a05b 1522 * Sliding-window exponentiation: X = A^E mod N (HAC 14.85)
HannesTschofenig 0:796d0f61a05b 1523 */
HannesTschofenig 0:796d0f61a05b 1524 int mpi_exp_mod( mpi *X, const mpi *A, const mpi *E, const mpi *N, mpi *_RR )
HannesTschofenig 0:796d0f61a05b 1525 {
HannesTschofenig 0:796d0f61a05b 1526 int ret;
HannesTschofenig 0:796d0f61a05b 1527 size_t wbits, wsize, one = 1;
HannesTschofenig 0:796d0f61a05b 1528 size_t i, j, nblimbs;
HannesTschofenig 0:796d0f61a05b 1529 size_t bufsize, nbits;
HannesTschofenig 0:796d0f61a05b 1530 t_uint ei, mm, state;
HannesTschofenig 0:796d0f61a05b 1531 mpi RR, T, W[ 2 << POLARSSL_MPI_WINDOW_SIZE ], Apos;
HannesTschofenig 0:796d0f61a05b 1532 int neg;
HannesTschofenig 0:796d0f61a05b 1533
HannesTschofenig 0:796d0f61a05b 1534 if( mpi_cmp_int( N, 0 ) < 0 || ( N->p[0] & 1 ) == 0 )
HannesTschofenig 0:796d0f61a05b 1535 return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
HannesTschofenig 0:796d0f61a05b 1536
HannesTschofenig 0:796d0f61a05b 1537 if( mpi_cmp_int( E, 0 ) < 0 )
HannesTschofenig 0:796d0f61a05b 1538 return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
HannesTschofenig 0:796d0f61a05b 1539
HannesTschofenig 0:796d0f61a05b 1540 /*
HannesTschofenig 0:796d0f61a05b 1541 * Init temps and window size
HannesTschofenig 0:796d0f61a05b 1542 */
HannesTschofenig 0:796d0f61a05b 1543 mpi_montg_init( &mm, N );
HannesTschofenig 0:796d0f61a05b 1544 mpi_init( &RR ); mpi_init( &T );
HannesTschofenig 0:796d0f61a05b 1545 mpi_init( &Apos );
HannesTschofenig 0:796d0f61a05b 1546 memset( W, 0, sizeof( W ) );
HannesTschofenig 0:796d0f61a05b 1547
HannesTschofenig 0:796d0f61a05b 1548 i = mpi_msb( E );
HannesTschofenig 0:796d0f61a05b 1549
HannesTschofenig 0:796d0f61a05b 1550 wsize = ( i > 671 ) ? 6 : ( i > 239 ) ? 5 :
HannesTschofenig 0:796d0f61a05b 1551 ( i > 79 ) ? 4 : ( i > 23 ) ? 3 : 1;
HannesTschofenig 0:796d0f61a05b 1552
HannesTschofenig 0:796d0f61a05b 1553 if( wsize > POLARSSL_MPI_WINDOW_SIZE )
HannesTschofenig 0:796d0f61a05b 1554 wsize = POLARSSL_MPI_WINDOW_SIZE;
HannesTschofenig 0:796d0f61a05b 1555
HannesTschofenig 0:796d0f61a05b 1556 j = N->n + 1;
HannesTschofenig 0:796d0f61a05b 1557 MPI_CHK( mpi_grow( X, j ) );
HannesTschofenig 0:796d0f61a05b 1558 MPI_CHK( mpi_grow( &W[1], j ) );
HannesTschofenig 0:796d0f61a05b 1559 MPI_CHK( mpi_grow( &T, j * 2 ) );
HannesTschofenig 0:796d0f61a05b 1560
HannesTschofenig 0:796d0f61a05b 1561 /*
HannesTschofenig 0:796d0f61a05b 1562 * Compensate for negative A (and correct at the end)
HannesTschofenig 0:796d0f61a05b 1563 */
HannesTschofenig 0:796d0f61a05b 1564 neg = ( A->s == -1 );
HannesTschofenig 0:796d0f61a05b 1565 if( neg )
HannesTschofenig 0:796d0f61a05b 1566 {
HannesTschofenig 0:796d0f61a05b 1567 MPI_CHK( mpi_copy( &Apos, A ) );
HannesTschofenig 0:796d0f61a05b 1568 Apos.s = 1;
HannesTschofenig 0:796d0f61a05b 1569 A = &Apos;
HannesTschofenig 0:796d0f61a05b 1570 }
HannesTschofenig 0:796d0f61a05b 1571
HannesTschofenig 0:796d0f61a05b 1572 /*
HannesTschofenig 0:796d0f61a05b 1573 * If 1st call, pre-compute R^2 mod N
HannesTschofenig 0:796d0f61a05b 1574 */
HannesTschofenig 0:796d0f61a05b 1575 if( _RR == NULL || _RR->p == NULL )
HannesTschofenig 0:796d0f61a05b 1576 {
HannesTschofenig 0:796d0f61a05b 1577 MPI_CHK( mpi_lset( &RR, 1 ) );
HannesTschofenig 0:796d0f61a05b 1578 MPI_CHK( mpi_shift_l( &RR, N->n * 2 * biL ) );
HannesTschofenig 0:796d0f61a05b 1579 MPI_CHK( mpi_mod_mpi( &RR, &RR, N ) );
HannesTschofenig 0:796d0f61a05b 1580
HannesTschofenig 0:796d0f61a05b 1581 if( _RR != NULL )
HannesTschofenig 0:796d0f61a05b 1582 memcpy( _RR, &RR, sizeof( mpi ) );
HannesTschofenig 0:796d0f61a05b 1583 }
HannesTschofenig 0:796d0f61a05b 1584 else
HannesTschofenig 0:796d0f61a05b 1585 memcpy( &RR, _RR, sizeof( mpi ) );
HannesTschofenig 0:796d0f61a05b 1586
HannesTschofenig 0:796d0f61a05b 1587 /*
HannesTschofenig 0:796d0f61a05b 1588 * W[1] = A * R^2 * R^-1 mod N = A * R mod N
HannesTschofenig 0:796d0f61a05b 1589 */
HannesTschofenig 0:796d0f61a05b 1590 if( mpi_cmp_mpi( A, N ) >= 0 )
HannesTschofenig 0:796d0f61a05b 1591 MPI_CHK( mpi_mod_mpi( &W[1], A, N ) );
HannesTschofenig 0:796d0f61a05b 1592 else
HannesTschofenig 0:796d0f61a05b 1593 MPI_CHK( mpi_copy( &W[1], A ) );
HannesTschofenig 0:796d0f61a05b 1594
HannesTschofenig 0:796d0f61a05b 1595 mpi_montmul( &W[1], &RR, N, mm, &T );
HannesTschofenig 0:796d0f61a05b 1596
HannesTschofenig 0:796d0f61a05b 1597 /*
HannesTschofenig 0:796d0f61a05b 1598 * X = R^2 * R^-1 mod N = R mod N
HannesTschofenig 0:796d0f61a05b 1599 */
HannesTschofenig 0:796d0f61a05b 1600 MPI_CHK( mpi_copy( X, &RR ) );
HannesTschofenig 0:796d0f61a05b 1601 mpi_montred( X, N, mm, &T );
HannesTschofenig 0:796d0f61a05b 1602
HannesTschofenig 0:796d0f61a05b 1603 if( wsize > 1 )
HannesTschofenig 0:796d0f61a05b 1604 {
HannesTschofenig 0:796d0f61a05b 1605 /*
HannesTschofenig 0:796d0f61a05b 1606 * W[1 << (wsize - 1)] = W[1] ^ (wsize - 1)
HannesTschofenig 0:796d0f61a05b 1607 */
HannesTschofenig 0:796d0f61a05b 1608 j = one << (wsize - 1);
HannesTschofenig 0:796d0f61a05b 1609
HannesTschofenig 0:796d0f61a05b 1610 MPI_CHK( mpi_grow( &W[j], N->n + 1 ) );
HannesTschofenig 0:796d0f61a05b 1611 MPI_CHK( mpi_copy( &W[j], &W[1] ) );
HannesTschofenig 0:796d0f61a05b 1612
HannesTschofenig 0:796d0f61a05b 1613 for( i = 0; i < wsize - 1; i++ )
HannesTschofenig 0:796d0f61a05b 1614 mpi_montmul( &W[j], &W[j], N, mm, &T );
HannesTschofenig 0:796d0f61a05b 1615
HannesTschofenig 0:796d0f61a05b 1616 /*
HannesTschofenig 0:796d0f61a05b 1617 * W[i] = W[i - 1] * W[1]
HannesTschofenig 0:796d0f61a05b 1618 */
HannesTschofenig 0:796d0f61a05b 1619 for( i = j + 1; i < (one << wsize); i++ )
HannesTschofenig 0:796d0f61a05b 1620 {
HannesTschofenig 0:796d0f61a05b 1621 MPI_CHK( mpi_grow( &W[i], N->n + 1 ) );
HannesTschofenig 0:796d0f61a05b 1622 MPI_CHK( mpi_copy( &W[i], &W[i - 1] ) );
HannesTschofenig 0:796d0f61a05b 1623
HannesTschofenig 0:796d0f61a05b 1624 mpi_montmul( &W[i], &W[1], N, mm, &T );
HannesTschofenig 0:796d0f61a05b 1625 }
HannesTschofenig 0:796d0f61a05b 1626 }
HannesTschofenig 0:796d0f61a05b 1627
HannesTschofenig 0:796d0f61a05b 1628 nblimbs = E->n;
HannesTschofenig 0:796d0f61a05b 1629 bufsize = 0;
HannesTschofenig 0:796d0f61a05b 1630 nbits = 0;
HannesTschofenig 0:796d0f61a05b 1631 wbits = 0;
HannesTschofenig 0:796d0f61a05b 1632 state = 0;
HannesTschofenig 0:796d0f61a05b 1633
HannesTschofenig 0:796d0f61a05b 1634 while( 1 )
HannesTschofenig 0:796d0f61a05b 1635 {
HannesTschofenig 0:796d0f61a05b 1636 if( bufsize == 0 )
HannesTschofenig 0:796d0f61a05b 1637 {
HannesTschofenig 0:796d0f61a05b 1638 if( nblimbs == 0 )
HannesTschofenig 0:796d0f61a05b 1639 break;
HannesTschofenig 0:796d0f61a05b 1640
HannesTschofenig 0:796d0f61a05b 1641 nblimbs--;
HannesTschofenig 0:796d0f61a05b 1642
HannesTschofenig 0:796d0f61a05b 1643 bufsize = sizeof( t_uint ) << 3;
HannesTschofenig 0:796d0f61a05b 1644 }
HannesTschofenig 0:796d0f61a05b 1645
HannesTschofenig 0:796d0f61a05b 1646 bufsize--;
HannesTschofenig 0:796d0f61a05b 1647
HannesTschofenig 0:796d0f61a05b 1648 ei = (E->p[nblimbs] >> bufsize) & 1;
HannesTschofenig 0:796d0f61a05b 1649
HannesTschofenig 0:796d0f61a05b 1650 /*
HannesTschofenig 0:796d0f61a05b 1651 * skip leading 0s
HannesTschofenig 0:796d0f61a05b 1652 */
HannesTschofenig 0:796d0f61a05b 1653 if( ei == 0 && state == 0 )
HannesTschofenig 0:796d0f61a05b 1654 continue;
HannesTschofenig 0:796d0f61a05b 1655
HannesTschofenig 0:796d0f61a05b 1656 if( ei == 0 && state == 1 )
HannesTschofenig 0:796d0f61a05b 1657 {
HannesTschofenig 0:796d0f61a05b 1658 /*
HannesTschofenig 0:796d0f61a05b 1659 * out of window, square X
HannesTschofenig 0:796d0f61a05b 1660 */
HannesTschofenig 0:796d0f61a05b 1661 mpi_montmul( X, X, N, mm, &T );
HannesTschofenig 0:796d0f61a05b 1662 continue;
HannesTschofenig 0:796d0f61a05b 1663 }
HannesTschofenig 0:796d0f61a05b 1664
HannesTschofenig 0:796d0f61a05b 1665 /*
HannesTschofenig 0:796d0f61a05b 1666 * add ei to current window
HannesTschofenig 0:796d0f61a05b 1667 */
HannesTschofenig 0:796d0f61a05b 1668 state = 2;
HannesTschofenig 0:796d0f61a05b 1669
HannesTschofenig 0:796d0f61a05b 1670 nbits++;
HannesTschofenig 0:796d0f61a05b 1671 wbits |= (ei << (wsize - nbits));
HannesTschofenig 0:796d0f61a05b 1672
HannesTschofenig 0:796d0f61a05b 1673 if( nbits == wsize )
HannesTschofenig 0:796d0f61a05b 1674 {
HannesTschofenig 0:796d0f61a05b 1675 /*
HannesTschofenig 0:796d0f61a05b 1676 * X = X^wsize R^-1 mod N
HannesTschofenig 0:796d0f61a05b 1677 */
HannesTschofenig 0:796d0f61a05b 1678 for( i = 0; i < wsize; i++ )
HannesTschofenig 0:796d0f61a05b 1679 mpi_montmul( X, X, N, mm, &T );
HannesTschofenig 0:796d0f61a05b 1680
HannesTschofenig 0:796d0f61a05b 1681 /*
HannesTschofenig 0:796d0f61a05b 1682 * X = X * W[wbits] R^-1 mod N
HannesTschofenig 0:796d0f61a05b 1683 */
HannesTschofenig 0:796d0f61a05b 1684 mpi_montmul( X, &W[wbits], N, mm, &T );
HannesTschofenig 0:796d0f61a05b 1685
HannesTschofenig 0:796d0f61a05b 1686 state--;
HannesTschofenig 0:796d0f61a05b 1687 nbits = 0;
HannesTschofenig 0:796d0f61a05b 1688 wbits = 0;
HannesTschofenig 0:796d0f61a05b 1689 }
HannesTschofenig 0:796d0f61a05b 1690 }
HannesTschofenig 0:796d0f61a05b 1691
HannesTschofenig 0:796d0f61a05b 1692 /*
HannesTschofenig 0:796d0f61a05b 1693 * process the remaining bits
HannesTschofenig 0:796d0f61a05b 1694 */
HannesTschofenig 0:796d0f61a05b 1695 for( i = 0; i < nbits; i++ )
HannesTschofenig 0:796d0f61a05b 1696 {
HannesTschofenig 0:796d0f61a05b 1697 mpi_montmul( X, X, N, mm, &T );
HannesTschofenig 0:796d0f61a05b 1698
HannesTschofenig 0:796d0f61a05b 1699 wbits <<= 1;
HannesTschofenig 0:796d0f61a05b 1700
HannesTschofenig 0:796d0f61a05b 1701 if( (wbits & (one << wsize)) != 0 )
HannesTschofenig 0:796d0f61a05b 1702 mpi_montmul( X, &W[1], N, mm, &T );
HannesTschofenig 0:796d0f61a05b 1703 }
HannesTschofenig 0:796d0f61a05b 1704
HannesTschofenig 0:796d0f61a05b 1705 /*
HannesTschofenig 0:796d0f61a05b 1706 * X = A^E * R * R^-1 mod N = A^E mod N
HannesTschofenig 0:796d0f61a05b 1707 */
HannesTschofenig 0:796d0f61a05b 1708 mpi_montred( X, N, mm, &T );
HannesTschofenig 0:796d0f61a05b 1709
HannesTschofenig 0:796d0f61a05b 1710 if( neg )
HannesTschofenig 0:796d0f61a05b 1711 {
HannesTschofenig 0:796d0f61a05b 1712 X->s = -1;
HannesTschofenig 0:796d0f61a05b 1713 MPI_CHK( mpi_add_mpi( X, N, X ) );
HannesTschofenig 0:796d0f61a05b 1714 }
HannesTschofenig 0:796d0f61a05b 1715
HannesTschofenig 0:796d0f61a05b 1716 cleanup:
HannesTschofenig 0:796d0f61a05b 1717
HannesTschofenig 0:796d0f61a05b 1718 for( i = (one << (wsize - 1)); i < (one << wsize); i++ )
HannesTschofenig 0:796d0f61a05b 1719 mpi_free( &W[i] );
HannesTschofenig 0:796d0f61a05b 1720
HannesTschofenig 0:796d0f61a05b 1721 mpi_free( &W[1] ); mpi_free( &T ); mpi_free( &Apos );
HannesTschofenig 0:796d0f61a05b 1722
HannesTschofenig 0:796d0f61a05b 1723 if( _RR == NULL || _RR->p == NULL )
HannesTschofenig 0:796d0f61a05b 1724 mpi_free( &RR );
HannesTschofenig 0:796d0f61a05b 1725
HannesTschofenig 0:796d0f61a05b 1726 return( ret );
HannesTschofenig 0:796d0f61a05b 1727 }
HannesTschofenig 0:796d0f61a05b 1728
HannesTschofenig 0:796d0f61a05b 1729 /*
HannesTschofenig 0:796d0f61a05b 1730 * Greatest common divisor: G = gcd(A, B) (HAC 14.54)
HannesTschofenig 0:796d0f61a05b 1731 */
HannesTschofenig 0:796d0f61a05b 1732 int mpi_gcd( mpi *G, const mpi *A, const mpi *B )
HannesTschofenig 0:796d0f61a05b 1733 {
HannesTschofenig 0:796d0f61a05b 1734 int ret;
HannesTschofenig 0:796d0f61a05b 1735 size_t lz, lzt;
HannesTschofenig 0:796d0f61a05b 1736 mpi TG, TA, TB;
HannesTschofenig 0:796d0f61a05b 1737
HannesTschofenig 0:796d0f61a05b 1738 mpi_init( &TG ); mpi_init( &TA ); mpi_init( &TB );
HannesTschofenig 0:796d0f61a05b 1739
HannesTschofenig 0:796d0f61a05b 1740 MPI_CHK( mpi_copy( &TA, A ) );
HannesTschofenig 0:796d0f61a05b 1741 MPI_CHK( mpi_copy( &TB, B ) );
HannesTschofenig 0:796d0f61a05b 1742
HannesTschofenig 0:796d0f61a05b 1743 lz = mpi_lsb( &TA );
HannesTschofenig 0:796d0f61a05b 1744 lzt = mpi_lsb( &TB );
HannesTschofenig 0:796d0f61a05b 1745
HannesTschofenig 0:796d0f61a05b 1746 if ( lzt < lz )
HannesTschofenig 0:796d0f61a05b 1747 lz = lzt;
HannesTschofenig 0:796d0f61a05b 1748
HannesTschofenig 0:796d0f61a05b 1749 MPI_CHK( mpi_shift_r( &TA, lz ) );
HannesTschofenig 0:796d0f61a05b 1750 MPI_CHK( mpi_shift_r( &TB, lz ) );
HannesTschofenig 0:796d0f61a05b 1751
HannesTschofenig 0:796d0f61a05b 1752 TA.s = TB.s = 1;
HannesTschofenig 0:796d0f61a05b 1753
HannesTschofenig 0:796d0f61a05b 1754 while( mpi_cmp_int( &TA, 0 ) != 0 )
HannesTschofenig 0:796d0f61a05b 1755 {
HannesTschofenig 0:796d0f61a05b 1756 MPI_CHK( mpi_shift_r( &TA, mpi_lsb( &TA ) ) );
HannesTschofenig 0:796d0f61a05b 1757 MPI_CHK( mpi_shift_r( &TB, mpi_lsb( &TB ) ) );
HannesTschofenig 0:796d0f61a05b 1758
HannesTschofenig 0:796d0f61a05b 1759 if( mpi_cmp_mpi( &TA, &TB ) >= 0 )
HannesTschofenig 0:796d0f61a05b 1760 {
HannesTschofenig 0:796d0f61a05b 1761 MPI_CHK( mpi_sub_abs( &TA, &TA, &TB ) );
HannesTschofenig 0:796d0f61a05b 1762 MPI_CHK( mpi_shift_r( &TA, 1 ) );
HannesTschofenig 0:796d0f61a05b 1763 }
HannesTschofenig 0:796d0f61a05b 1764 else
HannesTschofenig 0:796d0f61a05b 1765 {
HannesTschofenig 0:796d0f61a05b 1766 MPI_CHK( mpi_sub_abs( &TB, &TB, &TA ) );
HannesTschofenig 0:796d0f61a05b 1767 MPI_CHK( mpi_shift_r( &TB, 1 ) );
HannesTschofenig 0:796d0f61a05b 1768 }
HannesTschofenig 0:796d0f61a05b 1769 }
HannesTschofenig 0:796d0f61a05b 1770
HannesTschofenig 0:796d0f61a05b 1771 MPI_CHK( mpi_shift_l( &TB, lz ) );
HannesTschofenig 0:796d0f61a05b 1772 MPI_CHK( mpi_copy( G, &TB ) );
HannesTschofenig 0:796d0f61a05b 1773
HannesTschofenig 0:796d0f61a05b 1774 cleanup:
HannesTschofenig 0:796d0f61a05b 1775
HannesTschofenig 0:796d0f61a05b 1776 mpi_free( &TG ); mpi_free( &TA ); mpi_free( &TB );
HannesTschofenig 0:796d0f61a05b 1777
HannesTschofenig 0:796d0f61a05b 1778 return( ret );
HannesTschofenig 0:796d0f61a05b 1779 }
HannesTschofenig 0:796d0f61a05b 1780
HannesTschofenig 0:796d0f61a05b 1781 /*
HannesTschofenig 0:796d0f61a05b 1782 * Fill X with size bytes of random.
HannesTschofenig 0:796d0f61a05b 1783 *
HannesTschofenig 0:796d0f61a05b 1784 * Use a temporary bytes representation to make sure the result is the same
HannesTschofenig 0:796d0f61a05b 1785 * regardless of the platform endianness (useful when f_rng is actually
HannesTschofenig 0:796d0f61a05b 1786 * deterministic, eg for tests).
HannesTschofenig 0:796d0f61a05b 1787 */
HannesTschofenig 0:796d0f61a05b 1788 int mpi_fill_random( mpi *X, size_t size,
HannesTschofenig 0:796d0f61a05b 1789 int (*f_rng)(void *, unsigned char *, size_t),
HannesTschofenig 0:796d0f61a05b 1790 void *p_rng )
HannesTschofenig 0:796d0f61a05b 1791 {
HannesTschofenig 0:796d0f61a05b 1792 int ret;
HannesTschofenig 0:796d0f61a05b 1793 unsigned char buf[POLARSSL_MPI_MAX_SIZE];
HannesTschofenig 0:796d0f61a05b 1794
HannesTschofenig 0:796d0f61a05b 1795 if( size > POLARSSL_MPI_MAX_SIZE )
HannesTschofenig 0:796d0f61a05b 1796 return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
HannesTschofenig 0:796d0f61a05b 1797
HannesTschofenig 0:796d0f61a05b 1798 MPI_CHK( f_rng( p_rng, buf, size ) );
HannesTschofenig 0:796d0f61a05b 1799 MPI_CHK( mpi_read_binary( X, buf, size ) );
HannesTschofenig 0:796d0f61a05b 1800
HannesTschofenig 0:796d0f61a05b 1801 cleanup:
HannesTschofenig 0:796d0f61a05b 1802 return( ret );
HannesTschofenig 0:796d0f61a05b 1803 }
HannesTschofenig 0:796d0f61a05b 1804
HannesTschofenig 0:796d0f61a05b 1805 /*
HannesTschofenig 0:796d0f61a05b 1806 * Modular inverse: X = A^-1 mod N (HAC 14.61 / 14.64)
HannesTschofenig 0:796d0f61a05b 1807 */
HannesTschofenig 0:796d0f61a05b 1808 int mpi_inv_mod( mpi *X, const mpi *A, const mpi *N )
HannesTschofenig 0:796d0f61a05b 1809 {
HannesTschofenig 0:796d0f61a05b 1810 int ret;
HannesTschofenig 0:796d0f61a05b 1811 mpi G, TA, TU, U1, U2, TB, TV, V1, V2;
HannesTschofenig 0:796d0f61a05b 1812
HannesTschofenig 0:796d0f61a05b 1813 if( mpi_cmp_int( N, 0 ) <= 0 )
HannesTschofenig 0:796d0f61a05b 1814 return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
HannesTschofenig 0:796d0f61a05b 1815
HannesTschofenig 0:796d0f61a05b 1816 mpi_init( &TA ); mpi_init( &TU ); mpi_init( &U1 ); mpi_init( &U2 );
HannesTschofenig 0:796d0f61a05b 1817 mpi_init( &G ); mpi_init( &TB ); mpi_init( &TV );
HannesTschofenig 0:796d0f61a05b 1818 mpi_init( &V1 ); mpi_init( &V2 );
HannesTschofenig 0:796d0f61a05b 1819
HannesTschofenig 0:796d0f61a05b 1820 MPI_CHK( mpi_gcd( &G, A, N ) );
HannesTschofenig 0:796d0f61a05b 1821
HannesTschofenig 0:796d0f61a05b 1822 if( mpi_cmp_int( &G, 1 ) != 0 )
HannesTschofenig 0:796d0f61a05b 1823 {
HannesTschofenig 0:796d0f61a05b 1824 ret = POLARSSL_ERR_MPI_NOT_ACCEPTABLE;
HannesTschofenig 0:796d0f61a05b 1825 goto cleanup;
HannesTschofenig 0:796d0f61a05b 1826 }
HannesTschofenig 0:796d0f61a05b 1827
HannesTschofenig 0:796d0f61a05b 1828 MPI_CHK( mpi_mod_mpi( &TA, A, N ) );
HannesTschofenig 0:796d0f61a05b 1829 MPI_CHK( mpi_copy( &TU, &TA ) );
HannesTschofenig 0:796d0f61a05b 1830 MPI_CHK( mpi_copy( &TB, N ) );
HannesTschofenig 0:796d0f61a05b 1831 MPI_CHK( mpi_copy( &TV, N ) );
HannesTschofenig 0:796d0f61a05b 1832
HannesTschofenig 0:796d0f61a05b 1833 MPI_CHK( mpi_lset( &U1, 1 ) );
HannesTschofenig 0:796d0f61a05b 1834 MPI_CHK( mpi_lset( &U2, 0 ) );
HannesTschofenig 0:796d0f61a05b 1835 MPI_CHK( mpi_lset( &V1, 0 ) );
HannesTschofenig 0:796d0f61a05b 1836 MPI_CHK( mpi_lset( &V2, 1 ) );
HannesTschofenig 0:796d0f61a05b 1837
HannesTschofenig 0:796d0f61a05b 1838 do
HannesTschofenig 0:796d0f61a05b 1839 {
HannesTschofenig 0:796d0f61a05b 1840 while( ( TU.p[0] & 1 ) == 0 )
HannesTschofenig 0:796d0f61a05b 1841 {
HannesTschofenig 0:796d0f61a05b 1842 MPI_CHK( mpi_shift_r( &TU, 1 ) );
HannesTschofenig 0:796d0f61a05b 1843
HannesTschofenig 0:796d0f61a05b 1844 if( ( U1.p[0] & 1 ) != 0 || ( U2.p[0] & 1 ) != 0 )
HannesTschofenig 0:796d0f61a05b 1845 {
HannesTschofenig 0:796d0f61a05b 1846 MPI_CHK( mpi_add_mpi( &U1, &U1, &TB ) );
HannesTschofenig 0:796d0f61a05b 1847 MPI_CHK( mpi_sub_mpi( &U2, &U2, &TA ) );
HannesTschofenig 0:796d0f61a05b 1848 }
HannesTschofenig 0:796d0f61a05b 1849
HannesTschofenig 0:796d0f61a05b 1850 MPI_CHK( mpi_shift_r( &U1, 1 ) );
HannesTschofenig 0:796d0f61a05b 1851 MPI_CHK( mpi_shift_r( &U2, 1 ) );
HannesTschofenig 0:796d0f61a05b 1852 }
HannesTschofenig 0:796d0f61a05b 1853
HannesTschofenig 0:796d0f61a05b 1854 while( ( TV.p[0] & 1 ) == 0 )
HannesTschofenig 0:796d0f61a05b 1855 {
HannesTschofenig 0:796d0f61a05b 1856 MPI_CHK( mpi_shift_r( &TV, 1 ) );
HannesTschofenig 0:796d0f61a05b 1857
HannesTschofenig 0:796d0f61a05b 1858 if( ( V1.p[0] & 1 ) != 0 || ( V2.p[0] & 1 ) != 0 )
HannesTschofenig 0:796d0f61a05b 1859 {
HannesTschofenig 0:796d0f61a05b 1860 MPI_CHK( mpi_add_mpi( &V1, &V1, &TB ) );
HannesTschofenig 0:796d0f61a05b 1861 MPI_CHK( mpi_sub_mpi( &V2, &V2, &TA ) );
HannesTschofenig 0:796d0f61a05b 1862 }
HannesTschofenig 0:796d0f61a05b 1863
HannesTschofenig 0:796d0f61a05b 1864 MPI_CHK( mpi_shift_r( &V1, 1 ) );
HannesTschofenig 0:796d0f61a05b 1865 MPI_CHK( mpi_shift_r( &V2, 1 ) );
HannesTschofenig 0:796d0f61a05b 1866 }
HannesTschofenig 0:796d0f61a05b 1867
HannesTschofenig 0:796d0f61a05b 1868 if( mpi_cmp_mpi( &TU, &TV ) >= 0 )
HannesTschofenig 0:796d0f61a05b 1869 {
HannesTschofenig 0:796d0f61a05b 1870 MPI_CHK( mpi_sub_mpi( &TU, &TU, &TV ) );
HannesTschofenig 0:796d0f61a05b 1871 MPI_CHK( mpi_sub_mpi( &U1, &U1, &V1 ) );
HannesTschofenig 0:796d0f61a05b 1872 MPI_CHK( mpi_sub_mpi( &U2, &U2, &V2 ) );
HannesTschofenig 0:796d0f61a05b 1873 }
HannesTschofenig 0:796d0f61a05b 1874 else
HannesTschofenig 0:796d0f61a05b 1875 {
HannesTschofenig 0:796d0f61a05b 1876 MPI_CHK( mpi_sub_mpi( &TV, &TV, &TU ) );
HannesTschofenig 0:796d0f61a05b 1877 MPI_CHK( mpi_sub_mpi( &V1, &V1, &U1 ) );
HannesTschofenig 0:796d0f61a05b 1878 MPI_CHK( mpi_sub_mpi( &V2, &V2, &U2 ) );
HannesTschofenig 0:796d0f61a05b 1879 }
HannesTschofenig 0:796d0f61a05b 1880 }
HannesTschofenig 0:796d0f61a05b 1881 while( mpi_cmp_int( &TU, 0 ) != 0 );
HannesTschofenig 0:796d0f61a05b 1882
HannesTschofenig 0:796d0f61a05b 1883 while( mpi_cmp_int( &V1, 0 ) < 0 )
HannesTschofenig 0:796d0f61a05b 1884 MPI_CHK( mpi_add_mpi( &V1, &V1, N ) );
HannesTschofenig 0:796d0f61a05b 1885
HannesTschofenig 0:796d0f61a05b 1886 while( mpi_cmp_mpi( &V1, N ) >= 0 )
HannesTschofenig 0:796d0f61a05b 1887 MPI_CHK( mpi_sub_mpi( &V1, &V1, N ) );
HannesTschofenig 0:796d0f61a05b 1888
HannesTschofenig 0:796d0f61a05b 1889 MPI_CHK( mpi_copy( X, &V1 ) );
HannesTschofenig 0:796d0f61a05b 1890
HannesTschofenig 0:796d0f61a05b 1891 cleanup:
HannesTschofenig 0:796d0f61a05b 1892
HannesTschofenig 0:796d0f61a05b 1893 mpi_free( &TA ); mpi_free( &TU ); mpi_free( &U1 ); mpi_free( &U2 );
HannesTschofenig 0:796d0f61a05b 1894 mpi_free( &G ); mpi_free( &TB ); mpi_free( &TV );
HannesTschofenig 0:796d0f61a05b 1895 mpi_free( &V1 ); mpi_free( &V2 );
HannesTschofenig 0:796d0f61a05b 1896
HannesTschofenig 0:796d0f61a05b 1897 return( ret );
HannesTschofenig 0:796d0f61a05b 1898 }
HannesTschofenig 0:796d0f61a05b 1899
HannesTschofenig 0:796d0f61a05b 1900 #if defined(POLARSSL_GENPRIME)
HannesTschofenig 0:796d0f61a05b 1901
HannesTschofenig 0:796d0f61a05b 1902 static const int small_prime[] =
HannesTschofenig 0:796d0f61a05b 1903 {
HannesTschofenig 0:796d0f61a05b 1904 3, 5, 7, 11, 13, 17, 19, 23,
HannesTschofenig 0:796d0f61a05b 1905 29, 31, 37, 41, 43, 47, 53, 59,
HannesTschofenig 0:796d0f61a05b 1906 61, 67, 71, 73, 79, 83, 89, 97,
HannesTschofenig 0:796d0f61a05b 1907 101, 103, 107, 109, 113, 127, 131, 137,
HannesTschofenig 0:796d0f61a05b 1908 139, 149, 151, 157, 163, 167, 173, 179,
HannesTschofenig 0:796d0f61a05b 1909 181, 191, 193, 197, 199, 211, 223, 227,
HannesTschofenig 0:796d0f61a05b 1910 229, 233, 239, 241, 251, 257, 263, 269,
HannesTschofenig 0:796d0f61a05b 1911 271, 277, 281, 283, 293, 307, 311, 313,
HannesTschofenig 0:796d0f61a05b 1912 317, 331, 337, 347, 349, 353, 359, 367,
HannesTschofenig 0:796d0f61a05b 1913 373, 379, 383, 389, 397, 401, 409, 419,
HannesTschofenig 0:796d0f61a05b 1914 421, 431, 433, 439, 443, 449, 457, 461,
HannesTschofenig 0:796d0f61a05b 1915 463, 467, 479, 487, 491, 499, 503, 509,
HannesTschofenig 0:796d0f61a05b 1916 521, 523, 541, 547, 557, 563, 569, 571,
HannesTschofenig 0:796d0f61a05b 1917 577, 587, 593, 599, 601, 607, 613, 617,
HannesTschofenig 0:796d0f61a05b 1918 619, 631, 641, 643, 647, 653, 659, 661,
HannesTschofenig 0:796d0f61a05b 1919 673, 677, 683, 691, 701, 709, 719, 727,
HannesTschofenig 0:796d0f61a05b 1920 733, 739, 743, 751, 757, 761, 769, 773,
HannesTschofenig 0:796d0f61a05b 1921 787, 797, 809, 811, 821, 823, 827, 829,
HannesTschofenig 0:796d0f61a05b 1922 839, 853, 857, 859, 863, 877, 881, 883,
HannesTschofenig 0:796d0f61a05b 1923 887, 907, 911, 919, 929, 937, 941, 947,
HannesTschofenig 0:796d0f61a05b 1924 953, 967, 971, 977, 983, 991, 997, -103
HannesTschofenig 0:796d0f61a05b 1925 };
HannesTschofenig 0:796d0f61a05b 1926
HannesTschofenig 0:796d0f61a05b 1927 /*
HannesTschofenig 0:796d0f61a05b 1928 * Small divisors test (X must be positive)
HannesTschofenig 0:796d0f61a05b 1929 *
HannesTschofenig 0:796d0f61a05b 1930 * Return values:
HannesTschofenig 0:796d0f61a05b 1931 * 0: no small factor (possible prime, more tests needed)
HannesTschofenig 0:796d0f61a05b 1932 * 1: certain prime
HannesTschofenig 0:796d0f61a05b 1933 * POLARSSL_ERR_MPI_NOT_ACCEPTABLE: certain non-prime
HannesTschofenig 0:796d0f61a05b 1934 * other negative: error
HannesTschofenig 0:796d0f61a05b 1935 */
HannesTschofenig 0:796d0f61a05b 1936 static int mpi_check_small_factors( const mpi *X )
HannesTschofenig 0:796d0f61a05b 1937 {
HannesTschofenig 0:796d0f61a05b 1938 int ret = 0;
HannesTschofenig 0:796d0f61a05b 1939 size_t i;
HannesTschofenig 0:796d0f61a05b 1940 t_uint r;
HannesTschofenig 0:796d0f61a05b 1941
HannesTschofenig 0:796d0f61a05b 1942 if( ( X->p[0] & 1 ) == 0 )
HannesTschofenig 0:796d0f61a05b 1943 return( POLARSSL_ERR_MPI_NOT_ACCEPTABLE );
HannesTschofenig 0:796d0f61a05b 1944
HannesTschofenig 0:796d0f61a05b 1945 for( i = 0; small_prime[i] > 0; i++ )
HannesTschofenig 0:796d0f61a05b 1946 {
HannesTschofenig 0:796d0f61a05b 1947 if( mpi_cmp_int( X, small_prime[i] ) <= 0 )
HannesTschofenig 0:796d0f61a05b 1948 return( 1 );
HannesTschofenig 0:796d0f61a05b 1949
HannesTschofenig 0:796d0f61a05b 1950 MPI_CHK( mpi_mod_int( &r, X, small_prime[i] ) );
HannesTschofenig 0:796d0f61a05b 1951
HannesTschofenig 0:796d0f61a05b 1952 if( r == 0 )
HannesTschofenig 0:796d0f61a05b 1953 return( POLARSSL_ERR_MPI_NOT_ACCEPTABLE );
HannesTschofenig 0:796d0f61a05b 1954 }
HannesTschofenig 0:796d0f61a05b 1955
HannesTschofenig 0:796d0f61a05b 1956 cleanup:
HannesTschofenig 0:796d0f61a05b 1957 return( ret );
HannesTschofenig 0:796d0f61a05b 1958 }
HannesTschofenig 0:796d0f61a05b 1959
HannesTschofenig 0:796d0f61a05b 1960 /*
HannesTschofenig 0:796d0f61a05b 1961 * Miller-Rabin pseudo-primality test (HAC 4.24)
HannesTschofenig 0:796d0f61a05b 1962 */
HannesTschofenig 0:796d0f61a05b 1963 static int mpi_miller_rabin( const mpi *X,
HannesTschofenig 0:796d0f61a05b 1964 int (*f_rng)(void *, unsigned char *, size_t),
HannesTschofenig 0:796d0f61a05b 1965 void *p_rng )
HannesTschofenig 0:796d0f61a05b 1966 {
HannesTschofenig 0:796d0f61a05b 1967 int ret;
HannesTschofenig 0:796d0f61a05b 1968 size_t i, j, n, s;
HannesTschofenig 0:796d0f61a05b 1969 mpi W, R, T, A, RR;
HannesTschofenig 0:796d0f61a05b 1970
HannesTschofenig 0:796d0f61a05b 1971 mpi_init( &W ); mpi_init( &R ); mpi_init( &T ); mpi_init( &A );
HannesTschofenig 0:796d0f61a05b 1972 mpi_init( &RR );
HannesTschofenig 0:796d0f61a05b 1973
HannesTschofenig 0:796d0f61a05b 1974 /*
HannesTschofenig 0:796d0f61a05b 1975 * W = |X| - 1
HannesTschofenig 0:796d0f61a05b 1976 * R = W >> lsb( W )
HannesTschofenig 0:796d0f61a05b 1977 */
HannesTschofenig 0:796d0f61a05b 1978 MPI_CHK( mpi_sub_int( &W, X, 1 ) );
HannesTschofenig 0:796d0f61a05b 1979 s = mpi_lsb( &W );
HannesTschofenig 0:796d0f61a05b 1980 MPI_CHK( mpi_copy( &R, &W ) );
HannesTschofenig 0:796d0f61a05b 1981 MPI_CHK( mpi_shift_r( &R, s ) );
HannesTschofenig 0:796d0f61a05b 1982
HannesTschofenig 0:796d0f61a05b 1983 i = mpi_msb( X );
HannesTschofenig 0:796d0f61a05b 1984 /*
HannesTschofenig 0:796d0f61a05b 1985 * HAC, table 4.4
HannesTschofenig 0:796d0f61a05b 1986 */
HannesTschofenig 0:796d0f61a05b 1987 n = ( ( i >= 1300 ) ? 2 : ( i >= 850 ) ? 3 :
HannesTschofenig 0:796d0f61a05b 1988 ( i >= 650 ) ? 4 : ( i >= 350 ) ? 8 :
HannesTschofenig 0:796d0f61a05b 1989 ( i >= 250 ) ? 12 : ( i >= 150 ) ? 18 : 27 );
HannesTschofenig 0:796d0f61a05b 1990
HannesTschofenig 0:796d0f61a05b 1991 for( i = 0; i < n; i++ )
HannesTschofenig 0:796d0f61a05b 1992 {
HannesTschofenig 0:796d0f61a05b 1993 /*
HannesTschofenig 0:796d0f61a05b 1994 * pick a random A, 1 < A < |X| - 1
HannesTschofenig 0:796d0f61a05b 1995 */
HannesTschofenig 0:796d0f61a05b 1996 MPI_CHK( mpi_fill_random( &A, X->n * ciL, f_rng, p_rng ) );
HannesTschofenig 0:796d0f61a05b 1997
HannesTschofenig 0:796d0f61a05b 1998 if( mpi_cmp_mpi( &A, &W ) >= 0 )
HannesTschofenig 0:796d0f61a05b 1999 {
HannesTschofenig 0:796d0f61a05b 2000 j = mpi_msb( &A ) - mpi_msb( &W );
HannesTschofenig 0:796d0f61a05b 2001 MPI_CHK( mpi_shift_r( &A, j + 1 ) );
HannesTschofenig 0:796d0f61a05b 2002 }
HannesTschofenig 0:796d0f61a05b 2003 A.p[0] |= 3;
HannesTschofenig 0:796d0f61a05b 2004
HannesTschofenig 0:796d0f61a05b 2005 /*
HannesTschofenig 0:796d0f61a05b 2006 * A = A^R mod |X|
HannesTschofenig 0:796d0f61a05b 2007 */
HannesTschofenig 0:796d0f61a05b 2008 MPI_CHK( mpi_exp_mod( &A, &A, &R, X, &RR ) );
HannesTschofenig 0:796d0f61a05b 2009
HannesTschofenig 0:796d0f61a05b 2010 if( mpi_cmp_mpi( &A, &W ) == 0 ||
HannesTschofenig 0:796d0f61a05b 2011 mpi_cmp_int( &A, 1 ) == 0 )
HannesTschofenig 0:796d0f61a05b 2012 continue;
HannesTschofenig 0:796d0f61a05b 2013
HannesTschofenig 0:796d0f61a05b 2014 j = 1;
HannesTschofenig 0:796d0f61a05b 2015 while( j < s && mpi_cmp_mpi( &A, &W ) != 0 )
HannesTschofenig 0:796d0f61a05b 2016 {
HannesTschofenig 0:796d0f61a05b 2017 /*
HannesTschofenig 0:796d0f61a05b 2018 * A = A * A mod |X|
HannesTschofenig 0:796d0f61a05b 2019 */
HannesTschofenig 0:796d0f61a05b 2020 MPI_CHK( mpi_mul_mpi( &T, &A, &A ) );
HannesTschofenig 0:796d0f61a05b 2021 MPI_CHK( mpi_mod_mpi( &A, &T, X ) );
HannesTschofenig 0:796d0f61a05b 2022
HannesTschofenig 0:796d0f61a05b 2023 if( mpi_cmp_int( &A, 1 ) == 0 )
HannesTschofenig 0:796d0f61a05b 2024 break;
HannesTschofenig 0:796d0f61a05b 2025
HannesTschofenig 0:796d0f61a05b 2026 j++;
HannesTschofenig 0:796d0f61a05b 2027 }
HannesTschofenig 0:796d0f61a05b 2028
HannesTschofenig 0:796d0f61a05b 2029 /*
HannesTschofenig 0:796d0f61a05b 2030 * not prime if A != |X| - 1 or A == 1
HannesTschofenig 0:796d0f61a05b 2031 */
HannesTschofenig 0:796d0f61a05b 2032 if( mpi_cmp_mpi( &A, &W ) != 0 ||
HannesTschofenig 0:796d0f61a05b 2033 mpi_cmp_int( &A, 1 ) == 0 )
HannesTschofenig 0:796d0f61a05b 2034 {
HannesTschofenig 0:796d0f61a05b 2035 ret = POLARSSL_ERR_MPI_NOT_ACCEPTABLE;
HannesTschofenig 0:796d0f61a05b 2036 break;
HannesTschofenig 0:796d0f61a05b 2037 }
HannesTschofenig 0:796d0f61a05b 2038 }
HannesTschofenig 0:796d0f61a05b 2039
HannesTschofenig 0:796d0f61a05b 2040 cleanup:
HannesTschofenig 0:796d0f61a05b 2041 mpi_free( &W ); mpi_free( &R ); mpi_free( &T ); mpi_free( &A );
HannesTschofenig 0:796d0f61a05b 2042 mpi_free( &RR );
HannesTschofenig 0:796d0f61a05b 2043
HannesTschofenig 0:796d0f61a05b 2044 return( ret );
HannesTschofenig 0:796d0f61a05b 2045 }
HannesTschofenig 0:796d0f61a05b 2046
HannesTschofenig 0:796d0f61a05b 2047 /*
HannesTschofenig 0:796d0f61a05b 2048 * Pseudo-primality test: small factors, then Miller-Rabin
HannesTschofenig 0:796d0f61a05b 2049 */
HannesTschofenig 0:796d0f61a05b 2050 int mpi_is_prime( mpi *X,
HannesTschofenig 0:796d0f61a05b 2051 int (*f_rng)(void *, unsigned char *, size_t),
HannesTschofenig 0:796d0f61a05b 2052 void *p_rng )
HannesTschofenig 0:796d0f61a05b 2053 {
HannesTschofenig 0:796d0f61a05b 2054 int ret;
HannesTschofenig 0:796d0f61a05b 2055 const mpi XX = { 1, X->n, X->p }; /* Abs(X) */
HannesTschofenig 0:796d0f61a05b 2056
HannesTschofenig 0:796d0f61a05b 2057 if( mpi_cmp_int( &XX, 0 ) == 0 ||
HannesTschofenig 0:796d0f61a05b 2058 mpi_cmp_int( &XX, 1 ) == 0 )
HannesTschofenig 0:796d0f61a05b 2059 return( POLARSSL_ERR_MPI_NOT_ACCEPTABLE );
HannesTschofenig 0:796d0f61a05b 2060
HannesTschofenig 0:796d0f61a05b 2061 if( mpi_cmp_int( &XX, 2 ) == 0 )
HannesTschofenig 0:796d0f61a05b 2062 return( 0 );
HannesTschofenig 0:796d0f61a05b 2063
HannesTschofenig 0:796d0f61a05b 2064 if( ( ret = mpi_check_small_factors( &XX ) ) != 0 )
HannesTschofenig 0:796d0f61a05b 2065 {
HannesTschofenig 0:796d0f61a05b 2066 if( ret == 1 )
HannesTschofenig 0:796d0f61a05b 2067 return( 0 );
HannesTschofenig 0:796d0f61a05b 2068
HannesTschofenig 0:796d0f61a05b 2069 return( ret );
HannesTschofenig 0:796d0f61a05b 2070 }
HannesTschofenig 0:796d0f61a05b 2071
HannesTschofenig 0:796d0f61a05b 2072 return( mpi_miller_rabin( &XX, f_rng, p_rng ) );
HannesTschofenig 0:796d0f61a05b 2073 }
HannesTschofenig 0:796d0f61a05b 2074
HannesTschofenig 0:796d0f61a05b 2075 /*
HannesTschofenig 0:796d0f61a05b 2076 * Prime number generation
HannesTschofenig 0:796d0f61a05b 2077 */
HannesTschofenig 0:796d0f61a05b 2078 int mpi_gen_prime( mpi *X, size_t nbits, int dh_flag,
HannesTschofenig 0:796d0f61a05b 2079 int (*f_rng)(void *, unsigned char *, size_t),
HannesTschofenig 0:796d0f61a05b 2080 void *p_rng )
HannesTschofenig 0:796d0f61a05b 2081 {
HannesTschofenig 0:796d0f61a05b 2082 int ret;
HannesTschofenig 0:796d0f61a05b 2083 size_t k, n;
HannesTschofenig 0:796d0f61a05b 2084 t_uint r;
HannesTschofenig 0:796d0f61a05b 2085 mpi Y;
HannesTschofenig 0:796d0f61a05b 2086
HannesTschofenig 0:796d0f61a05b 2087 if( nbits < 3 || nbits > POLARSSL_MPI_MAX_BITS )
HannesTschofenig 0:796d0f61a05b 2088 return( POLARSSL_ERR_MPI_BAD_INPUT_DATA );
HannesTschofenig 0:796d0f61a05b 2089
HannesTschofenig 0:796d0f61a05b 2090 mpi_init( &Y );
HannesTschofenig 0:796d0f61a05b 2091
HannesTschofenig 0:796d0f61a05b 2092 n = BITS_TO_LIMBS( nbits );
HannesTschofenig 0:796d0f61a05b 2093
HannesTschofenig 0:796d0f61a05b 2094 MPI_CHK( mpi_fill_random( X, n * ciL, f_rng, p_rng ) );
HannesTschofenig 0:796d0f61a05b 2095
HannesTschofenig 0:796d0f61a05b 2096 k = mpi_msb( X );
HannesTschofenig 0:796d0f61a05b 2097 if( k < nbits ) MPI_CHK( mpi_shift_l( X, nbits - k ) );
HannesTschofenig 0:796d0f61a05b 2098 if( k > nbits ) MPI_CHK( mpi_shift_r( X, k - nbits ) );
HannesTschofenig 0:796d0f61a05b 2099
HannesTschofenig 0:796d0f61a05b 2100 X->p[0] |= 3;
HannesTschofenig 0:796d0f61a05b 2101
HannesTschofenig 0:796d0f61a05b 2102 if( dh_flag == 0 )
HannesTschofenig 0:796d0f61a05b 2103 {
HannesTschofenig 0:796d0f61a05b 2104 while( ( ret = mpi_is_prime( X, f_rng, p_rng ) ) != 0 )
HannesTschofenig 0:796d0f61a05b 2105 {
HannesTschofenig 0:796d0f61a05b 2106 if( ret != POLARSSL_ERR_MPI_NOT_ACCEPTABLE )
HannesTschofenig 0:796d0f61a05b 2107 goto cleanup;
HannesTschofenig 0:796d0f61a05b 2108
HannesTschofenig 0:796d0f61a05b 2109 MPI_CHK( mpi_add_int( X, X, 2 ) );
HannesTschofenig 0:796d0f61a05b 2110 }
HannesTschofenig 0:796d0f61a05b 2111 }
HannesTschofenig 0:796d0f61a05b 2112 else
HannesTschofenig 0:796d0f61a05b 2113 {
HannesTschofenig 0:796d0f61a05b 2114 /*
HannesTschofenig 0:796d0f61a05b 2115 * An necessary condition for Y and X = 2Y + 1 to be prime
HannesTschofenig 0:796d0f61a05b 2116 * is X = 2 mod 3 (which is equivalent to Y = 2 mod 3).
HannesTschofenig 0:796d0f61a05b 2117 * Make sure it is satisfied, while keeping X = 3 mod 4
HannesTschofenig 0:796d0f61a05b 2118 */
HannesTschofenig 0:796d0f61a05b 2119 MPI_CHK( mpi_mod_int( &r, X, 3 ) );
HannesTschofenig 0:796d0f61a05b 2120 if( r == 0 )
HannesTschofenig 0:796d0f61a05b 2121 MPI_CHK( mpi_add_int( X, X, 8 ) );
HannesTschofenig 0:796d0f61a05b 2122 else if( r == 1 )
HannesTschofenig 0:796d0f61a05b 2123 MPI_CHK( mpi_add_int( X, X, 4 ) );
HannesTschofenig 0:796d0f61a05b 2124
HannesTschofenig 0:796d0f61a05b 2125 /* Set Y = (X-1) / 2, which is X / 2 because X is odd */
HannesTschofenig 0:796d0f61a05b 2126 MPI_CHK( mpi_copy( &Y, X ) );
HannesTschofenig 0:796d0f61a05b 2127 MPI_CHK( mpi_shift_r( &Y, 1 ) );
HannesTschofenig 0:796d0f61a05b 2128
HannesTschofenig 0:796d0f61a05b 2129 while( 1 )
HannesTschofenig 0:796d0f61a05b 2130 {
HannesTschofenig 0:796d0f61a05b 2131 /*
HannesTschofenig 0:796d0f61a05b 2132 * First, check small factors for X and Y
HannesTschofenig 0:796d0f61a05b 2133 * before doing Miller-Rabin on any of them
HannesTschofenig 0:796d0f61a05b 2134 */
HannesTschofenig 0:796d0f61a05b 2135 if( ( ret = mpi_check_small_factors( X ) ) == 0 &&
HannesTschofenig 0:796d0f61a05b 2136 ( ret = mpi_check_small_factors( &Y ) ) == 0 &&
HannesTschofenig 0:796d0f61a05b 2137 ( ret = mpi_miller_rabin( X, f_rng, p_rng ) ) == 0 &&
HannesTschofenig 0:796d0f61a05b 2138 ( ret = mpi_miller_rabin( &Y, f_rng, p_rng ) ) == 0 )
HannesTschofenig 0:796d0f61a05b 2139 {
HannesTschofenig 0:796d0f61a05b 2140 break;
HannesTschofenig 0:796d0f61a05b 2141 }
HannesTschofenig 0:796d0f61a05b 2142
HannesTschofenig 0:796d0f61a05b 2143 if( ret != POLARSSL_ERR_MPI_NOT_ACCEPTABLE )
HannesTschofenig 0:796d0f61a05b 2144 goto cleanup;
HannesTschofenig 0:796d0f61a05b 2145
HannesTschofenig 0:796d0f61a05b 2146 /*
HannesTschofenig 0:796d0f61a05b 2147 * Next candidates. We want to preserve Y = (X-1) / 2 and
HannesTschofenig 0:796d0f61a05b 2148 * Y = 1 mod 2 and Y = 2 mod 3 (eq X = 3 mod 4 and X = 2 mod 3)
HannesTschofenig 0:796d0f61a05b 2149 * so up Y by 6 and X by 12.
HannesTschofenig 0:796d0f61a05b 2150 */
HannesTschofenig 0:796d0f61a05b 2151 MPI_CHK( mpi_add_int( X, X, 12 ) );
HannesTschofenig 0:796d0f61a05b 2152 MPI_CHK( mpi_add_int( &Y, &Y, 6 ) );
HannesTschofenig 0:796d0f61a05b 2153 }
HannesTschofenig 0:796d0f61a05b 2154 }
HannesTschofenig 0:796d0f61a05b 2155
HannesTschofenig 0:796d0f61a05b 2156 cleanup:
HannesTschofenig 0:796d0f61a05b 2157
HannesTschofenig 0:796d0f61a05b 2158 mpi_free( &Y );
HannesTschofenig 0:796d0f61a05b 2159
HannesTschofenig 0:796d0f61a05b 2160 return( ret );
HannesTschofenig 0:796d0f61a05b 2161 }
HannesTschofenig 0:796d0f61a05b 2162
HannesTschofenig 0:796d0f61a05b 2163 #endif /* POLARSSL_GENPRIME */
HannesTschofenig 0:796d0f61a05b 2164
HannesTschofenig 0:796d0f61a05b 2165 #if defined(POLARSSL_SELF_TEST)
HannesTschofenig 0:796d0f61a05b 2166
HannesTschofenig 0:796d0f61a05b 2167 #define GCD_PAIR_COUNT 3
HannesTschofenig 0:796d0f61a05b 2168
HannesTschofenig 0:796d0f61a05b 2169 static const int gcd_pairs[GCD_PAIR_COUNT][3] =
HannesTschofenig 0:796d0f61a05b 2170 {
HannesTschofenig 0:796d0f61a05b 2171 { 693, 609, 21 },
HannesTschofenig 0:796d0f61a05b 2172 { 1764, 868, 28 },
HannesTschofenig 0:796d0f61a05b 2173 { 768454923, 542167814, 1 }
HannesTschofenig 0:796d0f61a05b 2174 };
HannesTschofenig 0:796d0f61a05b 2175
HannesTschofenig 0:796d0f61a05b 2176 /*
HannesTschofenig 0:796d0f61a05b 2177 * Checkup routine
HannesTschofenig 0:796d0f61a05b 2178 */
HannesTschofenig 0:796d0f61a05b 2179 int mpi_self_test( int verbose )
HannesTschofenig 0:796d0f61a05b 2180 {
HannesTschofenig 0:796d0f61a05b 2181 int ret, i;
HannesTschofenig 0:796d0f61a05b 2182 mpi A, E, N, X, Y, U, V;
HannesTschofenig 0:796d0f61a05b 2183
HannesTschofenig 0:796d0f61a05b 2184 mpi_init( &A ); mpi_init( &E ); mpi_init( &N ); mpi_init( &X );
HannesTschofenig 0:796d0f61a05b 2185 mpi_init( &Y ); mpi_init( &U ); mpi_init( &V );
HannesTschofenig 0:796d0f61a05b 2186
HannesTschofenig 0:796d0f61a05b 2187 MPI_CHK( mpi_read_string( &A, 16,
HannesTschofenig 0:796d0f61a05b 2188 "EFE021C2645FD1DC586E69184AF4A31E" \
HannesTschofenig 0:796d0f61a05b 2189 "D5F53E93B5F123FA41680867BA110131" \
HannesTschofenig 0:796d0f61a05b 2190 "944FE7952E2517337780CB0DB80E61AA" \
HannesTschofenig 0:796d0f61a05b 2191 "E7C8DDC6C5C6AADEB34EB38A2F40D5E6" ) );
HannesTschofenig 0:796d0f61a05b 2192
HannesTschofenig 0:796d0f61a05b 2193 MPI_CHK( mpi_read_string( &E, 16,
HannesTschofenig 0:796d0f61a05b 2194 "B2E7EFD37075B9F03FF989C7C5051C20" \
HannesTschofenig 0:796d0f61a05b 2195 "34D2A323810251127E7BF8625A4F49A5" \
HannesTschofenig 0:796d0f61a05b 2196 "F3E27F4DA8BD59C47D6DAABA4C8127BD" \
HannesTschofenig 0:796d0f61a05b 2197 "5B5C25763222FEFCCFC38B832366C29E" ) );
HannesTschofenig 0:796d0f61a05b 2198
HannesTschofenig 0:796d0f61a05b 2199 MPI_CHK( mpi_read_string( &N, 16,
HannesTschofenig 0:796d0f61a05b 2200 "0066A198186C18C10B2F5ED9B522752A" \
HannesTschofenig 0:796d0f61a05b 2201 "9830B69916E535C8F047518A889A43A5" \
HannesTschofenig 0:796d0f61a05b 2202 "94B6BED27A168D31D4A52F88925AA8F5" ) );
HannesTschofenig 0:796d0f61a05b 2203
HannesTschofenig 0:796d0f61a05b 2204 MPI_CHK( mpi_mul_mpi( &X, &A, &N ) );
HannesTschofenig 0:796d0f61a05b 2205
HannesTschofenig 0:796d0f61a05b 2206 MPI_CHK( mpi_read_string( &U, 16,
HannesTschofenig 0:796d0f61a05b 2207 "602AB7ECA597A3D6B56FF9829A5E8B85" \
HannesTschofenig 0:796d0f61a05b 2208 "9E857EA95A03512E2BAE7391688D264A" \
HannesTschofenig 0:796d0f61a05b 2209 "A5663B0341DB9CCFD2C4C5F421FEC814" \
HannesTschofenig 0:796d0f61a05b 2210 "8001B72E848A38CAE1C65F78E56ABDEF" \
HannesTschofenig 0:796d0f61a05b 2211 "E12D3C039B8A02D6BE593F0BBBDA56F1" \
HannesTschofenig 0:796d0f61a05b 2212 "ECF677152EF804370C1A305CAF3B5BF1" \
HannesTschofenig 0:796d0f61a05b 2213 "30879B56C61DE584A0F53A2447A51E" ) );
HannesTschofenig 0:796d0f61a05b 2214
HannesTschofenig 0:796d0f61a05b 2215 if( verbose != 0 )
HannesTschofenig 0:796d0f61a05b 2216 polarssl_printf( " MPI test #1 (mul_mpi): " );
HannesTschofenig 0:796d0f61a05b 2217
HannesTschofenig 0:796d0f61a05b 2218 if( mpi_cmp_mpi( &X, &U ) != 0 )
HannesTschofenig 0:796d0f61a05b 2219 {
HannesTschofenig 0:796d0f61a05b 2220 if( verbose != 0 )
HannesTschofenig 0:796d0f61a05b 2221 polarssl_printf( "failed\n" );
HannesTschofenig 0:796d0f61a05b 2222
HannesTschofenig 0:796d0f61a05b 2223 ret = 1;
HannesTschofenig 0:796d0f61a05b 2224 goto cleanup;
HannesTschofenig 0:796d0f61a05b 2225 }
HannesTschofenig 0:796d0f61a05b 2226
HannesTschofenig 0:796d0f61a05b 2227 if( verbose != 0 )
HannesTschofenig 0:796d0f61a05b 2228 polarssl_printf( "passed\n" );
HannesTschofenig 0:796d0f61a05b 2229
HannesTschofenig 0:796d0f61a05b 2230 MPI_CHK( mpi_div_mpi( &X, &Y, &A, &N ) );
HannesTschofenig 0:796d0f61a05b 2231
HannesTschofenig 0:796d0f61a05b 2232 MPI_CHK( mpi_read_string( &U, 16,
HannesTschofenig 0:796d0f61a05b 2233 "256567336059E52CAE22925474705F39A94" ) );
HannesTschofenig 0:796d0f61a05b 2234
HannesTschofenig 0:796d0f61a05b 2235 MPI_CHK( mpi_read_string( &V, 16,
HannesTschofenig 0:796d0f61a05b 2236 "6613F26162223DF488E9CD48CC132C7A" \
HannesTschofenig 0:796d0f61a05b 2237 "0AC93C701B001B092E4E5B9F73BCD27B" \
HannesTschofenig 0:796d0f61a05b 2238 "9EE50D0657C77F374E903CDFA4C642" ) );
HannesTschofenig 0:796d0f61a05b 2239
HannesTschofenig 0:796d0f61a05b 2240 if( verbose != 0 )
HannesTschofenig 0:796d0f61a05b 2241 polarssl_printf( " MPI test #2 (div_mpi): " );
HannesTschofenig 0:796d0f61a05b 2242
HannesTschofenig 0:796d0f61a05b 2243 if( mpi_cmp_mpi( &X, &U ) != 0 ||
HannesTschofenig 0:796d0f61a05b 2244 mpi_cmp_mpi( &Y, &V ) != 0 )
HannesTschofenig 0:796d0f61a05b 2245 {
HannesTschofenig 0:796d0f61a05b 2246 if( verbose != 0 )
HannesTschofenig 0:796d0f61a05b 2247 polarssl_printf( "failed\n" );
HannesTschofenig 0:796d0f61a05b 2248
HannesTschofenig 0:796d0f61a05b 2249 ret = 1;
HannesTschofenig 0:796d0f61a05b 2250 goto cleanup;
HannesTschofenig 0:796d0f61a05b 2251 }
HannesTschofenig 0:796d0f61a05b 2252
HannesTschofenig 0:796d0f61a05b 2253 if( verbose != 0 )
HannesTschofenig 0:796d0f61a05b 2254 polarssl_printf( "passed\n" );
HannesTschofenig 0:796d0f61a05b 2255
HannesTschofenig 0:796d0f61a05b 2256 MPI_CHK( mpi_exp_mod( &X, &A, &E, &N, NULL ) );
HannesTschofenig 0:796d0f61a05b 2257
HannesTschofenig 0:796d0f61a05b 2258 MPI_CHK( mpi_read_string( &U, 16,
HannesTschofenig 0:796d0f61a05b 2259 "36E139AEA55215609D2816998ED020BB" \
HannesTschofenig 0:796d0f61a05b 2260 "BD96C37890F65171D948E9BC7CBAA4D9" \
HannesTschofenig 0:796d0f61a05b 2261 "325D24D6A3C12710F10A09FA08AB87" ) );
HannesTschofenig 0:796d0f61a05b 2262
HannesTschofenig 0:796d0f61a05b 2263 if( verbose != 0 )
HannesTschofenig 0:796d0f61a05b 2264 polarssl_printf( " MPI test #3 (exp_mod): " );
HannesTschofenig 0:796d0f61a05b 2265
HannesTschofenig 0:796d0f61a05b 2266 if( mpi_cmp_mpi( &X, &U ) != 0 )
HannesTschofenig 0:796d0f61a05b 2267 {
HannesTschofenig 0:796d0f61a05b 2268 if( verbose != 0 )
HannesTschofenig 0:796d0f61a05b 2269 polarssl_printf( "failed\n" );
HannesTschofenig 0:796d0f61a05b 2270
HannesTschofenig 0:796d0f61a05b 2271 ret = 1;
HannesTschofenig 0:796d0f61a05b 2272 goto cleanup;
HannesTschofenig 0:796d0f61a05b 2273 }
HannesTschofenig 0:796d0f61a05b 2274
HannesTschofenig 0:796d0f61a05b 2275 if( verbose != 0 )
HannesTschofenig 0:796d0f61a05b 2276 polarssl_printf( "passed\n" );
HannesTschofenig 0:796d0f61a05b 2277
HannesTschofenig 0:796d0f61a05b 2278 MPI_CHK( mpi_inv_mod( &X, &A, &N ) );
HannesTschofenig 0:796d0f61a05b 2279
HannesTschofenig 0:796d0f61a05b 2280 MPI_CHK( mpi_read_string( &U, 16,
HannesTschofenig 0:796d0f61a05b 2281 "003A0AAEDD7E784FC07D8F9EC6E3BFD5" \
HannesTschofenig 0:796d0f61a05b 2282 "C3DBA76456363A10869622EAC2DD84EC" \
HannesTschofenig 0:796d0f61a05b 2283 "C5B8A74DAC4D09E03B5E0BE779F2DF61" ) );
HannesTschofenig 0:796d0f61a05b 2284
HannesTschofenig 0:796d0f61a05b 2285 if( verbose != 0 )
HannesTschofenig 0:796d0f61a05b 2286 polarssl_printf( " MPI test #4 (inv_mod): " );
HannesTschofenig 0:796d0f61a05b 2287
HannesTschofenig 0:796d0f61a05b 2288 if( mpi_cmp_mpi( &X, &U ) != 0 )
HannesTschofenig 0:796d0f61a05b 2289 {
HannesTschofenig 0:796d0f61a05b 2290 if( verbose != 0 )
HannesTschofenig 0:796d0f61a05b 2291 polarssl_printf( "failed\n" );
HannesTschofenig 0:796d0f61a05b 2292
HannesTschofenig 0:796d0f61a05b 2293 ret = 1;
HannesTschofenig 0:796d0f61a05b 2294 goto cleanup;
HannesTschofenig 0:796d0f61a05b 2295 }
HannesTschofenig 0:796d0f61a05b 2296
HannesTschofenig 0:796d0f61a05b 2297 if( verbose != 0 )
HannesTschofenig 0:796d0f61a05b 2298 polarssl_printf( "passed\n" );
HannesTschofenig 0:796d0f61a05b 2299
HannesTschofenig 0:796d0f61a05b 2300 if( verbose != 0 )
HannesTschofenig 0:796d0f61a05b 2301 polarssl_printf( " MPI test #5 (simple gcd): " );
HannesTschofenig 0:796d0f61a05b 2302
HannesTschofenig 0:796d0f61a05b 2303 for ( i = 0; i < GCD_PAIR_COUNT; i++)
HannesTschofenig 0:796d0f61a05b 2304 {
HannesTschofenig 0:796d0f61a05b 2305 MPI_CHK( mpi_lset( &X, gcd_pairs[i][0] ) );
HannesTschofenig 0:796d0f61a05b 2306 MPI_CHK( mpi_lset( &Y, gcd_pairs[i][1] ) );
HannesTschofenig 0:796d0f61a05b 2307
HannesTschofenig 0:796d0f61a05b 2308 MPI_CHK( mpi_gcd( &A, &X, &Y ) );
HannesTschofenig 0:796d0f61a05b 2309
HannesTschofenig 0:796d0f61a05b 2310 if( mpi_cmp_int( &A, gcd_pairs[i][2] ) != 0 )
HannesTschofenig 0:796d0f61a05b 2311 {
HannesTschofenig 0:796d0f61a05b 2312 if( verbose != 0 )
HannesTschofenig 0:796d0f61a05b 2313 polarssl_printf( "failed at %d\n", i );
HannesTschofenig 0:796d0f61a05b 2314
HannesTschofenig 0:796d0f61a05b 2315 ret = 1;
HannesTschofenig 0:796d0f61a05b 2316 goto cleanup;
HannesTschofenig 0:796d0f61a05b 2317 }
HannesTschofenig 0:796d0f61a05b 2318 }
HannesTschofenig 0:796d0f61a05b 2319
HannesTschofenig 0:796d0f61a05b 2320 if( verbose != 0 )
HannesTschofenig 0:796d0f61a05b 2321 polarssl_printf( "passed\n" );
HannesTschofenig 0:796d0f61a05b 2322
HannesTschofenig 0:796d0f61a05b 2323 cleanup:
HannesTschofenig 0:796d0f61a05b 2324
HannesTschofenig 0:796d0f61a05b 2325 if( ret != 0 && verbose != 0 )
HannesTschofenig 0:796d0f61a05b 2326 polarssl_printf( "Unexpected error, return code = %08X\n", ret );
HannesTschofenig 0:796d0f61a05b 2327
HannesTschofenig 0:796d0f61a05b 2328 mpi_free( &A ); mpi_free( &E ); mpi_free( &N ); mpi_free( &X );
HannesTschofenig 0:796d0f61a05b 2329 mpi_free( &Y ); mpi_free( &U ); mpi_free( &V );
HannesTschofenig 0:796d0f61a05b 2330
HannesTschofenig 0:796d0f61a05b 2331 if( verbose != 0 )
HannesTschofenig 0:796d0f61a05b 2332 polarssl_printf( "\n" );
HannesTschofenig 0:796d0f61a05b 2333
HannesTschofenig 0:796d0f61a05b 2334 return( ret );
HannesTschofenig 0:796d0f61a05b 2335 }
HannesTschofenig 0:796d0f61a05b 2336
HannesTschofenig 0:796d0f61a05b 2337 #endif /* POLARSSL_SELF_TEST */
HannesTschofenig 0:796d0f61a05b 2338
HannesTschofenig 0:796d0f61a05b 2339 #endif /* POLARSSL_BIGNUM_C */
HannesTschofenig 0:796d0f61a05b 2340
HannesTschofenig 0:796d0f61a05b 2341