A. 什么是RSA非对称加密
非对称密钥——RSA算法
RSA算法是最流行的公钥密码算法，使用长度可以变化的密钥。RSA是第一个既能用于数据加密也能用于数字签名的算法。
RSA算法原理如下：
1.随机选择两个大质数p和q，p不等于q，计算N=pq；
2.选择一个大于1小于N的自然数e，e必须与(p-1)(q-1)互素。
3.用公式计算出d：d×e = 1 (mod (p-1)(q-1)) 。
4.销毁p和q。
最终得到的N和e就是“公钥”，d就是“私钥”，发送方使用N去加密数据，接收方只有使用d才能解开数据内容。
RSA的安全性依赖于大数分解，小于1024位的N已经被证明是不安全的，而且由于RSA算法进行的都是大数计算，使得RSA最快的情况也比DES慢上倍，这是RSA最大的缺陷，因此通常只能用于加密少量数据或者加密密钥，但RSA仍然不失为一种高强度的算法。
B. RSA 加密算法（原理篇）
前几天看到一句话，“我们中的很多人把一生中最灿烂的笑容大部分都献给了手机和电脑屏幕”。心中一惊，这说明了什么？手机和电脑已经成为了我们生活中的一部分，所以才会有最懂你的不是你，也不是你男朋友，而是大数据。
如此重要的个人数据，怎样才能保证其在互联网上的安全传输呢？当然要靠各种加密算法。说起加密算法，大家都知道有哈希、对称加密和非对称加密了。哈希是一个散列函数，具有不可逆操作；对称加密即加密和解密使用同一个密钥，而非对称加密加密和解密自然就是两个密钥了。稍微深入一些的，还要说出非对称加密算法有DES、3DES、RC4等，非对称加密算法自然就是RSA了。那么当我们聊起RSA时，我们又在聊些什么呢？今天笔者和大家一起探讨一下，有不足的地方，还望各位朋友多多提意见，共同进步。
RSA简介：1976年由麻省理工学院三位数学家共同提出的，为了纪念这一里程碑式的成就，就用他们三个人的名字首字母作为算法的命名。即 罗纳德·李维斯特 （Ron Rivest）、 阿迪·萨莫尔 （Adi Shamir）和 伦纳德·阿德曼 （Leonard Adleman）。
公钥：用于加密，验签。
私钥：解密，加签。
通常知道了公钥和私钥的用途以后，即可满足基本的聊天需求了。但是我们今天的主要任务是来探究一下RSA加解密的原理。
说起加密算法的原理部分，肯定与数学知识脱不了关系。
我们先来回忆几个数学知识：
φn = φ(A*B)=φ(A)*φ(B)=(A-1)*(B-1)。
这个公式主要是用来计算给定一个任意的正整数n，在小于等于n的正整数中，有多少个与n构成互质的关系。
其中n=A*B，A与B互为质数，但A与B本身并不要求为质数，可以继续展开，直至都为质数。
在最终分解完成后，即 φ(N) = φ(p1)*φ(p2)*φ(p3)... 之后，p1，p2，p3都是质数。又用到了欧拉函数的另一个特点，即当p是质数的时候，φp = p - 1。所以有了上面给出的欧拉定理公式。
举例看一下：
计算15的欧拉函数，因为15比较小，我们可以直接看一下，小于15的正整数有 1、2、3、4、5、6、7、8、9、10、11、12、13、14。和15互质的数有1、2、4、7、8、11、13、14一共四个。
对照我们刚才的欧拉定理： 。
其他感兴趣的，大家可以自己验证。
之所以要在这里介绍欧拉函数，我们在计算公钥和私钥时候，会用到。
如果两个正整数m 和 n 互质，那么m 的 φn 次方减1，可以被n整除。
其中 .
其中当n为质数时，那么 上面看到的公式就变成了
mod n 1.
这个公式也就是着名的 费马小定理 了。
如果两个正整数e和x互为质数，那么一定存在一个整数d，不止一个，使得 e*d - 1 可以被x整除，即 e * d mode x 1。则称 d 是 e 相对于 x的模反元素。
了解了上面所讲的欧拉函数、欧拉定理和模反元素后，就要来一些化学反应了，请看图：
上面这幅图的公式变化有没有没看明白的，没看明白的咱们评论区见哈。
最终我们得到了最重要的第5个公式的变形，即红色箭头后面的：
mod n m。
其中有几个关系，需要搞明白，m 与 n 互为质数，φn = x，d 是e相对于x的模反元素。
有没有看到一些加解密的雏形。
从 m 到 m。 这中间涵盖了从加密到解密的整个过程，但是缺少了我们想要的密文整个过程。
OK，下面引入本文的第四个数学公式：
我们来看一下整个交换流程：
1、客户端有一个数字13，服务端有一个数字15;
2、客户端通过计算 3的13次方 对 17 取余，得到数字12; 将12发送给服务端；同时服务端通过计算3的15次方，对17取余，得到数字6，将6发送给客户端。至此，整个交换过程完成。
3、服务端收到数字12以后，继续计算，12的15次方 对 17取余，得到 数字10。
4、客户端收到数字 6以后，继续计算，6的13次方 对 17 取余，得到数字 10。
有没有发现双方，最终得到了相同的内容10。但是这个数字10从来没有在网络过程中出现过。
好，讲到这里，可能有些人已经恍然大悟，这就是加密过程了，但是也有人会产生疑问，为什么要取数字3 和 17 呢，这里还牵涉到另一个数学知识，原根的问题。即3是17的原根。看图
有没有发现规律，3的1~16次方，对17取余，得到的整数是从1~16。这时我们称3为17的原根。也就是说上面的计算过程中有一组原根的关系。这是最早的迪菲赫尔曼秘钥交换算法。
解决了为什么取3和17的问题后，下面继续来看最终的RSA是如何产生的：
还记得我们上面提到的欧拉定理吗，其中 m 与 n 互为质数，n为质数，d 是 e 相对于 φn的模反元素。
当迪菲赫尔曼密钥交换算法碰上欧拉定理会产生什么呢？
我们得到下面的推论：
好，到这里我们是不是已经看到了整个的加密和解密过程了。
其中 m 是明文；c 是密文； n 和 e 为公钥；d 和 n 为私钥 。
其中几组数字的关系一定要明确：
1、d是e 相对于 φn 的模反元素，φn = n-1，即 e * d mod n = 1.
2、m 小于 n，上面在讲迪菲赫尔曼密钥交换算法时，提到原根的问题，在RSA加密算法中，对m和n并没有原根条件的约束。只要满足m与n互为质数，n为质数，且m < n就可以了。
OK，上面就是RSA加密算法的原理了，经过上面几个数学公式的狂轰乱炸，是不是有点迷乱了，给大家一些时间理一下，后面会和大家一起来验证RSA算法以及RSA为什么安全。
C. 密码学基础1：RSA算法原理全面解析
本节内容中可能用到的符号说明如下：
质数和合数： 质数是指除了平凡约数1和自身之外，没有其他约数的大于1的正整数。大于1的正整数中不是素数的则为合数。如 7、11 是质数，而 4、9 是合数。在 RSA 算法中主要用到了质数相关性质，质数可能是上帝留给人类的一把钥匙，许多数学定理和猜想都跟质数有关。
[定理1] 除法定理： 对任意整数 a 和 任意正整数 n，存在唯一的整数 q 和 r，满足 。其中， 称为除法的商，而 称为除法的余数。
整除： 在除法定理中，当余数 时，表示 a 能被 n 整除，或者说 a 是 n 的倍数，用符号 表示。
约数和倍数 ： 对于整数 d 和 a，如果 ，且 ，则我们说 d 是 a 的约数，a 是 d 的倍数。
公约数： 对于整数 d，a，b，如果 d 是 a 的约数且 d 也是 b 的约数，则 d 是 a 和 b 的公约数。如 30 的约数有 1，2，3，5，6，10，15，30，而 24 的约数有 1，2，3，4，6，8，12，24，则 30 和 24 的公约数有 1，2，3，6。其中 1 是任意两个整数的公约数。
公约数的性质：
最大公约数： 两个整数最大的公约数称为最大公约数，用 来表示，如 30 和 24 的最大公约数是 6。 有一些显而易见的性质：
[定理2] 最大公约数定理： 如果 a 和 b 是不为0的整数，则 是 a 和 b 的线性组合集合 中的最小正元素。
由定理2可以得到一个推论：
[推论1] 对任意整数 a 和 b，如果 且 ，则 。
互质数： 如果两个整数 a 和 b 只有公因数 1，即 ，则我们就称这两个数是互质数(coprime）。比如 4 和 9 是互质数，但是 15 和 25 不是互质数。
互质数的性质：
欧几里得算法分为朴素欧几里得算法和扩展欧几里得算法，朴素法用于求两个数的最大公约数，而扩展的欧几里得算法则有更多广泛应用，如后面要提到的求一个数对特定模数的模逆元素等。
求两个非负整数的最大公约数最有名的是 辗转相除法，最早出现在伟大的数学家欧几里得在他的经典巨作《几何原本》中。辗转相除法算法求两个非负整数的最大公约数描述如下：
例如， ，在求解过程中，较大的数缩小，持续进行同样的计算可以不断缩小这两个数直至其中一个变成零。
欧几里得算法的python实现如下：
扩展欧几里得算法在 RSA 算法中求模反元素有很重要的应用，定义如下：
定义： 对于不全为 0 的非负整数 ，则必然存在整数对 ，使得
例如，a 为 3，b 为 8，则 。那么，必然存在整数对 ，满足 。简单计算可以得到 满足要求。
扩展欧几里得算法的python实现如下：
同余： 对于正整数 n 和 整数 a，b，如果满足 ，即 a-b 是 n 的倍数，则我们称 a 和 b 对模 n 同余，记号如下： 例如，因为 ，于是有 。
对于正整数 n，整数 ，如果 则我们可以得到如下性质：
譬如，因为 ，则可以推出 。
另外，若 p 和 q 互质，且 ，则可推出：
此外，模的四则运算还有如下一些性质，证明也比较简单，略去。
模逆元素： 对整数 a 和正整数 n，a 对模数 n 的模逆元素是指满足以下条件的整数 b。 a 对 模数 n 的 模逆元素不一定存在，a 对 模数 n 的模逆元素存在的充分必要条件是 a 和 n 互质，这个在后面我们会有证明。若模逆元素存在，也不是唯一的。例如 a=3，n=4，则 a 对模数 n 的模逆元素为 7 + 4k，即 7，11，15，...都是整数 3 对模数 4 的模逆元素。如果 a 和 n 不互质，如 a = 2，n = 4，则不存在模逆元素。
[推论2] 模逆元素存在的充分必要条件是整数 a 和 模数 n 互质。
[定理3] 唯一质数分解定理： 任何一个大于1的正整数 n 都可以 唯一分解 为一组质数的乘积，其中 都是自然数(包括0)。比如 6000 可以唯一分解为 。
由质数唯一分解定理可以得到一个推论： 质数有无穷多个 。
[定理4] 中国剩余定理(Chinese remainder theorem，CRT) ，最早见于《孙子算经》(中国南北朝数学着作，公元420-589年)，叫物不知数问题，也叫韩信点兵问题。
翻译过来就是已知一个一元线性同余方程组求 x 的解：
宋朝着名数学家秦九韶在他的着作中给出了物不知数问题的解法，明朝的数学家程大位甚至编了一个《孙子歌诀》：
意思就是：将除以 3 的余数 2 乘以 70，将除以 5 的余数 3 乘以 21，将除以 7 的余数 2 乘以 15，最终将这三个数相加得到 。再将 233 除以 3，5，7 的最小公倍数 105 得到的余数 ，即为符合要求的最小正整数，实际上， 都符合要求。
物不知数问题解法本质
求解通项公式
中国剩余定理相当于给出了以下的一元线性同余方程组的有解的判定条件，并用构造法给出了解的具体形式。
模数 两两互质 ，则对任意的整数： ，方程组 有解，且解可以由如下构造方法得到：
并设 是除 以外的其他 个模数的乘积。
中国剩余定理通项公式证明
D. rsa算法原理
RSA算法是最常用的非对称加密算法，它既能用于加密，也能用于数字签名。RSA的安全基于大数分解的难度。其公钥和私钥是一对大素数（100到200位十进制数或更大）的函数。从一个公钥和密文恢复出明文的难度，等价于分解两个大素数之积。
我们可以通过一个简单的例子来理解RSA的工作原理。为了便于计算。在以下实例中只选取小数值的素数p,q,以及e，假设用户A需要将明文“key”通过RSA加密后传递给用户B，过程如下：设计公私密钥(e,n)和(d,n)。
令p=3，q=11，得出n=p×q=3×11=33；f(n)=(p-1)(q-1)=2×10=20；取e=3，（3与20互质）则e×d≡1 mod f(n)，即3×d≡1 mod 20。通过试算我们找到，当d=7时，e×d≡1 mod f(n)同余等式成立。因此，可令d=7。从而我们可以设计出一对公私密钥，加密密钥（公钥）为：KU =(e,n)=(3,33)，解密密钥（私钥）为：KR =(d,n)=(7,33)。
英文数字化。将明文信息数字化，并将每块两个数字分组。假定明文英文字母编码表为按字母顺序排列数值。则得到分组后的key的明文信息为：11，05，25。
明文加密。用户加密密钥(3,33) 将数字化明文分组信息加密成密文。由C≡Me(mod n)得：
C1(密文)≡M1（明文）^e (mod n) == 11≡11^3 mod 33 ;
C2(密文)≡M2（明文）^e (mod n) == 26≡05^3 mod 33;
C3(密文)≡M3（明文）^e (mod n) == 16≡25^3 mod 33;
所以密文为11.26.16。
密文解密。用户B收到密文，若将其解密，只需要计算，即：
M1(明文)≡C1（密文）^d (mod n) == 11≡11^7 mod 33;
M2(明文)≡C2（密文）^d (mod n) == 05≡26^7 mod 33;
M3(明文)≡C3（密文）^d (mod n) == 25≡16^7 mod 33;
转成明文11.05.25。根据上面的编码表将其转换为英文，我们又得到了恢复后的原文“key”。
当然，实际运用要比这复杂得多，由于RSA算法的公钥私钥的长度（模长度）要到1024位甚至2048位才能保证安全，因此，p、q、e的选取、公钥私钥的生成，加密解密模指数运算都有一定的计算程序，需要仰仗计算机高速完成。
E. 简述RSA算法中密钥的产生，数据加密和解密的过程，并简单说明RSA算法安全性的原理。
RSA算法的数学原理
RSA算法的数学原理:
先来找出三个数, p, q, r,
其中 p, q 是两个相异的质数, r 是与 (p-1)(q-1) 互质的数。
p, q, r 这三个数便是 private key。接着, 找出m, 使得 rm == 1 mod (p-1)(q-1)..... 这个 m 一定存在, 因为 r 与 (p-1)(q-1) 互质, 用辗转相除法就可以得到了..... 再来, 计算 n = pq....... m, n 这两个数便是 public key。
编码过程是, 若资料为 a, 将其看成是一个大整数, 假设 a < n.... 如果 a >= n 的话, 就将 a 表成 s 进位 (s <= n, 通常取 s = 2^t), 则每一位数均小于 n, 然后分段编码...... 接下来, 计算 b == a^m mod n, (0 <= b < n), b 就是编码后的资料...... 解码的过程是, 计算 c == b^r mod pq (0 <= c < pq), 于是乎, 解码完毕...... 等会会证明 c 和 a 其实是相等的 :) 如果第三者进行窃听时, 他会得到几个数: m, n(=pq), b...... 他如果要解码的话, 必须想办法得到 r...... 所以, 他必须先对 n 作质因数分解......... 要防止他分解, 最有效的方法是找两个非常的大质数 p, q, 使第三者作因数分解时发生困难......... <定理> 若 p, q 是相异质数, rm == 1 mod (p-1)(q-1), a 是任意一个正整数, b == a^m mod pq, c == b^r mod pq, 则 c == a mod pq 证明的过程, 会用到费马小定理, 叙述如下: m 是任一质数, n 是任一整数, 则 n^m == n mod m (换另一句话说, 如果 n 和 m 互质, 则 n^(m-1) == 1 mod m) 运用一些基本的群论的知识, 就可以很容易地证出费马小定理的........ <证明> 因为 rm == 1 mod (p-1)(q-1), 所以 rm = k(p-1)(q-1) + 1, 其中 k 是整数 因为在 molo 中是 preserve 乘法的 (x == y mod z and u == v mod z => xu == yv mod z), 所以, c == b^r == (a^m)^r == a^(rm) == a^(k(p-1)(q-1)+1) mod pq 1. 如果 a 不是 p 的倍数, 也不是 q 的倍数时, 则 a^(p-1) == 1 mod p (费马小定理) => a^(k(p-1)(q-1)) == 1 mod p a^(q-1) == 1 mod q (费马小定理) => a^(k(p-1)(q-1)) == 1 mod q 所以 p, q 均能整除 a^(k(p-1)(q-1)) - 1 => pq | a^(k(p-1)(q-1)) - 1 即 a^(k(p-1)(q-1)) == 1 mod pq => c == a^(k(p-1)(q-1)+1) == a mod pq 2. 如果 a 是 p 的倍数, 但不是 q 的倍数时, 则 a^(q-1) == 1 mod q (费马小定理) => a^(k(p-1)(q-1)) == 1 mod q => c == a^(k(p-1)(q-1)+1) == a mod q => q | c - a 因 p | a => c == a^(k(p-1)(q-1)+1) == 0 mod p => p | c - a 所以, pq | c - a => c == a mod pq 3. 如果 a 是 q 的倍数, 但不是 p 的倍数时, 证明同上 4. 如果 a 同时是 p 和 q 的倍数时, 则 pq | a => c == a^(k(p-1)(q-1)+1) == 0 mod pq => pq | c - a => c == a mod pq Q.E.D. 这个定理说明 a 经过编码为 b 再经过解码为 c 时, a == c mod n (n = pq).... 但我们在做编码解码时, 限制 0 <= a < n, 0 <= c < n, 所以这就是说 a 等于 c, 所以这个过程确实能做到编码解码的功能.....
F. 什么是RSA算法，求简单解释。
RSA公钥加密算法是1977年由Ron Rivest、Adi Shamirh和LenAdleman在（美国麻省理工学院）开发的。RSA取名来自开发他们三者的名字。RSA是目前最有影响力的公钥加密算法，它能够
抵抗到目前为止已知的所有密码攻击，已被ISO推荐为公钥数据加密标准。RSA算法基于一个十分简单的数论事实：将两个大素数相乘十分容易，但那时想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。由于进行的都是大数计算，使得RSA最快的情况也比DES慢上好几倍，无论是软件还是硬件实现。速度一直是RSA的缺陷。一般来说只用于少量数据加密。RSA的速度比对应同样安全级别的对称密码算法要慢1000倍左右。
基础
大数分解和素性检测——将两个大素数相乘在计算上很容易实现，但将该乘积分解为两个大素数因子的计算量是相当巨大的，以至于在实际计算中是不能实现的。
1.RSA密码体制的建立：
(1)选择两个不同的大素数p和q；
(2)计算乘积n=pq和Φ(n)=(p-1)(q-1)；
(3)选择大于1小于Φ(n)的随机整数e，使得gcd(e,Φ(n))=1；
(4)计算d使得de=1mod Φ(n)；
(5)对每一个密钥k=(n,p,q,d,e)，定义加密变换为Ek(x)=xemodn，解密变换为Dk(x)=ydmodn，这里x,y∈Zn；
(6)以{e,n}为公开密钥，{p,q,d}为私有密钥。
2.RSA算法实例:
下面用两个小素数7和17来建立一个简单的RSA算法：
(1)选择两个素数p=7和q=17；
(2)计算n=pq=7 17=119，计算Φ(n)=(p-1)(q-1)=6 16=96；
(3)选择一个随机整数e=5，它小于Φ(n)＝96并且于96互素；
(4)求出d，使得de=1mod96且d<96，此处求出d=77，因为 77 5＝385＝4 96＋1；
(5)输入明文M＝19，计算19模119的5次幂，Me＝195＝66mod119,传出密文C＝66；(6)接收密文66，计算66模119的77次幂；Cd=6677≡19mod119得到明文19。
G. rsa 的基本原理
1978年就出现了这种算法，它是第一个既能用于数据加密也能用于数字签名的算法。
它易于理解和操作，也很流行。算法的名字以发明者的名字命名：Ron Rivest, Adi
Shamir 和Leonard Adleman。但RSA的安全性一直未能得到理论上的证明。
RSA的安全性依赖于大数分解。公钥和私钥都是两个大素数（ 大于 100
个十进制位）的函数。据猜测，从一个密钥和密文推断出明文的难度等同于分解两个
大素数的积。
密钥对的产生。选择两个大素数，p 和q 。计算：
n = p * q
然后随机选择加密密钥e，要求 e 和 ( p - 1 ) * ( q - 1 ) 互质。最后，利用
Euclid 算法计算解密密钥d, 满足
e * d = 1 ( mod ( p - 1 ) * ( q - 1 ) )
其中n和d也要互质。数e和
n是公钥，d是私钥。两个素数p和q不再需要，应该丢弃，不要让任何人知道。
加密信息 m（二进制表示）时，首先把m分成等长数据块 m1 ,m2,..., mi ，块长s
，其中 2^s <= n, s 尽可能的大。对应的密文是：
ci = mi^e ( mod n ) ( a )
解密时作如下计算：
mi = ci^d ( mod n ) ( b )
RSA 可用于数字签名，方案是用 ( a ) 式签名， ( b )
式验证。具体操作时考虑到安全性和 m信息量较大等因素，一般是先作 HASH 运算。
RSA 的安全性。
RSA的安全性依赖于大数分解，但是否等同于大数分解一直未能得到理论上的证明，因
为没有证明破解
RSA就一定需要作大数分解。假设存在一种无须分解大数的算法，那它肯定可以修改成
为大数分解算法。目前， RSA
的一些变种算法已被证明等价于大数分解。不管怎样，分解n是最显然的攻击方法。现
在，人们已能分解140多个十进制位的大素数。因此，模数n
必须选大一些，因具体适用情况而定。
RSA的速度。
由于进行的都是大数计算，使得RSA最快的情况也比DES慢上100倍，无论是软件还是硬
件实现。速度一直是RSA的缺陷。一般来说只用于少量数据加密。
RSA的选择密文攻击。
RSA在选择密文攻击面前很脆弱。一般攻击者是将某一信息作一下伪装(
Blind)，让拥有私钥的实体签署。然后，经过计算就可得到它所想要的信息。实际上
，攻击利用的都是同一个弱点，即存在这样一个事实：乘幂保留了输入的乘法结构：
( XM )^d = X^d *M^d mod n
前面已经提到，这个固有的问题来自于公钥密码系统的最有用的特征--每个人都能使
用公钥。但从算法上无法解决这一问题，主要措施有两条：一条是采用好的公钥协议
，保证工作过程中实体不对其他实体任意产生的信息解密，不对自己一无所知的信息
签名；另一条是决不对陌生人送来的随机文档签名，签名时首先使用One-Way Hash
Function
对文档作HASH处理，或同时使用不同的签名算法。在中提到了几种不同类型的攻击方
法。
RSA的公共模数攻击。
若系统中共有一个模数，只是不同的人拥有不同的e和d，系统将是危险的。最普遍的
情况是同一信息用不同的公钥加密，这些公钥共模而且互质，那末该信息无需私钥就
可得到恢复。设P为信息明文，两个加密密钥为e1和e2，公共模数是n，则：
C1 = P^e1 mod n
C2 = P^e2 mod n
密码分析者知道n、e1、e2、C1和C2，就能得到P。
因为e1和e2互质，故用Euclidean算法能找到r和s，满足：
r * e1 + s * e2 = 1
假设r为负数，需再用Euclidean算法计算C1^(-1)，则
( C1^(-1) )^(-r) * C2^s = P mod n
另外，还有其它几种利用公共模数攻击的方法。总之，如果知道给定模数的一对e和d
，一是有利于攻击者分解模数，一是有利于攻击者计算出其它成对的e’和d’，而无
需分解模数。解决办法只有一个，那就是不要共享模数n。
RSA的小指数攻击。 有一种提高
RSA速度的建议是使公钥e取较小的值，这样会使加密变得易于实现，速度有所提高。
但这样作是不安全的，对付办法就是e和d都取较大的值。
RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。RSA是被研
究得最广泛的公钥算法，从提出到现在已近二十年，经历了各种攻击的考验，逐渐为
人们接受，普遍认为是目前最优秀的公钥方案之一。RSA
的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难
度等价。即RSA的重大缺陷是无法从理论上把握它的保密性能如何，而且密码学界多数
人士倾向于因子分解不是NPC问题。
RSA的缺点主要有：A)产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次
一密。B)分组长度太大，为保证安全性，n 至少也要 600 bits
以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大
数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。目前，SET(
Secure Electronic Transaction
)协议中要求CA采用2048比特长的密钥，其他实体使用1024比特的密钥。
DSS/DSA算法
Digital Signature Algorithm
(DSA)是Schnorr和ElGamal签名算法的变种，被美国NIST作为DSS(Digital Signature
Standard)。算法中应用了下述参数：
p：L bits长的素数。L是64的倍数，范围是512到1024；
q：p - 1的160bits的素因子；
g：g = h^((p-1)/q) mod p，h满足h < p - 1, h^((p-1)/q) mod p > 1；
x：x < q，x为私钥 ；
y：y = g^x mod p ，( p, q, g, y )为公钥；
H( x )：One-Way Hash函数。DSS中选用SHA( Secure Hash Algorithm )。
p, q,
g可由一组用户共享，但在实际应用中，使用公共模数可能会带来一定的威胁。签名及
验证协议如下：
1. P产生随机数k，k < q；
2. P计算 r = ( g^k mod p ) mod q
s = ( k^(-1) (H(m) + xr)) mod q
签名结果是( m, r, s )。
3. 验证时计算 w = s^(-1)mod q
u1 = ( H( m ) * w ) mod q
u2 = ( r * w ) mod q
v = (( g^u1 * y^u2 ) mod p ) mod q
若v = r，则认为签名有效。
DSA是基于整数有限域离散对数难题的，其安全性与RSA相比差不多。DSA的一个重要特
点是两个素数公开，这样，当使用别人的p和q时，即使不知道私钥，你也能确认它们
是否是随机产生的，还是作了手脚。RSA算法却作不到。
H. 加密基础知识二 非对称加密RSA算法和对称加密
上述过程中，出现了公钥(3233,17)和私钥(3233,2753)，这两组数字是怎么找出来的呢？参考 RSA算法原理（二）
首字母缩写说明：E是加密（Encryption）D是解密（Decryption）N是数字（Number）。
1.随机选择两个不相等的质数p和q。
alice选择了61和53。（实际应用中，这两个质数越大，就越难破解。）
2.计算p和q的乘积n。
n = 61×53 = 3233
n的长度就是密钥长度。3233写成二进制是110010100001，一共有12位，所以这个密钥就是12位。实际应用中，RSA密钥一般是1024位，重要场合则为2048位。
3.计算n的欧拉函数φ(n)。称作L
根据公式φ(n) = (p-1)(q-1)
alice算出φ(3233)等于60×52，即3120。
4.随机选择一个整数e，也就是公钥当中用来加密的那个数字
条件是1< e < φ(n)，且e与φ(n) 互质。
alice就在1到3120之间，随机选择了17。（实际应用中，常常选择65537。）
5.计算e对于φ(n)的模反元素d。也就是密钥当中用来解密的那个数字
所谓"模反元素"就是指有一个整数d，可以使得ed被φ(n)除的余数为1。ed ≡ 1 (mod φ(n))
alice找到了2753，即17*2753 mode 3120 = 1
6.将n和e封装成公钥，n和d封装成私钥。
在alice的例子中，n=3233，e=17，d=2753，所以公钥就是 (3233,17)，私钥就是（3233, 2753）。
上述故事中，blob为了偷偷地传输移动位数6，使用了公钥做加密，即6^17 mode 3233 = 824。alice收到824之后，进行解密，即824^2753 mod 3233 = 6。也就是说，alice成功收到了blob使用的移动位数。
再来复习一下整个流程：
p=17,q=19
n = 17 19 = 323
L = 16 18 = 144
E = 5(E需要满足以下两个条件：1<E<144,E和144互质)
D = 29(D要满足两个条件，1<D<144,D mode 144 = 1)
假设某个需要传递123，则加密后：123^5 mode 323 = 225
接收者收到225后，进行解密，225^ 29 mode 323 = 123
回顾上面的密钥生成步骤，一共出现六个数字：
p
q
n
L即φ(n)
e
d
这六个数字之中，公钥用到了两个（n和e），其余四个数字都是不公开的。其中最关键的是d，因为n和d组成了私钥，一旦d泄漏，就等于私钥泄漏。那么，有无可能在已知n和e的情况下，推导出d？
（1）ed≡1 (mod φ(n))。只有知道e和φ(n)，才能算出d。
（2）φ(n)=(p-1)(q-1)。只有知道p和q，才能算出φ(n)。
（3）n=pq。只有将n因数分解，才能算出p和q。
结论：如果n可以被因数分解，d就可以算出，也就意味着私钥被破解。
可是，大整数的因数分解，是一件非常困难的事情。目前，除了暴力破解，还没有发现别的有效方法。维基网络这样写道："对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA算法愈可靠。假如有人找到一种快速因数分解的算法，那么RSA的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA密钥才可能被暴力破解。到2008年为止，世界上还没有任何可靠的攻击RSA算法的方式。只要密钥长度足够长，用RSA加密的信息实际上是不能被解破的。"
然而，虽然RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价。即RSA的重大缺陷是无法从理论上把握它的保密性能如何。此外，RSA的缺点还有：
A)产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。
B)分组长度太大，为保证安全性，n 至少也要 600bits以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。因此， 使用RSA只能加密少量数据，大量的数据加密还要靠对称密码算法 。
加密和解密是自古就有技术了。经常看到侦探电影的桥段，勇敢又机智的主角，拿着一长串毫无意义的数字苦恼，忽然灵光一闪，翻出一本厚书，将第一个数字对应页码数，第二个数字对应行数，第三个数字对应那一行的某个词。数字变成了一串非常有意义的话：
Eat the beancurd with the peanut. Taste like the ham.
这种加密方法是将原来的某种信息按照某个规律打乱。某种打乱的方式就叫做密钥(cipher code)。发出信息的人根据密钥来给信息加密，而接收信息的人利用相同的密钥，来给信息解密。 就好像一个带锁的盒子。发送信息的人将信息放到盒子里，用钥匙锁上。而接受信息的人则用相同的钥匙打开。加密和解密用的是同一个密钥，这种加密称为对称加密（symmetric encryption）。
如果一对一的话，那么两人需要交换一个密钥。一对多的话，比如总部和多个特工的通信，依然可以使用同一套密钥。 但这种情况下，对手偷到一个密钥的话，就知道所有交流的信息了。 二战中盟军的情报战成果，很多都来自于破获这种对称加密的密钥。
为了更安全，总部需要给每个特工都设计一个不同的密钥。如果是FBI这样庞大的机构，恐怕很难维护这么多的密钥。在现代社会，每个人的信用卡信息都需要加密。一一设计密钥的话，银行怕是要跪了。
对称加密的薄弱之处在于给了太多人的钥匙。如果只给特工锁，而总部保有钥匙，那就容易了。特工将信息用锁锁到盒子里，谁也打不开，除非到总部用唯一的一把钥匙打开。只是这样的话，特工每次出门都要带上许多锁，太容易被识破身份了。总部老大想了想，干脆就把造锁的技术公开了。特工，或者任何其它人，可以就地取材，按照图纸造锁，但无法根据图纸造出钥匙。钥匙只有总部的那一把。
上面的关键是锁和钥匙工艺不同。知道了锁，并不能知道钥匙。这样，银行可以将“造锁”的方法公布给所有用户。 每个用户可以用锁来加密自己的信用卡信息。即使被别人窃听到，也不用担心：只有银行才有钥匙呢！这样一种加密算法叫做非对称加密(asymmetric encryption)。非对称加密的经典算法是RSA算法。它来自于数论与计算机计数的奇妙结合。
1976年，两位美国计算机学家Whitfield Diffie 和 Martin Hellman，提出了一种崭新构思，可以在不直接传递密钥的情况下，完成解密。这被称为"Diffie-Hellman密钥交换算法"。这个算法启发了其他科学家。人们认识到，加密和解密可以使用不同的规则，只要这两种规则之间存在某种对应关系即可，这样就避免了直接传递密钥。这种新的加密模式被称为"非对称加密算法"。
1977年，三位数学家Rivest、Shamir 和 Adleman 设计了一种算法，可以实现非对称加密。这种算法用他们三个人的名字命名，叫做RSA算法。从那时直到现在，RSA算法一直是最广为使用的"非对称加密算法"。毫不夸张地说，只要有计算机网络的地方，就有RSA算法。
1.能“撞”上的保险箱（非对称/公钥加密体制，Asymmetric / Public Key Encryption）
数据加密解密和门锁很像。最开始的时候，人们只想到了那种只能用钥匙“锁”数据的锁。如果在自己的电脑上自己加密数据，当然可以用最开始这种门锁的形式啦，方便快捷，简单易用有木有。
但是我们现在是通信时代啊，双方都想做安全的通信怎么办呢？如果也用这种方法，通信就好像互相发送密码保险箱一样…而且双方必须都有钥匙才能进行加密和解密。也就是说，两个人都拿着保险箱的钥匙，你把数据放进去，用钥匙锁上发给我。我用同样的钥匙把保险箱打开，再把我的数据锁进保险箱，发送给你。
这样看起来好像没什么问题。但是，这里面 最大的问题是：我们两个怎么弄到同一个保险箱的同一个钥匙呢？ 好像仅有的办法就是我们两个一起去买个保险箱，然后一人拿一把钥匙，以后就用这个保险箱了。可是，现代通信社会，绝大多数情况下别说一起去买保险箱了，连见个面都难，这怎么办啊？
于是，人们想到了“撞门”的方法。我这有个可以“撞上”的保险箱，你那里自己也买一个这样的保险箱。通信最开始，我把保险箱打开，就这么开着把保险箱发给你。你把数据放进去以后，把保险箱“撞”上发给我。撞上以后，除了我以外，谁都打不开保险箱了。这就是RSA了，公开的保险箱就是公钥，但是我有私钥，我才能打开。
2.数字签名
这种锁看起来好像很不错，但是锁在运输的过程中有这么一个严重的问题：你怎么确定你收到的开着的保险箱就是我发来的呢？对于一个聪明人，他完全可以这么干：
(a)装作运输工人。我现在把我开着的保险箱运给对方。运输工人自己也弄这么一个保险箱，运输的时候把保险箱换成他做的。
(b)对方收到保险箱后，没法知道这个保险箱是我最初发过去的，还是运输工人替换的。对方把数据放进去，把保险箱撞上。
(c)运输工人往回运的时候，用自己的钥匙打开自己的保险箱，把数据拿走。然后复印也好，伪造也好，弄出一份数据，把这份数据放进我的保险箱，撞上，然后发给我。
从我的角度，从对方的角度，都会觉得这数据传输过程没问题。但是，运输工人成功拿到了数据，整个过程还是不安全的，大概的过程是这样：
这怎么办啊？这个问题的本质原因是，人们没办法获知，保险箱到底是“我”做的，还是运输工人做的。那干脆，我们都别做保险箱了，让权威机构做保险箱，然后在每个保险箱上用特殊的工具刻上一个编号。对方收到保险箱的时候，在权威机构的“公告栏”上查一下编号，要是和保险箱上的编号一样，我就知道这个保险箱是“我”的，就安心把数据放进去。大概过程是这样的：
如何做出刻上编号，而且编号没法修改的保险箱呢？这涉及到了公钥体制中的另一个问题：数字签名。
要知道，刻字这种事情吧，谁都能干，所以想做出只能自己刻字，还没法让别人修改的保险箱确实有点难度。那么怎么办呢？这其实困扰了人们很长的时间。直到有一天，人们发现：我们不一定非要在保险箱上刻规规矩矩的字，我们干脆在保险箱上刻手写名字好了。而且，刻字有点麻烦，干脆我们在上面弄张纸，让人直接在上面写，简单不费事。具体做法是，我们在保险箱上嵌进去一张纸，然后每个出产的保险箱都让权威机构的CEO签上自己的名字。然后，CEO把自己的签名公开在权威机构的“公告栏”上面。比如这个CEO就叫“学酥”，那么整个流程差不多是这个样子：
这个方法的本质原理是，每个人都能够通过笔迹看出保险箱上的字是不是学酥CEO签的。但是呢，这个字体是学酥CEO唯一的字体。别人很难模仿。如果模仿我们就能自己分辨出来了。要是实在分辨不出来呢，我们就请一个笔迹专家来分辨。这不是很好嘛。这个在密码学上就是数字签名。
上面这个签字的方法虽然好，但是还有一个比较蛋疼的问题。因为签字的样子是公开的，一个聪明人可以把公开的签字影印一份，自己造个保险箱，然后把这个影印的字也嵌进去。这样一来，这个聪明人也可以造一个相同签字的保险箱了。解决这个问题一个非常简单的方法就是在看保险箱上的签名时，不光看字体本身，还要看字体是不是和公开的字体完全一样。要是完全一样，就可以考虑这个签名可能是影印出来的。甚至，还要考察字体是不是和其他保险柜上的字体一模一样。因为聪明人为了欺骗大家，可能不影印公开的签名，而影印其他保险箱上的签名。这种解决方法虽然简单，但是验证签名的时候麻烦了一些。麻烦的地方在于我不仅需要对比保险箱上的签名是否与公开的笔迹一样，还需要对比得到的签名是否与公开的笔迹完全一样，乃至是否和所有发布的保险箱上的签名完全一样。有没有什么更好的方法呢？
当然有，人们想到了一个比较好的方法。那就是，学酥CEO签字的时候吧，不光把名字签上，还得带上签字得日期，或者带上这个保险箱的编号。这样一来，每一个保险箱上的签字就唯一了，这个签字是学酥CEO的签名+学酥CEO写上的时间或者编号。这样一来，就算有人伪造，也只能伪造用过的保险箱。这个问题就彻底解决了。这个过程大概是这么个样子：
3 造价问题（密钥封装机制，Key Encapsulation Mechanism）
解决了上面的各种问题，我们要考虑考虑成本了… 这种能“撞”门的保险箱虽然好，但是这种锁造价一般来说要比普通的锁要高，而且锁生产时间也会变长。在密码学中，对于同样“结实”的锁，能“撞”门的锁的造价一般来说是普通锁的上千倍。同时，能“撞”门的锁一般来说只能安装在小的保险柜里面。毕竟，这么复杂的锁，装起来很费事啊！而普通锁安装在多大的保险柜上面都可以呢。如果两个人想传输大量数据的话，用一个大的保险柜比用一堆小的保险柜慢慢传要好的多呀。怎么解决这个问题呢？人们又想出了一个非常棒的方法：我们把两种锁结合起来。能“撞”上的保险柜里面放一个普通锁的钥匙。然后造一个用普通的保险柜来锁大量的数据。这样一来，我们相当于用能“撞”上的保险柜发一个钥匙过去。对方收到两个保险柜后，先用自己的钥匙把小保险柜打开，取出钥匙。然后在用这个钥匙开大的保险柜。这样做更棒的一个地方在于，既然对方得到了一个钥匙，后续再通信的时候，我们就不再需要能“撞”上的保险柜了啊，在以后一定时间内就用普通保险柜就好了，方便快捷嘛。
以下参考 数字签名、数字证书、SSL、https是什么关系？
4.数字签名（Digital Signature）
数据在浏览器和服务器之间传输时，有可能在传输过程中被冒充的盗贼把内容替换了，那么如何保证数据是真实服务器发送的而不被调包呢，同时如何保证传输的数据没有被人篡改呢，要解决这两个问题就必须用到数字签名，数字签名就如同日常生活的中的签名一样，一旦在合同书上落下了你的大名，从法律意义上就确定是你本人签的字儿，这是任何人都没法仿造的，因为这是你专有的手迹，任何人是造不出来的。那么在计算机中的数字签名怎么回事呢？数字签名就是用于验证传输的内容是不是真实服务器发送的数据，发送的数据有没有被篡改过，它就干这两件事，是非对称加密的一种应用场景。不过他是反过来用私钥来加密，通过与之配对的公钥来解密。
第一步：服务端把报文经过Hash处理后生成摘要信息Digest，摘要信息使用私钥private-key加密之后就生成签名，服务器把签名连同报文一起发送给客户端。
第二步：客户端接收到数据后，把签名提取出来用public-key解密，如果能正常的解密出来Digest2，那么就能确认是对方发的。
第三步：客户端把报文Text提取出来做同样的Hash处理，得到的摘要信息Digest1，再与之前解密出来的Digist2对比，如果两者相等，就表示内容没有被篡改，否则内容就是被人改过了。因为只要文本内容哪怕有任何一点点改动都会Hash出一个完全不一样的摘要信息出来。
5.数字证书（Certificate Authority）
数字证书简称CA，它由权威机构给某网站颁发的一种认可凭证，这个凭证是被大家（浏览器）所认可的，为什么需要用数字证书呢，难道有了数字签名还不够安全吗？有这样一种情况，就是浏览器无法确定所有的真实服务器是不是真的是真实的，举一个简单的例子：A厂家给你们家安装锁，同时把钥匙也交给你，只要钥匙能打开锁，你就可以确定钥匙和锁是配对的，如果有人把钥匙换了或者把锁换了，你是打不开门的，你就知道肯定被窃取了，但是如果有人把锁和钥匙替换成另一套表面看起来差不多的，但质量差很多的，虽然钥匙和锁配套，但是你却不能确定这是否真的是A厂家给你的，那么这时候，你可以找质检部门来检验一下，这套锁是不是真的来自于A厂家，质检部门是权威机构，他说的话是可以被公众认可的（呵呵）。
同样的， 因为如果有人（张三）用自己的公钥把真实服务器发送给浏览器的公钥替换了，于是张三用自己的私钥执行相同的步骤对文本Hash、数字签名，最后得到的结果都没什么问题，但事实上浏览器看到的东西却不是真实服务器给的，而是被张三从里到外（公钥到私钥）换了一通。那么如何保证你现在使用的公钥就是真实服务器发给你的呢？我们就用数字证书来解决这个问题。数字证书一般由数字证书认证机构（Certificate Authority）颁发，证书里面包含了真实服务器的公钥和网站的一些其他信息，数字证书机构用自己的私钥加密后发给浏览器，浏览器使用数字证书机构的公钥解密后得到真实服务器的公钥。这个过程是建立在被大家所认可的证书机构之上得到的公钥，所以这是一种安全的方式。
常见的对称加密算法有DES、3DES、AES、RC5、RC6。非对称加密算法应用非常广泛，如SSH,
HTTPS, TLS，电子证书，电子签名，电子身份证等等。
参考 DES/3DES/AES区别
I. 网络安全 简述RSA算法的原理和特点
1978年就出现了这种算法，它是第一个既能用于数据加密也能用于数字签名的算法。
它易于理解和操作，也很流行。算法的名字以发明者的名字命名：Ron Rivest, Adi
Shamir 和Leonard Adleman。但RSA的安全性一直未能得到理论上的证明。
RSA的安全性依赖于大数分解。公钥和私钥都是两个大素数（ 大于 100
个十进制位）的函数。据猜测，从一个密钥和密文推断出明文的难度等同于分解两个
大素数的积。
密钥对的产生。选择两个大素数，p 和q 。计算：
n = p * q
然后随机选择加密密钥e，要求 e 和 ( p - 1 ) * ( q - 1 ) 互质。最后，利用
Euclid 算法计算解密密钥d, 满足
e * d = 1 ( mod ( p - 1 ) * ( q - 1 ) )
其中n和d也要互质。数e和
n是公钥，d是私钥。两个素数p和q不再需要，应该丢弃，不要让任何人知道。
加密信息 m（二进制表示）时，首先把m分成等长数据块 m1 ,m2,..., mi ，块长s
，其中 2^s <= n, s 尽可能的大。对应的密文是：
ci = mi^e ( mod n ) ( a )
解密时作如下计算：
mi = ci^d ( mod n ) ( b )
RSA 可用于数字签名，方案是用 ( a ) 式签名， ( b )
式验证。具体操作时考虑到安全性和 m信息量较大等因素，一般是先作 HASH 运算。
RSA 的安全性。
RSA的安全性依赖于大数分解，但是否等同于大数分解一直未能得到理论上的证明，因
为没有证明破解
RSA就一定需要作大数分解。假设存在一种无须分解大数的算法，那它肯定可以修改成
为大数分解算法。目前， RSA
的一些变种算法已被证明等价于大数分解。不管怎样，分解n是最显然的攻击方法。现
在，人们已能分解140多个十进制位的大素数。因此，模数n
必须选大一些，因具体适用情况而定。
RSA的速度。
由于进行的都是大数计算，使得RSA最快的情况也比DES慢上100倍，无论是软件还是硬
件实现。速度一直是RSA的缺陷。一般来说只用于少量数据加密。
RSA的选择密文攻击。
RSA在选择密文攻击面前很脆弱。一般攻击者是将某一信息作一下伪装(
Blind)，让拥有私钥的实体签署。然后，经过计算就可得到它所想要的信息。实际上
，攻击利用的都是同一个弱点，即存在这样一个事实：乘幂保留了输入的乘法结构：
( XM )^d = X^d *M^d mod n
前面已经提到，这个固有的问题来自于公钥密码系统的最有用的特征--每个人都能使
用公钥。但从算法上无法解决这一问题，主要措施有两条：一条是采用好的公钥协议
，保证工作过程中实体不对其他实体任意产生的信息解密，不对自己一无所知的信息
签名；另一条是决不对陌生人送来的随机文档签名，签名时首先使用One-Way Hash
Function
对文档作HASH处理，或同时使用不同的签名算法。在中提到了几种不同类型的攻击方
法。
RSA的公共模数攻击。
若系统中共有一个模数，只是不同的人拥有不同的e和d，系统将是危险的。最普遍的
情况是同一信息用不同的公钥加密，这些公钥共模而且互质，那末该信息无需私钥就
可得到恢复。设P为信息明文，两个加密密钥为e1和e2，公共模数是n，则：
C1 = P^e1 mod n
C2 = P^e2 mod n
密码分析者知道n、e1、e2、C1和C2，就能得到P。
因为e1和e2互质，故用Euclidean算法能找到r和s，满足：
r * e1 + s * e2 = 1
假设r为负数，需再用Euclidean算法计算C1^(-1)，则
( C1^(-1) )^(-r) * C2^s = P mod n
另外，还有其它几种利用公共模数攻击的方法。总之，如果知道给定模数的一对e和d
，一是有利于攻击者分解模数，一是有利于攻击者计算出其它成对的e’和d’，而无
需分解模数。解决办法只有一个，那就是不要共享模数n。
RSA的小指数攻击。 有一种提高
RSA速度的建议是使公钥e取较小的值，这样会使加密变得易于实现，速度有所提高。
但这样作是不安全的，对付办法就是e和d都取较大的值。
RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。RSA是被研
究得最广泛的公钥算法，从提出到现在已近二十年，经历了各种攻击的考验，逐渐为
人们接受，普遍认为是目前最优秀的公钥方案之一。RSA
的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难
度等价。即RSA的重大缺陷是无法从理论上把握它的保密性能如何，而且密码学界多数
人士倾向于因子分解不是NPC问题。
RSA的缺点主要有：A)产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次
一密。B)分组长度太大，为保证安全性，n 至少也要 600 bits
以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大
数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。目前，SET(
Secure Electronic Transaction
)协议中要求CA采用2048比特长的密钥，其他实体使用1024比特的密钥。
DSS/DSA算法
Digital Signature Algorithm
(DSA)是Schnorr和ElGamal签名算法的变种，被美国NIST作为DSS(Digital Signature
Standard)。算法中应用了下述参数：
p：L bits长的素数。L是64的倍数，范围是512到1024；
q：p - 1的160bits的素因子；
g：g = h^((p-1)/q) mod p，h满足h < p - 1, h^((p-1)/q) mod p > 1；
x：x < q，x为私钥 ；
y：y = g^x mod p ，( p, q, g, y )为公钥；
H( x )：One-Way Hash函数。DSS中选用SHA( Secure Hash Algorithm )。
p, q,
g可由一组用户共享，但在实际应用中，使用公共模数可能会带来一定的威胁。签名及
验证协议如下：
1. P产生随机数k，k < q；
2. P计算 r = ( g^k mod p ) mod q
s = ( k^(-1) (H(m) + xr)) mod q
签名结果是( m, r, s )。
3. 验证时计算 w = s^(-1)mod q
u1 = ( H( m ) * w ) mod q
u2 = ( r * w ) mod q
v = (( g^u1 * y^u2 ) mod p ) mod q
若v = r，则认为签名有效。
DSA是基于整数有限域离散对数难题的，其安全性与RSA相比差不多。DSA的一个重要特
点是两个素数公开，这样，当使用别人的p和q时，即使不知道私钥，你也能确认它们
是否是随机产生的，还是作了手脚。RSA算法却作不到。
本文来自CSDN博客，