Dan Boneh密码学笔记10

10.Intro. Number Theory

1.Notation

2.Fermat and Euler

3.Modular e’th roots

4.Arithmetic algorithms

5.Intractable problems

更新本节用了三天。最近开学事情有点多，学习上有点不知道先学哪个。要学的东西太多了，区块链安全的15篇论文、以太坊的课程、密码学课程（进度10/13）、UC安全框架、现在学本节课的过程中遇到了些困难，又开始学信息安全数学基础（近世代数、数论）......越学越多，倒是也挺好，轮换着学，换脑子.....就是头皮有点冷。

在几经坎坷后，决定先把密码学的课刷完。本节课的数论基础，仅仅是为后面这几节课的铺垫。刚好够用。信息安全数学基础的东西不是很多，但是也需要时间。本科学过信安数基，对刷本节课非常有帮助。可能是斯德哥尔摩综合征吧，被数学虐的这么惨，现在竟然觉得有意思了......原来数学这么有用。

1.Notation

N 正整数

p 正质数

双对角线Z_N 表示集合{0，1，2…….,N-1} 以及模N的加法和乘法，Z_N表示一个环

最大公约数

扩展的欧几里得算法

x和y最大公约数是1，则x和y互质

Z_N 中哪些元素有逆？当且仅当X和N互质时

计算逆的方法，找到a和b，a就是X的逆

Z_N* 是Z_N中所有可逆的元素

0与p不互质

Z_p*就是Z_p除去0，意味着Z_p中的所有元素都是可逆的，0除外

Z_p*的大小就是p-1

解决线性同余方程

欧几里得算法求逆，时间复杂度是,是一个平方算法，quadratic algorithm，事实上这是已知的最好的算法。

2.Fermat and Euler

费马和欧拉的贡献

100年后欧拉给出了这个费马小定理的证明

另一个计算X模质数的逆的算法

不足，这个算法只能工作在质数模上，而欧几里得算法可以工作在合数模上

实际上这个算法效率更低

简单的费马小定理的应用

假质数FP（carmichael数，分布密度指数级衰减），有很少的数，不是质数，是合数的，却能通过这个检测的。

随机选择落到FP集合里的概率是很小的，可以忽略。

这种费马检测，是简单的但是实际中并不用这种方法来生成质数。

质数定理，迭代次数的期望是1024*ln2，约为710。

(Z_p)*的结构，是一个循环群

到g^(p-2)，因为到p^(p-1)=1 Zp回到了1

这样的元素g叫做生成元generator，比如3对于p=7

不是每个元素都是生成元比如2对于p=7

g的全体幂组成的集合，叫做g的生成群，用<g>表示

Ord(g)表示g的阶=集合的个数|<g>|

拉格朗日定理的一个特例，有限子群的阶必然整除有限群的阶

费马小定理是拉格朗日定理的直接推论

推广到合数Z_N^*的结构。

欧拉定理，一个费马小定理的直接推广

给定一个整数N，欧拉定义了函数Φ(phi)， φ(M)表示Z_N^*的大小，也叫做欧拉的φ函数

对质数，φ(p)=p-1

之后再RSA系统中要用：

如果N=p·q,pq是两个质数，φ(N)=N-p-q+1=(p-1)(q-1)

N是Z_N的大小，移除所有与m不是互质的元素，

一个元素如何才能不与m互质？它要不被p整除，要不就被q整除。

在0到m-1之间一定有q个元素能被p整除，一定有p个元素能被q整除。

减去p，来减去那些被q整除的数；减去q，来减去那些被p整除的数

我们见了0两次，因为0被q和p同时整除，所以再+1

欧拉还证明了这个定理，这是费马小定理的一个推广，特别地，费马小定理只适用于质数的情况。

欧拉定理还适用于合数

欧拉定理也是拉格朗日定理的特例 欧拉定理是RSA密码系统的基础

3.Modular e’th roots

上节讨论了如何解模线性方程，这节讨论如何解模二次方程

如何计算模e次方根

