密码学基本概念及破解方法

r_517

密码学基本概念及破解方法

By 小RR （转载请注明原作者）

密码学属于数学的一个分支。密码学又可分为密码编译和密码分析两个小分支，也就是俗称的加密和解密。
            第一部分 概念部分
有几个最基本的概念需要明白一下：
1．
明文：也就是加密前的文字。
2．
密文：加密后的文字。
3．
密钥：也就是key，分为加密密钥和解密密钥。作用也就相当于开保险箱的钥匙。也可分为公钥public key和私钥private key，公钥就是大家都能使用的钥匙，私钥就是只有加密的人才知道的钥匙。而破解此类密码需要同时有这2把钥匙。
最早(也不知道是不是最最早= =)的加密形式是在一个圆木条上卷上厚厚一卷纸，然后在纸的边缘处写字。写完后把木条保存好，把纸重新卷起来。于是，要传达的信息的明文就被加密成密文了，而我们的密钥也就是那根木条。只要把木条保存完好，敌人就是截取了那张写满信息的纸，也无法阅读出什么意思。比如要找到直径完全相同的才行。由于纸的厚度很薄，所以木条的直径哪怕相差几毫米，也会导致完全无法破解。
根据密钥的不同特点，我们也能将密码学分成两个体系，为对称加密体系和非对称加密体系。对称加密体系的特点就是，在加密和解密过程中我们需要的是同一把钥匙，比如锁上保险箱和开保险箱的箱子；而非对称加密体系的的加密解密过程需要的密钥就是两把不同的钥匙，最著名的实例就是20多年来久经考验的RSA算法，由于涉及到密码学三大数学难题，暂时还没有有效方法破解，所以用处相当广泛。

第二部分 实例讲解
由于不少复杂的密码学问题都需要涉及到电脑的算法设计和高深的数学能力，所以这里介绍到的一般都是一些比较简单的几种方法。
1．
栅栏加密
假设我们想要加密的明文是“I love cubes.”
把要加密的文字去掉空格分成n组。最常见的是分成2组。I love cubes这句话一共有10个字母，如果分成2组的话，每组就是5个字母：
ilove
cubes
再按照从上至下、从左至右（当然也可以是从下至上，从右至左等不同的变种方法）的顺序写出来，就变成了icluobvees，这也就是密文了。
栅栏加密的特点就是字母不会太多。并且，有时候在对拼音字母加密中，可以考虑将sh、ch、ang、ao等一整个生母或韵母捆绑在一起，这样就加大了破解的难度。

2．
凯撒密码
凯撒密码是凯撒大帝用来避免敌人破解出密码而想出的一种加密方式。是一种很基本的字母重新排序。对于字母表中的每个字母，对其进行“+1”后，a就变成了b，b变成了c……y变成了z，z变成了a。那么数字“+1”就是这里的密钥。
还是对于I love cubes这句话，我们把这句话每个字母-3，那么这句话就变成了f ilsb zrybp。在敌人不知道钥匙是“-3”的情况下，是很难很快得做到破解的。
现在的凯撒密码产生了很多变种。比如说，对于第i位的字母，加上i!(i的阶乘)，那句子越长，破解难度也就越大。又比如说按照键盘表顺序加密吖，对应顺序就是a-Q, b-W, c-E, d-R等。

3．
各种小技巧的加密技巧
ASCII代码：在计算机中，所有字符都能用ASCII代码来代表。比如感叹号（!）是十进制中的33，大写字母A是十进制中的65，小写字母b是十进制中的98。缺点是可以看出其的范围：所有字符的范围都是十进制中的32到126。当然如果将其和凯撒密码等密码混合使用的话就能加大破解难度。
进制转换：在一个足够大（16-bit以上）的系统中，一般足够将够大的数字进行进制转换。比如十进制中的107，换成二进制就变成了1101011，八进制就是153，十六进制中就是6B。缺点是可以从数列中的最大数中看出它是几进制的，比如对于数列：
154157166145，很容易看出里面最大数是7，就可猜测它是八进制数。
倒序：在复杂加密体系中倒序是经常出现的一环。也就是将所有数字或字母倒序写出来。要加大难度的话，可以将字母转换成ASCII码，再倒序。比如把字母d变成十进制ASCII码100，再将其倒序变成001，就很难有人会想到这是b了。
哈希：经典代表MD5算法。是公认的不可逆的算法。简单说就是数学中的一一对应，但由于数据量及其庞大，进行搜索需要庞大时间和内存。主要应用于与计算机学中相关的密码学中，不详细展开。
               

[ 本帖最后由 r_517 于 2010-3-5 00:53 编辑 ]

r_517

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。
证明过程不赘述了。大家可以试着证明一下。提示：费马小定理。

[ 本帖最后由 r_517 于 2010-3-5 00:54 编辑 ]

肥熊

有點懂了..
這個坐車應該好玩多了..

r_517

Discuz会改变段落的格式和字体之类。所以看起来可能有点点小问题。不影响阅读。发一个word版的上来。请用office2007或以上版本打开。

tm__xk

先顶后看........

mengfl

顶了再看。。。。。。

ANTY

你应该弄个03版的~~~

r_517

office03在線升級一下應該就行了~現在連office2010都出來了。。docx文件是流行趨勢。。還有macro enabled的文件比如docm之類的～

Cheng_943

呵呵 顶了  我上次看到一本字典厚度的密码学

任逸

很好很强大……lz学这个专业？