（计算机应用技术专业论文）直接匿名证言方案的改进与实现.pdf

河南大学研究生硕士学位论文第1 页 摘要 可信计算组织认为隐私保护是可信系统的一个必要因素，用户对自己的隐私 信息必须拥有选择和控制权，为此可信计算组织于2 0 0 4 年发布了d 从方案来保证 证过程的匿名性和解决p r i v a c yc a 方案存在的问题。但是d a a 方案的时间开销过 大，不能很理想的应用于现实系统。 本文在研究一些特殊的可以实现匿名性的签名方案像代理签名方案，盲签名 方案，群签名方案后，对d 从方案的产生背景、发展阶段、实现机制、具体协议 进行了研究。在d a a 匿名机制的原理框架内，解决缩短时间开销问题的方法主要是 缩短参数长度，如果仅缩短参数长度，将会降低新方案的安全性。要想缩短参数 长度又要保证新方案的安全性与匿名性，只有将离散对数问题转化成椭圆曲线离 散对数问题。然而d a a 方案是整数的因式分解系统与离散对数系统结合而产生的 方案，只是将离散对数问题转化成椭圆曲线离散对数问题，相关整数的因式分解 问题，因参数缩短而变得不安全，致使整个方案变得不安全。为此，本文提出了 一个新的d a a 方案，在新的方案中，摒弃了用整数的因式分解系统与离散对数系 统结合来完成方案要求的方法，加入新的方法能够在只使用椭圆曲线离散对数问 题进行构造来完成原方案的要求。 本文对新的方案和原来的方案在安全性，匿名性和执行效率几方面进行了比 较分析。为了进行效率分析，模拟实现了d 从方案和新的方案。在实现方案中省 去了通信的操作，实现单机版本的运行。为此建造了实现可以产生公钥功能的 s e t u p 类。用于哈希函数的h a s h 类，设计了一个可以满足d 从方案要求输出1 7 1 2 位的安全h a s h 函数。实现t p m 相应功能的t p m 类，实现h o s t 相应功能的h o s t 类， 实现d a a 发布者功能的相应i s s u e r 类，实现验证者功能的v e r i f i c a t i o n 类，和 模拟方案的d a a 类。以及新方案中要用到椭圆曲线的功能的e c c 类。 经过对新的方案与原方案相比分析，新的方案在不降低安全性和匿名性的情 i 况下，提高了执行效率，缩短了时间花费。 关键词：可信计算；零知识证明；直接匿名证言；可信平台模块 第1 i 页河南大学研究生硕士学位论文 a b s t r a c t t 1 1 l s t e dc o m p u t i n gg r o u pb e l i e v e st h a tp r i v a c yp r o t e c t i o ni so n eo fn e c e s s a 拶 e i e m e n t so ft 1 1 】s t e dc o m p u t i n gs y s t e m s ，a n du s e r sm u s th a v et h er i 西t st oc h o o s ea n d c o n n o l t h e i rp r i v a t ei n f b m a t i o n i n2 0 0 3 ，t oe n s u r et h ea n o n y m 时i na u t h e n t i c a t i o na n d r e s o l v et h ep r o b l e m so fp r i v a c yc as c h e m e ，t m s t e dc o m p u t i n gg r o u pi s s u e dd a a s c h e m e h o w e v e r ，t h ed a as c h e m ei sn o tv e 哆s a t i s f a c t o 叫i nr e a ls y s t e m sf o ri t s s p e n d i n gt o om u c ht i m e i nt h i sp a p e r ，s o m es p e c i a ls c h e m e sw h i c hc a l lb ea c h i e v e da 1 1 0 n 1 忡i 戗s u c ha s s i 印a 吡r ep r o x ys i 印a m r es c h e m e s ， b l i n ds i 印a m r es c h e m e sa n dg r o u p s i 朗a m r e s c h e m e s ，a r es t u d i e d t h e nt h eb a c k g r o u n d ，t h es t a g eo fd e v e l o p m e n ta n dt h ea c h i e v i n g m e c h a n i s m so fd a as c h e m ea r ea l s os t u d i e d i nt h e 行a m e w o r ko fd a aa n o n v m o u s m e c h a n i s m ，t h em a i nm e t h o do fr e d u c i n gt i m ee x p e n s ei st os h o r t e nt h el e n g t ho f p a r a m e t e r s b u to n l yt os h o r t e nt h ep a r 锄e t e r sl e n 酉h ，w i l lt h es e c u r i t yb ed e c r e a s e d t o o t os h o r t e nt 量1 el e n g t l lo fp a r 锄e t e r sa n dg u a r a n t e et h es e c u r i t ya n da n o n y m 岫o fn e w s c h e m e ， w em a y c h a n g e t h ed i s c r e t e l o g a r i t h mp r o b l e m i n t o e l l i p t i c c u r v e s c 拶p t o s y s t e m h o w e v e r ，d a as c h e m ei st h es c h e m ew h i c hi si n t e 黟a t e db yf a c t o r i n g i n t e g e r sa n dd i s c r e t el o g a r i t 王1 i i lp r o b l e m ，j u s tc h a n g i n gt h ed i s c r e t el o g a r i t h mp r o b l e m i n t oe 1 1 i p t i cc u r v e sc 聊t o s y s t e m s ，w i l lm a k et h es c h e m eu n s a f e f o rt h e s er e a s o n s ，a n e ws c h e m eh a sb e e no f f e r e d i nt h en e ws c h e m e ，f a c t o r i n gi n t e g e r sa n dd i s c r e t e l o g a r i t h mp r o b l e ma r ed i s c a r d e d ，a n dan e wm e t h o dw a sj o i n e d ，s ot h er e q u i r e m e n t so f t h eo r i g i n a ls c h e m ew o u l db ea c h i e v e db ye l l i p t i cc u r v e sc 眄p t o s y s t e m f i n a l l y ，w ec o m p a r e st h en e ws c h e m ew i t ht h eo r i g i n a ls c h e m e0 nt h es e c u r i t y ，t h e a j l o n y m i t ) ，锄dt h ee 筒c i e n c y i no r d e rt oc a n yo u tt h ee 筒c i e n c ya n a l y s i s ，t h en e w s c h e m ea i l dt h eo r i 百n a ls c h e m ea r es i m u l a t e d 1 1 1t h ei m p l e m e n t a t i o n ，t h eo p e r a t i o no f c o m m u n i c a t i o ni so m i t t e da n das t a n d - a l o n ev e r s i o ni sc a r r i e do u t 1 1 1t h es i m u l a t i o n p r o g r 锄s ，t h ec l a s so fs e t - u pf o rp r o d u c i n gap u b l i ck e y ，t h ec l a s so fh a s hf o r c o n s t m c t i n gh a s hm n c t i o n ，t h ec l a s so ft p m f o ri m p l e m e n t i n gt h em n c t i o n so ft p m ， t h ec l a s so fh o s t ，t h ec l a s so fi s s u e r ，m ec l a s so fv e n f i c a t i o n ，t h ec l a s so fd a a a n dt h e c l a s so fe c ca r ea l lc o n s 仃u c t e d c o m p a r i n gw i t ht h eo r i g i n a ls c h e m e ，t h en e ws c h e m ed o e sn o td e c r e a s et h es a f e t y a n da n o n y m i 够a tt h es a m et i m e ，i ti m p r 0 v e se m c i e n c yb yr e d u c i n gt h et i m ee x p e n s e k e y w o r d s ：t m s t e dc o m p u t i n g ；z e r 0 一l ( n o w l e d g ep r o o f d i r e c ta n o n y m o u sa t t e s t a t i o n ；t m s t e dp l a t f o 咖m o d u l e 关于学位论文独立完成和内容创新的声明 本人向河南大学提出硕士学位中请。本人郑重声明：所呈交的学位论文是 本人在导师的指导下独立完成的，对所研究的课题有新的见解。据我所知，除 文中特别加以说明、标注和致谢的地方外，论文中不包括其他人已经发表或撰 写过的研究成果，也不包括其他人为获得任何教育、科研机构的学位或证书而 段保存、汇编学位论文( 纸质文本和电子文本) 。 ( 涉及保密内容的学位论文在解密后适用本授权书) 学位获得者( 学位论文作者) 釜名：芬】钥乏里 2 0o 宫年月内目 学位论文指导教师签名盔z 量鑫 试略每毛羚f g 岛 河南大学研究生硕士学位论文第1 页 1 1研究背景 第1 章绪论 互联网的迅速发展改变传统的事务处理方式，开放的网络环境和开放的网络 协议给基于网络的业务系统的使用( 如证券系统、银行系统、网上购物以及电子政 务系统等) ，带来了极大的方便性。因为越来越多的系统都发展了网络业务，网络 用户的客户几乎成了客户群体的主体，但同时也降低了业务系统的安全性。系统 面临的威胁主要有：客户密码的安全保密和客户身份的网络认证，身份认证的真 实性和身份认证手段本身的可靠性。数字签名技术的发展，很好的解决了网络用 户身份认证的功能，防止虚假用户冒充真实用户在网上开展业务。 网络的开放性和匿名性也决定了单纯的互联网不可避免的存在许多的安全隐 患，例如电子商贸等有偿网上服务也会因为无法安全、便捷地确认用户身份而很 难开展。想要真正的实现互联网上的网上交易和信息传输的安全性，就必须满足 机密性、完整性、真实性、不可抵赖性4 大要求。 数字签名( d i g i t a ls i 盟a _ t u r e ) u 1 的概念自从1 9 7 6 年提出来以后，引起了密码应用 界和计算机网络界的普遍关注。密码学研究者根据应用环境的要求，先后设计了 多种数字签名方案。1 9 8 5 年e l g a m a l 第一次在有限域上基于离散对数问题设计了 e l g a m a l 数字签名方案，是数字签名历史上的一个里程碑。美国国家安全局和国 家标准局通力合作，在1 9 9 1 年提出了美国数字签名体制d s s 及其算法标准d s a 。 d s a 也是基于最初的e l g a m a l 数字签名方案的。1 9 8 5 年由k o b l i t z 和m i l l e r 分别 提出了基于椭圆曲线离散对数问题的公钥密码或者简称为椭圆曲线密码。它是用 椭圆曲线有限群代替基于有限域上离散对数问题公钥密码中的有限循环群所得到 的一类密码体制。椭圆曲线密码的优势逐渐凸现出来，它所具有的巨大商业价值 以及重大的军事价值正在为越来越多的人所关注。在新的数字签名中的应用也越 来越多。 为了实现一些特殊的要求，就产生了一些新的签名技术。比如在网上用信用 卡购物，相应的交易信息就会被存储到数据库中，久而久之，人们的消费习惯和 财政状况就有可能被某些别有用心的人所获知，这肯定不是人们所希望看到的。 消费者使用的电子现金必须加上银行的数字签名才能生效，此时为了保护消费者 第2 页河南大学研究生硕士学位论文 的匿名性，就要用到盲签名技术；同样，在电子选举中，选民提交的选票也必须 盖上选委会的戳记( 即数字签名) 才合法，为了保护选民的匿名性也要用到盲签 名技术。在现实世界里，人们经常需要将自己的某些权力委托给可靠的代理人， 让代理人代表本人去行使这些权力。在这些可以委托的权力中包括人们的签名权。 委托签名权的传统方法是使用印章，因为印章可以在人们之间灵活地传递。为了 让数字签名实现这种功能1 9 9 6 年，m 鲫b o 、u s u d a 和0 k 砌o t o 提出了代理签名的概 念，实现了这种功能。群签名的一个典型应用例子是在公司的管理中隐藏公司内 部管理层的结构，如用群签名对交易合同或其他文件签名，客户或其他验证者只 验证该文件是该公司签名即可，而不知道具体是谁签的，因此不可能从签名中得 知公司管理层的更详细情况，而公司在必要时又可利用群签名的打开功能来揭露 某文件签名人的身份，做到既隐藏管理层结构又可追查责任。 2 0 世纪7 0 年代初期，a n d e r s o n j p 首次提出可信系统的概念卫1 由此开始了人们 对可信系统的研究。较早期学者对可信系统研究( 包括系统评估) 的内容主要集中 在操作系统自身安全机制和支撑它的硬件环境，此时的可信计算被称为“可靠计 算”，与容错计算领域的研究密切相关。人们主要关注元器件随机故障、生产过程 缺陷、定时或数值的不一致、随机外界干扰、环境压力等物理故障，设计错误、 交互错误、恶意的推理、暗藏的入侵等人为故障造成的各种不同系统失效状况， 设计出许多集成了故障检测技术、冗余备份系统的高可用性容错计算机。这一阶 段研究出的许多容错技术已被用于目前普通计算机的设计与生产。 1 9 8 3 年美国国防部推出了“可信计算机系统评估标准( t c s e c ：t m s t e d c o m p u t e rs y s t e me v a l u a t i o nc r i t e r i a ) ( 亦称橙皮书) ，其中对可信计算机( t c b ， t r u s t e dc o m p u t i n gb a s e ) 进行了定义。这些研究主要是通过保持最小可信组件集合 及对数据的访问权限进行控制来实现系统的安全，从而达到系统可信的目的。1 9 9 9 年1 0 月，由m t e l 、c o m p a q 、h p 、i b m 、m i c r o s o r 发起了一个“可信计算平台联 盟”( t c p a ：1 h s t e dc o m p u t i n gp l a t f o ma l l i a n c e ) 【3 】截止至2 0 0 2 年7 月，已经有l8 0 多家硬件及软件制造商加入t c p a 。该组织致力于促成新一代具有安全、信任能力 的硬件运算平台。 2 0 0 2 年1 月1 5 日，比尔盖茨在致微软全体员工的一封信中称，公司未来的 工作重点将从致力于产品的功能和特性转移为侧重解决安全问题，并进而提出了 微软公司的新“高可信计算”战略。在可信计算三十余年的研究过程中，可信计 算的含义不断地拓展，由侧重于硬件的可靠性、可用性到针对硬件平台、软件系 河南大学研究生硕士学位论文第3 页 统、服务的综合可信，适应了i n t e r n e t 上应用系统不断拓展的发展需要。 可信计算组织认为隐私保护是可信系统的一个必要因素，用户对自己的隐私 信息必须拥有选择和控制权。由于每个可信平台模块( t r u s t e dp l a t f o r mm o d u l e ， t p m ) h 1 均有一对能惟一标志自己的r s a 背书密钥( e n d o r s e m e n tk e y ，e k ) ，很容易 造成平台用户的行为被跟踪，导致隐私泄露。对于可信计算技术而言，隐私保护 是其能够被用户广泛认可和使用的关键性因素。在分布式可信计算系统中，可信 计算平台( t r u s t e dc o m p u t i n gp l a t f o r m ，t c p ) 之间的认证包括确认对方有一个合 法的t p m ，确认对方运行着安全的操作系统及软件。对平台运行软件的安全确认由 验证对方提供的平台配置注册码( p l a t f o r mc o n f i g u r a t i o nr e g i s t e r s ，p c r ) 的值 来实现，但前提是提供p c r 度量值的对方t p m 是一个合法的t p m ，这就要求各个 t c p 所包含的t p m 之间能够实现身份认证。t p m 之间身份认证的核心问题是既能实 现相互认证又能保持匿名性，即t p m 能向认证者证明自己是一个合法的t p m ，但又 不能让认证者知道自己具体是哪一个t p m ，以防止平台用户的行为被跟踪。为此提 出了的直接匿名证言( d i r e c ta n o n y o u sa t t e s t a t i o n ，d 从) 嗨儿副方案。 但是，d a a 方案的性能也是一个需要关注的问题，据文献 5 显示，在i b m t h i n k p a dt 4 1 ( 1 7 g h zi n t e lp e n t i u m mc p u ，l g br a m ，l i i l u x ) 上运行i b m 开发的 d a a 原型系统，不计入通信时间，t p m 向发布者申请d a a 证明需要2 4 s ，其中 t p m 约占用2 5 ，主机约占用2 5 ，发布者约占用5 0 的时间：t p m 每次向验证 者认证自己需要4 4 s ，其中t p m 约占用8 ，主机约占用4 7 ，验证者约占用4 5 的时间。尽管通过改进求幂算法、主机预先计算一些值等措施能降低一些时间开 销，但d a a 方案的时间开销，尤其是每次认证时验证者花费的时间，无疑是过大 了。因此本文将对d a a 方案进行改进，来缩短原方案所花费的时间。 1 2 研究目的和研究意义 在分布式系统中，可信计算是通过t c p 和可信网络环境实现的。除了平台内 部各实体需要可信性认证外，t c p 之间也需要可信性认证。由于每个t p m 都有一对 能唯一标识自己的r s a 背书密钥( e k ，e n d o r s e m e n t k e y ) ，因而可准确提供自己的 身份证明，但也很容易造成平台用户的行为被跟踪，导致隐私泄露。对可信计算 技术而言，如何实现在t c p 之间相互认证的同时，提供隐私保护，即t p m 向认证 者证明自己是一个合法的t p m ，但又不让认证者知道自己具体是哪一个t p m ，是其 第4 页河南大学研究生硕士学位论文 能被用户广泛使用的关键。目前，t c g 已发布的可信平台身份认证方案包括p r i v a c y c a 方案和直接匿名证言( d a a ，d i r e c ta n o n y m o u sa t t e s t a t i o n ) 方案。 直接匿名证言方案可以实现很多功能解决很多问题是最有希望成为主流方 案，但是它也存在有问题，据文献 5 显示，在工b mt h i n k p a dt 4 l ( i 7 g h z i n t e l p e n t i u m mc p u ，l g br a m ，l i n u x ) 上运行i b m 开发的d a a 原型系统，不计入通信时 间，t p m 向发布者申请d a a 证明需要2 4 s ，其中t p m 约占用2 5 ，主机约占用2 5 ， 发布者约占用5 0 的时间；t p m 每次向验证者认证自己需要4 4 s ，其中t p m 约占用 8 ，主机约占用4 7 ，验证者约占用4 5 的时间。尽管通过改进求幂算法、主机预 先计算一些值等措施能降低一些时间开销，但d a a 方案的时间开销，尤其是每次 认证时验证者花费的时间，无疑是过大了，还不能很理想得用于现实的系统中。 直接匿名证言方案可以让客户同时拥有认证和隐私。它可以让客户安全的登 录i n t r a n e t ，安全和匿名的存取服务。本课题的研究意义在于改进直接匿名证言 方案，提高效率，使其能理想的用于现实的系统中。 1 3 本文研究的内容 本文首先对一些现有的特殊的签名方案：盲签名、代理签名、群签名进行了 研究，对它们的产生背景、实现机制、优点缺点进行了描述。在对以上签名方案 进行了研究以后，着重对d a a 方案进行了研究，并用j a v a 语言实现d a a 方案。在 文章中对d a a 方案的产生背景、发展阶段、实现机制、具体协议都进行详尽的叙 述，并且透漏了用j a v a 语言实现d a a 方案的一些细节问题。为了解决d a a 方案花 费的时间太长，还不能很理想得用于现实的系统中。 本文对d a a 方案进行了改进，写出了改进后的d a a 方案，并就匿名性、安全 性和执行效率与原方案进行了比较分析。 本文主要工作：一 ( 1 ) 研究了椭圆曲线，知识证明，和可信计算。 ( 2 ) 研究了数字签名。介绍了代理签名，盲签名和群签名产生的背景以及它们 可以实现的功能。对每种签名方案举出一个具体实现的例子，并卓一进行说明j 对他们的签名特性进行了研究。 ( 3 ) 研究了d 从方案的产生背景、发展阶段、实现机制、具体协议，并且模拟 实现了d a a 方案。在实现方案中省去了通信的操作，实现单机版本的运行。 河南大学研究生硕士学位论文第5 页 ( 4 ) 设计了可以缩短时间花费的直接匿名证言改进方案。 ( 5 ) 为了对新方案与原方案进行比较，模拟实现了新的方案。为了实现新的方 案，在原方案的基础上，特意构造了e c c 类来实现椭圆曲线的功能。 ( 6 ) 在安全性，匿名性和执行效率几方面，将原方案和新方案进行比了较分析。 本章小结 本章介绍了电子签名产生的背景，以及电子签名的现状以及可信计算组织发 布的d a a 方案的情况。给出了本文研究的目的以及研究意义，确定了本文的研究 主旨。最后介绍了本文的研究内容。 第6 页河南大学研究生硕士学位论文 2 1 椭圆曲线 第2 章知识背景 根据密码体系的研究需要，这里将探讨的是光滑的椭圆曲线j 1 。这一曲线在解 析平面中表现为一条非奇异( n o n s i n g u l a r i t y ) 的三次平面曲线。由r i e 唧a n r o c h 定理和亏格公式可知，任何一条椭圆曲线都可以用一个三次方程来表示，这个三 次方程一般称为w e i e r s t r a s s 方程。w e i e r s t r a s s 方程为： y 2 + q 砂+ 吩y = x 3 + 呸x 2 + x + ( 2 一1 ) 在仿射坐标系下椭圆曲线e ，可用w e i e r s t r a s s 方程式外加一个特殊的点d 来 表示。满足方程式w e i e r s t r a s s 的数偶( z ，y ) 为域f 上椭圆曲线上的点。其中， 域f 是代数闭域，它可以是有理数域r ，也可是有限域f 。 ， 与椭圆曲线公钥密码学有关的有限域主要有三类：z ，( 。和e 。 2 1 1椭圆曲线的简化形式 对于w e i e r s 仃a s s 方程式，令 及 # 鬯2 哆冬二8 日- 2 7 舅十9 6 2 6 4 仇 ( 2 - 3 ) l ( e ) = 露 ( e ) 显然，当且仅当 ( e ) 0 时，椭圆曲线方程式是光滑的，或者称为非奇异的。 幻q 蠢吒吒q 一 呸加咏锄咆吼瓴砌她卜n卜：一：彳即砰骘 = = i | i i i i 如玩环魄以 河南大学研究生硕士学位论文第7 页 本文均研究撑( e ) 0 的椭圆曲线。 定义2 1 6 设有椭圆曲线e ，其仿射方程为w e i e r s t r a s s 方程，则j f j ( e ) 为椭圆 曲线e 、的判别式，而( e ) 为椭圆曲线e 的j 不变量。 根据域f 的特征c h a r ( f ) 和j 不变量，可以得到w e i e r s t r a s s 方程的不同简化 形式。 ( 1 ) c h a r ( f ) 2 ，3 时 y 2 = x 3 + 以x + 6 ( 口，6 f ) ( 2 4 ) ( 2 ) c h a r ( f ) = 2 时 y ：+ 砂2x 3 _ 呸x 2 + ( 口2 ，魄f ，郧) o ( 2 5 ) 【y 2 + 吗y = x 3 + 口4 z + ( 口3 ，口4 ，f ，( e ) = o ) ( 3 ) c h a r ( f ) = 3 时 y ：2x ：+ 口2 2 2 + ( 吃，f ，( e ) o ) ( 2 6 ) i y 2 = 工3 + q x + ( q ，f ，( e ) = o ) 当需要设定一条椭圆曲线的方程时，若对域的情况已有所约定，则可以根据 域f 的特征c h a r ( f ) 和j 不变量等情况，选取上面5 个方程式中的一条作为该曲线 的w e i e r s t r a s s 方程进行研究。 2 1 2 椭圆曲线上点的运算 根据代数几何理论，椭圆曲线e 构成一个a b e l 加法群，d 是其单位元。椭圆 曲线上的点对应于a b e l 加法群中的元素。下面给出仿射坐标系下椭圆曲线上点的 运算公式。 ( 1 ) 求逆元 设p = ( 弘y ) e ，根据w e i e r s t r a s s 方程式，由根与系数的关系易知 一p = ( z ，一y q x 一吩) ( 2 ) 求和 ( 2 7 ) 第8 页河南大学研究生硕士学位论文 设p = ( _ ，y 1 ) 、q = ( 恐，款) e ，且p 一q ，r = p + q ，则点r ( 而，儿) 的坐标 为： j 黾2 旯2 + 口1 名一吒一x l 一吃( 2 8 ) 【儿= 一( 五+ q ) b 一1 ，一呜 其中 丝丛 尸q 1 镌一x l 以2 1 ，2 。一、 ( 2 9 ) i 笙箬型旦盟p ：q 怕列 【2 y l + 口l 五+ 吩 塑逊 j p q 0 叫t( 2 一l o ) 蔓善盟丝虹盟尸：q 2 y 1 + q j c l + 吗 ， 2 1 3 素数有限域椭圆曲线 素数有限域( p r i m ef i n i t ef i e l d s ) z 。的特征值为c h a r ( f ) = p ，其中p 为大 于3 的素数。由前文可知，此时的w e i e r s t r a s s 方程式为 y 2 = x 3 + 锻+ 6 ( 口，6 f ) 且( e ) = 4 口3 + 2 7 6 2 m o dp 。 此时，椭圆曲线群上点的运算为： ( 1 ) 逆元公式： 一p = ( x ，一y ) ( 2 1 1 ) ( 2 ) 加法运算： j 玛三( 旯2 一z l 一而) m o d p( 2 1 2 ) 【三( 五( 一屯) 一) ，i ) m o d p 其中 河南大学研究生硕士学位论文第9 页 l 丝边p q 肚 攀嘲 l2 乃 一z 2 1 4 2 一特征值有限域椭圆曲线 ( 2 1 3 ) 2 一特征值有限域( c h a r a c t e r i s t i c2 f i n i t ef i e l d s ) 的特征值c h a r ( f ) = 2 ，这 时椭圆曲线非奇异的条件是# ( e ) o 和j ( e ) 0 。 此时的w e i e r s t r a s s 方程式为 y 2 + 砂= x 3 + 日x 2 + 6 ( 口，6 ，) ，且( e ) = 6 0 。 此时，椭圆曲线群上点的运算为： ( 1 ) 逆元公式：由于在( 。上有一，? = ，2 ，则t 。上的逆元公式为： ( 2 ) 加法运算： 其中 一p = ( x ，一x y ) = ( x ，z + y ) ( 2 1 4 ) ( 2 一1 5 ) l 丝监j p q 力= 矿：1 ( 2 - 1 6 ) lx l + 丛 尸：q 【 而 素特征扩张有限域乞。的特征值为c h a r ( f ) 2 p ，所以其群运算与乃相同。 q q = 尸p 口+ 砭 + 口 + +力兄 + + 2 2 见兄 ，c、 = 第1 0 页河南大学研究生硕士学位论文 2 2 零知识证明 8 0 年代初，g o l d w a s s e r 等人提出了零知识证明这一概念。从本质上讲，零知 识证明是一种协议。所谓协议( p r o t o c 0 1 ) ，就是两个或两个以上的参与者为完成某 项特定的任务而采取的一系列步骤，包括以下三个特征： 1 协议自始至终是有序的过程，每一步骤必须依次执行，在前一步骤没有执 行完之前，后面的步骤不可能执行。 2 协议至少需要两个参与者，一个人可以通过执行一系列的步骤来完成某项 任务，但它不构成协议。 3 通过执行协议必须能够完成某项任务。 零知识证明必须包括两个方面，一方为证明者，另一方为验证者。证明者试 图向验证者证明某个论断是正确的，或者证明者拥有某个知识，却不向验证者透 露任何有用的消息。零知识证明目前在密码学中得到了广泛的应用，尤其是在认 证协议、数字签名方面，人们利用数字签名设计出了大量优良的算法。 用一个关于洞穴的故事来解释零知识。洞穴中有一个秘密，知道咒语的人能 打开c 和d 之间的密门，对其他人来说，两条通道都是死胡同。p e g g y 知道这个 洞穴的秘密。她想对v i c t o r 证明这一点，但也不想泄露咒语。 下面是她如何使c t o r 相信的过程： ( 1 ) v i c t o r 站在a 点。 ( 2 ) p e g g y 一直走进洞穴，到达c 点或者d 点。 ( 3 ) 在p e g g y 消失在洞穴中后，v i c t o r 走到b 点。 ( 4 ) v i c t o r 向p e g g y 喊叫，要她：从左通道出来，或者从右通道出来。 ( 5 ) p e g g y 答应了，如果有必要她就用咒语打开密门。 p e g g y 和v i c t o r 重复第( 1 ) 至第( 5 ) 步n 次。 假设v i c t o r 有一个摄像机能记录下他所看到的一切。他记录下p e g g y 消失在 洞中情景，记录下他喊叫p e g g y 从他选择的地方出来的时间，记录下p e g g y 走出 来。他记录下所有的n 次试验。如果他把这些记录给c a r o l 看，她会相信p e g g y 知 道打开密门的咒语吗? 肯定不会。在不知道咒语的情况下，如果p e g g y 和v i c t o r 事先商定好c t o r 喊叫什么，那将如何呢? p e g g y 会确信也走进v i c t o r 叫她出来那 条路，然后她就可以在不知道咒语的情况下在v i c t o r 每次要她出来的那条路上出 来。或许他们不那么做，p e g g y 走进其中一条通道，v i c t o r 发出一条随机的要求。 河南大学研究生硕士学位论文第1 1 页 如果v i c t o r 猜对了，好极了。如果他猜错了，他们会从录像中删除这个试验。总 之，v i c t o r 能获得一个记录，它准确显示与实际证明p e g g y 知道咒语的相同的事件 顺序。 这说明了两件事。其一是v i c t o r 不可能使第三方相信这个证明的有效性；其 二，它证明了这个协议是零知识的。在p e g g y 不知道咒语的情况下，v i c t o r 显然是 不能从记录中获悉任何信息。但是，因为无法区分一个真实的记录和一个伪造的 记录，所以v i c t o r 不能从实际证明中了解任何信息一它必是零知识。也就是说， p e g g y 在向v i c t o r 证明的过程中没有泄露任何有关秘密的知识，称为零知识。 现在，人们已经提出了多种基于零知识证明体制8 】【9 】，其中以r s a 零知识证 明体制【1 0 1 最为著名，其安全性是建立在基于大数分解问题的难解性，它要求很高 的大长度数据运算，因而计算十分复杂。这里介绍使用椭圆曲线算法，设计了一 种新的零知识体制1 1 1 。 l 系统的建立和密钥的生成 1 ) 系统的建立 选取基域f q ，一个定义在f q 上的椭圆曲线e 和e 上一个阶为素数n 的点p 。 点p 的坐标用( x p ，y p ) 表示。 本文选取的椭圆曲线方程为 y 2 = x 3 + 戚+ 6 有限域f q ，椭圆曲线参数a 和b ，点p 和素数阶n 均是公开信息。2 4 可信计 算 2 ) 密钥的生成 系统建成后，用户执行下列计算： ( 1 ) 在区间 1 ，n 一1 中随机选取一个整数x ； ( 2 ) 计算点q = x p ； ( 3 ) 用户的公钥为点q ； ( 4 ) 用户的私钥为整数x 。 用户将p 和q 作为公钥( 验证者知道) ，将x 作为私钥，同时视x 为用户的身 份。 2 用户身份认证过程 示证人a 要向验证人b 证明他知道x 满足x p = q ，p 、q 和n 公开，x 随机选择， 第1 2 页河南大学研究生硕士学位论文 但不能让b 知道。 ( 1 ) a 生成t 个随机数r ，r ：，r 。，r ； ，屯毒月 o 1 。+ 。+ 啊州，s 。毒r 0 ，1 + 啊+ 1 3 检验所有的( 五，石) 列表是否m 兰f 兀+ 石2 。( m o d i ) 4 2 d 从方案的模拟实现 在实现方案中省去了通信的操作，实现单机版本的运行。为此建造了实现可 以产生公钥功能的s e t u p 类，用于哈希函数的h a s h 类，保存公钥的p u b l i c k a y 类， 实现t p m 相应功能的t p m 类，实现h o s t 相应功能的h o s t 类，实现d 从发布者功 能的相应i s s u e r 类，实现验证者功能的v e r i f a t i o n 类，和模拟方案的d a a 类。 以下将对h a s h 类，d a a 类进行说明。 ，4 2 、1h a s h 类 为了满足d a a 方案对哈希函数的要求借鉴s h a 算法：4 3 1 和h a v a l 算法：4 钔，设计 了h a s h 类它拥有一个可以满足输出1 7 1 2 位的安全h a s h 函数，该h a s h 函数符合 单向性，抗弱碰撞，抗强碰撞，差分分布均匀性和映射分布均匀性等安全性要求。 h a s h 函数的构造算法 1 消息填充 对消息进行填充，使得填充后的消息长度为5 1 2 位的整数倍。消息的长度为 xi ，ixi 2 6 4 1 。l 表示ixf 的二进制，其长度最多为6 4 位。h a s h 函数的填充算 法如下： c o m m e n t ： x i 2 6 4 1 ； d 一( 4 3 8 一l x l ) m o d 5 1 2 ； l ixi 的二进制表示，il l = 6 4 ； h 一散列长度的二进制表示，fhi = 9 ； y x l0 8hl o 2 消息扩展 用下面的方法把5 1 2 位的消息分组，从1 6 个3 2 位( m 0 一m ，。) 扩展为8 0 个3 2 第3 8 页河南大学研究生硕士学位论文 位( m 0 一m ，。) 。 w 。= m 。， f o rt = 0t o1 5 ； w t = w t 一4ow t 一5ow t - 1 3ow t - 1 6 ， f o rt = 1 6t o7 9 。 3 初始变量 算法共需要1 2 个3 2 位常量，其中8 个为初始变量，4 个为主循环中要用到的 常量。这1 2 个初始变量是利用圆周率的产生的，取法如下：以( 兀一3 ) 术2 3 2 作为 初始值，取其整数部分为a 1 ，a 2 表示其小数部分，a 表示a 1 的十六进制表示。然 后b 1 表示a 2 术2 3 2 的小数部分，b 2 表示a 2 木2 3 2 的整数部分，同样b 表示b 2 的十六 进制。同理一直这样直到得到全部的1 2 个变量，其中8 个3 2 位初始变量的初始 值为： a = 0 x 1 5 e d 5 6 c 8b = 0 x 4 f d 3 6 c 7 5c = o x e c l 9 a 3 6 bd = o x 4 8 3 9 2 5 d ee = o x o e 5 f 6 8 a 2 f = 0 x 6 2 d f a 8 5 e g = 0 x 6 3 9 0 c e l fh = 0 x 8 2 2 9 e 7 2 a 主循环中用到的4 个常量初始值为： k 。= 0 x 6 3 6 f b c 2 a ，t 0 ，1 9 ；k ：= 0 x c 4 b f e s l b ，t 2 0 ，3 9 ；k 。= 0 x 8 2 4 3 0 e 8 8 ，t 4 0 ，5 9 ：k 。= o x 8 6 7 9 4 c 3 8 ，t 2 0 ，3 9 。 4 算法中非线性函数的设计 主循环算法中采用的非线性函数关系整个算法的安全性和有效性，本文使用 以下函数： f l ( a ，b ，c ，d ，e ，f ，) = aoa boc fob eoa d ，t o ，1 9 ； f 2 ( a ，b ，c ，d ，e ，f ，) = aoa cod eoc eob foa dob cob d eoa b c ，t 2 0 ， 3 9 f 3 ( a ，b ，c ，d ，e ，f ，) = a o a d o e f o b f o a d o a b c ，t 4 0 ，5 9 ； f 。( a ，b ，c ，d ，e ，f ，) = aoa eod eoc foc eoc dob fob doc d eob d eob c d ， t 6 0 ，7 9 。 以上四个非线性函数符合主循环算法的要求，具有良好的0 一l 平衡性、雪崩 性、不等价性和非线度性。 5 主循环算法 算法的一般性描述：消息中5 1 2 位分组的数目为循环的次数，循环有四轮； 分别对 o ，1 9 ， 2 0 ，3 9 ， 4 0 ，5 9 ， 6 0 ，7 9 这四轮进行2 0 次操作，每次操 作对8 个3 2 位初始变量进行线性变换，并使用相同的轮常数对其中6 个变量进行 一次非线性变换。 河南大学研究生硕士学位论文第3 9 页 f o ri = lt on ( n 为分组的个数) 初始化a ，b ，c ，d ，e ，f ，g ，h ： a a ，b b ，c c ，d d ， e e ，f f ，g g ，h h ； i fo t 1 9 a = a 1 l ；b = b 3 ；c = c0b0a ； d = dobo ( a 2 ) ； 耳2 a 。b 甲d ；h = h 2 3 ；t e m p 2 a 。h 。m t 。k t 。f t ( b ， g = f 1 4 ； f = e ；e = d ；d = c ； c = b ；b = a ；a = t e m p ； ) e l s ei f2 0 t 3 9 a = a 1 1 ；c = c 3 ；d = d 0c0 a ； e = eodo ( a 2 ) ； c ，d ，e ，f ， g ) ；h = g ； a = aocoe ；h = h 2 3 ；t e m p = aohom tok tof 。( b ，c ，d ，e ，f ，g ) ；h = g ； g = f 1 4 ；f 2 e ；e = d ；d = c ； c = b ； b = a ；a