《密码技术与物联网安全：mbedtls开发实战》 —2.9.2　大数运算示例

2.9.2　大数运算示例

完成Base64示例之后，本节继续在Zephyr平台运行一个大数运算示例。大数运算是密码学中常用的计算手段之一，是公钥密码和数字签名算法的基础。所谓大数运算，就是运算过程的参数或结果超过了计算机编程语言中基本数据类型所表示的范围，例如C语言中64位无符号整数的表示范围为0～1844 6744 0737 0955 1615。虽然64位无符号整数的表示范围已经很大，但在密码学范畴这种类型的整数依然不能满足需求。mbedtls支持大数运算，大数运算的具体实现详见{mbedtls代码仓库}/library/bignum.c。下面通过大数乘法运算、大数模指数运算和大数模逆运算这3个示例说明bignum相关接口的使用方法。在本示例***有A、E和N三组参数参与运算，先计算一组大数乘法X = A * E，再计算一组大数模指数运算X = A ^ E mod，最后计算一组大数模逆运算。本节示例相关参数和计算结果如图2-5所示。

与本章其他示例相似，本节示例也包括main.c、mbedtls_config.h、prj.conf和CMake-Lists.txt等文件。

1.示例代码

在示例代码中的大数运算中，大数乘法运算、大数模指数运算与实数域中的概念非常相似，但是模逆运算和实数域中的倒数运算存在很大差异。在实数域中，2与0.5的乘积为1，则称2的倒数为0.5，在有限域（此处的模逆运算）中，2 X 8 mod 17 = 1，则称2关于模17的逆元为8。总之，实数域中倒数的概念与乘积为1有关，而有限域中逆元的概念与余数为1有关。示例代码如代码清单2-10所示。

图2-5　大数运算示例

代码清单2-10　bignum 示例代码

#include <zephyr.h>

#include <string.h>

#include <stdio.h>

#include "mbedtls/bignum.h"

#include "mbedtls/platform.h"

static void dump_buf(char *buf, size_t len)

{

    for (int i = 0; i < len; i++) {

        mbedtls_printf("%c%s", buf[i], (i + 1) % 32 ? "" : "\n\t");

    }

    mbedtls_printf("\n");

}

int main(void)

{

    size_t olen;

    char buf[256];

    mbedtls_mpi A, E, N, X;

    mbedtls_platform_set_printf(printf);

    mbedtls_mpi_init(&A);

    mbedtls_mpi_init(&E);

    mbedtls_mpi_init(&N);

    mbedtls_mpi_init(&X);

    mbedtls_mpi_read_string(&A, 16,

        "EFE021C2645FD1DC586E69184AF4A31E" \

        "D5F53E93B5F123FA41680867BA110131" \

        "944FE7952E2517337780CB0DB80E61AA" \

        "E7C8DDC6C5C6AADEB34EB38A2F40D5E6" );

    mbedtls_mpi_read_string(&E, 16,

        "B2E7EFD37075B9F03FF989C7C5051C20" \

        "34D2A323810251127E7BF8625A4F49A5" \

        "F3E27F4DA8BD59C47D6DAABA4C8127BD" \

        "5B5C25763222FEFCCFC38B832366C29E" );

    mbedtls_mpi_read_string(&N, 16,

        "0066A198186C18C10B2F5ED9B522752A" \

        "9830B69916E535C8F047518A889A43A5" \

        "94B6BED27A168D31D4A52F88925AA8F5" );

    mbedtls_mpi_mul_mpi(&X, &A, &N);

    mbedtls_mpi_write_string(&X, 16, buf, 256, &olen);

    mbedtls_printf("\n  X = A * N = \n\t");

    dump_buf(buf, olen);

    mbedtls_mpi_exp_mod(&X, &A, &E, &N, NULL);

    mbedtls_mpi_write_string(&X, 16, buf, 256, &olen);

    mbedtls_printf("\n  X = A^E mode N = \n\t");

    dump_buf(buf, olen);

    mbedtls_mpi_inv_mod( &X, &A, &N);

    mbedtls_mpi_write_string(&X, 16, buf, 256, &olen);

    mbedtls_printf("\n  X = A^-1 mod N = \n\t");

    dump_buf(buf, olen);

    mbedtls_mpi_free(&A);

    mbedtls_mpi_free(&E);

    mbedtls_mpi_free(&N);

    mbedtls_mpi_free(&X);

    return 0;  

}

