一个RSA算法的加密运算，需要完整的演算过程。

那我给你解释下RSA吧，尽量让你看懂：

*RSA是非对称加密体系，也就是说加密用一个公钥，解密用一个私钥，这2个密钥不同，这点非常非常重要。

其实RSA非常简洁，但很美

流程

1，寻找2个大的素数p，q n=p*q=33 N=（p-1）*（q-1）=20

公钥e一般是3 私钥d要通过公钥e去算出指塌来

e*d=1(mod N) 就是说e和d的乘积模N得1 也就是e和d关于模N互为逆元

3*7=1（mod 20） 可知d=7

加密的明文设为M 加密后的密文设为c

加密过程：C=M^e(mod n)

解密过程：M=C^d(mod n)

举个具体的例子 假如M=2

加密过程：C=2^3(mod 33)=8(mod 33)

解密过程：M=8^7(mod 33)=2097152(mod 33)=2(mod 33) 可以看出和和本来的明文是相同的。

原理可以理解为 M=M^(ed) (mod n)

本例中 e*d=21 也就是是M^21次方等于M

RSA这个特性是数论中的费马定理推出的

在讲讲细节 比如楼主加密的是26的字母 就当明文的值是从1到26

就拿n=33说吧 加密后的密文的值是1到33 这很正常

但是派前解密后 一定和明文的值相同 也就是1到26

实际情况中 公钥e是公开的 私钥d是保密的

比如甲要给乙发个东西 乙的公钥由于是公开的 所以甲知道 但甲不知道乙的私钥

甲先用乙的公钥加密 之后 这个密文只能用乙的私钥 由于乙的私钥是保密的 只有他自己知道 所以保证了安全

RSA最大的安全问题是 n的分解 只要把n分解为p*q 则N=（p-1）（q-1）

根据 e*d=1（mod N） 就可以通过e算出d 那么私钥都被人算出来了 也就没安全性而言了

不过可惜的是 大数分解是一个单向的函数 你算知道p，q算n很容易，但是知道n算出p，q相当难

强调一句 n是加密解尘逗清密用的 N是知道e算d的

楼主也没说你要干嘛 想看懂就这么多

如果要实现这个算法：

必须知道2点：

1.p，q这个两个大素数的生成，这牵扯到素性检验，数论中是一章的内容，没法和你展开

2.取模运算，由于加密解密过程可能取一个数的几十次方的模数，所以这个必须用简便的算法来化解复杂度，也就是模重复平方算法。

如果要编程中使用，太容易了

去下个dll

在java中 直接有可用于RSA的类 相当容易

如果楼主想研究的更深 可以把邮箱 发我 RSA我以前做过一个ppt

看你催就仓促写了个，自我感觉写的不是很好，但是能用了。数据只能是大写字母组成的字符串。

加密的时候，输入Y，然后输入要加密的文本（厅空搏大写字母）

解密的时候，输入N，然后输入一个整数n表示密文的个数，然后n个整数表示加密时候得到的密文。

/*RSA algorithm */

#include <stdio.h>

#include <string.h>

#include <亏桥stdlib.h>

#define MM 7081

#define KK 1789

#define PHIM 6912

#define PP 85

typedef char strtype[10000]

int len

long nume[10000]

int change[126]

char antichange[37]

void initialize()

{ int i

char c

for (i = 11, c = 'A'c <= 'Z'c ++, i ++)

{ change[c] = i

antichange[i] = c

}

}

void changetonum(strtype str)

{ int l = strlen(str), i

len = 0

memset(nume, 0, sizeof(nume))

for (i = 0i <li ++)

{ nume[len] = nume[len] * 100 + change[str[i]]

if (i % 2 == 1) len ++

}

if (i % 2 != 0) len ++

}

long binamod(long numb, long k)

{ if (k == 0) return 1

long curr = binamod (numb, k / 2)

if (k % 2 == 0)

return curr * curr % MM

else return (curr * curr) % MM * numb % MM

}

long encode(long numb)

{ return binamod(numb, KK)

}

long decode(long numb)

{ return binamod(numb, PP)

}

main()

{ strtype str

int i, a1, a2

long curr

initialize()

puts("Input 'Y' if encoding, otherwise input 'N':")

gets(str)

if (str[0] == 'Y')

{ gets(str)

changetonum(str)

printf("encoded: ")

for (i = 0i <leni ++)

{ if (i) putchar('-')

printf(" %ld ", encode(nume[i]))

}

putchar('\n')

}

else

{ scanf("%d", &len)

for (i = 0i <leni ++)

{ scanf("%ld", &curr)

curr = decode(curr)

a1 = curr / 100

a2 = curr % 100

printf("扮祥decoded: ")

if (a1 != 0) putchar(antichange[a1])

if (a2 != 0) putchar(antichange[a2])

}

putchar('\n')

}

putchar('\n')

system("PAUSE")

return 0

}

测试：

输入：

Y

FERMAT

输出：

encoded: 5192 - 2604 - 4222

输入

N

3 5192 2604 4222

输出

