OpenSSL 中 RSA 加密解密实现源代码分析

1、RSA 公钥和私钥的组成。以及加密和解密的公式：

2、模指数运算：

先做指数运算，再做模运算。如 5^3 mod 7 = 125 mod 7 = 6

3、RSA加密算法流程：

选择一对不同的、而且足够大的素数 p 和 q
计算 n = p * q
计算欧拉函数 f(n) = (p-1) * (q-1)，p 和 q 须要保密
寻找与 f(n) 互质的数 e。而且 1 < e < f(n)
计算 d，使得 d * e ≡ 1 mod f(n)
公钥 KU = (e , n) 私钥 KR = (d , n)
加密时，将明文变换成 0 ~ n-1 的一个整数 M。明文较长能够切割。设密文为 C，则加密过程是：C ≡ M^e mod n
解密时，M ≡ C^d mod n

当中 ≡ 表示同余，就是符号两边模运算结果同样。

由于符号右边结果恒为 1

所以要找到符合条件的 d 使得 d * e mod f(n) = 1

4、OpenSSL中RSA加密解密实现

（1）BN_MONT_CTX
/* Used for montgomery multiplication */
struct bn_mont_ctx_st
     {
     int ri;              /* number of bits in R */
     BIGNUM RR;           /* used to convert to montgomery form */
     BIGNUM N;            /* The modulus */
     BIGNUM Ni;           /* R*(1/R mod N) - N*Ni = 1
                           * (Ni is only stored for bignum algorithm) */
     BN_ULONG n0[2];      /* least significant word(s) of Ni;
                                      (type changed with 0.9.9, was "BN_ULONG n0;" before) */
     int flags;
     };
（2）BIGNUM

struct bignum_st
     {
     BN_ULONG *d;     /* Pointer to an array of 'BN_BITS2' bit chunks. */
     int top;   /* Index of last used d +1. */
  /* The next are internal book keeping for bn_expand. */
     int dmax;   /* Size of the d array. */
     int neg; /* one if the number is negative */
     int flags;
     };

d：BN_ULONG (应系统而异，win32 下为4 个字节) 数组指针首地址，大数就存放在这里面，只是是倒放的。
比方。用户要存放的大数为 12345678000（通过BN_bin2bn 放入）。则d 的内容例如以下： 0x30 0x30 0x30 0x38 0x37 0x36 0x35 0x34 0x33 0x32 0x31 ；（注意这里是以ASCII码存放的。他是字符转 bignum ）

top：用来指明大数占多少个 BN_ULONG 空间，上例中top 为 3。

dmax：d 数组的大小。

neg：是否为负数。假设为1，则是负数，为 0。则为正数。

flags：用于存放一些标记，比方 flags 含有BN_FLG_STATIC_DATA 时。表明d 的内存

是静态分配的。含有 BN_FLG_MALLOCED 时。d 的内存是动态分配的。

（3）RSA

struct rsa_st
     {
     /* The first parameter is used to pickup errors where
     * this is passed instead of aEVP_PKEY, it is set to 0 */

int pad;
     long version;

/*此处的 method 方法指针比較重要，通过指向不同的函数，能够调用自定义的处理函数，也就是这个指针指向各种运算函数的地址*/
     const RSA_METHOD *meth;
     /* functional reference if 'meth' is ENGINE-provided */
     ENGINE *engine;
     BIGNUM *n;
     BIGNUM *e;
     BIGNUM *d;
     BIGNUM *p;
     BIGNUM *q;
     BIGNUM *dmp1;
     BIGNUM *dmq1;
     BIGNUM *iqmp;
     /* be careful using this if the RSA structure is shared */
     CRYPTO_EX_DATA ex_data;
     int references;
     int flags;

     /* Used to cache montgomery values */
     BN_MONT_CTX *_method_mod_n;
     BN_MONT_CTX *_method_mod_p;
     BN_MONT_CTX *_method_mod_q;

     /* all BIGNUM values are actually in the following data, if it is not NULL */
     char *bignum_data;
     BN_BLINDING *blinding;
     BN_BLINDING *mt_blinding;
     };

（4）RSA_METHOD

