首页
社区
课程
招聘
[求助]RSA加密算法
发表于: 2010-12-8 23:16 6167

[求助]RSA加密算法

2010-12-8 23:16
6167
#include"iostream"
#include"stdlib.h"
#include"time.h"
using namespace std;
typedef struct RSA_PARAM_Tag
{
        unsigned __int64 p,q;
        unsigned __int64 f;
        unsigned __int64 n,e;
        unsigned __int64 d;
        unsigned __int64 s;

} RSA_PARAM;
const static long g_PrimeTable[]=
{
3,
5,
7,
11,
13,
17,
19,
23,
29,
31,
37,
41,
43,
47,
53,
59,
61,
67,
71,
73,
79,
83,
89,
97
};
const static long g_PrimeCount=sizeof(g_PrimeTable)/sizeof(long);
const unsigned __int64 multiplier=12747293821;
const unsigned __int64 adder=1343545677842234541;
class RandNumber
{
   private:
           unsigned __int64 randSeed;
   public:
           RandNumber(unsigned __int64 s=0);
           unsigned __int64 Random(unsigned _int64 n);

}
RandNumber::RandNumber(unsigned __int64 s)
{

  if(!s)
  {
    randSeed=(unsigned __int64)time(NULL);

  
  }
  else
  {
    randSeed=s;
  
  }

}
unsigned __int64 RandNumber::Random(unsigned __int64 n)
{

  randSeed=multiplier*randSeed+adder;
  return randSeed%n;

}static RandNumber g_Rnd;

unsigned __int64 MulMod(unsigned __int64 a,unsigned __int64 b,unsigned __int64 n)
{
   return a*b%n;

}

unsigned __int64 PowMod(unsigned __int64 &base,unsigned __int64 &pow,unsigned __int64 &n)
{
  unsigned __int64 a=base,b=pow,c=1;
  while(b)
  {
  
    while(!(b&1))
        {
         b>>=1;
         a=MulMod(a,a,n);
       
       
        } b--;
        c=MulMod(a,c,n);
       
  }return c;

}

long RabinMillerKnl(unsigned __int64 &n)
{
          unsigned __int64 b,m,j,v,i;
          m=n-1;
          j=0;
          while(!(m&1))
          {
                 ++j;

                 m>>=1;
  
  
          }

          b=2+g_Rnd.Random(n-3);
          v=PowMod(b,m,n);
          if(v==1)
          {
                  return 1;
          }

        i=1;
        while(v!=n-1)
        {

           if(i==j)
           {
   
                 return 0;
           }
         // / v=(v*v)%n;
          ++i;
          return 1;
        }

}

long RabinMoller(unsigned __int64 &n,long loop)
{
          long i;
          for (i=0;i<g_PrimeCount;i++)
          {
                  if(n%g_PrimeTable==0)
                  {
                        return 0;
                  
                  }
          }
        for(i=0;i<loop;i++)
        {

           if(!RabinMliierKnl(n))
           {
                 return 0;
   
           }

          
        }return 1;

}

unsigned __int64 RandomPrime(char bits)
{

  unsigned __int64 base;
  do
  {
  
     base=(unsigned long)1<<(bits-1);
         base+=g_Rnd.Random(base);
         base|=1;
  
  }while(!RabinMillwe(base,30));
  return base;

}

unsigned _int64 EuclidGcd(unsigned _int64 &p,unsigned _int64 &q)
{

        unsigned __int64 a=p>q?p:q;
        unsigned __int64 b=p<q?p:q;
        unsigned __int64 t;
        if(p==q)
        {
          return p;
       
        }
        else
        {
       
           while(b)
           {
          
             a=a%b;
                 t=a;
                 a=b;
                 b=t;
          
           }
           return a;
       
        }
}

unsigned __int64 SteinGcd(unsigned __int64 &p,unsigned __int64 &q)

