CN1262830A

CN1262830A - 基于要求随机数绘制的密码系统的散列编码函数的伪随机发生器

Info

Publication number: CN1262830A
Application number: CN 98806980
Authority: CN
Inventors: D·纳卡希; D·穆赖希; F·莱维－蒂特－维赫尔
Original assignee: Gemplus SCA
Current assignee: Gemplus SA
Priority date: 1997-05-07
Filing date: 1998-05-05
Publication date: 2000-08-09
Also published as: WO1998051038A1; FR2763194A1; JP2001507479A; AU7659598A; EP0980607A1; CA2288767A1; FR2763194B1

Abstract

本发明涉及一种密码系统,该系统通常需要提取随机数k(k为整数)。该系统其特征在于通过用值h(m丨secret)代替所述随机数k来操作该系统,其中h是散列编码函数、m是所述系统中的消息插入和“secret”是密码系统之外的世界所未知的秘密。本发明特别用于诸如智能卡、PCMCIA卡、标记卡、非接触卡的通信媒体或任何其它的便携式媒体。

Description

基于要求随机数绘制的密码系统的散列编码函数的伪随机发生器

本发明描述了一种系统，该系统使得缺乏允许随机数绘图的硬件或软件资源的签名或加密设备(典型的是微处理器)有可能产生需要随机数绘图的数字签名或密码(典型的是签名的DSA、E1-Gama1、Fiat-Shamir和Guillou-Quisquater，加密的E1-Gama1和McEliece)。

本发明还提供一种防止由廉价便宜产生随机序列的某种威胁(典型的是短消息的加密和在Eurocrypt′96由Coppersmith等的“相关消息的低次幂”和“寻找单变量模块化等式的小方根(small root)”的文章里公开的新的攻击)的应答或保护，该威胁使得该随机序列有可能加入到要处理的信息中。

本发明还允许模糊因子的产生，在空白签名的上下文中或随机伪装机构中使用该模糊因子。

最后本发明可用于Diffie-Hellman类型的密钥交换协议中。

尽管在公众方面智能卡概念已经广泛分布和愉快接收，但大规模的实际使用只在几年前才出现，主要由于卡的计算能力的限制。关于信息的非易失性存储容量的进步，提出了安全性和电路技术(例如EEPROM)，很快出现了新一代卡和诸如新的美国数字签名(DSA)标准的越来越雄心勃勃的应用。

作为媒体的智能卡实现公开密钥算法的最大限制在于必须(经常遭遇)在卡片上具有产生随机数的设备。这是因为完善这种设备(也称作发生器)证明是复杂而又经常是不稳定的(对诸如环境温度或卡所用电压的卡外部现象灵敏)。在计算机上实现这种密码系统，由软件随机发生器的特性引起的其它现象模糊随机数的质量。典型地，一个非常流行的产生随机数的方法包括测量由用户按两次键盘之间所经过的时间。近来的犯罪案例表明可以通过欺诈设备激励键盘使这种发生器出现偏差，攻击者通过该欺诈设备得知各次击键之间所经过的时间。

本发明建议一种允许实现密码系统的替代解决方案，该密码系统需要在软件或硬件平台上高质量的随机数绘图：

1.不拥有任何随机数发生装置，

2.或产生低质量的随机数，

3.或当系统设计者怀疑外部因子通过修改外部和内部操作状态可以破坏随机数的质量时。

本发明用于加密算法的各种系列。为了更好地理解本发明和在仔细阅读描述中权利要求书的内容之前，回想本发明所用的所述加密算法系列的主要特征是有用的，这些算法的数目是六个。

第一应用系列涉及E1-Gama1类型的签名方案。

正如在名称为“基于离散对数的公开密钥密码系统和签名方案”和在期刊IEEE信息理论学报，1985年第4期，卷IT-31，第469-472页公开的文章里所描述的，E1-Gama1签名算法导致一些著名的签名算法：参考4,995,082在美国获得专利权的Schnorr，或GOST 34-10-俄罗斯联邦数字签名标准；DSA-美国数字签名标准。

一旦在DSA的上下文中说明了，本领域技术人员可以很容易地将本发明用于同一系列的其它算法。

此后，它称作DSA算法。

