当前位置: 代码迷 >> 综合 >> 密码学---公钥密码---数学知识
  详细解决方案

密码学---公钥密码---数学知识

热度:23   发布时间:2024-01-21 04:51:37.0

密码学中常用的数学知识

  • 1.群、环、域
    • 半群
      • 群的种类
      • 群的阶数x
      • 实例
      • 实例
      • 域的分类
      • 多项式
      • 实例
  • 2.素数、互素数
    • 因子及相关性质
    • 素数及相关性质
      • 整数的分解实例
    • 互素数、gcd(a,b)、lcm(a,b)
  • 3.模运算
    • 模n同余
    • 模运算性质
    • 定理
    • 实例
  • 4.模指数运算
  • 5.费尔马定理、欧拉定理、卡米歇尔定理
    • 费尔马定理
    • 欧拉函数及求解方法
    • 欧拉定理
      • 本原根
    • 卡米歇尔函数即求解方法
    • 卡米歇尔定理
  • 6.素性检验
    • 爱拉托斯散筛法
    • Miller-Rabin概率检测法
    • AKS算法
  • 7.欧几里得算法
    • 求最大公因子
    • 求乘法逆元
  • 8.中国剩余定理
    • 重构数据
    • 大数计算分解为小数实现
  • 9.离散对数
    • 指标
    • 离散对数
  • 10.平方剩余
    • 平方剩余定义
    • 平方剩余的实例
    • Legendre符号
    • Jacobi符号
    • 平方剩余的实例
  • 11.循环群
  • 12.双线性映射

1.群、环、域

群、环、域都是代数系统(代数结构)。代数系统包括数学对象的集合以及在集合上采用的关系或运算(可以是单元运算、也可以是多元运算)
常用集合:

Q:有理数集合
I:整数集合
Z:正整数集合
R:实数集合
C:复数集合
Zn:Zn={0,1,2,3,…,n-1},称Zn为模n的同余类集合
Mn:I上的n*n方阵
R(x):R(x)是所有实系数的多项式集合

详细介绍如下:

半群

设<G,×>是一个代数系统,×满足以下性质:

  1. 封闭性。设×是集合S上的多元运算,对?a,b∈S,有a×b∈S,则称S对运算×是封闭的。若×是一元运算,对?a∈S,有×a∈S,则称S对运算×是封闭的
  2. 结合律。若对?a,b,c∈S,有(a×b)×c=a×(b×c),则称×满足结合律
    则称<G,×>是半群

设<G,×>是一个代数系统,×满足以下性质:

  1. 封闭性
  2. 结合律
  3. 单位元。存在元素e,对?a∈G,有a×e=e×a=a;e称为<G,×>的单位元
  4. 逆元。对?a∈G,存在元素a-1,使得a×a-1=a-1×a=e;称a-1为a的逆元
    则称<G,×>是群。其中若运算×已经明确了,则可以直接将<G,×>简记为G

群的种类

1.有限群和无限群:若集合G为有限集合,则称群<G,×>是有限群,否则是无限群。
2.Abel群/交换群:若群<G,×>中的运算×满足交换律,即对?a,b∈S,有a×b=b×a,则称<G,×>为交换群或者是Abel群
3.乘法群:若群群<G,×>中的运算×是乘法,则称之为乘法群
4.加法群:若群群<G,×>中的运算×是加法,则称之为加法群,此时逆元a-1为-a
5.循环群:设有一个整数集合I和一个群<G,×>,若存在一个元素g∈G,对于每一个元素a∈G,都有一个相应的i∈I,使得a=gi,则称<G,×>是循环群,g称为循环群的生成元。记G=<gi|i∈I>。称满足方程am=e的最小正整数m为a的阶,记为|a|

群的阶数x

有限群中,G中的元素个数称为群的阶数

实例

<I,+>是Abel群,<Q,·>是Abel群

若代数系统<R,+,·>的二元运算+和·满足:

  1. <R,+>是Abel群
  2. <R,·>是半群
  3. 乘法·在加法+上可分配,即对?a,b,c∈R,有a·(b+c)=a·b+a·c和(b+c)·a=b·a+c·a
    则称<R,+,·>是环

实例

<I,+,·>是环、<Zn,+nn>,<Mn,+,·>,<R(x),+,·>是环

