4：基于线性代数与 差分方程方法模型.ppt

基于线性代数与 差分方程方法的模型 1 状态转移问题 2 密码的设计，解码与破译 3 动物数量问题 4 差分方程 5 市场经济的蛛网模 型 6 国民经济的稳定性 早期密码 RSA公开密钥体制 传统的密码通讯只能在事先约定的双方间进行，双方必须掌握相同的密钥，而密钥的传送必须使用另外 的“安全信道”。这样如果要使 n个用户都能够秘密的交换信息，则每个用户将需要用个密钥，这种巨大的密钥量给密钥的分配与管理带来了极大的困难；此外在有些情况下，事先约定密钥还是不可能的。 公开密钥体制的提出就是为了从根本上解决上述问题 。其基本思想是：把密钥划分为公开密钥和秘密密钥两部分 ,两者互为逆变换，但几乎不可能从公开密钥推出秘密密钥 .每个使用者均有自己的公开及秘密密钥。 虽然只要能解密的密文，从理论上讲 都是可破译的，但如果破译所需要 的工作量过大，要求花费的时间过 长，以致超过了必威体育官网网址期限，则该密 码系统应当被认为是安全可靠的。 定义1 设n为一正整数，将小 于n且与n互素的正整数个数记为Φ (n)，称之为欧拉（Euler L.）Φ函数。 不难证明：若 p，q为两个相异素数，n=p×q，则 φ(n) =(p-1)(q-1) 令p,q为随机选取的两个大素数（大约为十进 制100位或更大）, n=pq, n是公开的， 而p,q则是必威体育官网网址的。仅知道欧拉函数φ(n) =(p-1)(q-1)，但如果不知道因式分解就不能用这个公式计算。随机选取一个 数e，e为小于φ(n)且与它互素的正整数。利用辗转相除法，可以找到整 数d和r，使 ed+rφ(n) =1 即 ed ≡ 1 (mod φ(n)) 数n,e和d分别称为模、加密密钥和解密密钥。 数n和e组成公开密钥的加密密钥，而其余的 项p,q, φ(n)和 d 组成了秘密陷门。很显然，陷门信息包含了四个相关的项。 若知道φ(n),则由 pq=n p+q=n-φ(n)+1 可知p,q是二次方 程x2+(φ(n)-n-1)x+n=0的根，可以算 出p和q，从而将n因式分解。所 以RSA体制的安全性与因式分解密切相关，若能知 道n的因子分解，该密码就能被破 译。因此，要选用足够大 的n，使得在当今的条件下要分解它足够困难。 为加密消息 m，首先将它分为小 于n（对二进制数据，选取小于n的2的最大次方幂）的数据块，也就是说，如 果p和q都为十进制100位的素数，则 n 刚好在200位以内，因此每个消息块的长度也应在两百位以内。加密消息c由类似划分的同样长度的消息块组成。加密公式为 (mod n) 要解密消息，取每一个加密 块c(I)并计算 (mod n) 由公式ed ≡ 1 (mod φ(n)) 我们有ed = 1 - rφ(n),因此 ≡ ≡ ≡ (mod n) 其中r为某一整数。这里利用 了欧拉定理: φ(n)≡ 1(mod n)根据以上公式从密文恢复出了明文。 那么RSA公开密钥体 制是怎样使用的 呢？请 看下例！ 设使用者取 定 p=47，q=59, 则 N=pq=2773,φ(n)=(p-1)(q-1)=2668. 取素数e=17，显然它与φ(n)互素，加密者知 道p、q的值，易得出d=157。将(e,n)=(17,2773)作为公开密钥发布；严守机密的秘密密钥是(157,2773).现在有人要向此使用者传送一段（英文）明文信息，例如： I love zhejiang university 将这段文字转换为数字，不计大小写，每两个词之间为一个空格符号，空格符对应数 字00，每个英文字母对应表征其在字母表中位置的两位数字，例如：A对应01，B对应02，…，Z对应26，等等。再从头向后，将每四位数字划归一组，不足时补充空格。如此得到以下十三组数字： 0900 1215 2205 0026 0805 1009 0114 0700 2114 0922