双核公钥密码算法运算协处理器的一种实现方法转让专利
申请号 : CN200610114095.5
文献号 : CN101170406B
文献日 : 2010-10-06
发明人 : 胡晓波 , 陈立志 , 关红波 , 余秋芳 , 陈学振 , 田勇
申请人 : 北京中电华大电子设计有限责任公司
摘要 :
本发明提供一种双核公钥密码算法协处理器的实现方法，能够很好的解决由于运算中大数宽度过长导致的存储量过大问题。通过本发明描述的方式，只需增加必要的控制部分，并且不增加额外时间开销，就能达到在一定程度上节约面积资源，并提高后端版图布线利用率。同时双核运算模块的使用，大大提高了公钥密码运算效率。一位地址线的设计，不仅可适应在资源有限的情况下使用协处理器，还便于简化整个公钥密码算法流程的运算。在流程中协处理器的结果数据可以不从接口输出，只需根据算法需要直接参与下一个运算。实现该功能的部件是两个完全相同的运算模块和接口控制模块，每个运算模块包括：RAM模块、控制模块和算法模块。
权利要求 :
1.一种公钥密码算法协处理器的实现方法，其硬件是由两个相同的运算模块组成，每个运算模块包括：RAM模块、算法模块和控制模块，其特征在于：协处理器包括一位地址线，使用该协处理器需要完整的指令集，并按如下操作协处理器的操作流程执行：(1)、用户发送置数指令，此时地址线addr＝0；此指令中相关位应包括要置的数据是送入专用寄存器，还是送入RAM中，如果是送入RAM，还需要标明在RAM中的位置，RAM中只用来存放大数；
(2)、用户输入数据，此时地址线addr＝1；数据包括运算的操作数和参数；
(3)、用户发送运算指令，此时地址线addr＝0；运算类型有模乘、模加、模减和取模运算；指令中表明两个运算模块各自的操作；在发送运算指令之前，运算所需要的操作数和参数必须已经输入；
(4)、协处理器进行运算；
(5)、判断运算是否结束，有一个握手信号表明运算是否结束，这个信号既可以作为中断也可以作为查询；
(6)、用户读取结果数据。
2.如权利要求1所述的一种公钥密码算法协处理器的实现方法，其特征在于所述RAM模块，包括一个双端口RAM和一个单端口RAM。
3.如权利要求1所述的一种公钥密码算法协处理器的实现方法，其特征在于所述控制模块，主要包括接口控制、对RAM的读写控制、对专用寄存器的读写控制、握手信号的控制和算法模块的所有开关控制。
4.如权利要求1所述的一种公钥密码算法协处理器的实现方法，其特征在于：所述一位地址线为保证协处理器正常工作，其步骤如下：
1>输入写参数指令：地址线置0；
2>输入参数：地址线置1；
3>输入写数据指令：地址线置0；
4>输入数据：地址线置1；
5>输入运算指令：地址线置0；
6>等待运算结束，输出结果数据：地址线置1。
5.如权利要求1所述的一种公钥密码算法协处理器的实现方法，其特征在在于：所述算法模块中包括模乘运算、模加运算、模减运算、取模运算。
说明书 :
技术领域
本发明涉及信息安全密码领域，具体的说，涉及到公钥密码运算协处理器的硬件实现。主要针对RSA、ECC公钥密码算法中核心运算的硬件实现方法。
背景技术
随着计算机网络的普及，大量的电子数据通过网络传输到世界各地成为可能。但在具有重大的经济价值或关系国家、军队的命运等重要数据的传输过程中，任何一点泄露和差错都可能造成不可估量的损失。而密码技术则是信息安全的保障及核心技术。公钥密码算法大多基于数学难解问题，目前具有较高的安全性。其中ECC和RSA是已经成熟的公钥密码算法，使用也颇为广泛。
针对最常用的公钥密码算法RSA和ECC，基本运算分别如下：
RSA：
密钥对生成：随机大素数p和q，n＝pq，φ(n)＝(p-1)(q-1)，随机选取整数e，满足gcd(e，φ(n))＝1，计算d＝e-1modφ(n)，密钥对(e，d)；
加密：C＝Me(mod n)；
解密：M＝Cd(mod n)；
其中M是明文，待加密数据，C是密文，加密后数据，e是私钥，加密密钥，d是公钥，解密密钥，n是模数。
在加解密运算中，模幂运算由一系列模乘运算组成。此外，解密运算时可以使用中国剩余定理(CRT)使模幂运算大数的位数减少一半。
通常实现时，使用蒙哥马利(Montgomery)模乘算法，在运算过程中有大量大数需要存储，算法安全性依赖于大数的位数长度，一般都会选择512bit长度以上，存储量极大。关键运算为模乘。
ECC：
密钥对生成：选定椭圆曲线，基点G(Gx，Gy)，阶为N；在[1，2，…，N-1]中任意选取随机数A作为私钥；点乘AG＝P(Px，Py)为公钥。
加密(ECIES)：取任意随机数K在[1，2，…，N-1]中，计算KG＝H(Hx，Hy)、KP＝Q(Qx，Qy)和C3＝M xor Qx，C＝{Hx，Hy，C3}。其中M为明文，待加密数据。C为密文，加密后数据。点H、Q为椭圆曲线上的点。点G为基点，点P为公钥。随机整数A为私钥。
解密(ECIES)：计算AH＝I(Ix，Iy)，M＝C3 xor Ix。
可看出，ECC的核心运算是点乘运算。
通常实现时，使用一系列倍点和点加运算组成。基本运算由模乘、模加和模减构成。一般来说ECC没有亚指数攻击，所以它的密钥长度大大的减少，256bit即可满足一般要求。
基于如上分析，ECC和RSA公钥体制中兼容最基本运算模乘、模加和模减。而且RSA支持到位宽2048bit，ECC支持到位宽256bit.这样大数的存储和运算速度问题一直是硬件实现中的难点。
通常情况下，现有的实现一般都采用单核(即单个运算模块)和单RAM模块的技术，这样在速度和灵活性上无法得到突破性的提高。
针对最常用的公钥密码算法RSA和ECC，基本运算分别如下：
RSA：
密钥对生成：随机大素数p和q，n＝pq，φ(n)＝(p-1)(q-1)，随机选取整数e，满足gcd(e，φ(n))＝1，计算d＝e-1modφ(n)，密钥对(e，d)；
加密：C＝Me(mod n)；
解密：M＝Cd(mod n)；
其中M是明文，待加密数据，C是密文，加密后数据，e是私钥，加密密钥，d是公钥，解密密钥，n是模数。
在加解密运算中，模幂运算由一系列模乘运算组成。此外，解密运算时可以使用中国剩余定理(CRT)使模幂运算大数的位数减少一半。
通常实现时，使用蒙哥马利(Montgomery)模乘算法，在运算过程中有大量大数需要存储，算法安全性依赖于大数的位数长度，一般都会选择512bit长度以上，存储量极大。关键运算为模乘。
ECC：
密钥对生成：选定椭圆曲线，基点G(Gx，Gy)，阶为N；在[1，2，…，N-1]中任意选取随机数A作为私钥；点乘AG＝P(Px，Py)为公钥。
加密(ECIES)：取任意随机数K在[1，2，…，N-1]中，计算KG＝H(Hx，Hy)、KP＝Q(Qx，Qy)和C3＝M xor Qx，C＝{Hx，Hy，C3}。其中M为明文，待加密数据。C为密文，加密后数据。点H、Q为椭圆曲线上的点。点G为基点，点P为公钥。随机整数A为私钥。
解密(ECIES)：计算AH＝I(Ix，Iy)，M＝C3 xor Ix。
可看出，ECC的核心运算是点乘运算。
通常实现时，使用一系列倍点和点加运算组成。基本运算由模乘、模加和模减构成。一般来说ECC没有亚指数攻击，所以它的密钥长度大大的减少，256bit即可满足一般要求。
基于如上分析，ECC和RSA公钥体制中兼容最基本运算模乘、模加和模减。而且RSA支持到位宽2048bit，ECC支持到位宽256bit.这样大数的存储和运算速度问题一直是硬件实现中的难点。
通常情况下，现有的实现一般都采用单核(即单个运算模块)和单RAM模块的技术，这样在速度和灵活性上无法得到突破性的提高。
发明内容
针对大数存储和运算速度难点，本发明提供一种公钥密码算法协处理器的实现方法，在协处理器中实现ECC和RSA的最基本运算模乘、取模、模加和模减。本发明能够在解决大数存储问题的基础上，同时节约面积资源，并且能够提高后端版图布线利用率。同时，双核运算模块的使用，大大提高了公钥密码运算效率。
本发明公开了一种硬件协处理器的实现方法：双核，是指协处理器中包含两个完全相同的运算模块，每个运算模块都有各自的RAM模块、算法模块和控制模块。这两个运算模块既可以独立地进行公钥算法的基本运算，也可以在控制模块的控制下协同运算，以满足不同公钥算法协议的要求。两个运算模块之间还可以实现内部相互交换数据，数据不需要读出即可以参加下一次运算，大大加快了运算速度。最典型的情况是：利用CRT(中国剩余定理)进行RSA解密运算时，可以利用两个运算模块同时进行模乘运算。
本发明还能够很好地解决在地址线资源有限的情况下灵活实现公钥核心运算的问题。实现该功能的部件是两个完全相同的运算模块和接口控制模块，每个运算模块包括：RAM模块、控制模块和算法模块。
1>多RAM模块，用于存储运算过程中的大数以及运算过程中数据的交互，还方便对不同地址进行同时读写。协处理器中使用一个双端口RAM和一个单端口RAM。双端口RAM用于协处理器与外部交换数据以及缓存运算中间结果，单端口RAM用于缓存运算过程中的部分中间结果以及最终结果。这种结构的好处是既可以避免大量寄存器堆砌造成的面积过大，也可以避免用两块双口RAM所造成的面积浪费，同时还可以提高后端的布线利用率。另外使用两个RAM比单独使用一个RAM速度上有一定的提高。对RAM地址空间的读写控制可以在运算过程中并行实现，并不会增加额外的时间开销。
2>控制模块，主要包括接口控制、对RAM的读写控制、对专用寄存器的读写控制、握手信号的控制和算法模块的所有开关控制。
3>算法模块，包括模乘运算(最高支持2048bit)、模加运算(最高支持256bit)、模减运算(最高支持256bit)、取模运算(支持2048bit对1024bit取模和1024bit对512bit取模)。
在不同的应用中，资源的提供也不尽相同，本发明给出地址线只有1根的情况下方便灵活实现公钥密码基本运算。
一位地址线，在运算过程中标示两个地址：命令寄存器和数据寄存器。这样通过内部命令或者地址译码，进行相关操作或者将数据送到相应的RAM空间。在实现运算需要完整的指令集，包括七类：强制终止并复位指令、写参数指令、写数据指令、写命令指令、读参数指令、读数据指令和读命令指令。为保证协处理器的正常工作，操作流程包括：
1>输入写参数指令(地址线置0)；
2>输入参数(地址线置1)；
3>输入写数据指令(地址线置0)；
4>输入数据(地址线置1)；
5>输入运算指令(地址线置0)；
6>等待运算结束，输出结果数据(地址线置1)。
在操作流程中需注意：
●若整个公钥运算中协处理器的下一次操作流程中所使用输入参数与刚结束的这次运算相同，可以不用重复输入(即1>和2>可省略)。
●若整个公钥运算中协处理器的下一次操作流程中所使用数据是刚结束的这次运算的结果数据，那么刚结束的运算结果数据可以不用输出而直接开始下一次操作流程(7>可省略)。但需要清楚了解运算结果数据在RAM中的存放地址。
本发明具有以下优点：
1>本发明使用双核，即两个运算模块，既可以同时进行两个相同的运算，也可以同时进行两个不同的运算，便于进行多线程操作，从而大大提高运算效率。
2>本发明使用RAM模块存储算法运算中的大数，这样不仅节约了面积资源，还提高后端版图布线利用率。虽然增加RAM接口控制部分，但是由于算法本身特性，对RAM的读写可以在运算期间并行实现，不会增加时间上的开销。
3>本发明可支持在地址线资源有限的情况下灵活方便地使用指令实现数据输入输出，运算控制以及测试。
4>本发明可兼容实现ECC和RSA两种通用公钥密码体制的基本运算，能满足不同系统的要求，可以通过软件控制来实现不同协议的公钥密码运算。
本发明公开了一种硬件协处理器的实现方法：双核，是指协处理器中包含两个完全相同的运算模块，每个运算模块都有各自的RAM模块、算法模块和控制模块。这两个运算模块既可以独立地进行公钥算法的基本运算，也可以在控制模块的控制下协同运算，以满足不同公钥算法协议的要求。两个运算模块之间还可以实现内部相互交换数据，数据不需要读出即可以参加下一次运算，大大加快了运算速度。最典型的情况是：利用CRT(中国剩余定理)进行RSA解密运算时，可以利用两个运算模块同时进行模乘运算。
本发明还能够很好地解决在地址线资源有限的情况下灵活实现公钥核心运算的问题。实现该功能的部件是两个完全相同的运算模块和接口控制模块，每个运算模块包括：RAM模块、控制模块和算法模块。
1>多RAM模块，用于存储运算过程中的大数以及运算过程中数据的交互，还方便对不同地址进行同时读写。协处理器中使用一个双端口RAM和一个单端口RAM。双端口RAM用于协处理器与外部交换数据以及缓存运算中间结果，单端口RAM用于缓存运算过程中的部分中间结果以及最终结果。这种结构的好处是既可以避免大量寄存器堆砌造成的面积过大，也可以避免用两块双口RAM所造成的面积浪费，同时还可以提高后端的布线利用率。另外使用两个RAM比单独使用一个RAM速度上有一定的提高。对RAM地址空间的读写控制可以在运算过程中并行实现，并不会增加额外的时间开销。
2>控制模块，主要包括接口控制、对RAM的读写控制、对专用寄存器的读写控制、握手信号的控制和算法模块的所有开关控制。
3>算法模块，包括模乘运算(最高支持2048bit)、模加运算(最高支持256bit)、模减运算(最高支持256bit)、取模运算(支持2048bit对1024bit取模和1024bit对512bit取模)。
在不同的应用中，资源的提供也不尽相同，本发明给出地址线只有1根的情况下方便灵活实现公钥密码基本运算。
一位地址线，在运算过程中标示两个地址：命令寄存器和数据寄存器。这样通过内部命令或者地址译码，进行相关操作或者将数据送到相应的RAM空间。在实现运算需要完整的指令集，包括七类：强制终止并复位指令、写参数指令、写数据指令、写命令指令、读参数指令、读数据指令和读命令指令。为保证协处理器的正常工作，操作流程包括：
1>输入写参数指令(地址线置0)；
2>输入参数(地址线置1)；
3>输入写数据指令(地址线置0)；
4>输入数据(地址线置1)；
5>输入运算指令(地址线置0)；
6>等待运算结束，输出结果数据(地址线置1)。
在操作流程中需注意：
●若整个公钥运算中协处理器的下一次操作流程中所使用输入参数与刚结束的这次运算相同，可以不用重复输入(即1>和2>可省略)。
●若整个公钥运算中协处理器的下一次操作流程中所使用数据是刚结束的这次运算的结果数据，那么刚结束的运算结果数据可以不用输出而直接开始下一次操作流程(7>可省略)。但需要清楚了解运算结果数据在RAM中的存放地址。
本发明具有以下优点：
1>本发明使用双核，即两个运算模块，既可以同时进行两个相同的运算，也可以同时进行两个不同的运算，便于进行多线程操作，从而大大提高运算效率。
2>本发明使用RAM模块存储算法运算中的大数，这样不仅节约了面积资源，还提高后端版图布线利用率。虽然增加RAM接口控制部分，但是由于算法本身特性，对RAM的读写可以在运算期间并行实现，不会增加时间上的开销。
3>本发明可支持在地址线资源有限的情况下灵活方便地使用指令实现数据输入输出，运算控制以及测试。
4>本发明可兼容实现ECC和RSA两种通用公钥密码体制的基本运算，能满足不同系统的要求，可以通过软件控制来实现不同协议的公钥密码运算。
附图说明
图1为协处理器的整体结构示意图；
图2为运算模块的结构示意图；
图3使用协处理器的操作流程图。
图2为运算模块的结构示意图；
图3使用协处理器的操作流程图。
具体实施方式
本发明的具体实施基本和说明书中所阐述的结构和原理一致，以下结合附图，具体说明本发明。
本发明公开了一种公钥算法协处理器的硬件实现方法，能够很好的解决由于公钥密码运算中大数位数过长造成存储量过大问题。实现该功能的部件是两个完全相同的运算模块和接口控制模块，每个运算模块包括：RAM模块、控制模块和算法模块。
请参阅图1，其为本发明硬件协处理器的整体结构示意图，根据本示意图，本硬件部件由运算模块1、运算模块2和接口及控制模块部分构成。
其中，所述接口及控制模块，是把两个运算模块的接口合并为一个IO，根据指令来选择是操作单个运算模块，还是两个运算模块同时操作。注意，除非输入数据相同，两个运算模块的数据不能同时输入。
运算模块，请参阅图2，其为运算模块的结构示意图。
图2中所述RAM模块，包括一个双端口RAM和一个单口RAM，图中单口RAM是在运算期间算法模块存储中间数据，图中双口RAM是存储协处理器输入输出数据以及部分中间结果。
图2中所述控制模块，包括对2个RAM的读写控制、对专用寄存器的读写控制、握手信号的控制和算法模块的所有开关控制。在结构示意图中没有标识出专用寄存器，大概有模长N、模乘参数MC等。
图2中所述IF，指运算模块的一些接口转换。
请参阅图3，该图描述了使用上述说明的硬件部件，操作协处理器的流程，具体步骤如下：
1>用户发送置数指令，此时地址线addr＝0。此指令中相关位应包括要置的数据是送入专用寄存器，还是送入RAM中，如果是送入RAM，还需要标明在RAM中的位置，RAM中只用来存放大数；
2>用户输入数据，此时地址线addr＝1。数据包括运算的操作数和参数，以模乘运算X*Y(mod M)为例，操作数X和Y，参数有模数M、模长N和运算需要数据MC。其他运算根据算法类推；
3>用户发送运算指令，此时地址线addr＝0。运算类型有模乘、模加、模减和取模运算。指令中应该表明两个运算模块各自的操作。注意，在发送运算指令之前，运算所需要的操作数和参数必须已经输入；
4>协处理器进行运算；
5>判断运算是否结束，一般情况下应该有一个握手信号表明运算是否结束，这个信号既可以作为中断也可以作为查询。
6>用户读取结果数据。
在整个流程中，根据协议决定运算的顺序，如果相邻两次运算有相同的操作数或参数，可以不重复输入；如果下一次运算的操作数是此次运算的结果数据，用户也可以不读出结果数据，在内部直接运算即可。
本发明公开了一种公钥算法协处理器的硬件实现方法，能够很好的解决由于公钥密码运算中大数位数过长造成存储量过大问题。实现该功能的部件是两个完全相同的运算模块和接口控制模块，每个运算模块包括：RAM模块、控制模块和算法模块。
请参阅图1，其为本发明硬件协处理器的整体结构示意图，根据本示意图，本硬件部件由运算模块1、运算模块2和接口及控制模块部分构成。
其中，所述接口及控制模块，是把两个运算模块的接口合并为一个IO，根据指令来选择是操作单个运算模块，还是两个运算模块同时操作。注意，除非输入数据相同，两个运算模块的数据不能同时输入。
运算模块，请参阅图2，其为运算模块的结构示意图。
图2中所述RAM模块，包括一个双端口RAM和一个单口RAM，图中单口RAM是在运算期间算法模块存储中间数据，图中双口RAM是存储协处理器输入输出数据以及部分中间结果。
图2中所述控制模块，包括对2个RAM的读写控制、对专用寄存器的读写控制、握手信号的控制和算法模块的所有开关控制。在结构示意图中没有标识出专用寄存器，大概有模长N、模乘参数MC等。
图2中所述IF，指运算模块的一些接口转换。
请参阅图3，该图描述了使用上述说明的硬件部件，操作协处理器的流程，具体步骤如下：
1>用户发送置数指令，此时地址线addr＝0。此指令中相关位应包括要置的数据是送入专用寄存器，还是送入RAM中，如果是送入RAM，还需要标明在RAM中的位置，RAM中只用来存放大数；
2>用户输入数据，此时地址线addr＝1。数据包括运算的操作数和参数，以模乘运算X*Y(mod M)为例，操作数X和Y，参数有模数M、模长N和运算需要数据MC。其他运算根据算法类推；
3>用户发送运算指令，此时地址线addr＝0。运算类型有模乘、模加、模减和取模运算。指令中应该表明两个运算模块各自的操作。注意，在发送运算指令之前，运算所需要的操作数和参数必须已经输入；
4>协处理器进行运算；
5>判断运算是否结束，一般情况下应该有一个握手信号表明运算是否结束，这个信号既可以作为中断也可以作为查询。
6>用户读取结果数据。
在整个流程中，根据协议决定运算的顺序，如果相邻两次运算有相同的操作数或参数，可以不重复输入；如果下一次运算的操作数是此次运算的结果数据，用户也可以不读出结果数据，在内部直接运算即可。