若代数系统<F,+,·>的二元运算+和·满足:

  1. <F,+>是Abel群
  2. <F-{0},·>是Abel群,其中0是+的单位元
  3. 乘法·在加法+上可分配,即对?a,b,c∈R,有a·(b+c)=a·b+a·c和(b+c)·a=b·a+c·a
    则称<F,+,·>是域

域的分类

1.有限域和无限域:有限域是指元素个数有限的域,其中元素的个数称为域的阶;无限域则是指元素个数无限的域
2.Galois域:阶为素数的幂q的域称为Galois域,记为GF(q)或Fq。其中q=pr,p是素数,r是自然数

多项式

不可约多项式:
F(x)是任意域F上的多项式集合(多项式的系数取自F),若F(x)仅能被非0常数或者自身的常数倍除尽,但不能被其他多项式除尽的多项式

若多项式的系数取自以素数p为模的域F时,这样的多项式集合记为Fp[x]。若m(x)是Fp[x]上的n次不可约多项式,Fp[x]上多项式加法和乘法改为以m(x)为模的加法和乘法,此时的多项式集合记为Fp[x]/m(x),集合中元素个数为pn,则Fp[x]/m(x)是一个有限域GF(pn)

实例

<Q,+,·>,<R,+,·>,<C,+,·>都是域
任意域F上的多项式(即系数取自F)集合F(x)在多项式加法和乘法运算下构成环。

2.素数、互素数

因子及相关性质

设a,b是两个整数,如果存在另一个整数m,使得a=mb,则称b整除a,记为b|a,并且称b是a的因子;具有下列相关性质:

1.若a|1,则a=+1或-1
2.若a|b且b|a,则a=+b或a=-b
3.对任一b(b≠0),有b|0
4.若b|g,b|h,对任意的正整数m,n,都有b|(mg+nh)

素数及相关性质

若p只有+1,-1和p,-p这四个因子,则p为素数,否则p为合数;

整数分解的唯一性(任何一个整数都能分解为多个素数的乘积):
任意一个整数a(a>1)都能唯一分解成以下形式:
在这里插入图片描述
其中p1<p2<…<pn是素数,ai≥0。两数相乘可以等价于对应的指数相加。

整数的分解实例

1.整数11011可被分解为如下:
11011=7×112×13,也可由指数表示为{a7=1,a11=2,a13=1}
2.整数24和45相乘可分成如下:
24=23×3,可用指数表示成{a2=3,a3=1}
45=32×5,可用指数表示成{a3=2,a5=1}
因此24×35={a2=3,a3=3,a5=1}=23×33×5

互素数、gcd(a,b)、lcm(a,b)

互素数是指最大公因子为1的一对数据。可用gcd(a,b)=1表示。

gcd(a,b)表示a和b的最大公因子。由于公因子要求为正数,因此gcd(a,b)=gcd(-a,b)=gcd(a,-b)=gcd(-a,-b),因此一般gcd(a,b)=gcd(|a|,|b|)。

特例:由于0能被任何一个非0的数b整除,即b|0,因此有gcd(a,0)=a

lcm(a,b)表示a和b的最小公倍数

基于整数分解的唯一性可以用来求解gcd和lcm。如a=300,b=18,求gcd(a,b)和lcm(a,b).

解:有300=22×3×52,指数形式为{a2=2,a3=1,a5=2},
18=2×32,指数形式为{a2=1,a3=2}
则c=gcd(a,b)={a2=1,a3=1}=2×3=6
d=lcm(a,b)={a2=2,a3=2,a5=2}=22×32×52=600

3.模运算

称求余运算a mod n将整数a映射到集合{0,1,…,n-1}上的算术运算为模运算。求余运算符号为mod,可表示为a=n×b+r。其中r∈[0,n),b=向下取整(a/n),则r=(a mod n)

模n同余

若(a mod n)=(b mod n),则称整数a,b模n同余,记为a≡b mod n。将与a模n同余的数的全体称为a的同余类,记为[a],a为这个同余类的表示元素。
注意:若a≡0 (mod n),则n|a

同余运算的性质

1.n|(a-b)与a≡b mod n等价
2.a≡b mod n,则b≡a mod n
3.a≡b mod n,b≡c mod n,则a≡c mod n
4.若a≡b mod n,d|n,则a≡b mod d
5.若a≡b mod ni(i=1,2,…,k),d=lcm(n1,n2,…,nk,),则a≡b mod d