由美国标准和技术协会建议的数字签名标准(DSA，名称为“数字签名算法“的美国专利5,231,668)以便为需要数字签名代替传统签名的应用提供合适的基础。DSA签名是计算机中由二进制数字串表示的两个大数。通过一系列计算规则(DSA)和一组参数以有可能证明签名人身份和数据完整性的方式计算数字签名。DSA使得产生和验证签名成为可能。

签名产生方法利用私人密钥(为了产生数字签名)。验证方法使用相应于保密密钥但不相同的公开密钥。每个用户拥有两个密钥(公开、保密)。假设所有人都知道公开密钥而保密密钥不公开。任何人都能用用户的公开密钥而不是使用用户的保密密钥验证其签名但不能产生签名。

DSA的参数是：

1.质数模数p，其中2^L-1＜p＜2^L，512≤L≤1024，L＝64α，α为任何值。

2.质数模数q，其中2¹⁵⁹＜q＜2¹⁶⁰，p-1是q的倍数。

3.数g，阶q模p，其中g＝h^(p-1)q模p，其中h是1＜h＜p-1的任何整数。

4.数x，随机或伪随机产生。

5.数y，由关系式：y＝g^x模p定义。

6.数k，随机或伪随机产生，其中0＜k＜q。

整数p、q和g是能被公开系统参数和/或由一组用户共享。签名的保密和公开密钥分别是x和y。用参数x和y产生签名并必须保密。必须为每个签名重新产生参数k。

为了签名消息m(初始文件M的散列值)，签名者用：

r＝g^k模p模q和s＝(m+xr)/k模q

计算签名(r，s)，其中除以k理解为模q(即，1/k是数k′，kk′＝1模q)

例如，如果q＝5和k＝3，则1/k＝2，因为3×2＝6＝1模5。

正如在DSA的描述中所解释的，在测试r和s≠0之后，签名(r，s)发送给检验器，该检验器计算：

1.w＝1/s模q

2.μ₁＝mw模q

3.μ₂rw模q

4.v＝g^μ1y^μ2模p模q

5.和比较v和r是否相等以便接收或拒绝签名

第二系列也涉及签名方案；这些方案是从零公开协议中得到的方案。

本发明所应用的第二系列签名算法是从零公开协议(典型的是序列号分别为4,748,668和5,140,634的在美国获得专利的Fiat-Shamir或Guillou-Quisquater)中得到的方案。另外，只描述其中一个协议，一旦用到Guillou和Quisquater算法，对于本领域技术人员来说本发明扩展到该系列的其它算法证明是不言而喻的。

Guillou-Quisquater算法的参数是：

1.两个大小至少等于256比特的保密质数p和q，以特定方式产生这些质数，对理解本发明没有必要的细节可以在Thomson出版的Bruce Schneier的著作(由Marc Vauclair翻译)“应用的密码、算法、协议和源代码”中找到；

2.公开模数n＝pq和表示签名者身份的串ID；

3.公开指数v和保密密钥B，其中B′ID＝1模n；参数B必须保密；

4.为了签名消息m，发送者写下随机数k，计算最初的标记符T＝kv模n并产生签名：

d＝h(T，m)和D＝kB^h(T、m)模n

5.检验器通过验证：

d＝h(T′，m)来确定签名的真实性，其中T′＝D^vId^d。

第三应用系列涉及需要随机数的公共密钥加密方案。

随后描述的需要随机数的第一加密算法是E1 Gamal。

该算法的参数是：

1.指数模数p(至少512个比特)；

2.数g，阶p-1模p(即，其中对于任何整数u，0＜u＜p-1，gu≠1模p)；

3.数x，1≤x≤p-2，随机或伪随机产生；

4.数y，由关系式：y＝g^x模p

5.数k，随机或伪随机产生，0＜k＜q；

整数p和g是能被公开的系统参数和/或由一组用户共享。公开加密密钥是数y，和保密解密密钥是数x。

参数k用于产生密码，并不能被泄露。而且，在每次加密都必须重新产生参数k。

消息m(0≤m≤p-1)的加密是整数对(r，s)，其中：

r＝g^k模p和s＝my^k模q

为了恢复消息m，密码的接收者(其拥有x)计算：

s/r^x模p

这就是精确的m。

需要产生随机数的第二加密算法是McEliece方案，该方案基于码理论问题，更精确的说是使用名称为Goppa码的一类特殊码。通常的想法是把Goppa码伪装为线性码；这是因为存在有效的算法解码Goppa码，但另一方面解码一般的线性码是困难的问题。因此知道有可能伪装码的信息的接收者可以通过解码得到的Goppa码来解密消息。

