一种基于CPU时钟和USB独立时钟的真随机数产生方法

摘要

本发明公开了一种基于CPU时钟和USB独立时钟的真随机数产生方法，所述方法包括：采用CPU时钟和USB独立时钟的抖动差异作为随机噪声源，生成随机数种子，采用散列算法对随机数种子进行散列操作，生成所需的真随机数。该方法在硬件上只依靠现代CPU电路板上普遍具备的CPU主时钟和USB模块独立时钟，相比外接物理噪声源、外接多种时钟源计数电路、CPU访问外设或重复内存访问运算等操作来产生真随机数的方法，更加简便高效，可用于密钥生成、数字签名和密钥协商等信息安全处理操作中需要真随机数的场合。

说明书

技术领域

本发明涉及密码技术领域，具体涉及一种基于CPU时钟和USB独立时钟的真随机数产生方法，该方法可用于密钥生成、数字签名和密钥协商等需要生成真随机数的场合。

背景技术

随机数广泛用于密钥产生、数字签名、密钥协商等方面，在密码应用中十分重要，随机数产生方法的安全性直接影响密码系统的安全性。多数情况下，攻击者难以直接破解密码算法，而采用猜测密码算法所用的秘密随机数等迂回攻击方法，往往得到秘密随机数便可攻破整个密码系统。

随机数产生包括真随机数产生和伪随机数产生两类。真随机数产生通常基于自然界中具备随机性质的物理熵源，如掷硬币的正反面、电路噪声、环境噪声、温度变化，这种方法产生随机数的随机性非常好，完全不可预测和回溯，但需要依靠相应的物理条件才能获取，该方式的产生效率低，应用受限。实际中更多使用的是伪随机数产生方法。伪随机数产生器也称为确定性随机数产生器，即在确定输入种子的情况下，其输出也确定。伪随机数的产生一般采用软件或可编程硬件算法实现，通常需要采用具备随机性质的数据源作为熵源，以提供一串不可预测的数据作为种子。

为避免单一随机数熵源失效造成安全设备功能性失效，我国部分新的安全技术规范中要求安全设备中至少具备两种随机数熵源。部分高性能CPU中增加基于多个时钟源输入驱动的专门电路提供真随机数发生功能，可以作为一种随机数熵源。

在椭圆曲线密码签名应用中，确保采用不重复的真随机数对保障应用的安全性尤其重要。2010年后曾发生两起因秘密随机数泄露而导致密码系统被破解的著名安全漏洞事件。一是Sony PlayStation3游戏终端平台被破解，导致非法软件未经Sony数字签名即可进入平台运行，二是Android中的比特币钱包因随机数产生器缺陷导致钱包被盗。两起安全漏洞事件的原因都是因为椭圆曲线数字签名所用的真随机数泄露从而被破解。

基于椭圆曲线密码的数字签名和随机数泄露相关步骤说明如下。

限于篇幅，椭圆曲线密码及相关的有限域和点加、倍点和点乘与有限域运算可参考相关技术资料。下面只对椭圆曲线签名及其随机数泄露过程予以说明。

椭圆曲线数字签名算法(ECDSA)步骤如下：

签名和验签双方共同约定使用特定的椭圆曲线E(Fp)：E:y^2≡x^3+ax+b(mod p)，为描述特定的椭圆曲线，需明确六个参数：T＝(p,a,b,G,n,h)，

p:代表有限域Fp的素数，

a,b：椭圆方程的参数，

G:椭圆曲线的一个基点G＝(xG,yG)，

n：椭圆曲线基点G的阶，

h：余因数，h＝#E(Fp)/n,#E(Fp)表示椭圆曲线上点元素的个数。

签名方的密钥对:(d,Q)；(d为私钥，Q为公钥，Q＝dG)

待签名的信息：m；

输出签名：Signature(m)＝(r,s)

签名过程如下：

1、生成一个秘密随机数k，0<k<n,计算R＝kG＝(xR,yR)，

2、令r＝xR mod n，如果r＝0，则返回步骤1，

3、计算h＝Hash(m)，将h转化为整数e，

4、s＝k^-1(e+rd)mod n，若s＝0,则返回步骤1，k^-1表示取k的倒数(模逆)，即k*k^-1＝1mod n