一般定义Zn为小于n的所有非负整数集合,即Zn={0,1,…,n-1},称Zn为模n的同余类集合,其上的模运算有以下性质:

1.交换律:(w+x)mod n=(x+w)mod n和(w×x)mod n=(x×w)mod n
2.结合律:[(w+x)+y]mod n=[w+(x+y)]mod n和[(w×x)×y]mod n=[w×(x×y)]mod n
3.分配律:[w×(x+y)]mod n=[(w×x)+(w×y)]mod n
4.单位元:(0+w)mod n=w mod n和(1×w)mod n=w mod n
5.加法逆元:对w∈Zn,存在z∈Zn,使得w+z≡0 mod n,记z=-w
6.加法的可约律:若(a+b)≡(a+c)mod n,则b≡c mod n

模运算性质

  1. [(a mod n)+(b mod n)]mod n=(a+b) mod n
  2. [(a mod n)-(b mod n)]mod n=(a-b) mod n
  3. [(a mod n)×(b mod n)]mod n=(a×b) mod n

定理

Zn*中的每一个元素都有乘法逆元

实例

以下是Z8上的模加法和模乘法,结果如下图所示:
在这里插入图片描述

4.模指数运算

模指数运算是用来计算给定正整数m,n,am mod n表达式的值。
当表达式am mod n=1 mod n时,满足等式的最小正整数m称为模n下a的阶,记为ordn(a)

5.费尔马定理、欧拉定理、卡米歇尔定理

费尔马定理

费尔马定理内容:若p是素数,a是正整数且gcd(a,p)=1,则ap-1≡1 mod p。
也可写成如下形式:设p是素数,a是任一正整数,则ap≡a mod p。

欧拉函数及求解方法

设n是一正整数,小于n且与n互素的正整数的个数称为n的欧拉函数,记为φ(n)。如φ(6)=2(正整数为1,5),φ(8)=4(正整数为1,3,5,7)

φ(n)的求法如下:

1.任n是素数,则φ(n)=n-1;
2.若n是两个素数p×q的乘积,则φ(n)=φ§×φ(q)=(p-1)×(q-1)
3.若n有标准的分解式(整数分解的唯一性中整数的表达方式)如下:
在这里插入图片描述
如φ(21)=φ(3)×φ(7)=2×6=12,φ(72)=φ(23×32)=72×(1-1/2)×(1-1/3)=24

欧拉定理

欧拉定理如下:若a和n互素,则aφ(n)≡1 mod n
有如下推论:ordn(a)一定是φ(n)的因子,即ordn(a)|φ(n)。

本原根

若ordn(a)=φ(n),则称a为n的本原根。
注意:
1.若a是素数p的本原根,则a,a2,…,an-1mod p的值都不相同
2.本原根不唯一
3.不是所有的整数都有本原根,只有以下形式的整数才有本原根:2,4,pa,2pa(p为奇数)

卡米歇尔函数即求解方法

对满足gcd(a,n)=1的所有a,使得am≡1 mod n同时成立的最小正整数m,称为n的卡米歇尔函数λ(n)。即在ordn(a)的基础上加了互素的条件

求解方法:

1.若a|b,则λ(a)|λ(b)
2.对任意互素的正整数a,b,有λ(ab)=lcm(λ(a),λ(b))
3.在这里插入图片描述

具体解法如以下例子:
在这里插入图片描述

卡米歇尔定理

定理内容如下:若a和n互素,则aλ(n)≡1 mod n

6.素性检验

素性检验的目的是为了检验给定的数据是否是素数。有爱拉托斯散(Eratosthenes)筛法、Miller-Rabin概率检测法、AKS算法等,下面将详细介绍以上三种算法的步骤。

爱拉托斯散筛法

我们都知道,如果对所有满足p≤ √n的素数p,都有p不整除n,则n一定是素数。爱拉托斯散筛法就是基于该定理产生的,但是在n很大时,不可行
基本过程(假设求不超过n的所有素数):
1.先将2到n之间的所有整数A都列出
2.找到小于等于√n的所有整数
3.依次在A中删除小于等于√n的整数的倍数
4.剩下的整数即为所求的所有素数

Miller-Rabin概率检测法