{
        unsigned __int64 a=p>q?p:q;
        unsigned __int64 b=p<q?p:q;
        unsigned __int64 t,r=1;
        if(p==q)
        {
          return p;
       
        }

        else
        {
                 while((!(a&1))&&(!(b&1)))
          {
          
             r<<=1;
                 a>>=1;
                 b>>=1;
          
          }
          if(!(a&1))
          {
            t=a;
                a=b;
                b=t;
          
          }
          do
          {
            while(!(b&1))
                {
               
                   b>>=1;
               
                }
if(b<a)

                {
                  t=a;
a=b;
                  b=t;
               
               
                }
                b=(b-a)>>=1;
          
          }while(b);
          return r*a;
       
        }

}

unsigned _int64 Euclid(unsigned __int64 &a,unsigned __int64 &b)
{
   unsigned __int64 m,e,i,j,x,y;
   long xx,yy;
   m=b;
   e=a;
   x=0;
   y=1;
   xx=1;
   yy=1;
   while(e)
   {
   
      i=m/e;
          j=m%e;
          m=e;
          e=j;
          j=y;
          y*=i;
          if(xx==yy)
          {
            if(x>y)
                {
                  y=x-y;

               
                }
                else
                {
               
                 y-=x;
                 yy=0;
                }
          
          
          }
          else
          {
           y+=x;
           xx=1-xx;
           yy=1-yy;
          
          
          } x=j;

   
   }
   if(xx==0)
   {
   
   x=b-x;
   }
   return x;

}

RSA_PARAM RsaGetParam(void)
{
        RSA_PARAM Rsa={0};
        unsigned __int64 t;
        Rsa.p=RandomPrime(16);
        Rsa.q=RandomPrime(16);
        Rsa.n=Rsa.p*Rsa.q;
        Rsa.f=(Rsa.p-1)*(Rsa.q-1);
        do
        {
       
          Rsa.e=g_Rnd.Random(65536);
          Rsa.e|=1;

       
        }while(SteinGcd(Rsa.e,Rsa.f)!=1);Rsa.d=Euclid(Rsa.e, Rsa.f);
        Rsa.s=0;
        t=Rsa.n>>1;
        while(t)
        {
          Rsa.s++;
          t>>=1;
          return Rsa;
        }

}

void TestRSA(void)
{
   RSA_PARAM r;
   char pSrc[]="abcdefghijklmnopqrstuvwxyz";
  const unsigned long n=sizeof(pSrc);
  unsigned char *q,pDec[n];
  unsigned __int64 pEnc[n];
  unsigned long i;
  r=RsaGetParam();
  cout<<"p="<<r.p<<endl;
  cout<<"q="<<r.q<<endl;
  cout<<"f=(p-1)*(q-1)="<<r.f<<endl;
  cout<<"n=p*q="<<r.n<<endl;
  cout<<"e="<<r.e<<endl;
  cout<<"d="<<r.d<<endl;
  cout<<"s="<<r.s<<endl;
  cout<<"Source:"<<pSrc<<endl;
  q=(unsigned char *)pSrc:
  cout<<"Encode:";
  for(i=0;i<n;i++)
  {
    pEnc[i]=PowMod(q[i],r.e,r.e);
        cout<<hex<<pEnc[i]<<" ";
       
  
  
  }cout<<endl;
  cout<<"Decode:";
  for(i=0;i<n;i++)
  {
  
    pDec=PowMod(pEnc,r.d,r.n);
        cout<<hex<<(unsigned long)pDec<<" ";

  }cout<<endl;
  cout<<(char *)pDec<<endl;

}

int main(void)
{

  TestRSA();
  return 0;
}

//这是我从网上找到的关于RSA加密的算法,但我的编译通不过,哪位大虾帮忙指点指点~~~

[招生]科锐逆向工程师培训(2024年11月15日实地,远程教学同时开班, 第51期)

