数论与信息安全.ppt

数论与信息安全,王晓峰,深圳大学数学与计算科学学院,目录,1. 引言,2. 历史背景与若干基本概念,3. 初等数论,4. 公钥密码,5. 量子计算与量子密码介绍*,6. 实用例子：PGP*,1. 引言,研究秘密通信,保证通信安全,目的及意义,1) 分组密码（block ciphers）-第一类对称密码,2) 流密码 （stream ciphers）-第二类对称密码,密码分类,非对称密码（asymmetric ciphers）,1) 秘密密钥密码,2) 公开密钥密码,对称密码（symmetric ciphers）,数学基础,1) 数论知识,2) 群论基础,3) 有限域,4) 信息论,5) 概率论,6) 可计算理论,2. 历史背景与密码学基本概念,传输密文的发明地-古希腊,公元前2世纪，一个叫Polybius的希腊人设计了一种将字母编码成符号对的方法，他使用了一个称为Polybius的校验表:,两次世界大战扮演重要角色,Arthur Scherbius于1919年设计出了历史上最著名的密码机德国的Enigma机, 在二次世界大战期间, Enigma曾作为德国陆、海、空三军最高级密码机. Enigma机使用了3个正规轮和1个反射轮. 这使得英军从1942年2月到12月都没能解读出德国潜艇发出的信号. 4轮Enigma机在1944年装备德国海军.,转轮密码机的使用大大提高了密码加密速度, 但由于密钥量有限, 到二战中后期时, 引出了一场关于加密与破译的对抗. 二次大战期间, 波兰人和英国人破译了Enigma密码, 美国密码分析者攻破了日本的RED, ORANGE和PURPLE密码, 这对联军在二次世界大战中获胜起到了关键性作用, 是密码分析最伟大的成功.,1970-1977：,近代密码学与计算机技术、电子通信技术紧密相关. 在这一阶段, 密码理论蓬勃发展, 密码算法设计与分析互相促进, 出现了大量的密码算法和各种攻击方法. 另外, 密码使用的范围也在不断扩张, 而且出现了许多通用的加密标准, 促进网络和技术的发展 .,七十年代早期 Feistel 在IBM做的工作和1977年美国官方宣布将DES作为数据加密标准算法. 标志着密码学的理论与技术的划时代的革命性变革, 宣布了近代密码学的开始.,1976:,1976年W.Diffie和M.Hellman发表了“密码学的新方向”(New Directions in Cryptography)一文, 提出了适应网络上保密通信的公钥密码思想, 开辟了公开密钥密码学的新领域, 掀起了公钥密码研究的序幕. 受他们的思想启迪, 各种公钥密码体制被提出, 特别是1978年RSA (Rivest, Shamir, Adleman) 公钥密码体制的出现, 成为公钥密码的杰出代表, 并成为事实标准, 在密码学史上是一个里程碑. 可以这么说: “没有公钥密码的研究就没有近代密码学”.,2000-?,混沌密码？ 量子密码？,密码学基本概念,如何达成秘密通信-密码编码学 (cryptography)；,如何破译秘密通信-密码分析学 (cryptanalysis).,密码学泛指一切有关研究密码通信的学 问，包括：,基本概念,m: 明文 (Plaintext) c: 密文 (Ciphertext),加密(算法)：把明文经某种方式处理成他人难以 理解的密文.,解密(算法)：将密文用特定的变换还原成明文.,密钥(K): 用以控制加密和解密的一定长度的符号串.,采用密钥后， 保密通信过程则为：,例如：明文为 during the last twenty years there has been an explosion of public academic research in cryptography,K=5,加密算法：,1. 将明文m按每5个字符分组：,durin gthel asttw entyy earst hereh asbee nanex plosi onofp ublic acade micre searc hincr yptog raphy,2. 每组反序得密文c：,nirudlehtgwttsayytnetsraehereheebsaxenanisolppfonocilbuedacaercimcraesrcnihgotpyyhpar,理论安全与实际安全,1949年， Shannon 提出如下的安全问题：,1. 当破译者有无限制的时间和无限制的计算能力 时一个密码系统的安全性；,2. 当破译者在有限的时间和有限的计算能力时， 一个密码系统的安全性.,计算复杂性,Turing machine & computability Turing machine: 一个有限控制器； 一条右端无限延长的输入带； 一个能左右移动的读写头.,Turing machine 的特点：,非常简单的数学模型；,本质上类似于现代计算机,定义：一数论函数称为可计算当且仅当它是 Turing machine可计算.,计算问题分类,计算问题的时间复杂性,记一可计算问题的输入数据的二进制数串的长度为n, 则计算此问题的时间(Turing machine 操作的次数)是一个n的函数f(n). 如果 f(n)=a0+a1n+aknk 则记f(n)=O(nk)，并称此问题是k次多项式时间内可计算的现实可计算的.,P与NP问题,P问题：多项式时间内可计算；,NP问题：在不确定性Turing machine上多项式时间内可计算, 不确定性Turing machine能进行猜测, 即不确定性Turing machine如能猜出一个解的话, 则确定性Turing machine在多项式时间内可校验解的正确性.,显然：NPP,3. 数论基础,3.1 带余除法: 设a, b是整数，b0. 则a可唯一地表为 a=bq+r 其中q, r为整数并且0r|b|.,3.2 数的因数分解,整除、素数、合数、因数、公因数 、倍数、 公倍数,互素,最大公因数 (greatest common divisor) gcd.,最小公倍数 (least common mutiple) lcm.,引理 如果 r 是一正整数，那么gcd(r, 0)=r.,定理3.1 若a=bq+r，则 gcda, b=gcdb, r,Euclidean Algorithm,1. 设整数 a 和 b 满足： |a|b|0.,2. 如果 b=0, 那么 gcd(a, b)=a. 如果b0, 由带余除法存在 q 和 r 使得 a=bq+r |b|r0,定理 3.2 每一对不为零的整数a, b有一个正的 gcd, 记为(a, b).,定理 3.3 若d=(a, b)，则存在整数p, q使得 pa+qb=d,例1 求(726, 393), 并求整数p和q使得 (726, 393)=726p+393q,定理3.3的推论 整数a, b互素当且仅当存在整数p, q使得 pa+qb=1,推论 若素数p整除a1a2an，则存在k, 1kn, 使得p|ak.,定理 3.4 若a|bc, (a, b)=1，那么a|c.,定理 3.5 每一个正合数可表为若干个素数的积，并且若不考虑素数在积中的顺序则此表示是唯一的.,从而， 如果一合数c有素因子p1, p2, , pn，那么,3.3 同余类,设m1为整数，a, b为任意整数. 如果 m|(ab) 则称a和b模m同余，记为（称为同余式） ab mod m,定理 3.7 若(a, m)=1, 则a1 mod m 存在.,例3.2 求 51 mod 13 , 和 111 mod 13.,设m1为整数, a为任意整数. 如果存在整数b 使得 ab 1 mod m 则称b为a 模m的逆元，记为 b a1 mod m,习题 求 51 mod 17.,定理 3.8 模m的同余关系是等价关系.,定理 3.9 若ab mod m，cd mod m，则 (1) a cbd mod m; (2) acbd mod m,定理 3.10 若acbc mod m, 且c与m互素，则 ab mod m,定理 3.11 若acbc mod m, 且d=(c, m), 则 ab mod m/d,例3.4 已知 427 mod 5, 且1=(7, 5), 则,61 mod 5,例3.5 633 mod 12, but 211 mod 12 ?,3.4 线性同余式,来自孙子算经的问题： “今有物不知其数, 三三数之剩二, 五五数之剩三, 七七数之剩二, 问物几何?”,一般地，称 axb mod m 为线性同余式.,定理 3.12 如果x1是线性同余式axb mod m的解，则对模m与x1同余的每一整数也是axb mod m的解.,例 易知x=5是 5x7 mod 6 的一个解，求更多的解.,定理 3.13 设(a, m) =d. 同余式 axb mod m (A-2) 有解的充分必要条件是 d | b,3.5 联立的线性同余式和中国剩余定理,定理 3.14 联立的线性同余式,定理 3.15 联立的线性同余式,中国剩余定理,例 3.6 求解联立的线性同余式,习题,1. 求(937, 576), 并求整数p和q使得 (937, 576)=937p+576q,2. 将23456表为16进制数.,3. 求 51 mod 17.,4. 求解联立的线性同余式:,3.6 欧拉定理和费尔玛定理,模m的完全剩余集 :,(1) 欧拉函数 设m0为一正整数, 记 (m)为小于m且与m互素的正整数的个数, 并称其为m的欧拉函数.,定理3.17 若m1，m2互素，则 (m1m2)= (m1) (m2),定理3.18,(2) 欧拉定理,定理3.19 (Euler) 若a与m互素，则 a(m) 1 mod m,推论 (Fermat) 若p是素数，(a, p)=1, 则 ap1 1 mod p,定理3.20 (Fermat) 若p是素数，则 apa mod p,故当p是素数，则 a1ap2 mod p,例子：,例3.9 求21 mod 11.,(3) 应用,例3.11 解方程： 7x22 mod 31,习题 1. 解方程： 7x5 mod 23 2. 求 31 mod 13.,3. 7 威尔森定理,定理 3.21(Wilson) 若p是素数，则 (p1)! 1 mod p 反之，如果整数p满足上式， 则p是素数.,3.1.8 平方剩余,例子 设有下列同余式: x21, x22, x23, x24 mod 5 求解?,引理 若p是奇素数, p与a互素, 则 x2a mod p 或无解, 或有两个模p不同余的解. 并且, 如果1xp是一解, 则 另一解为px.,定理 3.22 若p是奇素数, 则1, 2, . . ., p1正好有 (p1)/2个是模p的平方剩余. 即为：1, 2, . . ., p1中模p与12, 22, , 1/2(p1)2同余的数.,例如：取p=11，求模11的平方剩余(1ap).,4. 公钥密码,4.1 引言,公开密钥密码学是密码学历史上最大的而且也 是唯一真正的革命. 传统密码编码技术(包括分组密码)建立在替代 和置换基础之上. 它们的加密和解密是对称的.,1976年，Diffie 和 Hellman 在这方面取得了惊人的突破：他们开创的公钥密码技术同时解决了这两个问题.,但常规的密码存在两个重大问题: l 密钥管理和分配问题 l 数字签名问题,原理：,加密密钥和解密密钥不同，而且加密密钥公开，解密密钥保密.,例如：,l 甲和乙同时选用同一个公钥密码系统；,l 乙将公开密钥传送给甲；,甲用此公钥加密他的信息并传送给乙；,乙用他自己的私人密钥解密甲传来的加密文件.,需要澄清的问题：,l 不要误认为公钥密码加密在防止密码攻击方面 更安全可靠（任何加密方案的安全性都依赖于密 钥的长度和加密算法的计算复杂度）；,l 不要误认为公钥密码加密使得常规加密技 术过时（公钥密码加密开销更大，所以公认 为仅用于密钥管理和数字签名）；,l 不要误认为公钥密码技术使得密钥管理非 常简单，事实上，仍需要一个代理中心，而 且整个过程既不简单，也不是更有效.,采用的技术的核心：,基于单向陷门函数: 加密容易, 但解密却相当难. 其中, 陷门就是解密密钥.,例如利用求 mod p (素数) 的离散对数的困难度:,l 甲和乙在1，2，3，p1各中选取一 数作为x甲和x乙并计算,l 乙将y乙通知甲, 而且甲将y甲通知乙;,l 双方得到通信密钥:,（Rivest, Shamir & Adleman） 基于：数论中的Euler 定理和因子分解问题是计算上困难的问题.,4.2 RSA公钥密码,4.2.1 RSA 加密算法,操作过程：,1. 取两个充分大的素数p, q;,2. 计算n=pq (公开), 和(n)=(p1)(q1) (保密)；,3. 随机选取整数e (公开)，满足 gcd(e, (n)=1；,4. 计算d (保密), 满足de 1 mod (n),4.2.2 RSA 加密算法,对明文的加密过程： 1. 将明文(二进制数串)按长度不大于log2n分组； 2. 对每一组(设为mn)加密： 加密算法: c=E(m) me mod n,对明文的解密过程： 解密算法: m=D(c) cd mod n,例 4.3 取p=43, q=59，并取e=13. 则 n=pq=2537，(n)=4258=2436.,解方程： de 1 mod 2436 得 d=937.,取m=73, 则 7e =713 =78747 2172=c mod 2436,4.2.3 RSA 的安全性,关键：在于数n的因子分解,目前最快的因子分解算法的计算复杂度为：,即，如果数n=pq的因子分解被破， 则可得 (n)=(p1)(q1), 从而由加密密钥e可由下式解 得解密密钥： de1 mod (n),从而，RSA建议： 1p, q为100位的十进制数(2332), 从而n=pq为200位 的十进制数； 2 p, q的差应较大(差几位)； 3 p1, q1有较大的素因子; 4gcd(p1, q1)很小.,这样的p, q 称为安全素数.,此外, 如果en, 并且 dn1/4, 则 d 很容易确定.,注：,1. 知道n与(n) 容易破解p, q:,2. 如果pq=k 较小, 容易破解p, q:,(n)=(p1)(q1)=pq(p+q)+1=n (p+q) (pq)2= (p+q)2 4pq,(p+q)2 (pq)2=4pq=4n (p+q)2=4n+k2 p+q=(4n+k2)1/2, pq=k,其它的公钥密码：,1） Rabin公钥密码,2） Elgamal公钥密码,3） McEliece公钥密码,4） 椭圆曲线(ECC)公钥密码,5. 各种协议,5.1 数字签名协议,在文件上手写签名长期以来被用作作者身份 的证明，或至少同意文件的内容. 签名为什么 会如引人注目呢？,5.1.1 签名的重要性,RSA 数字签名:,回忆 RSA 加密,取两个充分大的素数p, q; 2. 计算n=pq (公开), 和(n)=(p1)(q1) (保密)； 3. 随机选取整数e (公开)，满足 gcd(e, (n)=1； 4. 计算d (保密), 满足de 1 mod (n) 5. 加密 c=E(m)me mod n 6. 解密 m=D(c)cd mod n,RSA 签名过程:,1. A计算: SmdA mod nA;,2. A将 (S, m) 同时寄给B;,3. B计算: mSe mod nA;,4. B将m与m 进行比较，如一致则确认，否则则拒绝,由于 S 是A用私人密钥对m 加密的结果，A无 法抵赖而B也无法伪造,DSA(Digital Signature Algorithm) 数字签名:,1981年，由National Institute of Standard and Technology (NIST)公布，为Elgamal系统的变形, 又采用了Schnorr系统中的g为非本原元的做法，以降低签名文的长度.,DSA(Digital Signature Algorithm) 数字签名:,B的秘密密钥为x, 0xq, 公开密钥为 y gx mod p,(1) 选取大素数(512位) p及q (160位)满足q|(p1). (2) g满足ghp1/q mod p, 其中h1, p1的任意 整数. (3) H为单向散列函数.,DSA数字签名(继续):,签名： (1) B任选一整数k (0kq), 并计算 r (gk mod p) mod q 及 s k1(H(m)+xr) mod q 其中，k k1 1 mod q 则(r, s)为B对m (0mp)的签名.,验证： (1) A首先验证r和s是否属于0, q, 如不是, 则(r, s)不是签名文; (2) A计算 ts1 mod q, 及 r(gH(m)tyrt mod p) mod q (3) A检查r =r是否正确, 如正确, 则(r, s)为m的 合法签名:,6. 量子计算与量子密码学,爱因斯坦說上帝不丟骰子, 意味着他相信世界的下一步是确定的；然而经由验证贝尔不等式, 代表世界的下一步是随机的的量子(quantum)学派得到现今大多数物理学家的认同.,6.1 量子特性,20世纪初发生了两大物理学革命：相对论和量子力学. 这两大革命把物理学的研究领域从经典物理学的宏观世界分别扩展到了宇观世界和微观世界.,R. Feynman在八十年代提出利用量子现象來增加计算的速度之后, 产生了量子计算机的概念. 量子计算机的最大特点是N个儲存位元可以同時儲存2N个资料, 可以在多项式時间內解決一些目前计算机需要指数计算量才能解決的問題, 例如素数分解, 计算离散对数等；另外, 量子计算机也可以加快完全搜寻(exhaustive search)的速度.,据估计, 只要有几千量子位元(qbits)的量子计算机, 它的計算能力就要比現今地球上所有计算机的计算能力总和強上不知多少倍. 目前具有几个量子位元的量子计算机已经实验成功, 20至30量子位元的量子计算机也在设计与实验中(基于Shor算法).,光的偏振现象实验：,准备一个强光源，三个分别为水平、45、垂直的偏光板滤波器A, B, C.,1. 将光照射向荧屏, 然后在光源和荧屏间插入偏光板A, 此时看到光子穿过滤波器A但出现偏振现象, 即仅留下所有水平方向的偏振光子;,3. (最奇异的一步): 现在在偏光板A和偏光板C之间放入偏光板B, 会发现有光子到达荧屏:偏光板A和偏光板C已经滤掉所有的光子, 而多余的偏光板C反而允许光子到达荧屏!,2. 再在偏光板A和荧屏间插入偏光板C, 由于C有垂直偏振功能, 它滤掉了所有来自偏光板 A的水平方向的偏振光子, 从而没有光子到达荧屏;,量子论对这些现象的解释是一个电子是可以“同時”出現在不同的位置, 量子论称同時出現在不同的位置为重叠，也就是这些量子状态纠缠在一起. 因此我們可以用一个量子来同時表示两个不同的状态，这称为一 量子位元(qbit)；以此类推，N个量子位元可以同時表示2N个不同的状态！,我们知道, 目前两个位元的存贮器，在一時刻只能表示00、01、10和11中的一种状态，但是两个量子位元的存贮器，在一時刻却可以同時表示00、01、10和11四种状态, 我們可以把一个运算同時作用在这四个数字上. 量子计算机的超級计算能力就是来自这里.,我们通过二维复向量空间中的一个单位向量来描述一个光子的偏振. 并用 | (表示垂直方向) 和| (表示水平方向)来表示这个空间的一个基. 从而任意的一个偏振(以单位向量表示)可以表示为 a | +b| 其中a, b为复数并且满足|a|2+|b|2=1.,我们也可选择不同的正交基, 例如45的旋转|和 |.,对光子偏振的解释: .,而当插入偏光板C时, 水平状态|的光子全被滤掉, 从而不会有光子到达荧屏.,光子以状态 a| +b| 被发射. 有一半(概率)的光子通过偏光板A, 并转化为水平状态| , 其余一半被转化为垂直状态|而被滤掉.,当我们再插入偏光板B(例如它测量状态 | 的光子)时, 那些水平状态 | 的光子的一半被转化为状态 | 的光子(因为|=1/sqt(2) | + 1/sqt(2) |), 另一半被转化为状态 | 的光子并被滤掉. 而通过偏光板B后状态为| 的光子又有一半最后通过偏光板C被转化为状态| 的光子并达到荧屏(仅剩1/8?).,6.2 量子密码学,量子通信利用量子力学的测不准原理和量子不可克隆定理, 通过公开信道建立密钥, 当事人之外的第三人根本不可能破解其密码. 量子通信的最终目标是解决通信的绝对安全等传统通信所存在的一系列问题, 并为即将到来的量子计算机网络时代做好通信上的准备.,6.2.1 量子密码学的产生,量子特性在信息领域中有着独特的功能，在提高运算速度、确保信息安全、增大信息容量和提高检测精度等方面可能突破现有经典信息系统的极限，于是便诞生了一门新的学科分支量子信息科学. 它是量子力学与信息科学相结合的产物，包括：量子密码、量子通信、量子计算等. 量子信息科学为信息科学的发展开创了新的原理和方法，将在21世纪发挥出巨大潜力。,6.2.2 量子状态与编码,Alice有两个正交基选择: A=|, | 和 B=|, |.当她选择A时, 那么她将 |编码为0, |编码为1. 而当她选择B时,那么她将 |编码为0, |编码为1.,每当Alice随机地选择A或B传送一个光子时, Bob 也随机地选择A或B来测量接收到的光子.,6.2.3 A practical example,1. Alice用随机的filter 以光子的极化方向 当做資料传出 (在quantum channel中),A B A B A A B A A,A A B B A B B B A,A A B B A B B B A,2. Bob随机使用 type A or B 的filter接 收,3. Bob解出的資料,4. 在另一个公共频道中Alice告诉Bob他的filter选择是否正确.,Example contd,5. Bob得知何者为正确資料 (不需要透露任何資料),6. Alice和BBob在公共频道中检查某些bit确定否有人監听.,7. 若发现資料有损坏(可能有人窃听)Alice和Bob就重傳資料, 直到确定沒有人窃听为止, 从而建立两人间的会话密钥.,6.2.4 量子密码学的弱点,目前此方法受到物理上的限制 (因为光信号在光纤中传递需要repeater,而放大的动作会破坏光子极化方向) ,目前最远到达约130 公里. (中科大李光灿教授领导的小组成功做到125公里),极化方向受到noise的影响, 若有人窃听所造成的原資料损坏会被誤以为是noise而被忽略.,6. 实用例子：PGP与电子邮件加密,由Phil Zimmermann 设计的PGP可以在电子邮件和文件存储中提供保密和认证服务. Phil作了如下的工作:,(1) 在构造块时, 选取了可获得的最好的密码算法.,(2) 将这些算法集成一通用程序, 这些应用独立于操作系统和处理器, 而只依赖于一个小规模指令集.,(3) 将其封装成包和文挡, 可在公告牌和商用网络上使用.,(4) 与公司达成协议, 使得人们可十分廉价地使用.,PGP的使用成爆炸性地增长, 其原因为:,(1) 提供免费的低版本, 并且在许多平台上可使用.,(2) 经过公众经验, 非常安全可靠. (软件包包括: RSA, DSS, Diffie-Hellman, IDEA, 3DES, SHA-1),(3) 应用范围广.,(4) 不受任何政府或标准制定机构控制.,(5) 已成为Internet 的标准文挡.,PGP提供如下五种服务:,(1) 认证.,(2) 保密.,(3) 压缩.,(4) 电子邮件的兼容性.,(5) 分段.,认证过程:,(1) Alice 创建消息M.,(2) 算法用SHA-1对消息生成160位Hash值H(M).,(3) Alice 用其私钥按RSA加密H(M): EKRa(H(M), 作为签名.,(4) Alice发送给Bob: (M, EKRa(H(M).,(5) Bob对消息M计算新H(M), 并与解密得到的 H(M)比较, 如匹配, 则消息是真实的.,(4) Bob用Alice的公钥按R