struct rsa_meth_st
     {
     const char *name;
/*与（6）中RSA_eay_public_encrypt函数相应*/
     int (*rsa_pub_enc)(int flen,
const unsigned char *from,
unsigned char *to,
RSA *rsa,int padding);

     int (*rsa_pub_dec)(int flen,
const unsigned char *from,
unsigned char *to,
RSA *rsa,int padding);

     int (*rsa_priv_enc)(int flen,
const unsigned char *from,
unsigned char *to,
RSA *rsa,int padding);

     int (*rsa_priv_dec)(int flen,
const unsigned char *from,
unsigned char *to,
RSA *rsa,int padding);

     int (*rsa_mod_exp)(BIGNUM *r0,
const BIGNUM *I,
RSA *rsa,
BN_CTX *ctx);   /* Can be null */

/*与（6）中BN_mod_exp_mont 函数相应*/
     int (*bn_mod_exp)(BIGNUM *r,
const BIGNUM *a, const BIGNUM *p,
const BIGNUM *m, BN_CTX *ctx,
BN_MONT_CTX *m_ctx); /* Can be null */

     int (*init)(RSA *rsa);          /* called at new */
     int (*finish)(RSA *rsa); /* called at free */
     int flags;   /* RSA_METHOD_FLAG_* things */
     char *app_data;   /* may be needed! */

/* New sign and verify functions: some libraries don't allow arbitrary data
* to be signed/verified: this allows them to be used. Note: for this to work
* the RSA_public_decrypt() and RSA_private_encrypt() should *NOT* be used
* RSA_sign(), RSA_verify() should be used instead. Note: for backwards
* compatibility this functionality is only enabled if the RSA_FLAG_SIGN_VER
* option is set in 'flags'.
*/
     int (*rsa_sign)(int type,
const unsigned char *m,
unsigned int m_length,
unsigned char *sigret,
unsigned int *siglen,
const RSA *rsa);

     int (*rsa_verify)(int dtype,
const unsigned char *m,
unsigned int m_length,
const unsigned char *sigbuf,
unsigned int siglen,
const RSA *rsa);

/* If this callback is NULL, the builtin software RSA key-gen will be used. This
* is for behavioural compatibility whilst the code gets rewired, but one day
* it would be nice to assume there are no such things as "builtin software"
* implementations. */
     int (*rsa_keygen)(RSA *rsa,
int bits,
BIGNUM *e,
BN_GENCB *cb);
     };

用户可实现自己的 RSA_METHOD 来替换openssl 提供的默认方法。

（5）rsa_crpt.c 详细实现了下面几个函数

int     RSA_public_encrypt(int flen,
const unsigned char *from,
unsigned char *to,
RSA *rsa,
int padding);

int     RSA_private_encrypt(int flen,
  const unsigned char *from,
  unsigned char *to,
  RSA *rsa,
  int padding);

int     RSA_public_decrypt(int flen,
  const unsigned char *from,
  unsigned char *to,
  RSA *rsa,
  int padding);

int     RSA_private_decrypt(int flen,
  const unsigned char *from,
  unsigned char *to,
  RSA *rsa,
  int padding);

RSA_public_encrypt 函数体内部，真正调用的是例如以下函数：

return(rsa->meth->rsa_pub_enc(flen, from, to, rsa, padding));

也就是 RSA_public_encrypt 调用的是（4）中 rsa_pub_enc 这个函数。

在 rsa.h中有例如以下说明：
/* these are the actual SSLeay RSA functions */
const RSA_METHOD *RSA_PKCS1_SSLeay(void);

const RSA_METHOD *RSA_null_method(void);

（6）rsa_esy.c 中有例如以下定义：

const RSA_METHOD *RSA_PKCS1_SSLeay(void)
     {
     return(&rsa_pkcs1_eay_meth);
     }

static RSA_METHOD rsa_pkcs1_eay_meth={
     "Eric Young's PKCS#1 RSA",
     RSA_eay_public_encrypt,
     RSA_eay_public_decrypt,   /* signature verification */
     RSA_eay_private_encrypt,   /* signing */
     RSA_eay_private_decrypt,
     RSA_eay_mod_exp,
     BN_mod_exp_mont,   /* XXX probably we should not use Montgomery if e == 3 */
     RSA_eay_init,
     RSA_eay_finish,
     0, /* flags */
     NULL,
     0,   /* rsa_sign */
     0,   /* rsa_verify */
     NULL   /* rsa_keygen */
     };

这个结构体完毕了函数地址映射的功能。如：

RSA_public_encrypt 终于调用的是 RSA_eay_public_encrypt 这个函数

bn_mod_exp 终于调用的是 BN_mod_exp_mont这个函数



（7）RSA_eay_public_encrypt 在 rsa_esy.c 中实现

static int RSA_eay_public_encrypt(int flen,
const unsigned char *from,
unsigned char *to,
RSA *rsa,
int padding)
     {

..............

/*核心调用在此。事实上调用的是（6）中 BN_mod_exp_mont 函数*/
     if (!rsa->meth->bn_mod_exp(ret,f,rsa->e,rsa->n,ctx,
          rsa->_method_mod_n)) goto err;

..............
     }

（8）BN_mod_exp_mont 在 bn_exp.c 中实现

int BN_mod_exp_mont(BIGNUM *rr,
const BIGNUM *a,
const BIGNUM *p,
const BIGNUM *m,
BN_CTX *ctx,
BN_MONT_CTX *in_mont)
     {
..........
     if (!BN_to_montgomery(val[0],aa,mont,ctx)) goto err; /* 1 */

     window = BN_window_bits_for_exponent_size(bits);
     if (window > 1)
          {
          if (!BN_mod_mul_montgomery(d,val[0],val[0],mont,ctx)) goto err; /* 2 */
          j=1<<(window-1);
          for (i=1; i<j; i++)
               {
               if(((val[i] = BN_CTX_get(ctx)) == NULL) ||
                         !BN_mod_mul_montgomery(val[i],val[i-1],
                              d,mont,ctx))
                    goto err;
               }
          }

..........
     }

