发信人: tsingxiao()
整理人: girlrong(1999-11-13 15:02:58), 站内信件
|
最近大家经常在网络上讨论 security 的问题........
有一个地方讲起来非常头大, 就是网路窃听的问题.......
因为现今大部分的资料传递是使用明码,
所以, 有心人只要组一台 PC 上网, 就可以窃听到许许多多有用的资讯,
即使机器的 su 密码也不能幸免........
所以, 人们就想在资料上做加密解密的工作....
在网路上所传输的都是经过加密之後资料, 来防止第三者窃听.....
其实, 对资料作加密解密的工作并不困难,
只要会写程式的人就可以想出许许多多千奇百怪的方法......
但问题是, 如果这个演算法一但外流了,
那这个方法就破功了...... 所传的码顿时之间成为明码......
所以, 在一般公用的 service, 如 telnet, ftp..... 等,
作者不可能使用自定的演算法作加密解密的工作......
现今, 大家最常用的方法是 DES 演算法.....
DES 是一个公开的演算法, 但它在加密解密的过程中需要一个 key......
解码时如果 key 不对, 那还是没效......
所以, 只要 key 不要外流, 即使传输过程中有人窃听, 也不怕资料曝光......
但 DES 有个问题, 因为加密解密需用同一个 key,
所以在传输时, 要如何使双方都使用同一个 key?
这个问题实在很头大, 因为如果不靠其它方法,
比如你自己到对方耳边亲口告诉他, 或是寄一封挂号信给对方等等.
单靠网路的话, 这个 key 是无法不被第三者所知.........
所以, 像 KERBEROS 这类的安全系统 (它也是使用 DES 演算法),
就必须作一些人工设定 (也就是有些动作不能透过网路设定)
有个演算法, RSA, 可以解决上述的问题........
它的做法大概如下: 假设资料要由 A 机器传至 B 机器,
那, 由 B 机器用乱数决定一个 key, 我们称之为 private key,
这个 key 自始至终都只留在 B 机器里不送出来.......
然後, 由这个 private key 计算出另一个 key, 我们称之为 public key......
这个 public key 的特性是几乎不可能反演算出 private key 来.......
然後将这个 public key 透过网路丢给 A 机器.........
A 机器将资料用这个 public key 编码,
这个编码过的资料一定得使用 private key 才解得开.......
然後 A 机器将编码过的资料透过网路传给 B,
B 再用 private key 将资料解码...........
这时, 如果有第三者窃听资料时, 他只得到 B 传给 A 的 public key,
以及 A 用这个 public key 编码後的资料........
没有 private key, 第三者根本无法解码.............
所以这个方法确实能防止第三者的窃听........
嗯...... 接下来就是说明 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 是整数
因为在 modulo 中是 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, 所以这个过程确实能做到编码解码的功能.....
--
我
既不能达而兼善天下
只好穷而独善自身
青山处处 斯民如土矣……
※ 来源:．月光软件站 http://www.moon-soft.com．[FROM: 202.96.253.41]
|
|