cryptography

密码学背后的数学

想尽量写的浅显易懂一点。
主要包括一些经典加密系统,比如基于DLP问题的加密系统,RSA加密系统,和一些针对这些系统的破解算法,以及
一些处理这些加密系统所需的基本数学工具,比如质数检验,分解算法,概率论,信息论以及碰撞算法。(本文默认各位看官有一些最基础的群论,概率论,排列组合的知识)(本文主要是参考“An introduction to mathematical cryptography by Jeffrey Hoffstein et al.”

acknowledgement:感谢一直以来白上フブキちゃん、湊あくあちゃん、名取さなちゃん、夏色まつりちゃん、猫宮ひなたちゃん、絆アイちゃん、神楽めあちゃん、神楽ななちゃん、笹木咲ちゃん(排名不分先后)给我的支持

简单的替换式密码(凯撒密码)

这个加密方法是以罗马共和时期恺撒的名字命名的,据称当年恺撒曾用此方法与其将军们进行联系。凯撒密码是最简单最原始的加密系统,非常容易被破解。其原理非常好理解,明文中的所有字母都在字母表上向后(或向前)按照一个固定数目进行偏移后被替换成密文。例如,当偏移量是3的时候,所有的字母A将被替换成D,B变成E,以此类推。
例如,当偏移量是左移3的时候(解密时的密钥就是3):

1
2
明文字母表:ABCDEFGHIJKLMNOPQRSTUVWXYZ
密文字母表:DEFGHIJKLMNOPQRSTUVWXYZABC

这个完全可以通过频率分析或者样式单词分析的方法来进行破解,本文不再赘述。

Vigenère 密码

维吉尼亚密码曾多次被发明。该方法最早记录在吉奥万·巴蒂斯塔·贝拉索( Giovan Battista Bellaso)于1553年所著的书《吉奥万·巴蒂斯塔·贝拉索先生的密码》(意大利语:La cifra del. Sig. Giovan Battista Bellaso)中。然而,后来在19世纪时被误传为是法国外交官布莱斯·德·维吉尼亚(Blaise De Vigenère)所创造,因此现在被称为“维吉尼亚密码”。Vigenère密码也是一种比较容易破解的加密系统,它通过适用不同的偏移量来加密不同的字母,为了决定每个字母的偏移量为多少,Alice与Bob首先秘密达成一致使用一个短语或者密钥。Bob然后用密钥中的字母逐个加密明文,通过不可信的信道传输给Alice,Alice再用此密钥进行解密。

假设密钥是“dog”,明文是“yellow”。密钥的第一个字母是d,代表给出了一个3的偏移量,于是Bob将明文的第一个字母向后移动三位,得到密文字母b(记住z后面是a)。密钥的第二个字母是o,偏移量为14,所以将明文的第二个字母向后移动14位得到s。密钥的第三个字母为g,偏移量为6,所以将明文的第三个字母向后移动6位,得到密文r。

然后Bob的密钥已经用完了,这时候我们简单地从第密钥的第一个字母开始加密。即用d加密l,o加密l,g加密o,d加密w。最后我们得到整个密文为bsrocc

再举个例子,Bob想用密钥flamingo加密明文the rain in spain stays mainly in the plain,密文则是ysedivtwsdpmqayhfjsyivtzdtnfprvzftn。

Vigenère密码的破解是可以很吸引初学者的兴趣、给初学者成就感的,虽然有一定的难度但是可以用笔和纸破解出来的,不过过程可能要花上一番笔墨。

理论部分

首先,对Vigenère 密码分析的第一步是找到密钥的长度。我们介绍Kasiski方法,在Friedrich Kasiski的1863年出版的书 Die Geheimschriften und die Dechiffrir-kunst (密码学与解密的艺术)中第一次出现。其主要的想法就是通过查找密文中重复的片段来找到密钥的长度。再英文语境中,因为the,and,but经常出现,我们通常分析三字母的重复片段。

还有一个稍微复杂的方法就是单独分析独立的字母来找到密钥长度。

我们引入Index of Coincidence的概念。
定义$s=c_1 c_2 c_3 \dots c_n$是一个含有n个字母的字符串,则s的Index of Coincidence是在s中随机选择的两个字母是一致的可能性,用 $IndCo(s)$来表示。

我们用排列组合的知识,易证

其中$F_i$是第i个字母出现的频数

用一个例子来说明,我们设

s=”A bird in hand is worth two in the bush”

除掉空格一共有30个单词,则我们可以进行列表进行统计

\ A B D E H I N O R S T U W
i 0 1 3 4 7 8 13 14 17 18 19 20 22
$F_i$ 2 2 2 1 4 4 3 2 2 2 3 1 2

通过上述公式以及表格可计算得到

我们假设如果每个字母出现的概率相等,则可得到$IndCo(s)=\frac{1}{26}\approx 0.0385$。而如果是对普通的英语文本计算IndCo,则它的值大概是0.0685。

0.0385与0.0685,看上去差别很小,但是它确实对于文本的可读性产生了很大的影响。更精确地说:

如果IndCo接近0.068,那么s看上去更像是英语或者采用凯撒密码加密的英语

如果IndCo接近0.038,那么s看上去更像是随机的字符串

我们现在假设Eve知道了一串用Vigenère密码加密的密文s。她猜测密钥的长度为k,她首先要做的就是把s分成$s_1,s_2,s_3, \dots ,s_k$份,
且$s_i$包含了从第i个字母开始的每第k个字母,用数学语言来表示就是:
如果$s=c_1 c_2 c_3 \dots c_n$,那么

我们注意到如果Eve的猜测是正确的,那么每一个$s_i$都是用相同偏移量加密的凯撒密码!这也就意味着我们可以用IndCo进行分析每个$s_i$,如果$IndCo(s_i)$比起0.038更接近0.068,那么我们可以有一定把握认为Eve的猜测是正确的。一般我们说,如果IndCo大于0.06,那么可以认为k是正确的密钥长度

我们现在假设Eve已经通过Kasiski方法或者Index of Coincidence分析法确定了密钥长度。下一步要做的就是要分别确定$s_1,s_2,s_3,\dots,s_k$的偏移量。

假设$s_i$的偏移量为$\beta_i$,$s_j$的偏移量为$\beta_j$。设

如果$s_i$加上一个偏移量$\sigma$后每个字母出现的频率与$s_j$的相似度较高的话,我们可以认为$\sigma$是$s_i,s_j$之间的偏移量之差。

这里我们很自然地引入一个与index of coincidence相类似的概念:mutual index of coincidence。

是两串字符串,那么s与t的mutual index of coincidence是s中的字母与t中的字母相同的概率,用$MutIndCo(s,t)$来表示

并且通过排列组合的知识,易证

类比IndCo,当MutIndCo很大,说明s,t是采用相同的偏移量,如果MutIndCo很小,说明s,t可能采用不同的偏移量。

我们现在回到Eve的例子,现在密文s已经被分成了k份,每一份都是用相同的偏移量进行加密。Eve首先计算所有的MutIndCo

检索计算出来的值,找到大于0.065的值的话,我们就可以认为

最后我们可以得到$\sigma_2,\sigma_3,\dots,\sigma_k$,满足:

这是一个无穷解的方程组,但是好在$\beta_1$的取值为0-25,所以我们通过从0-25不断测试$\beta_1$的取值,找到有意义的的一个取值即是正确的$\beta_1$。

理论部分到此结束,下面通过一个例子来让破解过程更加直观

实践部分

图1
如图1,我们假设该密文为Vigenère加密密文,我们首先分析k(密钥长度)。

采用Kasiski方法对密文进行分析
图2
由图2可以看出,Kasiski方法显示周期很有可能是7。

然后我们再采用index of coincidence进行分析

图3
我们可以看出,当k的值等于7的时候,其平均IndCo比其他k值的情况大得多!因此,我们有足够的理由认为k的值为7。

然后我们计算Mutual Index of Coincidence
图4
从图4可以得出
图5
将方程组全部化成关于$\beta_1$的方程,然后对$s_1$施加不同的偏移量(即$\beta_1$取不同的值)
图6
我们可以看出,当偏移量为3($\beta_1=3$)的时候,keyword是Dickens,并且解密的文本看起来可以接受。我们给文本加上标点符号和空格,最终破译了整个原文本,出自查尔斯狄更斯的《大卫·科波菲尔》:

Whether I shall turn out to be the hero of my own life, or whether that station will be held by anybody else, these pages must show. To begin my life with the beginning of my life, I record that I was born (as I have been informed and believe) on a Friday, at twelve o’clock at night. It was remarked that the clock began to strike, and I began to cry, simultaneously.

至此,Vigenère密码的解密已经全部完成,是不是很有趣?这只是开胃前菜,更有趣的还在后面。

离散对数与Diffie-Hellman

数论简介

从这一节开始,我们进入了现代密码学的范围内了。现代密码学从根本上是基于数论的一些问题与定理产生的,所以我们先学习一下密码学所需的数论知识。
(我们现在所有的运算都是在模算术里讨论,也就是带mod的算术)

可除性

定义:设a和b为整数且$b\neq 0$,如果有一个整数c使得

那么我们说b可以除a,或者说a可以被b除。一般我们记作$b | a$表示b可以除a,用$b \dagger a$表示b不可以除a。

推论:设$a,b,c\in Z$

(a)如果$a|b$且$b|c$,那么$a|c$

(b)如果$a|b$且$b|a$,那么$a=\pm b$

(c)如果$a|b$且$a|c$,那么$a|(b+c)$且$a|(b-c)$

证明省略。

最大公约数

定义:两个整数a,b的最大公约数是指一个可以同时除a和b的最大的正整数d,也就是说$d|a$且$d|b$。最大公约数一般用d=gcd(a,b)来表示

欧几里得算法(辗转相除法)

欧几里得算法是为了快速找到gcd的算法。首先我们定义a,b为正整数,那么a除b,商为q余数为r意味着

那么从上述等式中可以看出,如果d是r与b的公约数,那么d也就是b与a的公约数,于是我们可以得出

不断递归下去,最终我们可以得到余数为0的情况,即gcd(s,0)=s,那么此时s=gcd(a,b)

我们将这个步骤标准化得到欧几里得算法

(1)设$r_0=a,r_1=b$

(2)设$i=1$,

(3) 用第i个r去除第i-1个r,可以得到

(4)如果余数$r_{i+1}=0$,那么$r_i=gcd(a,b)$,欧几里得算法结束

(5)当$r_{i+1}>0$,i加1并且回到步骤(3)

步骤(3)最多重复执行$2log_{2}(b)+1$次。

证明省略。

拓展欧几里得算法

定义:设a,b为正整数,那么等式

总有一对u,v使之成立。如果$(u_0,v_0)$是一对解,那么,每一对解都具有以下形式:

证明:我们知道$a=bq_1+r_2$将其代入$b=r_2q_2+r_3$中,我们可以到得到

然后我们将$r_2,r_3$代入上述等式中,得到

整理一下我们可以得到

关键点在于$r_4=au+bv$。继续这样下去,我们可以得到$r_t=au+bv$,而且有$r_t=gcd(a,b)$。Q.E.D

定义:设a,b为整数,如果$gcd(a,b)=1$,我们可以说a和b互质(coprime)

互质这个概念非常又用,在后面的加密系统中会经常用到。我们有相应的欧几里得算法来解u和v,但是在这里不进行演示了。

模算术

定义:令$m \geq 1$是一个整数,如果a-b可以被m整除,那么我们说a和b对于模m同余。即

推论:令$m \geq 1$是一个整数。

(a)如果$a_1\equiv a_2(mod\ m) , b_1\equiv b_2(mod\ m)$,那么

(b)令a为一个整数,那么当且仅当$gcd(a,m)=1$时,有整数b使得

如果上述整数b存在,那么我们说b是以m为模的a的逆(乘法意义上)。
证明:(a)的证明不难,留作课后练习((

(b)首先假设gcd(a,m)=1。然后拓展欧几里得算法告诉我们,$au+mv=1$,这也就意味着$au-1=-mv$可以被m整除,所以根据定义,$au\equiv 1(mod\ m)$。
然后我们证明当$a\cdot b\equiv 1(mod\quad m)$时,也就可以推出存在某个c使得$ab-1=cm$,所以gcd(a,m)=1。证毕。

费马小定律

令p为一个质数,a为任意的整数,那么

如果学过抽象代数相关的知识,根据拉格朗日定理(有限群G的每个元素的阶均能整除G的阶)即可证明。我们这里用另一种方法进行证明。

证明:如果p|a,很明显a的幂可以被p整除。我们只需要考虑$p\dagger a$的情况。我们考虑下面一个数列:

这里有p-1个数,并且他们都是不同的。这是因为,假设有两个数相同,那么有我们设ja,ka为这个数列里的两个数,假设它们相同,那么

然后我们整理可得

所以p可以整除(j-k)a,但是我们根据题设知道无论是a不能被p整除,而且j和k的取值范围在1到p-1之间,所以j-k的值在-(p-2)到(p-2)之间,那么这之间能被p整除的只有0!从而得出ja=ka,所以假设与之矛盾,推出不可能有两个数相同。

现在我们知道此数列中包含p-1个不同的数,并且取值在1到p-1之间,这说明该数列只是把$1,2,3\dots,p-1$打乱顺序了而已。

因此我们可以知道该数列的乘积正好等于(p-1)!,现在结果已经非常明显了

整理一下可以得到

因为(p-1)!不能被p整除,所以我们可以把等式两边的(p-1)!约去,然后我们就可以得到费马小定理

Q.E.D

Remark:我们现在提供一个快速计算一个数在模算术下的逆的算法:如果p为质数,那么根据费马小定理

所以我们只要通过快速平方算法计算$a^{p-2}$就可以得到a的逆。

Remark:我们注意到如果$a^{m-1}\neq 1\quad(mod\ m)$,那么我们可以说m不是一个质数。这是一件很棒的事情,我们甚至不用知道这个数m的因子就可以判断其是否为质数。

推论:对于一个特定的a,可能会有比p-1更小的次方n使得$a^k\equiv 1(mod \ p)$成立。我们定义最小的一个使上述等式成立的k为a模p的序(order)。我们假设$a^n\equiv 1(mod \ p)$,那么a模p的序k可以整除n,当然也可以整除p-1。

证明留作练习(

原根定理

在讲这个定理前先科普一下,如果学习过抽象代数的知识,我们可以知道域是一个每个非零元素都具有乘法逆的一个可交换环。我们已经接触过很多域了,实数域,复数域等等。我们这次要讲的是$\mathbb{F}_p$,有限域F里含有有限个元素,有限域是密码学里的重要基础。我们可以认为

而加上*号的有限域就是是去掉0元素的$\mathbb{F}_p$

原根定理:令p为一个质数,那么存在一个元素$g\in \mathbb{F}^*_p$,g的次方可以表示该有限域中的任意一个元素。即

具有这种性质的元素g被叫做$\mathbb{F}^*_p$中的原根或者生成子(英文是generators,我不知道对应的翻译)。

它们是$\mathbb{F}^*_p$中具有order=p-1的元素

证明比较难,省略。

例子:
3是有限域7($\mathbb{F}^*_7$)的原根

离散对数(DLP)

我们首先直接给出离散对数问题(Discrete Logarithm Problem)的定义

令g为有限域$\mathbb{F}_p$中的原根,h为其中的一个非零的元素。离散对数问题是找到一个指数x使得

x是以g为底关于h的离散对数,用$log_g(h)$来表示。

Remark:虽然DLP是一个比较难解决的问题,但是只要能解出一个x,那么我们就可以知道无穷个x使等式成立。这是因为:根据费马小定理,我们可以知道$x+k(p-1)$对于每个整数k都可以使等式成立

求$627^i \ mod \ 941$对于$i=1,2,3,\dots$
从图中可以看出,其幂的分布是没有章法可循的,我们求DLP的唯一办法就是从1开始往后计算,直到找到一个正确的x使等式成立。

Diffie-Hellman密钥交换

过程:首先Alice和Bob同意使用同一个很大的质数p,和一个非零整数g。Alice和Bob可以把p和g公开,Eve也可以知道它,这时候(p,g)就被叫做公钥。因为一些接下来将会讨论的原因,g最好是在$\mathbb{F}^*_p$上有较大的质数的序(order)的数。

下一步,Alice选出一个秘密的没告诉过任何人的整数a,同时Bob也选出一个秘密的整数b,Alice和Bob分别用他们的秘密整数去计算

接下来他们互相交换他们计算出来的值,也就是说Alice把A传给Bob,Bob把B传给Alice,通过不可信的信道传送。

最后Alice和Bob再用他们分别的秘密整数去计算

他们通过计算各自得到了A’和B’,但是实际上A’和B’是相等的,这是因为

到此密钥交换就已经完成了。

现在我们来分析一些为什么这种密钥交换方式是安全的。我们通过一个例子来说明。

例子:Alice和Bob同意使用质数p=941以及其原根g=627作为公钥。Alice选择私钥a=347,计算得到A=390,Bob选择私钥b=781计算,得到B=691。Alice把390发送给Bob,Bob把691发送给Alice。它们都是通过不可信的信道发送的,所以我们可以把390和691认为是公开的情报。但是a和b并没有被通信,它们是不公开的。然后Alice和Bob计算

而470就是只被他们俩所知道密钥。

假设Eve看见了整个传送过程,她所知道的信息可以用以下来表示

Eve所不知道的只有a和b,只要知道了a或者b其中一个,Eve就可以解出他们俩的密钥。但是解出a或者b的过程本质上是一个DLP(离散对数问题),所以Eve很难破解他们俩的秘密。

当然,我们这个例子里选的数都过小,现在一般选择$p=2^{1000}$左右为宜,并且g是一个序为质数并且接近p/2的数。

El-Gamal加密系统

尽管Diffie-Hellman密钥交换提供了一种分享随机密钥的方法,但是它还不是一个完整的公钥加密系统,我们这里先介绍El-Gamal加密系统。

首先,和Diffie-Hellman相似,Alice选出一个较大的p和有大的质数的序的g。然后她选出她的秘密整数a,然后计算

然后她发布A,但是隐藏起她的秘密整数a。

接下来Bob要用Alice的公钥来加密他想发送的信息m(假设m是从2到p之间的整数)。Bob随机选择一个k,叫做ephemeral key。它的存在只是为了加密单个信息,每次加密都会换一个新的k。

Bob选择他想发送的信息m,和随机的k,以及Alice公开的的g,p和A计算

然后Bob把$(c_1,c_2)$发送给Alice,那么Alice如何从它们中提取出Bob想发送的信息m呢?她首先计算

然后计算$x^{-1}\ (mod\ p)$(之前介绍过求逆的方法)。

到了最后一步了,将$c_2$和$x^{-1}$乘起来,Alice就得到了m!这是因为

那么如果Eve尝试破解出信息呢?Eve知道公钥p和g以及A,以及$(c_1,c_2)$,但是因为她不知道a,所以无法解出m,而她解出a的方法只有解决DLP(离散对数问题),所以这是一个困难的问题。

例子:Alice用质数p=467以及其原根g=2。她选择a=153作为她的私钥,然后她计算A

并且将g,p,A通过不可信的信道发送给Bob

Bob想要发送信息m=331。他选择随机短暂性钥匙k=197,然后他计算

那么Bob将$(c_1,c_2)=(87,57)$是Bob通过不可信的信道发送给Alice的密文

Alice首先通过她的a=153来计算x

然后算出x的逆得到$x^{-1}\equiv 14\ (mod \ 467)$,最后她即可计算得到m

就得到了Bob想要发送的密文331了。这就是整个加密系统。

我们现在引出一个重要的问题,El-Gamal系统是不是和Diffie-Hellman系统一样难攻破?这里我们给出一个推论

推论:我们假设Eve可以用一种特殊的破解器可以破解El-Gamal系统,那么她可以根据上述条件破解出Diffie-Hellman系统。

证明:比起给出一个严谨的证明,我们通过讨论并解释如何使用El-Gamal的破解器来解决Diffie-Hellan系统。我们回想一下Diffie-Hellman问题,知道

她知道A和b,但是不知道a和b,要求计算$g^{ab}$的值。

我们现在假设Eve可以使用El-Gamal的破解器,这也就意味着如果Eve往破解器里输入p、g、A,$(c_1,c_2)$,那么破解器就会输出信息m的值,即

如果Eve想用这个破解器来解决Diffie-Hellman问题,那么我们令$c_1=B=g^b,c_2=1$,输入到破解器中,我们就可以得到$(g^{ab})^{-1}$的值,然后我们简单地求个逆就可以解出$g^{ab}$,也就解决了Diffie-Hellman问题。

或者我们也可以令$c_2$为一个随机的数,但只要$c_1=B$,我们一样可以解决Diffie-Hellman问题。因为

这时,我们只要计算出m的逆,然后乘以$c_2$就可以得到$g^{ab}$的值。Q.E.D

碰撞算法

因为我们上述的加密系统都是基于DLP的,所以接下来我们要介绍的是针对DLP的一系列攻击算法。

生日悖论

想必大家对生日悖论都略有耳闻吧,碰撞算法就是基于生日悖论而引申出来的,这里我先简要介绍一下它。

假设有40人在一个派对上,考虑下面两个问题。

(1)这些人中存在和你有同一天生日的概率是多少?

(2)这些人中至少有两个人同一天生日的概率是多少?

这两个问题的答案很不同。我们首先计算(1)$Pr=1-(\frac{364}{365})^{40}\approx 10.4 \%$。而第二个问题$pr=1-\prod_{i=1}^{40}\frac{365-(i-1)}{365}\approx 89.1\%$。而碰撞算法就是基于第二个问题的。

碰撞算法:一个盒子里装了N个球,n个球是红色的,N-n个球是蓝色的。Bob随机从盒子中拿出一个球,再放回去,再随机拿第二个球,再重新放回去,然后接着进行下去。他一直进行到拿出了m个球为止。

(a)Bob至少拿出了一个红球的概率是

(b)这个概率的一个下界是

如果N而且m和n都不算太大于$\sqrt{N}\ (eg.m,n<10\sqrt{N})$,那么上述(a)(b)两式差不多相等。

证明的话根据不等式$e^{-x}\geq 1-x \quad for\ all \ x \in \Re$就可以证明,限于篇幅,我们省略证明。

例子:如果我们有N个物品,Bob随机选择n个作为一组,然后返回,然后在选n个作为一组。那么n要多大才有50%的概率有一个物品相同呢?n要多大才有99.99%的概率呢?

Bob使用式子(b)来进行近似

那么我们可以解出$n=\sqrt{N\cdot ln2}\approx 0.83\sqrt{N}$

我们现在解

解$n=\sqrt{N\cdot 10^4}\approx 3.035\sqrt{N}$,这是一个很有趣的事情,这反映了当mn大于N的时候这个函数增长的很快。

针对DLP的碰撞算法

碰撞算法在密码学里有广泛的应用,我们这里先讲针对我们学过的DLP的碰撞算法。对于有限域$\mathbb{F}_p$,碰撞算法解决DLP需要大约$\sqrt{p}$步。当p是一个很大的数的时候,这个算法比p步会节省很多时间。

我们通过一个具体的碰撞算法来阐述一下

Shanks’s Babystep-Ginatstep 算法:G是一个群,且$g\in G$并且g的序N大于2。那么下述算法可以在$O(\sqrt{N}\cdot logN)$步解决离散对数问题。

(1)令$n=1+[\sqrt{N}]$,那么特别地,$n>\sqrt{N}$

(2)写出两组数列,

(3)找到两个数列里相等的一对,$g^i=hg^{-jn}$

(4)那么x=i+jn就是该DLP的一个解

证明省略。

我们用一个例子来说明:我们设g=9704,h=13896,p=17389。g=9704的序N是1242,我们设$n=[\sqrt{1242}]+1=36$并且我们令$u=g^{-n}=9704^{-36}=2494$。下面的表格展示了如何找到一个碰撞
用Babystep-Ginatstep去解决$9704^x\equiv 13896\ (mod\ 17389)$
我们找到了

我们知道$2494=9704^{-36}$,计算

所以x=1159.

现在我们介绍基于碰撞算法的一般理论。

令G为一个群,令$h\in G$并且有序数N,然后假设下面的离散对数问题

有解,那么解可以在$O(\sqrt{N})$步找到。

证明:我们把x拆分成$x=y-z$,那么我们要找到

的解

我们把$h^y$排成一列,$b\cdot h^z$排成一列,去找到两个列中相等的一对。

我们先从1到N中选择随机的指数$y_1,y_2,\dots,y_n$,然后计算

我们注意到上面的数列里的值是在集

中,那么上面的数列就是从集合S中选择n个元素,相当于从含有N个球的箱子中拿出了n个球。

下一步我们从1到N中选择随机的指数$z_1,z_2,\dots,z_n$,然后计算

那么上述数列中的每一个数都在集合S里,也就是说这一步也是从含有N个球的箱子里拿出n个球,我们想知道的是第二次拿出来的球中有第一次拿出来的球的概率是多少。

也就是说,如果$n\approx 3\sqrt{N}$,那么就有99.98%的概率有两个数相等,如果觉得99.98%还是小了,那么当$n\approx 5\sqrt{N}$时,有两个数相等的概率是$1-10^{-10}$

一旦我们找到了两个相等的数,那么我们就知道了$h^y=b\cdot h^z$,也就通过了x=y-z解决了DLP。Q.E.D

那么要花多长时间来找到一个解呢?两个数列有n个元素,所以需要花2n步。更精确的说,其中的每个元素要计算i属于1到N之间的$h^i$,而它需要用快速幂算法花$2log_2(i)$次群乘法来计算$h^i$。然后还要用$long_2(n)$步来计算第一列里的元素是否与第二列里的元素相等。所以总的来说,需要花费

步来解决这个问题。如果我们取$n\approx 3\sqrt{N}$,那么计算时间约等于$13.5\cdot \sqrt{N}\cdot log_2(1.3\cdot N)$。

例子:我们想解决离散对数问题

2在有限域659中的序为658,这是一个原根。
用随机指数碰撞来解决$2^x=390\ in\ \mathbb{F}_{659}$
我们可以看到

所以我们用一个长度为18的数列就解决了DLP(我们还是挺幸运的,当n=18时,我们只有38%的概率有两个数相等)

解是 x=177。

这个方法在理论上是很好的,但是在计算机上实现是有一些缺陷:两个数组的长度太大,需要的计算机内存也过大。我们下一次介绍的Pollard’s $\rho$ 方法可以解决这个问题。

Pollard’s $\rho$ 方法

我们上节说过了,碰撞算法需要大量的内存。Pollard的这个精妙的想法可以几乎不用什么内存,而只用多花一点点计算时间。我们先介绍Pollard’s $\rho$ 方法的抽象形式。

我们设S是一个有限集,并且

是一个可以起到打乱S里面元素的函数。假设我们取其中的一个$x\in S$,然后重复应用函数ƒ去创造一个序列。

换句话说就是,

从S到自身的映射ƒ是离散动力系统(discrete dynamical system)的一个例子,数列

被叫做基于映射ƒ的x的(向前)轨道(orbit),并且用$O_{f}^{+}(x)$表示。

这个集合S是有限的,那么集合S里的元素必定会在轨道$O_{f}^{+}(x)$中出现第二次,我们用下面这个图来说明
Pollard's $\rho$ 方法
因为这个图像很像希腊字母‘rho’,所以像这种基于一个元素的轨道动力系统的碰撞算法,我们称之为$\rho$算法。

$\rho$算法的种类有很多,我们这里介绍Pollard最早提出了的一种,虽然这种方法的效率没有之后几种的高,但是它方便理解,我们就拿它来作为例子。

言归正传,Pollard的想法就是不仅计算$x_i$序列的值,也要计算序列$y_i$。

换句话说,当我们用ƒ迭代一次x的时候,我们同时要用ƒ迭代两次y,但是最终,我们有

经过多久的计算我们才能找到一个i使得上述等式成立呢?通常来说,对于j>i,我们有

我们从之前的rho图型中可以看出,当迭代过$x_T$之后,我们有上述等式成立。

那么$x_{2i}=x_i$当且仅当

的时候成立。最后一个条件等价于$M|i$,所以我们得到当i等于第一个大于T的M的倍数时等式成立。因为$T,T+1,\dots,T+M-1$中的一个可以被M整除,我们可以证明

在下面的理论中,我们将证明T+M约等于$1.25\cdot \sqrt{N}$,所以运行到$\sqrt{N}$步时我们有较大的概率找到一个碰撞。

定理:S是一个有N个元素的有限集,我们让$f:S\longrightarrow S$是一个映射,$x\in S$是一个起始点。

(a)假设向前轨道$O_{f}^{+}(x)={x_0,x_1,x_2,\dots }$有长度为T的尾巴和长度为M的循环,那么

(b)如果映射ƒ足够随机的话,那么T+M的期望值是

之前我们已经证了(a),我们现在来证明(b)。假设我们计算前k个x的值,有多少的概率没有一对相等呢?

因为i相对于N来说很小。我们用下列式子进行近似

我们得到

因为当k比较大的时候

我们得到

我们现在近似出来了$x1,x_2,x_3,\dots ,x{k-1}$都是不同的概率。我们现在假设前k-1个数都是不同的,那么第k个数有相同的概率是多少?相当于有N个元素选中其中k个元素,该条件概率是

那么根据贝叶斯定理

接下来我们算出其期望值

我们接下来需要算出E的值

引理:假设F(t)是一个连续函数,有比较好的微积分性质,且$\int_0^{\infty}F(t)dt$收敛,那么当n很大的时候

证明:我们首先计算t属于0到A的时候,我们可以通过定义知道,该积分等于一个黎曼和的极限

而当n很大的时候,有

然后令A趋向于正无穷即可证。Q.E.D

我们用上面的引理可以得到

Q.E.D

最后一步我们用数值的方法来进行估计,虽然也可以求出它的精确解,其值是$\sqrt{\pi /2}$,留作课后习题。

Remark:

E1是精确解,但是当N很大的时候难以计算。E2和E3是近似。

从图中可以看出E2和E3非常接近,而且当N很大的时候,它们对E1是一个很好的近似。所以我们说用E3来近似E1是合理的。

接下来我们讲Pollard’s $\rho$ 方法的具体实现。

我们现在面临的最大的困难就是要找到一个可以随机打乱S里元素的排列顺序的映射,但是Pollard已经帮我们找好了

Remark:虽然没有人证明过ƒ(x)是不是足够随机,但是从经验来看,它还是挺随机的。

假设我们设置起始点是$x_0=1$,对其不断应用该函数。考虑一下,每一步我们可能是乘以a,可能是乘以g,可能是平方之前的值,所以最后我们会得到

然后我们可以把上面的函数进行拆分得到

同样,我们对于第二个序列

那么我们要找到

我们设

我们根据在$\mathbb{F}_p$有$g^u=a^v$,有

如果gcd(v,p-1)=1,那么我们可以同时乘以v的逆来解决离散对数问题。

更一般的情况下,如果d=gcd(v,p-1)>1,那么我们用拓展欧几里得算法去找到一个整数s

然后两边同时乘以s得到

然后我们可以得到

然后就可以解决离散对数问题。

例子:解决下列离散对数问题

我们的第一步是计算x和y的序列以找到一个$xi=y_i$,同时也计算指数系数$\alpha ,\beta ,\gamma, \delta$
用Pollard's $\rho$方法解决$19^t\equiv 24717\quad (mod\ 48611)$
从表格中我们知道在有限域$\mathbb{F}
{48611}$有$x{548}=x{1096}=33252$
所以我们知道

然后我们化简一下得到$19^{-35140}=24717^{26510}$,再进行化简可以得到

我们下一步可以知道

接下来

所以

也就是

我们列出改对数的可能取值

我们将这些值一个个代入进行验证,以找到正确的解

于是我们找到了答案$log_{19}(24717)=37869$。

中国剩余定理

中国剩余定理描述了如何解决一个一元的线性同余方程组

且gcd(m,n)=1。中国剩余定理告诉我们我们可以找到符合这个方程组的余mn的解。

中国剩余定理在数论中有很广泛的应用,我们这里需要用到中国剩余定理来解决DLP。我们首先通过一个例子来展示中国剩余定理

例子

首先$x\equiv 1\quad (mod \ 5)$告诉我们

将其代入第二个方程可以得到

我们通过计算得到gcd(5,11)=1,那么我们可以通过乘以5的逆来解出y。通过拓展欧几里得算法我们可以知道5在11下的逆是9

我们再把y代入x=1+5y之中可以得到

定理:(中国剩余定理)我们设$m_1,m_2,m_3,\dots ,m_k$是两两互质的整数,也就是说

设$a_1,a_2,\dots,a_k$为随机的整数,那么我们有

有解x=c。如果x=c和x=c’是同解,那么

证明省略,限于篇幅原因(

我们再通过一个例子加深一下理解

例子:我们解决

首先我们从第一个方程开始,我们知道

代入第二个方程可得到

化简得到$3y=1\quad (mod\ 7)$,然后两边同时乘以3的逆5可以得到$y\equiv 5\quad (mod\ 7)$。然后代入x=2+3y得到

前两个方程的同余解是x=17+21z,我们把它代入第三个同余方程可以得到

化简得到$5z\equiv 3\ (mod \ 16)$,我们两边同时乘以5在16下的逆13,得到

最后再将其代入x=17+21z,得到x=164。

解决模数为组合数的同余

对于解决一个组合数的模,用中国剩余定理解决几个质数或者质数的次方的同余方程组就行。我们通过阐述如何找到模数为m的平方根来说明这点。如果一个数是质数的话,想找到它的平方根是比较容易的,而且如果是模4余3的质数的话,找到平方根这种事就变得非常容易了。

我们现在讨论一个推论:p是一个质数且满足$p\equiv 3\ (mod \ 4)$,令a为一个整数且$x^2\equiv a\quad (mod\ p)$有解,那么

有解,那么它满足$b^2\equiv a\ (mod\ p)$,当a是一个平方根的时候此推论才有效,之后我们会讲一个快速判断一个数是否有平方根的方法。

证明:g是p下的原根,a是g的幂,为了使得a有平方根,我们令a是g的偶数次方,$a\equiv g^{2k}\ (mod\ p)$,然后我们计算

所以b是a的在p下的平方根。Q.E.D

假设我们想要计算模数为m的平方根,但是m并不是一个质数。一个有效的方法是先计算每个质数或者质数的次方的平方根,然后再用中国剩余定理结合起来。我们通过一个例子来阐明:

我们想找到同余方程

的解,但是437=19*23,那么我们把原式拆分成两个

因为23和19都模4余3,然后我们可以通过之前的推论知道

我们选择两个正的解,然后用中国剩余定理解决同余方程组

我们解得$x\equiv 236\ (mod \ 437)$。

当然解不是唯一的我们可以取负数

同样是其一个平方根。如果模数是质数,那么就只有这两个根了,但是437=19*23是和数,那么就有另外的两个。为了找到这两个根,我们取8和6中的一个为负数,然后我们可以得到x=144和x=293。

之前的例子告诉我们,如果知道如何把m除成质数之积,那么计算平方根就会变得相对简单。但是,假设m非常大我们没办法取除它,那么找到对应的平方根也就变得非常困难了。而且,更准确的说,如何除m和计算模数为m的平方根一样困难。

事实上,当m是一个很大的组合数的时候,就连判断一个给定的整数a是否有平方根都是非常困难的。我们之后要讲的Goldwasser-Micali加密系统就是通过二次互反律来判断一个数是否有平方根来加密的。

The Pohlig-Hellman 算法

在我们介绍这个算法之前,希望读者可以多熟悉一下中国剩余定理

Pohlig-Hellman算法是一种针对DLP的攻击算法。在离散对数问题中,我们要解决等式

因为p是一个质数,所以显得好像中国剩余定理起不到什么作用。然而,回想一下解$x\in Z/(p-1)Z$,说明了x只在0到p-1内取值,这提醒了我们把p-1分解成质数之积对于决定DLP的难度起到了很大的作用。更一般的说,如果G是一个群,$g\in G$且序数为N,那么在G中$g^x=h$仅仅被模N所决定,所以N的分解就显得很有关系。这就是Pohlig-Hellman算法的核心。

定理:令G是一个群,假设我们有一个算法解决任意一个序为质数的的DLP。更确切的说,如果$g\in G$的序数为$q^e$,那么我们可以在$O(S_{q^e})$步内解决$g^x=h$。那么现在假设$g\in G$有序数N,并且N可以被分解成

那么DLP可以在

步内解决。

我们用下面的方法实现:

(1) 对于每个在[1,t]之间的i,我们令

我们注意到$g_i$的序是$q_i^{e_i}$,所以我们用之前说的算法来解决下列离散对数问题

(2)然后我们用中国剩余定理来解决

就可以得到原来DLP问题的解。

证明:运行时间是非常清楚的,步骤(1)要花

步,步骤2用中国剩余定理要花上O(logN)步。在实际情况下,因为中国剩余定理的运行时间和第一步想比很小,我们可以忽略其运行时间。

我们从(2)可以知道,对于每一个i我们有

我们接下来计算

现在我们知道了

接下来我们观察下列的序列

它们的最大公约数为1。我们用拓展欧几里得算法可以得到

我们从1到t在同余式乘以$c_i$,然后我们得到

然后我们再有之前拓展欧几里得算法得到的结果可以得到

也就得到了x。Q.E.D

Pohlig-Hellman算法告诉我们如果一个群的序数可以被分解成小的质数(我们叫做光滑数,之后将重点讨论),那么这个加密系统是不安全的。更一般的说,如果$g^x=h$中g可以被分解成小的质数的话,解出x将会变得简单。特别地,它被应用在有限域p的DLP问题中,如果p-1可以被分解成小的质数的情况下。但是因为p-1总是偶数,我们能采取的最好的办法就是让p=2q+1,q是一个很大的质数。

Pohlig-Hellman算法或多或少降低的DLP的难度,其降低的是序为和数的情况下的简化法,但是我们还是可以通过降低序数为质数的DLP运行时间进一步简化,接下来我们要讨论的推论可以将之前的$O(S_{q^e})$步降低到$O(eS_q)$步。其思想非常简单:如果g的序数是$q^e$,那么$g^{q^{e-1}}$的序数为q。重复这个步骤我们将得到最终的答案。

推论:令G是一个群,假设q是一个质数,假设我们知道一个可以在$S_q$步内解决g的序数为q的DLP。那么我们也可以解决离散对数问题

证明:证明的关键在于把指数x写成以下形式

我们要求的变成了$x_0,x_1,x_2,\dots$,我们知道元素$g^{q^{e-1}}$的序数为q,然后我们就可以计算

因为$(g^{q^{e-1}})^{x_0}$在G中的序数为q,那么下列等式

是一个序数为q的离散对数问题。根据假设,我们知道我们可以在$S_q$步内解出$x_0$。

然后我们再计算

我们之前已经解出了$x_0$,并且$g^{q^{e-1}}$的序数是q。为了找到$x_1$,我们要解决离散对数问题

来找到$x_1$。我们用给定的算法可以在$S_q$步内解出来。所以在$O(2S_q)$步内我们解出了$x_0,x_1$,并且他们满足

同样的,为了解出$x_2$,我们需要解决离散对数问题

我们进行推广,在我们解决了

之后,要解决离散对数问题

任意一个这种DLP序数都为q,所以每一个都可以在$S_q$步内解出来。

所以在$O(eS_q)$步后,我们得到了

就解出了离散对数问题。Q.E.D

例子:解决离散对数问题

质数p对于的p-1被$5^4$整除,然后我们可以很容易验证5448的序数就是$5^4$。我们的第一步是解出$x_0$

然后可以得到$11089^{x_0}=11089$,可以观察出来答案就是$x_0=1$。接下来我们要计算

然后我们得到$11089^{x_1}=3742$,因为该DLP的序数为5,我们只要从1到4进行遍历即可。然后我们解得$x_1=2$,接着我们计算

然后化简得到$11089^{x_2}=1$,所以令$x_2=0$即是该方程的解。最后一步我们计算

化简得到$11089^{x_3}=6320$,我们解得$x_3=4$,我们的最终答案就是

我们接下来再与之前序数为和数的情况结合起来,用例子来阐述一个完整的Pohlih-Hellman算法。

例子:考虑下面离散对数问题

23是在有限域11251中的一个原根,那么其序数就是$11250=2\cdot 3^2\cdot 5^4$,可以被分解成小质数的积的形式,那么我们这里Pohlig-Hellman算法就可以很好的派上用场了。第一步就是要分别解决三个离散对数问题

q e $g^{p-1}/q^e$ $h^{p-1}/q^e$ 在$(g^{p-1}/q^e)^x=^{p-1}/q^e$中解出x
2 1 11250 11250 1
3 2 5029 10724 4
5 4 5448 6909 511

然后我们在用中国剩余定理解决同余方程组

解得x=4261。

Index Calculus方法

Index Calculus方法是一个在有限域$\mathbb{F}_p$中解决离散对数问题的方法,先申明一点,它只适用于有限域$\mathbb{F}_p$,对于之后的圆锥曲线群的离散对数问题并不是很好用,而Pohlig-Hellman适用于所有群的离散对数问题。但是在有限域F中它比Pohlig-Hellman算法时间复杂度更小。(吐槽一下,Index Calculus我不知道该怎么翻译,wiki也没查到,就直接用英文算了)

Index Calculus方法的思想很简单。我们想解决离散对数问题

我们不直接把x解出来,取而代之,我们选定一个值B,然后解决离散对数问题

换句话说,我们计算每个$l\leq B$的质数的离散对数$log_g(l)$。

计算完之后,我们观察

直到我们找到一个k使得$h\cdot g^{-k}\ (mod\ p)$是一个B-光滑数(这个之后会讲,B-光滑数是指可以被分解成小于B的质数的积的形式的数),然后对于这个k我们有

对于特定的指数$e_l$,我们把上式重写成

其中$log_g(h)$就是我们想解的离散对数,所以我们要找到的就是对于小质数l的$log_g(l)$。想找到它的话我们随机选择一个i作为指数计算

如果$g_i$不是一个B-光滑数,那么我们忽略它,如果它是一个B-光滑数,那么我们可以把它分解成

然后我们有以下关系

通过找到多于$\pi(B)$(小于B的质数的个数)上述形式的等式,我们就可以通过线性代数的知识解出这些$log_g(l)$。

还有一个问题就是,我们上面所说的线性方程组是同余模p-1的,标准的线性方程组解法,比如高斯消元法在模为和数的情况下不能成立,因为这些数没有乘法逆。而中国剩余定理可以解决这个问题,首先我们先解出每个模为q的同余方程,且q是一个可以除p-1的质数。如果p-1最高可以被q的e次方除尽的话,那么我们将等式同时提升到q的e次方。最后,用中国剩余定理将它们全部结合起来得到关于模p-1的同余方程。实际上,为了防止Pohlig-Hellman算法的攻击,我们一般选择的p-1是2和一个质数的乘积,这也简化了Index Calculus方法的计算量。

我们下面通过一个例子来阐明:

用Index Calculus方法解决下面离散对数问题

我们注意到37是模18843下的原根。我们取B=5,然后我们随机选择x使$37^x$是一个5-光滑数。我们假设找到了以下等式

然后我们令

我们要解下列线性同余方程组

而p-1=18442可以被分解成2和9221,且9221是一个质数。我们可以把上述方程组分成两个方程组,然后再用中国剩余定理结合起来

结合起来我们可以得到

于是我们就得到了

我们的最终目标是解决

我们计算$211\cdot 37^{-k}$随机选择k以找到一个数是5-光滑数,假设经过尝试我们找到

用我们之前计算出的2,3,5的离散对数可以得到

我们可以用以下方法粗略地估计一下index calculus方法的运行时间。首先我们需要找到$\pi (B)$个$g^i\ (mod\ p)$形式的B-光滑数。我们建议令$B=L(p)^{1/2}$,理由之后会讲。那么我们要检查大约$L(p)^{\sqrt{2}}$个i。我们还要检查每个值是否是B-光滑数,但是之后也会将一种加速这个过程的方法。基于这个方法,运行时间可以被减少成$L_{1/3}(p)$。在任何情况下,index calculus方法都是一个亚指数运行时间的算法。顺便提一句,无论是那种算法,对于解决圆锥曲线群中的DLP都是完全的指数运行时间的。

整数分解和RSA

Euler‘s Formula 和模pq下的根

在我们之前学的Diffie-Hellman密钥交换和El-Gamal加密系统都是基于费马小定理来完成的。费马小定理表达了质数的一个优美的性质

那么很自然地,我们想问一个问题,假设我们用任意一个整数m取代质数p,那么$a^{m-1}\equiv 1\ (mod\ m)$成立吗?虽然我们可以通过一些计算来知道它是不成立的,但是在这节中,我们想找到费马小定理当m=pq时的规律(p和q是两个不同的质数)。这种情况在加密里是最重要的一种。

我们从一个例子开始。关于模15的数的次方是怎么样的呢,我们通过计算发现

为什么会出现这样的情况呢?我们思考一下就可以发现对于3,5,6,9,10,12与模数15的最大公约数不为1,但是对于a=1,2,4,7,8,11,13,14与模数15互质。这个例子暗示了如果a与m互质的话费马小定理可能成立。

我们再来探究一下为什么指数4可以成立。我们可以把原式拆分成

3和5都是质数,所以有

所以对于4来说是成立的,接下来我们陈述RSA加密系统背后的基础等式
定理:令p和q是两个不同的质数,并且令

那么

特别的,如果p和q都是奇数的质数,那么

证明

同理我们也可以得到

那么这意味着$a^{(p-1)(q-1)/g}-1$可以同时被p和q整除,所以它可以被pq整除。Q.E.D

我们知道El-Gamal加密系统和Diffie-Hellman密钥交换的可靠性依赖于解决等式

a,b,p已知,要求的是指数x的难度。而我们下一节要讲的RSA加密系统的可靠性依赖于解决等式

e,c,p已知,要求的是x的难度。也就是依赖于在模p下解出c的e次的方根的难度。

这个假设是合理的吗?如果N是一个质数,那么解出c的e次方根就会很容易。我们下面用一个推论进行说明

推论:令p是一个质数,令e是一个满足gcd(e,p-1)=1且大于或等于1的整数,我们知道e有一个在模p-1下的逆

那么同余式

有唯一解$x\equiv c^d\ (mod \ p)$

证明:如果$c\equiv 0\ (mod \ p)$那么$x\equiv 0\ (mod \ p)$就是唯一解,那么我们就解出来了。所以我们主要考虑
$c\neq 0\ (mod \ p)$。我们知道$de\equiv 1\ (mod\ p-1)$意味着存在一个整数k使得

然后我们来证明$c^d$是$x^e\equiv c\ (mod \ p)$的解:

于是我们就知道了$x=c^{de}$。为了确认这个解是唯一的,我们假设存在$x_1,x_2$是该同余方程的解,我们刚刚证明了对于非零的数z我们有$z^{de}\equiv z\ (mod \ p)$,然后我们知道

那么$x_1,x_2$在模p下是一样的,我们证明了解的唯一性。Q.E.D

我们再考虑模为和数N的情况,如果知道如何将N分解成质数的话,解决c的e次方根就会变得简单。我们下面的这个推论说明了当N=pq,pq是两个质数的情况。

推论:p和q是两个不同的质数,且令e大于等于1且满足

那么我们有一个在模(p-1)(q-1)下e的逆

那么下面的同余

有唯一解$x\equiv c^d \ (mod \ pq)$。

证明:我们知道

然后我们计算

我们接下来证明解是唯一的。假设x=u是另外一个解,那么

所以每个解都等于$c^d\ (mod \ pq)$,所以它是唯一解。Q.E.D

例子:我们想解决下列同余方程

我们通过计算知道N=pq=64394=229*281,然后我们需要解决同余式

其中63840=(p-1)(q-1)=228*280,我们用拓展欧几里得算法可以得到$d\equiv 53509\ (mod \ 63840)$,我们就可以得到

在了解这一节所讲的内容后,之后的RSA的流程就变得很清晰了。

RSA加密系统

这节我们要讨论的RSA加密系统是第一个被发明的也是最广为人知的加密系统。RSA以它的作者 Ron Rivest, Adi Shamir, Leonard Adleman 的名字命名。我们下面通过一个表格来说明RSA加密的步骤

Bob Alice
密钥创建
秘密地选择质数p,q,选择一个加密指数e使得gcd(e,(p-1)(q-1))=1,发布N=pq以及e
加密过程
设明文是m,使用Bob的公钥(N,e)计算$c\equiv m^e\ (mod \ N)$,把密文c发送给Bob
解密过程
计算出满足$de\equiv 1 \ (mod\ (p-1)(q-1)$的d,计算$m’\equiv c^d \ (mod \ N)$,m‘就等于明文m

用一句话来说就是:Bob选择两个质数,找一个与(p-1)(q-1)互质的e,然后把N=pq和e作为公钥。Alice计算明文在模N下的e次方,然后发给Bob,Bob再计算e在(p-1)(q-1)下的逆d,然后再计算密文在模N下的d次方就是明文了。

我们再通过一个例子来说明:

RSA公钥创建:Bob选择两个质数p=1223,q=1987,然后得到N=pq=2430101。他再找到e=948047且有

RSA加密:Alice把她的明文转化成一个大于0小于N的整数m,我们设m=1070777。然后Alice用Bob的公钥(N, e) = (2430101, 948047)计算

Alice把密文c发送给Bob。

RSA解密:Bob计算满足

的d,他得到d=1051235。Bob然后可以计算出明文m

RSA加密过程很清晰明了,看几遍就可以轻松背下来。

在这个系统中,N被叫做模,e被叫做加密指数,d被叫做解密指数。我们知道如果我们选择一个小一点的加密指数或者解密指数,计算会变得更简单。但是当然,Bob不能让它们俩都很小,因为如果d和e中的一个被选定后,另一个只能由等式$de\equiv 1\ (mod \ (p-1)(q-1)$来决定。

我们先来选一个小一点的e(当然我们不能选择e=1,因为如果e=1的话,明文就和密文是一样的了。我们也同样不能选择e=2,因为e要与(p-1)(q-1)互质)我们选择e=3,到现在为止,我们一般认为e=3和选一个比较大的e有相同的安全性,虽然有一篇论文对此提出了一些疑问。如果想要快速加密且担心e=3过小,一般会选择$e=2^{16}+1=65537$,这个幂次在计算上比较简便。

如果Bob想选一个小一点的d,那么e就会相对较大。但是选一个小的d是不可取的,因为已经有论文证明了当$N^{1/4}$的时候,Eve可以用连分数的理论来破解RSA。

Bob的公钥N=pq,是两个秘密的质数的乘积,如果Eve知道(p-1)(q-1)的值,那么她就可以破解这个加密系统。我们展开(p-1)(q-1)

因为N=pq,而且N作为公共知识已经被Eve知道了,那么Eve只要知道p+q的值就可以解出(p-1)(q-1)了。实际上如果Eve知道了pq和p+q,那么她可以非常轻易地算出p和q,通过

X的两个根就是p和q。所以对于Eve来说找到(p-1)(q-1)的值和找到p,q的难度相同。

最后,很重要的一点,我们已经看到了找到(p-1)(q-1)很分解N难度差不多,但是这并不意味着Eve只能通过这两种方式破解密文,Eve最终要做的还是解出同余式$x^e\equiv c\ (mod \ N)$,虽然没有人知道是否有一个有效的算法在不知道(p-1)(q-1)的前提下解出x。但是有论文指出计算模N的次方根比分解N要简单。(注:我查了一下这篇论文发布于1998年,但是我找到一篇2009年的论文说一般情况下,如果分解N困难的话,那么没有高效的算法可以解决RSA问题)(这里提供一个Futher Reading)。

质数检验

Bob在RSA加密中首先需要选择两个非常大的质数p和q。那么问题来了,怎么确保Bob选择的p和q是质数而不是和数。如果Bob选择的两个数p和q中有和数,而且这个和数里有小的质数因子,那么Eve就会很容易破解这个加密系统。

那么如果检验p和q是不是质数呢?举个例子Bob随机找了一个比较大的数

他想知道n是不是质数。首先Bob搜寻小的因子,但是Bob没有找到小于1000000的任何因子。于是他就开始怀疑n可能是质数了。然后他计算$x^{n-1}\ (mod\ n)$,然后他发现

根据费马小定理,上述等式告诉了他n是一个和数,虽然他不知道n的任何一个因子。

Bob决定再选一个数来检验其是否为质数

首先发现n不能被小的质数整除。然后Bob再用费马小定理进行检验,他发现

费马小定理只证明了n是质数是$a^n\equiv a \ (mod \ n)$的充分条件,我们不能反推出n为质数。我们只能认为它有一定的概率不是一个和数。我们举个例子

定义:给定一个整数n,如果有整数a

我们就说a是n(是和数)的见证数。我们知道如果有一个数是n的见证数,我们就可以完全认为n是和数。如果通过不断的确认,但是还是找不到n的一个见证数,那么我们只能认为有很大的概率n是一个质数,但是并不能确认。

假设我们就算确认完了所有与n互质的数都不是n的见证数,我们仍然不能确认n是一个质数。这是因为一种神奇的数,Carmichael数的存在。所谓Carmichael数是指对于所有与n互质的整数a,都有$a^n\equiv a\quad (mod\ n)$的和数。举个例子,数561是和数,561=31117,但是对于任意的与561互质的a都有

虽然Carmichael数很少,但是已经有人证明过有无穷多个Carmichael数的存在。所以Bob需要用一种更可靠的方法来检验一个数是否为质数。我们接下来讲的Miller-Rabin检验。

推论:令p是一个质数,且令q是一个奇数

我们令a是一个不能被p整除的数,那么下面两种情况必有一个发生:

(a)在模p下$a^q$同余于1

(b)在模p下$a^q,\ a^{2q},\ a^{4q},\ \dots ,\ a^{2^{k-1}q}$中的一个同余于-1

证明:我们观察下列数列

我们由条件知道数列中的最后一个数等于$a^{p-1}$,在模p下同余于1。数列中的每一个数都是前面一个数的平方,那么下面两个可能中必有一个发生:

(a)该数列中的第一个数在模p下同余于1

(b)数列中的某一个数并不同余于1,但是当它平方时同余于1。那么满足

的数只有b=-1,所以数列中的某个数同余于-1。Q.E.D

定义:令n,q是奇数,且$n-1=2^kq$,如果对于与n互质的a满足下面两个条件

那么我们称a为n(是和数)的Miller-Rabin证明。

步骤 操作
1 如果n是偶数或者1<gcd(a,n)<n,返回和数
2 令$n-1=2^kq$,q是奇数
3 令$a\equiv a^q\ (mod \ n)$
4 如果$a\equiv 1\ (mod \ n)$,返回测试失败
5 从$i=0,1,2,\dots , k-1$循环,如果$a\equiv -1\ (mod\ n)$,返回测试失败。否则,令$a\equiv a^2\ (mod\ n)$
6 返回和数

从推论可以知道,如果存在一个a是n的Miller-Rabin证明,那么n一定是一个和数。现在如果Bob想检验n是不是一个质数,他用Miller-Rabin检验运行一些随机选择的a。为什么用Miller-Rabin检验比直接用费马小定理来的好呢?因为用Miller-Rabin检验在遇到Carmichael数的时候不会像费马小定理检验一样判断错误。而且事实上,每一个和数都有很多个Miller-Rabin证明.

推论:令奇数n是一个和数,那么在1到n-1之间有至少75%的数是Miller-Rabin证明。证明不是很难,但是省略。

Bob想找到一个大的质数,他用他选择的一个大数运行(假设10次)Miller-Rabin检验,如果有任何一个数a是n的Miller-Rabin证明,那么Bob知道它是一个和数。假设Bob没有找到任何一个Miller-Rabin证明,那么根据上述推论,我们可以很自然地知道n是一个和数的概率最多是$(25 \% )^{10}\approx 10^{-6}$,这已经算是一个很小的概率了,如果他仍然觉得不放心的话,可以运行100次,如果没有一个Miller-Rabin证明,那么n是一个和数的概率最多是$(25 \% )^{100}\approx 10^{-60}$(虽然这个概率看上去很有道理,但是它的值并不是准确的。根据概率论的知识,我们需要计算当n是和数的时候10次Miller-Rabin检验失败的条件概率)

例子:我们通过一个例子来说明Miller-Rabin检验。我们令a=2,n=561,561是一个Carmichael数。我们有

然后计算

第一个数既不是1也不是-1,之后的数也没有同余于-1的,那么2是561的一个Miller-Rabin证明,所以561是一个和数。

质数分布

如果Bob随机选择一个数,那么它有多大的可能是质数呢?我们下面非常简单地介绍一下数论里最有名的定理。我们先给出一个定义:

对于任意数X,令

举个例子,$\pi(10)=4$,因为在2到10之间只有2,3,5,7是质数。

质数定理

证明太难了,需要用到复分析相关的知识,省略。

例子:在900000到1000000之间大概可以找到多少个质数呢?通过质数定理我们估算

事实上在900000到1000000之间有7224个质数。

对于密码学来说,我们需要很大的质数。以二进制来说一般是1024位,我们来计算以在$2^{1023}<p<2^{1024}$之间大概有多少个质数

所以实际上,在这个区间里有很多个质数。

从直觉上来说,从1到X之间的数,是质数的部分占大概1/ln(X)。我们换一种说法

例子:假如Bob想找到一个1024-bit的质数,那么上面的陈述告诉我们$N\approx 2^{1024}$是一个质数的概率大概是0.14%,所以大概尝试700次后可能会发现一个质数。但是Bob用了一个更聪明的方法,他知道他不想要一个偶数,也不想要一个能被3或者5整除的数,等等。Bob于是想要找到于2,3,5,7,11互质的数。为了做到这点,Bob首先选择了一个于$2\cdot 3\cdot 5\cdot 7\cdot 11=2310$互质的数,他选择了1139,然后他仅仅考虑下列形式的N

那么N是质数的概率大概是

所以Bob随机选择一个具有上述形式的1024位的N的话,他会有0.67%的概率得到一个质数,所以从概率上来说,他只需要尝试150次就可以找到一个质数。

关于质数的分布有许多深层次的待解决的问题,其中最著名的就是黎曼猜想了。黎曼猜想需要用到一些复分析的知识,在这里我们只简单介绍一下。黎曼zeta函数被定义为

当s是一个实部大于1的复数的时候收敛。黎曼猜想说如果$\sigma,t$是实数且$0\leq \sigma \leq 1$时有$\zeta(\sigma + it)=0$,那么实际上有$\sigma=\frac{1}{2}$。

看上去它似乎和质数没什么联系。然而,我们不难发现黎曼zeta函数等于

所以黎曼zeta函数里包含了很多关于质数的知识。虽然有无数的例子暗示了黎曼猜想是正确的,但是从150年前被提出到现在,数学家们并不能证明这一点。

Primality proofs versus probabilistic tests

Miller-Rabin检验是找到可能的质数的有效方法。一般选择50-100次检验后这个数仍然没有Miller-Rabin证明,那么有非常大的可能性它是一个质数。但是Bob仍然对结果不满意,他想确切的知道这个数到底是不是质数。

从原理上来说,方法是非常简单的,Bob只需要从1到$\sqrt{n}$确认能不能整数n即可。如果没有一个数可以整除n,那么n肯定是一个质数了。但是不幸的是,这个算法是一个指数时间算法,Bob的n太大了,以至于就算太阳熄灭了Bob也算不完。

我们需要一个多项式时间的算法来确认一个数是否是质数。如果黎曼猜想是正确的,那么下面的推论就是正确的

推论:如果黎曼猜想是正确的,那么每一个和数n都有一个Miller-Rabin证明a满足

证明省略。

这是一个多项式时间的算法,我们只要用Miller-Rabin检查所有小于$2(ln n)^2$的数,如果有一个Miller-Rabin证明,那么n就是和数,否则就为质数。

自从1978年RSA发明之后,人们对找到一个不是基于像黎曼猜想这样的没被证明的猜想的多项式时间的质数检验算法产生了浓厚的兴趣。对于这方面的研究终止于2002年,这时,M.Agrawal, N.Kayal, N.Saxena终于找到了一个这样的算法。对他们的算法改进后有以下结果。

定理:(AKS质数性检验)$\forall \ \epsilon>0$,存在一个算法可以决定性地确定一个数是否是质数在$O((ln n)^{6+\epsilon})$步内。

证明:这里不提供证明,但是可以去看AKS发表的原始论文“PRIMES is in P”。

上述定理代表的是现代算法数论的一个胜利。因为AKS算法比Miller-Rabin算法慢很多,它在实践上对密码学的贡献不是很大。实践上,如果一个数通过了50-100次Miller-Rabin检验,大多数人很乐意认为这个数是一个质数。

Pollard’s p-1分解算法

我们之前的章节讲了如何检查一个数是否是质数。那是极好的,RSA加密系统需要很大的质数。

RSA的安全性依赖于分解大数的困难程度。整数分解的理论至少可以追溯到古希腊,但是只有当计算机被发明后,人们才开始研究整除大数的方法。为了使得RSA更加高效,我们想使得模N=pq尽可能的小,但是另一方面,当N过小的时候,加密通信就有可能不安全。所以我们需要知道整除大数到底有多难,并且要知道一些现在的攻击算法的有效性。

我们首先讲Pollard‘s p-1方法,这也是一个非常有趣的算法。虽然这种方法并不能对所有的大数都很有效,但是对特定类型的大数是非常有效的。

假设我们通过某种方式知道了一个有以下性质的L

这也就意味着有整数i,j,k且k不等于零

我们随机选择一个整数a,然后计算$a^L$,根据费马小定理我们有

指数k不等于0,那么$a^k$不太可能同余于1。有很大的可能性,对于大多数a,我们有

这也就意味着我们可以通过简单地计算gcd来得出p

那么,我们怎么找到这个L呢?Pollard观察到如果p-1碰巧是许多小的质数的乘积,那么它可以整除n!,如果n不是太大的话。所以对于每个$n=2,3,4,\dots $我们计算

(一般我们选择用a=2)如果gcd等于1,我们找下一个n,如果gcd等于N,那么很不幸,我们可能要重新选择一个a。如果我们计算gcd得到一个介于1到N之间的数,那么我们就找到了N的一个因子。

在我们讲Pollard‘s p-1算法的时候,首先需要先解决两个问题。第一个就是$a^{n!}-1$的大小,首先我们取a=2,然后我们取一个比较小的n,比如n=100,那么$2^{100!}$有超过$10^{157}$位数!幸运的是,我们并不需要精确计算出这个值,我们感兴趣的是它和N的GCD,所以我们只需要计算

就可以了。那么要计算$a^{n!}\ (mod \ N)$的值的话需要计算多久呢?快速指数算法告诉我们计算$a^k\ (mod \ N)$需要花费$2log_2 k$步,每一步都是模N下的乘法。Stirling公式告诉我们如果n很大的话,n!近似等于$(n/e)^n$。所以我们可以在$2nlog_2(n)$步内完成$a^{n!}\ (mod\ N)$的计算。所以我们认为计算$a^{n!}\ (mod \ N)$是可行的。

第二,我们需要甚至不需要计算n!。假设我们已经计算出了$a^{n!}$,那么我们下一步只需要计算

就可以了。这也就引入了我们接下来的算法。

步骤 操作
1 设置待被分解的数N以及令a=2
2 从$j=2,3,4,\dots$循环到一个特定的上界
3 令$a=a^j\quad (mod \ N)$
4 计算$d=gcd(a-1,N)$
5 如果$1<d<N$那么算法成功,返回d的值。
6 j自增,从步骤2开始循环。

例子:我们用Pollard的p-1方法来分解N=13927189。首先计算一下$gcd(2^{9!}-1,N)$,然后再应用上述算法。

最后一行给了我们一个p=3823。这是一个质数,那么另一个因子$q=N/p=13927189/3823=3643$也是一个质数。指数14!行得通是因为p-1可以被分解成小的质数

另一个因子$q-1=3642=2\cdot 3\cdot 607$,不是小的质数的乘积。

我们可以注意到Alice和Bob可以很轻松地避免被Pollard的p-1算法破解,他们只要令p-1和q-1不能被完全分解成小的质数即可。我们会想起在介绍攻击DLP的算法,Pohlig-Hellman算法的时候介绍了,如果g的序数N可以被分解成小的质数的话,这个加密系统也会变得不安全。那么很自然地我们知道,对光滑数的研究就凸显出其重要性。首先提出一个定义:一个所有的质数因子都小于或等于B的整数叫做B-光滑数。那么我们提出一个问题

所有的现代整数分解算法的有效性都取决于这个问题的答案。我们将在下面几节进行探讨。

通过平方差的分解算法

到目前为止最强有力的分解算法依赖于下面这个最简单的公式:

平方差公式,中学的时候就耳熟能详的公式。

我们现在来说明怎么用它来分解整数。它的想法非常简单,为了找到分解N的方法,我们通过计算$N+b^2$,如果它等于$a^2$,那么

我们通过一个例子来说明。

例子:我们想找到如何整除N=25217。那么:

然后我们就知道

如果N很大的话,那么一个随机选择的b不太可能使$N+b^2$成为一个平方。我们需要找到一个更好的方法来选择b。我们不一定非要用N,我们可以用$kN$来代替$N$,如果

然后我们可通过$gcd(N,a+b)$和$gcd(N,a-b)$就可以得到N的两个质数的因子。我们通过一个例子来说明:

例子:我们想分解N=203299。如果我们用$N+b^2$从b=1,2,3就算到100我们也不会找到一个平方值。所以我们接下来尝试计算$3N+b^2$,然后我们可以找到:

然后

然后我们计算gcd就可以得到两个质数了

我们就知道了$203299=263\cdot 773$。

为什么我们不选择$2N+b^2$呢?如果N是一个奇数,那么$2N+b^2$永远也不会是一个平方。我们首先计算模4

但是平方是在模4下同余于0或者1的,那么如果N是一个奇数,那么$2N+b^2$不可能是一个平方。

但是对于$kN+b^2=a^2$,我们用模算术的形式重写一下可以得到

我们用下表描述的算法来阐明我们之前的思想,这个算法是最现代的分解算法。

步骤 操作
1,建立关系 找到一些整数$a_1,a_2,a_3,\dots,a_r$使得$c_i\equiv a_i^2\ (mod \ N)$是小的质数的乘积
2,消元 我们计算 $b^2=c{i_1}c{i2}\dots\ c{i_s}$使其每一个质数都有偶数次的幂,那么它是一个完美平方。
3,计算GCD 令$a=a{i_1}a{i2}\dots\ a{is}$,然后计算d=gcd(N,a-b),因为 $a^2=(a{i1}a{i2}\dots\ a{is})^2\equiv c{i1}c{i2}\dots\ c{i_s}\equiv b^2\ (mod \ N)$ 那么我们很有机会找到d是N的一个因子。

例子:我们用上述算法来分解N=914387。我们首先找到$a^2\ (mod\ N)$是小的质数的乘积的整数。例如,我们想要每一个$a^2\ (mod \ N)$是集合${ 2,3,5,7,11 }$的乘积,忽略怎么找到这种a的问题,我们找到

如果我们把他们都乘起来,我们就得到了一个平方

我们同时计算得到$1869\cdot 1909\cdot 3387\equiv 9835\ (mod \ 914387)$,然后我们就知道

现在我们就分解了$914387=1103\cdot 829$

在写完这个例子后,我们来系统地分析一下这个过程。分解步骤有三步,第三步没什么好说的,用欧几里得算法计算GCD即可。另一方面,建立关系这个步骤过于复杂,我们下一章专门用一章来讲它。我们接下来讨论步骤2

我们假设我们完成了步骤1,然后其中的每一个数字$a_1,a_2,\dots,a_r$都有$c_i\equiv a_i^2\ (mod \ m)$可以被分解成小的质数,假设这个小的质数的集合是${ p_1,p_2,p_3,\dots,p_t }$,那么这也就意味着

用数学语言来说,我们想做的是让

是一个平方。我们得到

我们想要解出$u1,u_2,\dots , u_r$使得对于每一个从1到r的i都有$\sum{i=1}^r e_{ij}u_i$是一个偶数。我们把它写成同余方程组的形式

我们可以发现这是一个有限域$\mathbb{F}_2$中的一个线性同余方程组。所以我们可以用高斯消元法来解出未知数。事实上,在有限域$\mathbb{F}_2$中做线性代数比在实数域$\mathbb{R}$中要简单得多。我们下面用一个例子来说明

例子:我们想分解

我们想找到令$a^2\ mod \ N$是一个50-光滑数,就是说$a^2\ mod \ N$的取值在下面集合中

下面的这个表的上部分列出了从3129(至于为什么从3129开始是因为,$\sqrt{N}=\sqrt{9788111}\approx 3128.6$,如果a的平方不大于N,它就不需要模N,我们也就得不到任何信息)到4700之间有这个性质的20个数$a{1},a{2},\dots,a{20}$。下面的部分列出了解出$(u{1},u{2},\dots,u{20})$方程组。方便书写,我们写成了矩阵的形式。

下一步就是如何解出这个线性方程系统了。我们采用高斯消元法。我们得到它的基础解系

其中每一个向量都是这个线性系统的一个解,我们从下表可以看出,有的值可以解出N的因子,有的只能解出1或者N。

在实际应用上,为了分解一个很大的数字N,我们需要一个包含几千个甚至即百万的质数的集合${p_1,p_2,p_3,\dots,p_t }$。系统中包含了几百万个线性方程,如果在常规的线性系统中解决这个是非常复杂的,但是好在我们是在有限域$\mathbb{F}_2$中。而且从实践上来说,解里面的多数参数都是0,只有一小部分是1。我们有解决这种对应类型的线性系统的有效方法。但是这里不再赘述。

光滑数,筛,整数分解的建立关系

在这节里,我们将描述两个已知的最快解决整数分解问题的有效方法。我们首先来讨论一下光滑数,这是这一大节的基础,然后我们再讨论一下二次筛,这是找到光滑数的快速方法。

光滑数

定义:如果n的所有质数因子小于或等于B的话,n就是B-光滑数。

定义:函数$\psi(X,B)$计算小于或等于X的B-光滑数数量。

举个例子

这是因为在1到25之间一共有15个5-光滑数

为了估计三步分解方法的效率,我们需要知道当X和B很大的时候$\psi (X,B)$是如何变化的。我们下面介绍一个由Canfield,Erdős,Pomerance证明的定理。

定理:给定一个数字$0<\epsilon<1$,并且让X和B同时增长当满足

为了方便书写,我们令

那么小于X的B-光滑数满足

我们这里使用了小o标记,o(1)代表一个当X趋向于无穷的时候趋向于0的函数。更一般的

当X趋向于无穷的时候$f(X)/g(X)$趋向于0。这和大O标记法不同,大O标记法$f(X)=O(g(X))$意味着$f(X)$小于$g(X)$的倍数。

回到原问题,我们现在要解决如何用X来替代B。结果下面这个看上去有点奇怪的函数就是我们所需要的

我们于是得到了$\psi$的一个基本的估计。

结果:对于任意给定的$0<c<1$的c,

证明:注意到如果$B=L(X)^c$,而且如果我们取任意的$\epsilon <\frac{1}{2}$,那么

满足$(ln X)^{\epsilon} < ln B < (ln X)^{1-\epsilon}$,所以我们应用上述定理得到

对$\psi (X,B)=X\cdot u^{-u(1+o(1))}$化简,我们可以很容易推导出

Q.E.D

函数$L(X)=e^{\sqrt{(ln X)(ln ln X)}}$和其他的类似函数在整数分解理论中很重要,因为它和光滑数的分布有很大的关系。那么了解L(X)如何随着X的变化而变化就显得很重要了

我们下面通过一个表来说明L(X)如何随着X而增长。

$X$ $ln L(X)$ $L(X)$
$2^{100}$ $17.141$ $2^{24.73}$
$2^{250}$ $29.888$ $2^{43.12}$
$2^{500}$ $45.020$ $2^{64.95}$
$2^{1000}$ $67.335$ $2^{97.14}$
$2^{2000}$ $100.145$ $2^{144.48}$

假设我们正在找到一个是B-光滑数的$a^{2}\ (mod \ N)$,为了解出第二步的线性方程组,我们需要至少和小于B的质数的个数一样多的B-光滑数。也就是说我们需要至少$\pi (B)$个光滑数。所以我们可以通过对$B=L(N)^c$取一个合适的c值即可。在下一个推论中,我们用质数定理和公式$\psi (X,L(X)^c)$来确定一个给我们一些机会来分解N的最小的c值。

推论:设$L(X)=e^{\sqrt{(ln X)(ln ln X)}}$,令N是一个大整数,并且设$B=L(N)^{1/\sqrt{2}}$

(a)我们在检查大约$L(N)^{\sqrt{2}}$个模N的随机数后可以找到$\pi (B)$个B-光滑数。

(b)我们在检查大约$L(N)^{\sqrt{2}}$个$a^2\ (mod \ N)$形式的数后能找到足够的B-光滑数来分解N。

证明:(a)和(b)是等价的,在假设我们选择的$a^2\ (mod \ N)$足够随机的条件下。我们下面来证明(a).

随机选择一个数是B-光滑数的概率是$\psi (N,B)/N$。为了找到$\pi (B)$个B-光滑数,我们需要检查大约

个随机数字。我们想确定B来最小化这个函数,因为检查数字的光滑性是一个费时间的过程。我们知道

所以我们设$B=L(N)^c$来找到c的最小值。质数定理告诉我们,$\pi (B)\approx B/ln(B)$,所以我们得到

因子$L(N)^{c+1/2c}$决定了最后一个表达式,所以我们选择最小化$c+\frac{1}{2c}$。然后我们可以知道当$c=\frac{1}{\sqrt{2}}$的时候最小,最小值是$\sqrt{2}$。所以我们选择$B\approx L(N)^{1/\sqrt{2}}$,我们需要检查大约$L(N)^{\sqrt{2}}$个数来找到$\pi (B)$个B-光滑数。

之前的推论告诉我们要检查大约$L(N)^{\sqrt{2}}$个随机数,但是实际上我们可以进一步减少这个过程。实际上,比起用随机值来找到光滑数,不如选择比$\sqrt{N}$稍微大一点的数。已经有研究发现采用这种方法只需要检查大约$L(N)$个数就可以找到足够的光滑数,这和$L(N)^{\sqrt{2}}$相比节约了很多时间

但是实际上,我们忽略了检查每个数的B-光滑性的时间,我们用普通的方法,要大概$\pi (B)$次尝试才能确定B-光滑性。把这个附加的时间纳入考虑,我们发现要大约$L(N)^{\sqrt{2}}$次尝试才能找到足够的光滑数来分解N,尽管我们用之前一段所说的取$a\approx \sqrt{N}$。

二次筛,我们下一节将会讨论,用更有效的方法来找到B-光滑数,可以把运行时间降低到$L(N)$。而更高级的方法,数域筛更是能将运行时间降低到$e^{c\sqrt[3]{(ln N)(ln ln N)^2}}$,比$L(N)^{\epsilon}$的任意$\epsilon >0$都要快。

二次筛

这一章我们来解决通过平方差的分解算法的最后一块拼图。我们现在来介绍Pomerance的二次筛法,到目前为止,这是在小于$2^{230}$内最快的N分解算法。如果你想更为详细地了解筛方法以及其历史,可以看Pomerance的优雅的文章”A Tale of Two Sieves”

我们先介绍埃拉托斯特尼筛,是古希腊的一个找质数的方法,埃拉托斯特尼的想法是首先圈出质数2,然后把所有是2的倍数的划掉,再圈出质数3,划掉所有3的倍数,然后最小的没被划掉的数是5,然后圈出5,划掉所有5的倍数,按照这种方式不断进行下去。
The sieve of Eratosthenes
我们注意到有些数字被划去多次,但是比起划去,我们可以用除。就是说,我们首先把每个偶数除2,然后对每个三的倍数除3,对每个5的倍数除5,那么这么对所有小于B的质数这么做的话,那些数字会最终减到1呢?答案是那些是小于B的质数的乘积的数。所以最终我们得到了一列B-光滑数。

很不幸的是,我们错过了一些B-光滑数。那些是小的质数的次方的乘积的数。但是这也很容易解决。就是说在筛完3之后,我们比起处理5,我们先处理4。为了做到这点,我们用2再筛一次(注意到在用2筛的时候4已经被筛过一遍了,所以我们再用2筛),如果我们这么做的话,到最后小于X的所有B-光滑数都可以被除到1。我们可以证明要求进行大约$Xln(ln(B))$次除法运算。这个双对数函数$ln(ln(B))$增长的及其缓慢。

但是我们的目标是不是找到从1到X中的B-光滑数,我们想找到的是一列$a^2\ (mod \ N)$形式的B-光滑数。我们的策略是用下列多项式

我们从一个稍微大于$\sqrt{N}$的a开始,我们设

我们看下面这个数列

我们想通过用小于B的质数筛上面的数列来找到足够多的B-光滑数来分解N。下面的定义对描述这个过程起到帮助。

定义:小于B的质数的集合叫做因数基底

假设p是我们的因数基底里的一个数,那么上述数列中的那一个数可以被p整除呢?我们换一种等价的说法,哪一个介于a和b之间的t满足

如果这个同余没有解,我们消去质数p,或者这个同余有两个解,记作

那么接下来这两列数字

可以被p整除。那么我们

例子:我们在和数N=221上来应用二次筛。平方大于N的最小的数是$a=[\sqrt{221}]+1=15$,我们设

然后从$F(15)=4$一直筛到$F(30)=679$。我们首先用p=2筛,得到

接下来我们再用p=3来筛,但是下面的同余式

无解,所以整个数列中没有可以被3整除的数,我们接下来用4来筛,我们得到下面的同余式

这也就意味着我们可以用2再筛一次,虽然这个箭头上标的4,但是实际上只是用2来筛。

然后我们再用5来筛,那么下面同余式

我们得到两个解$\alpha_5 =1 , \beta_5 = 4$,我们可以得到从$F(16)$,每5第5个数被5整除。

从$F(19)$开始,每5个数被5整除

最后我们再用质数p=7来筛,同余式

有两解$\alpha_7=2,\beta_7=5$,我们可以得到从F(16)开始,每7个数被7整除,从F(19)开始,每7个数被7整除

我们注意到原来的数

所以我们得到

举个例子,我们可以得到

计算得到

得到了221的一个因数。我们已经分解了221,但是为了进一步演示,我们继续筛到B=11.下一个要被筛的质数次方是$3^2$,但是事实上$t^2\equiv 221\ (mod \ 3)$无解也就意味着$t^2\equiv 221\ (mod \ 9)$也是无解的。所以我们继续用p=11来筛。同余式$t^2\equiv 221\equiv 1 \ (mod \ 11$有两解,$\alpha{11}=1,\beta{11}=10$,也就是可以从F(23)和F(21)开始的每11个数

如果p是一个奇数质数,那么同余$t^2\equiv N\ (mod \ p)$有0个或者两个解,更一般的说,同余

有0或者两个解。这就使得筛奇数变得很直接。但是筛偶数的次方略微需要一点技巧。比如,$t^2\equiv N \ (mod \ 8)$,如果$N\equiv 1\ (mod \ 8)$,那么它就有4个不同的解。虽然筛2的次方并不算难,但是它是要被特殊对待的例子。

有许多可以大大加快二次筛速度的方法。一个比较消耗时间的部分是对每p个数除p,因为实际上数字会比较大,所以除p是比较消耗时间的。当然,计算机演算的很快,但是筛的过程需要大约L(N)次除法,所以任何降低这个步骤的方法都会是显著的。一个降低这个运行时间的方法是使用大约的对数,可以用更快的减法运算来代替比较慢的除法运算。

我们来描述一下基本的思想,比起用

我们用下面的数来大约等于

为了从F(t)中筛p,我们减去一个$log(p)$的近似,我们得到

如果我们用对数的精确值,在筛过程的最后,减到0的数对应的F(t)就是B-光滑数。然而,我们使用的仅仅是估计对数值,在最后我们找被减到小的数的F(t),然后再对这些数应用除法来找到真正的B-光滑数。

还有一个用来加速二次筛的方法就是用多项式$F(t)=t^2-N$仅仅当t到达了一定的规模的时候,然后用一个新的多项式。有很多人做了这方面的研究。

二次剩余和二次互反律

令p是一个质数,下面这个简单的数学问题

举个例子,假设Alice问Bob,181是不是模1223下的一个平方,那么Bob只能建立下面这一张表来判断

这是一个很大量的工作,所以Bob计算到96就放弃了,Alice告诉他$437^2\equiv 181\ (mod \ 1223)$,所以181是模1223下的一个平方。我们的目标是找到一个更高效的方式来确定一个数是否是模一个质数下的平方。

定义:令p是一个奇数质数,并且令a是一个不能被p整除的数。我们说a是模p下的二次剩余如果a是模p下的一个平方。就是说存在一个数c使得$c^2\equiv a\ (mod \ p)$。如果a不是模p下的一个平方,也就是说没有这种c的存在,那么a就被叫做模p下的二次非剩余。

推论:令p是一个奇数质数

(a)两个模p的二次剩余的乘积是模p下的一个二次剩余

(b)一个模p下的二次剩余于模p下的二次非剩余的乘积是模p下的二次非剩余

(c)两个模p下的二次非剩余的乘积是模p下的二次剩余

证明:从二次剩余的定义上来直接证明(a)和(b)是很容易的,但是我们用一种不同的方法来同时证明。令g是一个模p下的原根,那么g的多少次幂是模p下的二次剩余?如果m=2k是偶数,那么$g^m=g^{2k}=(g^k)^2$是一个二次剩余。另一方面,令m是奇数,比如m=2k+1,并且假设$g^m$是一个二次剩余,就是$g^m\equiv c^2\ (mod \ p)$。费马小定理告诉我$c^{p-1}\equiv 1\quad (mod \ p)$,然而它还等于

因为

我们也就得到

这于g是一个原根相矛盾,所以证明了g的所有奇数次幂都是二次非剩余。那么现在来证明这个推论就很轻松了。

(a)假设a和b是二次剩余,那么$a=g^{2i},b=g^{2j}$,所以$ab=g^{2(i+j)}$,有一个偶数指数,那么ab是一个二次剩余。

(b)假设a是一个二次剩余,b是一个二次非剩余,那么$a=g^{2i},b=g^{2j+1}$,那么$ab=g^{2(i+j)+1}$有一个奇数指数,所以ab是二次非剩余

(c)假设a和b是二次非剩余,那么$a=g^{2i+1},b=g^{2j+1}$,所以$ab=g^{2(i+j+1)}$有一个偶数指数,那么ab是二次剩余。

Q.E.D

定义:令p是一个奇数质数,我们定义勒让德符号(Legendre symbol)是$(\frac{a}{p})$且满足下面的规则

那么上面的推论可以简单地用下面的乘法规则表示

我们同样可以观察出来

我们下面来介绍著名的二次互反律

定理:令p和q是奇质数

它的证明第一次由Gauss给出,到现在已经有200多种不同的证明方法了。但是我们在这里不做证明。

二次互反这个名字来源于特性(c)。然后我们通过一个例子来解释一下如何应用二次互反律

例子:我们想确定-15750是不是在模37907的一个二次剩余,我们通过Legendre符号来表示

所以我们知道-15750是模37907下的一个平方。注意到它并没有告诉我们其平方根的值,它只告诉我们存在一个解。

你可能注意到在计算步骤中,我们需要分解15750,我们很幸运,这个15750很容易分解。但是假如我想确定p=228530738017是不是在q=9365449244297下的一个平方。但是p和q都是质数,所以我们用二次互反律计算

现在不幸的是224219723617不是一个质数,我们不能直接应用二次互反律,而且它不是一个可以轻松用笔和纸来分解的和数,所以这时候显得二次互反律有点鸡肋。但是幸运的是,我们有另一个版本的二次互反律可以完全消除这个问题。我们先进行定义

定义:令a和b是整数,b是奇数且为正数,假设b可以被分解成质数的积

雅可比(Jacobi)符号$(\frac{a}{b})$被定义为

注意到如果b是一个质数,那么$*(\frac{a}{b})$就是勒让德符号本身,所以可以说雅可比符号是勒让德符号的一个推广。注意到我们定义雅可比符号的b仅仅是奇数且为正数。

例子:一个简单的例子

从定义上来说,我们需要知道如果分解b来计算雅可比符号。但是实际上雅可比符号继承了勒让德符号的很多特性,允许我们很快的计算出$(\frac{a}{b})$而不要做任何分解。我们讨论一下其特性

推论:令$a,a_1,a_2,b_1,b_2$是整数,且$b_1,b_2$是正数且为奇数

证明很简单,在这里不赘述了。

我们现在到了最不可思议的地方了,雅可比符号和勒让德符号的二次互反律是一样的

定理:令a和b是奇数且为正数

证明省略

例子:我们之前想用勒让德符号的二次互反律来计算$(\frac{228530738017}{9365449244297})$,但是我们遇到了整数分解问题,现在我们用雅可比符号的二次互反律来解决。

所以228530738017不是模9365449244297下的一个平方。

假设$(\frac{a}{b})=1$,b是一个正奇数。那么这个事实是否告诉我们a是模b下的平方呢?如果b是质数的话确实是这样的,这是因为根据勒让德符号的定义。但是如果b是和数呢?举个例子假设b=pq,p,q是质数,那么根据定义

那么现在有两种方式使得$(\frac{a}{b})=1$也就是

那么我们注意在情况1中我们有$c_1^2\equiv a \ (mod \ p)\quad c_2^2\equiv a \ (mod \ q)$。我们可以用中国剩余定理找到一个c满足$c\equiv c_1\ (mod \ p)\quad and \quad c\equiv c_2\ (mod \ q)$,也就是$c^2\equiv a\ (mod \ pq)$

我们的结论是,如果b=pq是两个质数的积,那么尽管计算雅可比符号$\frac{a}{pq}$的值比较容易,但是这个值并不能告诉我们a是否是模pq下的一个平方。

可能性加密与Goldwasser-Micali 加密系统

假设Alice想要加密传输给Bob 1比特数据,就是说Alice想要发送0或者1中的一个值。我们第一眼看上去会觉得这个从本身来说就不安全。Eve需要做的就是加密两个可能的明文m=0和m=1,然后她比较她的加密与Alice的密文。更一般的说,在任何可能的明文很小的条件下,Eve可以用Bob的公钥来加密可能的明文直到她找到与Alice的密文匹配的一个。

可能性加密被Goldwasser和Micali发明。这种加密方法可以解决这个问题。想法是Alice选择明文m和随机数据r,然后她用Bob的密钥加密这对(m,r)。理想上来说,r可以取任何可能的值。更精确地,对于任意给定的$m_1,m_2$以及变化的r,下面这两个值的分布

应该不能被分辨出来。注意到Bob不需要完全恢复整个(m,r)对,他只需要恢复m即可。

这个抽象的想法很清晰,现在我们来讲一下Goldwasser和Micali的具体做法。他们的想法是基于下面问题的

我们注意到Bob知道如何分解N,他也就可以轻松解决这个问题。因为

但是Eve她并不知道p和q,她能计算出$(\frac{a}{N})$,但是我们之前讨论过,这并不能决定a是否是模N下的一个平方。我们用一个表来描述Goldwasser-Micali加密系统

Bob Alice
密钥创建
选择秘密的质数p和q,选择a使得$(\frac{a}{p})=(\frac{a}{q})=-1$发布N=pq和a
加密
选择明文$m\in{ 0,1 }$,选择随机数大于1小于N的随机数r。使用Bob的公钥(N,a)。当m=0的时候$c=r^2\ (mod \ N)$;当m=1的时候$c=ar^2\ (mod \ N)$。并将密文c发送给Bob
解密
计算$(\frac{c}{p})$。如果$(\frac{c}{p})=1$那么m=0,如果$(\frac{c}{p})=-1$那么m=1。

最后一步是因为

如果Eve计算Jacobi符号$(\frac{c}{N})$的话她会得到什么?如果m=0,那么

另一方面,如果m=1,那么

也等于1,那么计算Jacobi符号并不能给Eve提供任何信息,Eve需要做的是找到如何将N分解成两个质数。

例子:Bob创建了一个Goldwasser-Micali加密系统,他选择

然后Bob发布他的公钥(N,a)。Alice想要发送给Bob明文m=0。她首先在1到13048158之间选择一个随机数r=1642087。她计算

并且发送密文c=8513742给Bob。Bob通过计算$(\frac{8513742}{2309})=1$知道明文是m=0。

下一步Alice想发送给Bob明文m=1,那么她选择随机数r=11200984,并且计算

Bob通过计算$(\frac{2401627}{2309})=-1$得到明文m=1。

实际上,Goldwasser-Micali加密系统并不实用,因为它每次只能加密1bit的信息。而且为了确保加密系统的安全性,必须使得Eve不能分解出N=pq,所以在安全性上来说它和RSA是等价的。N至少需要1000-bit的数。也就是说,从效率上来说,如果Alice想发送k位数的明文给Bob,那么她的密文就有1000k-bit那么长,也就是说她的密文有明文的1000倍长,在效率上远远不如RSA。比起使用Goldwasser-Micali加密系统,我们更一般地使用RSA。

还有其他的可能性加密系统,我们之前讨论的El-Gamal加密系统就是一种,以及之后的NTRU加密系统也是一种。

讲完了。

扫这里给我🍭次

Author: Azusa
Link: http://azukatze.moe/2019/08/09/cryptography/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.