关系学在密码学中的应用

《关系学在密码学中的应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、关系学在密码学中的应用韩宝燕（山东工艺美术学院公共课教学部，山东济南250000）【摘　要】本文我们给出关系的定义，讨论关系学中的重要分支之一等价关系，给出关系学在密码学中的应用..jyqk个元素，B中有n个元素，则A×B和B×A中都有mn个元素.下面研究与笛卡尔积密切相关的一个重要概念——二元关系.在现阶段我们用的最多的是二元关系，所谓二元关系就是在集合中两个元素之间的某种相关性.例如，甲、乙、丙3个人进行乒乓球比赛，如果任何两个人之间都要赛一场，那么共要赛三场.假如三场比赛的结果是乙胜甲、甲胜丙、乙胜丙，这个结果可以记作{<乙，甲

2、>,<甲，丙>,<乙，丙>}，其中<x,y>表示x胜y.它表示了集合{甲，乙，丙}中元素之间的一种胜负关系.除了二元关系以外，还有多元关系，在此不做讨论.下面出现关系的地方均指二元关系.下面给出二元关系的一般定义.定义4　如果一个集合为空集或者它的元素都是有序对，则称这个集合是一个二元关系，一般记作R.对于二元关系R，如果<x,y>∈R，则记作xRy；如果<x,y>∈R，则记作定义5　设A、B为集合，A×B的任何子集所定义的二元关系称作从A到B的二元关系，特别当A=B时，则叫

3、做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所列的特点不难判

4、断关系的性质.例如，集合A上的全域关系和恒等关系是自反的、对称的和传递的.整除关系、小于等于关系和幂集上的包含关系是自反的、反对称的和传递的.2　在密码学中的应用在离散数学中有一种关系——同余关系，面我们来看看它的具体定义.定义4　给定正整数m，若用m去除两个整数a和b所得余数相同，称a和b对模m同余，记作a≡b(modm)，并称该式为同余式.对于给定的b和m，与b模m同余的所有数为：b＋km，其中k＝0，±1，±2，±….同余关系具有以下性质：（１）自反性　a≡a(modm).（２）对称性　若a≡b(modm)，则b≡a(modm).（３

5、）传递性　若a≡b(modm)，b≡c(modm)，则a≡c(modm).不难看出，同余关系是一种等价关系.实际应用中，我们将这种关系推广到了密码学中，先看一下下面这个例子.例　凯撒密码这是一个古老的加密方法，当年凯撒大帝行军打仗时用这种方法进行通信，因此得名.它的原理很简单，其实就是单字母的替换.看一个简单的例子：“ThisisCaesarCode”.用凯撒密码加密后字符串变为“vjkukuEcguctEqfg”.看起来似乎加密得很“安全”.可是你可以尝试一下，把这段很难懂的东西每一个字母换为字母表中前移2位的字母……哦，结果出来了.凯撒

6、密码的字母对应关系：Abcdefghi…xyzCdefghIjk…zab（[1]），从这个例子不难看出，实际上就是模为2的同余关系的一种应用.再来看下面一个例子.例　（rot13）ROT13是网络上常见的一种简单的“加密”方式.它的原理和凯撒密码非常类似.凯撒密码移了2位，而ROT13移了13位.ROT13通常作为简单的手段使得我们的电子信件不能被直接识别和阅读，也不会被那些匹配程序用通常的方法直接找到.如“VYbirlbh!”这个句子实际上是“ILoveyou!”.ROT13字母对应关系：AbcdefghI…xyzNopqrstuv…kl

7、m([2]).jyqk].北京:机械工业出版社,2003:107-178.［２］斯汉.密码学与计算机网络安全[M].北京:清华大学出版社,2001:17-58.［３］耿素云,屈婉玲,张立昂,编.离散数学.3版.北京:清华大学出版社,2004,3.［责任编辑：汤静］