前提:若p为大于2的素数,则方程x2≡1 (mod p)的解只有x ≡ 1和x ≡ -1,且其逆否命题也成立:如果方程x2 ≡ 1 mod p有一个解x0?{-1,1},那么p不为素数。
该算法的流程如下所示:

AKS算法

AKS算法是一个确定性的素数判别算法,算法基于以下引理:
设n≥2的一个自然数,a∈I,gcd(a,n)=1,则n是素数的充要条件是:(X+a)n≡Xn+a(mod n)
为了减少系数的计算,可在等式的两边同时对一个形如Xr-1的多项式取模,即将判断的等式进行变形,只需要判断如下等式是否成立即可:
(X+a)n≡Xn+a(mod Xr-1,n),表示在环Zn[x]/(Xr-1)上,(X+a)n=Xn+a
算法具体流程如下:

7.欧几里得算法

欧几里得算法的本质是反复使用辗转相除法,从而确定两个正整数的最大公因子的简化过程。推广的欧几里得算法不仅可求两个正整数的最大公因子,并且当两个正整数互素时,还可以求出其中一个数关于另一个数的乘法逆元

求最大公因子

欧几里得算法基于以下的结论:
设a,b是任意两个正整数,将它们的最大公因子gcd(a,b)简记为(a,b),有以下重要结论(a,b)=(b,a mod b)

欧几里得算法的过程如下:
在这里插入图片描述
利用欧几里得算法求最大公因子的实例:
在这里插入图片描述

求乘法逆元

具体流程如下:
在这里插入图片描述

8.中国剩余定理

中国剩余定理的两个用途:
一是如果已知某个数关于一些两两互素的数的同余类集,就可重构这个数;二是可将大数用小数表示,大数的运算通过小数实现。

中国剩余定理的内容如下:
在这里插入图片描述

重构数据

重构数据是指已知该数据的某些信息,通过计算得到该数据的值。具体操作用一下示例:
假设已知数据x满足如下方程组:
在这里插入图片描述
求x的值。
求解步骤:
1.将3个余数写成和式的形式:2+3+2
2.为了满足第一个方程,模3后,后面2项消失,因此后两项需要乘3,依次类推,第1,3项乘5,第1,2项乘7,得到2·5·7+3·3·7+2·3·5
3.进行整理得到a=2·5·7·(5·7)-1mod 3+3·3·7·(3·7)-1 mod 5+2·3·5·(3·5)-1 mod 7=2·5·7·2+3·3·7·1+2·3·5·1=233
4.计算M=3·5·7=105
5.计算a mod M=233 mod 105=23,因此x=23

大数计算分解为小数实现

前提:假设只能处理5以内的数,则15可以分解成35以内的数表示,即用一个35的矩阵表示,矩阵的行代表该数据mod 3的值,列代表该数据mod 5的值,因此1-15之间的数据还可表示如下所示:
在这里插入图片描述
如11模15可表示为(2,1)

大数计算分解为小数可以简化计算过程,使计算更加容易。
具体过程示例如下:
需要计算x=973 mod 1813+678 mod 1813的值。
步骤:
1.将973 mod 1813由模数分别为37和49的两个数表示,可取a1=973 mod 37=11,a2=973 mod 49=42,因此973模1813可用(11,42)表示,同理678模1813可用(12,41)表示
2.直接模加法运算得到x=(11,42)+(12,41)=(23,34)表示

9.离散对数

指标

指标的符号为inda,p(b),含义是模p下以a为底b的指标
关于指标的定义如下:

设p是一个素数,a是p的本原根,则a,a2,a3,…,ap-1产生出1到p-1之间的所有值,且每一个值只出现一次。因此对任意b∈{1,…,p-1},都存在唯一的i(1≤i≤p-1),使得b≡ai mod p。称i为模p下以a为底b的指标,记为i=inda,p(b)

关于指标的定理如下:

若az≡aq mod p,其中p为素数,a是p的本原根,则有z≡q mod φ§

关于指标的实例如下:

在这里插入图片描述

关于指标性质的如下:

在这里插入图片描述

离散对数