McEliece算法的参数(下面所有的公式理解为在GF(2)中)是：

1.数n、k和t，系统参数；在描述其加密方案的原始文本中，McEliece建议n＝1024、t＝50和k＝524；

2.保密密钥包括：

*纠正t个错误的大小为n和维数为k的二进制Goppa码的发生器矩阵G和相应的解码算法；

*k×k维随机可逆矩阵S；

*大小为n的随机置换矩阵P；

3.相应的公开密钥包括：

*码等于G的发生器矩阵T＝SGP；

纠正率t；

4.通过计算用McEliece算法对k比特消息m的加密：

c＝mT+e

其中e是随机选择的等于t的汉明加权的误差矢量。

c的解密通过计算：

cP^-1＝mTP^-1+eP^-1＝mSG+eP^-1来执行。

因为e是加权t，eP^-1也是加权t。因此用码G可以纠正矢量cP^-1。通过解码，解密器得到mS，接着得到m，因为解密器知道S并且S是可逆的。

第四系列涉及需要随机填充的密码方案。

要加密的数据项必须首先填充是很平常的，例如增加以便得到固定长度的数据项。可以通过RSA加密的例子给出这个方面的说明，RSA加密由R。Rivest、A.Shamir和L.Adl eman于1978年发表，并以“密码通信系统和方法”的名称获得专利权，参考US 4,405,829。

RSA密码是计算机中用二进制或十六进制数字串表示的大数。使用一系列计算规则(加密算法)通过软件计算资源(程序)和/或硬件计算资源(电子电路)计算该密码，在处理所有人都可得到的一组参数时使用该计算规则以便隐藏所处理数据的内容。以类似的方式，使用一系列计算规则(解密算法)通过软件或硬件计算资源解密密码，该计算规则(由密码的接收者)用于一组保密参数和密码。

加密方法使用公开密钥以便产生密码。解密方法使用相应于保密密钥但不相同的公开密钥。每个用户拥有两个密钥(公开、保密)并假设所有人都知道公开密钥而保密密钥不公开。任何人都能用用户的公开密钥而不是使用用户的保密密钥加密用户的消息但不能解密密码。

RSA算法的参数是：

1.两个大小至少为256比特的保密质数p和q。以特定方式产生这些质数，对理解本发明没有必要的细节可以在Thomson出版的Bruce Schneier的著作(由Marc Vauclair翻译)“应用的密码、算法、协议和源码”中找到；

2.公开模数n＝pq；

3.一对表示为(e，d)的指数如：

ed＝1模(p-1)(q-1)

所有人都能得到称作“加密指数”的指数e，但“解密指数”d必须保密。

为了加密消息m，发送者计算密码c＝ms模n和接收者通过计算m＝cs模n解密c。

为了尽可能地选择参数，在加密模数大小的消息和不处理加密信息的发送者与接收者之间特定关系的通常情况下，基于因数分解问题算法的安全性允许在加密信息的发送者和接收者之间提供机密性。

另一方面，由Coppersmith等在Eurocrypt′96(在Springer-Verlag会议进行过程中公开的著名的“相关消息的低次幂”和“寻找单变量模块化等式的小方根(smallroot)”，参考LNCS1070)提出的新的攻击表明在用一个和相同的小指数加密的消息之间存在的多项式关系允许反映为清楚文本的有效攻击，在多项式关系中在通常使用用于加密的加密设备的应用的上下文之间经常出现，由于性能原因公开指数e＝3。

一种可能的解决方案是用随机序列填充消息(但不采取特定的预防措施)或打破消息间的各种关系，该解决方案依赖于应用而且并不一定总是可能的解决方案。

在步骤4介绍下面的修改。

为了加密消息，发送者产生具有一定程度随机性的序列sr并计算密码c＝(m|s_r)e模n，符号|表示级联；接收者通过计算cd模n解密c和通过删除填充字符恢复m。

填充消息的正确方法依赖标准、应用条件或所需的安全性程度而改变。

第五系列涉及模糊因子和空白签名。

在许多密码协议和方案中使用的被本领域技术人员称作原语的基本功能是给定消息的空白签名机理。这种由Chaum公开和获得专利权的功能(美国专利4,759,063和欧洲专利0139313)使得有可能获得签名的消息而不要要签名者能阅读该消息。该功能需要产生只有签名的请求者知道的模糊因子，该模糊因子有可能隐藏消息。所用的机理对于E1 Gama1类型的签名系统和对于RSA的签名系统同样好。

