4． 密码学三大难题所代表的三种加密算法。
a.
大整数因子分解系统（代表算法为RSA加密系统）
b.
椭圆曲线离散对数系统（ECC）
c.
离散对数系统（DSA）
以上这三种算法由于在数学和计算机学中还没有有效的解决方案，所以唯一的解密方法就是穷举、强行破解，这也是密码破译中最忌讳的方法。
椭圆曲线离散对数和离散对数的问题解释这里就不再详细说了，否则可以占掉10页……大整数因子分解系统（RSA算法）的原理比较简单易懂，初中以上的学生应该都能看懂，主要用到的定理是费马小定理，在这里简单介绍一下。 5． RSA加密算法
先找三个数字p, q, r。其中 p, q 是两个相异的质数, r 是一个与 (p-1)(q-1) 互质的数。
p, q, r这三个数字都是私钥。是外人不知道的。
由于r和(p-1)(q-1)互质，所以一定存在一个正整数m, 使得 r*m ≡ 1 (mod (p-1)*(q-1)) 。接着，使得n=p*q。
m, n 这两个数便是公钥，大家都可以知道。
我们设上面的p = 3, q = 7, r = 5, m = 5, n = 21。
现在开始加密：先把要加密的资料翻译成数字。方法有多种，例如ASCII码、字母表顺序直接转换(a=1,b=2,c=3)、倒序转换等等。
以“I ate an apple.”为例，我们按照字母表顺序将它变成0901200501140116161205，然后进行分组，每2^t(如1或2或4或8等等)一组，但每一组所有数都必须小于n。所以这里将其2个一组，变成A集合{9,1,20,5,1,14,1,16,16,12,5}。
对于每一个A集合中的元素a，计算出b，使得b ≡ a^m (mod n)，且b∈[0,n)。
对于A集合第一个元素9，相对应可以算出的值是18。(9^5除以21的余数)
这样我们就能得到加密后的B集合{18,1,20,17,1,14,1,4,4,3,17}。
解密过程是对B集合中的每个元素b，使得计算 a ≡ b^r (mod n) ，且a∈[0,n)。
对于B集合第一个元素18，相对应可以算出的值其实就是A集合中的9。(18^5除以21的余数)。
如果有盗密者偷听，他会得到的信息是: m, n, B集合。
而他想要解码，他就必须找到r。所以,他必须先对n(=p*q)进行分解质因数。 当p和q这两个质数变得非常非常大的时候，计算机学和数学中均暂且尚未找到适当的解法能够有效快捷地找到p和q这两个质数的值，但加密过程中如果知道两个大质数p和q的值，用高精度算法很容易算出p和q的乘积n。这就是密码学三大难题之一的大整数因子分解问题。
上述解密过程中用到以下定理：
如果p和q是相异质数，并且r*m ≡ 1 (mod (p-1)*(q-1))。a是任意一个正整数，b ≡ a^m (mod p*q), c ≡ b^r (mod p*q)，则 c ≡ a mod p*q。
证明过程不赘述了。大家可以试着证明一下。提示：费马小定理。
附件: 密码学基本概念及破解方法.rar (2010-3-5 01:18:41, 15.61 KB) / 下载次数 34