数学不行，看到一段RSA加密程序，关于快速取模的，特来请教下，看了几个小时，搞不懂

lihui_mc

这个是一个RSA加密程序的片段，该RSA加密程序对小于100的数加密结果正确，对大于100的数加密结果有偏差。
跟踪了一下，提取了以下片段。是一个快速取模的运算。
返回值是M^e%n,也就是m的e次方，再模n。看起来像是整数运算溢出了。
1920^4519 mod 10403 = 10000，结果有问题，计算器无法计算的，1920是加密得到的，用计算器算过加密过程是对的，问题出在解密过程。
int kuaisuqumo(int m,int e,int n){
        int i,j,t=0,c=1,b[15],len=0;
        for(i=0;e!=0;i++){
                b=e%2;
                e=e/2;
                len++;
        }
        for(j=i-1;j>=0;j--){
                t=2*t;
                c=(c*c)%n;
                if(b[j]==1){
                        t+=1;
                        c=(c*m)%n;
                }
        }
        return c;
}

int _tmain(int argc, _TCHAR* argv[]){
        printf("%d ",kuaisuqumo(1817,4519,10403));//结果打印了9897，是正确的
        printf( "%d",kuaisuqumo(1920,4519,10403) );//结果打印了10000，正确应该是10099
}


(原文件名:2.jpg)


(原文件名:3.jpg)

算法原理百度文库有介绍，不过看不太懂。http://wenku.baidu.com/view/cf2d6b651ed9ad51f01df21a.html

付上VC工程，哎，看了几个小时，找不到问题所在
VC工程ourdev_704457UXF0AJ.rar(文件大小:136K) (原文件名:RSA.rar)

lihui_mc

回复【楼主位】lihui_mc  软硬兼施
-----------------------------------------------------------------------
版面的代码格式都没缩进了，上传个图好看点

(原文件名:5.jpg)

lihui_mc

搞错了，正确结果应该是99100，不过它返回了10000仍然是有问题的

root

回复【2楼】lihui_mc 软硬兼施
搞错了，正确结果应该是99100，不过它返回了10000仍然是有问题的
-----------------------------------------------------------------------

正确结果应该小于10403,所以99100肯定不正确.

root

貌似10000是正确的

http://acme.com/software/bigint/bic.cgi?expr=modpow%281920%2C4519%2C10403%29
===========================================================================
bic results

% bic
modpow(1920,4519,10403)
10000

Try another
===========================================================================
http://acme.com/software/bigint/

google "modular exponentiation calculator", 找个计算器先验证下吧~~

lihui_mc

回复【4楼】root  菜鸟活化石
-----------------------------------------------------------------------

原来如此，谢谢提醒了，问题找到了呵，出错是出在数据分组，将97和98组合，结果是97*100+98=9798，而将99和100组合，结果是99*100+100=10000，溢出了，作者源程序只能支持两位10进制组合的，因此超过了100就溢出了。

eduhf_123

MARK RSA