RSA公开密钥加密算法

工作中用某library写了些RSA公钥密钥对生成,则有空时就重新阅读并思考了下这个已被广泛运用的加密技巧。我是高中时得知这个算法的,当然完全是似懂非懂,主要是那时候对其所基于的数论还未形成最基本的直觉,所以必然无法真正搞懂,不久就忘掉如没学一样。好的是,用现在更成熟的眼光看,这个算法真挺直接的,要点就那么几个。

先简单讲讲它的背景。他的被公布的发现发明是七十年代末,由美国的Rivest, Shamir, Adleman。维基百科的英文页也说这算法也是七十年代初就被英国情报局的一位数学家发现,但它直到九十年代末才被公布。那时候的计算力量还不足以让这个算法可被实现在我们日常生活中,但是好像八九十年代Rivest, Shamir, Adleman为此创办了一家公司,把它非常成功的商业化了,也赚了不少钱。毫无疑问,这算是比较重要的新技术和发展,美国也占了它的牛耳。这些如何进入别的国家(或是被别人也独立发现而至今为公布)我就不太清楚了,我读到过美国对密码学技术出口法律上有严格限制的,九十年代在美国好像有个做这个的人由于公开某加密技术而被美国政府调查,这个人的名字是Zimmerman

RSA算法

现在,我把RSA的技巧简单解释一下,细节也不必讲的太透彻,主要讲讲他的思路和启发。

基本数论有个欧拉定理(欧拉18世纪就发现了),它的断言为

a^{\phi(n)} \equiv 1 \mod n

\phi为totient函数,\phi(n) = |\{1 \leq k \leq n : \gcd(k, n) = 1\}|

通过这个可以观察到在a^m,若m \equiv 1 \mod \phi(n),就可恢复a。那如果d \cdot e \equiv 1 \mod \phi(n),可以试试以a^d加密编码为a信息,收信方以e为自己的钥,以其解密。在\mod nd次方是计算复杂度很高的计算问题,则即使第三方知道被加密的信息是某数的d次方,也难以进行反过来的操作,而取d次方确是个复杂度为\log d的问题。

那如何生成de呢,并使得他人无法快速从d计算出必保密的私钥e呢?在这一点,观察到计算\phi(n),若不是每一个小于n的整数都以欧几里得算法算出最大同因子,数与其互质的,那就得分解因式,而分解因式问题,若以分解任意b个比特的数的形式表示,还未知任何多项式时间的算法。所以可以随机选两个巨大的素数pq,并让n = pq\phi(n) = (p-1)(q-1)。他方知道n但无法分解它则无法算出\phi(n)e是随机选的与\phi(n)互质的数,它在\mod \phi(n)里的逆元素可以扩展欧几里得算法快速计算出来,以d命名,为公钥,传给他方,他方以a^d加密a,被加密的信息一旦受到可用仅自己知道的密钥e解密。

数位签章

我们已看到密钥可以给他方提供加密的方式保证中间监听者无法解密他方所传的信息。又一个核心功能就是这个密钥也可以用以做数位签章而验证身份。这个数位签章可以保证信息绝对是发信人发的,并未在中途改于某恶意的第三方。这个如何实现呢?要发信息a,可以将某双方同意定的哈西函数ha上的值h(a)e次方(e为私钥),(h(a))^e同时发送。对方把发的信息解密了,也把数位签章以d(公钥)次方解密,若前者的哈西与后者同等,就能保证没问题,因为这验证了发信息的拥有了某个代表并限制于某身份的密钥。若想对此有更清晰的图像,读者可以试试画个交换图标。

非对称与对称加密

读者可以观察到该算法的不对称性,则RSA也被称为非对称加密。对称的加密方法也是有的,它需要先双方互相安全交换共享的对称密钥,该钥代表可逆的加密及解密方法。想理解这个可以先参考下Diffie-Hellman密钥交换算法,这个算法很简单,比RSA还要简单。然后对称钥密钥加密方法有很多,什么DES,AES,Blowfish,若感兴趣可以看看,了解下它们的细节所在。

A derivation of a Riemann zeta function identity

Yesterday, I saw the following Riemann zeta function identity:

\displaystyle\sum_{n=1}^{\infty} \frac{\sigma_a(n)\sigma_b(n)}{n^s} = \frac{\zeta(s)\zeta(s-a)\zeta(s-b)\zeta(s-a-b)}{\zeta(2s-a-b)}.

I took some time to try to derive it myself and to my great pleasure, I succeeded.

Eventually, I realized that it suffices to show that

\{(dd_a, dd_b, d^2 n) : d_a | n, d_b | n : d, d_a, d_b, n \in \mathbb{Z}\}

and

\{(dd_a, dd_b, n) : dd_a d_b | n : d, d_a, d_b, n \in \mathbb{Z}\}

are equal as multisets. As sets, they are both representations of the set of 3-tuples of positive integers such that the third is a multiple of the least common multiple of the first two. In the latter one, the frequency of (a,b,c) is the number of d that divides both a and b such that ab | cd. In the other one, if we write (a,b,c) as (d_1 d_2 a', d_1 d_2 b', c) where \mathrm{gcd}(a', b') = 1, the ab | cd condition equates to d_1^2 d_2 a'b' | c, which corresponds to the number of d_1 dividing a and b and such that d_1^2 | c and with that, d_2a', d_2b' both dividing d_1^2 / c, which is the frequency of (a,b,c) via the former representation.

The coefficients \{a_n\} of the Dirichlet series of the LHS of that identity can be decomposed as follows:

a_n = \displaystyle\sum_{d^2 | n, d_a | \frac{n}{d^2}, d_b | \frac{n}{d^2}} (dd_a)^a (dd_b)^b.

