密码学笔记(1)——数论准备知识
发布日期:2022-01-31 14:08:46 浏览次数:10 分类:技术文章

本文共 9971 字,大约阅读时间需要 33 分钟。

  最近因为毕业论文的需要开始阅读冯登国老师的《密码学原理与实践》(第三版),一边读一边做自己的读书笔记,加深对密码学的理解。

  在密码学中可以看到大量的数论知识,这些都是抽象代数课程的一部分内容,有时间我会再以另外一个分类的形式叙述抽象代数的内容。在这里只叙述密码学中应用到的内容及其扩充。

一、一些基本概念

Def1 (群)设G是一个非空集合,若在G上定义一个二元运算" · ",它满足

(1) 结合律:对任何 $ a,b,c  \in G,有 (a \cdot b) \cdot c = a \cdot (b \cdot c) $,则称G是一个半群,记作 $ (G, \cdot ) $ ,若 $ (G, \cdot ) $还满足

(2) 存在单位元 $ e \in G $ ,使得对任何 $ a \in G $ 有 $ e \cdot a = a \cdot e = a $ 

(3) 对任何 $ a \in G $ ,有 $ a^{-1} \in G $ ,使得 $ a^{-1} \cdot a = a \cdot a^{-1} = e $ ,则称 $ (G, \cdot ) $ 是一个

如果半群中也有单位元,则称为幺半群

 

Def2 (交换群)如果群 $ (G, \cdot ) $ 满足交换律:对任何 $ a,b \in G $ 有 $ a \cdot b = b \cdot a $ ,则称G为交换群或者Abel群

 

Def3 (环)设R是一个非空集合,如果在R中有两种运算 $ +,\cdot $ 满足一下条件:

(1) R是加法Abel群乘法半群

(2) $ a \cdot (b \cdot c) = (a \cdot b) \cdot c $

(3) $ (a + b) \cdot c = a \cdot c + b \cdot c $ 和 $ a \cdot (b + c) = a \cdot b + a \cdot c $ 对任何 $ a,b,c \in R $ 成立。

(4) 存在 $ e \in R $ ,使得 $ e \cdot a = a \cdot e = a $ 对任何 $ a \in R $ 成立,e称为R中的单位元(或幺元)

则称R为一个

PS:在许多抽象代数课本中,第(4)条不是环定义所必须的,不过在密码学讨论的环中一般都是包含有单位元的环。

 

Def4 (模m剩余类环)集合 $ \{ 0,1,…, m-1 \} $ 与运算加法(+)和乘法($\times$)定义为模m剩余类环,记为$ Z_{m} $ 。

 

Thm5 设 $ a \in Z_{m} $ ,对任意的 $ b \in Z_{m} $ ,同余方程 $ ax \equiv b(mod \, m) $ 有唯一解 $ x \in Z_{m} $ 的充分必要条件是 $ gcd( a , m ) = 1 $。

证明:假设 $ gcd(a,m) ≠ 1 $,那么设 $ gcd(a,m) = d > 1 $ ,那么同余方程 $ ax \equiv 0(mod \, m) $ 至少有两个解,分别为$ x = 0 $ 和$ x = m / d $ ,矛盾。

假设 $ gcd(a,m) = 1 $,如果存在 $ x_{1},x_{2} $ 使得$$ ax_{1} \equiv ax_{2}(mod \, m) $$

那么有$$ a(x_{1} - x_{2}) \equiv 0(mod \, m) $$

于是$$ m \mid a(x_{1} - x_{2}) $$

根据整除的基本属性,由于$ gcd(a , m) = 1 $,即 $ m \mid (x_{1} - x_{2}) $,这就意味着 $ x_{1} \equiv x_{2}(mod \, m) $,于是同余方程的解是唯一的。

 

