密码学之数论基础

2019-04-13 16:47发布生成海报

站内文章 / 模拟电子

13779 0

素数

整数p>1是素数当且仅当它只有因子+(-)1和+(-)p。
任意整数a>1都可以唯一地因子分解为：

其中p1,p2,…,pt均是素数，p1

上式右边是所有素数之积。对某一整数a，其大多数指数ap为0.两数相乘即是指数对应相加。设

，定义k=ab。我们知道整数k可以表示为素数方幂的乘积：

。可以推出对于所有的p属于P，有kp=ap+bp成立。

费马定理

费马定理和欧拉定理在公钥密码学中占有重要地位。
费马定理可如下描述：若p是素数，a是正整数且不能被p整除，则：

费马定理的另一种有用的表示形式是：若p是素数且a是任意正整数，则：

注意定理的第一种形式要求a与p互素，而后一种没有这个要求。

欧拉函数

欧拉函数Φ(n)是指小于n且与n互素的正整数的个数。习惯上，Φ(1)=1。
显然，对素数p:Φ(p)=p-1。
假设有两个素数p和q，p不等于q，那么对n=pq，Φ(n)=Φ(pq)=Φ(p)Φ(q)=(p-1)(q-1)。
欧拉定理说明，对任意互素的a和n，有：

注意这里Φ(n)是指小于n且与n互素的正整数的个数。
类似费马定理，欧拉定理的另一种表述也很有用：

同样和费马定理类似，欧拉定理的第一种形式要求a与n互素，而后一种没有这个要求。

中国剩余定理

剩余类

定义比n小的非负整数集合为Zn:
Zn={0,1,….,(n-1)}
这个集合被成为剩余类集，或模n的剩余类。更准确地说，Zn中每一个整数都代表一个剩余类，我们可以将模n的剩余类表示为[0],[1],[2],…,[n-1],其中
[r]={a:a是一个整数，a与r模n同余}
在剩余类的所有整数中，我们通常用最小非负整数来代表这个剩余类。寻找与k是模n同余的最小非负整数的过程，称为模n的k约化。
比如：当k=8，n=4时，寻找8 mod4同余的最小非负整数为0，当k=7，n=4时，寻找7 mod4 同余的最小非负整数为3.

笛卡尔积

笛卡尔积又叫笛卡尔乘积，是一个叫笛卡尔的人提出来的。简单的说就是两个集合相乘的结果。
举个例子：
集合A={a1,a2,a3}
集合B={b1,b2}
他们的笛卡尔积是
A*B={(a1,b1),(a1,b2),(a2,b1),(a2,b2),(a3,b1),(a3,b2)}
即任意两个元素结合在一起

CRT

中国剩余定理(CRT)是数论中最有用的定理之一。CRT说明某一范围内的整数可通过它的一组剩余类来重构，这组剩余类数是对该整数用一组两两互素的整数取模得到的。
CRT可有几种不同的表示形式，这里我们给出其中一种最有用的表示形式：

其中mi是两两互素的，即对1<=i,j<=k, i!=j 有gcd(mi,mj)=1。我们可将ZM中的任一整数对应一个k元组，该k元组的元素均在Zmi中，这种对应关系即为：

其中A属于ZM，对于1<=i<=k, ai属于Zmi，且ai=A mod mi。
CRT 说明下列两个断言成立：
(1)上面的映射是ZM到笛卡尔积Zm1Zm2….*Zmk的一一对应(称为双射)，也就是说，对任何A，0<=A<=M,有唯一的k元组(a1,a2,…,ak)与之对应，其中0<=ai
(2)ZM中元素上的运算可等价于对应的k元组上的运算，即在笛卡尔积的每一个分量上独立地执行运算。
中国剩余定理的用途之一是，它给出了一种方法，使得模M的大数运算转化到更小的数上来进行运算，当M为150位或150位以上时，这种方法非常有效。

离散对数

离散对数是包括Diffie-Hellman密钥交换和数字签名算法(DSA)在内的许多公钥算法的基础。

模n的整数幂

欧拉定理告诉我们，对任何互素的a和n，有

其中a的指数是欧拉函数指小于n且与n互素的正整数的个数。下面我们考虑欧拉定理更一般的表示形式：

若a与n互素，则至少有一个整数m满足上式，即m=Φ(n),我们称使上式成立的最小正幂为下列之一：
a(模n)的阶
a所属的模n的指数
a所产生的周期长

本原根

更一般地，我们说Φ(n)是一个数所属的模n的可能的最高指数。如果一个数的阶为Φ(n)，则称之为n的本原根。本原根的重要之处在于，若a是n的本原根，则其幂
a,a2,….,aΦ(n)
是(模n)各不相同的，且均与n互素。特别地，对素数p，若a是p的本原根，则
a,a2,….,ap-1
是(模p)各不相同的。
并不是所有的整数都有本原根。事实上，只有形为2，4，pa和2pa的整数才有本原根，这里p是任何奇素数，a是正整数。

模算术对数

对于普通正实数，对数函数是指数函数的逆函数。对模算术也有类似的函数。
对数函数：给定一个数，它的对数是满足下列条件的幂：以某个正数(除1外)为底的该次幂恰好等于给定的这个整数，即对底x和数y：

对数具有下列性质：

对某素数p(对非素数亦可)的本原根a，a的1到(p-1)的各次幂恰可产生1到(p-1)的每个整数一次且仅一次。而对任何整数b，根据模算术的定义，b满足：

因此，对任何整数b和素数p的本原根a，有唯一的幂i使得

该指数i称为以a为底(模p)b的离散对数，记为

.注意仅当a是p的本原根时，才存在有唯一的以a为底模p的离散对数。上述内容大部分摘录于《密码编码学与网络安全》，记录在此方便随时回顾。