区块链学习第一月作业 - 到底什么是RSA加密

原文 在此
本来RSA跟区块链并无联系, 但是非对称加密以及私钥/公钥的理解相似, 因此理解RSA对与理解ECC有相当大的帮助, 因此这里再炒一次剩饭.

RSA加密演算法是一种非对称加密演算法。在公开密钥加密和电子商业中RSA被广泛使用。RSA是1977年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。

上面是维基百科对RSA加密算法的定义, 具体内容请点此(wikiwand让你以更优雅的姿势查看维基百科)查看.

最近在学习区块链知识, 读了<<精通比特币>>, 想把椭圆加密算法搞懂, 但是感觉很懵B, 想着先把RSA搞懂了, 再去啃硬骨头.

我们以经典的 Alice 和 Bob 举例

原始方法: 明文

Bob 是一个才子, Alice 是个美人. Bob 喜欢 Alice, 经常给 Alice 写纸条. 慢慢的 Alice 也开始给 Bob 回复纸条.
这是最原始的通信方式: 你说什么我收到什么.

双向加密

后来, Bob 和 Alice 关系有了一些进展, 班里开始有一些八卦, 传递纸条的同学忍不住开始偷窥内容. Alice 开始不再回复 Bob 的纸条, 也不太高兴, 不想让 Bob 给她传纸条了.
Bob 是个才子, 想出来一个方法: 约定一个密码, 把想写的字换掉, 比如密码是一本<<三国演义>>, 三字在第十页第二行第三字, 便写作 0100203, 国字在第200夜第10行第20字, 变成2001020. Bob 教会了 Alice 这个方法. 这样他们俩就又能开开心心地传纸条了.

双向加密的不安全性

好景不长, Alice 有一次在回复纸条时被归蜜 Lucy 撞见, Lucy 是个大嘴巴, 这样班里人手一本<<三国演义>> 大家都开始了这种时髦的通信方式, 一时间语文老师开心的不行, 以为大家突然开窍了.

RSA

Bob 想让 Alice 换一本书把, Alice 觉得太麻烦而且大家都知道怎么玩的了再要隐密传递也不太可能. 所以 Bob 回家苦心钻研, 终于发现了一个神奇的方法: RSA. (其实RSA由三人共同设计)

圆不回来了, 正题开始

公钥与私钥的产生

RSA 加密算法的核心在于一对密钥与公钥, 那么怎么产生自己的密钥和公钥呢?

1. 随机选择两个不相等的质数p和q
2. 计算p和q的乘积n
3. 计算n的欧拉函数φ(n)
4. 随机选择一个整数e，条件是1< e < φ(n)，且e与φ(n) 互质
5. 计算e对于φ(n)的模反元素d
6. 将n和e封装成公钥，n和d封装成私钥

"Talk is easy, show me the code."
通过示例看一下具体过程:

var BigNumber = require('bignumber.js'); // js 处理数字的位数有限, 避免溢出

// 随机选择两个数字
var p = 47;
var q = 97;

var N = p * q;
var r = (p - 1) * (q - 1);

// console.log(N, r); // 4559 4416

var e = 5; // 1 < e < r && e r 互质
// 计算e对于r的模反元素d。
var d;
// e * d % r = 1; // 模反元素
// 上面的算式 等价于: e * d + k * r = 1
// 已知 e = 3; r = 4416; 5 * d + k * 4416 = 1; // "扩展欧几里得算法" 可以求解, 至于具体的数学方法, 我不太懂. 使用下面的简单方法也可求解.
// for (var i = 10; i > -100; i--) {
//   var result = (1 + i * 4416) / 5;
//   console.log(i, result);
//   if (result.toString().indexOf('.') < 0) {
//     break
//   }
// } 
// 使用上面的代码得出其中一个解为: 7949, -9;
d = 7949;

// 得到公钥/私钥, 其中任意一组作为公钥都可以, 另一组作为私钥自己保存
// PrivateKey: (4559, 5)
// PublicKey:  (4559, 7949)

加密过程

function rsa(key1, key2, message) {
  message = +message;
  if (key1 < 1 || key2 < 1) {
    return 0;
  }
  //加密或者解密之后的数据
  var rsaMessage = 0;

  //加密核心算法
  rsaMessage = (new BigNumber(message)).toPower(key2).modulo(new BigNumber(key1));
  return rsaMessage.valueOf();
}