通过使用求逆的算法，知道如何解线性方程了

怎么解高次多项式方程呢？

什么时候这些e次方根存在？

当我们想计算某个数的e次方根时，正好有e与p-1互质，这时c^(1/e)始终存在

proof，首先因为e与p-1互质，我们知道e模p-1有逆，记为d

当e与p-1不互质时

当我们工作在奇质数模下，平方函数实际上是2-to-1函数，它把x和-x映射到了同一个值x^2。

本质上，这个平方函数也是一个群同态

例如4模11是一个二次剩余，9、5、3、1也是二次剩余

如果p是奇质数，Z_p中的二次剩余一共有(p-1)/2+1个

0总是二次剩余的。

约有一半的元素有平方根，另一半则没有

在容易的情况下，Z_p的每一个元素都有一个e次方根，当e与p-1不互质的时候就不是这样了。特别是p=2时，只有一半的元素有平方根。我们能否对Z_p^*里的一个元素x判断出x是否有平方根呢？

Q.R.二次剩余

=1 的就是二次剩余 ，13459有平方根，p=11

勒让德符号，只有1和-1

只证明了二次剩余存在，没有展示如何计算我们想要的平方根

如何计算质数模的平方根

P=3(mod 4)必然有p+1=0 mod 4，意味着p+1可以被4整除

当p=1(mod 4)时，有点困难

求二次方程的解

当Z_p中有平方根的时候，这个公式可解。

如何计算合数模而不是质数模。

计算合数模的e次方根困难得多，需要因子分解N。

4.Arithmetic algorithms

质数模与合数模的加法、乘法和指数算法

如何计算大整数的模

如何在计算机里表示大整数

加减乘除时间复杂度

karatsuba苏联的科学家发明了这种更好的乘法，常用

最好的乘法是n·logn，不实用，特别大数据才有效。

带余数的除法

求幂的问题

有限循环群G，g是生成元

快速计算幂乘的方法，重复平方算法。

举例x=53，把53写成二进制。

5次平方，4次乘法。所以我们只需要做9步乘法就可以得到g的53次方

重复平方算法

y是一个总是做平方运算的寄存器，z是一个累加器

以非常快的速度计算极高次幂运算

循环次数log_2 x 取决于x的位数

5.Intractable problems

质数模、合数模的难题

这些难题是我们下周构建密码系统的基础

考虑一个指数函数，x映射到g^x，正向计算简单，但是逆向计算是困难的。

离散对数discrete logarithm Dlog问题

g^x的离散对数是x

大数，计算离散对数的困难的

不在局限于Z_p*，更抽象地看一个普通群G

有限循环群G，g是生成元

群G上的离散对数问题是困难的

没有有效的算法能够以不可忽略的概率计算出离散对数

离散的椭圆曲线群

椭圆曲线群上的问题要比Z_p*群上的困难的多

计算离散对数有一个亚指数算法，一个n位的质数，这个算法的运行时间的指数大约是n的立方根。

对于椭圆曲线群，运行时间的2^(n/2), 这是一个合适的指数时间算法。

椭圆曲线大小（质数模的大小）是对称密钥大小两倍的原因是，由于指数里的这个因子2 ，我们必须将椭圆曲线群的大小扩大一倍以获得2^n的运行时间

离散对数困难性的直接应用

这个函数H 哈希函数是防碰撞的，找到一个H的碰撞与计算G上的离散对数一样困难

碰撞为两对不同的信息对，(x0,y0),(x1,y1),它们正好在函数H上发生碰撞

得证，g为底h的离散对数。

y1-y0的模q的逆，然后把结果与x0-x1相乘

所以，为什么我们希望q是质数，因为我们需要确保y1-y0始终可逆

如果y1-y0=0，我们无法得到离散对数，与前提矛盾，不存在的。

高斯的毕业论文，因子分解和素性检测

把合数因子分解仍然是个难题，在计算机中

目前最好的算法叫做数域筛法NFS,但是运行时间的指数级的，指数是立方根次的，所以这就是为什么合数要非常大才难分解。