Def6 (欧拉函数)设 $ a \geq 1 ,m \geq 2 $且均为整数,如果 $ gcd( a , m ) = 1 $,则称a与m互素,在 $ Z_{m} $中所有与m互素的数的个数使用 $ \phi (m) $来表示,称为欧拉函数

 

Thm7 (欧拉函数的一种计算公式)假定 $$ \prod_{i=1}^{n} {p_{i}} ^ {e_{i}} $$这里$ p_{i} $均为素数且互不相同,$ e_{i}>0 ,  1 \leq\ i \leq n $。则$$ \phi (m) = \prod_{i=1}^{n} {({p_{i}}^{e_{i}} - {p_{i}}^{e_{i}-1})} $$

 

Def8 (乘法逆)设$ a \in Z_{m} $,若存在$ a^{'} \in Z_{m} $,使得$ aa^{'} \equiv a^{'}a \equiv 1(mod \, m) $,则$a^{'}$称为a在$Z_{m}$上的乘法逆,将其记为$a^{-1} mod \, m$。在m是固定的情形下,也可将其简记为$a^{-1}$。

  以上基本是书本第一章介绍的数论知识,下面根据此介绍Euclidean算法和中国剩余定理,该内容在书上的第五章。

二、Euclidean算法

  Euclidean算法又称为辗转相除法,是求给定两个非负整数的最大公约数(用gcd(a,b)表示),其中最为本质的是来源于多项式环中的带余除法,可以总结为如下的定理。

Thm9  (带余除法)设R为一个交换环(即对乘法可交换),$f(x),g(x) \in R[x]$,若$g(x) \neq 0$且它的首项系数是R中的乘法可逆元,则存在唯一的一对多项式$q(x),r(x) \in R[x]$,使得

(1)$f(x) = g(x)q(x) + r(x)$;

(2)$deg(r) < deg(g)$;

此时q(x)称为,r(x)称为余式

  算法的主要步骤是令两个数中较大的数作为被除数,较小的数作为除数做带余除法,得到余数,除数和余数继续做带余除法,直到某一项中余数为0,那么商为最大公约数,换言之,是如下的一个过程。

  令这两个数为a,b,且$ a > b $,取商序列为$q_{i}$,余数序列为$r_{i}$,其中$r_{0} = a , r_{1} = b , 0 \leq i \leq + \infty $,则$$ \begin{align} r_{0} &= r_{1}q_{1}+r_{2},r_{2} < q_{1} \\ r_{1} &= r_{2}q_{2}+r_{3},r_{3} < q_{2} \\ r_{2} &= r_{3}q_{3} + r_{4},r_{4} < q_{3}\\ r_{3} &= r_{4}q_{4} + r_{5},r_{5} < q_{4}\\ &……\\ r_{n-2} &= q_{n-1}r_{n-1}+r_{n},r_{n} < q_{n-1} \\ r_{n-1} &= q_{n}r_{n} \end{align}$$

  于是最大公约数即为$r_{n}$,写成代码版本就是

#include 
// std::swap for c++ before c++11#include
// std::swap for c++ since c++11int gcd(int a,int b){ if (a < b) std::swap(a, b); return b == 0 ? a : gcd(b, a % b);}

  但是这里有一个问题存留就是,怎么证明算法过程是对的,也就是,为什么这么做可以求得最大公约数,需要一个严格的数学证明。

Thm10 在上述Euclidean算法中,有如下结论 $$gcd( a , b ) = gcd ( b , r_{1} ) = gcd ( r_{1} , r_{2} ) = gcd ( r_{2} , r_{3} ) = …… = gcd ( r_{n-2} , r_{n-1} ) = gcd(r_{n-1} , r_{n}) = r_{n} $$

