大素数阶有限域上的乘法运算

mathe

http://en.wikipedia.org/wiki/Montgomery_reduction
现代密码学中经常会使用大素数阶有限域上的运算，而其中最耗时最关键的时其中乘法运算。
比如有限域椭圆曲线上的ECDSA算法，通常需要在一个256比特的大素数阶有限域上进行运算。
而在其上运算，Montgomery reduction算法非常有效，不知道大家是否有兴趣专门为之写个快速代码。

mathe

Intel IPP Cryptography libraries里面就有MontReduce的实现，但是没有专门针对256比特情况进行优化。
我试着使用了一下，发现同一台机器，使用64位的代码要比32位的代码快3倍多，不知道论坛中汇编高手是否知道为什么会有这么大的差距？

mathe

根据上面wiki中链接，如果我们需要在N阶有限域中进行计算，我们首先需要选择一个2的幂R>N.
然后我们需要事先计算$R^-1(mod N)$并且计算出$R R^-1=kN+1$
对于$0<T<NR$,T的Montgomery reduction就是计算$MontReduce{T}=TR^-1(mod N)$,有以下非常快速的算法
$m=(k(T mod R))mod R$
$t=(T+mN)/R$
然后如果$t>=N$,那么$t=t-N$,结果就是$t$
可以看出，如果我们选择$R=2^256$,而且$R^-1,k$都可以事先计算，那么Montgomery reduction算法主要就是两次两个256比特整数的乘法运算。

mathe

然后对于$N$阶域中任意一个元素$x$,在计算过程中，我们将它保存为$\bar{x}=xR(mod N)$
于是域上面的加法运算$z=x+y(mod N)$可以对应为$\bar{z}=\bar{x}+\bar{y}(mod N)$
而乘法运算$z=xy(mod N)$可以表示为$\bar{z}=MontReduce{\bar{x}\bar{y}}$
另外我们还可以事先计算好$R_2=R^2(mod N)$
如果需要初始化一个元素$x$,我们可以有$\bar{x}=MontReduce{xR_2}$
而输出一个元素$x$也很简单，因为$x=MontReduce{\bar{x}}$
当然，上面的算法不能解决域中的逆运算（或除法）问题。而实际上，比如我们要在$N$阶域上一条椭圆曲线上进行操作时，可以用射影坐标来表示，通过这种方法，可以避免逆运算（只有在最后输出时才需要进行一次出发运算），而特别的，由于射影坐标中$(xR,yR,zR)$和$(x,y,z)$表示同一个点，所以初始化和输出时的转化都可以省略掉

cn8888

gxqcn早就写出来了,不过,
由于他的软件是闭源代码的,
所以他也肯定是不会给你看源代码的

mathe

不需要原码。我只是有些不理解32位和64位乘法速度上为什么差这么大。

gxqcn

可以这么看待这个问题，大整数快速计算，外层可以有FFT/FNT等高阶算法，
但最终避免不了对常规整数的乘法，它的复杂度为\(O(n^2)\)
如果CPU支持的整数乘法指令bit数翻倍了，则一次乘法运算，相当于先前的4次乘法，
且bit数翻倍后，FFT/FNT被切分的段数也可缩减一半。

gxqcn

我一直在规划64位平台下的大整数算法，评估下来可能不止3倍的效率提升，
之所以迟迟未动手，因为一来近几年比较忙，二来我期盼的那款CPU一直在推迟面市。

借楼主的帖子，询问一下：64位平台下可以直接内嵌汇编吗？比如说用Intel的编译器。
因为喜欢内嵌汇编的那份自由。

liangbch

我知道VS不支持64位内嵌式汇编。需要使用64位汇编的时候，需要书写单独的汇编文件，并用ml64.exe来编译。
比如VS2010 中自带的ml64 版本是10.0，输入ml64.exe,显示下面的信息。

D:\Program Files\Microsoft Visual Studio 10.0\VC>ml64 /?
Microsoft (R) Macro Assembler (x64) Version 10.00.30319.01
Copyright (C) Microsoft Corporation.  All rights reserved.

        ML64 [ /options ] filelist [ /link linkoptions ]

/Bl<linker> Use alternate linker          /Sf Generate first pass listing
/c Assemble without linking               /Sl<width> Set line width
/Cp Preserve case of user identifiers     /Sn Suppress symbol-table listing
/Cx Preserve case in publics, externs     /Sp<length> Set page length
/D<name>[=text] Define text macro         /Ss<string> Set subtitle
/EP Output preprocessed listing to stdout /St<string> Set title
/F <hex> Set stack size (bytes)           /Sx List false conditionals
/Fe<file> Name executable                 /Ta<file> Assemble non-.ASM file
/Fl[file] Generate listing                /w Same as /W0 /WX
/Fm[file] Generate map                    /WX Treat warnings as errors
/Fo<file> Name object file                /W<number> Set warning level
/Fr[file] Generate limited browser info   /X Ignore INCLUDE environment path
/FR[file] Generate full browser info      /Zd Add line number debug info
/I<name> Add include path                 /Zf Make all symbols public
/link <linker options and libraries>      /Zi Add symbolic debug info
/nologo Suppress copyright message        /Zp[n] Set structure alignment
/Sa Maximize source listing               /Zs Perform syntax check only
/errorReport:<option> Report internal assembler errors to Microsoft
    none - do not send report
    prompt - prompt to immediately send report
    queue - at next admin logon, prompt to send report
    send - send report automatically

G-Spider

gxqcn 发表于 2014-8-7 07:55
我一直在规划64位平台下的大整数算法，评估下来可能不止3倍的效率提升，
之所以迟迟未动手，因为一来近几 ...

Intel 支持内嵌汇编，liangbch的做法也很好。