rsadesign.cpp

RSA公钥加密的基本实现 bmp灰度图片加解密操作包括 RSA 的加减密算法； 素数检测算法；RSA 密钥生成算法； 应用该 RSA 密码体制加、解密； BMP 灰度图的算法； Pollard p-1

#include "RSA.h"
#include <iostream>
#include <stdlib.h>

using namespace std;

long MillerRabin(long n)//Prime check, is return n;else return -1
{
//n-1=2^k * m
    long k=0,m=0;
    long newn=n-1;
    for (long i=0; m ==0 ; i++)
    {
        if (OddEvenTest(newn)==1)
        {
            m=newn;
            break;
        }
        else
        {
            newn=newn/2;
            k++;
        }
    }
//    cout << "n-1 =" << n-1 <<" "<< "k m"<<k <<" "<<m<<endl;
//get a ;1<=a<=n-1
    long tempa[MAX_N]={0};
    for (long i=0; i<MAX_N ;i++)
        tempa[i]=i;
    srand((unsigned)time(NULL));
    long a = tempa[rand()%(n-1)];
//b= a^m % n
    long Binary_m[100];//Binary of m
    long l_m;//length of m
    l_m=NumberToBinary(Binary_m, m);
    long b=SquareMultiply(Binary_m, n, a, l_m);
    if ((b%n)==1)  return n;
    for (long i=0; i<=k-1; i++)
    {
        if ((b%n)==n-1) return n;
        else b=(b*b)%n;
    }
    return -1;
}
long OddEvenTest(long n)//if odd return 1, even return 2
{
    long m = n%2;
    if (m==0) return 2;
    else return 1;
}
long NumberToBinary(long *Out, long In)
//Number change to Binary, ok return bits
{
    long count=0;
    long tempin=In;
    long temp[MAX_E_D]={0};
    do{
        temp[count]=tempin%2;
        tempin=tempin/2;
        if (tempin==1)
        {
            temp[count+1]=1;
            break;
        }
        count++;
    }while(1);
    count=count+2;
//    bits=&count;
    long i=0;
    for (long j=count-1; i<count; i++)
    {
        Out[j]=temp[i];
        j--;
    }
    return count;
}
long SquareMultiply(long *In, long n, long x, long l)
//Square_And_Multiply, z=x^c mod n, In is the z's Binary, l is the In's length
{
    long long z=1;
    for (long i=0; i<=l-1; i++)
    {
        z=(z*z)%n;
        if (In[i]==1)
        {
            z=(z*x)%n;
        }
    }
    return z;
}

long MultiplicativeInverse(long a, long b)
//get b_1
{
    long a0=a,b0=b,t0=0,t=1;
    long q=a0/b0;
    long r=a0-q*b0;
    while (r>0)
    {
        long temp=(t0-q*t)%a;
        t0=t;
        t=temp;
        a0=b0;
        b0=r;
        q=a0/b0;
        r=a0-q*b0;
    }
    if (b0!=1)
//        cout<<NO b_1 exits!!!!<<endl;
        return -1;
    else
        return t;
}