關系學在密碼學中的應用

韓寶燕

（山東工藝美術學院公共課教學部，山東 濟南250000）

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.符號化表示為

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

由排列組合的知識不難證明，如果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上的二元關系.

定義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上的全域關系和恒等關系是自反的、對稱的和傳遞的.整除關系、小于等于關系和冪集上的包含關系是自反的、反對稱的和傳遞的.

表1

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])

［1］[美]Paul Garrett.密碼學導引[M].北京：機械工業出版社,2003：107-178.

［2］斯漢.密碼學與計算機網絡安全[M].北京：清華大學出版社,2001：17-58.

［3］耿素云,屈婉玲,張立昂,編.離散數學.3 版.北京：清華大學出版社,2004,3.