5、输出S＝(r,s)即为签名。

验证过程如下：

1、计算h＝Hash(msg)，h转化为整数e，

2、计算u1＝es^-1mod n,u2＝rs^-1mod n，

3、计算R＝(xR,yR)＝u1G+u2Q,如果R＝零点，则签名无效，

4、令v＝xR mod n,若v＝＝r，则签名有效，若v≠r,则签名无效。

真随机数和私钥泄露过程如下(所有操作包含mod n，不再注明)：

假如签名方不小心对不同消息m和m’采用相同的真随机数k签名，分别得到签名(r,s)和(r,s’)，攻击者对消息m和m’分别散列，转化为整数得到e和e’,将有:

s’＝k^-1(e’+rd)，

s-s’＝k^-1(e-e’),

k＝(s-s’)^-1(e-e’),

d＝r^-1(sk-e)。

攻击者比较两个消息的数字签名后，先求出真随机数k，通过上述步骤即可求出私钥d。

如前所述，在椭圆曲线数字签名中，如果相同的真随机数重复用于两个不同消息的签名将会泄露签名所用的真随机数，进而泄露签名者私钥，将导致整个数字签名系统被破解。

此外，现有的真随机数生成方法通常外接硬件随机噪声源，或者采用CPU访问外部设备(如磁盘、键盘、鼠标)的时间延迟或大量重复性的内存访问及运算延迟，作为随机熵源，前者增加硬件成本，后者在许多服务器或安全设备中缺乏相应外设无法采用或操作效率低。

发明内容

本发明的目的在于，为克服上述椭圆曲线密码应用中真随机数容易破解问题，同时为满足我国新的安全技术规范中要求安全设备具备两种以上随机熵源要求，提供一种真随机数产生方法，能够确保攻击者无法预测随机数的生成规律或回溯曾经用过的秘密随机数，确保密码系统中随机数不会重复使用。

为了实现上述目的，本发明提供了一种基于CPU时钟和USB独立时钟的真随机数产生方法，所述方法包括：采用CPU时钟和USB独立时钟的抖动差异作为随机噪声源，生成随机数种子，采用散列算法对随机数种子进行散列操作，生成所需的真随机数。

上述技术方案中，所述方法具体包括：

步骤1)开启USB帧开始SoF中断，SoF中断处理程序定期重复执行，读取CPU主时钟计数，获得连续两次SoF事件间的计时读数变化量，取变化量的最低若干位比特，与随机数种子池中原有种子拼接成比特串，累积放入随机数种子池，直到随机数种子比特串大于或等于特定长度b；所述初始原有种子为空；

步骤2)取随机数种子池中最新得到的特定长度b的随机种子比特串，采用散列算法对随机种子进行散列运算，得到初始随机数；

步骤3)获取CPU主机系统时间和累计读取随机数种子池次数，依次串接在所述初始随机数后，采用与步骤2)不同的散列算法对串接后的随机数进行散列运算，输出散列值作为备用随机数；

步骤4)如果该随机数不是用于离散对数或椭圆曲线密码签名操作，则所述备用随机数为所要生成的真随机数。

上述技术方案中，如果是针对离散对数或椭圆曲线密码数字签名而生成真随机数，在步骤4)之后还包括：

步骤5)将待签名消息的散列值与所述备用随机数串接，采用与步骤3)不同的散列算法进行散列运算，输出散列值，将该散列值作为本次椭圆曲线数字签名的真随机数。

上述技术方案中，所述步骤1)中的变化量的最低若干位为最低2bit。

上述技术方案中，所述步骤2)的特定长度b为256bit。

上述技术方案中，所述步骤2)和步骤3)中的散列算法为SHA-256或国密SM3。

上述技术方案中，所述步骤2)、步骤3)和步骤5)中的散列算法为SHA-256或国密SM3。

与现有技术相比，本发明的技术优势在于：

1、本发明的方法在硬件上只需满足CPU主时钟和USB模块时钟独立条件即可实施，不需要额外的硬件。在现代CPU配备的USB中，USB模块时钟由于有特定频率要求，通常为USB提供独立的内部或外接时钟，这一条件在多数配置USB模块的CPU系统中已经具备，便于低成本实施；

