一种实现RSA密码体制的大数求模方法

IPRDB

API 数据接口

专利申请

使用指引 chat嘟嘟

会员体验

联系我们

交流群

现在联系顾问~

一种实现RSA密码体制的大数求模方法
申请号	CN201310205216.7	申请日	2013-05-28	公开(公告)号	CN103294448A	公开(公告)日	2013-09-11
申请人	福建升腾资讯有限公司;			发明人	蒋声障; 张登峰; 余杭军;
摘要	本发明提供一种实现RSA密码体制的大数求模方法，首先进行RSA加解密算法的初始化；取得模值n的有效比特长度值k；将2^（2k）除以n得到单位商值Q0；整数a输入到整数寄存器，且整数a≤2^（2k）；将a的低k位比特忽略后，取得高部数据D1；将D1和Q0相乘的结果忽略低k位比特后，得出一准商值Q1；将Q1和n相乘得到的结果取低（k＋3）位比特后得出近似整数值D2；取得a的低（k＋3）位比特后的低部数据D3；计算D3与D2两者相减的差值记为余数R0；R0与n进行对比，得出数求模值R；将所述大数求模值R输入到输出模块，完成大数求模。本发明的优点在，速度快，消耗内存小。
权利要求	1.一种实现RSA密码体制的大数求模方法，其特征在于：包括：整数寄存器：用于存储待求模的整数a；模值寄存器：用于存储模值n，模值寄存器中的数据在RSA加解密算法运算过程中保持不变；模值有效比特长度计算模块：用于计算所述模值n在二进制表示下的有效比特长度值k；单位商计算模块：用于计算2^（2k）除以所述模值n的所得到的单位商值Q0；单位商寄存器：用于存储所述单位商值Q0；取大数高部模块：用于取得所述整数a忽略低k位比特后的高部数据D1；整数高部寄存器：用于存储所述高部数据D1；取大数低部模块：用于取得所述整数a的低（k＋3）位比特后的低部数据D3；整数低部寄存器：用于存储所述低部数据D3；乘法忽略低部模块：用于计算所述高部数据D1和商值Q0相乘的积值M1，并将该积值M1忽略低k位比特后，得出一准商值Q1；准商寄存器：用于存储所述准商值Q1；乘法计算低部模块：用于计算所述准商值Q1和所述模值n相乘的积值M2，并取得该积值M2的低（k＋3）位比特后的近似整数值D2；近似整数寄存器：用于存储所述近似整数值D2；数据相减模块：用于计算所述低部数据D3与近似整数值D2相减的差值，并将该差值记为余数R0；余数寄存器：用于存储所述余数R0；误差修正模块：用于依据所述模值n对所述余数R0进行误差修正，得出余数修正值R1；误差修正结果寄存器：用于存储所述余数修正值R1；输出模块：将所述误差修正结果寄存器内的余数修正值R1记为大数模值R输出结果；该方法具体包括如下步骤：步骤10、进行RSA加解密算法的初始化；所述模值n输入到模值寄存器；所述模值n通过所述有效比特长度计算模块得到该模值n的有效比特长度值k；将2^（2k）除以所述模值n所得到的单位商值Q0输入到所述单位商寄存器；步骤20、所述整数a输入到所述整数寄存器，且所述整数a≤2^（2k）；步骤30、所述整数a、有效比特长度值k输入到所述取大数高部模块；所述取大数高部模块将所述整数a的低k位比特忽略后，取得高部数据D1；步骤40、所述高部数据D1、单位商值Q0、有效比特长度值k输入到所述乘法忽略低部模块；所述高部数据D1和商值Q0相乘得到积值M1，并将该积值M1忽略低k位比特后，得出一准商值Q1；步骤50、所述准商值Q1、模值n输入到所述乘法计算低部模块；所述准商值Q1和模值n相乘得到积值M2，并取得该积值M2的低（k＋3）位比特后的近似整数值D2；步骤60、所述整数a输入到取大数低部模块；取得所述整数a的低（k＋3）位比特后的低部数据D3；步骤70、所述低部数据D3、近似整数值D2输入到数据相减模块；计算所述低部数据D3与近似整数值D2两者相减的差值，并将该差值记为余数R0；步骤80、所述余数R0输入到所述误差修正模块；余数R0与模值n进行对比；当R0≥n时，进入步骤81；当R0＜n时，进入步骤82；步骤81、所述余数R0减去模值n的结果记为余数修正值R1，并判断该余数修正值R1是否小于模数n；当R1≥n时，将该余数修正值R1记为余数R0，返回步骤80，并指示仍需修正；当R1＜n时，将该余数修正值R1记为大数求模值R输出至所述误差修正结果寄存器，并指示无需修正；进入步骤90；步骤82、所述余数R0记为大数求模值R输出至所述误差修正结果寄存器，并指示无需修正；进入步骤90；步骤90、将所述大数求模值R输入到输出模块，完成大数求模。 2.根据权利要求1所述的一种实现RSA密码体制的大数求模方法，其特征在于：所述步骤10中，将2^（2k）除以所述模值n所得到的单位商值Q0能通过移位相减法实现。
说明书全文	一种实现RSA密码体制的大数求模方法技术领域 [0001] 本发明涉及一种密码安全领域，特别指一种实现RSA密码体制的大数求模方法。背景技术 [0002] 在RSA密码体制、SM2密码体制等金融安全相关领域，大数的求模运算速度以及运算所需要的内存空间，直接影响了金融产品的使用性能及限制了部分应用范围，可能还间接地影响金融产品的成本；其中，所述大数在RSA密码体制中一般指1024位比特以上（包含1024位比特）的数值，目前以2048位比特较为常见；所述大数在SM2密码体制中一般指192位比特、224位比特及256位比特。目前业内虽公认蒙哥马利求模方法为最快的方法，但计算速度仍然还不够快，且消耗内存大。发明内容 [0003] 本发明要解决的技术问题，在于提供一种实现RSA密码体制的大数求模方法，速度快且耗内存小。 [0004] 本发明是这样实现的：一种实现RSA密码体制的大数求模方法，包括： [0005] 整数寄存器：用于存储待求模的整数a； [0006] 模值寄存器：用于存储模值n，模值寄存器中的数据在RSA加解密算法运算过程中保持不变； [0007] 模值有效比特长度计算模块：用于计算所述模值n在二进制表示下的有效比特长度值k； [0008] 单位商计算模块：用于计算2^（2k）除以所述模值n的所得到的单位商值Q0； [0009] 单位商寄存器：用于存储所述单位商值Q0； [0010] 取大数高部模块：用于取得所述整数a忽略低k位比特后的高部数据D1； [0011] 整数高部寄存器：用于存储所述高部数据D1； [0012] 取大数低部模块：用于取得所述整数a的低（k＋3）位比特后的低部数据D3； [0013] 整数低部寄存器：用于存储所述低部数据D3； [0014] 乘法忽略低部模块：用于计算所述高部数据D1和商值Q0相乘的积值M1，并将该积值M1忽略低k位比特后，得出一准商值Q1； [0015] 准商寄存器：用于存储所述准商值Q1； [0016] 乘法计算低部模块：用于计算所述准商值Q1和所述模值n相乘的积值M2，并取得该积值M2的低（k＋3）位比特后的近似整数值D2； [0017] 近似整数寄存器：用于存储所述近似整数值D2； [0018] 数据相减模块：用于计算所述低部数据D3与近似整数值D2相减的差值，并将该差值记为余数R0； [0019] 余数寄存器：用于存储所述余数R0； [0020] 误差修正模块：用于依据所述模值n对所述余数R0进行误差修正，得出余数修正值R1； [0021] 误差修正结果寄存器：用于存储所述余数修正值R1； [0022] 输出模块：将所述误差修正结果寄存器内的余数修正值R1记为大数模值R输出结果； [0023] 该方法具体包括如下步骤： [0024] 步骤10、进行RSA加解密算法的初始化；所述模值n输入到模值寄存器；所述模值n通过所述有效比特长度计算模块得到该模值n的有效比特长度值k；将2^（2k）除以所述模值n所得到的单位商值Q0输入到所述单位商寄存器； [0025] 步骤20、所述整数a输入到所述整数寄存器，且所述整数a≤2^（2k）； [0026] 步骤30、所述整数a、有效比特长度值k输入到所述取大数高部模块；所述取大数高部模块将所述整数a的低k位比特忽略后，取得高部数据D1； [0027] 步骤40、所述高部数据D1、单位商值Q0、有效比特长度值k输入到所述乘法忽略低部模块；所述高部数据D1和商值Q0相乘得到积值M1，并将该积值M1忽略低k位比特后，得出一准商值Q1； [0028] 步骤50、所述准商值Q1、模值n输入到所述乘法计算低部模块；所述准商值Q1和模值n相乘得到积值M2，并取得该积值M2的低（k＋3）位比特后的近似整数值D2； [0029] 步骤60、所述整数a输入到取大数低部模块；取得所述整数a的低（k＋3）位比特后的低部数据D3； [0030] 步骤70、所述低部数据D3、近似整数值D2输入到数据相减模块；计算所述低部数据D3与近似整数值D2两者相减的差值，并将该差值记为余数R0； [0031] 步骤80、所述余数R0输入到所述误差修正模块；余数R0与模值n进行对比；当R0≥n时，进入步骤81；当R0＜n时，进入步骤82； [0032] 步骤81、所述余数R0减去模值n的结果记为余数修正值R1，并判断该余数修正值R1是否小于模数n；当R1≥n时，将该余数修正值R1记为余数R0，返回步骤80，并指示仍需修正；当R1＜n时，将该余数修正值R1记为大数求模值R输出至所述误差修正结果寄存器，并指示无需修正；进入步骤90； [0033] 步骤82、所述余数R0记为大数求模值R输出至所述误差修正结果寄存器，并指示无需修正；进入步骤90； [0034] 步骤90、将所述大数求模值R输入到输出模块，完成大数求模。 [0035] 进一步的，所述步骤10中，将2^（2k）除以所述模值n所得到的单位商值Q0能通过移位相减法实现。 [0036] 本发明具有如下优点：通过整数寄存器、模值寄存器、模值有效比特长度计算模块、单位商计算模块、单位商寄存器、取大数高部模块、整数高部寄存器、取大数低部模块、整数低部寄存器、乘法忽略低部模块、准商寄存器、乘法计算低部模块、近似整数寄存器、数据相减模块、余数寄存器、误差修正模块、误差修正结果寄存器、输出模块对模值n及整数a进行求模运算，实现快速且低耗内存求得大数求模值R。附图说明 [0037] 下面参照附图结合实施例对本发明作进一步的说明。 [0038] 图1为本发明一种实现RSA密码体制的大数求模方法的执行流程图。 [0039] 图2为本发明一种实现RSA密码体制的大数求模方法在一较佳实施例中的执行流程图。具体实施方式 [0040] 请参阅图1所示，本发明一种实现RSA密码体制的大数求模方法，包括： [0041] 整数寄存器：用于存储待求模的整数a，且在一次求模运算过程中所述整数a的值能不断更新； [0042] 模值寄存器：用于存储模值n，模值寄存器中的数据在RSA加解密算法运算过程中保持不变； [0043] 模值有效比特长度计算模块：用于计算所述模值n在二进制表示下的有效比特长度值，并将该有效比特长度值记为k；其中，所述有效比特长度值为从所述模值n于二进制表示下为1的最高位比特至最低位比特的比特位数总和；（如：模值n于二进制表示下为0010110的有效比特长度值为5，k＝5） [0044] 单位商计算模块：用于计算2^（2k）除以所述模值n的所得到的单位商值，并将该单位商值记为Q0； [0045] 单位商寄存器：用于存储所述单位商值Q0，且单位商寄存器中的数值在RSA加解密算法运算过程中保持不变； [0046] 取大数高部模块：用于取得所述整数a忽略低k位比特位后的高部数据，并将该高部数据记为D1； [0047] 整数高部寄存器：用于存储所述高部数据D1； [0048] 取大数低部模块：用于取得所述整数a的低（k＋3）位比特后的低部数据，并将该低部数据记为D3； [0049] 整数低部寄存器：用于存储所述低部数据D3； [0050] 乘法忽略低部模块：用于计算所述高部数据D1和商值Q0相乘的积值M1，并将该积值M1忽略低k位比特后，得出一准商值，并将该准商值记为Q1； [0051] 准商寄存器：用于存储所述准商值Q1； [0052] 乘法计算低部模块：用于计算所述准商值Q1和所述模值n相乘的积值M2，并取得该积值M2的低（k＋3）位比特后的近似整数值D2； [0053] 近似整数寄存器：用于存储所述近似整数值D2； [0054] 数据相减模块：用于计算所述低部数据D3与近似整数值D2相减的差值，并将该差值记为余数R0； [0055] 余数寄存器：用于存储所述余数R0； [0056] 误差修正模块：用于依据所述模值n对所述余数R0进行误差修正，输出余数修正值R1，使大数求模结果落在正确的范围； [0057] 误差修正结果寄存器：用于存储所述余数修正值R1； [0058] 输出模块：将所述误差修正结果寄存器内的余数修正值R1记为大数模值R输出； [0059] 该方法具体包括如下步骤： [0060] 步骤10、进行RSA加解密算法的初始化，即计算模值的有效比特长度值及单位商值的计算；所述模值n输入到模值寄存器；所述模值n通过所述有效比特长度计算模块得到该模值n的有效比特长度值k；将2^（2k）除以所述模值n所得到的单位商值Q0输入到所述单位商寄存器； [0061] 步骤20、所述整数a输入到所述整数寄存器，且所述整数a≤2^（2k）； [0062] 步骤30、所述整数a、有效比特长度值k输入到所述取大数高部模块；所述取大数高部模块取得所述整数a忽略低k位比特后的高部数据D1； [0063] 步骤40、将所述高部数据D1、单位商值Q0、有效比特长度值k输入到所述乘法忽略低部模块；所述乘法忽略低部模块将所述高部数据D1和商值Q0相乘得到积值M1，并将该积值M1忽略低k位比特后，得出一准商值Q1； [0064] 步骤50、将所述准商值Q1、模值n、（k＋3）的数值输入到所述乘法计算低部模块；所述乘法计算低部模块将所述准商值Q1和模值n相乘得到积值M2，并取得该积值M2的低（k＋3）位比特后的近似整数值D2； [0065] 步骤60、将所述整数a、（k＋3）的数值输入到取大数低部模块；所述大数低部模块取得所述整数a的低（k＋3）位比特后的低部数据D3； [0066] 步骤70、将所述低部数据D3、近似整数值D2输入到数据相减模块；所述数据相减模块计算所述低部数据D3与近似整数值D2两者相减的差值，并将该差值记为余数R0； [0067] 步骤80、将所述余数R0输入到所述误差修正模块；所述误差修正模块将余数R0与模值n进行对比；当R0≥n时，进入步骤81；当R0＜n时，进入步骤82； [0068] 步骤81、所述余数R0减去模值n的结果记为余数修正值R1，并判断该余数修正值R1是否小于模数n；当R1≥n时，将该余数修正值R1记为余数R0，返回步骤80，并指示仍需修正；当R1＜n时，将该余数修正值R1记为大数求模值R输出至所述误差修正结果寄存器（即R＝R1），并指示无需修正；进入步骤90； [0069] 步骤82、所述余数R0记为大数求模值R输出至所述误差修正结果寄存器（即R＝R0），并指示无需修正；进入步骤90； [0070] 步骤90、将所述大数求模值R输入到输出模块，完成大数求模。 [0071] 其中，本发明一种实现RSA密码体制的大数求模方法的相关理论证明如下： [0072] 1.）由所述步骤10中，可知存在非负整数r1满足0≤r1＜n，使得2^（2k）＝n＊Q0＋r1成立...（1）； [0073] 2.）本发明所述步骤30中，可知存在非负整数r2满足0≤r2＜2^k＜2n，使得a＝D1＊2^k＋r2成立...（2）； [0074] 3.）本发明所述步骤40中，可知存在非负整数r3满足0≤r3＜2^k＜2n，使得D1＊Q0＝Q1＊2^k＋r3成立...（3）； [0075] 4.）本发明所述步骤50中，可知M2＝Q1＊n...（4）； [0076] 5.）由（2）、（4）式相减，可得 [0077] a－M2＝D1＊2^k＋r2－Q1＊n...（5） [0078] （5）式结合（3）式，消去Q1，可得 [0079] a－M2＝D1＊2^k－D1＊Q0＊n／（2^k）＋r3＊n／（2^k）＋r2...（6）[0080] （6）式结合（1）式，消去n＊Q0，可得 [0081] a－M2＝D1＊r1／（2^k）＋n＊r3／（2^k）＋r2...（7） [0082] 显然（7）式的右边非负，另一方面： [0083] a.）本发明所述限制条件a≤2^2k，因此D1≤2^k，所以D1＊r1／（2^k）≤r1＜n...（8） [0084] b.）显然n＜（2^k），所以n＊r3／（2^k）＜r3＜2n...（9）； [0085] c.）又有r2＜2n...（10） [0086] 结合上述证明，可知0≤a－M2＜5＊n＜2^（k＋3）...（11） [0087] 因此在计算a与M2的差时，取低（k＋3）位比特即可，也就是D3－D2＝a－M2，即本发明所述步骤81中，有R1＝a－M2； [0088] 6.）由（11）式可知，R1最多经过5次与n的比较相减，即可得R1mod n的结果（即大数求模值R），即本发明所述步骤81中，R＝R1mod n＝a mod n。 [0089] 本发明一种实现RSA密码体制的大数求模方法与蒙哥马利对比的测试数据[0090] 参考： [0091] 在同一环境中进行测试蒙哥马利求模方法与本发明所述的一种大数求模算法的运行时间及代码所需内存对比,以供参考，结果如下表： [0092] [0093] 具体实施方式举例，以RSA密码体制中的1024位比特为例： [0094] 以a＝0x [0095] 269800253D3D3B4C9E2455E50AA06730D81BF1C81C6BDC10C082F16BF184E2BCF697881C1AA3733DC6E4BF961C7C4B8F86B1F555069D2A0B81FD9355A8E361EE8CF7024F8F505EF91CD781DB2BDB55904DF6F4485562554D31B63B5DD2B1A6AB4C7AEE0C7C312196DDA47B8F953D886 05B0976FBAFA479487C884CB42EF078C5FBDE3BC77EDC6201CED6D5DDEC09E7901DA5EB1E8B17 88EBAFCEF67939D6D505F9149AE185EEBF8C158CAD D444A3A4AA24A4134730B565801D08FC2D 69EA8A9D7E982BDDDA84E38C563DCF7686E55AE4A6E06080F81F4E935C92B581B10BD86BD0CC9D0F D232BD8CBD1ED61CFF87CFB29B7D5C126EF2101A652A662AAB201FF3、n＝0x[0096] D07C5019B5F9AF9887AE74CBB43A6FA041C6FFD9B88C7FBCA190D D9F527A86A536BEC17A9F7A58AC39B51995B5266AC8B6A955119BC0FA E6C3FF0528A440CCC747FF2353368D56A9 201CE8E3D4E4C4F46A22A21B E6C8FDDB433465F86C8C89C80A5A062972045324AAB22040D299 3B63FD CEAFDF0C91C6210C68D23C537992A1，求a对n的模R为例: [0097] 如图2所示，通过本发明一种大数求模算法，如下步骤： [0098] 1、n的比特数k＝1024 [0099] 2、Q0＝2^（2K）／n＝0x [0100] 13A57D2975C1FC9F8B18B9FD8A196ECE39B9C922D00F38503CF67701F6407BFAB130C1266990E355345BF6043CF8D2DB59F79A5BDD16013669D5FA5A76B197AAA425CC6BB0B4EA5C79700632042CE3A549C838573F206FD3606DE87089E19006B0970E343CA2C6A7D29A6F26C23BEF15135AD6FB11BA9E59FBAE02E175C309FE9 [0101] 3、取a的高部，即D1＝0x [0102] 269800253D3D3B4C9E2455E50AA06730D81BF1C81C6BDC10C082F16BF184E2BCF697881C1AA3733DC6E4BF961C7C4B8F86B1F555069D2A0B81FD9355A8E361EE8CF7024F8F505EF91CD781DB2BDB55904DF6F4485562554D31B63B5DD2B1A6AB4C7AEE0C7C312196DDA47B8F953D886 05B0976FBAFA479487C884CB42EF078C5 [0103] 4、计算D1乘以Q0，并舍弃低K位比特，得到Q1＝0x [0104] 2F63AD953B6EF7A6B76B153C3803E7201645B943156BBF8D737913A6DF50B15469A4877E736D9ECDD19B95B94A996C1A77CEA91E48556717574D2C2A50088C8CD8EDBFF033502DD1E62C1AE60B39AAA9224A78DC093F0C43D79238DE36CD73E2F7B3EEA7CB4FB314889C631597E05 9A05AF6DED17D64463A452ACF4294CAC739 [0105] 5、计算Q1乘以n，并取低（K＋3）位比特，得到D2＝0x [0106] 0EE1990AE6090A447B6F4AA31DB11AE0C17061949DE580D4E3ADB53CD6214671482639AE5956E78F86BD6820480605C871732F8DC3A51E9E3BB B2B620B16A0295F4B2A1E5AF774DB8E426C5E04E8B786DF9B2511F99C1F3A7A41388B561DF889F257ADB326781871515845E89699B3D6D8F3B40704F AAE24048F1D786DE16CCD9； [0107] 6、取D3为a的低（K＋3）位比特，计算D3减去D2，得到R0＝0x [0108] 10DC4AB191E4BBDBA17E22BAC10F83984069FD1D4ACBF7B9D74F3A2ABD7C26DF176B0FFFBF0804693A9B62BCFC44348230D711A6AF6637B9C6156460CB880880789E589F82B0D95D3721709963859E276AD2E0F615E5D5AEBB87F2CCC4F2C4FCCAB51C1DD6AB13677A79A779395EC92450C421BA21F472DDA1C388EA3CD09531A； [0109] 7、比较R0与n的大小，R0大于n，因此减去n，得到R1＝R0－n； [0110] 由于R1比n小，因此得到R＝R1＝0x [0111] 3D485AFF68520E219033B6E05CBDC9E3C4D8D1FAF432FBE0D362C50C8547E74C3FF23E815105EDE77001123A0F1CDD5A56C7C5595AA280B59D5740E4143FBB4041E666A4F4803F2A51FA20B263751D82430B6D4577945D10754AC6D3E29FC604A0F7BBB3F8ACE352FCE85752C353 56E10E736B C312B567B90FCFBC67798FC079； [0112] 综上所述，上述实施例以RSA密码体制为例，同理，本发明一种实现RSA密码体制的大数求模方法还能应用于SM2密码体制中，且本发明所指大数并不局限于RSA密码体制中的1024位比特、2048位比特或在SM2密码体制的192位比特、224位比特及256位比特等长度；本发明一种实现RSA密码体制的大数求模方法针对大数求模方法提出相对于现有蒙哥马利求模方法更高速度、更低内存消耗的方法。 [0113] 虽然以上描述了本发明的具体实施方式，但是熟悉本技术领域的技术人员应当理解，我们所描述的具体的实施例只是说明性的，而不是用于对本发明的范围的限定，熟悉本领域的技术人员在依照本发明的精神所作的等效的修饰以及变化，都应当涵盖在本发明的权利要求所保护的范围内。