示例代码中相关接口描述如表2-8所示。

表2-8　大数运算示例相关接口描述

接　　口    描　　述

mbedtls_mpi_init    初始化大数结构体

mbedtls_mpi_read_string     将字符串读取到大数结构体中

mbedtls_mpi_write_string    将大数结构体以字符串形式写入数组中

mbedtls_mpi_mul_mpi  大数乘法运算

mbedtls_mpi_exp_mod 大数模指数运算

mbedtls_mpi_inv_mod  大数模逆运算

mbedtls_mpi_free   释放大数结构体

2.编写 mbedtls_config.h

为了使mbedtls支持大数运算，需要在配置文件中增加MBEDTLS_BIGNUM_C定义。mbedtls_config.h的其他部分与上一节介绍的模板文件相同。

3.编写 prj.conf

由于大数运算需要消耗更大的栈空间，建议把MAIN_STACK_SIZE设置为4096字节或更大值，默认情况下MAIN_STACK_SIZE的大小为仅1024字节。另外大数运算过程中还会使用动态内存分配接口，可以在配置文件中定义mbedtls栈大小，示例中将mbedtls的堆大小设置为4096字节。prj.conf配置文件内容如下：

CONFIG_STDOUT_CONSOLE=y

CONFIG_MAIN_STACK_SIZE=4096

CONFIG_MBEDTLS=y

CONFIG_MBEDTLS_BUILTIN=y

CONFIG_MBEDTLS_ENABLE_HEAP=y

CONFIG_MBEDTLS_HEAP_SIZE=4096

CONFIG_MBEDTLS_CFG_FILE="mbedtls_config.h"

4.编写 CMakeLists.txt

CMakeLists.txt文件内容与上一节完全相同。

5.编译与运行

基础示例默认会运行在necluo_f429zi 平台，若需要运行在仿真平台只需将-DBOARD参数指定为native_posix即可，具体过程可回顾2.8.4节。编译过程完成后，控制台将输出Flash空间和RAM空间的消耗情况。由于增加了mbedtls自定义栈空间，栈空间占4KB，另外还增加了4KB的Zephyr主线程栈空间，所以大数运算的内存消耗增加至11KB左右，约占STM32F429ZI整个RAM空间的4.4%。

应用程序将把运行结果输出至串口控制台，所以应用程序下载至开发板运行之前需新建终端，并通过minicom工具打开指定串口。操作指令如下：

# 请根据实际情况修改串口名称

$ sudo minicom -b 115200 -D /dev/ttyACM0

编译与运行过程如下：

# 进入示例代码文件夹

$ cd 02_start/zephyr/bignum

# 新建一个build目录，用于存放临时文件

$ mkdir -p build && cd build

# 通过cmake指令生成nucleo_f429zi平台makefile文件

$ cmake -DBOARD=nucleo_f429zi ..

# 编译并查看资源消耗情况

$ make

Memory region         Used Size  Region Size  %age Used

           FLASH:       22760 B         2 MB      1.09%

             CCM:          0 GB        64 KB      0.00%

            SRAM:       11548 B       256 KB      4.41%

        IDT_LIST:         200 B         2 KB      9.77%

# 下载到开发板运行

$ make flash

# 串口控制台输出

  X = A * N =

        602AB7ECA597A3D6B56FF9829A5E8B85

        9E857EA95A03512E2BAE7391688D264A

        A5663B0341DB9CCFD2C4C5F421FEC814

        8001B72E848A38CAE1C65F78E56ABDEF

        E12D3C039B8A02D6BE593F0BBBDA56F1

        ECF677152EF804370C1A305CAF3B5BF1

        30879B56C61DE584A0F53A2447A51E

  X = A^E mode N =

        36E139AEA55215609D2816998ED020BB

        BD96C37890F65171D948E9BC7CBAA4D9

        325D24D6A3C12710F10A09FA08AB87

  X = A^-1 mod N =

        3A0AAEDD7E784FC07D8F9EC6E3BFD5C3

        DBA76456363A10869622EAC2DD84ECC5

        B8A74DAC4D09E03B5E0BE779F2DF61