密码学数学基础(一)

admin 2022年10月8日08:41:54评论35 views字数 3455阅读11分31秒阅读模式

密码学数学基础(一)

密码学数学基础(一)

突然感觉自己没什么可写了,就算是新的密码学算法,我这种小菜鸡也是只能来简单的复述一下他的过程,所以呢,打算对密码学算法告一个段落,来补一下我这所剩无几的数学知识,所以打算写一个有关密码学当中所用到的数学基础的一个系列的文章,正好也催促这我来看这部分知识,因为我的能力和水平实在有限,因此文章当中如果说哪里出现错误,也还请各位大佬给指出来,在这里小Q先谢谢各位读者大佬们了。

先来个开篇词吧,也就是随便聊聊,聊到数学相信各位读者可能和我一个感受,那就是头大,如果是数学大佬,估计也不会来看我这篇文章了,相信书本上和论文里面介绍的要比我好得多,所以呢,我这里尽量用我所理解的东西来吧这部分知识复述出来,毕竟根据学习金字塔(图片来源于网络),真正讲出来,可能记忆才是最深刻的,我本身也不是学数学的,在看相关的数学知识的时候也很是头大,不过好在有相关的书籍来帮助我学习,在这里感谢所有写书的作者,来帮助我这种小菜鸡来理解相关的知识,好了有关这个系列的初衷就聊这么多,话不多说,我们来开始这一篇文章吧。

密码学数学基础(一)

前言

提到密码学的数学基础,那么首先肯定是要讲到数论的相关知识了,这个我光在这里说,可能读者也感受不到这一点,那么我们来搜一下密码学数学基础的相关书籍,然后我们来看一下它们的目录(图片来源于参考资料[^1])。

密码学数学基础(一)

那么为什么大多数讲到密码学相关的数学知识,大概率都会要先讲一下数论呢,这里我先卖个关子,等介绍完了相关的知识,再来说一说我的个人看法,也给不了解相关知识的读者一个缓冲。

「数论」(Number Theory)是纯粹数学的分支之一,主要研究整数的性质[^2]。对于数论当中的很多知识呢,其实我们在小学都是学过的,因此呢,本文呢捎带着回顾回顾小学所学过的知识。

背景

我们先来看一个大家经常看到的场景,相信大家应该都经历过排队列的场景,考虑一下,下面的情况,假设一共要给12个人排队,那么我们可以将这12个人按照如下的分组。

密码学数学基础(一)
排队样例图

这里我们只考虑行比列多的情况,如果说是列比行多,上面的所有小人儿左转或者右转90度就好了,实际上来说,他们是等价的。

这里我们来回顾一下真小学二年级所学过的除法知识[^3]

密码学数学基础(一)
小学二年级除法

看到上面的例子,是不是仿佛回到了小学的时光,时光荏苒,岁月变迁,我们又重新的回到了学习小学所学的知识,通过上面的知识呢,我们来引出来我们本次文章的主角,「整除的概念」

整除的概念

首先呢,我们先来定义一些符号,看到这些符号读者们不要害怕,这实际上只是一些notation而已,就好比我们用 「苹果」 这两个字来表示苹果树的果实,一般呈紅色,但需視品種而定,富含矿物质和维生素,是人们最常食用的水果之一[^4]。在数学当中呢,我们也会使用一些符号来表示一些东西,这里所用的符号呢,我采用我之前所学到的记号来表示,如果说读者用过其他的版本,那就忍一下吧,溜了溜了。

符号(Notation)

  • : 表示全体整数组成的集合

  • :表示全体自然数组成的集合(这里自然数包括0)

相关定义

「定义1」,如果存在,使得,那么,就说b可以被a整除,记作,称b是a的倍数,a是b的因子(也有叫做约数或者除数的)。否则,我们说b不可以被a整除,或者a不整除b,记作

上面这个定义呢,就是整除的官方定义了,可能读者会觉得这个定义实在是太抽象了,那么我们先来用简单的例子来理解一下上面的定义,这个例子呢还是用小学二年级所学过的知识来讲吧。

假设,我们有b个桃子,然后需要分给a个小朋友,这里呢显然桃子和小朋友肯定都是整数了(不考虑孙悟空偷吃桃子,只剩下核儿的这种情况哈),然后呢,如果每个小朋友恰好所分的的桃子都相等,并且恰好是q个,而且桃子没有剩余,这时候呢,我们就可以说这b个桃子可以均分给a个小朋友,每个小朋友可以分到q个桃子,否则呢,我们就可以说,b个桃子不能均分给a个小朋友了,对比这个例子,我们再来看一下整除的定义,这样是不是就会比较清晰了,也就是说,如果b可以被a整除,那么就代表可以把b均分成a份,并且没有剩余。

好了,这里我们介绍完整除的定义,接下来我们来升华一下,来看一下整除相关的性质吧。

