rsa：大整数相乘的问题

cjaizss

回复 8# keymirage
我的意思是,
你要算的是p^e%n
p^e根本没必要计算,更不用关心如何存储p^e
c=p^e%n
可以这样算
假设
k=p%n
e最高1024位
那么以下伪码
c=1;
k=p%n;
for n=0:1023
if(e & (1<<n))
     c=(c*k)%n;
end
k = (K*k)%n;
end
那么,你所需要的空间(不考虑过程中可能需要的很小的存储)也就是
k 1024bits
c 1024 bits
e 1024 bits
k  1024 bits
c*k
k*k  共用2048bits

yulihua49

keymirage 发表于 2016-03-05 16:51
rsa 加密的公式 ：
c = p^e % n （p的e次方 对 n 取模）
其中 c, p, e, n 都为 1024位（128字节）。

有限域，懂不懂？p^e%N是不可分割的整体。
给你个程序看看吧：expmod.c

1. 
   
2. #include "bignum.h"
   
3. /* ret = a ** z % n */
   
4. u_int *_e_m_(int n,u_int *a,u_int *z,u_int *m,u_int *ret)
   
5. {
   
6. u_int a1[MAXNUMBER+1];
   
7. u_int z1[MAXNUMBER+1];
   
8. u_int x[MAXNUMBER+1];
   
9.         numcpy(n,a1,a);
   
10.         numcpy(n,z1,z);
    
11.         n_one(n,x);
    
12.         while(!n_iszero(n,z1)) {
    
13.                 while(!(z1[0]&1)) {
    
14.                         rshift(n,z1,1);
    
15.                         /* a1 = (a1 *a1) % m; */
    
16.                         _m_m_(n,a1,a1,m,a1);
    
17.                 }
    
18.                 decm(n,z1);
    
19.                 /* x = (x*a1) % m; */
    
20.                 _m_m_(n,x,a1,m,x);
    
21.         }
    
22.         numcpy(n,ret,x);
    
23.         return ret;
    
24. }
    

复制代码

mulmod.c:每次乘积立即求模，就不会无限大了，有限域算法

1. 
   
2. #include "bignum.h"
   
3. u_int *_m_m_(int n,u_int *a,u_int *b,u_int *m,u_int *ret)
   
4. {
   
5. u_int tmp[MAXNUMBER*2+1];
   
6.         mulm(n,a,b,tmp);
   
7.         divm(n,tmp,m,(u_int *)0,ret);
   
8.         return ret;
   
9. }
   

复制代码

zuoyuanturing

RSA算法的破解
一.什么是RSA算法
    RSA公钥加密算法是1977年由罗纳德•李维斯特（Ron Rivest）、阿迪•萨莫尔（Adi Shamir）和伦纳德•阿德曼（Leonard Adleman）一起提出的。
    RSA算法基于一个十分简单的数论事实：将两个大素数相乘十分容易，但是想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。
   正是基于这种理论，1978年出现了著名的RSA算法，它通常是先生成一对RSA 密钥，其中之一是保密密钥，由用户保存；另一个为公开密钥，可对外公开，甚至可在网络服务器中注册。为提高保密强度，RSA密钥至少为500位长，一般推荐使用1024位。这就使加密的计算量很大。为减少计算量，在传送信息时，常采用传统加密方法与公开密钥加密方法相结合的方式，即信息采用改进的DES或IDEA对话密钥加密，然后使用RSA密钥加密对话密钥和信息摘要。对方收到信息后，用不同的密钥解密并可核对信息摘要。

二.我们的破解思路
    以往的破解思路都在关注大数分解，理论证明这是极难的。在分解大数没有结果的情况下我们就得换思路进行破解。
    我们先看MD5的破解，MD5HASH值不可逆，但仍然可以破解，基于的是彩虹表破解法，就是先用MD5工具算大量的明文的MD5值，然后储存起来。破解时对比MD5值，相同时就被破解。
    那么，我们破解RSA算法也可以这样，先算大量素数，然后对比是不是在素数表中，这样就能找到了。当然计算需要强大的计算能力，用天河这样的超级计算机比较合适。
    那么有朋友可能要问了，最一般的RSA1024的素数也有2^512大小，穷举的时间也是天河计算机不可接受的。我们的理论来了：
    受到素数产生技术的限制，能产生的素数较少。
    也就是说我们用一般的素数生成工具不断产生素数，用超算算一定时间后就有一个很大的素数集合了。那些素数生成工具不会产生的素数，我们同样也不用计算。这样我们就可以用彩虹表进行破解了

                                        湖南长沙 左远
                                                   2016/3/10

3P用户

好像有人在捣鼓这个，超大数运算，追求千万级整数的阶乘什么的。