收藏
免费 0
支持
分享
最新回复 (5)
雪    币: 768
活跃值: (530)
能力值: ( LV13,RANK:460 )
在线值:
发帖
回帖
粉丝
2
没工程文件?
2010-12-9 08:13
0
雪    币: 12
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
3
什么工程文件呀???因为最近上课刚好上到RSA的加密算法,所以在网上找到了这个算法,其思想跟老师上课讲的是一样的,就是编译通不过,不知道怎么改.
2010-12-9 09:43
0
雪    币: 12
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
4
什么工程文件呀???因为最近上课刚好上到RSA的加密算法,所以在网上找到了这个算法,其思想跟老师上课讲的是一样的,就是编译通不过,不知道怎么改.
2010-12-11 21:51
0
雪    币: 9
活跃值: (127)
能力值: ( LV12,RANK:200 )
在线值:
发帖
回帖
粉丝
5
进来看看!!!!!!!!!!!!
2010-12-12 23:19
0
雪    币: 440
活跃值: (87)
能力值: ( LV9,RANK:200 )
在线值:
发帖
回帖
粉丝
6
#include <stdlib.h>
#include <stdio.h>
#include <time.h>

typedef struct RSA_PARAM_Tag
{
  unsigned __int64 p,q;
  unsigned __int64 f;
  unsigned __int64 n,e;
  unsigned __int64 d;
  unsigned __int64 s;
} RSA_PARAM;

const static long g_PrimeTable[]=
{ 3,5,7,11,13,17,19,23,29,31,
  37,41,43,47,53,59,61,67,71,
  73,79,83,89,97
};

const static long g_PrimeCount=sizeof(g_PrimeTable)/sizeof(long);

class RandNumber
{
   private:
     unsigned __int64	m_randSeed;
     static unsigned __int64	s_multiplier;
     static unsigned __int64	s_adder;
   public:
     RandNumber(unsigned __int64 s = 0);
     unsigned __int64 Random(unsigned __int64 n);

};
unsigned __int64 RandNumber::s_multiplier = 12747293821;
unsigned __int64 RandNumber::s_adder = 1343545677842234541;

RandNumber::RandNumber(unsigned __int64 s)
{
  if(!s)
  {
    m_randSeed = (unsigned __int64)time(NULL);
  }
  else
  {
    m_randSeed = s;
  }
}

unsigned __int64 RandNumber::Random(unsigned __int64 n)
{
  m_randSeed = s_multiplier * m_randSeed + s_adder;
  return m_randSeed % n;
}

RandNumber g_Rnd;




unsigned __int64 MulMod(unsigned __int64 a,unsigned __int64 b,unsigned __int64 n)
{
   return (a*b)%n;
}

unsigned __int64 PowMod(unsigned __int64 &base,unsigned __int64 &pow,unsigned __int64 &n)
{
      unsigned __int64 a=base,b=pow,c=1;
      while(b)
     {
            while(!(b&1))
            {
	 b>>=1;
	 a=MulMod(a,a,n);
            } 
            b--;
            c=MulMod(a,c,n);
      }
      return c;
}

long MillerRabinKnl(unsigned __int64 &n)
{
    unsigned __int64 b,m,j,v,i;
    m=n-1;
    j=0;
    while(!(m&1))
    {
	++j;
	m>>=1;
    }
    b=2+g_Rnd.Random(n-3);
    v=PowMod(b,m,n);
    if(v==1)
    {
	return 1;
    }
    i=1;
    while(v!=n-1)
    {
        if(i==j)
        {
            return 0;
         }
        v=(v*v)%n;
        ++i;
    }
    return 1;
}


long MillerRabin(unsigned __int64 &n,long loop)
{
    long i;
    for (i=0;i<g_PrimeCount;i++)
    {
	if(n%g_PrimeTable[i]==0)
	{
	    return 0;
	}
    }
    for(i=0;i<loop;i++)
    {
           if(!MillerRabinKnl(n))
           {
	return 0;
           }
    }
    return 1;
}


unsigned __int64 RandomPrime(char bits)
{
  unsigned __int64 base;

  do
  {
	  base=(unsigned long)1<<(bits-1);
	  base+=g_Rnd.Random(base);
	  base|=1;
  }while(!MillerRabin(base,30));
  return base;
}

