（应用数学专业论文）密码学中两个问题的研究.pdf

a b s t r a c t i nt h i sp a p e r s o m ep r o b l e m sa b o u tc r y p t o g r a p h ya r ed i s c u s s e d f i r s t l yw ed i s c u s s e dt h ek e y a g r e e m e n tp r o t o c o l sk e ya g r e e m e n tp r o t o c o lo rm e c h a n i s m i sa k e ye s t a b l i s h m e n tt e c h n i q u e si n w h i c has h a r e ds e c r e ti sd e r i v e db yt w o ( o rm o r e lp a r t i e sa saf u n c t i o no fi n f o r m a t i o nc o n t r i b u t e d b y o ra s s o c i a t e dw i t h e a c ho ft h e s e ，( i d e a l l y ) s u c ht h a tn op a r t yc a np r e d e t e r m i n et h er e s u l t i n g v a l u ew e p r e s e n ts o m ep r o t o c o l ss u c ha sk e yd i s t r i b u t i o ns y s t e m d i f f i e - h e l l m a np r o t o c o le t c t h e nw ea n a l y z eak e ya g r e e m e n ts c h e m eb a s e do nt h em - pi n v e r s eo fm a t r i xo v e rf i n i t ef i e l d w h i l ed i s c u s s i n gt h ek e ya g r e e m e n ts c h e m eb a s e do nt h eg e n e r a l i z e di n v e r s eo fm a t r i x ，w e l i n dt h e r ea r es o m eq u e s t i o n sa b o u tt h em o o r e p e n r o s eg e n e r a l i z e di n v e r s eo fm a t r i xo v e rf i n i t e f i e l d an e c e s s a r ya n ds u f f i c i e n tc o n d i t i o nf o ra nmxnm a t r i xao v e rf 口h a v i n ga nm pi n v e r s e w a sg i v e ni n n i no u rp a p e rf u r t h e rn e c e s s a r ya n ds u f f i c i e n tc o n d i t i o n sa r eo b t a i n e d ，w h i c h m a l ( ec l e a rt h es e to fn 2 nm a t r i c e so v e r 凡o fr a n kra n dh a v i n ga nm - pi n v e r s e ，w h i c hi sm p i n v e r t i b l ei sa l s og i v e na n dt h ec o n s t r u c t i o np r o b l e ma n dt h ee n u m e r a t i o np r o b l e ma r es o l v e d t h o r o u g h l yb yb o r r o w i n gr e s u l t si ng e o m e t r yo fc l a s s i c a lg r o u p so v e rf i n i t ef i e l d s s e c o n d l y ，i n1 9 7 6 d i f f i ea n dh e l l m a ni n v e n t e dt h ec o n c e p to fp u b l i c k e yc r y p t o g r a p h y 【3 0 s i n c et h e n ，s e v e r a lp u b l i c k e ye r y p t o s y s t e m sb a s e do nj u s to n eh a r dp r o b l e mh a v eb e e np r o p o s e d i ft h e s ec r y p t o g r a p h i ca s s u m p t i o n sb e c o m ee a s yt os o l v e ，t h ec o r r e s p o n d i n gc r y p t o s y s t e mw i f l n ol o n g e rb es e c u r e h o w e v e r ，i ti sv e r yu n l i k e l yt h a tm u l t i p l ec r y p t o g r a p h i ca s s u m p t i o n sw o u l d s i m u l t a n e o u s l yb e c o m ee a s yt os o l v e t h u ss e v e r a lc r y p t o g r a p h i cs y s t e m st r yt ob a s e dt h e i r s e c u r i t yo ns o l v i n gm u l t i p l eh a r dp r o b l e m ss i m u l t a n e o u s l ys oa st oe n h a n c es e c u r i t y i nt h i s p a p e rw ea n a l y z es o m ed i g i t a ls i g n a t u r es c h e m e sb a s e do nt w oh a r dp r o b l e m s ：f a c t o r i s a t i o na n d d i s c r e t el o g a r i t h mp r o b l e m a n dg i v et w ot y p es i g n a t u r es c h e m e s f i n a l l y ，n o w a d a y s ，i n s l ys e c u r es y s t e m sa j l o wp e o p l et oc h o o s et h e i ro w np a s s w o r d s ，b u t th o s ep e o p l et e n dt oc h o o s ep a w o r d st h a tc a nb ee a s i l yr e m e m b e r e da n dg u e s s e d ，s u c ha st h e i r n a m e b i r t h d a yo ro t h e rr e c o g n i z a b l ew o r d st h i sw e a k n e s se x i s t si np r a c t i c a l l ya l lw i d e l yu s e d s y s t e m s m l dm a k e st h es y s t e mv u l n e r a b l et o ”d i c t i o n a r ya t t a c k ”i nt h i sp a p e rw ed i s c u s ss o m e p r o t o c o l ss u c ha se n c r y p t e dk e ye x c h a n g ea n ds t r o n gp a s s w o r d o n l ye n c r y p t e dk e ye x c h a n g et h a t m a i n t a i nb o t hu s e r sc o n v e n i e n c ea n dah i g hl e v e lo fs e c u r i t ya tt h es a m et i m e t h eb a s i ci d e a i st oe n s u r et h a td a t aa v a i l a b l et ot h ea t t a c k e ri ss u f f i c i e n t l yu n p r e d i c t a b l et op r e v e n ta no f f - l i n e v e r i f i c a t i o no fw h e t h e ra g u e s si ss u c c e s s f u lo rn o t k e y w o r d ：k e ya g r e e m e n tp r o t o c o l ，m - pg e n e r a l i z e di n v e r s eo fm a t r i xo v e rf i n i t e f i e l d d i g i t a ls i g n a t u r es c h e m e d i c t i o n a r ya t t a c k 感谢 特别感谢我的导师戴宗铎教授在北京三年的研究生阶段的学习和生活中戴 老师给予我充分的理解、关怀和指导! 从她身上我学到的不仅是本专业的理论知 识，更重要的是那种严谨求实的治学精神，而这些都会让我们年青的一代获益匪 浅 感谢翟启滨教授，杨君辉教授、裴定一教授在三年中在学习和研究中的指导 特别是翟老师的讨论班和基础课使我真正了解到数学和密码学的密切关系 感谢戴英侠教授在学习和生活上的关心! 感谢赵战生教授、冯登国教授、吕述 望教授、刘振华教授、荆继武教授和张实老师在各方面的支持! 感谢韩老师和徐老 师等实验室的各位工作人员! 感谢蒋绍权董军武等同学。通过和他们的讨论，特别是许多学术问题的讨论 中，使我对密码学方向有了更进一步的理解，这些对我的过去学习生活和将来的 研究都有着十分重要的意义同时感谢实验室的各位同学、特别是9 7 级的各位同 学在平时生活中的热心帮助 感谢所有关心和支持我的人 中国科学技术大学硕士学位论文 前言 论文第一章介绍了一些密钥协同方案( k e ya g r e e m e n ts c h e m e ) 并分析了一种基 于有限域上、卜p 广义可逆矩阵的密钥协同方案；在第二章我们进一步研究了有 限域上m p 广义可逆矩阵的判定，分类、构作和计数等同题，并给出了彻底的 解决 第三章我们主要分析了两个已有的数字签名方案，指出它们的安全性并非 同时得到两个数学难题的保障同时我们构造了两类签名方案并分析说明它们 的安全性是同时得到两个数学难题的保障的 在第四章我们讨论了密码( 口令) 应用中一个十分普遍的问题：字典攻击 我们讨论了能够进行字典攻击的条件。并介绍了一些能够抵御字典攻击的密码 协议的最新进展 一，基于矩阵广义逆的密钥协同方案的分析 当我们对一个系统或协议进行分析时，总假设一个密码系统的安全性取决 于对密钥的保护，而不是对系统或硬件本身的保护密钥管理包括密钥的产生、 存储、装入、分配、保护、丢失、销毁以及保密等内容密钥协同方案是密钥管 理的一个方面 本文第一章简要介绍了一些密钥协同方案。如基于私钥体制的一些密钥协 同方案；基于公钥体制的d i f f i e h e l l m a n 方案，端端方案。m t i 方案等。并在最 后介绍了一种基于矩阵广义逆的密钥协同方案我们分析了此方案，并由此引 出了第二章关于有限域上矩阵的m p 广义逆的一系列问题的研究 ：、有限域上矩阵的m p 广义逆的分类、构造与计数 矩阵广义逆的概念渊源于线性方程组的求解问题设实数域中任意一个g r n 矩阵 ，p e n r o s e ( 1 9 5 5 ) 把满足下面四个方程的矩阵y 定义为 的广义逆： a x a = a ( i ) x a x = x ( i l ) ( x a ) 7 = x a ( i 1 1 ) l a x ) = a x ( j v ) 其中 7 表示 的转置矩阵( 如果在复数域上定义，则a r 表示a 的共轭转置矩 中国科学技术大学硕士学位论文 阵) t e n r o s e ( 1 0 5 5 ) 证明了，满足上面四个方程的矩阵y 是唯一的然而更早些时 候，m o o r e ( 1 9 2 0 1 9 3 5 ) 用另外一种等价形式定义了这种广义逆后来人们就把上 述方程组定义的广义逆称为m o o r e 。p e n r o s e 广义逆( m p 广义逆) ，简记为 + ，而 把上述四个方程统称为p e n r o s e 方程至今，广义逆矩阵的理论和计算方法的研 究已经取得了长足的进展，并在概率统计、数学规划、数值分析、控制论，博奕 论和网络理论等领域得到不同程度的应用 现有的大多数结果都是建立在实数域或者复数域上，但是在有限域上这些 结果并不一定成立例如，在实数域上任意的矩阵- 都有m p 广义逆，但是在 有限域的情况下，矩阵4 则不一定具有m p 广义逆。如凡上的矩阵 b ( i ni n ) ， ( 1 ) 就不存在相应的矩阵、r 满足p e n r o s e 方程我们定义有限域f 上的矩阵a 是m p 广 义可逆的如果存在、满足p e n r o s e 方程 本文主要给出了以下的结果 1 有限域上矩阵m p 广义可逆的便于应用的判定条件； 2 将m p 广义可逆阵的构作与计数问题归结为有限域上有关典型群几何中非 奇异子空间的构作与计数问题； 3 利用有关典型群几何中非奇异子空间分类与计数的结果完全解决了m p 广 义可逆阵的构作与计数问题 三、基于两个数学难题的数字签名方案 熟知的一些公钥密码系统的安全性都是基于某个经典的数学难题，例如r s a 的安全性是基于大数分解问题( f p ) ；而d i i f i e h e l l m a a 密钥交换系统，e i g a m a l 体 制，d s a 签名系统，椭圆益线密码系统等都是基于离散对数问题( d l p ) 基于两 个难题的公钥密码系统是指系统的安全性得到两个难题的支持。即使其中一个 问题得到解决，只要另外一个问题仍然是难以解决的，系统的安全性仍能得到 保证 本文分析了一些基于大数分解闯题和离散对效问题的数字签名方案，同时 我们给出了两类基于两个数学难题并且具有信息恢复功能的签名方案 四、可抵御字典攻击的可验证密钥交换协议 密码( 口令) 在安全系统中起着非常重要的作用，它的一个主要应用是验证 中国科学技术大学硕士学位论文 用户的身份在现在的许多系统中允许用户自己选取密码，可是一般的用户习 惯于选取容易记忆、容易猜测的的密码，例如用户的姓名，相关的数字等等， 这样就产生了字典攻击的方法近年来许多密码学家对字典攻击进行了分析， 并构造了一些安全的协议来抵御在线字典攻击，例如：基于密码的可验证密钥 交换协议近期i e e e1 3 6 3 研究小组( p 1 3 6 3s t u d yg r o u p 也开始制定基于密码的 可验证密钥交换协议的标准本文主要对可验证密钥交换协议的最新进展进行 了调研，并希望进行进一步的研究 第一章基于矩阵广义逆的密钥协同方案的分析 密钥协同方案( 密钥协定) 是两个或多个成员通过交互的通信在一个公开的 信道上联合地建立一个用于将来会话的密钥的协议 1 0 基于私钥和公钥体制。 我们都可以构造密钥协同方案，我们首先介绍一些已有的密钥协同方案，最后 我们分析了一种基于有限域上矩阵广义逆的密钥协同方案 1 1 密钥协同方案 1 1 1基于私钥体制的密钥协同方案 依赖于密钥分配中心的密钥协同方案 此协议假设用户 b 和密钥分配中心( k d c ) 共享一个秘密密钥在协议 初始化时，用户和密钥中心通过由密钥中心分发或者密钥中心和用户共同生成 等方法产生一个共享密钥当用户4 ，b 需要生成会话密钥进行通信时，他们进 行以下步骤： 1 1 发送信息给密钥中心，请求一个与b 通信的会话密钥 2 密钥中心产生一随机会话密钥“，并对它的两个副本加密：一个用 的密 钥，另一个用b 的密钥加密并发送这两个副本给t ：1 对他的会话密钥的副本解密，并将用用户b 的密钥加密后的会话密钥的 副本发送给用户b 4 b 对他的会话密钥的副本解密 至此用户i b 拥有了一个有密钥中心产生的会话密钥凡这个协议依赖于密钥 中心的绝对安全与可靠性如果入侵者破坏了密钥中心，整个网络都会遭受损 害当入侵者获得了密钥中心与每个用户共享的所有秘密密钥；他可以读所有 过去和将来的通信业务他所做的事情就是对通信线路进行搭线窃听，并监视 加密的报文业务这个系统的另外一个问题是密钥中心可能会成为瓶颈他必 须参与每一次密钥交换。如果密钥中心出了同题。整个系统就会被破坏 密钥分配系统( k e yd i s t r i b u t i o ns y s t e m ) 另一种基于私钥体制的密钥协同方案减少了对密钥中心的依赖性，只要 求在初始化阶段密钥中心的参与，这种方案称为密钥分配系统( k e yd i s t r i b u t i o n s y s t e m ) 。此种方法在系统初始化阶段由密钥中心产生并分发给每一个用户一些 4 1j 密钥协同方案 秘密的信息，使得任何一对用户可以产生其它用户不知遭的共享密钥直接的 方法( 平凡) 是密钥中心为每一对用户产生密钥并分发给此两用户，这样一个 用户就应该存储有n 一1 个密钥这种方法是十分安全的，任何别的用户以及外 部的入侵者都无法获得别的两用户之间的共享密钥但考虑到这种方法需要存 储很多的信息，我们可以采取其他的方法牺牲一些安全性来减少用户存储的 信息 定义1 1 一个 。d s 称为是j 安全的如果任意给定了一对用户t ，b 。其它用户中 j 个或少于j 个用户联合起来，利用所有的密钥中心给他们的与密钥有关的信 息，也不能得到关于用户4 ，b 的共享密钥的任何信息 任何j 一安全的密钥分配系统( k d s ) ，如果两用户间的共享密钥为m 比特， 则每一用户存储的信息至少为m + ( j + i ) 比特上述平凡的方法是j = n 一2 的特 殊情况此时用户存储的信息为m + ( n 一2 + 1 ) 比特 b i o t a 密钥预分配系统是一种达到了上述信息论下界的密钥分配系统“ ”一2 ) 系统不褥要交互过程。用户只需要有一个唯一的索引值i ，1s i sn ，利 用密钥中心分配给用户的一个与密钥有关的向量以及公开的信息。用户i 与用 户可以产生共享密钥k 。 系统在初始化时密钥中心通过如下步骤给每个用户分发信息： l 公开一个有限域r 上的( n ，i ) 极大距离可分码( m d s ) 的生成矩阵g m ( q ) 2 随机产生一个凡上的k 女的对称矩阵d ：；计算分发给每个用户的与密钥有关的向量s 。( 1 isn ) s 为n k 矩阵s = ( o c ) 7 的第i 行 用户i 通过如下步骤计算计算与用户j 的共享密钥“。= j 利用s 与g 的第j 列，可以计算n n 对称矩阵k = ( d g ) r g 的第( i ，j ) 个分量，记为k 。，；用 户可以利用s 与g 的第i 计算对称矩阵k = ( d g ) 7 g 的第( ，z ) 个分量，记为 k j i = k 1 j 这种密钥预分配系统起源于线性纠错码的概念，关于极大距离可分码m d s 和密钥预分配系统的详细情况可以查阅有关书籍 中国科学技术大学硕士学位论文 下面我们介绍一些基于公钥体制的密钥协同方案众所周知的一个基于公 钥的密钥协同方案是d i f l i e h e l l m a n 密钥交换协议假设p 是一个大素数，g 为昂 的一个本原元( 阶数很大的元素) ，p 和g 是公开的d i f f i e h e l l m a n 协议是通过 如下的步骤在两个用户之间建立密钥 1 用户 随机选择几，0sr p 一2 计算9 8 - ( r o o dp ) 并发送给用户b 2 用户b 随机选择r 日，0sr 8 p 一2 计算g a e ( r o o dp ) 并发送给用户4 3 用户i 计算k = ( 9 8 e ) “，用户b 计算k = ( 9 8 一) 舶 上面方案容易受到一个主动攻击者进行的中间入侵( i n t r u d e r i n m i d d l e ) 攻击 的方法为：主动攻击者截取用户4 发送给b 的口n ，换之以f 8 j 而把b 发给 的g l i b 换成g “这样，用户a ，w 之间建立了秘密密钥g r a r ；用户b ，w 之间建 立了秘密密钥9 8 j r 。 为了克服中间入侵，必需要求用户a ，b 之间进行交换密钥时能通过某个步骤 或协议来确认对方的身份有些密钥协同方案能自己认证参与者的身份，这种方 案称为认证密钥协同方案例如d i t t i e h e l l m a n 方案的一个的简单变形为：e i g a m a t 密钥协同方案，此种方案在初始化时用户首先随机选择一个整数0 茎nsp 一2 ，计 算f a 并公开( p m 9 a ) 为其公钥，而保留n 为其私钥当用户 需要和用户b 产生 秘密密钥时，他首先获得用户8 的公钥( p 涵g a ) ，随机产生整数l tsp 一2 ，并把 矿( m o dp ) 发送给用户则他们都可以计算出= g 一这种方案是单方验证的 下面我们介绍另外几种密钥协同方案，其安全都是基于d i f l l e h e l l m a n 问题， 既给出一个域r 上的大阶元g 在只知道旷，矿的情况下难以求出9 ” 1 1 2 端- 端协议( s t a t i o n t o - s t a t i o n ) 端端协议对d i f f i e h e l l m a n 协议进行了一些修改。具体方案如下 设e 是一个公开的加密算法。用户a ，b 有各自的签名算法s i g 一，s 匆a 和签名 验证算法i e e r a 系统的公开参效为一个大素数p 以及乙的一个本原元g 两用户可以通过如下的步骤建立共享的密钥； l 用户。4 随机选取r ，1 z p 一1 ，计算矿( m o dp ) ，并发送给用户b 2 用户b 随机选取y ，l y p i ，计算共享的密钥i = ( 旷) ”= g ”( r o o dp ) 并 把g y ( r o o dp ) 与e k ( s i g s ( g ，g t ) ) 传送给用户4 3 用户4 计算= ( ) 。( r o o dp ) ，并用其解出s 讪( g p 扩) 然后利用v e r b 验 证其是否为用户b 对( 扩，旷) 的签名如果不正确，则终止密钥建立过程 否则，一接受女为与用户b 建立的共享密钥。并发送类似的加密后的签名 5 jj 密钥协同方案 “( s i g ( g 。，) ) 给用户日 4 用户b 利用解出s 协旷，口v ) ，验证后如果正确则认为与用户4 建立了共享 的密钥k s t s 协议在步骤( 3 ) 和( 4 ) 中要对签名进行验证，中间入侵者若要进行攻击， 必须伪造出用户口对( g v ，旷) 或( 旷，矿) 的签名，而签名方案的一个性质就是不 能伪造，这样就可以避免中间入侵 1 1 3m t i 密钥协同方案 m a t s u m o t o t a k a s h i m a 和i m a i 等通过修改d i f t i e h e l l m a n 密钥交换协议构造了另 外一系列的密钥交换协议，我们将这些协议统称为m t i 密钥交换协议于s t s 协议相比较，这是一些两段协议。同时，它们不需要用户之间运算任何签名就 能抵御中间入侵我们只详细介绍其中之一：m t i a o 系统的公开参数为一个大素数p 和一个生成元g 用户a 的秘密密钥为n ， 公开密钥为：。= g a ( r o o dp ) 同时用户b 的秘密密钥为p ，公开密钥为：日= 9 口 ( r o o d 纠他们通过如下步骤建立共享的密钥凡 1 用户4 随机选择z ，2sz 2 _ h 0 ：) ? 如果n 是偶敷。”= 2 v 0p 卜 0，u i v 一10 ，、，tn l k 7 = “吨a = ( ，0 ，：3 ) 6 1 = 如果n 兰l ( m o d4 ) 或q 三1 ( r o o d 4 如果n 三3 ( m o d4 ) 且口三3 ( r o o d 4 如果r l i0 ( m o d4 ) 或口三1 ( r o o d4 如果n 兰2 m o d4 ) 且q 三3 ( r o o d4 ) 证明：由上述引理知存在n n 可逆矩阵k 使得 哪7 = 岛t a = ( ，c 0 7 ：) 、i 吼。 0 l 0 ，jilii 2 中国科学技术大学硕士学位论文 其中，一2 ，+ 6 ，陋3 ) ：1 1 1 1 n 【1 ) ，或0 , o ) 或1 2 1o 卜，：为中的一个 【j一： 非平方元 考虑d 。，t ( s ) ：d e t ( ，、p ，、r ) = d e t ( ) 2 为一平方元令碍表示中平方 元的全体 当n 为奇数时，设n = 2 r + l 因为一1 曙当且仅当q 三1 ( m o d 4 ) 所以 d e t ( s 2 l 【i ) ) = ( 一1 ) 一碍当且仅当”p i0 ( r o o d2 ) 或q 三l ( r o o d 4 ) ”； d e t ( s 2 ，( ：) ) = 一1 ) 一：碍当且仅当“g 三3 ( m o d4 ) 且p i1 ( j n o d2 】”可见引 理中当，t 是奇数时的情形得证 n 是偶数时的情形可以类似地证明，只需注意到如果j = 0 ，d e t ( 5 2 川a ) = ( 一1 ) “；如果d = 2 ，贝0d e t ( s 2 。+ 6 ) = ( 一1 ) ”： 设r 为一“中的一个r 一维子空间，由【6 】可知r s 。“ar r 合同与以下四 种合同标准型之一： 0 ( h 2 j 一1 其中( ) 一：为阶为r 一2 s 一1 的零矩阵，且( j ，a ) 为下述四种类型之一：( 1 ，( 1 ) i ) ( i ( 。) ) 邶o ) 和( 2 f 1o 1 ) ，子空间r 可称为2 川中相对与正交群o d ( ，岛川。 0 - ： 的、，( - 2 s 十7 ，s ，r ) 类型的子空间 如果r s 2 。“。r r 合同于m ( r ，2 s + 1 ，s ，r ) ，则存在子空间r 的一个矩阵表示r ( r = b r 6 g l ，( ) ) 使得 丁s 2 p + 6 a t = m ( r ，2 s + 1 ，s ，i )( 28 】 子空间r 称为非迷向的当且仅当r 一2 s 一1 = 0 令尺。= r k ，注意到 r r 7 = r 一1 s 6 ( i , 7 ) 一1 r 7 = r k 一1 岛( 一) 7 r 7 = r l s 6 r ， 易知有以下引理 引理2 6 设n = 2 v + 6 ，且( 6 ，) 如引理中由n q 确定设r 为向量空1 ：1 硝“1 的 一个r 维子空间，令r i = r k 则下述条件等价： j 25 非奇异子空问与正交几何( p 2 7 子空间r 属于一2 ”6 ( r ； ) j 子空间r 非迷向 ，子空间r l 为一2 “+ 6 中相对于0 2 。( 晶) 的m ( n2 s + 1 ，s ，r ) 类型的子空间， 而且r = 2 s + 1 其中1 o ，1 ，2 ) ，且r = ( 1 ) 或( z ) ，如果1 = 1 ir = 0 如果7 = o i i _ f 1o 1 如果7 ：2 。一： 构造：根据定理构造，n n 的秩为r 的m 。p 可逆矩阵的问题简化为构造一2 “鲫( ) 中的子空间进一步可以简化为构造相对于o 。，“( r ) 的( n2 s + 7 ，s ，r ) 类型的子 空间其中r = 2 s + 1 ，7 和r 由上述引理确定更进一步可逆矩阵的构造问题可以 简化为构造矩阵丁满足等式( 28 ) 而在中，为了求出n ( r 2 s + 7 ，s ，r ：2 v + 6 ，) 的计算公式，即满足等式( 28 ) 的矩阵的数日，书中举出了一种构造满足等式( 2 8 ) 的方法，利用此方法我们就 可以构造所有的m n 的秩为r 的m p 可逆矩阵 计算( r 2 s + 7 ，s ，r ；2 p + 6 ，) 的公式，即相对于正交群o 6 ( ) 的( r 12 s + 7 ，s ，r ) 类型的向量子空间的个数可在【4 】中查到，有如下定理t 定理2 6 上2 v + 6 维正交几何中( 即相对于正交群0 2 。“( ) ) 中( m + 7 ，2 s - i - 1 ，s r 2 v + j ) 类型子空间的个数为： v ( m + 7 ，2 s + 7 ，s ，i ；2 v + 6 ，a ) 兀 ( q - 1 ) ( q “+ 1 ) = i 二二：i j 二：i i q 2 。( ”+ ) + ( 6 - - 卜1 ( ”一2 。一l m 一4 兀( q l _ 1 ) 兀( 口) 兀( q 一l n o ( m + 7 ，2 s + 1 ，s ，r ；2 v + j a ) 其中 2 s n j 卧s _ m 嘶一，0 ) ，如耜憾扛俩r _ i + s 一1 ，如果j = 1 = l 而r ； n o ( m + 1 ，2 s + 1 ，5 ，r ；2 u + 6 ，) = n o ( m ，2 s ，s ；2 v + 6 ，a ) = 1 ( ，+ 一1 ) 旷一，如果j = 0 ， ( r + 一1 ) q ，如果6 = i r a ， ( 旷+ + 1 ) 矿一，如果j = 1 ，r = a ， ( g ”+ + 1 + i ) ，如果j = 2 ； t 1 0 h n + 2 2 s + 2 5 2 v + d ，a 1 = 中国科学技术大学硕士学位论文 ( q 一+ 一l u ( q 一十1 i ) ( q 2 ( 】一? ) j 口果j = o ( 口。+ 卜m 一1 ) ( q 一+ + 1 ) ( q 2 i 卜) 口果j = 1 ( g r + + u ( q r + + 十1 ) ( 9 2 ( ) j 口果d = 2 定理2 7 ( 记数) 记有限域f q 上，n x n 的秩为r 的 f p 可逆矩阵的个数为i u ( ， ( r = ) 如j ，中定义设n = 2 p + d ( j ，) 如q l 理? 5 中由”和q 确定则我们有 2 - m ( ：r ：) i = i g l ，( f q ) l lf j ( r ：) i if ：州( r ： i 一2 “6 ( ) i j 扯”：u v ( 2 t ，2 s + 1 s ，r ，2 v + j3 ) 如果，_ 2 t ， le ，：l ；v ( 2 t + l ，2 t + 1 f ，( ) ：2 u + d ，- m ， 如果r = 2 t + 计算i f ；( h i 的公式类似 证明：第一个等式可由定理2 5 得到，第二个等式可由引理2 6 得到 2 6 非奇异子空间与伪辛群几何( p = 2 ) 本节设为特征为2 的有限域与上一节类似，上的r n n 的秩为r 的 ，一，广义可逆矩阵的构造与计数问题已经可以归结为一州( r ：，) 与一( 一) 中 所有元素的构造与计数问题本节的讨论将利用伪辛群几何中的已有结论 注意到。单位阵是对称可逆的，存在n n 的可逆矩阵，、使得 其中 k i ( “1 | i = s i 如果n 为奇数 如果n 为偶数， f o l 岛= l ，p 0i ，= 可见n = 2 p + 6 如果j = ( 2 9 ) 如果j ：2 ( 2 1 0j “， 5 26 非奇异子空间与伪辛群几何( p = 2 ) 如果d2 ”叫中的子空间尺满足 相对于伪辛群s 胁+ 6 ( r ，) 的。尺乳r 7 合同与 ( r 2 s + ) ，一，我们称1 t 为相对于伪辛群s 跏+ 6 ( ) ( r ，2 s + ，c ) 型的子空间存在r 的矩阵表示t ( 存 在b f ? ，( ) ，使得t = b r ) 满足： 而且 _ r & t 7 = m ( r ，2 s + r ，s + lg t 如果f _ o ；+ l t 如果( _ 其中 。i = ( 1 ，0 ，0 ，o ) ，。2 = ( 0 ，1 ，0 ，0 ) ，一，。2 v + 6 = ( 0 ，0 ， 、0 1 类似上一节的引理我们有 引理2 7 令n = 2 p + j 且如上定义j 和设r 是尉2 ”6 中的一个r 维向量子 空间r 。= r k 一1 则下述条件等价： j 子空间1 t 一2 “( r ：+ ) ! r l t t i 可逆 ? _ r l 为曩”“中相对于伪辛群p s 2 v + 6 ( r ，8 6 ) 的( 2 s + r ，s ，( ) 型的子空间其中 r = 2 s + r r f 0 ，1 2 ，e f 0 ，l 构造：设n = 2 u + 6 j 乳如上定义则构造所有t n n 的r 维的m p 广义可逆矩阵的 问题归结为构造所有的f ：2 “引( ”) 中的子空间进一步的可以归结为构造所有 “2 “引中相对于伪辛群p s 2 v + 6 ( r ，) 的( r ，2 s + r s ，c ) 类型的子空间其中r = 2 s + r 如 上述引理所定，更进一步，此问题可以归结为构造所有的满足( 21 1 ) 和( 21 2 ) 的矩 阵的全体在【4 】中为了计算矗2 “”中相对于伪辛群p 跏+ d ( ，) 的( r ，2 s + ”，e ) 类型的子空间的个数。书中提供了一种构造方法这样我们就得到了一种构造 所有m n 的秩为r 的m p 广义可逆矩阵的方法 定理2 8 ( 计数) 把m n 的秩为r 的m - p 广义可逆的矩阵的个数记为。( ； ) l ， 设n = 2 v + 6 。其中j 如r2 9 ，中定义则我们有 m r 。 ：r ：) i = i c l r ( f d l f 曩州( r ；) i i 哪( r ： 砖”+ ( ” 中国科学技术大学硕士学位论文 i 仁o ln ( 2 t + 1 2 t + 1 f f ：2 v + d ) ，如果r = 2 t + 【仨o l ，：o 2 坛旦 n ( 2 t ，2 s + s ，f ：2 v + d ) ，士口果，= 2 t v ( 2 t ，2 s + r ，s ( ：2 v + j ) 的公式可以在“，中得到 计算i “”( r + ) l 的公式类似 证明：第一个等式可由定理2 5 得到，第二个等式可以由引理27 得到 2 7 值得进一步研究的问题 本文将上m p 广义可逆阵的构作归结为非奇异子空间集合if ：”( ) i ，i 列叫( 的构作进一步归结为有关典型群几何中非奇异子空间的构作 注意到 6 l 在构作伪辛群几何或正交几何中非奇异子空间的矩阵表示时， 同一子空间有多个不同的矩阵表示被构作出来因此一个值得进一步研究的问 题是如何构作非奇异子空间的矩阵表示，使每一个非奇异子空间的矩阵表示恰 出现一次? 第三章基于两个数学难题的签名方案 3 1 引言 熟知的一些公钥密码系统的安全性都是基于某个经典的数学难题，例如r s a 的安全性是基于大数分解问题( f p ) ；而d i f f i e h e l l m a n 密钥交换系统，e i g a m a l 体 制，d s a 签名系统，椭圆曲线密码系统等都是基于离散对数问题( d l p ) 基于两 个难题的公钥密码系统是指系统的安全性得到两个难题的支持，即使其中一个 问题得到解决，只要另外一个问题仍然是难以解决的，系统的安全性仍能得到 保证 如何设计这种基于两个难题的公钥密码系统的问题一直受到关注早在1 9 8 8 年，m c u r l e y 在 1 2 】中将有限域g f ( p ) 上的d i f f i e - h e l l m a n 密钥交换系统推广到模 n 的环z f v ) 上。这里n 是两个大素数p 与q 之积，并证明了这一系统得到f p 和d l p 两个难题的支持 为了增强e i g a m a l 签名方案的安全，我们可以在签名的过程中嵌入别的数学 难题。如大数分解问题等在【1 3 ，1 4 ，1 5 】等中就有人提出了一些基于上述两个难 题的签名方案我们对 1 3 】中提出的方案进行了分析，指出其方案并不象其作 者认为的那样能同时得到d l p 和“模一合数的平方根问题”这样两个问题的支 持，事实上，只要方案中的d l p 解决了，任何人都可以伪造用户的签名文章 l 剐的作者提出了两种签名方案。并宣称其安全性是基于上述两个难题的。我们 分析发现这两种签名方案在代换攻击下其实是不安全的，并给出了伪造签名的 公式( 注；代换攻击是指在已知某消息的有效签名时，可以在不知道签名者 私钥的情况下伪造别的消息的签名) 结合n y b e r g 和r u e p p e l 在【2 1 ，2 2 】中提出了基于离散对数问题并且带有信息 恢复的签名方案，本文提出了两类具有信息恢复功能的签名方案。并说明它们 的安全性是基于大数分解问题和离散对数问题的而且本文提出的方案在实施 中的计算时间和效率上都比【1 3 ，1 4 ，1 5 l 中提出的方案要好 3 2 对一些数字签名方案的分析 3 2 1对【1 3 1 中签名方寨的分析 先介绍【1 3 】中的签名方案 2 3 中国科学技术大学硕士学位论丈 该系统有公开参数( p ，9 ，h ) ，其中p = 1 + 2 p 。qp p 。，q l 都是大素数( ) 公开蕴 含着乘积p q 。是公开的) ，g 是g f ( p ) 中阶为p 的元素，i t 为一h a s h 函数 用户的私钥为随机选定的r ( o r 肌q 。) ，公钥是( p ：) ，这里= 旷。( r o o dp - ：= h ，( r o o dp 1 用户对消息i n ( 0 ，n r 】) 的签名为( ) ，其中 ， lr=9(modp ) l5 = ( m l z + n z 。) f ( r o o dp l q l 】 其中t ( 0 t p 1 ) 随机选取，t , q ，为m 在二进制表示下的前几位( 长度于p l g j 相 同) ，n = j 【，( m ) + r ( r o o dp ) 接收者认为( ) 是a 对消息m 的签名当且仅当 g m i ：“3 9 2 m t n = 一2 ( m o dp ) ，其中n = ( m ) + r 方案设计者认为这一方案能同时得到d l p 与f p 两个难题的支持下面的命 题表明即使分解p 。q 。是困难的，但只要方案中的d l p 问题可解，任何人都可以 对任何消息伪造用户的签名 命题1 假设上述方案中的d l p 可解，即可以从用户公开的= g r 3 ( m o d 尸) 求 出z 2 则任何人可以对任何消息伪造用户的签名，具体地说，任取r ( o r p t g 。) ， 并令 r = ：r 1 ( m o d p 1 l t = h ( m ) + r ( 3 1 ) 8 = r 一。( n + m l z 2j ( m o dp t q lj 那么( 一) 必能通过签名验证而成为用户对消息m 的合法签名 证明：设t = r r 那么 s t = s t z 一= n + m l