证明:

  令$gcd( a , b ) = d$,那么有$ d \vert a $ 以及 $ d \vert b $,由$a = bq_{1}+r_{1}$,可知$a - bq_{1} = r_{1}$,那么得到$d \vert r_{1} $,又因为$d \vert b$,即有d为b和$r_{1}$的公约数,接下来要证明的是$d是b和r_{1}$的最大公约数。

  假设存在$gcd(b,r_{1}) = d^{'} > d$,那么由于$d和d^{'}$都是公约数,有$d^{'} = dh,h > 1$,那么由$a = bq_{1}+r_{1}$就容易得到$d^{'} \vert a$,所以$d^{'}$也是$a和b$的公约数,显然这与$d = gcd(a,b)$矛盾,这就说明$d^{'} \leq d$。

  如果$d^{'} < d$,这与$d \vert r_{1},d \vert b$矛盾,于是只能够$d^{'} = d$。

  同理可一直这样子证到最后一步,当能整除时,最大公约数当然是待比较的两个数中较小的那个数。

  到这里为止,由于Euclidean算法能计算出最大公因子,它可以用来判断一个非负整数$b < n$是否有模n的乘法逆,如果求出来最大公约数为1,说明b与n互素,否则说明b与n有公因子。不过还存在一个问题是,当b与n互素的时候,还是没有办法求出$b^{-1} mod \, n$,因此下一步我们要想办法求出乘法逆,这就是接下来要介绍的扩展Euclidean算法,先讨论它的数学理论,那就是著名的Bezout等式。

Thm11 (Bezout定理的数学版本)设$a,b \geq 0$且为整数,则$gcd( a , b ) = c_{1}a+c_{2}b$,其中$c_{1}和c_{2}$为常数。

证明:回忆辗转相除法的求解过程,我们令$gcd(a,b) = r_{n}$,在倒数第二步的时候有$$r_{n-2} = r_{n-1}q_{n-1}+r_{n}$$求解$r_{n}$得$$\begin{align} r_{n} &= r_{n-2}-r_{n-1}q_{n-1} \\ &=r_{n-2} - (r_{n-3}-r_{n-2}q_{n-2})q_{n-1} \\ &=(1+q_{n-2}q_{n-1})r_{n-2}-q_{n-1}r_{n-3} \\ &=(1+q_{n-2}q_{n-1})(r_{n-4}-r_{n-3}q_{n-3})-q_{n-1}r_{n-3} \\ & …… \\ &=ua+vb \\ \end{align}$$

  证明过程其实也就是将辗转相除法倒回去计算,不断的递归消去$r_{i}$,从而得到原来a和b的一个线性组合。下一步考虑的是如何使用计算机实现扩展的Euclidean算法,课本上给出伪代码的形式,我将其转化为C++的代码求解。

