BA / SerialCom

Important changes to repositories hosted on mbed.com

Mbed hosted mercurial repositories are deprecated and are due to be permanently deleted in July 2026.

To keep a copy of this software download the repository Zip archive or clone locally using Mercurial.

It is also possible to export all your personal repositories from the account settings page.

Fork of OmniWheels by Gustav Atmel

mbed-os/features/mbedtls/src/bignum.c@1:9c5af431a1f1, 2018-05-01 (annotated)

Committer:
gustavatmel
Date:
Tue May 01 15:47:08 2018 +0000
Revision:
1:9c5af431a1f1
sdf

Who changed what in which revision?

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