unsigned __int64 EuclidGcd(unsigned __int64 &p,unsigned __int64 &q)
{	
	unsigned __int64 a=p>q?p:q;
	unsigned __int64 b=p<q?p:q;
	unsigned __int64 t;
	if(p==q)
	{
		return p;
	}
	while(b)
	{
		a=a%b;
		t=a;
		a=b;
		b=t;
	}
	return a;	
}


unsigned __int64 SteinGcd(unsigned __int64 &p,unsigned __int64 &q)
{
	unsigned __int64 a=p>q?p:q;
	unsigned __int64 b=p<q?p:q;
	unsigned __int64 t,r=1;
	if(p==q)
	{
		return p;
	}
	while((!(a&1))&&(!(b&1)))
	{
		r<<=1;
		a>>=1;
		b>>=1;
	}
	if(!(a&1))
    {
		t=a;
		a=b;
		b=t;
    }
    do
    {
		while(!(b&1))
		{
			b>>=1;
		}
		if(b<a)	
		{
			t=a;
			a=b;
			b=t;
		}
		b=(b-a)>>1;
    }while(b);
    return r*a;
}

unsigned __int64 ModReverse(unsigned __int64 &a,unsigned __int64 &b)
{
	unsigned __int64 m,e,i,j,x,y;
	long xx,yy;
	m=b;
	e=a;
	x=0;
	y=1;
	xx=1;
	yy=1;
	while(e)
	{
		i=m/e;
		j=m%e;
		m=e;
		e=j;
		j=y;
		y*=i;
		if(xx==yy)
		{
			if(x>y)
			{
				y=x-y;
			}
			else 
			{
				y-=x;
				yy=0;
			}
		}
		else 
		{
			y+=x;
			xx=1-xx;
			yy=1-yy;
		}
		x=j;
	}
	if(xx==0)
	{
		x=b-x;
	}
	return x;
}



RSA_PARAM RsaGetParam(void)
{
  RSA_PARAM Rsa={0};
  unsigned __int64 t;
  Rsa.p=RandomPrime(16);
  Rsa.q=RandomPrime(16);
  Rsa.n=Rsa.p*Rsa.q;
  Rsa.f=(Rsa.p-1)*(Rsa.q-1);
  do 
  {
    Rsa.e=g_Rnd.Random(65536);
    Rsa.e|=1;
  }while(SteinGcd(Rsa.e,Rsa.f)!=1);
  Rsa.d=ModReverse(Rsa.e, Rsa.f);
  Rsa.s=0;
  t=Rsa.n>>1;
  while(t)
  {
    Rsa.s++;
    t>>=1;
  }
  return Rsa;
}



void TestRSA(void)
{
	RSA_PARAM r;
	char pSrc[]= {"abcdefghijklmnopqrstuvwxyz"};
	const unsigned long n=sizeof(pSrc);
	unsigned char *q;
	unsigned __int64 pEnc[n],pDec[n];
	unsigned long i;

	r=RsaGetParam();
	printf("p = %I64u\n", r.p);
	printf("q = %I64u\n", r.q);
	printf("f=(p-1)*(q-1)= %I64u\n", r.f);
	printf("n=p*q= %I64u\n", r.n);
	printf("e = %I64u\n", r.e);
	printf("d = %I64u\n", r.d);
	printf("s = %I64u\n", r.s);
	printf("Source: %s\n", pSrc);
	q=(unsigned char *)pSrc;
	printf("Encode:");
	for(i=0;i<n;i++)
	{
		unsigned __int64 base;
		base = (unsigned __int64)q[i];
		pEnc[i]=PowMod(base, r.e, r.n);
	}
	printf("\n");
	printf("Decode: ");
	for(i=0;i<n;i++)
	{
		pDec[i]=PowMod(pEnc[i], r.d, r.n);
		printf("%c", pDec[i]);
	}
	printf("\n");
}

int main(void)
{
  TestRSA();
  return 0;
}

2010-12-24 08:40
0
游客
登录 | 注册 方可回帖
返回
//