RSA算法笔记

RSA算法笔记

Chris Yue One comment

Posts

使用git提交代码到github.com的代码库必须要事先生成一对key,而且要把其中的public key提交到github以后才能让你提交代码,出于好奇心我打算了解一下github这种加密方式,结果~OMG~苦逼的研究历程开始了> <……内星人就是麻烦,总有一部分素质低的想偷窥别人的秘密,结果弄出一个数据加密算法还包含那么多知识点……作为一个健忘的外星人还是记个笔记好了。

加密的方式有好几种,比较简单的就是对称加密。比如说地球人A君暗恋地球人B君(无误),A给B写了一张小纸条“520”,然后让火星人C君帮忙传递。由于C君不懂520是什么意思,所以就算他看了纸条也不会明白A君原来想跟B君搞基,但B君作为地球人可以轻松明白A君的意思。但是此加密方法有一个缺点就是,如果“520”的含义被泄露,那么加密就失去了意义(C君:“愚蠢的地球基友……”)。

与对称加密对应的,非对称加密要求加密过程必须使用两个key,一个key是用来加密的,叫public key或公钥,还有一个是解密的叫private key或私钥。其实公钥很像上锁的箱子,使用公钥加密数据就是把数据放在箱里,而私钥就是箱子的钥匙。这就是为什么需要把本机生成的公钥提交到github而私钥不用的原因了。

每种加密都要对应一个加密算法,github使用的是rsa,如果还要想深入了解,头疼的阻碍便出现了,没错,我指的就是那传说中自然科学的皇后——数学。Kill me now my Queen …

当然要是你能驾驭得住其实皇后娘娘还是很萌的这里就不再黑她了。对称加密有个难点是如何通过算法可以使用一个数字进行加密但却用另外一个数字进行解密,而且关键是这个公式就算大家都知道,只要没有那解密的数字就得不到原来的内容。这个恼人的问题在70年代由R君S君以及A君三个地球人给出了答案,下面分步骤详细说明之。

首先是生成keys。这也分了好几个步骤(翻译自wikipedia):

  1. 随便选两个质数p和q
  2. 记录p和q的乘积n
  3. 利用欧拉质数公式(Euler’s totient function)找到小于n而且和n互质的数的个数φ,在这里此公式表达式为φ(n) = (p – 1)(q – 1)
  4. 在[0, φ]这个区间找到一个正整数e,并且e和φ互质
  5. 求一个数d让其满足d = e–1 mod φ(n)

上面步骤中的e和n便是public key,d和n便是private key,求的这一切的两个质数以及φ已经没用了,舍去。

我查阅资料的时候好多博客写到这里就接着写下一步了,但我估计好多读者读到这里也就晕菜了,整这么些晦涩的公式给大家看不是坑爹么。作为一个有良心有责任感的外星人,这里我觉得有必要对上面的公式进行简单的解析。

首先是Euler’s totient function的证明。要想得到一个小于数M而且和M互质的数的个数,可以先得到小于M而且和M有公约数的个数。如果一个数M是由p1, p2, p3, …, pn这几个质数构成的,那么可以暂时记M有M/p1 + M/p2 + M/p3 + … + M/pn个小于M且同M有公约数的数,不过在这些数中,有些有两个相同质数的数肯定是被重复计算了,所以要将这些数(M/p1p2 + M/p1p2 + M/p1p3 + … + M/p1pn + M/p2p3 + … + M/p2pn + … + M/pn-1pn)去掉,地球上这称为排容原理(inclusion-exclusion principle)。根据排容原理,有一些有三个相同质数的数肯定又被多减了,所以又要把这些数给加上……反复使用排容原理,然后整理最后的公式f(M),那么小于M而且和M互质的数就是M – f(M),简化这个公式后就可以得到Euler’s totient function: M(1 – 1/p1)(1 – 1/p2)(1 – 1/p3)…(1 – 1/pn)。由于在RSA算法获取n值的时候只用了两个质数所以上式变成了pq(1 – 1/p)(1 – 1/q) == pq(1 + 1/pq – 1/p + 1/q) == pq + 1 – p + q == (p – 1)(q – 1)这个最简式。

另外是求d的公式。粗看很难以理解,不过在等式两边同乘以e以后,公式变成de = 1 mod φ(n)就好理解了,意思就是de mod φ == 1呗(其实标准写法是de ≡ 1 (mod φ),≡表示恒等),求这个数字的时候我们可以利用php脚本获取这样的一个数d:

for ($d = 1; $d < $phi; $d++) { // 希腊字符φ读作[fai]即phi
  if ($d * $e % $phi === 1) {
    echo $d; break;
  }
}

生成key之后就是加密和解密的步骤了。如果我们要加密一个数字M,那么利用以下公式可以得到加密后的内容:

C = Me mod n;

接收端可以利用以下公式还原M:

M = Cd mod n;

RSA算法笔记 by Chris Yue is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

微信赞赏码

写作累,服务器也越来越贵
求分担,祝愿好人一生平安
天使打赏人

One comment

eirc

5月 5, 2011 在 7:32 上午

又见密码学相关知识…这需要强大的神器“数学”啊…
KMN

 回复

发表评论

7 + 1 =