遇到RSA算法后，首先进入脑海的念头是OpenSSL，这是一年多来实践经验的反射，一般情况下它都能很好的解决问题。直到我遇到了这样一个课题：
在逆向Hello语音的授权登陆协议时，需要将其授权登陆页面的JS代码中RSA加密算法翻译成OC/C#代码。该文件中RSA加密算法的最关键代码如下：
var rsaPubkey_m = "b5f53d3e7ab166d99b91bdee1414364e97a5569d9a4da971dcf241e9aec4ee4ee7a27b203f278be7cc695207d19b9209f0e50a3ea367100e06ad635e4ccde6f8a7179d84b7b9b7365a6a7533a9909695f79f3f531ea3c329b7ede2cd9bb9722104e95c0f234f1a72222b0210579f6582fcaa9d8fa62c431a37d88a4899ebce3d";
var rsaPubkey_e = "10001";
var RSAKeyPair = function(encryptionExponent, decryptionExponent, modulus) {
var $dmath = RSAUtils;
this.e = $dmath.biFromHex(encryptionExponent);
this.d = $dmath.biFromHex(decryptionExponent);
this.m = $dmath.biFromHex(modulus);
// We can do two bytes per digit, so
// chunkSize = 2 * (number of digits in modulus - 1).
// Since biHighIndex returns the high index, not the number of digits, 1 has
// already been subtracted.
this.chunkSize = 2 * $dmath.biHighIndex(this.m);
this.radix = 16;
this.barrett = new that.BarrettMu(this.m);
};
RSAUtils.getKeyPair = function(encryptionExponent, decryptionExponent, modulus) {
return new RSAKeyPair(encryptionExponent, decryptionExponent, modulus);
};
if(typeof that.twoDigit === 'undefined') {
that.twoDigit = function(n) {
return (n < 10 ? "0" : "") + String(n);
};
}
// Altered by Rob Saunders (rob@robsaunders.net). New routine pads the
// string after it has been converted to an array. This fixes an
// incompatibility with Flash MX's ActionScript.
RSAUtils.encryptedString = function(s) {
if(s == null || RSAUtils.containsChinese(s)){// do not encrypt when contains chinese
return "";
}
s = s.split("").reverse().join("");
var key = new RSAUtils.getKeyPair(rsaPubkey_e, "", rsaPubkey_m);
var a = [];
var sl = s.length;
var i = 0;
while (i < sl) {
a[i] = s.charCodeAt(i);
i++;
}
while (a.length % key.chunkSize != 0) {
a[i++] = 0;
}
var al = a.length;
var result = "";
var j, k, block;
for (i = 0; i < al; i += key.chunkSize) {
block = new BigInt();
j = 0;
for (k = i; k < i + key.chunkSize; ++j) {
block.digits[j] = a[k++];
block.digits[j] += a[k++] << 8;
}
var crypt = key.barrett.powMod(block, key.e);
var text = key.radix == 16 ? RSAUtils.biToHex(crypt) : RSAUtils.biToString(crypt, key.radix);
result += text + " ";
}
result = result.substring(0, result.length - 1);// Remove last space.
if(result.length == 256){// when result.length not pubkey.length, it is wrong!
return result;
}else if(result.length == 252){ // 个别特殊字符串（如dlknfk101） 加密左边会少4个0000,补齐
return "0000" + result;
}else{
return "";
}
};
从这段JS代码中很容易定位出RSA算法生成PublicKey所需要的Modules与Exponent。同时依据这段代码同一源串每次加密结果都相同的特征，猜测其使用了OpenSSL里的NoPadding。那么至此OpenSSL中RSA算法所需要的三个维度Modules/Exponent/Padding都确定了，再梳理下JS代码，发现其在源串前补位0，使源串长度达到126位后做加密处理。是时候用OpenSSL开始表演来见证奇迹了。
const char* hex = "b5f53d3e7ab166d99b91bdee1414364e97a5569d9a4da971dcf241e9aec4ee4ee7a27b203f278be7cc695207d19b9209f0e50a3ea367100e06ad635e4ccde6f8a7179d84b7b9b7365a6a7533a9909695f79f3f531ea3c329b7ede2cd9bb9722104e95c0f234f1a72222b0210579f6582fcaa9d8fa62c431a37d88a4899ebce3d";
int lenModules = 0;
const unsigned char* modules = hex2bin(hex, strlen(hex), &lenModules);
int lenE = 0;
const char* srcE = "00010001";
const unsigned char* e = hex2bin(srcE, strlen(srcE), &lenE);
BIGNUM* bnn = BN_new();
BIGNUM* bne = BN_new();
BN_bin2bn(modules, lenModules, bnn);
BN_bin2bn((const unsigned char*)e, lenE, bne);
RSA* r = RSA_new();
r->n = bnn;
r->e = bne;
r->iqmp=NULL;
r->d=NULL;
r->p=NULL;
r->q=NULL;
int size = RSA_size(r);
unsigned char* buffer = (unsigned char*)malloc(size);
bzero(buffer, size);
unsigned char* src = (unsigned char*)malloc(size);
bzero(src, size);
for (int i = 0, j = size - 1; i < [source length]; i++) {
src[j--] = [source characterAtIndex:i];
}
ret = RSA_public_encrypt(size, src, buffer, r, RSA_NO_PADDING);
if (ret > 0) {
NSString* value = [[NSString alloc] initWithUTF8String:(const char*) buffer];
NSLog(@"value = %@", value);
}
然而奇迹并没有如想象般的发生，OC代码相同的输入得到了与JS不一样的输出，再尝试其他类型的Padding方式，依然无效。通过Google找到这段RSA算法JS实现的源头，原来它是一个老外的算法练手之作，后来慢慢的流传开来，而它第一个版本与OpenSSL有很多兼容性的问题，当然这些问题在后来的版本更新中得到了修复，但这并不能解决现有的问题。最终我决定去啃RSA算法的数学原理，它最终帮助我攻克了这个难题。
RSA加解密的数学原理
相信很多同学到这里应该就没有读下去的欲望了。为此我不会在罗列网上那一堆又一堆的方程式，只提及与加解密最密切相关的两个方程式（最终还是方程式。。。）：
- 加密
c = (p ^ e) mod n; - 解密
p = (c ^ d) mod n;
方程中p表示源串，c表示加密串，n就是文件上面说的Modules，e则为Exponent，(n, e)表示PublicKey，(n, d)表示PrivateKey。原来RSA加解密的具体计算工作如此简单，当然这是将n/e/d三个参数生成算法过滤掉的结果，但对于实际应用这两方程式已经足够了。
要明白的是，这两个方程式中的所有的数都不是编程语言里普通的数字对象了，它们是由输入字符组成的大数对象。OpenSSL中的BigNumber类、BouncyCastle中的BigInteger类、C#中的BigInteger类等等都是用来表示大数这一概念的。
破题
理解了RSA加解密算法的计算过程，而OpenSSL提供的RSA加密api无法适用于这个问题，那么尝试下抛弃OpenSSL原有的那套加解api，自己编写一套RSA的加密算法吧，当然大数库依然使用OpenSSL提供的那套。你总不至于无聊到自己造一套大数的轮子吧。
const char* hex = "b5f53d3e7ab166d99b91bdee1414364e97a5569d9a4da971dcf241e9aec4ee4ee7a27b203f278be7cc695207d19b9209f0e50a3ea367100e06ad635e4ccde6f8a7179d84b7b9b7365a6a7533a9909695f79f3f531ea3c329b7ede2cd9bb9722104e95c0f234f1a72222b0210579f6582fcaa9d8fa62c431a37d88a4899ebce3d";
int lenModules = 0;
const unsigned char* modules = hex2bin(hex, strlen(hex), &lenModules);
int lenE = 0;
const char* srcE = "00010001";
const unsigned char* e = hex2bin(srcE, strlen(srcE), &lenE);
BIGNUM* bnn = BN_new();
BIGNUM* bne = BN_new();
BN_bin2bn(modules, lenModules, bnn);
BN_bin2bn((const unsigned char*)e, lenE, bne);
int size = 126;
unsigned char* buffer = (unsigned char*)malloc(size);
bzero(buffer, size);
for (int i = 0, j = size - 1; i < [source length]; i++) {
buffer[j--] = [source characterAtIndex:i];
}
BIGNUM* message = BN_new();
BN_bin2bn(buffer, size, message);
BN_CTX* ctx = BN_CTX_new();
BIGNUM* c = BN_new();
//RSA加密的数学算法函数，仅此一行代码足矣，是不是很出乎意料。。。。
int succ = BN_mod_exp(c, message, bne, bnn, ctx);
if (succ == 1) {
char* encryptValue = BN_bn2hex(c);
if (encryptValue != NULL) {
printf("encryptValue = %s", encryptValue);
OPENSSL_free(encryptValue);
}
}
程序跑起来，奇迹出现了，相同的输入等到了同JS代码一致的输出。至此才明白原来这段JS中的RSA算法只是实现了自己的一套填充规则，与主流的填充规则有些许不同。
总结
RSA加解密是一种数学运算，而OpenSSL/BouncyCastle算法库提供的RSA api只是按照市面上通用的规则实现了这套数学运算，比如主流的PKCS1填充规则。如果遇上不按常理出牌，非得自己搞一套填充规则的主，使用合适的大数库按照它的这套规则实现RSA算法就是了。
这段JS代码的C#版本也已完成并验证OK，但其间也碰到了因大小端字节序导致的问题，这里就不在说明了。