离散对数的符号表示为i=loga(b)(mod p),含义是模p下以a为底b的离散对数。
离散对数的定义如下:
设p是素数,a是p的本原根,则a1,a2,a3,…,ap-1在mod p下产生1到p-1的所有值,所以对任意b∈{1,…,p-1},有唯一的i∈{1,…,p-1},使得b≡ai mod p。称i为模p下以a为底b的离散对数,记为i=loga(b)(mod p)。

当a,p,i已知时,用快速指数算法能比较容易地求出b,但是如果已知a、b和p,求i就会很困难,目前已知的求离散对数算法的时间复杂度为O(exp(lnp)1/3ln(lnp))2/3),因此当p很大时,该算法不可行

10.平方剩余

平方剩余定义

设n是正整数,a是整数,满足gcd(a,n)=1,若方程x2≡a (mod n)有解,则称a是模n的二次剩余,否则称为二次非剩余

平方剩余的实例

在这里插入图片描述
则1,2,4是模7的二次剩余,且每个二次剩余都有两个平方根。

**注意:
1.若n是素数,则模n的二次剩余的个数为(n-1)/2个,非二次剩余个数为(n-1)/2个
2.若a是模n的一个二次剩余,那么x2≡a (mod n)有两个平方根,其中一个解x1的范围在区间(0,(n-1)/2],另一个解x2的范围在区间((n-1)/2,n-1]
3.两个平方根中的一个解也是模n的二次剩余
**

Legendre符号

Legendre符号表示为(a/p).可用来判断平方剩余是否解。

设p是素数,a是一个整数,则Legendre符号(a/p)的定义如下:
在这里插入图片描述
除此之外,计算(a/p)有一个简单的公式,(a/p)=a(p-1)/2 mod p

Legendre符号的性质如下:
设p是奇素数,a和b都不能被p除尽,则:

1.若a≡b mod p,则(a/p)=(b/p)
2.(ab/p)=(a/p)(b/p)
3.(a2/p)=1
4.(a+p/p)=(a/p)

定理如下:
1.当p≡q≡ 3 mod 4时,求解方程x2≡a (mod n) 与分解n是等价的。
2.当p≡q≡ 3 mod 4时,a mod n的两个不同的平方根u和w的Jacobi符号有如下关系:
在这里插入图片描述

Jacobi符号

Jacobi符号是Legendre符号的推广,设n是一个整数,且n用分解形式表示,因此定义Jacobi符号为:
在这里插入图片描述
当n为素数时,Jacobi符号就是Legendre符号

Jacobi符号的性质:
设n是正合数,a和b是与n互素的整数,则:

1.若a≡b mod n,则(a/n)=(b/n)
2.(ab/n)=(a/n)(b/n)
3.(ab2/n)=(a/n)
4.(a+n/n)=(a/n)

特殊的Jacobi符号有:
在这里插入图片描述

Jacobi符号的互反律:
设m,n均为大于2的奇数,则:
在这里插入图片描述
若m≡n≡ 3 mod 4,则(m/n)=-(n/m);否则(m/n)=(n/m)

Jacobi符号与Legendre符号的区别在于Jacobi符号不表示方程x2≡a (mod n)是否有解

平方剩余的实例

在这里插入图片描述

11.循环群

这里主要介绍有关循环群的一些定理
Lagrange定理:有限群G的任意子群H的阶整除群的阶,即|H| | |G|
定理1:循环群的子群也是循环群
定理2:设G是n阶有限群,a是G中任一元素,有an=e
定理3:素数阶的群是循环群,且任一与单位元不同的元素是生成元
定理4:设ar是n阶循环群G=<a,>中任意元素,d=gcd(n,r),那么有:
在这里插入图片描述
定理5:在n阶循环群G=<a,>中,ar是生成元当且仅当gcd(r,n)=1

12.双线性映射

双线性映射的定义:
设q是一大素数,G1和G2是两个阶为q的群,其上的运算分别称为加法和乘法。G1到G2的双线性映射e:G1×G1->G2,满足下面的性质:

1.双线性:如果对任意P,Q,R∈G1和a,b∈Z,有其中一条等式成立即可:
在这里插入图片描述
则称该映射为双线性映射

2.非退化性:映射不把G1×G1中的所有元素对(即序偶)映射到G2中的单位元。即若P是G1的生成元,那么e ?(P,P)就是G2的生成元

3.可计算性:对任意的P,Q∈G1,存在一个有效算法计算e ?(P,Q)

  相关解决方案