（计算机软件与理论专业论文）数字现金防重用技术研究.pdf

南京邮i 乜大学硕： ：研究生学位论文摘要 摘要 近年来，随着全球信息化进程不断深化，尤其是计算机网络技术的快速发展，基于 i n t e r n e t 的电子商务发展迅猛，引起了产业界和学术界的极大关注。支付作为商务活动的一 个重要环节，能否较好地实现电子化、网络化，自然成了整个电子商务成败的关键因素之 一。数字现金以其方便、灵活、使用成本低等优点，在电子商务中的应用日趋广泛。 由于数字现金只是一系列加密数字序列，持有者很容易将其复制和重复花费，即数字 现金的重用，因此数字现金的防止重用技术十分关键。一般数字现金方案所采用的防重用 措施主要集中于预防、探测和限制欺骗，以及在发现欺骗时能够有效地确定欺骗者的身份。 作者研究了现有数字现金的主要协议模型，重点分析了其中的防重用原理。对目前应用最 为广泛的b r a n d s 数字现金协议模型进行了一定的改进。主要是在原有基础上结合了局部性 原理和自动控制理论中的反馈原理，提出了一种反馈式匿名数字现会协议模型。该模型更 为符合中国国情，能够自动地根据联网条件和用户的信用状况，判断是否对支付过程进行 在线验证，较好地解决了数字现金的灵活性与安全性相矛盾的问题。 本文论述了新模型的安全性和可行性，并且给出了相应的逻辑推理和数学证明，对实 际系统丌发设计也给出了一定篇幅的介绍。 关键词：电子商务、数字现金、重用、加密、解密、反馈、局部性原理 南京邮电大学硕匕研究生学位论文 a b s t r a c t a b s t r a c t i nr e c e n ty e a r s ，w i t ht h eg l o b a li n f o r m a t i z a t i o nd e v e l o p i n gd e e p l ya n dt h ec o m p u t e rn e t w o r k t e c h n o l o g yg r o w i n gu pr a p i d l y ，b o t ha c a d e m i aa n di n d u s t r yp a ym u c hm o r ea t t e n t i o nt o e - b u s i n e s sb a s e do ni n t e r n e t o n l i n ep a y m e n ta n de l e c t r o n i cp a y m e n tb e c o m eav e r yi m p o r t a n t p a r to fe _ b u s i n e s s d i g i t a lc a s hi su s e dm o r ea n dm o r ew i d e l yf o ri t sc o n v e n i e n c e ，a g i l i t ya n d l o wc o s t b e c a u s ed i g i t a lc a s hi se s s e n t i a l l yas e r i e so fe n c r y p t e dd i g i t a ls e q u e n c e ，t h eo w n e rc a n c o p ya n d r e u s ei tv e r ye a s i l y s ot h ea n t i r e u s et e c h n o l o g i e sp l a yav e r yi m p o r t a n tr o l ei nad i g i t a lc a s h s y s t e m t h ea n t i - r e u s et e c h n i q u e si ng e n e r “d i g i t a lc a s hs c h e m ef o c u so nt h ep r e v e n t i o n ， d e t e c t i o na n dr e s t r i c t i o nd e c e p t i o n ，a n dc a ne f f e c t i v e l yd e t e r m i n et h e i d e n t i t yo fc h e a t e r a c c o r d i n g l y ，t h ea u t h o rh a ss t u d i e ds o m ee x i s t i n gd i g i t a lc a s hs c h e m e s ，a n da n a l y z e dt h e p r i n c i p l eo fr e u s ei np a r t i c u l a r t h ea u t h o ra l s oe x t e n d e dt h eb r a n d sm o d e la n dp r e s e n t e dak i n d o ff e e d b a c ka n o n y m o u sd i g i t a lc a s hm o d e l ，b ya p p l y i n gt h ef e e d b a c kt h e o r ya n dl o c a lp r i n c i p l e t h i sm o d e li sm o r es u i t a b l ef o rc h i n a ss i t u a t i o n ，w h i c hc a nd e c i d ew h e t h e ri tn e e da no n l i n e p a y m e n ta u t h e n t i c a t i o na u t o m a t i c a l l y , o nt h eb a s i so fn e t w o r k i n gc o n d i t i o n sa n dt h eu s e r 。sc r e d i t s i t u a t i o n i ti sab e a e rs o l u t i o nt ot h ef l e x i b i l i t ya n ds e c u r i t yc o n t r a d i c t o r yp r o b l e m t h i sd i s s e r t a t i o nd e s c r i b e st h e s a f e t y a n df e a s i b i l i t yo ft h en e wm o d e l ，p r o v i d i n ga l o g i c a l i n f e r e n c ea n dm a t h e m a t i c a lp r o o f , p u t t i n gf o r w a r dac e r t a i na d v i c eo nt h ed e v e l o p m e n t a n dd e s i g no ft h ei m p l e m e n t a t i o n k e yw o r d s ：e - b u s i n e s s ，d i g i t a lc a s h ，r e u s e ，e n c r y p t i o n ，d e c r y p t i o n ，f e e d b a c k ，l o c a lp r i n c i p l e i i 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名：继 日期： 兰! ! 兰：竺! 岁 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电大学研究生部办理。 1f 石 研究生签名：筘磊毳导师签名日期：j 一。驴幺歹 南京邮咆入学顾 ：研究生学位论文第一章绪论 1 1 课题的背景 第一章绪论 i n t e r n e t 的出现为人类社会创造了一个全新的信息空间，在这一空间里人们用数字信号 在网上交换物品，讨论问题，甚至写作游戏。商务活动作为现代人类经济生活最基本、最 广泛的联系方式自然会渗透到这个空间中，于是人类想到了用数字信号在网上开展商务活 动1 1 1 。所以电子商务是人类经济、科技、文化发展的必然产物，是信息化社会的商务模式， 也是整个商务活动方式发展的方向。支付作为商务活动的一个重要环节，能否较好地实现 电子化、网络化，自然成了整个电子商务成败的关键因素之一。 1 1 1 电子支付系统( e p s ) 电子支付他1 从广义上讲就是资金或与资金有关的信息通过网络进行交换的行为，在电 子商务中就表现为单位、个人通过电子终端，直接或间接向银行业金融机构发出支付指令， 实现货币支付与资金转移。 1 电子支付的一般实现步骤 客户首先用定金额的现金或者存款从银行兑换得到代表相同金额的电子货币，通过 电子化方法直接转移给收款方。这种方法实施的基础就是金融电子化：以商用电子化设备 和各类交易卡作为媒介，以计算机和通信技术为手段，二进制数字作为存储形式，通过计 算机网络系统进行买卖交易。 2 电子支付的几种形式 ( 1 ) 按电子支付指令发起方式分类 网上支付：网上支付是电子支付的一种形式。广义地讲，网上支付是以互联网为基础， 利用银行所支持的某种数字金融工具，发生在购买者和销售者之间的金融交换，而实现从 买者到金融机构、商家之间的在线货币支付、现金流转、资金清算、查询统计等过程，由 此电子商务服务和其它服务提供金融支持。 电话支付：电话支付是电子支付的一种线下实现形式，是指消费者使用电话( 固定电 话、手机、小灵通) 或其他类似电话的终端设备，通过银行系统的“电话银行”就能从个 人银行账户旱直接完成付款的方式。 移动支付：移动支付是使用移动设备通过无线方式完成支付行为的一种新型的支付方 式。移动支付所使用的移动终端可以是手机、p d a 、移动p c 等。 南京邮电大学硕上研究生学位论文 第一章绪论 ( 2 ) 按电子支付工具的表现形式分类 智能卡：智能卡即嵌入微型控制芯片的i c 卡，使用智能卡必须使用相应的读卡设备 和智能卡操作系统。开发商使用智能卡的程序编制器，同时提供智能卡的程序应用接口。 支付流程如下：首先，启动浏览器，通过读卡机登录到开户银行，并将卡上的身份标识信 息发送给银行：然后，用户从智能卡上下载或上传现金到商家账户，或从银行帐号下载现 金存入卡中。 电子支票：电子支票是一种利用数字传递将钱款从一个帐户转移到另一个帐户的电子 付款形式。电子支票支付和传统支票一样都需要支付人的签名，所不同的是电子支票所使 用的是电子签名，而电子签名的伪造成本和难度远远大于手写签名。因而，它具有更高的 安全性。同时，电子支票事务处理费用较低，而且银行也能为参与电子商务的商户提供标 准化的资金信息。 数字现金：数字现金实质上就是一种表示现金的加密数字序列，它能够履行纸币的所 有职能，并且具备更多优点，如节省交易时间、无纸张印刷环节、持币安全、传递过程无 需武装押运等。 3 电子支付发展的趋势 尽管电子支付系统已经有了近3 0 年的发展，但是现金仍然是现实生活中最主要的支 付手段。主要原因如下：现金是可以转让的，是一种法定货币，具有无可比拟的权威性； 现金的主要形式纸币或硬币在现实生活中使用起来很方便，整个支付过程无需银行参与， 也无需支付双方拥有银行账户；现金可以很好的保护收付双方的隐私性，具有匿名支付的 特点，交易结束后很难根据支付过程中使用的现金去确定支付双方的身份。不难看出，在 上文中列举的几中电子支付形式中，数字现金不但具有现金支付的基本特点，更有现金支 付手段不可比拟的许多优点，发展前景广阔。 1 1 2 数字现金的发展现状 在众多学者从事数字现金理论研究的同时，国内外的许多公司、研究机构为数字现金 的广阔应用前景所吸引，也投入了大量的人力物力从事实用系统丌发研制。迄今为止，已 经出现了数十种商用数字现金方案。 1 m o n d e x 3 1 m o n d e x 电子钱包卡由英国西敏斯国民银行、米兰德银行共同投资创办的名为m o n d e x u k 的企业开发，是一种以智能卡为电子钱包的数字现金系统，具有信息存储、安全密码 锁等功能，目前主要在欧洲使用。m o n d e x 是一个不计帐的开放式预支付系统，发行公司 2 塑塞些! 坠堂堡主婴窒生兰堡丝壅墨二里笪堡 向成员机构出售m o n d e x 市值，这些成员机构再出售m o n d e x 市值，即卖给持卡人和零售 商。发行公司成员在现阶段仅限于信用机构。持卡人和发行公司并没有合同关系，但可能 承担发卡成员银行破产等造成的信用风险。m o n d e x 电子钱包可以在商家的终端进行支付， 并可通过钱包接口装置( 如a t m 机、专门电话机或电子钱夹等) 转账到其他的m o n d e x 卡中， 不再需要专门金融机构的交易授权、清算和结算。 m o n d e x 目前正在与一些大型跨国银行商讨合作将m o n d e x 电子钱包卡在国际上发行。 为了达到在国际上推广的目的，m o n d e x 正在研制存储多种货币的功能。设计方案为每种 货币均由独立的发行公司发行，购买某国币种必须通过该货币发行国家的银行。m o n d e x 主要在欧洲使用，是一种以智能卡为电子钱包的数字现金系统，具有信息存储、安全密码 锁等功能。 2 d i g i c a s h d i g i c a s h 是最早从事开发电子支付系统和数字现金系统的公司，其创立者是“数字现 金 之父c h a u m 。d i g i c a s h 设计了好几种不同的电子支付方案，使用公钥密码算法提供安 全性和隐私性。e c a s h 是d i g i c a s h 公司开发的基于互联网的无条件匿名的安全数字现金。 主要特点是通过数字记录现金，集中控制和管理现金，是一种足够安全的电子支付系统。 该系统是一种基于软件的数字现金方案，只要有联网的个人计算机就可以使用数字现金， 无需专门的硬件，这一点具有很强的吸引力。 3 v i s a 和n t t 联合试验晦1 v i s ai n t e m a t i o n a l 是美国最大的信用卡公司，1 9 9 6 年在亚特兰大奥运期间进行的v i s a c a s h 试验，成功发行了3 0 万张信用卡，为以后的电子货币取得了宝贵的经验。近年来， 又与日本n t t 数据通信公司合作，发展智能卡电子货币业务。v i s a 从2 0 0 0 年6 月开始 与6 家智能卡公司和东京三菱银行及富士银行等9 家银行联合进行智能卡电子现金 v i s a c a s h 实用实验。v i s a c a s h 有四种不同的卡，分别是像预支付卡那样的一次性使用型卡、 可重复输入货币数据的补加型卡、单独的信用卡和现金卡。 4 。n e t c a s h n e t c a s h 可以在因特网上提供匿名支付。它是一种支持实时电子支付的电子货币。顾 客必须在一个n e t c h e q u e 服务器上开一个帐户，以便从货币服务器获取电子货币。 n e t c h e q u e 系统为在线支付系统提供了一个安全框架，并且可以将其扩展到包括电子现金。 由于提供了n e t c a s h 和n e t c h e q u e 的组合，因此，顾客可以选择他们的匿名级别。由于 n e t c a s h 硬币只能通过n e t c h e q u e 来购买，因此，匿名不像在d i g i c a s h 系统中那么重要。 用来分发n e t c a s h 硬币的货币服务器可以跟踪购买硬币的顾客。但是，顾客可以自由选择 1 南京邮电大学硕l 研究生学位论文第一章绪论 他们使用的货币服务器，因此，货币服务器不可能跟踪到购买硬币的顾客。一旦硬币被一 个顾客所购买，它们就可以被传送给其他顾客或贸易商，虽然涉及到一个用来确保硬币有 效的货币服务器，但是，这不会泄露购买者的身份。 1 1 3 数字现金的发展方向 自c h a u m 博士首次提出数字现金的概念以来，数字现会的巨大发展潜力，引起了各方 的密切关注，现代密码学发展的日趋成熟为数字现金的应用提供了坚实的理论基础，国内 外学者提出了数种数字现金方案。目前数字现金的主要研究方向有： 1 数字现金的多银行性研究 现有的公平数字现金方案都是由一个银行发行的，但在现实生活中能由多个电子银行 系统发行的数字现金较之单个银行发行的数字现金更为实用，因为在一个国家或地区具有 数字现金发行能力的银行可能不止一家。为此，b r a n d s 首次提出了多银行数字现金的实现 思想，如图1 1 所示，各个银行形成一个群体，它们受国家中央银行管理，每个银行都可 以发行数字现金。如果系统中的分行数量较少，则所有分行的公钥表可以存放在每个用户 的本地数据库中，如果数量较多，可以使用公钥证书技术。每个商家都可以检查每个分行 发行的数字现金的有效性。系统中还包括一个分行间清算系统以解决银行之间的资金结算 问题。由于每个商家和分行都必须保存其他分行的公钥，且不同分行发行的数字现会采用 不同的签名体制，实现起来比较困难，在成员银行数量比较多的情况下效率比较低，此外 还存在成员银行的动态加入和退出问题。 图1 1 多银行离线式数字现金协议模型 为了克服商家和银行必须保存大量其它银行公钥的缺陷，c h a u m 和v a nh e y s t 首先提 出了群签名的概念。在群数字签名方案中，群中的任意一个成员都能代表整个群进行匿名 签名，且可以用单一的群公钥对该签名进行公开验证。随后c a m e n i s h 和s t a d l e r 提出了适 合于大群体的群签名方案，其群公钥和签名长度不依赖于群成员的个数。在此基础上， 4 南京邮i 乜大学硕士研究生学位论文 第一章绪论 l y s y a n s k a y a 和r a m z a n 将群签名和盲签名结合起来提出了群盲签名的概念，并构建一个由 中央银行和多个成员银行参与的数字现金模型，较好地模拟了现实生活中的银行实际情 况。但是，由于该方案实质是一个在线方案，而且其“打开”算法效率比较低，所以有待 进一步研究。 2 数字现金的可传递性研究 传递性是物理现金的一个基本特征，但在数字现金中还没有实现。最主要的原因是： 为了能跟踪重复花费的用户，须在数字现金中加入盲化的用户身份信息，并在数字现金流 动的过程中加入使用过该数字现金的所有用户身份信息，根据信息论的理论，数字现金的 长度是不断增加的，每次交易都将不断增大网络通信量，因此很难将其实际应用。鉴于此， 目前公平的离线数字现金的研究并不关注数字现金的传递性。 3 数字现金的可分性研究哺1 可分数字现金系统能够让用户进行多次合法的精确支付，减少提款次数，从而可以降 低网络通信量，提高系统效率，因此可分的数字现金系统也是当前数字现金研究的重点之 一。o k a m o t o 和o h t a 于1 9 9 1 年首次提出了可分数字现金系统旧1 ，该系统允许用户将数字 现金分成任意金额进行多次支付，直到与该数字现金总额相等为止。为使银行能够有效地 检测用户的重复支付，他们采用二叉树技术对数字现金进行表示，但这种技术导致数字现 金的支付协议通信量大、计算复杂度高、效率低。尽管许多学者对该方案从不同的角度提 出了改进，但都未能摆脱二叉树技术，改进后的支付协议执行效率仍然很低。因此，到目 前为止，可分数字现金系统依然不够实用。 1 2 研究的主要内容、目的及方案 近年来国内的电子商务蓬勃发展，其主要使用的仍是类似电子支票，需要在线身份验 证的支付方式，目前还没有一种成熟、实用、能较好实现安全离线支付的数字现金系统问 世。数字现金的安全是关键，只有保证了足够的安全性，让用户信任，才可能具备实用价 值。数字现金要像纸质现金一样地广泛使用，必须支持离线支付。虽然对数字现金的相关 理论研究不少，但是主要集中于对数字现金的传递性、多银行性及可分性的研究，少有专 门针对其反重用性的研究，本课题正是以此为切入点，在分析研究现有系统实现和理论的 基础上，尝试构建一种实用、有效的反重用技术模型。为了达到这一目的整个研究过程分 为以下几个步骤完成： 1 查阅国内外相关文献，了解国内外相关研究现状及发展趋势； 南京邮l 乜大学硕i ：研究生学位论文 第一章绪论 2 熟悉电子商务、银行货币结算等相关业务工作流程，较为系统地研究了各种数字 现金的防重用技术原理，比较其优缺点，提出改进方案； 3 应用密码学、数理逻辑等相关知识构建一种新型现金协议模型。 1 3 本章小结 本章对数字现金的出现背景、发展状况作了一定介绍，并对课题的研究内容、研究方 案做了具体交代。 6 南京邮电人学硕 ：研究生学位论文 第二章数字现金的相关理论基础 第二章数字现金的相关理论基础 现代密码学的发展成熟为数字现金的支付安全提供了可靠的理论基础。因此研究数字 现金，很有必要对现代密码学做深入研究。限于篇幅，本文仅仅对与数字现会支付密切相 关的基础理论和密码算法做一些介绍。同时为了构建一个具有实用价值且更符合中国国情 的数字现金系统，本文的研究还涉及到一些自动控制理论、法学甚至于犯罪心理学方面的 知识，本章也根据需要做了一些必要的介绍。本章中所有的代数、数论和密码学等相关理 论可以参考文献f 1 0 卜1 4 1 。 2 1 代数与数论的相关定义、定理 代数和数论是密码学研究最重要、最基础的数学工具，他们与现代密码学发展有着密 切联系。密码学中的安全性绝大部分都依赖于数论和代数的一些相关理论。本节将对一些 基本的数论和代数知识做简要介绍。 定理2 1 每个不等于1 的正整数均可分解为有限个素数的乘积；如不考虑因素在乘积 中的顺序时，则该分解方式是唯一的。 定义2 1 给定某个集合g 和该集合上的二元运算毒，称满足下述四个条件的代数系统 ( g ，木) 为群： 1 封闭性：若口，b g ，则必存在某个c g ，使得a 木6 = c ； 2 结合律成立：对于a ，b ，c g ，恒有 木b ) 水c - - a 宰( 6 木c ) ； 3 存在单位元g ：即存在p g ，对于v a g ，恒有口木p = p 水a = a ； 4 存在逆元：对于v a g ，恒有a * g 一! - , - - a 一1 木口= p ，则称a 一1 为口的逆元。 定义2 2 群g 的非空子集h ，若对g 的运算木也构成群，则称h 为g 的一个子群。 在上述条件下，如果群运算水满足交换律时，则称g 为交换群或a b e l 群：g 的元素 个数称为群g 的阶，记为o r d ( g ) ，并且有：v a g ，口删g ) = e 。阶为有限的群称为 有限群。如果存在群g 的元素g ，使得对群中的任意元素a ，都存在某个整数x ，使得 a = g j ，则称g 为循环群，g 称为g 的生成元，并且g = ( g ) 表示由g 可以生成g 的全 部元素。 关于有限循环群的一个重要结论是： 定理2 3 阶为素数的有限循环群g 中除了单位元e 以外，每个元素都是该群的生成 南京邮电大学硕士研究生学位论文第二二章数字现会的相关理论基础 定理2 3 阶为素数的有限循环群g 中除了单位元e 以外，每个元素都是该群的生成 元。因此如果给定g 的某个生成元g ，则任取0 w z 0 ( g 1 ( 或0 w o ，1 ) 钿们，如 果仅知道g 的阶的二进制串长度) ，通过计算g w 就可以得到另一个新的生成元g ，我们 将这种处理记为g 尺g 。除非特别说明，本文中后续章节中所涉及的计算均在有限循环 群g 口中进行，为了记述方便本文中省略模运算符( m o d p ) 。 定义2 3 域f 是至少含有两个元素的集合，在f 上定义两种二元运算+ 和木，称满足 下述条件的代数系统( f ，水，+ ) 为域： 1 f 的元素关于+ 运算构成a b e l 群，设其单位元为0 ； 2 f 的所有非零元素关于宰运算构成a b e l 群，设其单位元为1 ； 3 对于口，b ，c f ，分配律成立，即( a + 6 ) 球c = a 木c + b 术c 。 满足：1 1 = o 的最小正整数m 称为域f 的特征。如果特征为m 的域f 的元素个数 ( f 的阶) 有限，则称之为有限域或g a l o i s 域，记为g f ( 历) 。 定理2 4 设，的特征必为素数。 给定素数q 和j 下整数m ，存在唯一阶为q 册的有限域f ，该域成为有限域g f ( q ) 的 扩域，其特征也是q ，简记g f ( q 肌) 。 定义2 4 设口乏，如果存在某个x 乏使得x 2 三am o dn 成立，则称口为模f 的 二次剩余，称x 为a 模刀的平方根；否则成a 模即的非二次剩余。 z ：中所有模船的二次剩余的元素组成子集记为q ：所有模刀的非二次剩余的元素组 成子集记为q 。如果，2 为奇素数p ，则乏中恰有( p - 1 ) 2 个元素为模p 的二次剩余， 另一半的元素为模p 的非二次剩余。 如果即是两个奇素数p 和q 的乘积，则当且仅当a q ，a q 时，有口q ；并 且乏中模，2 的二次剩余元素个数和非二次剩余元素个数分别为：( p 一1 ) ( q - i ) 4 ， 3 ( p - 1 ) ( q 一1 ) 4 。 定义2 5 设n 为两个不同的素奇数p 和q 的乘积，且p 兰3r o o d8 ，q 言7 m o d 8 ， 则称n 为威廉整数。 定理2 5 设，z 为威廉整数，任取x 乏，则x ，一x ，2 x ，2 x 中有且仅有一个元素属于 南京邮电大学硕t ：j f 究生学位论文第二章数字现会的相关理论慕础 q ，其他三个元素属于q 。 定义2 6 设，2 为整数，称缈( 刀) 为刀的欧拉函数，妒( 刀) 的取值表示小于刀的数中与n 互素的数的个数。当，z 为素数时缈( 门) = 刀一1 ；当刀为两个素数p 和q 的乘积，则 缈( 甩) = ( p 一1 ) ( g 一1 ) 。 定理2 6 欧拉定理：对于小于n 且与1 1 互素的任何正数x ，有以下恒等式： x 矿( 以) m o d n 三1 。 2 2 数论困难问题 数论中的一些困难问题是现代密码体制中的安全基础。如果不存在能够利用有限资源 解出问题的算法，则称该问题为困难问题。尽管人们还无法证明针对某些困难问题的有效 解法一定不存在，但因为经过很多科学家几个世纪的努力始终没有找到解决这些问题的有 效算法，所以可以假设有效解决这些困难问题的算法不存在。下面我们介绍与本文相关的 数论困难问题。数字现金的支付系统安全性也正是建立在这些困难问题的基础之上。 2 2 1 因子分解问题 因子分解问题又称为大数分解问题，作为数论中最古老问题之一，是公认的难题。以 下是因子分解问题的一般定义。 定义2 6 因子分解问题：给定正整数刀，找到其因子分解，即确定不同的因子只和正 整数呼，使得刀= p p 露霄。 2 2 2 平方根与e 次方根问题 计算模数为合数的e 次方根问题是r s a 密码体制的基础。 定义2 7e 次方根问题：给定阶数未知的群g ，正整数1 e o r a l ( g ) 以及群中的任 一元素a g ，找到元素x g ，满足r = a 。 如果选择g = 乏，其中刀为两个不同的奇素数的乘积，且条件x g 修改为x 乙， 则p 次方根问题演变为r s a 问题。如果知道，z 的分解，则g 次方根问题也得到解决，也就 是说e 次方根问题不比因子分解问题更容易得到解决。反过来，目前还不能证明因子分解 问题比p 次方根问题更困难。 特别地，如果e = 2 则得到如下所述的平方根问题。 q 南京邮电大学硕上研究生学位论文 第二章数：现企的相关理论皋础 定义2 8 平方根问题：给定阶数未知的群g 以及群中的任一元素口g ，找到元素 x g ，满足x 2 = a 。 2 2 3 离散对数问题 密码学的众多协议几乎都是以离散对数困难问题作为其理论基础的。 定义2 9 令g 是有限循环群，g g 为群的某一生成元。元素a g 关于g 的离散对 数是一个满足a = g x 的整数x ，0 x z ( g ) ，记为l o g g a 。 普通对数的一些结论在离散对数中也成立。假设有限循环群g = ( g ) 的阶为力，a 、b 和c 是g 的元素，则有： l o g ga b 兰l o g ga + l o g gb ( m o d n ) ( 2 1 ) 并且对于任意正数x ，有： l o g ga j - x l o g ga ( m o d n ) ( 2 2 ) 2 3 加密解密的基本原理 2 3 1 消息和加密 消息( m e s s a g e ) 被称为明文( p l a i m e x t ) 。用某种方法伪装消息咀隐藏它的内容的过程称为 ；i j i 密( e n c r y p t i o n ) ，被加密的消息成为密文( c i p h e n e x t ) ，而把密文转换为明文的过程称为解 密( d e c r y p t i o n ) 。图2 1 标明了这一过程。 图2 1 加密和解密 明文和密文分别用m 和c 表示，加密函数e 作用于m 得到密文c ，可用如下的数 学公式表示： e ( m ) = c( 2 3 ) 相反地，解密函数d 作用于c 可以产生明文m ： d ( c ) = m( 2 4 ) 由上述两式容易得知以下公式也一定成立： d ( e ( m ) ) = m( 2 5 ) 1 n 南京邮电火学硕士研究生学位论文第二章数字现金的相关理论基础 2 3 2 算法和密钥 如果加密算法的可靠性是依赖于保持算法的秘密，那么这个算法是受限制的。一个大 的或者是经常有成员变动的组织不可能使用它，因为一旦有成员离开这个组织，其他的成 员必须改变算法。更糟糕的是受限制的算法不可能进行质量控制和标准化。现代密码学用 密钥( k e y ) 来解决这个问题，密钥用k 来表示。k 的取值范围叫着密钥空间。这样加密解密 函数变成： 色，( m ) = c( 2 6 ) 反( c ) = m( 2 7 ) 上述两式中，当k 和心取值相同时则称算法为对称式加密算法取值不同时称之为非对称 式加密算法( 也叫公钥算法) 。加密解密流程见图2 2 。 图2 2 带密钥的加密与解密 公开密钥算法的原理是基于单向陷门函数的，这种函数的值不难计算，但除非知道陷 门，否则逆向计算将非常困难。例如给定函数f ：ajb ，如果其陷门( 私钥) 存在，则 该函数可以作为公钥，从而对消息m a 的加密就是f ( m ) ，解密即为f 叫( ( m ) ) = m 。 由于公钥密码体制用公钥和私钥分别用于加密、解密过程，从而可以实现多个用户使用某 个用户的公钥加密信息而只能由密钥的所有者用自己私钥解密的功能。这样大大提高了算 法的灵活性。但是在相同的安全强度下，公钥密码体制的硬件实现比对称密码体制要慢1 0 0 倍，所以公钥算法一般不会直接应用于直接的加密解密，一般用于对称式密钥的交换。 2 3 3r s a 算法 r s a 是目前应用最为广泛的一种公钥加密算法，该算法已经经过了多年密码分析者的 分析，虽然密码分析者不能证明它的安全性，但是同时也不能否认它的安全性，因此在现 实意义上可以认为它有足够的安全可信度。其原理如下： 1 选择两个大的素数p 和q ( 5 0 0 比特以上) ，计算，z = p 术q ； 2 计算欧拉函数：缈( 刀) = ( p - 1 ) ( q - 1 ) ； 3 选择一个与缈( ，2 ) 互素的正数p ，使其满足g c d ( e ，汐( ，z ) ) = 1 ) 和1 p 缈( ，z ) ，e 1 1 南京邮电人学硕a ：j i j f 究生学位论文第一二章数现会的相关理论基础 常取6 5 5 3 7 ，将k 口= ( 聆，e ) 作为公钥，将k = ( f , d ) 作为私钥； 4 求出正数d 使其满足2 木d - - l m o d 缈( n ) ，l d 够( 聆) ，将作为私钥； 5 加密过程：对明文m 作变换c = 反。( m ) = m 8m o d n ，从而得到密文c ： 6 解密过程：对密文c 作变换m = o g ( ) = d ，从而得到明文 。 使用 加密算法应该着重注意以下几点$ ：c cm o d n mrsa 1 不能泄漏解密密钥或欧拉函数值以及所使用的2 个素数； 2 不同用户不可使用相同的( 模n ) ； 3 不同用户使用的素数不可相重； 4 密钥( 模，z ) 应足够长，使得因子分解非常困难； 5 解密密钥应该大。 2 3 4h a s h 函数 h a s h 函数又叫单向散列函数或哈希函数，其功能是作用于一任意长度的消息m ， 返回一固定长度的散列值c ：c = ( m ) ，其中c 的长度为，。 输入任意长度且输出为固定长度的函数有很多种，但单向散列函数还需要具有以下特 性： 1 公开性：h ( ) 的描述是公开的，其处理过程无需保密； 2 单向性：给定m 很容易计算c ，但是根据c 无法反向逆推出m ； 3 抗碰撞性：要找出两个随机消息m 和m ，使h ( m ) = h ( m ) 很困难。 h a s h 函数可以使用密钥控制，也可以不使用密钥控制。前者的散列值不仅与消息 有关，还与发送者的密钥有关，因而具有身份认证功能：后者仅能用于检测消息的完整性。 根据函数设计方法可以将h a s h 函数分为以下两大类： 1 基于复杂性理论专门设计的h a s h 函数，如s h a 、m d 4 、m d 5 等算法： 2 采用分组密码构造的h a s h 函数，如m d c 2 、m d c 4 ，基于i d e a 的平行、串 接和并接等。 2 4 数字签名 为了鉴别文件或者书信的真伪，传统的做法是相关人员在文件或书信上签署自己的名 字，签名起到认证、核准、生效的作用。信息时代的到来，人们希望能够通过数字通信网 1 2 南京邮电火学硕士研究生学位论文 第二章数7 现金的相关理论幕础 来传递合同，数字签名技术应用而生。根据i s 0 7 4 9 8 2 的定义，数字签名可以理解为：附 加在数据单元上的一些数据，或是对数据单元所作的密码变换，这种数据和变换允许数据 单元的接收者用以确认数据单元来源和数据单元的完整性，并保护数据，防止被人( 例如 接收者) 进行伪造。一个可靠的数字签名机制通常必须具有以下三个特点： 1 接收者能够核实发送者对报文的签名： 2 发送者事后不能抵赖对报文的签名： 3 接收者不能伪造对报文的签名。 数字签名算法有很多种。例如，r s a 数字签名算法，e i g a m a l 数字签名算法，f i a t s h a m i r 数字签名算法，s c h n o r r 数字签名算法，美国数字签名标准算法( d s s d s a ) 以及 椭圆曲线数字签名算法等。限于篇幅本文仅对应用最为广泛的r s a 数字签名作介绍。 2 4 1r s a 数字签名 r s a 数字签名算法使用公钥密码技术实现数字签名。签名和验证过程如下： 1 发送方彳签名过程： 发送方彳用其不公开的解密密钥( 私钥) a k ，对报文膨进行运算，结果 c = d ( m ，似，) ，这就表示报文m 已经被彳电子签名了。将c 传给接收方b 艮p - i 。 2 接收方曰验证过程： 召用已知的加密密钥( a 的公钥) a k 口，对收到的内容c 进行运算，得出结果 e ( c , a x p ) = e ( d ( m ，a k s ) ，a k , ) - - m 。 由上述过程很容易得知r s a 签名过程有如下特点： 1 签名是可信的：由于接收方b 收到的密文用发送方彳的公钥可以解密，故必定是彳 的私钥加密的。因而是可以信任的，不必怀疑； 2 签名是不可伪造的：如果接收方b 将m 伪造成m ，则b 不能在仲裁方面前出示 m = e ( c ，a x , ) ，从而证明b 伪造了报文； 3 签名的文件是不可改变的( 保证完整性) ：如果接收方j 5 f 将签名的文件m 修改成 m ，则b 不能在仲裁方面前出示m 。= e ( c ，a k p ) ，从而证明b 修改了报文，这就保证 了签名文件的完整性。 2 4 2s c h n o rr 数字签名 选择大素数：p 、q ，且q i p 1 ) ，即q 是j p 一1 的素数因子。然后选择a ( a 1 ) ，满 足a q 三1m o dp 。所有这些数可以由一组用户共用，并公开发布。为了产生特定的公丌 1 3 南京邮电人学硕上研究生学位论文第二章数字现金的相关理论桀础 密钥私有密钥对，选择一个小于q 的随机数s 作为私有密钥，计算v = a 吖m o dp 作为 公开密钥。s c h n o r r 数字签名算法遵循以下步骤( 假设签名的发送方为彳，接收方为b ) ： 1 彳选取一个小于q 的随机数厂，并计算x = a m o dp ； 2 a 将消息m 与x 连接起来，并对其进行哈希运算得到散列值e - - - h ( m ，x ) ； 3 a 计算y = ( 厂+ s e ) m o dq ，并将e 和少作为签名发给b ； 4 b 计算x 。= a y v 8m o dp ，然后计算值e - - - h ( m ，x ) ，比较e 和e 的值，如果 相同则证明签名有效。 s c h n o r r 数字签名所需要的大部分计算都可以在预处理阶段完成，并且这些计算与签名 信息无关，可以在计算机的空闲时间内进行，并且不会影响签名速度。对于相同的安全级， s c h n o r r 的签名长度比r s a 更短。 2 4 3 盲签名 在一些强调隐私的场合，如电子投票系统、网上拍卖和数字现金支付，除了要强调一 般数字签名的不可抵赖性、不可更改性、不可伪造性和可仲裁性等特点之外，还应该满足 下述两个条件： 1 待签名文件对签名者来说是不可见的，即签名者并不知道他所签署消息的具体内 容； 2 签名是不可跟踪的，即当消息及其签名被其所有者公布以后，签名者无法知道这是 他那一次签名过程产生的。 为了更好地理解这一签名过程，可以做个比喻：接收者在待签文件上放一张复写纸将 他们一起装到一个信封内并交给签名者，签名者在信封表面上签名后复写纸在待签文件上 留下了他的签名。基本原理如图2 3 所示： 图2 3 盲签名协议原理 1 4 南京邮电人学顾i j 研究生学位论文 第二章数宁现金的相关理论基础 2 5 反馈机制 反馈理论勒广泛的应用于生物学和自动控制等领域，分为正反馈和负反馈两种类型。 正回馈是指作用后产生的效应是加强、增加的；负回馈则完全相反，产生的效应是降低、 减少的。在自动控制领域可以这样定义：把输出信号的一部分或全部送回输入端，以改变 放大性能的放大电路。由输出端送回输入端的信号称为反馈信号。反馈信号在输入端与外 加信号相加( 或相减) 组成放大器的净输入。当反馈信号使净输入增强从而使放大器增益 提高时，称为正反馈。当反馈信号使净输入减弱从而使增益下降时，称为负反馈。在一个 输入输出系统中设定值为d e f a u l t ，反馈为r e a c t i v i t y ，输入为i n p u t ，输出为o u t p u t 。则正 反馈和负反馈系统可以用公式2 8 和公式2 9 表示。 正反馈：d e f a u l t + r e a c t i v i t y = i n p u t ( 2 8 ) 负反馈：d e f a u l t r e a c t i v i t y = i n p u t ( 2 9 ) 2 6 局部性原理 局部性原理n 刚广泛地应用于工程领域，在计算机科学中，局部性原理的最常见应用就 是程序的局部性原理。根据统计，进程运行时，在一段时问内，其程序的执行往往呈现出 高度的局限性，包括时间局部性和空间局部性： l 、时间局部性：是指若一条指令被执行，则在不久的将来，它可能再次被执行； 2 、空间局部性：是指一旦一个存储单元被访问，那它附近的单元也将很可能被访问。 程序的局部性原理是指程序总是趋向于使用最近使用过的数据和指令，也就是说程 序执行时所访问的存储器地址分布不是随机的，而是相对地簇集，这种簇集包括指令和数 据两部分。其原因可以做如下解释：由于程序中具有大量的循环结构，因此一条指令被执 行后，很可能因为循环在较短时间内被反复执行，因此有了时间上的局部性；在程序中还 存在大量的数组，由于数字的地址空间是连续的，当数字中的某一个元素被访问，数字中 其他元素被访问的可能性就大大增强，因此导致了局部范围的存储器地址被频繁访问，从 而有了空间局部性。 由此，我们可以大胆做一个推论，认为向商家购买商品的用户信用状况也满足局部 性原理。试想一个商家所售的商品其种类和购买对象都是相对集中的，用户的消费习惯和 社会地位、收入教育状况有一定的趋同性，因此用户的信用状况也有一定的趋同性，也就 查塞堕皇叁兰堡主塑塞圭堂篁堡茎笙三童鏊兰堡全塑塑菱堡垒苎型 是说用户的信用状况满足空间局部性。同时，在某一段时间内，整个社会的经济环境和法 制环境会有一个较为稳定的持续过程，如在经济持续增长的情况下，国民收入稳步提高， 公民进行经济犯罪的可能性会随之降低，此时信用状况也会随之提高。在法制环境较为严 厉的情况下，如前些年我国大力提倡建设诚信社会的大背景下，各种经济诚信的法律法