decoded: FERMAT

总括： 本文详细讲述了RSA算法详解，包括内部使用数学原理以及产生的过程。

相濡以沫。到底需要爱淡如水。

之前写过一篇文章 SSL协议之数据加密过程 ，里面详细讲述了数据加密的过程以及需要的算法。SSL协议很巧妙的利用对称加密和非对称加密两种算法来对数据进行加密。这篇文章主要是针对一种最常见的非对称加密算法——RSA算法进行讲解。其实也就是对私钥和公钥产生的一种方式进行描述。首先先来了解下这个算法的历史：

RSA是1977年由 罗纳德·李维斯特 （Ron Rivest）、 阿迪·萨莫尔 （Adi Shamir）和 伦纳德·阿德曼 （Leonard Adleman）一起提出的。当时他们三人都在 麻省理工学院 工作。RSA就是他们三人姓氏开头字母拼在一起组成的。

但实际上，在1973年，在英国政府通讯总部工作的数学家 克利福德·柯克斯 （Clifford Cocks）在一个内部文件中提出灶雀了一个相同的算法，但他的发现被列入机密，一直到1997年才被发表。

所以谁是RSA算法的发明人呢？不好说，就好像贝尔并不是第一个发明电话的人但大家都记住的是贝尔一样，桐辩岁这个地方我们作为旁观者倒不用较真，重要的是这个算法的内容：

RSA算法用到的数学知识特别多，所以在中间介绍这个算法生成私钥和公钥的过程中会穿插一些数学知识。生成步骤如下：

随意选择两个大的质数p和q，p不等于q，计算N=p*q

什么是质数?我想可能会有一部分人已经忘记了，定义如下：

比如2，3，5，7这些都是质数，9就不是了，因为3*3=9了

r = φ(N) = φ(p)φ(q) = (p-1)(q-1) 。

这里的数学概念就是什么是欧拉函数了，什么是欧拉函数呢？

欧拉函数 的定义：

互质 的定义：

例如： φ(8) = 4 ，因为 1,3,5,7 均和 8 互质。

推导欧拉函数:

（1）如果 n = 1 , φ(1) = 1 ；(小于等于1的正整数中唯一和1互质的数就是1本身)；

（2）如果 n 为质数， φ(n) = n - 1 ；因为质数和每一个比它小的数字都互质。比如5，比它小的正整数1,2,3,4都和他互质；

(3) 如果 n 是 a 的 k 次幂，则 φ(n) = φ(a^k) = a^k - a^(k-1) = (a-1)a^(k-1) ；

(4) 若 m , n 互质，则 φ(mn) = φ(m)φ(n)

证明： 设 A , B , C 是跟 m , n , mn 互质的数的集，据 中国剩余定理 (经常看数学典故的童鞋应该了解，剩余定理又叫韩信点兵，也叫孙子定理)， A * B 和 C 可建立双射一一对应)的关系。（或者也可以从初等代数角度给出 欧拉函数积性的简单证明 ） 因此的φ(n)值使用 算术基本定理 便知。（来自维基百科）

选择一个小于r并与r互质的整数e，求得e关于r的模反元素，命名为 d （ ed = 1(mod r) 模反元素存在，当且仅当e与r互质）， e 我们通常取65537。

模反元素：

比如 3 和 5 互质， 3 关于 5 的模反元素就可能是2，因为 3*2-1=5 可以被5整除。所以很明显模反元素不止一个，2加减5的整数倍都是3关于5的模反元素 {...-3, 2,7,12…} 放在公式里就是 3*2 = 1 (mod 5)

上面所提到的欧拉函数用处实际上在于欧拉定理：

欧拉定局睁理：

欧拉定理就可以用来证明模反元素必然存在。

由模反元素的定义和欧拉定理我们知道， a 的 φ(n) 次方减去1，可以被n整除。比如，3和5互质，而 5 的欧拉函数 φ(5) 等于4，所以 3 的 4 次方 (81) 减去1，可以被 5 整除（ 80/5=16 ）。

小费马定理：

此时我们的 (N , e) 是公钥， (N, d) 为私钥，爱丽丝会把公钥 (N, e) 传给鲍勃，然后将 (N, d) 自己藏起来。一对公钥和私钥就产生了，然后具体的使用方法呢？请看： SSL协议之数据加密过程详解

我们知道像RSA这种非对称加密算法很安全，那么到底为啥子安全呢？

我们来看看上面这几个过程产生的几个数字：

N 和 e 我们都会公开使用，最为重要的就是私钥中的 d ， d 一旦泄露，加密也就失去了意义。那么得到d的过程是如何的呢？如下:

所以得出了在上篇博客说到的结论，非对称加密的原理：

将a和b相乘得出乘积c很容易，但要是想要通过乘积c推导出a和b极难。即对一个大数进行因式分解极难

目前公开破译的位数是768位，实际使用一般是1024位或是2048位，所以理论上特别的安全。

RSA算法的核心就是欧拉定理，根据它我们才能得到私钥，从而保证整个通信的安全。

---