function test(msg) {
  var encodeMsg = rsa(N, e, msg);
  var decodeMsg = rsa(N, d, encodeMsg);
  console.log('原始数据: ', msg, ', 密文: ', encodeMsg, ': 解密: ', decodeMsg);
}
test();

运行node index.js, 产生以下输出:

原始数据:  10 , 密文:  4261 : 解密:  10
原始数据:  20 , 密文:  4141 : 解密:  20
原始数据:  30 , 密文:  530 : 解密:  30
原始数据:  40 , 密文:  301 : 解密:  40
原始数据:  50 , 密文:  3345 : 解密:  50
原始数据:  60 , 密文:  3283 : 解密:  60
原始数据:  70 , 密文:  1855 : 解密:  70
原始数据:  80 , 密文:  514 : 解密:  80
原始数据:  90 , 密文:  1138 : 解密:  90

信任问题

上面的方法是没问题了, Bob 使用 Alice 的公钥 加密自己的消息, Alice 收到之后, 使用自己的消息解密, 但是这个方式没有办法确认消息来源, 如果 Jim 也使用这个方式来加密消息传给 Alice, 那么 Alice 怎么确认消息�的真实性呢?

是的, 聪明如你一定想到了, 签名啊, Bob使用自己的私钥来对发送的消息签名, 这样别人即使知道如何加密解密, 但是无法知道 Bob 的私钥, 是无法冒充的 Bob 的. 看一下具体过程:
上面有了 Alice 的私钥/公钥对, 我们可以用同样的方式给 Bob 找到一对私钥/公钥, 假设是(33, 3) 和 (33, 7)

1. 比如 Bob 想要发送消息 14 给 Alice
2. 使用 HASH 方法计算出消息的 HASH 值为 4,
3. 使用 Bob 自己的私钥(33, 3)对 HASH 签名 为 31
4. 那么消息变成了 1431, Bob 再次使用 Alice 的公钥加密此消息(882)传递给 Alice
5. Alice 收到消息之后, 使用自己的私钥解密得到1431
6. 我们已经知道这是一个包含签名的消息, 后两位是签名(真实情况, 签名比这个复杂, 但是原理相似), Alice 首先得到消息内容 14, 然后开始校验签名 31, 之前我们知道 RSA 是不可逆单向加密, 那么如何校验签名呢?
7. Alice 其实不需要知道这个消息是谁发送的, 只需要知道它是不是来自 Bob 就行, 因此她使用 Bob 的公钥对此签名解密, 得到 原始消息 Hash 4, 然后使用和 Bob 相同的一套 Hash 算法, 计算消息 14 的 Hash 也是 4, Alice 很开心, 她知道这是 Bob 在向她表达一世.

这一过程简单代码示意如下:

var message = 14;
var hashOfMessage = hash(message);
var signature = rsa(33, 3, hashOfMessage);

var hashMessage = +`${message}${signature}`;
console.log('原始消息: ', message, 'Hash: ', hashOfMessage, 'Hash 签名', signature, '签名消息', hashMessage);

var encodeMsg = rsa(N, e, hashMessage);
console.log('收到消息: ', encodeMsg);

var decodeMsg = rsa(N, d, encodeMsg);
console.log('解密消息: ', decodeMsg);
// 最后2位是签名
var sentMsg = +(decodeMsg.toString()).slice(0, 2);
var sentHash = +(decodeMsg.toString()).slice(2);
console.log('原始消息:', sentMsg, '签名:', sentHash);
var rightHash = hash(sentMsg);
var decodeHash = rsa(33, 7, sentHash);
console.log('正确签名: ', rightHash, '校验签名: ', decodeHash);

安全性

上面的例子中选取的密钥都是简单密钥, 很容易被破解, 而且通过代码我们可以知道, 公钥/私钥第一位数字是加密算法一次处理上限, 大于该值加密无效.
但实际应用中我们会选择比较大的数字 作为 公钥/私钥组合, 这样破解难度也将高到极致.
比如数字: 1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413, 你知道哪两个数相乘等于它吗? 参考链接里面可以看到答案.

关于 RSA 就先写到这儿.

参考

1. 维基百科 RSA 词条
2. RSA算法原理（一）
3. RSA算法原理（二）