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
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 中有例如以下定义：
{
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这个函数
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;
}
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
乘法的实现方式例如以下：
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
#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