19第十九章-初等数论.pptVIP

Discrete Math. , HZP 【定义】设a,b是两个整数, 且b≠0, 如果存在整数c使a=bc, 则称a被b整数, 或b整数a, 记作b|a 。又称a是b的倍数，b是a的因子。 把b不整除a记作b | a 对于 整除 有如下性质： 【性质19.1】如果a|b且a|c, 则对任意的整数x, y, 有 a|xb+yc； 【性质19.2】如果a|b且b|c，则a|c； 【性质19.3】设m≠0, 则a|b当且仅当ma|mb； 【性质19.4】如果a|b且b|a，则a=±b。 【性质19.5】如果a|b且b≠0，则|a| ≤ |b|。 【定义19.1】如果正整数a大于1且只能被1和它自己整除，则称a是素数；如果a大于1且不是素数，则称a是合数。素数也称为质数。 素数 和 合数 有如下性质： 【性质19.6】如果d1, p是素数且d|p，则d=p。 【性质19.7】设p素数且p|ab，则必有p|a或p|b。 更一般地，设p是一个素数且p|a1a2…ak, 则必存在1≤i ≤k，使得p|ai。 【性质19.8】 a1是合数当且仅当a=bc, 其中1ba, 1ca . 【性质19.9】合数必有素数因子, 即设a是一个合数, 则存在素数p, 使得p|a 。 无条件安全（Unconditionally secure） 无论破译者有多少密文,他也无法解出对应的明文,即使他解出了,他也无法验证结果的正确性. Onetime pad 计算上安全（Computationally secure） 破译的代价超出信息本身的价值 破译的时间超出了信息的有效期. 基于字符的密码 代替密码 (substitution cipher)：就是明文中的每一个字符被替换成密文中的另一个字符。接收者对密文做反向替换就可以恢复出明文。 简单代替密码(simple substitution cipher), 即单字母密码: 明文的一个字符用相应的一个密文字符代替。 多字母密码(ployalphabetic cipher): 明文中的字符映射到密文空间的字符，还依赖于它在上下文中的位置。 置换密码(permutation cipher)，又称换位密码:明文的字母保持相同，但顺序被打乱了。 例 take action at middle night 给定加密的消息: PHHW PH DIWHU WKH WRJD SDUWB 对k=(a,b) ∈K, 解密函数形式为 D( E(i) ) = a-1( E(i) – b)(mod 26) 例 设k＝(7, 3)，注意到 7-1(mod 26)=15, 加密函数是 E(x)=7x+3, 相应的解密函数是 D(y)=15(y-3)=15y-19 , 易见 D(E(x)) = D(7x+3) = 15(7x+3)-19 = x+45-19 = x (mod 26) 与简单代替密码类似, 只是映射是一对多的, 每个明文字母可以加密成多个密文字母。 例, A可能对应于5、13、25 B可能对应于7、9、31、42 当对字母的赋值个数与字母出现频率成比例时。这是因为密文符号的相关分布会近似于平均的，可以挫败频率分析。 多表代替密码: 是以一系列(两个以上)代换表依此对明文消息的字母进行代换的方法。 定义 加密函数为: E(m1m2…mn) = c1c2…cn 其中 ci = (mi+ki) mod 26 , mi=0,1,…,25, i=1,2,…,n 现代常规加密技术 DES(Data Encryption Standard) Triple DES IDEA Blowfish RC5 CAST-128 …… RSA公钥密码是由Ron Rivest、Adi Shamir和Len Adleman 于1977年发明，1978年公布的。 图灵（Alan Mathison Turing） Alan Mathison Turing,1912～1954. 英国数学家。 一生对智能与机器之间的关系进行着不懈探索。 1936年，24岁的图灵提出 “图灵机”的设想。二战期间成功地破译了纳粹德国的密码，设计并制造了 COLOSSUS,向现代计算机迈进了重要一步。 1952年，图灵遭到警方拘捕，原因是同性恋。1954年6月8日，服毒自杀，年仅42岁。 图灵去世12年后，美国计算机协会以他的名字命名了计算机领域的最高奖“图灵奖”。 它是一种块加密算法, 是目前应用最广泛的公钥密码算法, 只在美国申请专利, 且已于20