一旦在RSA的上下文中说明后，对本领域技术人员来说本发明应用到其它的签名算法是不言而喻的。这里只描述基于RSA的空白签名机理。

再次使用在描述本发明第四应用系列的上下文中所用的符号，由此定义RSA签名：

s＝m^d模n

通常这样进行进行验证：

s^e模n＝(m^d)^e模n＝m

由消息m的发送者E得到空白签名的步骤是：

1.E产生随机数k，计算模糊因数ke模n并向接收者(或签名者)发送m′＝mk^e模n；

2.接收者计算m′的签名s′＝m′d模n并把s′发送给E。

3.E计算s′/k＝(mk^s)d/k＝m^dk^sd/k＝m^d模n，并由此得到m的签名s。

乘以模糊因子的这项技术也用于随机隐藏的上下文中(欧洲专利申请EP 91402958.2)。

随机隐藏的方法例如用于设备A希望与设备B转包合同操作但不希望操作数完全显露给设备B。例如采用模数减法操作：A可以通过将其乘以模数的随机倍数把该数伪装为减少的模n。因此，如果A希望得到c＝ab模n，其可以产生随机数k，计算c′＝ab+kn(kn伪装产品ab)，并把c′发送给设备B用于减法。

设备B计算c′模n＝ab+kn模n＝c。

最终该技术使得建议对在Crypto′96描述的Kocher攻击(在Springer-Verlag公布的会议进程中“对实现Diffie-Hellman、RSA、DSS和其它系统的定时攻击”，参考LNCS 1109)的应答成为可能，该攻击基于测量操作保密幅度的操作所需的时间以便猜测其值本身。

这是因为有效应答是由模糊因子操作的保密幅度的操作以便解相关计算时间和幅度。例如在RSA签名的情况下(本领域技术人员都知道如何把该结果扩展到攻击所涉及的所有的算法，值得注意的是所有那些要求用保密密钥处理模数指数的计算)，再次使用在描述本发明第四应用系列的上下文中所用的符号，它满足：

1.签名者产生随机数k并计算

d′＝d+k(p-1)(q-1)

2.接着该签名者通过计算：

