第一论文网免费提供职业技术教育论文范文,职业技术教育论文格式模板下载

关系学在密码学中的应用

  • 投稿VVVV
  • 更新时间2015-09-23
  • 阅读量720次
  • 评分4
  • 84
  • 0

韩宝燕

(山东工艺美术学院公共课教学部,山东 济南 250000)

【摘 要】本文我们给出关系的定义,讨论关系学中的重要分支之一等价关系,给出关系学在密码学中的应用.

教育期刊网 http://www.jyqkw.com
关键词 密码学;离散数学;关系学

1 关系

宇宙万物之间存在着形形色色的联系,这种联系正是各门学科所关注的根本问题. 例如,人与人之间有父子、兄弟、师生关系;两数之间有大于、等于、小于关系;电学中有电压、电阻与电流间的关系;元素与集合之间的属于关系;计算机科学中程序间的调用关系,程序执行过程中状态之间的转换关系,程序执行前变量取值状况和执行后变量取值状况的关系,文件与路径的关系……集合论为刻划这种联系提供了一种数学模型——关系,它仍然是一个集合,以具有那种联系的对象组合为其成员.换言之,集合论中关系不是通过描述关系的内涵来刻划这种联系,而是通过列举其外延(具有那种联系的对象组合全体)来刻划这种联系.这使关系的研究可以方便地使用集合论概念、运算及研究方法和研究成果.

1.1 关系的定义

在关系模型中,数据是以二维表的形式存在的,这个二维表就叫做关系.关系理论是以集合代数理论为基础的,因此,我们可以用集合代数给出二维表的关系的定义.为了以集合论的角度给出关系的定义,我们先引入笛卡尔积的概念.

在定义笛卡尔积之前,先来了解有序对的定义.

定义1 由两个元素x和y(允许x=y)按一定的顺序排列成的二元组叫做一个有序对(也称序偶),记作<x,y>.其中x是它的第一元素,y是它的第二元素.

一般说来有序对具有以下特点:

(1)当x≠y时,<x,y>≠<y,x>;

(2)两个有序对相等,即<x,y>=<u,v>的充分必要条件是x=u且y=v.

这些特点是集合{x,y}所不具备的,例如,当x≠y时,有{x,y}={y,x}.原因在于有序对<x,y>中强调了x与y的序列性,而集合{x,y}中的x和y是无序的.

定义2 一个有序n元组(n≥3)是一个有序对,其中第一个元素是一个有序n-1元组,一个有序n元组记作<x1,x2,…,xn>,即<x1,x2,…,xn>=<<x1,…,xn-1>,xn>.

下面定义给出笛卡尔积的定义,它是一种集合运算.

定义3 设A、B为集合,用A中元素为第一元素,B中元素为第二元素,构成有序对.所有这样的有序对组成的集合叫做A和B的笛卡尔积,记作A×B.符号化表示为

A×B={<x,y>|x∈A∧y∈B}.

例1 A={a,b},B={0,1,2},则

A×B={<a,0>,<a,1>,<a,2>,<a,2>,<b,0>,<b,1>,<b,2>};

B×A={<0,a>,<0,b>,<1,a>,<1,b>,<2,a>,<2,b>}.

由排列组合的知识不难证明,如果A中有m个元素,B中有n个元素,则A×B和B×A中都有mn个元素.

下面研究与笛卡尔积密切相关的一个重要概念——二元关系.

在现阶段我们用的最多的是二元关系,所谓二元关系就是在集合中两个元素之间的某种相关性.例如,甲、乙、丙3个人进行乒乓球比赛,如果任何两个人之间都要赛一场,那么共要赛三场.假如三场比赛的结果是乙胜甲、甲胜丙、乙胜丙,这个结果可以记作{<乙,甲>,<甲,丙>,<乙,丙>},其中<x,y>表示x胜y.它表示了集合{甲,乙,丙}中元素之间的一种胜负关系.

除了二元关系以外,还有多元关系,在此不做讨论.下面出现关系的地方均指二元关系.下面给出二元关系的一般定义.

定义4 如果一个集合为空集或者它的元素都是有序对,则称这个集合是一个二元关系,一般记作R.对于二元关系R,如果<x,y>∈R,则记作xRy;如果<x,y>∈R,则记作

定义5 设A、B为集合,A×B的任何子集所定义的二元关系称作从A到B的二元关系,特别当A=B时,则叫做A上的二元关系.

对于任何集合A都有3种特殊的关系.其中之一就是空集,它是A×A的子集,也是A上的关系,称作空关系.另外两种就是全域关系EA和恒等关系IA.

定义6 对任何集合A,

EA={〈x,y〉|x∈A∧y∈A}=A×A  IA={〈x,x〉|x∈A}

1.2 关系的性质

在一个很小的集合上就可以定义很多个不同的关系,但是真正有实际意义的只是其中很少的一部分,它们一般都是有着某些性质的关系.

设R是A上的关系,R的性质主要有以下5种:自反性、反自反性、对称性、反对称性和传递性.它们的定义及其在关系矩阵中的特征如表1所示.

根据表1所列的特点不难判断关系的性质.例如,集合A上的全域关系和恒等关系是自反的、对称的和传递的.整除关系、小于等于关系和幂集上的包含关系是自反的、反对称的和传递的.

2 在密码学中的应用

在离散数学中有一种关系——同余关系,面我们来看看它的具体定义.

定义4 给定正整数m,若用m去除两个整数a和b所得余数相同,称a和b对模m同余,记作a≡b(mod m),并称该式为同余式.

对于给定的b和m,与b模m同余的所有数为:

b+km,其中k=0,±1,±2,±….

同余关系具有以下性质:

(1)自反性 a≡a(mod m).

(2)对称性 若a≡b(mod m),则b≡a(mod m).

(3)传递性 若a≡b(mod m),b≡c(mod m),则a≡c(mod m).

不难看出,同余关系是一种等价关系.

实际应用中,我们将这种关系推广到了密码学中,先看一下下面这个例子.

例 凯撒密码

这是一个古老的加密方法,当年凯撒大帝行军打仗时用这种方法进行通信,因此得名.它的原理很简单,其实就是单字母的替换.看一个简单的例子:“This is Caesar Code”.用凯撒密码加密后字符串变为“vjku ku Ecguct Eqfg”.看起来似乎加密得很“安全”.可是你可以尝试一下,把这段很难懂的东西每一个字母换为字母表中前移2位的字母……哦,结果出来了.

凯撒密码的字母对应关系:A b c d e f g h i … x y z

C d e f g h I j k … z a b ([1]) ,

从这个例子不难看出,实际上就是模为2的同余关系的一种应用.再来看下面一个例子.

例 (rot13)ROT13是网络上常见的一种简单的“加密”方式.它的原理和凯撒密码非常类似.凯撒密码移了2位,而ROT13移了13位.ROT13通常作为简单的手段使得我们的电子信件不能被直接识别和阅读,也不会被那些匹配程序用通常的方法直接找到.

如“V Ybir lbh!”这个句子实际上是“I Love you!”.

ROT13字母对应关系:A b c d e f g h I … x y z

N o p q r s t u v … k l m ([2])

教育期刊网 http://www.jyqkw.com
参考文献

[1][美]Paul Garrett.密码学导引[M].北京:机械工业出版社,2003:107-178.

[2]斯汉.密码学与计算机网络安全[M].北京:清华大学出版社,2001:17-58.

[3]耿素云,屈婉玲,张立昂,编.离散数学.3版.北京:清华大学出版社,2004,3.

[责任编辑:汤静]