信息安全数学基础课件

7.1 拟素数7.2 素性检测7.3 Euler拟素数7.4 安全性基础–信息论–复杂性理论第7章素性检测及算法安全性基础计算机科学与技术学院计算机科学与技术学院定义1设n是一个奇合数.如果整数b, (b,n)=1,使得同余式b n-1=1 (mod n) 成立,则n叫做对于基b的拟素数.2340=1 mod 341, 2560=1 mod 561, 2644=1 mod 645,计算机科学与技术学院计算机科学与技术学院计算机科学与技术学院计算机科学与技术学院7.1 拟素数7.2 素性检测7.3 Euler拟素数7.4 安全性基础–信息论–复杂性理论第7章素性检测及算法安全性基础计算机科学与技术学院生成大素数:素性检测•随机生成一个大奇数•然后检验它是否是素数•需要检验多少个随机整数?–一般每ln n个整数有一个素数•对于一个512 bit的n, ln n = 355. 平均需要检测大约177=355/2个奇数•需要解决素性检验问题•欧拉定理: 若a和n互素,则a (n)≡1 mod n •费马小定理:设p是素数, 由于对任意的a(0<a<p), 有gcd(a,p)=1,则a p-1≡1 mod p•Miller-Rabin算法(费马测试)•n 是素数→a n-1≡1 mod n•n-1=2k m且a n-1=((a m)2)2…–a m ≡1 mod n ⇒a n-1≡1 mod n–((a m)2)2 … ≡±1 mod n⇒a n-1≡1 mod nMiller-Rabin 检验•确定一个给定的数n是否是素数–n-1 = 2k m, (m 是奇数)–选择随机整数a, 1 ≤a ≤n-1–b ← a m mod n–若b=1,则返回“n 是素数”–计算b, b2,b4,…,b2^(k-1) mod n, 若发现±1,返回“n 是素数”–返回“n 是合数”Why Rabin-Miller Test Work?•声明:若输出“n 是合数”, 则n一定不是素数•Proof:if we choose a number n and returns composite –Then a m≠1, a m≠-1, a2m≠-1, a4m≠-1, …, a2^{k-1}m≠-1 (mod n)–Suppose n is prime,–Then a n-1=a2^{k}m=1 (mod n)–There are two square roots modulo n: 1 and -1⇒a2^{k-1}m = 1 (mod n)–There are two square roots modulo n: 1 and -1⇒a2^{k-2}m = 1 (mod n)–…–Then a m= 1 (contradiction!)–因此若n是素数, 算法不将输出“合数”偏“是”•Bias to YES–如果n是素数,那么Rabin-Miller 检测一定返回“素数”–但a n-1 1 mod n 不能证明n 是素数–合数以1/4的概率通过检测–我们可以检验多次来减少错误概率!•但是有一些非素数!–Carmichael 数: 561, 1105, …Carmichael 数计算机科学与技术学院7.1 拟素数7.2 素性检测7.3 Euler拟素数7.4 安全性基础–信息论–复杂性理论第7章素性检测及算法安全性基础计算机科学与技术学院计算机科学与技术学院7.3 Euler拟素数计算机科学与技术学院7.1 拟素数7.2 素性检测7.3 Euler拟素数7.4 安全性基础–信息论–复杂性理论第7章素性检测及算法安全性基础计算机科学与技术学院密码系统的数学模型•P=M L = {m=(m 1,m 2,…,m L )|m i ∈M}–M={a i , i=1,2,…,N} p(a i )≥0 ∧∑i=1N p(a i )=1•K= B R = {b=(b 1,b 2,…,b R )|b i ∈B}–B={b i , i=1,2,…,S} p(b i )≥0 ∧∑i=1S p(b i )=1•C={c|c=e k (m), k ∈K ∧m ∈M}m c Sender Encryption Decryption Receiver Secure ChannelCryptanalysis m k Key Space(K)Message Space(P)CiphertextSpace(C)明文密文概率分布•Pr[C = c] = ∑k∈K;c∈C(k)Pr[K = k]Pr[m = d k(c)]–C(k) = {e k(m)|m∈P}•Pr[C = c|P = m] = ∑k∈K;m=dk(c)Pr[K = k]•Pr[P = m|C = c]=Pr[C = c|P = m]Pr[P = m]/Pr[C = c]= (Pr(m)∑{k|m=dk(c)}Pr(k))/∑k∈K;c∈C(k)Pr(k)Pr(d k(c))Shannon安全•基本思想:密文不能提供明文的任何“信息”–怎样定义“信息”?•定义:一个密码算法是Shannon安全的,如果–对于P上的∀Pr,和∀c ∀m,有Pr[P=m]=Pr[P=m|C=c]–也称这样一个算法是绝对保密的绝对保密定理•Suppose (P, C, K, E, D) is a cryptosystem where |K| = |P| = |C|.•Then the cryptosystem provides perfect secrecy if and only if–every key is used with equal probability 1/|K|–and ∀x ∈P and ∀y ∈C, there is a unique key k suchthat e k(x) = y关于绝对保密的“坏消息”•定理:设明文空间P有n个元素,则对于绝对保密的密码有:|K| n•Proof:–Consider a nonezero probability distribution of P–Given any C=c, for every mPr[P=m|C=c] = Pr[P=m] > 0thus there must exist one key that decrypts c into m –As one key can decrypt c into one message, at least n keys are needed复杂性理论介绍•Perfect Secrecy ⇒key-length ≥msg-length –Can NOT use one key to encrypt many message–Such as use 56-bit key to encrypt a document(>56-bit)•So in modern cryptography–NOT perfect secrecy–IS secure under limited resource (complexity)–Mean that the key(or plaintext) recovery is difficult–Complexity is the foundation of modern cryptography问题(Problems)•Definition:A problem is a general question with associated parameters whose values are not specified•Example:–Name: GCD problem–Instance: Two natural numbers a,b N–Question: What is the greatest common divisor of aand b?–An instance of GCD problem: what is gcd(24,16)?图灵机•Definition:A Turing Machine is–σ: S⨯B →S–μ: S⨯B →B⋃{l,r}–When S is State, B is Characters, l is shift left, r is shift rightState Machine… 0 1 1 0 0 0 1 1 …算法(Algorithms)•Definition:An algorithm is a step-by-step procedure (based on Turing Machine) which for an instance produces the correct answer•Description:An algorithm is said to solve a problem if it produces the correct answers for all instances of a problem问题和算法(Problems and Algorithms)算法复杂性•Definition:time complexity of an algorithm is how many steps (based on TM) are necessary to produce the solution for a given instance of the size n•Time complexity function (TCF):–Logarithmic functionsf(n)=log(n)–Polynomial functionsf(n)=n a a∈N–Exponential functionsf(n)=Ω(a n) a∈N and exist b∈N f(n)=O(b n)问题复杂性•Definition:The complexity of a problem is complexity of the best algorithm for a problem OR the least complexity of all algorithms–The complexity of problem is much more difficult–It relay on the mathematical analysis •Definition:Complexity theory is mathematical discipline that classifies problems based on the difficulty to solve them问题分类•Decidable–P–can be solved in polynomial time usingDTM•Example: A*B–NP –can be solved in polynomial time using NDTM•σ: S⨯B →2S–NPC:The most difficult problem in NP •How to define the difficulty?•P problem is considered as easy problem!密码学中的问题•FACTORING:Factorize n(= p1e1p2e2…p k e k)•DLP:Find x satisfying αx≡β(mod p)•DHP:Find αab(mod p) from αa (mod p) andαb(mod p)•Subset-Sum:Given a set of positive integersA={a1,a2,…,a n} and a positive integer s, determine there is a subset of A whose sum is s•QRP:Decide a is a quadratic residue modulo n?•SQROOT:Find x satisfying x2≡a (mod n)第7章素性检测及算法安全性基础总结•素性检测–费马小定理–欧拉定理•Shannon 安全–绝对保密–概率论•计算复杂性–P, NP, NPC。