BN_mod_exp_mont 调用 BN_mod_mul_montgomery 函数实现了核心功能

（9）BN_mod_mul_montgomery 在 bn_mont.c 中实现

int BN_mod_mul_montgomery(BIGNUM *r,
const BIGNUM *a,
const BIGNUM *b,
BN_MONT_CTX *mont,
BN_CTX *ctx)
     {
..........

     if (num>1 && a->top==num && b->top==num)
          {
          if (bn_wexpand(r,num) == NULL) return(0);
          if (bn_mul_mont(r->d,a->d,b->d,mont->N.d,mont->n0,num))
               {
               r->neg = a->neg^b->neg;
               r->top = num;
               bn_correct_top(r);
               return(1);
               }
          }
..........
     }

BN_mod_mul_montgomery 调用 bn_mul_mont 函数实现了核心功能

（10）bn_mul_mont 在 bn_asm.c 中实现，即实现蒙哥马利模乘

例如以下是 bn_mul_mont 函数的详细实现：

int bn_mul_mont(BN_ULONG *rp,
const BN_ULONG *ap,
const BN_ULONG *bp,
const BN_ULONG *np,
const BN_ULONG *n0p,
int num)
     {
     BN_ULONG c0,c1,*tp,n0=*n0p;
     volatile BN_ULONG *vp;
     int i=0,j;

     vp = tp = alloca((num+2)*sizeof(BN_ULONG));

     for(i=0;i<=num;i++)     tp[i]=0;

     for(i=0;i<num;i++)
          {
/* t = a * b */
          c0         = bn_mul_add_words(tp,ap,num,bp[i]);
          c1         = (tp[num] + c0)&BN_MASK2;
          tp[num]    = c1;
          tp[num+1] = (c1<c0?1:0);

/* u = (t + (t*n0 mod r) * n) / r */
          c0         = bn_mul_add_words(tp,np,num,tp[0]*n0);
          c1         = (tp[num] + c0)&BN_MASK2;
          tp[num]    = c1;
          tp[num+1] += (c1<c0?
1:0);

          for(j=0;j<=num;j++)     tp[j]=tp[j+1];
          }

/* return u>=n ? u-n : u */
     if (tp[num]!=0 || tp[num-1]>=np[num-1])
          {
          c0 = bn_sub_words(rp,tp,np,num);
          if (tp[num]!=0 || c0==0)
               {
               for(i=0;i<num+2;i++)     vp[i] = 0;
               return 1;
               }
          }

     for(i=0;i<num;i++)     rp[i] = tp[i],     vp[i] = 0;
     vp[num]   = 0;
     vp[num+1] = 0;
     return 1;
     }

bn_mul_add_words 在 bn_asm.c 中定义实现。能够通过例如以下部分代码知道详细的实现方法：

num --> 表示大数占用的 BN_ULONG 的个数，也就是 BIGNUM 中的 top 成员
rp --> 表示输出结果的指针
ap --> 表示输入大数的指针
w --> 表示输入word
c1 --> 表示输出进位

BN_ULONG bn_mul_add_words(BN_ULONG *rp, const BN_ULONG *ap, int num, BN_ULONG w)
     {
......
while (num)
          {
          mul_add(rp[0],ap[0],w,c1);
          ap++; rp++; num--;
          }
......
}

bn_mul_add_words 函数实现了将一个大数 ap 与字 w 乘累加，而且得到结果保存到大数 rp ,进位保存到 c1 中。
实现了例如以下表达式：

(c1, rp) = ap * w + rp + c1

乘法的实现方式例如以下：

bn_sub_words 在 bn_asm.c 中定义实现。能够通过例如以下部分代码知道详细的实现方法：

n --> 表示大数占用的 BN_ULONG 的个数，也就是 BIGNUM 中的 top 成员
a --> 表示输入被减数
b --> 表示输入减数
c --> 表示输出借位

BN_ULONG bn_sub_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int n)
        {
......
while (n)
          {
          t1=a[0]; t2=b[0];
          r[0]=(t1-t2-c)&BN_MASK2;
          if (t1 != t2) c=(t1 < t2);
          a++; b++; r++; n--;
          }
......
}

实现了两个大数 a 和 b 的减法运算，当中 c 是借位。实现例如以下表达式：

(r, c) = a - b

bn_lcl.h 中定义了例如以下几个宏：实现乘累加运算

#define Lw(t) (((BN_ULONG)(t))&BN_MASK2)
#define Hw(t)    (((BN_ULONG)((t)>>BN_BITS2))&BN_MASK2)

#define mul_add(r,a,w,c) {
     BN_ULLONG t;
     t=(BN_ULLONG)w * (a) + (r) + (c);
     (r)= Lw(t);
     (c)= Hw(t);
     }

mul_add 函数实现了乘累加的功能。实现例如以下的表达式：

(c, r) = a * w + r + c