1 #include 
2 using namespace std; 3 4 void Extended_Euclidean_Algorithm(int a, int b) 5 { 6 int a0 = a; 7 int b0 = b; 8 int t0 = 1; 9 int t = 0;10 int s0 = 0;11 int s = 1;12 int q = a0 / b0;13 int r = a0 - q*b0;14 int temp = 0;15 while (r > 0)16 {17 //迭代系数t18 temp = t0 - q*t;19 t0 = t;20 t = temp;21 //迭代系数s22 temp = s0 - q*s;23 s0 = s;24 s = temp;25 //求最大公约数26 a0 = b0;27 b0 = r;28 q = a0 / b0;29 r = a0 - q*b0;30 }31 r = b0;32 cout << "最大公约数为:" << r << endl;33 cout << "s的值为:" << s << endl;34 cout << "t的值为:" << t << endl;35 cout << "sa+tb=" << s*a + t*b << endl;36 }37 38 int main()39 {40 int a, b;41 cin >> a >> b;42 Extended_Euclidean_Algorithm(a, b);43 system("pause");44 return 0;45 }

  这里面最难理解的是两个迭代系数为什么要如此进行求解,为此我们需要如下一个定理。

Thm11' (Bezout定理的计算机版本)给定$r_{i}$为Euclidean算法中$r_{i}$的定义,那么对于$0 \leq i \leq m$,有$r_{i} = s_{i}r_{0} + t_{i}r_{1}$,其中定义序列$s_{i}$和$t_{i}$如下$$s_{i} = \begin{cases} 1 &\text i = 0 \\ 0  &\text i = 1 \\ s_{i-2} - q_{i-1}s_{i-1} &\text i \geq 2 \\ \end{cases} $$ $$t_{i} = \begin{cases} 0 &\text i = 0 \\ 1 &\text i = 1 \\ t_{i-2} - q_{i-1}t_{i-1} &\text i \geq 2\\ \end{cases} $$

证明:

  只需要对i用归纳法证明即可,当$i = 0 和 i = 1$时命题显然成立,假设命题对于$i = k - 1和 i = k - 2,k \geq 2$时成立,我们需要证明命题对于$i = k$时成立,由归纳假设有$$r_{k-2} = s_{k-2}r_{0} + t_{k-2}r_{1}$$和$$r_{k-1} = s_{k-1}r_{0} + t_{k-1}r_{1}$$现在计算$$\begin{align} r_{k} &= r_{k-2}-q_{k-1}r_{k-1}\\ &= s_{k-2}r_{0}+t_{k-2}r_{1}-q_{k-1}(s_{k-1}r_{0}+t_{k-1}r_{1})\\ &=(s_{k-2}-q_{k-1}s_{k-1})r_{0}+(t_{k-2}-q_{k-1}t_{k-1})r_{1} \\ &=s_{k}r_{0}+t_{k}r_{1} \\ \end{align}$$

  因此由归纳法可知,命题对于所有整数$i \geq 0$是正确的。

  有了这个定理,我们就理解了这个迭代系数是怎么设置的了,也就明白了整个扩展Euclidean算法的流程了,有了这个算法,我们就可以求$b^{-1} mod \, m$了,来看下面的一个定理。

Thm12 假设$gcd(r_{0} , r_{1}) = 1$,则$r^{-1}_1 (mod \, r_{0}) = t_{n} (mod \, r_{0})$,其中$t_{n}$如前面定义。

证明:

  由Thm11',可以得到$$1 = gcd(r_{0} , r_{1}) = s_{n}r_{0} + t_{n}r_{1}$$两边模$r_{0}$约化等式就可以得到$$ t_{n}r_{1} \equiv 1(mod \, r_{0})$$得证。

  最后要说的是,在扩展Euclidean算法中,如果只为了求$b^{-1} mod \, m$,可以将所有的$s_{i}$过程全部去掉,只留下求$t_{i}$的过程。

三、中国剩余定理

  中国剩余定理是求解特定的同余方程组的方法。考虑$m_{1},…,m_{r}$为两两互素的正整数,假定$a_{1},…,a_{r}$为整数,考虑如下的同余方程组$$ \begin{align} x &\equiv a_{1} \quad (mod \, m_{1}) \\ x &\equiv a_{2} \quad (mod \, m_{2}) \\ x &\equiv a_{3} \quad (mod \, m_{3}) \\ &……\\ x &\equiv a_{r} \quad (mod \, m_{r}) \\ \end{align}$$中国剩余定理断言这个方程组有模$M=m_{1} \times m_{2} \times m_{3} \times … \times m_{r}$的唯一解。

Thm13 (中国剩余定理)假定$m_{1},…,m_{r}$为两两互素的正整数,$a_{1},…,a_{r}$为整数,那么同余方程组$x \equiv a_{i}(mod \, m_{i})(1 \leq i \leq r)$有模$M=m_{1} \times m_{2} \times … \times m_{r}$的唯一解,此解由下列式子给出:$$x=\sum_{i=1}^{r}a_{i}M_{i}y_{i} \, (mod \, M)$$其中$M_{i} = M/m_{i}$,且$y_{i} = M^{-1}_{i} mod \, m_{i},1 \leq i \leq r$。

证明:

  如上述定义,设$1 \leq i \leq r$,则有$M_{i} = M/m_{i}$,那么有$$ gcd(M_{i},m_{i}) = 1 $$  

  再由前面Thm12可知$y_{i}$的定义是合理的,因此可以得到$$ \begin{align} M_{i}y_{i} &\equiv 1(mod \, m_{i})\\ a_{i}M_{i}y_{i} &\equiv a_{i}(mod \, m_{i})\\ \end{align}$$ 

  注意到$M_{i}$的构造,可以知道当$i \neq j$时,有$$a_{i}M_{i}y_{i} \equiv 0(mod \, m_{j}) $$

  现在,定义一个函数$\rho: Z_{m1} \times Z_{m2} \times … \times Z_{mr} \longrightarrow Z_{M}$如下:$$\rho (a_{1},a_{2},…,a_{r}) = \sum_{i=1}^{r}a_{i}M_{i}y_{i} \, (mod \, M) $$

  于是很容易得到这个函数$$ \rho (a_{1},a_{2},…,a_{r}) \equiv a_{i}(mod \, m_{i}) $$

  因此这个函数就是我们需要的中国剩余定理的解。

  对于证明唯一性,需要考虑它的反函数$$\chi: Z_{M} \longrightarrow Z_{m1} \times Z_{m2} \times …… \times Z_{mr}$$

  这个函数是从基数为M的定义域到基数为M的值域的映射,很显然这是一个单射,通过计数可以验证它是一个满射,因此它是一个双射,再由离散数学相关定理可知道它的反函数也是一个双射,证毕。

 四、其他有用的结果

Def14 (元素和群的阶数)对于一个有限群G,定义元素$g \in G$的阶数为使得$g^{m} = 1$的最小正整数m,定义群的阶数为群的所有元素个数。

 

Thm15  (Lagrange定理)假定G是一个阶为n的乘法群,且$g \in G$,那么g的阶整除n。

证明:这个证明需要较多的抽象代数知识,故先略去。

 

Thm16 定义$Z^{ \star }_{n}$为$Z_{n}$中所有与n互素的全体元素的集合,如果$b \in Z^{ \star }_{n}$,那么$b^{\phi (n)} \equiv 1 (mod \, n)$,其中$\phi (n)$为欧拉函数

证明:这是因为$Z^{\star}_{n}$是阶为$\phi (n)$的乘法群。

 

Thm17  (Fermat小定理)假定p是一个素数,且$b \in Z_{p}$,那么$b^{p} \equiv b(mod \, p)$

证明:如果p是一个素数,那么欧拉函数$\phi (p) = p - 1$,且$b \in Z_{p}$,因此$gcd(b , p) = 1$,由Thm16可知$b^{\phi (p)} \equiv 1 (mod \, p)$,即$b^{p-1} \equiv 1 (mod \, p)$,两边再同乘一个b即证。

 

Def18 (模p的本原元素)如果一个元素b具有模p的阶等于p-1,即对于所有的$1 \leq i \leq p-2$,均有$b^{i} \neq 1(mod \, p)$,且$b^{p-1} \equiv 1(mod \, p)$。

 

Thm19 假定p是一个素数且b是一个模p的本原元素,任一元素$\beta \in Z^{\star}_{p}$可以写成唯一的形式$\beta = b^{i}$,其中$0 \leq i \leq p-2$,且$\beta$的阶为$\frac{p-1}{gcd(p-1,i)}$

证明:

  利用抽象代数的知识可知道任何一个有限循环群可以写成生成元的幂次的形式,且最高幂次+1就是群的阶,因此这个定理的前半部分是非常显然的。

  后半部分通过计算得$$\beta ^{\frac{p-1}{gcd(p-1,i)}} \quad = b^{\frac{i(p-1)}{gcd(p-1,i)}}$$

  那么令$k = \frac{i}{gcd(p-1,i)} \in N$,于是就有$$\beta ^{\frac{p-1}{gcd(p-1,i)}} \quad = b ^{k(p-1)} = b ^{(p-1)k} = 1^{k} = 1$$

PS:模p的本原元素的个数为$\phi (p-1)$

  有了Thm19,我们可以迅速的确定某个素数的本原元素个数,但是如果还需要计算它们的具体值,还需要根据定义验证所有的幂次值,这在素数非常大的情况下是很难的,有没有什么更快的方法呢?

Thm20 假定$p > 2$是一个素数,且$b \in Z^{\star}_{p}$,那么当b是一个模p的本原元素当且仅当$b^{\frac{p-1}{q}} \neq 1(mod \, p)$对于所有满足$q \mid (p-1)$的素数q都成立。

证明:

  充分性显然,下面来证必要性。

  假定$ b \in Z^{\star}{p}$不是模p的本原元素。令d为b的阶,由Lagrange定理有$d \mid (p-1)$。

  因为b不是本原的,所以有$d < p-1 $,于是有$\frac{p-1}{d}$是一个大于1的整数,取q为$\frac{p-1}{d}$的素因子(即除了1和q以外没有),那么有d是$\frac{p-1}{q}$的一个因子,从而有$$b^{d} \equiv 1(mod \, p)且d \mid \frac{p-1}{q}$$于是$b^{\frac{p-1}{q}} \equiv 1(mod \, p)$,证毕。

  下一篇文章我打算会一边更新我在读的RSA密码体制内容,一边更新以前读过的一些概率论和熵的知识。

转载于:https://www.cnblogs.com/jcchan/p/8408768.html

转载地址:https://blog.csdn.net/dianshou3172/article/details/102373979 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:密码学笔记(2)——RSA密码
下一篇:密码学笔记(3)——分解因子算法

发表评论

最新留言

网站不错 人气很旺了 加油
[***.192.178.218]2024年03月22日 13时36分43秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

java list二分查找_java中的ArrayList和LinkedList的二分查找速度比 | 学步园 2019-04-21
php中的变量名称用什么表示,PHP变量,方法,类等名称中的有效字符是什么? 2019-04-21
pic32mx是什么cpu_PIC32MX单片机外设库使用(Ⅰ)- 系统时钟及I/O口基本设置 2019-04-21
用c 在mysql上存图片_C 批量保存图片进 mysql 利用MYSQL_BIND插入longblob 2019-04-21
mysql 1045 28000_mysql报关于用户密码1045(28000),几种处理方法 (zhuan) 2019-04-21
solr比mysql的优势_Solr与Elasticsearch的优缺点比较总结和归纳 2019-04-21
华为博士招聘上机考试题目_牛客网-华为-2020届校园招聘上机考试-3 2021-06-24
python中for可以做变量名吗_Python中使用动态变量名的方法 2021-06-24
mysql 日期转换天数_MySQL 日期操作 增减天数、时间转换、时间戳 2021-06-24
java对象去重复_JAVA中List对象去除重复值的方法 2021-06-24
java bss_[转] .bss段和.data段的区别 2021-06-24
java上传图片损坏_大神求助 上传图片后 图片损坏 2021-06-24
java socket唯一标识符_Java Socket编程之常识网络基础知识 2021-06-24
java给xyz大小排序_java递归实现string xyz排序 2021-06-24
arctime必须要java_Arctime使用教程 Arctime常见问题解答 2021-06-24
mysql pxc mysql5.7_mysql之PXC5.7.18集群系列——1. Percona XtraDB Cluster 搭建 2021-06-24
mysql 自适应字段宽度_box-sizing解决自适应布局容器宽度问题 2021-06-24
java 配置文件配置路径_Java读取配置文件路径设置 2021-06-24
vux 选择器_vue中的scoped分析以及在element-UI和vux中的应用 2021-06-24
java cache 有效期_springboot cache 自定义过期时间及自定义缓存key前缀 2021-06-24