2、将本发明的方法编制成软件，具有简便高效的优点；CPU系统的开发软件包通常包含相应的USB功能模块，USB帧开始SoF中断会以固定频率重复发生，SoF频率为1KHz，对应1ms周期，软件上只需在SoF中断处理中增加获取CPU主时钟计数器在本次SoF时刻与上次SoF时刻的读数变化量即为SoF周期。由于USB和CPU的时钟独立无关，分别存在抖动，且CPU主时钟频率(如1000MHz)大大高于USB帧频率，获得的基于CPU主时钟计数的SoF帧周期会围绕1ms*1000MHz＝1000000个主时钟周期上下随机抖动，截取该变化量的尾数即可获得抖动值，可作为真随机数发生器的熵源；举例来说，CPU主时钟为1GHz，USB的SOF帧率为1KHz，其时域抖动的根均方为周期的十万分之一即10ns，对应SoF周期的CPU时钟计时器的读数变化值将围绕SoF理想周期值1ms＝1000000(ns)上下抖动变化，假定抖动变化量为t，t将符合均值为0，标准差σ＝10的高斯分布，根据其概率分布曲线，t将以60％以上概率落入+/-4以外范围；简单起见，可取CPU时钟计时器的读数变化值的最低2位尾数作为随机抖动值，随机种子池的更新速率将为1k*2＝2kbps，当通过输出为256bit的散列算法处理时，获得的随机数发生速率为512kbps，可满足大部分安全应用需求；

3、本发明的方法产生的秘密随机数具备良好的抗攻击性；即使攻击者连续重复请求生成随机数或对同一消息重复请求基于椭圆曲线密码的数字签名，因为在步骤5)中加入了散列操作，随机数生成者或攻击者都不可能通过多次连续操作中获得所生成随机数的变化规律，可有效防止随机数生成系统的提供方设置后门或遭攻击破解风险；

4、本发明的方法可确保离散对数或椭圆曲线签名所用真随机数的新鲜性，避免重复使用导致私钥泄密。

附图说明

图1为本发明的基于CPU时钟和USB独立时钟的真随机数产生方法的流程图。

具体实施方式

下面通过附图和实施例对本发明技术方案进行详细说明。

以针对素域椭圆曲线数字签名为例，设椭圆曲线的阶n和有限域模p均为二进制表示下长度为256bit大数，p<n。

如图1所示，一种基于CPU时钟和USB独立时钟的真随机数产生方法，包括如下步骤：

步骤1)USB SoF中断处理程序重复循环读取CPU主时钟计数器，获得前后两次SoF事件间的计时读数变换量，取变化量最低2bit尾数，与随机数种子池中原有种子(初始为空)拼接成比特串，累积放入随机数种子池，直到随机数种子长度大于或等于256bit；

步骤2)取随机数种子池中最新得到的256bit随机种子，利用SHA-256散列算法对随机种子进行散列运算，得到初始随机数；

步骤3)获取CPU主机系统时间和累计读取随机数种子池次数，依次串接在所述初始随机数后，再利用国密SM3散列算法进行散列运算，输出散列值作为备用随机数；

步骤4)判断是否为针对离散对数或椭圆曲线密码数字签名而生成真随机数，如果是，将待签名消息的散列值与上述备用随机数串接，进一步进行SHA256散列操作，输出散列值，将该散列值作为本次离散对数或椭圆曲线数字签名的真随机数，否则，备用随机数即为本次随机数生成请求得到的真随机数。

上述实施示例步骤中轮流采用不同的散列算法，所述散列算法为SHA-256和国密SM3。

上述步骤1)中独立随机抖动变化的时钟计数器尾数提供了基础的随机性种子，步骤2)进一步确保生成结果的随机性，增加生成结果的不确定性，确保不可预测；步骤4)可确保离散对数或椭圆曲线签名不会重复使用相同秘密随机数对不同消息进行签名，避免前述秘密随机数和私钥泄露问题。

以上实施例仅用以说明本发明的技术方案而非限制。尽管参照实施例对本发明进行了详细说明，本领域的普通技术人员应当理解，对本发明的技术方案进行修改或者等同变换，都不脱离本发明技术方案的精神和范围，其均应盖在本发明的权利要求范围当中。