m^d′＝m^{d+k(p-1)(q-1)}＝m^d(m^(p-1)(q-1)k＝m^d模n产生m的签名

第六系列涉及基于Diffie-Hellman方法的密钥交换方案。

在IEEE信息理论学报，卷IT-22，第6期公开的并在美国获得专利(参考4,200,770)的“密码学的新方向”所描述的第一个公开密钥算法。该方法利用希望通过非保密信道对保密信息取得一致的两个参与者(或设备)。

Difie-Hellman协议的参数如下：

1.发送设备(A)和设备(B)取得一致的两个公开参数：至少512比特的质数p和为模p原根的整数g。可以在一组用户中共用这两个参数。

协议过程如下：

为了共享保密信息，两台设备执行如下操作：

*设备A产生随机数x并计算幅度X＝g^x模p；

*设备B产生随机数y并计算幅度Y＝g^y模p；

*两个设备彼此交换量X和Y；

*设备A计算key＝Y^s模p；

*设备B计算key′＝X^y模p。

因此这两个设备在协议终端共享量key′＝key＝g^xy模p的知识。

随后这两个设备通过把量“key”和要加密的消息作为参数的对称加密算法可以使用保密量“key”以便通过保密信道彼此交换消息。

在描述本发明的不同应用系列后，希望指出本发明的主要优点。

关于智能卡市场的经济限制需要持续研究以便改进生产成本。该努力经常通过使用最可能简单的产品来进行。该既成事实导致一种重要性逐渐增加的解决方案，该方案使得在便宜的8比特微控制器上实现公开密钥算法成为可能，例如在微控制器的中心具有80C51或68HC05。

在数字签名或加密方面，本发明相对于以前的建议具有的主要优点在于虽然签名或加密电路上没有随机数发生器，也具有计算签名或执行加密操作的能力。

为了清晰起见，有必要指定所提出的各种系统密钥和参数的产生保持一致。因此将参考已有的著作和专利以便尽可能好地产生对本发明提出的签名鉴别和加密算法有必要的各种元素。一本实用参考书是Thomson出版Bruce Schneier(由Marc Vauclair翻译)的“应用的密码、算法、协议和源码”。

本发明涉及一种密码系统，通常需要随机数k的绘图，该随机数是整数；该系统其特征在于通过用量h(m|secret)替代所述随机数k来实现该系统，其中h是散列函数、m是在所述系统出现的消息和“secret”是密码系统之外的世界所未知的保密项。

更精确的，本发明的密码系统至少包括：

-公开密钥签名系统；

-公开密钥加密系统；

-随机填充系统；

-模糊因子产生系统；

-密钥交换协议。

在密码系统包括DSA、Schnorr、E1-Gama1、GOST 34.10或IEEEECDSA椭圆曲线标准类型的公开密钥签名系统的情况下，由签名者在用量h(m|x)替代每个签名时更新随机数(k)，其中x是签名者的保密密钥。

在密码系统包括Fiat-Shamir或Guillou-Quisquater类型的公开密钥签名系统的情况下，由签名者在用量h(m|B)替代每个签名时更新随机数，B是签名者的保密密钥和m是要签名的消息。

在密码系统包括E1 Gama1类型的公开密钥加密系统的情况下，由加密者在用量h(m)替代每个发送的加密消息时更新随机数(k)。

在密码系统包括McEliece类型的公开密钥加密系统的情况下，从量h(m)得到由加密者在每次加密时更新的随机误差矢量e。

在密码系统包括出现在公开密钥加密系统的随机填充系统的情况下，加密者拥有解密者未知的密钥σ并根据下列步骤执行消息填充：

a.产生尽可能多的k_i＝h(m|σ|i)以使级联k_is的长度至少等于模n大小的1/6(例如RSA加密的情况下)，或产生k＝h(m|σ)并将其扩展；

b.形成m^r，其中m^r＝SIZE(m)|m|(k_i)；

c.加密m^r替代m。

在密码系统包括在空白签名产生或随机伪装操作的上下文中产生模糊因子的系统的情况下，用量h(m|σ)替代由发送者在每次模糊或伪装操作时更新的随机数(k)。

在密码系统包括Diffie-Hellman类型密钥交换协议的情况下，希望发送消息m的设备使用量h(m|σ)而不是随机保密项，其中σ是保密数据项。

在该密码系统相同的情况下，所述协议至少包括以下步骤：

a.第一设备希望发送消息m，计算b₁＝g^h(m|σ)模p；

b.第二设备(接收者)产生随机数a并计算b₂＝g^a模p；

c.两台设备交换b₁和b₂，并计算密钥key＝g^ah(m|σ)模p；

d.第一设备加密c＝f(m，key)，其中f是对称加密机制；

第一设备发送c到将其解密并恢复m的第二设备。

最好，通信设备是智能卡、PCMCIA卡、标记卡、非接触卡或任何其它的便携式设备。

最好，通过交换电信号、无线电波或红外线信号完成实现本发明的所述设备间的通信。

随后，以更详细的方式描述本发明，再次采用描述应用系列所实用的符号。

如上所述，由散列操作h产生随机数的想法。对于本发明的前两个应用系列，h将用作保密数据项(即签名者的保密密钥)、公开数据项、要签名的消息的参数。

对于第三系列，h将只用作要签名的消息的参数。

最后，对于其它系列，h将用作公开数据项和保密数据项的参数(此后表示为σ)。

更精确地：

-对于涉及所述E1 Gamal类型签名方案的第一系列，随机数k按照如下产生：k＝h(m|x)，其中m是要签名的消息M的散列和x是签名者的保密密钥。以与原始方法相同的方式执行产生签名(r，s)的剩余步骤。同样，对所产生的签名的验证保持不变。

-对于涉及从零公开协议中得到所述得到所述签名方案的第二系列，k按照如下产生：k＝h(m|B)，其中m是要签名的消息M的散列和B是签名者的保密密钥。以与原始方法相同的方式执行产生签名(d，D)的剩余步骤。同样，对所产生的签名的验证保持不变。

-对于涉及需要随机数的所述加密方案的第三系列，要考虑两种情况：

1.E1 Gamal加密情况：

-随机数k按照如下产生：k＝h(m)，其中m是要加密的消息。接着以上述方式执行E1 Gamal算法。解密还保持不变。

2.McEliece加密情况：

-不是从随机数中得到误差矢量e，而是从h(m)中产生该矢量，其中m是要加密的消息。值得注意的是e必须正好是汉明加权t。一种从h(m)中得到大小为n(所考虑的码的大小)和加权为t的矢量的方式如下：

-假设大小为n和加权为t的矢量已经排序。接着可以把该表中位置为h(m)(或从h(m)得到的位置，因为该数可以超过根据t，n的二项式(t，n)和所用的散列函数)的矢量选为矢量e。

接着以上述方式执行McEliece算法。解密还保持不变。

而且，该产生e的方法使得有可能解决两次加密相同消息的问题。事实上，在通用McEliece的情况下，加密相同的消息两次(并因此具有两种不同的误差矢量)是不明智的，因为有可能猜测部分误差矢量媒体，随后更容易恢复清楚的消息。

通过本发明e的产生，相同的消息总是具有相同的加密。

本发明以下面的方式应用到第四系列，该系列涉及需要随机填充的密码方案：

-按规定，一种明智的安全措施是用随机序列填充消息。但是如果序列随相同消息的多次加密而改变，则又会出现显示清楚消息的攻击。

使用产生随机数的确定方法使得有效停止这类现象成为可能。这是因为通过尽可能多次地增加消息m(填充长度必须至少是n大小的1/6，因为传统模数大小在512到1024比特之间所以该填充长度在86到171比特之间)值ki＝h(m，σ，i)，σ是至少128比特的保密数。因为消息之间不再有任何联系而且加密多次的相同消息总是具有相同的填充。所以所有的攻击都不可能。接着由发送者按如下执行消息m的加密：

1.产生尽可能多的ki＝h(m|σ|i)以使级联kis的长度至少等于n大小的1/6；还可以最好使用单个k＝h(m|σ)，接着在将其与消息级联前扩展k；

2.形成m_r，其中m_r＝size(m)|m|(kI)；

3.计算密码c＝m_r ^e模n以使接收者通过计算mr＝cd模n来解密c。

得知m的大小和因此知道mr的有效比特，接着接收者简单地提取m。

对于涉及模糊因子和空白签名的第四系列，要考虑三种情况：

1.空白签名的情况：

-k按照如下产生：k＝h(m|σ)，其中m是要签名的消息和σ是保密数据项。以与原始方法相同的方式执行产生空白签名的剩余步骤。同样，对m的签名的提取保持不变；

2.随机伪装情况：

-k按照如下产生：k＝h(a|b|σ)，其中a和b是要加倍的操作数和σ是保密数据项。以与原始方法相同的方式执行随机伪装操作的剩余步骤。同样，由接收者对c′的模数减法保持不变；

3.保护基于测量处理时间的攻击的机制情况：

-在例如RSA签名的情况下，按照如下产生(p-1)(q-1)的随机倍数k：k＝h(m|σ)，其中m是要签名的消息和σ是保密数据项。以与原始方法相同的方式执行伪装指数(d′＝d+k(p-1)(q-1))操作的剩余步骤。

本发明以下面的方式应用到第六系列，该系列涉及基于Diffie-Hellman方法的所述密钥交换方案。

在Diffie-Hellman类型的密钥交换系统，希望发送消息m的设备不使用随机数而是使用量h(m|σ)，其中σ是固定的保密数据项。很明显本方法可以自然扩展到协议中所有的参与者。后者至少具有下面的步骤：

*希望发送消息m的第一设备，计算X＝gh(m|σ)模p；

*第二设备(接收者)产生随机数y并计算Y＝gy模p；

*两台设备交换X和Y，并计算密钥key＝g yh(m|σ)模p；

*第一设备加密c＝f(m，key)，其中f是对称加密机制；

*第一设备发送c到将其解密并恢复m的第二设备。

在图1到图4的帮助下可以更容易理解本发明。

图1描述实现本发明所建议系统的签名或解密设备的结构图。

图2描述实现本发明所建议系统的验证或加密设备的结构图。

图3描述由签名设备和验证设备交换的数据。

图4描述由加密设备和解密设备交换的数据。

根据建议的发明，每台签名/解密设备(典型的是智能卡)由处理单元(CPU)、通信接口、随机存储器(RAM)和/或只读存储器(ROM)和/或可写(通常可重写)存储器(EPROM或EEPROM)组成。

签名/解密设备的CPU和/或ROM包括相应于签名/解密算法(用于计算和用于使用散列、乘法、平方、加法、模倒数、和模减法函数的规则)步骤的程序或计算资源。这些操作当然可以组合在一起：例如，模数减法可以直接融入乘法中。

RAM包含消息M，对该消息M应用散列函数或产生签名的计算规则或产生密码的计算规则。按照下面描述的规定，E(E)PROM至少包含所述的产生和使用的参数m、x和k。

CPU通过地址和数据总线控制通信接口和存储器的读写操作。

每台签名设备用物理保护装置在外部环境中得到保护。这些保护装置足以防止任何未经授权的进入得到保密密钥。这方面目前使用最多的技术是在安全模块内芯片的集成和为芯片配备能检测温度或光的改变还有非正常电压和时钟频率的设备。也使用诸如混合存储器访问的特殊设计技术。

根据建议的本发明，验证设备至少由处理单元(CPU)和存储器资源组成。

CPU通过地址和数据总线控制通信接口和存储器的读写操作。

授权的CPU和/或ROM包含使得实现签名或加密协议成为可能的程序或计算资源(计算规则和散列、乘法、求幂和模数减法函数)。这些操作当然可以组合在一起(例如，模数减法可以直接融入乘法中)。

Claims

1.一种密码系统，该系统通常需要随机数k(随机数为整数)的提取，该系统其特征在于通过用量h(m|secret)代替所述随机数k来实现该系统，其中h是散列函数、m是出现在所述系统中的消息和“secret”是密码系统之外的世界所未知的保密项。

2.根据权利要求1的密码系统，其特征在于该系统至少包括：

-公开密钥签名系统；

-公开密钥加密系统；

-随机填充系统；

-模糊因子产生系统；

-密钥交换协议。

3.根据权利要求2，包括DSA、Schnorr、E1-Gamal、GOST 34.10或IEEE ECDSA椭圆曲线标准类型的公开密钥签名系统的密码系统，其特征在于用量h(m|x)替代由签名者在每个签名时更新的随机数(k)，其中x是签名者的保密密钥。

4.根据权利要求2，包括Fiat-Shamir或Guillou-Quisquater类型的公开密钥签名系统的密码系统，其特征在于用量h(m|B)替代由签名者在每个签名时更新的随机数，B是签名者的保密密钥和m是要签名的消息。

5.根据权利要求2，包括E1 Gamal类型的公开密钥加密系统的密码系统，其特征在于用量h(m)替代由加密者在每个发送的加密消息时更新的随机数(k)。

6.根据权利要求2，包括McEliece类型的公开密钥加密系统的密码系统，其特征在于从量h(m)得到由加密者在每次加密时更新的随机误差矢量e。

7.根据权利要求2，包括出现在公开密钥加密系统中的随机填充系统的密码系统，其特征在于加密者拥有解密者未知的密钥σ和在于根据下列步骤执行消息填充：

a.产生尽可能多的ki＝h(m|σ|i)以使级联kis的长度至少等于模n大小的1/6(例如RSA加密的情况下)，或产生k＝h(m|σ)并将其扩展；

b.形成m_r，其中m_r＝size(m)|m|(k_I)；

c.加密m_r替代m。

8.根据权利要求2，包括在空白签名产生或随机伪装操作的上下文中产生模糊因子的系统的密码系统，其特征在于用量h(m|σ)替代由发送者在每次模糊或伪装操作时更新的随机数(k)。

9.根据权利要求2，包括Diffie-Hellman类型密钥交换协议的密码系统，其特征在于希望发送消息m的设备使用量h(m|σ)而不是随机保密项，其中σ是随机保密项。

10.根据权利要求9的密码系统，其特征在于所述协议至少包括以下步骤：

a.第一设备希望发送消息m，计算b₁＝g^h(m|σ)模p；

b.第二设备(接收者)产生随机数a并计算b₂＝g^a模p；

c.两台设备交换b₁和b₂，并计算密钥key＝g^ah(m|σ)模p；

d.第一设备加密c＝f(m，key)，其中f是对称加密机理；

-第一设备发送c到将其解密并恢复m的第二设备。

11.根据权利要求1到10任何一个的密码系统，其特征在于该设备是智能卡、PCMCIA卡、标记卡、非接触卡或任何其它的便携式设备的通信没备。

12.根据权利要求1到11任何一个的密码系统，其特征在于通过交换电信号、无线电波或红外线信号实现所述设备间的通信。