The coefficients \{b_n\} of the Dirichlet series of the RHS of that identity are

b_n = \displaystyle\sum_{dd_a d_b | n} (dd_a)^a (dd_b)^b.

Observe how both are equivalent in that via the multiset equivalence proved above, n determines the same multiset of (dd_a, dd_b) for both and across that, the values of the same function (dd_a)^a (dd_b)^b are summed. Hence the two series are equal.

湾区游

上周底,又跑湾区一趟,为了面试,也为了玩。这次受益匪浅,拿到了比较好的工作,同时也再次得到学习数学的启发。我的一位不善学,疯疯癫癫的,苏犹半朋友,却建议我跟一位正在MIT学数学的美国IMO金牌得主聊天。此人我已被介绍过,通过一位“知名的高才生中间人”,可与此人未说任意有含量的话,从而想这牛人太忙,与我这庸人无话可说。出乎意料,介绍者却说他与牛人沟通频繁,并且将我加入他们俩人的脸书群,后来又加了一位不相信智商,反徐道辉的,女生物博士生,犹裔也。面试之前的晚上,我住在旧金山的宾馆,附近有一家“现代犹太博物馆”,好奇去看了看,楼上关门,楼下没啥好看的。我们在群里所讨论的好多与种族,文化,智商,和学科相关,还记得我曾经对数学尖子开玩笑,美国IMO选手,非亚裔,必犹裔,而他似乎未感到我的玩笑口气,回说他那界有一两位非犹太白人。他还强调自己很美国人,不是那种在以色列待过的。高中时,他选了中文为他的外语,以童话为他爱听的一首中文歌。学术上,给的感觉是专注,单一的纯数学本科生,非常肯定他会走学术道路。他的具体数学兴趣及倾向为组合数学和理论计算机和解析数论。那天晚上,问他知道那几个二次互反律(law of quadratic reciprocity)的证明,他回答一个引用Zolotarev’s lemma的,并且发了个链接。当时,我只知道高斯和(Gauss sum)的那个,而细节已经记不清楚了。我花了一小时细读那个证明,领悟后感觉漂亮无比,引用的工具极其简单。从来没有想到可以将这数论皇后的定理视为,表达为置换的奇偶的积,毕竟Legendre symbol给的是1或-1,与sgn一样,好妙啊。回顾透明Legendre symbol给的基本是在给循环阿贝尔群(\mathbb{Z}/{p\mathbb{Z}})^{\times}的元素奇偶,二次剩余和偶置换在他们对应母群都是指数为2的子群。这又让我想到高斯对于正十七边形可作图的证明也是引用指数2的子群,其由Galois theory对应于度数为2的域扩张。过两天,我又学到了Gauss lemma,就是\left(\frac{a}{p}\right) = (-1)^n, n\{a, 2a, \ldots, \frac{p-1}{2}a\}大于p/2的元素的数量。证明思路很直接,将\{a, 2a, \ldots, \frac{p-1}{2}a\}的大于p/2的元素负掉,可和其他元素从新凑成\{1, 2, \ldots, \frac{p-1}{2}\}. Eisenstein对该定理的证明,我以前知道其存在但没看懂的,引用类似于Gauss lemma的引理,思路及证明策略抓住,这次却清晰了然。二次互反律的美妙我之前无法欣赏,记得对此定理有过一种稀奇古怪,难以思议之感,是没有抓住并且悟觉它的美妙的对称结构。想起在Eisenstein的证明中,画了一个pq的格子,将-1的次数示为格子的下左象限所有的点数,此为(p-1)(q-1)/4的来源。

数论是纯数学比较活的分支,与现在被我看为形式化繁琐枯燥的测度论相反。回想起,我学测度论习题做不出来开始大大怀疑自己数学的能力并且对数学稍失去了兴趣。而数论从某种角度而言有相反的作用。昨天,我从新过了Bertrand’s postulate的源于Erdos的证,对此同样有新的见解,至少感觉是这样。这次很明确它是以好紧限的有易与素数次数相连的\binom{2n}{n}在假设n2n范围无素数情况下,导致未成立的不等式。证明里的关键观察是2n/3n之间的素数不整除,此有大大减小上限的作用。

我有想过回到学校做数学,可是此愿望看来还是非强于我对自己的能力的怀疑加上挣钱的“心里”需要。在所谓的工业界有了一定的见识是大大开阔了眼界,与那些学术界单纯做学问的人恰恰相反。正面看,这给了我更多的实用性思维,眼观,和技能,而反面,这使得我失去,以不可逆转的方式,利于做研究的隔离所排出的干扰。我小时看到人说离开学校再回去很难,现在知道为何人这么说。所以我的回到学校的企图又失败了,下一个工作来了,有新的实用性的挑战和机会。不过,数学我很可能业余还会学学,盼望在此将出前所未有的新视野。

Proof of fundamental theorem of arithmetic

I read it a couple days ago and actually remembered it this time in a way that I will never forget it. It invokes Euclid’s lemma, which states that if p | ab for p prime, then p | a or p | b, which can be proved using Bezout’s lemma. For existence, it does induction on the number of factors, with 1 as the trivial base case. For the non base case, wherein our number is composite, apply the inductive hypothesis on the factors. For uniqueness, assume two distinct factorizations: p_1p_2\ldots p_n = q_1q_2\ldots q_n. By Euclid’s lemma, each of the p_is divides and is thus equal to one of the q_is. Keep invoking Euclid’s lemma, canceling out a prime factor on each iteration and eventually we must end with 1 = 1 in order for the two sides to be equal.