精华内容
下载资源
问答
  • 2018-03-07 15:47:49

    一、引言

     

    随着网络技术的飞速发展,信息安全性已成为亟待解决的问题。公钥密码体制中,解密和加密密钥不同,解密和加密可分离,通信双方无须事先交换密钥就可建立起保密通信,较好地解决了传统密码体制在网络通信中出现的问题。另外,随着电子商务的发展,网络上资金的电子交换日益频繁,如何防止信息的伪造和欺骗也成为非常重要的问题。数字签名可以起到身份认证、核准数据完整性的作用。目前关于数字签名的研究主要集中基于公钥密码体制的数字签名。

    公钥密码体制的特点是:为每个用户产生一对密钥(PK和SK);PK公开,SK保密;从PK推出SK是很困难的;A、B双方通信时,A通过任何途径取得B的公钥,用B的公钥加密信息。加密后的信息可通过任何不安全信道发送。B收到密文信息后,用自己私钥解密恢复出明文。

    公钥密码体制已成为确保信息的安全性的关键技术。RSA公钥密码体制到目前为止还是一种认可为安全的体制。本文详述了RSA算法和用RSA算法实现数字签名的理论,以及它们在实际应用中的实现。

     

    二、RSA算法和RSA数字签名算法的理论描述

     

    1  RSA算法

       RSA算法的理论基础是一种特殊的可逆模幂运算。

       n是两个不同奇素数p和q的积,即:n=pq, j(n)=(p-1)(q-1)。

       定义密钥空间  k={(n,p,q,d,e)|n=pq,p和q是素数,deº1 mod j(n),e为随机整数},

       对每一个k=(n,p,q,d,e),

       定义加密变换为   Ek(x)=xb mod n,xÎZn;

       解密变换为       Dk(x)=ya mod n,yÎZnZn为整数集合。

       公开n和b,保密p,q和a.

       为证明加密变换Ek和解密变换 Dk满足Dk(Ek(x))=x,这里不加证明的引用下面两个定理:

    定理1(Euler)对任意的aÎZn*,有aj(n)º1 mod n,其中Zn*={xÎZn|gcd(x,n)=1},j(·)表示Euler函数。

    定理2  设p和q是两个不同的素数,n=pq, j(n)=(p-1)(q-1),对任意的xÎZn及任意的非负整数k,有 xkj(n)+1ºx mod n.

    现在来证明RSA算法的加密变换和解密变换的正确性。

    证明:  对于加密变换Ek和解密变换Dk。因为abº1 mod j(n),所以可设ab=tj(n)+1,t是整数且t³1。对于任意的xÎZn,有Dk(Ek(x))ºDk(xbº(xb)aºxtj(n)+1ºx mod n.因此解密过程是正确的。

     

    2 RSA数字签名算法

       RSA数字签名算法的过程为:A明文m用解密变换作: (公钥用来加密,私钥用来解密,数字签名是用私钥完成的,所以称为解密变换,这与onu sdk中一致) Dk (m)=md mod n,其中dnA的私人密钥,只有A才知道它;B收到A的签名后,用A的公钥和加密变换得到明文,因: Ek(s)= Ek(Dk (m))= (md)e mod n, deº1 mod j(n)即de=lj(n)+1,根据欧拉定理mj(n)=1 mod n,所以Ek(s)=mlj(n)+1=[mj(n)]em=m mod n。若明文m和签名s一起送给用户B,B可以确信信息确实是A发送的。同时A也不能否认送给这个信息,因为除了A本人外,其他任何人都无法由明文m产生s.因此RSA数字签名方案是可行的。

       但是RSA数字签名算法存在着因计算方法本身同构造成签名易被伪造和计算时间长的弱点,因此实际对文件签名前,需要对消息做MD5变换。

       MD5函数是一种单向散列函数,它将任意长度的消息压缩成128位的消息摘要。应用MD5的单向性(即给定散列值,计算消息很难)和抗碰撞性(即给定消息M,要找到另一消息M’ 并满足两者的散列值很难),可以实现信息的完整性检验。另外该函数的设计不基于任何假设和密码体制而直接构造,执行的速度快,是一种被广泛认可的单向散列算法。

     

    三、RSA算法的实现

     

    RSA算法的实现分为:生成密钥,加密,解密。

    数据结构

    RSA密码系统的安全性依赖于大数分解的难度,一般建议用户选择的素数pq至少为100位,则n=pq是至少为200位的十进制数。因此实现RSA算法有必要定义大数的数据结构如图一所示。

    typedef struct

    {

      unsigned long int bn[MAX_LENGTH];

      unsigned int size;

    }BigNum

                 图2 大数的数据结构

    密钥生成,加密和解密涉及到一些大数的基本运算。定义大数的基本运算库,包括加、减、乘、除、取模运算等,其中最重要的模乘运算和模幂运算。

    模幂算法是加密解密的核心算法。计算模幂的一种有效算法是“平方-”方法,通过对指数的二进制化来实现。8

    过程如图1

    Procedure modmult

     begin

    typedef struct {

      unsigned int bits; /* 公钥n的位数  */

      unsigned char modulus[MAX_RSA_ LEN] ;/*公钥n*/          

      unsigned char exponent[MAX_RSA_LEN]; /*公钥e*/

    }  RSA_PUBLIC_KEY;

                      图3 RSA公钥

    Z=1

    for i=l-1 downto 0 do:

          begin

                   Z=Z 2 mod n;

          if bi=1 then Z=Z*x mod n;

              end

        end

      图一

    密钥的生成

    2.1 RSA公钥和私钥的结构定义

       根据文档PKCS#1定义RSA公钥和私钥分别如图2和图3。理论上讲,RSA私钥只需包括解密模数和解密指数。但是为加快RSA解密计算的效率,采用中国剩余定理算法,因此RSA私钥包含p,q,d mod (p-1),d mod (q-1),q-1 mod p,其中p,q为大素数, d mod (p-1),   d mod (q-1),q-1 mod p由计算过程生成。

     

    2.2 生成密钥步骤

    typedef struct {

      unsigned int bits; /*公钥n的长度*/

      unsigned char modulus[MAX_RSA_LEN];  /*公钥n */           

      unsigned char publicExponent[MAX_RSA_ LEN]; /*公钥e */

      unsigned char exponent[MAX_RSA_LEN];  /*私钥d*/

      unsigned char prime[2][MAX_RSA_ LEN]; /*两个素数因子*/     

      unsigned char primeExponent[2][MAX_RSA_PRIME_LEN];

      unsigned char coefficient[MAX_RSA_PRIME_LEN]; 

    } RSA_PRIVATE_KEY;

                    图4  RSA私钥

    生成RSA密钥需完成下列步骤:

      (1) 选择e的值为3或者25537;

      (2) 随机生成大素数p,直到gcd (e,p-1)=1;

         其中gcd(a,b)表示a,b取最大公约数

      (3) 随机生成不同于p的大素数q,直到

         gcd (e,q-1)=1;

      (4) 计算n=pq , j(n)=(p-1)(q-1);

      (5) 计算d,满足deº1 (mod j(n));

      (6) 计算d mod (p-1), d mod (q-1);

      (7) 计算q-1 mod p;

      (8) n,e放入RSA公钥;将n,e,d mod (p-1),d mod (q-1) q-1 mod p放入RSA私钥。

       随机素数的产生可分为两个模块:

     

    2.2.1 随机数的产生                                 

        随机数不仅用于密钥生成,也用作公钥加密时的填充字符。它必须具有足够的随机性,以防止破译者掌握随机数的规律性后重现密钥的配制过程或者探测到加密块中的明文。因为在计算机上不可能产生真正的随机数,实际采用周期大于2256位的伪随机序列发生器。

    实现过程为:

        (1) 记录相邻两次敲击键盘的时间间隔,直到不再需要随机事件。

        (2) MD5计算,直到不再需要伪随机数。

     

    2.2.2 素数的产生

        对随机数作素性检测,若通过则为素数;否则增加一个步长后再做素性检测,直到找出素数。素性检测采用Fermat测试。这个算法的理论依据是费尔马小定理:如果m是一个素数,且a不是m的倍数,那么根据费尔马小定理有:m-1=1 ( mod m) 实际应用时:m-1 = 1 ( mod m)Û a m = a ( mod m) Ûa= a m ( mod m) 因此对于整数m,只需计算m ( mod m),再将结果与a比较,如果两者相同,则m为素数。选取a=2,则a一定不会是任何素数的倍数。

     

    加密过程

    加密规则为:Ek(x)=xb mod n,xÎZn

    加密过程的输入为:明文数据D,模数n, 加密指数e(公钥加密)或解密指数d(私钥加密)。输出为密文。D的长度不超过[log2n]-11,以确保转换为PKCS格式时,填充串的数目不为0

    (1)    格式化明文。  采用PKCS格式: EB = 00 || BT || PS || 00 || D   其中BT表示块的类型,PS为填充串,D为明文数据。开头为0确保EB长度大于k。对公钥加密BT=02,对私钥解密BT=01。当BT=02时,PS为非0随机数;当BT=01PS值为FF

        (2) 明文由字符型数据转换成整型数据。

        (3) RSA计算。   为整数加密块x作模幂运算:y = x^c mod n0 <= y <n,其中y

           为密文,公钥加密时,c为公钥加密指数e;私钥加密时,c为私钥加密指数d

        (4) 密文由整型数据转换成字符型数据。

    解密过程

      解密规则为      Dk(x)=yc mod n,yÎZnZn为整数集合,x为密文。

      解密过程的输入为:密文ED;模数n;加密指数e(公钥解密)或解密指数d(私钥解密),结果为明文。

         (1) 密文整型化。

         (2) RSA计算。  对密文做模幂运算:x = y^c mod n,  0 <= x < n .,其中x为明文。

         (3) 此时明文为整型数据,转换为ASCII型数据,得到PKCS格式的明文。

     (4) PKCS格式明文中分离出原明文。 PKCS格式分离明文的过程也是检查

        数据完整性的过程。若出现以下问题则解密失败:不能清楚的分割;填充字符

        少于64位或与BT所注明的类型不匹配;BT与实际操作类型不符。

     

    四、           RSA数字签名算法的实现

     

    RSA数字签名算法,包括签名算法和验证签名算法。首先用MD5算法对信息作散列计算。签名的过程需用户的私钥,验证过程需用户的公钥。A用签名算法将字符串形式的消息处理成签名;B用验证签名算法验证签名是否是A对消息的签名,确认是A发送的消息;消息没有被攥改过;A一定发送过消息。

     

    签名算法

      签名算法包括三步:消息摘要计算,RSA加密。

    (1)    消息摘要计算。  消息在签名前首先通过MD5计算,生成128位的消息摘要

          digest

    (2)    对摘要作RSA计算。  用加密算法,采用签名者的私钥加密消息摘要,得到加密后的字符串。加密算法中使用的加密块为01类型。

     

    验证签名算法

       验证签名算法包括两步:RSA解密得签名者的消息摘要,验证者对原消息计算摘要,比较两个消息摘要。验证签名的过程输入为消息,签名者的公钥,签名;输出为验证的结果,即是否是正确的签名。

    (1)    RSA解密。  签名实际是加密的字符串。用3.5所述的解密算法,采用签名者的公钥对这个加密的字符串解密。解密的结果应为128位的消息摘要。在解密过程中,若出现得到的加密块的类型不是01,则解密失败。签名不正确。

    (2)    消息摘要计算和比较。  验证者对消息用MD5算法重新计算,得到验证者自己的消息摘要。验证者比较解密得到的消息摘要和自己的消息摘要,如果两者相同,则验证成功,可以确认消息的完整性及签名确实为签名者的;否则,验证失败。

     

    五、RSA算法的时间复杂性

     

       RSA算法的时间复杂性取决于它所设计的几个基本运算的时间复杂性。

       密钥生成过程时间主要是生成随机素数的时间及计算公钥和私钥的模乘法的时间。生成随机素数的时间在于完成对随机大数的Fermat测试的时间,Fermat测试的时间复杂度为O((log2n)3)n所测试的整数。模乘法的计算方法采取先计算两个数的乘积,再取模n,时间复杂性为O((log2n)2)

       RSA加密解密计算的时间主要是模幂运算的时间,即形式为xc mod n的函数的运算时间。模幂算法采取平方乘算法,设lc的长度,则计算xc mod n至多需要2l次模乘法,因为l£[log2n]+1,所以模幂运算能在时间O((log2n)3)内完成。因此,RSA的加密和解密均可在多项式时间内完成。

     

                                   六、结束语

     

       本文讨论了RSA算法的基本原理和基本实现。RSA算法是一种安全技术,但是RSA算法的安全性只是一种计算安全性,绝不是无条件的安全性,这是由它的理论基础决定的。因此,在实现RSA算法的过程中,每一步都应尽量从安全性考虑。本文采取的一些主要算法是目前在数学上被认可的安全的算法之一。

        本文所提到的算法及实现原理已在作为设计的安全电子邮件系统中完全实现并获得满意的效果。

    更多相关内容
  • RSA数字签名算法的具体实现
  • 基于RSA数字签名算法的实现,能够用在VC6.0 平台运行。RSA加密算法中,消息发送方是用公钥对数据进行加密,消息接收方用私钥对密文进行解密获得消息;在RSA签名算法中,消息发布者用私钥对消息进行签名,消息接收...
  • 本代码主要用于实现RSA数字签名算法,用java进行编程,能够完整的在eclipse上运行,具体可用于密码学的课程设计等。
  • RSA算法和RSA数字签名算法的实现

    热门讨论 2011-05-29 14:01:52
    RSA算法和RSA数字签名算法的实现,RSA算法和RSA数字签名算法的实现,RSA算法和RSA数字签名算法的实现
  • mbedtls系列文章 mbedtls | 01 - 移植mbedtls库到STM32的两种方法 mbedtls | 02 - 伪随机数生成器(ctr_drbg)的配置与使用 mbedtls | 03 - 单向散列算法...mbedtls | 06 - 非对称加密算法的配置与使用(RSA算法) mbe

    mbedtls系列文章

    Demo工程源码

    本工程基于STM32L41RCT6开发板,包含了本系列文章中所编写的所有Demo,持续更新……



    一、数字签名算法

    1. 什么是数字签名

    数字签名类似于盖章和签字,数字签名可以检查消息是否被篡改、并验证消息的可靠性,因为私钥只有签名者持有,所以还可以防止否认。

    2. 数字签名算法

    RSA数字签名

    RSA数字签名算法基于RSA非对称加密算法,在用于数字签名时公钥和私钥的用法刚好相反:

    • 发送方使用私钥对消息执行加密操作 = 对消息进行签名;
    • 接收方使用公钥对签名进行解密 = 对签名进行认证;

    RSA签名算法还需要包括填充方法,有两种:PKCS1-V1.5和PSS(使用随机数填充,推荐使用)。

    DSA算法

    ECDSA算法

    在相同的安全等级下,ECDSA算法具有秘钥短、执行效率高的特点,更适合物联网应用。

    二、RSA数字签名功能模块的配置与使用

    1. 配置宏

    使用RSA功能需要提前开启伪随机数生成器(依赖AES算法、SHA256算法、MD通用接口),其中伪随机数生成器的硬件适配移植实现已经讲述,请参考对应的第二篇博客,不再赘述。

    综合上述,本实验中需要开启的宏如下表:

    宏定义功能
    MBEDTLS_NO_DEFAULT_ENTROPY_SOURCES不使用默认熵源(如果已有、要屏蔽该宏)
    MBEDTLS_NO_PLATFORM_ENTROPY不使用系统内置熵源
    MBEDTLS_AES_C使用AES算法
    MBEDTLS_ENTROPY_C使能熵源模块
    MBEDTLS_CTR_DRBG_C使能随机数模块
    MBEDTLS_SHA256_C使能SHA256算法
    MBEDTLS_MD_C开启MD通用接口
    MBEDTLS_AES_ROM_TABLES使能预定义S盒(节约内存空间)
    MBEDTLS_BIGNUM_C开启大数运算
    MBEDTLS_GENPRIME开启生成素数
    MBEDTLS_OID_C开启OID数据结构模块
    MBEDTLS_RSA_C开启RSA算法
    MBEDTLS_PKCS1_V21开启PKCS#1 v2.1填充方案(OAEP)

    新建配置文件mbedtls_config_rsa_sign.h,编写以下内容:

    /**
     * @brief   Minimal configuration for RSA Sign Function
     * @author  mculover666
     * @date    2020/10/03
    */
    
    #ifndef _MBEDTLS_CONFIG_RSA_SIGN_H_
    #define _MBEDTLS_CONFIG_RSA_SIGN_H_
    
    /* System support */
    #define MBEDTLS_HAVE_ASM
    //#define MBEDTLS_HAVE_TIME
    
    /* mbed feature support */
    #define MBEDTLS_ENTROPY_HARDWARE_ALT
    //#define MBEDTLS_NO_DEFAULT_ENTROPY_SOURCES
    #define MBEDTLS_NO_PLATFORM_ENTROPY
    
    /* mbed modules */
    #define MBEDTLS_AES_C
    #define MBEDTLS_AES_ROM_TABLES
    #define MBEDTLS_CTR_DRBG_C
    #define MBEDTLS_ENTROPY_C
    #define MBEDTLS_SHA256_C
    #define MBEDTLS_MD_C
    #define MBEDTLS_BIGNUM_C
    #define MBEDTLS_GENPRIME
    #define MBEDTLS_OID_C
    #define MBEDTLS_RSA_C
    #define MBEDTLS_PKCS1_V21
    
    #include "mbedtls/check_config.h"
    
    #endif /* _MBEDTLS_CONFIG_RSA_SIGN_H_ */
    
    

    在MDK中设置使用该配置文件:

    2. RSA数字签名功能模块API说明

    使用该功能模块需要包含头文件:

    #include "mbedtls/rsa.h"
    

    ① RSA签名接口

    /**
     * \brief          This function performs a private RSA operation to sign
     *                 a message digest using PKCS#1.
     *
     *                 It is the generic wrapper for performing a PKCS#1
     *                 signature using the \p mode from the context.
     *
     * \note           The \p sig buffer must be as large as the size
     *                 of \p ctx->N. For example, 128 Bytes if RSA-1024 is used.
     *
     * \note           For PKCS#1 v2.1 encoding, see comments on
     *                 mbedtls_rsa_rsassa_pss_sign() for details on
     *                 \p md_alg and \p hash_id.
     *
     * \deprecated     It is deprecated and discouraged to call this function
     *                 in #MBEDTLS_RSA_PUBLIC mode. Future versions of the library
     *                 are likely to remove the \p mode argument and have it
     *                 implicitly set to #MBEDTLS_RSA_PRIVATE.
     *
     * \note           Alternative implementations of RSA need not support
     *                 mode being set to #MBEDTLS_RSA_PUBLIC and might instead
     *                 return #MBEDTLS_ERR_PLATFORM_FEATURE_UNSUPPORTED.
     *
     * \param ctx      The initialized RSA context to use.
     * \param f_rng    The RNG function to use. If the padding mode is PKCS#1 v2.1,
     *                 this must be provided. If the padding mode is PKCS#1 v1.5 and
     *                 \p mode is #MBEDTLS_RSA_PRIVATE, it is used for blinding
     *                 and should be provided; see mbedtls_rsa_private() for more
     *                 more. It is ignored otherwise.
     * \param p_rng    The RNG context to be passed to \p f_rng. This may be \c NULL
     *                 if \p f_rng is \c NULL or doesn't need a context argument.
     * \param mode     The mode of operation. This must be either
     *                 #MBEDTLS_RSA_PRIVATE or #MBEDTLS_RSA_PUBLIC (deprecated).
     * \param md_alg   The message-digest algorithm used to hash the original data.
     *                 Use #MBEDTLS_MD_NONE for signing raw data.
     * \param hashlen  The length of the message digest.
     *                 Ths is only used if \p md_alg is #MBEDTLS_MD_NONE.
     * \param hash     The buffer holding the message digest or raw data.
     *                 If \p md_alg is #MBEDTLS_MD_NONE, this must be a readable
     *                 buffer of length \p hashlen Bytes. If \p md_alg is not
     *                 #MBEDTLS_MD_NONE, it must be a readable buffer of length
     *                 the size of the hash corresponding to \p md_alg.
     * \param sig      The buffer to hold the signature. This must be a writable
     *                 buffer of length \c ctx->len Bytes. For example, \c 256 Bytes
     *                 for an 2048-bit RSA modulus. A buffer length of
     *                 #MBEDTLS_MPI_MAX_SIZE is always safe.
     *
     * \return         \c 0 if the signing operation was successful.
     * \return         An \c MBEDTLS_ERR_RSA_XXX error code on failure.
     */
    int mbedtls_rsa_pkcs1_sign( mbedtls_rsa_context *ctx,
                        int (*f_rng)(void *, unsigned char *, size_t),
                        void *p_rng,
                        int mode,
                        mbedtls_md_type_t md_alg,
                        unsigned int hashlen,
                        const unsigned char *hash,
                        unsigned char *sig );
    

    ② RSA验证签名接口

    /**
     * \brief          This function performs a public RSA operation and checks
     *                 the message digest.
     *
     *                 This is the generic wrapper for performing a PKCS#1
     *                 verification using the mode from the context.
     *
     * \note           For PKCS#1 v2.1 encoding, see comments on
     *                 mbedtls_rsa_rsassa_pss_verify() about \p md_alg and
     *                 \p hash_id.
     *
     * \deprecated     It is deprecated and discouraged to call this function
     *                 in #MBEDTLS_RSA_PRIVATE mode. Future versions of the library
     *                 are likely to remove the \p mode argument and have it
     *                 set to #MBEDTLS_RSA_PUBLIC.
     *
     * \note           Alternative implementations of RSA need not support
     *                 mode being set to #MBEDTLS_RSA_PRIVATE and might instead
     *                 return #MBEDTLS_ERR_PLATFORM_FEATURE_UNSUPPORTED.
     *
     * \param ctx      The initialized RSA public key context to use.
     * \param f_rng    The RNG function to use. If \p mode is #MBEDTLS_RSA_PRIVATE,
     *                 this is used for blinding and should be provided; see
     *                 mbedtls_rsa_private() for more. Otherwise, it is ignored.
     * \param p_rng    The RNG context to be passed to \p f_rng. This may be
     *                 \c NULL if \p f_rng is \c NULL or doesn't need a context.
     * \param mode     The mode of operation. This must be either
     *                 #MBEDTLS_RSA_PUBLIC or #MBEDTLS_RSA_PRIVATE (deprecated).
     * \param md_alg   The message-digest algorithm used to hash the original data.
     *                 Use #MBEDTLS_MD_NONE for signing raw data.
     * \param hashlen  The length of the message digest.
     *                 This is only used if \p md_alg is #MBEDTLS_MD_NONE.
     * \param hash     The buffer holding the message digest or raw data.
     *                 If \p md_alg is #MBEDTLS_MD_NONE, this must be a readable
     *                 buffer of length \p hashlen Bytes. If \p md_alg is not
     *                 #MBEDTLS_MD_NONE, it must be a readable buffer of length
     *                 the size of the hash corresponding to \p md_alg.
     * \param sig      The buffer holding the signature. This must be a readable
     *                 buffer of length \c ctx->len Bytes. For example, \c 256 Bytes
     *                 for an 2048-bit RSA modulus.
     *
     * \return         \c 0 if the verify operation was successful.
     * \return         An \c MBEDTLS_ERR_RSA_XXX error code on failure.
     */
    int mbedtls_rsa_pkcs1_verify( mbedtls_rsa_context *ctx,
                          int (*f_rng)(void *, unsigned char *, size_t),
                          void *p_rng,
                          int mode,
                          mbedtls_md_type_t md_alg,
                          unsigned int hashlen,
                          const unsigned char *hash,
                          const unsigned char *sig );
    

    3. 编写测试函数

    新建文件mbedtls_rsa_sign_test.c,编写以下测试内容:

    /**
     * @brief   RSA Sign Function demo
     * @author  mculover666
     * @date    2020/10/03
    */
    
    #if !defined(MBEDTLS_CONFIG_FILE)
    #include "mbedtls/config.h"
    #else
    #include MBEDTLS_CONFIG_FILE
    #endif
    
    #if defined(MBEDTLS_RSA_C)
    
    #include <stdio.h>
    #include "string.h"
    #include "mbedtls/entropy.h"
    #include "mbedtls/ctr_drbg.h"
    #include "mbedtls/rsa.h"
    
    static char buf[516];
    
    static void dump_rsa_key(mbedtls_rsa_context *ctx)
    {
        size_t olen;
        
        printf("\n  +++++++++++++++++ rsa keypair +++++++++++++++++\n\n");
        mbedtls_mpi_write_string(&ctx->N , 16, buf, sizeof(buf), &olen);
        printf("N: %s\n", buf); 
    
        mbedtls_mpi_write_string(&ctx->E , 16, buf, sizeof(buf), &olen);
        printf("E: %s\n", buf);
    
        mbedtls_mpi_write_string(&ctx->D , 16, buf, sizeof(buf), &olen);
        printf("D: %s\n", buf);
    
        mbedtls_mpi_write_string(&ctx->P , 16, buf, sizeof(buf), &olen);
        printf("P: %s\n", buf);
    
        mbedtls_mpi_write_string(&ctx->Q , 16, buf, sizeof(buf), &olen);
        printf("Q: %s\n", buf);
    
        mbedtls_mpi_write_string(&ctx->DP, 16, buf, sizeof(buf), &olen);
        printf("DP: %s\n", buf);
    
        mbedtls_mpi_write_string(&ctx->DQ, 16, buf, sizeof(buf), &olen);
        printf("DQ: %s\n", buf);
    
        mbedtls_mpi_write_string(&ctx->QP, 16, buf, sizeof(buf), &olen);
        printf("QP: %s\n", buf);
        printf("\n  +++++++++++++++++ rsa keypair +++++++++++++++++\n\n");
    }
    
    static void dump_buf(uint8_t *buf, uint32_t len)
    {
        int i;
        
        for (i = 0; i < len; i++) {
            printf("%s%02X%s", i % 16 == 0 ? "\r\n\t" : " ", 
                               buf[i], 
                               i == len - 1 ? "\r\n" : "");
        }
    }
    
    static uint8_t output_buf[2048/8];
    
    int mbedtls_rsa_sign_test(void)
    {
        int ret;
        const char* msg = "HelloWorld";
       
        const char *pers = "rsa_sign_test";
        mbedtls_entropy_context entropy;
        mbedtls_ctr_drbg_context ctr_drbg;
        mbedtls_rsa_context ctx;
    
        /* 1. init structure */
        mbedtls_entropy_init(&entropy);
        mbedtls_ctr_drbg_init(&ctr_drbg);
        mbedtls_rsa_init(&ctx, MBEDTLS_RSA_PKCS_V21, MBEDTLS_MD_SHA256);
        
        /* 2. update seed with we own interface ported */
        printf( "\n  . Seeding the random number generator..." );
        
        ret = mbedtls_ctr_drbg_seed( &ctr_drbg, mbedtls_entropy_func, &entropy,
                                   (const unsigned char *) pers,
                                   strlen(pers));
        if(ret != 0) {
            printf( " failed\n  ! mbedtls_ctr_drbg_seed returned %d(-0x%04x)\n", ret, -ret);
            goto exit;
        }
        printf( " ok\n" );
    
        /* 3. generate an RSA keypair */
        printf( "\n  . Generate RSA keypair..." );
        
        ret = mbedtls_rsa_gen_key(&ctx, mbedtls_ctr_drbg_random, &ctr_drbg, 2048, 65537);
        if(ret != 0) {
            printf( " failed\n  ! mbedtls_rsa_gen_key returned %d(-0x%04x)\n", ret, -ret);
            goto exit;
        }
        printf( " ok\n" );
        
        /* shwo RSA keypair */
        dump_rsa_key(&ctx);
        
        /* 4. sign */
        printf( "\n  . RSA pkcs1 sign..." );
        
        ret = mbedtls_rsa_pkcs1_sign(&ctx, mbedtls_ctr_drbg_random, &ctr_drbg, MBEDTLS_RSA_PRIVATE, MBEDTLS_MD_SHA256, strlen(msg), (uint8_t *)msg, output_buf);
        if(ret != 0) {
            printf( " failed\n  ! mbedtls_rsa_pkcs1_sign returned %d(-0x%04x)\n", ret, -ret);
            goto exit;
        }
        printf( " ok\n" );
        
        /* show sign result */
        dump_buf(output_buf, sizeof(output_buf));
        
        /* 5. verify sign*/
        printf( "\n  . RSA pkcs1 verify..." );
        
        ret = mbedtls_rsa_pkcs1_verify(&ctx, mbedtls_ctr_drbg_random, &ctr_drbg, MBEDTLS_RSA_PUBLIC, MBEDTLS_MD_SHA256, strlen(msg), (uint8_t *)msg, output_buf);
        
        if(ret != 0) {
            printf( " failed\n  ! mbedtls_rsa_pkcs1_encrypt returned %d(-0x%04x)\n", ret, -ret);
            goto exit;
        }
        printf( " ok\n" );
        
        exit:
        
        /* 5. release structure */
        mbedtls_ctr_drbg_free(&ctr_drbg);
        mbedtls_entropy_free(&entropy);
        mbedtls_rsa_free(&ctx);
        
        return ret;
    }
    
    #endif /* MBEDTLS_RSA_C */
    
    

    4. 测试结果

    在main.c中声明该测试函数:

    extern int mbedtls_rsa_sign_test(void);
    

    在main函数中调用该测试函数:

    /* 8. rsa sign test */
    mbedtls_rsa_sign_test();
    

    编译、下载,在串口助手中查看测试结果:

    ① 生成秘钥对成功(需要几min的时间):

    ② 生成签名和验证签名成功:

    三、ECDSA数字签名功能模块的配置与使用

    1. 配置宏

    使用ECDSA秘钥协商功能需要提前开启伪随机数生成器(依赖AES算法、SHA256算法、MD通用接口),其中伪随机数生成器的硬件适配移植实现已经讲述,请参考对应的第二篇博客,不再赘述。

    综合上述,本实验中需要开启的宏如下表:

    宏定义功能
    MBEDTLS_NO_DEFAULT_ENTROPY_SOURCES不使用默认熵源(如果已有、要屏蔽该宏)
    MBEDTLS_NO_PLATFORM_ENTROPY不使用系统内置熵源
    MBEDTLS_AES_C使用AES算法
    MBEDTLS_ENTROPY_C使能熵源模块
    MBEDTLS_CTR_DRBG_C使能随机数模块
    MBEDTLS_SHA256_C使能SHA256算法
    MBEDTLS_MD_C开启MD通用接口
    MBEDTLS_AES_ROM_TABLES使能预定义S盒(节约内存空间)
    MBEDTLS_BIGNUM_C开启大数运算
    MBEDTLS_ECP_C开启椭圆曲线基础运算
    MBEDTLS_ECP_DP_SECP256R1_ENABLED选择secp256r1曲线参数
    MBEDTLS_ECDSA_C开启ECDSA算法
    MBEDTLS_ASN1_WRITE_C开启ASN1格式写入
    MBEDTLS_ASN1_PARSE_C开启ASN1结构解析

    下面补充几个一个第一次出现宏的定义。

    MBEDTLS_ECDSA_C

    /**
     * \def MBEDTLS_ECDSA_C
     *
     * Enable the elliptic curve DSA library.
     *
     * Module:  library/ecdsa.c
     * Caller:
     *
     * This module is used by the following key exchanges:
     *      ECDHE-ECDSA
     *
     * Requires: MBEDTLS_ECP_C, MBEDTLS_ASN1_WRITE_C, MBEDTLS_ASN1_PARSE_C
     */
    #define MBEDTLS_ECDSA_C
    

    MBEDTLS_ASN1_WRITE_C

    /**
     * \def MBEDTLS_ASN1_WRITE_C
     *
     * Enable the generic ASN1 writer.
     *
     * Module:  library/asn1write.c
     * Caller:  library/ecdsa.c
     *          library/pkwrite.c
     *          library/x509_create.c
     *          library/x509write_crt.c
     *          library/x509write_csr.c
     */
    #define MBEDTLS_ASN1_WRITE_C
    

    MBEDTLS_ASN1_PARSE_C

    /**
     * \def MBEDTLS_ASN1_PARSE_C
     *
     * Enable the generic ASN1 parser.
     *
     * Module:  library/asn1.c
     * Caller:  library/x509.c
     *          library/dhm.c
     *          library/pkcs12.c
     *          library/pkcs5.c
     *          library/pkparse.c
     */
    #define MBEDTLS_ASN1_PARSE_C
    

    新建配置文件mbedtls_config_ecdsa.h,编写以下内容:

    /**
     * @brief   Minimal configuration for ECDSA Function
     * @author  mculover666
     * @date    2020/10/03
    */
    
    #ifndef _MBEDTLS_CONFIG_ECDSA_H_
    #define _MBEDTLS_CONFIG_ECDSA_H_
    
    /* System support */
    #define MBEDTLS_HAVE_ASM
    //#define MBEDTLS_HAVE_TIME
    
    /* mbed feature support */
    #define MBEDTLS_ENTROPY_HARDWARE_ALT
    //#define MBEDTLS_NO_DEFAULT_ENTROPY_SOURCES
    #define MBEDTLS_NO_PLATFORM_ENTROPY
    
    /* mbed modules */
    #define MBEDTLS_AES_C
    #define MBEDTLS_AES_ROM_TABLES
    #define MBEDTLS_CTR_DRBG_C
    #define MBEDTLS_ENTROPY_C
    #define MBEDTLS_SHA256_C
    #define MBEDTLS_MD_C
    #define MBEDTLS_BIGNUM_C
    #define MBEDTLS_ECP_C
    #define MBEDTLS_ECP_DP_SECP256R1_ENABLED
    #define MBEDTLS_ECDSA_C
    #define MBEDTLS_ASN1_WRITE_C
    #define MBEDTLS_ASN1_PARSE_C
    
    #include "mbedtls/check_config.h"
    
    #endif /* _MBEDTLS_CONFIG_ECDSA_H_ */
    
    

    在MDK中配置使用该配置文件:

    2. ECDSA签名功能API说明

    ① 初始化ECDSA结构体:

    /**
     * \brief           This function initializes an ECDSA context.
     *
     * \param ctx       The ECDSA context to initialize.
     *                  This must not be \c NULL.
     */
    void mbedtls_ecdsa_init( mbedtls_ecdsa_context *ctx );
    

    ② ECDSA生成秘钥接口:

    /**
     * \brief          This function generates an ECDSA keypair on the given curve.
     *
     * \see            ecp.h
     *
     * \param ctx      The ECDSA context to store the keypair in.
     *                 This must be initialized.
     * \param gid      The elliptic curve to use. One of the various
     *                 \c MBEDTLS_ECP_DP_XXX macros depending on configuration.
     * \param f_rng    The RNG function to use. This must not be \c NULL.
     * \param p_rng    The RNG context to be passed to \p f_rng. This may be
     *                 \c NULL if \p f_rng doesn't need a context argument.
     *
     * \return         \c 0 on success.
     * \return         An \c MBEDTLS_ERR_ECP_XXX code on failure.
     */
    int mbedtls_ecdsa_genkey( mbedtls_ecdsa_context *ctx, mbedtls_ecp_group_id gid,
                      int (*f_rng)(void *, unsigned char *, size_t), void *p_rng );
    

    ③ ECDSA签名接口:

    /**
     * \brief           This function computes the ECDSA signature of a
     *                  previously-hashed message.
     *
     * \note            The deterministic version implemented in
     *                  mbedtls_ecdsa_sign_det() is usually preferred.
     *
     * \note            If the bitlength of the message hash is larger than the
     *                  bitlength of the group order, then the hash is truncated
     *                  as defined in <em>Standards for Efficient Cryptography Group
     *                  (SECG): SEC1 Elliptic Curve Cryptography</em>, section
     *                  4.1.3, step 5.
     *
     * \see             ecp.h
     *
     * \param grp       The context for the elliptic curve to use.
     *                  This must be initialized and have group parameters
     *                  set, for example through mbedtls_ecp_group_load().
     * \param r         The MPI context in which to store the first part
     *                  the signature. This must be initialized.
     * \param s         The MPI context in which to store the second part
     *                  the signature. This must be initialized.
     * \param d         The private signing key. This must be initialized.
     * \param buf       The content to be signed. This is usually the hash of
     *                  the original data to be signed. This must be a readable
     *                  buffer of length \p blen Bytes. It may be \c NULL if
     *                  \p blen is zero.
     * \param blen      The length of \p buf in Bytes.
     * \param f_rng     The RNG function. This must not be \c NULL.
     * \param p_rng     The RNG context to be passed to \p f_rng. This may be
     *                  \c NULL if \p f_rng doesn't need a context parameter.
     *
     * \return          \c 0 on success.
     * \return          An \c MBEDTLS_ERR_ECP_XXX
     *                  or \c MBEDTLS_MPI_XXX error code on failure.
     */
    int mbedtls_ecdsa_sign( mbedtls_ecp_group *grp, mbedtls_mpi *r, mbedtls_mpi *s,
                    const mbedtls_mpi *d, const unsigned char *buf, size_t blen,
                    int (*f_rng)(void *, unsigned char *, size_t), void *p_rng );
    

    ④ ECDSA验证签名接口

    /**
     * \brief           This function verifies the ECDSA signature of a
     *                  previously-hashed message.
     *
     * \note            If the bitlength of the message hash is larger than the
     *                  bitlength of the group order, then the hash is truncated as
     *                  defined in <em>Standards for Efficient Cryptography Group
     *                  (SECG): SEC1 Elliptic Curve Cryptography</em>, section
     *                  4.1.4, step 3.
     *
     * \see             ecp.h
     *
     * \param grp       The ECP group to use.
     *                  This must be initialized and have group parameters
     *                  set, for example through mbedtls_ecp_group_load().
     * \param buf       The hashed content that was signed. This must be a readable
     *                  buffer of length \p blen Bytes. It may be \c NULL if
     *                  \p blen is zero.
     * \param blen      The length of \p buf in Bytes.
     * \param Q         The public key to use for verification. This must be
     *                  initialized and setup.
     * \param r         The first integer of the signature.
     *                  This must be initialized.
     * \param s         The second integer of the signature.
     *                  This must be initialized.
     *
     * \return          \c 0 on success.
     * \return          #MBEDTLS_ERR_ECP_BAD_INPUT_DATA if the signature
     *                  is invalid.
     * \return          An \c MBEDTLS_ERR_ECP_XXX or \c MBEDTLS_MPI_XXX
     *                  error code on failure for any other reason.
     */
    int mbedtls_ecdsa_verify( mbedtls_ecp_group *grp,
                              const unsigned char *buf, size_t blen,
                              const mbedtls_ecp_point *Q, const mbedtls_mpi *r,
                              const mbedtls_mpi *s);
    

    ⑤ 释放ECDSA结构体:

    /**
     * \brief           This function frees an ECDSA context.
     *
     * \param ctx       The ECDSA context to free. This may be \c NULL,
     *                  in which case this function does nothing. If it
     *                  is not \c NULL, it must be initialized.
     */
    void mbedtls_ecdsa_free( mbedtls_ecdsa_context *ctx );
    

    3. 编写测试函数

    新建文件mbedtls_ecdsa_test,编写以下测试函数:

    /**
     * @brief   ECDSA Function demo
     * @author  mculover666
     * @date    2020/10/03
    */
    
    #if !defined(MBEDTLS_CONFIG_FILE)
    #include "mbedtls/config.h"
    #else
    #include MBEDTLS_CONFIG_FILE
    #endif
    
    #if defined(MBEDTLS_ECDSA_C)
    
    #include <stdio.h>
    #include "string.h"
    #include "mbedtls/entropy.h"
    #include "mbedtls/ctr_drbg.h"
    #include "mbedtls/ecdsa.h"
    
    uint8_t buf[97];
    
    static void dump_buf(uint8_t *buf, uint32_t len)
    {
        int i;
        
        for (i = 0; i < len; i++) {
            printf("%s%02X%s", i % 16 == 0 ? "\r\n\t" : " ", 
                               buf[i], 
                               i == len - 1 ? "\r\n" : "");
        }
    }
    
    int mbedtls_ecdsa_test(void)
    {
        int ret;
        size_t qlen, dlen;
        size_t rlen, slen;
        uint8_t hash[32];
       
        const char *msg  = "HelloWorld";
        const char *pers = "ecdsa_test";
        mbedtls_entropy_context entropy;
        mbedtls_ctr_drbg_context ctr_drbg;
        mbedtls_mpi r, s;
        mbedtls_ecdsa_context ctx;
        mbedtls_md_context_t md_ctx;
            
        /* 1. init structure */
        mbedtls_md_init(&md_ctx);
        mbedtls_entropy_init(&entropy);
        mbedtls_ctr_drbg_init(&ctr_drbg);
        mbedtls_mpi_init(&r);
        mbedtls_mpi_init(&s);
        
        /* 2. update seed with we own interface ported */
        printf( "\n  . Seeding the random number generator..." );
        
        ret = mbedtls_ctr_drbg_seed( &ctr_drbg, mbedtls_entropy_func, &entropy,
                                   (const unsigned char *) pers,
                                   strlen(pers));
        if(ret != 0) {
            printf( " failed\n  ! mbedtls_ctr_drbg_seed returned %d(-0x%04x)\n", ret, -ret);
            goto exit;
        }
        printf( " ok\n" );
        
        /* 3. hash message */
        printf( "\n  . Hash message..." );
        
        ret = mbedtls_md(mbedtls_md_info_from_type(MBEDTLS_MD_SHA256), (uint8_t *)msg, strlen(msg), hash);
        if(ret != 0) {
            printf( " failed\n  ! mbedtls_md returned %d(-0x%04x)\n", ret, -ret);
            goto exit;
        }
        printf( " ok\n" );
        
        /* show hash */
        dump_buf(hash, sizeof(hash));
        
        /* 4. generate keypair */
        printf( "\n  . Generate ecdsa keypair..." );
        
        ret = mbedtls_ecdsa_genkey(&ctx, MBEDTLS_ECP_DP_SECP256R1, mbedtls_ctr_drbg_random, &ctr_drbg);
        if(ret != 0) {
            printf( " failed\n  ! mbedtls_ecdsa_genkey returned %d(-0x%04x)\n", ret, -ret);
            goto exit;
        }
        printf( " ok\n" );
        
        /* show keypair */
        mbedtls_ecp_point_write_binary(&ctx.grp, &ctx.Q, MBEDTLS_ECP_PF_UNCOMPRESSED, &qlen, buf, sizeof(buf));
        dlen = mbedtls_mpi_size(&ctx.d);
        mbedtls_mpi_write_binary(&ctx.d, buf + qlen, dlen);
        dump_buf(buf, qlen + dlen);
        
        /* 5. ecdsa sign */
        printf( "\n  . ECDSA sign..." );
        
        ret = mbedtls_ecdsa_sign(&ctx.grp, &r, &s, &ctx.d, hash, sizeof(hash), mbedtls_ctr_drbg_random, &ctr_drbg);
        if(ret != 0) {
            printf( " failed\n  ! mbedtls_ecdsa_sign returned %d(-0x%04x)\n", ret, -ret);
            goto exit;
        }
        printf( " ok\n" );
        
        /* show sign */
        rlen = mbedtls_mpi_size(&r);
        slen = mbedtls_mpi_size(&s);
        mbedtls_mpi_write_binary(&r, buf, rlen);
        mbedtls_mpi_write_binary(&s, buf + rlen, slen);
        dump_buf(buf, rlen + slen);
        
        /* 6. ecdsa verify */
        printf( "\n  . ECDSA verify..." );
        
        ret = mbedtls_ecdsa_verify(&ctx.grp, hash, sizeof(hash), &ctx.Q, &r, &s);
        if(ret != 0) {
            printf( " failed\n  ! mbedtls_ecdsa_verify returned %d(-0x%04x)\n", ret, -ret);
            goto exit;
        }
        printf( " ok\n" );
    
        exit:
        
        /* 7. release structure */
        mbedtls_ctr_drbg_free(&ctr_drbg);
        mbedtls_entropy_free(&entropy);
        mbedtls_mpi_free(&r);
        mbedtls_mpi_free(&s);
        mbedtls_md_free(&md_ctx);
        mbedtls_ecdsa_free(&ctx);
        
        return ret;
    }
    
    #endif /* MBEDTLS_DHM_C */
    
    

    4. 测试结果

    在main.c中声明该函数:

    extern int mbedtls_ecdsa_test(void);
    

    在main函数中调用该函数:

    /* 9. ecdsa sign test */
    mbedtls_ecdsa_test();
    

    编译、下载,在串口助手中查看结果:

    接收精彩文章及资源推送,请订阅我的微信公众号:『mculover666』

    展开全文
  • 程序要求清单: 基本流程: 运行结果: INPUT: ...

    程序要求清单:
    在这里插入图片描述

    基本流程:
    在这里插入图片描述

    运行结果:

    INPUT:
    34862844108815430278935886114814204661242105806196134451262421197958661737288465541172280522822644267285105893266043422314800759306377373320298160258654603531159702663926160107285223145666239673833817786345065431976764139550904726039902450456522584204556470321705267433321819673919640632299889369457498214445

    OUTPUT:
    Private Key:
    N: 78841181099223968401000784537446044237784489958930626859661546319915734535564286843929089858806160927583636785213641674742891604758519466416270196149968424211401434194951250003636471951939037856583335344796681676680421749817561884185156901077848451414919839607481314547384942033488032689776582103680101651419
    d: 62155833398861149551836037970138554652072353958920365936071774016793504678445192437067806518338650323999067951432452330136982318568982506703216642632242364544915699439246876432122640429532494207894118612299932412964430445703068916755189092721834765176438536555924699728021363703536949347875046151882728437253
    Public Key:
    N: 78841181099223968401000784537446044237784489958930626859661546319915734535564286843929089858806160927583636785213641674742891604758519466416270196149968424211401434194951250003636471951939037856583335344796681676680421749817561884185156901077848451414919839607481314547384942033488032689776582103680101651419
    e: 54379617782319392288508796983156014528426545469465358516629409491913015829046366478896491813056080903568607614496062598318891266649056224190078944747724625447985747390726774036280359056832185917603499408809384176157027477704342977680394354765523168680279688950215134901092221515962361649676202653429692278117
    Signature:
    s: 71919406352359937084182187510227490541914896613466645529207649594247552008972305126510851689232143019784944438466693655526353672464782061473850818475550335761134900001275567160947332462719877194559692283550511188231994020480408965265818017774491786539810263037297828665666952885117080533173354443950829657265
    Verify s of m:
    valid
    m’ (faked): 76185632416095212195849362379326949631255492531288160212489433749029013809159477234031442742457342006136621757534807192466386195243552371639270795778065774775711134972235456069060155133423454262578532881646543833960203758700964200167278452490427449581011414060671053975994766090766673869892463027013529590471
    invalid
    s’ (faked): 64886342123697490001106226310357396118874720615188625977759508709028733843402866228754809027591115956249353484164041076852718802175168533537718549149953512673140432858680493424329023049213294957469230294496190453936529669882382633436019205635629312788163444233181192368101923610587237545646774852698003010422
    invalid

    代码实现:

    import random
    
    
    # 求最大公约数
    def gcd(a, b):
        if a < b:
            return gcd(b, a)
        elif a % b == 0:
            return b
        else:
            return gcd(b, a % b)
    
    
    # 快速幂+取模
    def power(a, b, c):
        ans = 1
        while b != 0:
            if b & 1:
                ans = (ans * a) % c
            b >>= 1
            a = (a * a) % c
        return ans
    
    
    # 快速幂
    def quick_power(a: int, b: int) -> int:
        ans = 1
        while b != 0:
            if b & 1:
                ans = ans * a
            b >>= 1
            a = a * a
        return ans
    
    
    # 大素数检测
    def Miller_Rabin(n):
        a = random.randint(2, n - 2)  # 随机第选取一个a∈[2,n-2]
        # print("随机选取的a=%lld\n"%a)
        s = 0  # s为d中的因子2的幂次数。
        d = n - 1
        while (d & 1) == 0:  # 将d中因子2全部提取出来。
            s += 1
            d >>= 1
    
        x = power(a, d, n)
        for i in range(s):  # 进行s次二次探测
            newX = power(x, 2, n)
            if newX == 1 and x != 1 and x != n - 1:
                return False  # 用二次定理的逆否命题,此时n确定为合数。
            x = newX
    
        if x != 1:  # 用费马小定理的逆否命题判断,此时x=a^(n-1) (mod n),那么n确定为合数。
            return False
    
        return True  # 用费马小定理的逆命题判断。能经受住考验至此的数,大概率为素数。
    
    
    # 卢卡斯-莱墨素性检验
    def Lucas_Lehmer(num: int) -> bool:  # 快速检验pow(2,m)-1是不是素数
        if num == 2:
            return True
        if num % 2 == 0:
            return False
        s = 4
        Mersenne = pow(2, num) - 1  # pow(2, num)-1是梅森数
        for x in range(1, (num - 2) + 1):  # num-2是循环次数,+1表示右区间开
            s = ((s * s) - 2) % Mersenne
        if s == 0:
            return True
        else:
            return False
    
    
    # 扩展的欧几里得算法,ab=1 (mod m), 得到a在模m下的乘法逆元b
    def Extended_Eulid(a: int, m: int) -> int:
        def extended_eulid(a: int, m: int):
            if a == 0:  # 边界条件
                return 1, 0, m
            else:
                x, y, gcd = extended_eulid(m % a, a)  # 递归
                x, y = y, (x - (m // a) * y)  # 递推关系,左端为上层
                return x, y, gcd  # 返回第一层的计算结果。
            # 最终返回的y值即为b在模a下的乘法逆元
            # 若y为复数,则y+a为相应的正数逆元
    
        n = extended_eulid(a, m)
        if n[1] < 0:
            return n[1] + m
        else:
            return n[1]
    
    
    # 按照需要的bit来生成大素数
    def Generate_prime(key_size: int) -> int:
        while True:
            num = random.randrange(quick_power(2, key_size - 1), quick_power(2, key_size))
            if Miller_Rabin(num):
                return num
    
    
    # 生成公钥和私钥
    def KeyGen(p: int, q: int):
        n = p * q
        e = random.randint(1, (p - 1) * (q - 1))
        while gcd(e, (p - 1) * (q - 1)) != 1:
            e = random.randint(1, (p - 1) * (q - 1))
        d = Extended_Eulid(e, (p - 1) * (q - 1))
        return n, e, d
    
    
    def Sign(x: int, d: int, n: int) -> int:
        s = power(x, d, n)
        return s
    
    
    def Verify(s: int, e: int, n: int) -> int:
        x_ = power(s, e, n)
        return x_
    
    
    if __name__ == '__main__':
        key_size = 512
        p = Generate_prime(key_size)
        q = Generate_prime(key_size)
        n, e, d = KeyGen(p, q)
    
        # 消息
        x = int(input("Message: "))
        if type(x) != int:
            raise ValueError("Must be an integer!")
        # 签名
        s = Sign(x, d, n)
        # 验证
        x_ = Verify(s, e, n)
        Valid = (x_ == x)
    
        # Attack
        s_ = random.randint(1, (p - 1) * (q - 1))
        m_ = random.randint(1, (p - 1) * (q - 1))
    
        # Output
        print("Private Key: ")
        print("N: ", n)
        print("d: ", d)
        print("Public Key: ")
        print("N: ", n)
        print("e: ", e)
        print("Signature: ")
        print("s: ", s)
        print("Verify s of m: ")
        if Valid:
            print("valid")
        else:
            print("invalid")
    
        print("m' (faked): ", m_)
        if Verify(m_, s, n) == x:
            print("valid")
        else:
            print("invalid")
        print("s' (faked): ", s_)
        if Verify(x_, s_, n) == x:
            print("valid")
        else:
            print("invalid")
    
    展开全文
  • RSA算法和RSA数字签名算法的实现.doc
  • RSA数字签名算法的模拟实现.doc
  • RSA数字签名算法

    千次阅读 2017-07-03 17:02:00
    1.数字签名数字签名无非就两个目的:证明这消息是你发的;证明这消息内容确实是完整的---也就是没有经过任何形式的篡改(包括替换、缺少、新增)这种是两个目的都达到了,还有一些只达到一个目的公钥和私钥都可以...

    1.数字签名

    数字签名无非就两个目的:
    证明这消息是你发的;

    证明这消息内容确实是完整的---也就是没有经过任何形式的篡改(包括替换、缺少、新增)


    这种是两个目的都达到了,还有一些只达到一个目的

    公钥和私钥都可以用来加密或解密---只要能保证用A加密,就用B解密就行。至于A是公钥还是私钥,其实可以根据不同的用途而定。例如说,如果你想把某个消息秘密的发给某人,那你就可以用他的公钥加密。因为只有他知道他的私钥,所以这消息也就只有他本人能解开,于是你就达到了你的目的。

    但是如果你想发布一个公告,需要一个手段来证明这确实是你本人发的,而不是其他人冒名顶替的。那你可以在你的公告开头或者结尾附上一段用你的私钥加密的内容(例如说就是你公告正文的一段话),那所有其他人都可以用你的公钥来解密,看看解出来的内容是不是相符的。如果是的话,那就说明这公告确实是你发的---因为只有你的公钥才能解开你的私钥加密的内容,而其他人是拿不到你的私钥的。

    最后再说一下数字签名
    数字签名无非就两个目的:
    证明这消息是你发的;
    证明这消息内容确实是完整的---也就是没有经过任何形式的篡改(包括替换、缺少、新增)。

    其实,上面关于“公告”那段内容,已经证明了第一点:证明这消息是你发的。那么要做到第二点,也很简单,就是把你公告的原文做一次哈希(md5或者sha1都行),然后用你的私钥加密这段哈希作为签名,并一起公布出去。当别人收到你的公告时,他可以用你的公钥解密你的签名,如果解密成功,并且解密出来的哈希值确实和你的公告原文一致,那么他就证明了两点:这消息确实是你发的,而且内容是完整的。

    其实概念很简单:

    1. 小明想秘密给小英发送消息

    2. 小英手里有一个盒子(public key),这个盒子只有小英手里的钥匙(private key)才打得开

    3. 小英把盒子送给小明(分发公钥)

    4. 小明写好消息放进盒子里,锁上盒子(公钥加密

    5. 小明把盒子寄给小英(密文传输)

    6. 小英用手里的钥匙打开盒子,得到小明的消息(私钥解密)

    7. 假设小刚劫持了盒子,因为没有小英的钥匙,他也打不开



    2.RSA加密算法过程简

    这边文章总结为:

     


    A和B进行加密通信时,B首先要生成一对密钥。一个是公钥,给A,B自己持有私钥。A使用B的公钥加密要加密发送的内容,然后B在通过自己的私钥解密内容。

    要想B发送消息,A会先计算出消息的消息摘要,然后使用自己的私钥加密这段摘要加密,最后将加密后的消息摘要和消息一起发送给B,被加密的消息摘要就是“签名”。

    B收到消息后,也会使用和A相同的方法提取消息摘要,然后使用A的公钥解密A发送的来签名,并与自己计算出来的消息摘要进行比较。如果相同则说明消息是A发送给B的,同时,A也无法否认自己发送消息给B的事实。

    其中,A用自己的私钥给消息摘要加密成为“签名”;B使用A的公钥解密签名文件的过程,就叫做“验签”。

    数字签名的作用是保证数据完整性,机密性和发送方角色的不可抵赖性

    下面是对签名和验签过程的简要描述:

    签名过程:

    1.A计算消息m的消息摘要,记为 h(m)

    2.A使用私钥(n,d)对h(m)加密,生成签名s ,s满足:

    s=(h(m))^d mod n;

    由于A是用自己的私钥对消息摘要加密,所以只用使用s的公钥才能解密该消息摘要,这样A就不可否认自己发送了该消息给B。

    3.A发送消息和签名(m,s)给B。

    验签过程:

    1.B计算消息m的消息摘要,记为h(m);

    2.B使用A的公钥(n,e)解密s,得到

    H(m) = s^e mod n;

    3.B比较H(m)与h(m),相同则证明

    下面简单总结加密和解密的完整过程。

    签名过程:

    1.A提取消息m的消息摘要h(m),并使用自己的私钥对摘要h(m)进行加密,生成签名s

    2.A将签名s和消息m一起,使用B的公钥进行加密,生成密文c,发送给B。

    验证过程:

    1.B接收到密文c,使用自己的私钥解密c得到明文m和数字签名s

    2.B使用A的公钥解密数字签名s解密得到H(m).

    3.B使用相同的方法提取消息m的消息摘要h(m)

    4.B比较两个消息摘要。相同则验证成功;不同则验证失败。

    展开全文
  • RSA数字签名算法密码实用.pdf
  • 6.2RSA数字签名法 数字签名一般利用公钥密码技术来实现,其中私钥用来签名,公钥用来验证签名。比较典型的数字签名方案有: RSA签名算法(R. L. Rivest, A. Shamir, and L. M. Adleman, 1978) ElGamal 签名算法(T....
  • Go实现RSA数字签名算法(附代码)

    千次阅读 2020-01-13 23:13:49
    数字签名如何工作 数字签名由两部分组成: 使用私钥从消息创建签名的算法; 允许任何人验证签名的算法; ...数字签名应该满足的要求 ...签名可信任,签名的识别应用相对容易,任何人都可以验证签名的...RSA数字签名的核...
  • 数字签名算法rsa

    千次阅读 2021-05-25 01:51:44
    数字签名算法消息传递模型由消息发送方构建密钥对,这里由甲方完成。由消息发送方公布公钥至消息接收方,这里由甲方将公钥公布给乙方。...RSA数字签名算法是迄今为止应用最为广泛的数字签名算法。 RS...
  • C++编写的rsa数字签名程序源代码C++编写的rsa数字签名程序源代码C++编写的rsa数字签名程序源代码
  • 实验六:RSA数字签名算法 一、实验目的 理解、掌握RAS数字签名算法的基本过程。 二、实验内容 熟悉MPIR大整数运算库函数的调用。 熟悉MD5散列的调用。 利用MPIR大整数运算库函数,实现RSA数字算法。要求:1)...
  • RSA签名算法

    千次阅读 2021-09-04 18:32:23
    RSA数字签名算法的过程为:A对明文m用解密变换作: (公钥用来加密,私钥用来解密,数字签名是用私钥完成的,所以称为解密变换,这与onu sdk中一致)sº Dk (m)=md mod n,其中d,n为A的私人密钥,只有A才知道它;...
  • 数字签名算法RSA

    千次阅读 2021-05-26 02:42:27
    //使用私钥进行签名 System.out.println("jdk RSA签名" + Hex.encodeHexString(result)); //验证签名 X509EncodedKeySpec x509EncodedKeySpec = new X509EncodedKeySpec(rsaPublicKey.getEncoded()); keyFactory = ...
  • python实现RSA数字签名(纯算法实现)

    千次阅读 多人点赞 2022-01-14 19:22:56
    利用python实现RSA数字签名(纯算法实现),用到的hash256得到消息摘要,欧几里得,扩展欧几里得算法
  • 主要介绍了Java实现的数字签名算法RSA,结合完整实例形式详细分析了RSA算法的相关概念、原理、实现方法及操作技巧,需要的朋友可以参考下
  • 数字签名算法,c++实现,RSA的算法

    热门讨论 2010-12-23 10:10:56
    包涵三个RSA算法,c++是实现,数字签名的合集,三个独自的程序,可以独自编译运行,VC6.0下编译
  • 1)利用C\C++语言实现DSA算法。 2)DSA中的Hash函数采用SHA算法。 (1)消息填充:因为我们存储的时候是以字节为单位存储的,所以消息的长度(单位:位)一定是 8 的倍数。而我们填充的时候也一定是 8 位、8 位...
  • python实现RSA算法

    2019-12-02 16:41:16
    基于Python实现RSA算法,包括的函数有:判断一个数是否为素数、判断两个数是否互为素数、欧几里得算法求最大公约数、产生公私钥、扩展欧几里得算法求模逆、加密明文、解密密文以及代码测试。
  • RSA-PSS数字签名算法

    千次阅读 2022-01-29 19:04:21
    RSA-PSS数字签名算法

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 33,821
精华内容 13,528
关键字:

rsa数字签名算法