（基础数学专业论文）一种新的矩阵加密系统.pdf

摘要 自1 9 7 6 年以来，公钥密码系统发展迅速，大量的研究人员对密码学的发 展做出了巨大的贡献。在上一世纪九十年代，曹珍富提出了一个新的公钥密码 系统。它的加密算法基础是基于计算一个二次型的值，解密算法是利用中国 剩余定理解一组二次同余式。后来，曹珍富和张彪合作破解了原有的系统， 并对最早的原型给出了修改形成了现在成熟的c a o l i 系统。 在本文中，我们将指出c a o l i 公钥密码系统由于某些参数选择会导致系 统的安全问题；其次，利用背包系统对c a o l i 系统进行改进，解决原有系统 的参数问题。 a b s t r a c t s i n c e1 9 7 6 ，p k ih a sd e v e l o p e dv e r yf a s ta n dm a n yr e s e a r c h e r sh a v em a d eag r e a t d i s t r i b u t i o nt oi t sd e v e l o p m e n ti n1 9 9 0 s ，c a oz h e n f up u tf o r w a r dw i t hau e wp u b l i ck e y c r y p t o s y s t e m i t sd e c o d i n ga l g o r i t h mi s b a s e do nc a c u l a t i n gav a l u eo faq u a d r a t i cf o r m 、 i t se n c o d i n ga l g o r i t h mm a k e su s eo fc h i n e s er e m a i n d e rt h e o r e mt os o l v eaq u a d r a t i c c o n g r u e n c e i n1 9 9 5 c a oz h e n f ua n dz h a n gb i a ow o r k e dt o g e t h e rt ob r e a kd o w nt h e s y s t e ma n dt om o d i f yt h eo r i g i n a ls y s t e mt ot u r ni ti n t oam a t u r ec r y p t o s y s t e m i n t h i sp a p e r ，i tw a sp o i n t e do u tt h a ti m p r o p e rs e l e c t i o no fc a o l ic r y p t o s y s t e m s p a r a m e t e r sw i l ll e a dt os e c u r i t yp r o b l e m t h ea u t h o rg a v eap a r t i a lc r y p t a n a l y t i cm e t h o d t oa t t a c kc a o l ic r y p t o s y s t e m f i n a l l gan e wm a t r i xc r y p t o s y s t e mw a sb r o u g h tf o r w a r d i tw a nb a s e do nc a o l ic r y p t o s y s t e ma n dk n a p s a c kp r o b l e m k e y w o r d s ：p k i ；c r y p t o g r a p h y ；c a o l ip u b l i ck e ye r y p t o s y s t e m ；k n a p s a c ks y s t e m 1 1引言 自古以来，信息保密被广泛地关注。历史上的战争，对密码学理论和技术的 发展起了巨大的推动作用。1 9 4 9 年，ce s h a n n o n 发表了t h ec o m m l l n i c a t i o n t h e o r yo fs e c r e c ys y s t e m s ( “保密系统的通信理论) ；1 9 7 6 年，wd i f f l e 和 meh e l l m a n 发表了n e wd i r e c t i o n si nc r y p t o g r a p h y ( 密码学的新方向) ， 这两篇重要的论文标志着密码学的理论和技术的新变革。 从1 9 7 6 年之后，人们提出了许多公开密钥算法，其中许多是不安全的。 而那些被视为安全的算法有些却又不太实用，不是密钥太长，就是密文远大 于明文。只有不多的几个密码算法既安全又实用。在这些算法中，一些仅适用 于密钥分配，一些适用于加密，还有一些只是适用于数字签名。迄今为止，仅 有三种算法可同时很好的用于加密和数字签名：r s a ，e l g a m a l 和r a b i n 算 法。不过这些算法都比较的慢，以至于很难用于大量数据的加密。 近几年来，大量的公开密钥算法不断被提出又被破译，但是令人担忧的是 其中成熟的算法所依赖的数学基础很狭隘。在1 9 8 8 年，w h i t e f i e l dd i f f i e 指出 绝大多数的公开密钥算法都基于以下三种疑难闻题之一： 1 ，背包问题：给定一个互不相同的数组成的集合，找出一个集合其和为n 。 2 离散对数：如果p 是素数，g 和m 是整数，找出z 满足g 。；mm o dp 。 3 因子分解：设v 是两个素数的乘积，则 ( a ) a 分解礼。 ( b ) 给定整数m 和c ，寻找d 满足m “三cm o dn 。 ( c ) 给定整数z ，判定是否存在整数y 满足。三y 2 r o o d n 。 人们对于密码学基于如此狭窄的数学基础感到担忧。但是这种状况不能短 期内解决，因为并不是任意的n p 问题或难题都能够转化为一个密码系统。 c a o l i 公钥密码系统就是对新的方向的探讨，本文是在c a o l i 公钥密码系 统基础上的一次尝试和补充最早的c a o l i 公钥密码系统的原型首先出现在 文献1 1 中，是一个没有正式发表的密码系统，他的加密算法是计算一个二次 型的值，解密算法是利用中国剩余定理解一组二次同余式并进行一次线性变 换。这一公钥系统先后出现在文献f 5 ，6 j 中，后来l i m ( 文献f 2 ) 给出了此系统 的一个部分攻击方法。最后原来系统的作者和张彪合作破解了原有的原型， 并对最早的原型给出了修改形成了现在的c a o - l i 系统，具体见文献【3 3 。 在本文中，我们将指出对于c a o l i 系统参数的某些选择会造成系统的安 全问题，同时我们给出了一个改进方案。本文的安排如下：第二节中简要介 绍c a o l i 系统的原型及其发展；第三节介绍o r t h o n 的背包系统；第四节指出 c a o l i 系统的安全问题；第五节在基于c a o l i 系统和背包系统的基础上重新 构建了一个新的密码系统；第六节描述了一个简单的例子。 2 c a o l i 公开密钥系统的原型及其发展 2 1 c a o l i 系统的原型 c a o 一系统的原型出现在文献【1 1 中。他的加密算法是计算一个二次型的 值，解密算法是利用中国剩余定理解一组二次同余式并进行一次线性变换。 原型的具体算法表述如下： 1 公共参数选择 ( a ) 选取n 个不同的素数m “= 1 ，2 ，一，n ，其中m 。满足i3m o d 4 ； ( b ) 计算 m = i i m ，； z = 1 ( c ) 计算 尬= g z t i ，( i = 1 ，2 ，一，n ) ； ( d ) 对每个舰计算叫，满足心尬三1m o d 碱，0 叫 m ：，( i = 1 ，2 ，几) 记 a 。= 心舰，( i = 1 ，2 ，n ) 记对角阵为 以= a 1 0 0 儿 0 0 ( e ) 选取n 阶满秩的下三角阵p ，p7 ，其中p ，p 中的非零元均为正整数且小 精于 仁m 蜓i n 。 周， 卢2 。1 1 赢i ， d 为大于或等于l 的整数； ( f ) 令a = p 7 a p ，b = p a p ，； 2 公开密钥的选择：b ； 3 私钥的选择：只只，m 。，( i = l ，2 ，n ) ； 4 加密的过程：设明文为x = ( 研，z 。) ，0 3 7 ；d ，( i = 1 ，2 ，- ，n ) ，计算 c = x b x 7 ，c 即为密文； 5 解密的过程：令y = x 尸l 了1 p t ，则有c = 九玑2 ，于是有y 。2 = cm o dm 。，( i = 1 ，2 ，n ) 求出小于m ：2 的解叭，( i = 1 ，2 ，n ) ，然后计算x = y ( p 1 7 p r ) 1 明文。 上述原型仅仅是一个雏形，曹珍富、张彪在文献 3 中给出上述原型的完 全破译方案。在同一篇文献中作者对原型做出了重大修改，使之成为一个实 用的，成熟的算法。下面一小节就是介绍成熟的c a o l i 密码系统。 2 2 c a o l i 系统中用到的符号 1 选取n 个不同的素数m ；，i = 1 ，2 ，n ，其中m ，满足m 。三3r o o d4 ； 2 计算 m = i i m i ； 2 = 1 3 计算 眠= m m i ，( i = 1 ，2 ，n ) ； 4 对每个尬计算心，满足叫尬= 1m o dm ，0 d 2 e b ”+ p d 2 c m i , j i , 3z ，j g c d ( m ，曲) = 1 ， 记矩阵g = ( g i j j ， 9 玎= 叫( 6 ”+ p c i j ) m o d 7 ，( i ，j = l ，2 ，n ) 上述就是c a o l i 密码系统的主要结构和用到的一些符号。 3o r t o n 背包密码系统 3 1背包系统简介 为了弥补c a o l i 系统中的漏洞，我们在原来的算法基础上引入了背包算 法。先简要介绍背包系统。公开密钥的第一个算法就是由r a l p hm e r k l e 和m a r t i n h e l l m a n 开发的背包算法。背包算法的安全性是基于背包难题，它是一个n p 完全问题。对于背包问题的公式化描述如下： 给定一系列值尬，尬，螈和一个和s ，计算以使之满足s = 玩尬，其中 b 。的值可为0 或者1 。s c h r o e p p e l 和s h a m i r 在1 9 7 9 年给出了最快解背包问题方 法在2 n a 存储单元下，需要2 2 次试验。若背包向量a = ( o 。，o 。，a ”一，a 。) 满 足o ； ，i = l ，2 ，一，n 我们称之为超递增背包向量，相应的背包被称为简单 背包。简单背包是易于求解的。m e r k l e h e l l m a n 陷门背包是对简单背包进行伪 装，使得对所有其他人为一个难的背包，而对合法用户则为一个简单背包。 具体构造方法如下： 1 用户随机选择一个超递增序列a 。= a o ，。2 ，o 。0 ； 2 将其进行随机排列得到向量a7 = ( o ：，。：，o ：) ； 3 随机选择两个整数“和u 使得且 由e u c l i d e a n 算法可求出 g c d ( “，u ) = 1 ，0 ( 2 8 1 ) o ? 。 i = l ( c ) 私钥是由 o 。0 ，i = 1 ，2 ，n ； q 2p 。，l 2 。，( k = 1 ，2 ，一，r ) ； 组成。 3 公钥的产生： ( a ) 计算q 。= 矿q 。的整数部分；( 其实是先确定q t ，q 2 然后确定p 的) ( b ) 计算 o ：= o ? 。叫。r o o dp ，i = l ，2 ，- 一，n + 七一l ，k = 1 ，2 ，一，r ； n ：+ k = 一p 2 ，k = 1 ，2 ，一，r 一1 ； ( c ) 计算 ( d ) 计算 霄= 2 8 。( 2 l a ? 2 p r e c ( k ) p 2 j ，i = 1 ，2 ，n + k i ，k = 1 ，2 ，r ( e ) 计算 a i ，j = o ；r o o d ，i = 1 ，2 ，n + 一l ，j = 1 ，2 ( f ) 公钥部分是由 q l ，p r e c ( k ) ； 啦，j ，z = l ，2 ，一，n + 一l ，21 ，2 ； 以及落在2 一e c ( k f o ，2 即。( 2 ) 之间的有理数疗组成。 4 加密算法： ( a ) 对于用户的任何一条明文信息轧，z 。 0 ，2 5 ) ( b ) 计算 x n + fl 孔芹j ，k = l ，2 ，r ； 6 = k p dc g 足 满 e ( c ) 计算 l = z 胁，1r o o dq l ； t = l ( d ) 计算 y 2 = x i a i ，l ； ；= l ( e ) 密文就是，g 。 5 解密算法： ( a ) 利用中国剩余定理求解方程组 y 7 三玑r o o d 吼( j = i ，2 ) 得到 y = q 2 ( ( 2 一yl ) q 2 1m o dq l + 2 ) ( b ) 计算 。= ( 叫k - i ) r o o d p ，= r ，r 一1 ，1 ( c ) 求解方程 x i a 譬y o z = l 由于。? ( 2 s 一1 ) 掣n 0 ，利用超递增性原方程易求解。 4 对c a o l i 密码系统的安全性分析 4 1结论：当c a o l i 密码系统中的u d 2 时，系统是不安全的； 现在我们仅知道加密矩阵g ，以及假定u d 2 切+ p d 2 勺，则有+ p 勺 m 所以当u 扩时，得到 2 i jz ，j 7 u 他j + p c i j ) m ，( 1 ) 由( 1 ) 式我们得到 夕z j = u ( 6 ”+ p c ”) ，( 2 ) 接着我们估计u 。求鳓，i ，j = 1 ，2 ，n 的最大公因子，记求出的最大公因子 为u 。由上述方程组( 2 ) 可以看出原有系统中的“必定是“。的因子或者u 。 本身。把u 。的因子按从大到小的顺序记为比现在我们先假定找到的 u 。即为“本身，然后将它带入运算，通过后面的验证性工作我们可以知道u 。 是否即我们所找的u 。如果不是，回到这一步，将u 。代入运算，依次下去必 可找到真正的u 。 先假定找到的“。即为“，本身，我们可以修改g ，得到 g = b i j + p c i j ( 3 ) 第二步是为了估计p 先取向量”。除了z ，j 两个位置上的的元素，其他元素都为0 ，在m a x ( ，7 ) 的位置上的元素为一l ，另外一个元素为l 。再取向量”0 ，( i ，j ) 两个元素上都 为一1 ，其他位置上的元素为0 。将对应的和”0 带入运算”。g7 ”：j 。例如取 地和v l 。，带入运算得到 k 1 2 = y 2 g 。 ：2 = - ( b l l + p c l t ) + ( b 2 2 + p c 2 2 ) 一( b 1 2 + p c l 2 ) + ( b 2 1 + p c 2 1 ) = 一( 6 u + p c l l ) + ( 6 2 2 + p c 2 2 ) 一p c l 2 + p c 2 1 ， 由矩阵b 的构造我们可以知道矩阵b 为对称矩阵 记 k i 2 = k 1 2 一( b l i + p c l l ) + ( b 2 2 + p c 2 2 ) = 一p c l 2 + p c 2 1 ， ( 4 ) 象这样可以得到类似方程( 3 ) 的方程共有n ( n 一1 ) 2 个，这里i j ，记这些方程 为 七：，= 七”一( 6 十p c ，。) + ( b j + p c 3 3 ) = p c i j + p c j i ， ( 5 ) 然后求这；n ( n + 1 ) 个刍的最大公因子，设为p o 。按照方程原密码系统中的p 必然是p 。或者是它的因子。我们先假定就是p o ，带入g4 ，求出6 。 接下来验证求出的屹是否即为所求b i j 验证的过程就是随机产生几个消 息，用g 加密后得到密文，用我们求出的u ，b q 解密看是否能解出明文，如果 8 可以那么原系统已被破解，如果不行，那么回到第二步将p 。的因子一个个试 过去，如果他们中每一个都不对，回到第一步，对u 。的小于d 。的因子依7 欠按 以上步骤进行运算，直至破解出原系统。 5 对c a o l i 密码系统的修改 原有c a o l i 密码系统由于其参数的不当选择会导致原有系统的安全性问 题，且相对而言原有系统的公钥长度过长。新的算法是在原有c a o l i 密码系 统的基础上混合利用了背包系统的密码系统。新的系统减少了密钥长度并且 防止了原来的参数选择不当造成的问题。在新的系统中我们用到了o r t o n 背 包，( 现在还有许多背包系统，它们都可以用来替换我系统中的o r t o n 背包) 。 密码算法的描述分为三个部分 5 1第部分：用户a 的密钥选择 本系统中的密钥选择就是利用了o r t o n 背包系统中的秘钥选择 1 公共参数选择：首先确定背包向量的维数是佗，r 是要产生密钥需要经过 的迭代次数，8 是背包向量每个分量表示成二进制数时的最大位数。 2 私钥的产生： ( a ) 选择n 个数 n ，0 ，i = 1 ，2 ，一，n 且满足 0 0 _ 1 ，o ( 2 5 1 ) 。? ； 2 = l ( b ) 一些非负整数q 2 ，p 。，t o ，k = 1 ，2 ，r ； ( c ) 私钥是由 a p ，i = 1 ，2 ，一，n ； q 2 ，p ，( k = 1 ，2 ，r ) ； 组成。 3 公钥的产生： ( a ) 计算q 1 - 矿啦( 其实是先确定q t ，q 2 再确定p 的) ( b ) 计算 a = o ? 1 1 1 1 1 m o dp 2 ，i = l ，2 ，n + k 一1 ，k = i ，2 ，- ，r 9 n 7 k l + = 一p 2 ，k = 1 ，2 ，r 一1 ( c ) 计算 p r e c ( k ) = s + l 0 9 2 n + k + 2 ； ( d ) d 计算 ：2 - p r e c ( 2 l o ? 2 p r e c ( 。1 p 2 j ，i = l ，2 ，t t + k 一1 ，k = 1 ，2 ，r ； ( e ) 计算 a i ，j = a ；m o dq j ，i = 1 ，2 ，一，n 十一l ，j = l ，2 ； ( f ) f 公钥部分是由 玑，p r e c ( k ) ； a i i = 1 ，2 ，n + 一1 ，j = l ，2 ； 以及落在2 一”( 2 【o ，2 p ”。( 。) 之间的有理数劈组成。 5 2第二部分：加密算法的主体部分 这里假设用户b 想要发消息给用户a 1 与c a o l i 系统类似，用户a 先作如下步骤 选取n + 1 个不同的素数m 一= 1 ，2 ，礼+ 1 ，其中m 。满足m ；三3 r o o d4 ； 选取d q 1 ； 选取卢= l m i o ，注意这儿的m 。必须选的比较大，才不至于使 找到的卢较小； 计算 m = i i m 。； 计算 尬= m t l i ，( i = 1 ，2 ，n ，n + i ) ； 对每个尬计算心，满足删三1r o o dm 。0 d 2 e b 。j + p d 2 c ：j ，g c d ( 阮，u ) = l 利 用矩阵c ，p ，u ，虢构造矩阵g ，9 ”= u ( b + p c ：，) r o o d 虢，( i ，j = 1 ，2 ，n + 1 ) ； 2 记矩阵g 的第一，二两行中元素的最大值为t ，构造矩阵g7 如下 f 丁t 一- - ，9 。1 ，, ，i ；一- ，9 。l ，, 。2 ：；一- - ，q 。l 。, n + + 。i g = l。 ijjjj 3 构造矩阵 g ”= 丁t 丁t 9 3 ，l卯，2 t t 9 3 ，n + 1 4 用户a 再任意选取一个非奇异矩阵，记为l = ( 2 。) ，用户a 计算z 。= g “l ， 然后将乙传给用户b ； 5 用户b 收到乙，用户b 也任意选取一个非奇异矩阵彤，计算z 。= w z o ，然 黾豫产b 祷z 1 谩递绘甩户吣 6 用户a 收到z 。，计算互= z 。l ，然后用户a 将乙传递给用户b ； 7 用户b 收到乙，计算乙= w _ 1 乙= w 1 z 。l “= w 1 w z o l - 1 = w 1 w g “l l “ g “我们的明文空间是指分量数值不超过d 的n + l 维向量。上述方式类似 于e 1 g a m a l 密码系统具体文献 4 ，7 ，8 ； 8 与上述的传送方式类似用户a 将矩阵g 传送给用户b ； 9 用户利用矩阵g 和矩阵g “求出矩阵g 1 0 记用户b 想要传送的第一条消息的编码形式为x o = z 。o ，x 2 0 ，o ，用户b 随机选择一个向量y o = ( 0 。m 目2 ，o ，氓o ) ，帅为【0 ，2 。) n 【0 ，d ) 之间的整数； i l 用户b 利用用户a 的公开密钥( 利用o r t o n 密码的加密方式) 加密k ，得到 的结果记为z 。扎。和z n + 2 ，o ； 1 2 用户b 构造向量w o o = 2 3 l0 十1 ，0 x 2 0 + 可2 ，0 1 3 用户b 计算s o = ( z io ，z ；旷一，z ；t + t , 0 ) g 。妒 z 2 。 ； z ：、o z ：+ z 。 x l ，。、 z ：。 z n , 0 ， z n + 10 1 4 用户b 将s o 和z 。+ 2 0 传给用户a ； 1 5 如果用户在一条消息中就传送完所有信息，那么加密过程就此结束，如果 还有后续消息，那么按如下处理； 1 6 记用户b 想要传送的消息为x 。= ( x ，3 6 2 。，x n , i ) ，其中i 1 用户b 再选 取相应的随机向量x = ( y h ，y 。一，。) ，用户b 利用用户a 的公开密钥加 密k ，得到的结果记为x 。和x 。作为消息的第n + 1 ，n + 2 个分量那么 用户b 构造出向量 x i = 肌，l ox l ，t i + y l ，i 0 2 z0 0 2 t _ + 2 ，2 1 7 最后用户b 计算s ，= x i g x i7 ，然后将s 。z n + 2 。其中i21 传给用户a 。到这 里加密算法就结束了 5 3 第三部分：解密算法的主体： 1 用户a 收到的第一条消息z 。托o 2 用户a 计算w 一1s or o o d 跣= s o ，1 ，然后他再计算s o ，1r o o d p = s o ，o 1 2 3 用户a 再求解方程组 小于粤的解玑，o 4 计算 5 求解方程组 得到 6 计算 7 求解方程组 i ois o ，or o o dm 。，i = 0 ，1 ，2 ，一，n + 1 = p il p 一1 l ，0 2 ，0 可n + t ，0 t 71x n “or o o dq 1 t jx n + 20m o d q 2 t k = t k ( 训。一1 ) m o dp ，= r ，r 一1 ，1 利用超递增序列的性质 8 计算 n y i a 净矿 l = l 把随机向量y 求出 y t ，i ， 2 i 注意现在维数是n 维 9 由于第一条消息和后面的消息的加密方式不同，所以解密时也有些不同 上面的步骤是一样的，下面有些不同，第一条消息已经收到。把上面求解 出的第一条原文记为 e n ，0 1 0 用户a 收到密文s i ) z n + 。，。我们用i 纪录密文到达的先后顺序； 1 1 同前n - - 样n 户a 计算叫一。乱m o d 泥= 5 ，然后他再计算8 i , - m o dp = 8 佃 1 3 1 2 用户a 再求解方程组 小于孕的解协，。 1 4 求解方程组 鳐。；8 i , or o o dm ，= o ，l ，2 ， ，n + l ：p _ 1 p i y 2 y n + 得到 t 7 = 啦( ( z 。+ 2 j z ：+ 1 。) 啦一。r o o dq l + z 。+ 2 p ) 1 5 计算 1 6 求解方程组 利用超递增序列的性质 1 7 计算 n 舭譬t o 2 = 1 把随机向量l ，求出 l i y 2 i t i 注意现在维数是n 维 1 8 我们已经知道前一条消息的原文记为 e l i c 2 ，2 ： e n ，2 得到的 1 4 即为第i 条原文。 一 一 一 j 一 二 谢j彬朋jj加 1 2 z z o o 一 一吼眈 5 4 算法正确性说明如下： 就第一条消息作证明由于 有 = c o ( b 1 1 ，j + p c ) z ：，o z ：，o r o o d 瓣 z ，j u 一1 8 0 = ( 6 ”+ p q ，j ) x l ，o z ；，or o o d 跪 i ，j 所以0 2 - 1 s or o o dp = ( 6 。，j ) x l ，o z j ，om o dp 得到 2 j c o = ( z j 小z ；肼，z j 扎o ) b 记 q l ，0 q 2 ，0 q n + 1 ，0 = ( pp 1 ) = ( z i ，o ，z ：，o ，z ：+ 。，o ) ( p p i ) 丁1 ( p 尸。) z 1 , 0 x 2 ，0 ： ， z n + - 10 贝0 有c oja l q o + a 2 q ；，o + + a 。+ 1 q i “，o 所以 蟊；c 。r o o dm 。( z = 1 ，2 ，n ) 。由于n + l 阶满秩的下三角阵p ，一其中j d ，p 中的非零元均为正整数且小于等于 仁螺l r 丽 得到q 印；坐笋口2sm i n 等，所以可求出方程组 妃三8 i , om o d 叻，j = l ，2 小于鱼2 的解q 。由于下三角阵p ，p 。可逆，故 = p 1 p _ 1 1 5 0 0 o lg，吼，0 0 0 l k 乏 十 z z n z 获得原文。 这是第一条消息的解密方式，后面的消息仅仅多做一步异或运算即可获 得原文 6 一个具体的例子 这里举个例子取公共参数为r = 2 ，n = 2 ，s = 2 用户a 私钥的选择如下： 用户a 公钥的选择如下： 2 计算得到a j = 2 ，a 5 = 8 ，a = 一p 1 = 一1 9 3 计算得到f ? = o i 0 ，月= 0 4 2 4 计算得到a 2 _ i 0 ，a ；= 1 9 ，a ；= 1 0 6 计算得到gl ，2 = 3 ，a 2 ，2 = 5 ，a 3 ，2 = 3 这样用户a 的公钥即为o = 1 ，a 2 ，l = i ，a 3 ，l = 1 和a t , 2 = 3 ，a 2 ，2 = 5 ，a 3 ，2 = 3 加密的过程：( 这里我们假定通信双方是用户a 和用户b ) 2 取3 个不同的素数为m 1 = 1 9 ，7 t t 2 = 7 ，t r t 3 = i i 5 计算得到m i = l ，噬= 6 ，嵋= 1 6 构造对角阵 忙a 。| 3 ) ； 7 构造下三角阵 p = ( ；i ；) ； 8 构造下三角阵 9 计算得到矩阵a 为 i 0 计算得到矩阵b 为 1 1 取p = 5 6 6 1 1 矩阵c 为 尸 _ 4 = 1 2 5 41 3 3 1 2 5 40 o1 3 3 1 3 8 7 1 3 8 7 1 3 3 1 2 取m ：5 6 6 1 1 1 ，w 取为1 1 ，计算得到矩阵 g = 1 3t ：6 3 7 9 7 8 ，这样用户a 得到矩阵 1 5 2 5 7 6 3 7 9 7 8 1 4 6 3 3 3 3 3 3 3 6 3 7 9 7 8 6 3 7 9 7 8 6 3 7 9 7 8 3 戮男6 霉 1 4 同样用户a 得到矩阵 g = 6 2 1 8 7 4 6 2 2 7 2 i o 6 2 2 7 2 1 o 0 6 3 6 5 1 5 6 3 6 5 1 5 o 、0 o o 1 o 1 1 1 o o ，tl、 、，、，； 蝌删瑚 ，。 = d 蝌脚m ，flil、 = b 、 o o o 0 1 0 o o o ， 、 3 3 3| 星i 莹| 莹 、，、， ，。，。一 1 5 用户a 随机选择一个非奇异矩阵 1 6 用户a 计算得到矩阵 = ( i f 3 8 2 7 8 6 88 9 3 1 6 9 21 3 3 9 7 5 3 8 1 磊= | 3 8 2 7 8 6 8 8 9 3 1 6 9 21 3 3 9 7 5 3 8 8 7 7 8 2 0 4 8 23 0 7 2 3 1 7 用户b 收到矩阵z 0 ，也随机选择一个非奇异矩阵 1 8 用户b 计算得到矩阵 201 、 w ：l 35 1 i i3 7o 7 6 6 4 5 1 4 1 7 8 8 3 8 6 6 z ，= i3 0 6 3 1 7 2 27 1 4 7 4 0 1 8 3 8 2 7 8 6 8 08 9 3 1 6 9 2 0 1 9 用户a 收到矩阵z 。，计算得到 乙= ( 1 0 e + 0 0 6 ) l51 0 5 35 1 0 5 3 1 2 7 7 4 12 7 7 4 f 6 3 7 9 863 7 9 8 2 0 用户b 收到矩阵乙，计算得到z 3 = g “这样用户a 就将矩阵g ”顺利的传 送到用户b 手中，同理用户a 将矩阵g7 传送到用户b 的手中 2 1 利用矩阵g “和矩阵g ，用户b 很容易得到矩阵g 2 2 假设用户b 要传送的消息是( 1 ，1 ) ，他随机选择的干扰向量为( 1 ，0 ) 2 3 用户b 利用用户a 的公开密钥加密干扰向量( 1 ，0 ) 得到向量( 1 ，3 ) 2 4 用户b 利用矩阵g 加密向量( 2 ，l ，1 ) ，传给用户a 密文( 7 7 3 6 6 3 ，3 ) 解密的过程 i 耋啪渤 篇一 、， 似弘g ；卯m 钾 1 5 6 1 用户a 收到密文( 7 7 3 6 6 3 ，3 ) 后，计算得到c 1 = 1 5 4 3 9 4 * 7 7 3 6 6 3m o d5 6 6 1l l ： 7 0 3 3 3 2 在计算c o = 7 0 3 3 3m o d5 6 6 1 1 = 1 3 7 2 2 3 求解方程组得到( l ，。，蜘) = ( 2 ，1 ，1 ) 4 利用o r t h o n 的密钥求解( 1 ，3 ) 的原文，解密过程如下 5 2 = ( 1 ，3 ) r o o d ( 3 ，7 ) = ( 1 ，3 ) 6 f 2 = 7 ( ( 1 3 ) 1r o o d3 ) + 3 = 1 0 7 1 = 1 7 $ 1 0 r o o d2 1 = 2 8 g 。= i o 2m o d1 9 = l 9 z 2 = 1 4 = 0 1 0z l = 1 0 = i 1 1 这样就把干扰信息( i ，0 ) 先求解出来 参考文献 1 】曹珍富，李迎春一个矩阵覆盖公钥密码系统 捌，哈尔滨，哈尔滨工业大学研究报 告，1 9 9 1 ，1 - 3 7 。 2 】l i mlho nt h es e c u r i t y o ft h ec a o - l ip u b l i ck e yc r y p t o s y s t e m j i e e ee l e c t r o n i c s l e t t e r s ，1 9 9 8 ，3 4 ( 2 ) ，1 7 0 1 7 2 3 】张彪，曹珍富关于c a o l i 公钥密码系统的分析与修改m ，计算机学报，1 8 9 1 9 5 4 】d i n gc ，p e id ，s a l o m a aa c h i n e s er e m a i n d e rt h e o r e m ：a p p l i c a t i o n si nc o m p u t i n g ，c o d i n g ，c r y p t o g r a p h y m 】，s i n g a p o r e