整除的性质

假设,我们有

  • 对任意的

  • ,则

好了,这次我们来证明一下这几个性质吧,证明这块不感兴趣的读者可以直接略过了,证明这块就当做我的笔记了,有兴趣的读者可以看看。

「证明」

1) 由于,我们根据整除的定义可以得到同样的,,从而我们可以得到

也就是。(这里直接使用了乘法的交换律和结合律,后续这种常识性的定律就不在一一指出了)

2) 我们先来证明一下充分性,通过,我们同样的可以根据整除的定义,对于任意的,我们有

这也就是

接下来,我们来证明一下必要性,我们通过可以得到,对于任意的,我们一定可以找到一组使得,那么我们就得到了

然后,对比一下就可以得到也就是

3) 通过我们可以得到 a = qb,然后可以推的 am = q(bm)也就是,然后我们来证明一下必要性,通过我们可以得到 ma = q(mb),又因为我们可到达a = qb 也就是

4)通过我们可以得到 也就是因为所以我们可以得到如果说a=0,那么根据n那么b=0,满足条件,如果说我们可以得到也就是或者也就得到了

5)我们用一下反证法,不妨假设b > 0,并且b < a,由于 我们可以得到 a = qb,然后可以得到b < qb,因为b >0 所以1 < q,这里显然与q为整数矛盾,因此呢我们有 a ≥ b。同理b < 0时可以得到类似结论,因此呢可以得到

到这里呢,有关于整除的一些性质,我们在这里就证明完了,那么我们对其中的某几个性质来个通俗点的解释吧,我们先来看性质1,还是用小朋友分桃子的例子来看,b个桃子可以分给a个小朋友,然后c个桃子可以分给b个小朋友,那么c个桃子是不是一定可以分给a个小朋友,不信的话,可以自己分一分试一下,我们再来看一下第三个性质,我们有b个桃子,可以分给a个小朋友,那么来了mb个桃子,是不是可以分给ma个小朋友,这个很好理解,我们可以先把mb个桃子分成m份,每份是b个桃子,然后再把ma个小朋友也分为m组,每组是a个小朋友,对于每一组当中,我们是不是可以把b个桃子分给a个小朋友,然后组数相同,因此呢,我们可以得到这个性质哈。到这里,有关于整除的相关知识呢,就介绍的差不多了,最后呢,我们来个小结吧。

小结

在小结之前,我先来说一下为什么大部分的密码学数学基础都会先介绍数论的相关知识,通过维基百科我们可以知道,数论是主要研究整数的数学分支,思考一下,在计算机当中呢,无论是整数还是浮点数,存在计算机当中的是不是都是有限大小的内存,比如说我们存一个无符号的32位整数,它占用了4个字节,然后它的范围是固定的大小,也就是说,我们在对于数据的处理上,并不会去实际的存连续的值,即使是浮点数,根据IEEE表示法,他也不是连续的,也就是说,我们在绝大多数密码学算法当中,都会和整数来打交道,而刚才我们说了,数论就是来研究整数性质的一个数学分支,因此呢,了解数论相关的知识是十分的必要的。

这里是真的小结了,开这系列的文章呢,主要还是以我的学习笔记为主,还是佛系更新,没准下篇就没了,溜了溜了,为了给我的文章增加点文艺的气息,作为结尾呢,咱们来一句诗词吧,就当学完数学之后看点其他的,换换脑子了。

沉舟侧畔千帆过,病树前头万木春。—刘禹锡【唐】

即使是沉舟,旁边也总会有其他千千万万的帆船经过,枯木前面,也会迎来春意盎然的春天,人生道路千千万万,实话说,写到这里我没词了,好,本篇文章到此结束,我们下次再见~~

参考资料

[^1]: 信息安全数学基础(第2版)陈恭亮[1]

[^2]: https://en.wikipedia.org/wiki/Number_theory[2]

[^3]: 苏教版小学数学二年级上册[3]

[^4]: https://zh.wikipedia.org/zh/苹果[4]

Reference

[1]

信息安全数学基础(第2版)陈恭亮: "信息安全数学基础(第2版)陈恭亮"

[2]

https://en.wikipedia.org/wiki/Number_theory: https://en.wikipedia.org/wiki/Number_theory

[3]

苏教版小学数学二年级上册: "苏教版小学数学二年级上册"

[4]

https://zh.wikipedia.org/zh/苹果: https://zh.wikipedia.org/zh/苹果


原文始发于微信公众号(Coder小Q):密码学数学基础(一)

  • 左青龙
  • 微信扫一扫
  • weinxin
  • 右白虎
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2022年10月8日08:41:54
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出):
                   密码学数学基础(一)http://cn-sec.com/archives/1335791.html

发表评论

匿名网友 填写信息