c语言对英文字母循环加密 RSA加密算法(C语言实现）

这次轮到RSA加密算法了。RSA加密过程相对DES和MD5要简单很多，但作为现在还在使用的加密算法之一，它还是有需要认真思索的地方哒~

首先是密钥对的生成：

(1)选取两个大素数p和q(目前两个数的长度都接近512bit是安全的)

(2)计算乘积n=p*q，Φ(n)=(p-1)(q-1)，其中Φ(n)为n的欧拉函数(因为两素数乘积的欧拉函数等于两数分别减一后的乘积)

(3)随机选取整数e(1

(4)用Euclid扩展算法计算私钥d，已满足d * e ≡ 1 (mod Φ(n))，即d ≡ e^(-1) (mod Φ(n))。则e与n是公钥，d是私钥

注意：e与n应公开，两个素数p和q不再需要，可销毁，但绝不可泄露。

加密过程：

将接收到的明文转换成特定的编码方式。如p=43，q=59，e=13，明文为cybergreatwall，按照英文字母表的顺序a=00，b=01，... ，z=25进行编码后为022401041706001922001111。

然后将转码后的字符串分块，分组要求：每个分组对应的十进制数小于0。这个要求是什么意思呢？我个人的理解通过举例向大家说明：上文字符串分组如下0224 0104 1706 0019 2200 1111。每一分组的数都小于n(2537)，而2537能接受的最大的数为2525(也就是‘zz’的情况)，所以是4位1组，即两字符一组。这样一来，m1=0224，m2=0104，... ，m6=1111

现在可以加密了~~加密算法就是这个式子----ci≡ mi^e (mod n)，如第一分组 0224^13≡ mod 2537≡ 1692=c1 。这里有个隐藏的算法是需要了解的：

在RSA算法过程中容易出现天文数字(像上文的0224^13)，而这些天文数字会为我们编程的过程造成一定的麻烦，更可恶的是会影响速度！！为了避免这种情况，快速取模指数算法可以很有效地算出c≡m^e mod n的准确结果且避免过程中出现天文数字~~

下面用伪代码为大家介绍下这种神奇的算法(个人感觉伪代码里的 ‘

t

for i

do t

c

if bi=1 then t

c

return c

(p.s：e的二进制表示为bk bk-1 ... b0，如e=13=(1101)，所以k为3)

所以，用快速取模指数算法计算上文例子里的c1过程就该是这样子哒：

i 3 2 1 0

bi1 1 0 1

t 1 3 6 13

ci (1*224)mod2537 (224*224*224)mod2537 (514*514)mod2537 (348*348*224)mod2537

=224 =514 =348 =1692

到这里RSA加密的算法就讲完了，下面附上代码

#include

#include

/* 函数申明 */

int long_n(int n);

int shuru(char *arr, int k, char *wei, int is_first);

void jiami(char *arr, int k, int e, int n);

/* 输入函数，记录从键盘输入的明文*/

int shuru(char *arr, int k, char *wei, int is_first)

{

int i;

char ch;

/*判断是否为第一分组的输入，如果是则获取输入的字符，否则就将上一分组最后获取的字符作为这一分组的第一个字符*/

if (is_first == 1)

ch = getchar();

else

ch = *wei;

for (i = 0; (i < k) && (ch != '\n');i++) //获取字符直到获取到回车符为止

{

arr[i] = ch;

ch = getchar();

}

*wei = ch; //最后获取到的字符准备作为下一分组的第一个字符

for (i = i; i < k; i++)

arr[i] = 'a'; //输入不够一组个数的整数倍则补'a'(即为补零)

if (ch == '\n') //接收到回车符返回0，否则为1

return 0;

else

return 1;

}

/*加密函数*/

void jiami(char *arr, int k, int e, int n)

{

int m = 0,c=1, i, j,t=0, shu,temp,num=0;

int *array;

/*Mi赋值过程*/

for (i = 0; i < k; i++)

{

temp = 1;

for (j = 0; j < (k-i-1)*2; j++)

temp = temp * 10;

shu = (int)arr[i] - 97;

m = m + temp * shu;

}

temp = e;

/*获取e的二进制表达形式的位数*/

do{

temp = temp / 2;

num++;

} while (temp != 0);

array = (int *)malloc(sizeof(int)*k); //申请动态数组

temp = e;

/*动态数组存储e的二进制表达形式*/

for (i = 0; i < num; i++)

{

array[i] = temp % 2;

temp = temp / 2;

}

/*避免出现天文数字的算法，详情见上文文字说明*/

for (i = num - 1; i >= 0; i--)

{

t = t * 2;

temp = c*c;

if (temp > n)

{

for (j = 0; temp - n*j >= 0; j++);

j--;

c = temp - n*j;

}

else

c = temp;

if (array[i] == 1)

{

t = t + 1;

temp = c*m;

if (temp > n)

{

for (j = 0; temp - n*j >= 0; j++);

j--;

c = temp - n*j;

}

else

c = temp;

}

e = e / 2;

}

temp = c;

i = 0;

/*c的位数小于分组长度则在前补零*/

do{

temp = temp / 10;

i++;

} while (temp != 0);

for (i; i < num; i++)

printf("0");

printf("%d", c);

}

/*获取分组的长度*/

int long_n(int n)

{

int temp,i,j,k,shi,comp=0;

temp = n;

/*获取n的位数*/

for (i = 1; temp / 10 != 0; i++)

{

temp = temp / 10;

}

temp = i;

/*若n的位数为基数*/

if (i % 2 != 0)

{

i = i - 1;

return i;

}

/*若位数为偶数*/

else

{

for (j = 0; j < i/2; j++)

{

shi = 1;

for (k = 0; k < temp - 2; k++)

shi = shi * 10;

comp = comp + shi * 25;

temp = temp - 2;

}

if (comp <= n)

return i;

else

{

i = i - 2;

return i;

}

}

}

/*主函数*/

int main()

{

int p, q, e, d, n, fai_n, k, i,is_first=1;

char ch,*arr,wei='a';

printf("请输入p、q、e值，用空格间隔开\n");

scanf_s("%d%d%d", &p, &q, &e); //从键盘获取p、q、e值

n = p*q;

fai_n = (p-1)*(q-1); //Φ(n)

for (k = 0; (k*n + 1) % e != 0; k++);

if ((k*n + 1) % e == 0)

d = (k*n + 1) / e; //d * e ≡ 1 (mod Φ(n))

k = long_n(n);

k = k / 2; //分组的长度

ch = getchar(); //缓冲回车符

arr = (char *)malloc(sizeof(char)*k); //申请动态数组

printf("请输入明文\n");

while (1)

{

i=shuru(arr,k,&wei,is_first); //调用输入字符的函数，接收到回车符返回0，否则为1

is_first = 0; //第一分组录入结束设为0

jiami(arr,k,e,n); //调用加密函数

if (i == 0) //接收到返回值为0跳出循环

break;

}

printf("\n");

return 0;

}

运行结果：

如果有对算法和代码不理解或者有不同看法的请联系我哦，邮箱在我的信息里~~