信安数学7

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。

第5章习题答案一、判断题1. 设p是素数,g是模p的原根,若g x≡1(mod p),则x是p的整数倍. （×）2. 设m是正整数, (a,m)=1,若x d≡1(mod m),则d|φ(m). （×）3. 只有m是素数时,模m的原根才存在. （×）4. 根据费马小定理, 26≡1(mod7),故ord7(2)=6. （×）5. 若y≡g x(mod p), 则x≡ind g y(mod y).（×）二、综合题1. 已知6是模41的原根, 9=630,求ord41(9).解：6是模41的原根因此可知φ(41)=40, 640≡1 (mod 41)9≡630(mod 41)1≡(640)3≡(630)4(mod 41),因此ord41(9)=42. 写出模5的全部原根.解：5是素数，肯定有原根，原根个数φ(φ(5))=φ(4)=2. 5是比较小素数，因此可以用穷举方法进行求解原根5的简化剩余系为{1,2,3,4,}，且计算可得11≡1;21≡2, 22≡4, 23≡3, 24≡1;31≡3, 32≡4, 33≡2, 34≡1;41≡4, 42≡1;因此根据原根定义，可知2和3是模5的原根。

3. 已知模22的原根存在,求出模22的所有原根.解：22=2*11，满足2pα形式，原根肯定存在。

原根个数为φ(φ(22))=φ(10)=4=22的素因数只有q=2,φ(m)=φ(22)=5根据定理5.8.1，故只需计算g5模p=22是否同余1.先判断g=2是否为模22的原根，因25(mod22)≢1. 所以2模22的原根. 因此模22的所有原根2d,其中d为模10的简化剩余系{1,3,7,9}。

模22的所有原根为：21≡2, 23≡8, 27≡18, 29≡6 (mod 22).即模22的所有4个原根为:2,8,18,64. 已知5对模17的阶为16, 列出所有模17阶为8的整数a(0<a <17).解：φ(17)=16, 516≡1(mod 17)。

信安数学符号介绍
信息安全（简称为信安）是计算机科学的一个重要分支，它涉及到信息的保密性、完整性和可用性。

在信安领域，数学扮演着至关重要的角色，其中涉及大量的专业数学符号。

了解这些符号及其意义，对于深入理解信安原理和应用至关重要。

1. 加密算法：用于确保信息在传输过程中不被非法获取。

常见的加密算法有对称加密（如AES）和非对称加密（如RSA）。

在算法表示中，我们常常会看到字母“E”或“加密”，表示加密操作，而字母“D”或“解密”表示解密操作。

2. 哈希函数：用于将任意长度的数据映射为固定长度的字符串，常用于数据完整性验证。

哈希函数通常用“H”表示，后接一串字符表示具体的哈希算法，如SHA-256。

3. 公钥和私钥：在非对称加密中，公钥用于加密，私钥用于解密。

私钥必须保密，而公钥可以公开分享。

在表示时，公钥和私钥通常会用大写字母“K”和“k”来表示。

4. 签名：通过哈希函数和私钥对数据进行签名，用于验证信息的完整性和发送者的身份。

签名操作常用符号“Sign”或“sig”表示。

5. 随机数：在信息安全中，随机数是至关重要的，因为它能提供密钥等安全参数。

常用的随机数生成器用字母“R”表示，后接随机数生成器的名称或描述。

6. 运算符：包括算术运算符（+、-、、/）和逻辑运算符（&&、||、！），它们在信息安全中用于各种算法和操作的实现。

这些数学符号是信息安全领域的基本语言，通过掌握这些符号，我们可以更深入地理解信安原理和构建有效的安全策略。

,考试作弊将带来严重后果！华南理工大学期末考试《信息安全数学基础》试卷B1. 考前请将密封线内填写清楚；所有答案请直接答在试卷上；．考试形式：闭卷；选择题：（每题2分，共20分）1．设a, b都是非零整数。

若a|b，b|a，则( )。

(1) a＝b，(2) a＝±b，(3) a＝－b，(4) a > b2．大于10且小于50的素数有( ) 个。

(1) 9，(2) 10，(3) 11，(4) 153．模7的最小非负完全剩余系是( )。

(1) －3, －2, －1, 0, 1, 2, 3，(2) －6, －5, －4, －3, －2, －1, 0，(3) 1, 2, 3, 4, 5, 6, 7，(4) 0, 1, 2, 3, 4, 5, 64．模30的简化剩余系是( )。

(1) －1, 0, 5, 7, 9, 19, 20, 29，(2) －1, －7, 10, 13, 17, 25, 23, 29，(3) 1, 7, 11, 13, 17, 19, 23, 29，(4) －1, 7, 11, 13, 17, 19, 23, 29 5．设n是整数，则(2n, 2(n＋1))＝( )。

(1) 1，(2) 2，(3) n，(4) 2n6．设a, b是正整数，若[a, b]＝(a, b)，则( )。

(1) a＝b，(2) [a, b]＝ab，(3) (a, b)＝1，(4) a > b7．模17的平方剩余是( )。

(1) 3，(2) 10，(3) 12，(4) 158．整数5模17的指数ord17(5)＝( )。

(1) 3，(2) 8，(3) 16，(4) 329．欧拉(Euler)定理：设m 是大于1的整数，如果a 是满足(a , m )＝1的整数，则 ( )。

(1) a m ＝a (mod m )， (2) a ϕ (m )＝1 (mod a )， (3) a ϕ (m )＝a (mod m )， (4) a ϕ (m )＝1 (mod m )10．Fermat 定理：设p 是一个素数，则对任意整数a ，有 ( )。

信安实验中学2018-2019学年七年级下学期数学期中考试模拟试卷含解析班级__________ 座号_____ 姓名__________ 分数__________一、选择题1、（2分）如左下图，直线a∥b，直线c分别与a，b相交，∠1=50°，则∠2的度数为（）A. 150°B. 130°C. 100°D. 50°【答案】B【考点】对顶角、邻补角，平行线的性质【解析】【解答】解：∵a∥b，∴∠2+∠3=180°∵∠1=∠3=50°∴∠2=180°-∠3=180°-50°=130°故答案为：B【分析】根据平行线的性质，可证得∠2+∠3=180°，再根据对顶角相等，求出∠3的度数，从而可求出∠2的度数。

2、（2分）若a＞b，则下列不等式一定成立的是（）A. a+b＞bB. ＞1C. ac2＞bc2D. b-a＜0【答案】D【考点】不等式及其性质，有理数的加法，有理数的减法，有理数的除法【解析】【解答】解：A、当b＜a＜0，则a+b＜b，故此选项不符合题意；B、当a＞0，b＜0，＜，1故此选项不符合题意；C、当c=0，ac2＞bc2，故此选项不符合题意；D、当a＞b，b-a＜0，故此选项符合题意；故本题选D【分析】根据有理数的加法，减法，除法法则，及不等式的性质，用举例子即可一一作出判断。

3、（2分）关于x的不等式（a+2 014）x-a>2 014的解集为x<1,那么a的取值范围是（）A. a>-2 014B. a<-2 014C. a>2 014D. a<2 014【答案】B【考点】不等式的解及解集，解一元一次不等式【解析】【解答】解：（a+2 014）x>a+2 014∵此不等式的解集为：x<1,∴a+2 014＜0解之：a<-2 014故答案为：B【分析】先将不等式转化为（a+2 014）x>a+2 014，再根据它的解集为x<1，得出a+2 014＜0，解不等式即可求解。

信息安全数学基础教案（禹勇）教师教案（2009 —2010 学年第一学期）课程名称: 信息安全数学基础授课学时: 40学时授课班级: 信息安全专业，〜60班任课教师: 禹勇教师职称: 讲师教师所在学院：计算机科学与工程学院电子科技大学信息安全数学基础教案（禹勇）第一章整除与同余授课时数：6一、教学内容及要求1. 整除的概念及欧几里得除法，理解2. 整数的表示，理解3. 最大公因数及广义欧几里得除法，掌握4. 整除的进一步性质及最小公倍式，掌握5. 素数和算术基本定理，掌握6. 同余的概念，掌握二、教学重点与难点本章的内容较多，难点较少，教学重点在于以下方面:信息安全数学基础教案(禹勇)1. 欧几里得除法和广义欧几里得除法。

2. 最大公因数和最小公倍数。

3. 整数的标准分解式。

4. 同余的概念三、内容的深化和拓宽在内容的深化和拓宽方面，介绍如何运用欧几里得除法求整数的二进制、十进制和十六进制，使学生对欧几里得除法有更深的理解。

四、教学方式(手段)及教学过程中应注意的问题1. 在讲述本章内容时，主要采用口头讲解，PPT 演示的方式。

2. 讲述证明整除方面的定理的常用方法。

3. 通过举例阐述重要定理的内容和含义。

五、作业1. 证明：若2|n, 5|n, 7|n那么70|n。

2. 证明：如果a是整数，则a3-a被3整除。

3. 证明：每个奇整数的平方具有形式8k+1。

4. 证明：任意三个连续整数的乘积都被6 整除。

5. 证明：对于任给的正整数k,必有k个连续正整数都是合数。

6. 证明：191，547都是素数，737，747都是合数。

7. 利用爱拉托斯筛法求出500 以内的全部素数。

8. 求如下整数对的最大公因数：(1) (55, 85) (2) (202, 282)9. 求如下整数对的最大公因数：信息安全数学基础教案(禹勇)(1) (2t+1, 2t-1) (2) (2n, 2(n+1))10.运用广义欧几里得除法求整数s, t，使得sa+tb=(a,b)(1) 1613, 3589 (2)2947, 377211. 证明:若(a,4)=2, (b,4)=2，则(a+b,4)=41 2 .求出下列各对数的最小公倍数。

信安初级中学2018-2019学年七年级下学期数学期中考试模拟试卷含解析班级__________ 座号_____ 姓名__________ 分数__________一、选择题1、（2分）下列各数是无理数的为（）A. B. C. 4.121121112 D.【答案】B【考点】无理数的认识【解析】【解答】根据无理数的定义可知，只有是无理数，﹣9、4.121121112、都是有理数，故答案为：B.【分析】利用无理数是无限不循环的小数，可解答。

2、（2分）如图，直线AB，CD交于O，EO⊥AB于O，∠1与∠3的关系是（）A. 互余B. 对顶角C. 互补D. 相等【答案】A【考点】余角、补角及其性质，对顶角、邻补角【解析】【解答】∵EO⊥AB于O，∴∠EOB=90°，∴∠1+∠3=90°，则∠1与∠3的关系是互余．故答案为：A．【分析】根据对顶角相等得到∠2=∠3，再由EO⊥AB于O，得到∠1与∠3的关系是互余.3、（2分）在“同一平面内”的条件下,下列说法中错误的有（）①过一点有且只有一条直线与已知直线平行;②过一点有且只有一条直线与已知直线垂直;③两条不同直线的位置关系只有相交、平行两种;④不相交的两条直线叫做平行线;⑤有公共顶点且有一条公共边的两个角互为邻补角.A. 1个B. 2个C. 3个D. 4个【答案】B【考点】对顶角、邻补角，垂线，平行公理及推论，平面中直线位置关系【解析】【解答】解：①同一平面内，过直线外一点有且只有一条直线与已知直线平行，故①错误；②同一平面内，过一点有且只有一条直线与已知直线垂直，故②正确；③同一平面内，两条不同直线的位置关系只有相交、平行两种，故③正确；④同一平面内，不相交的两条直线叫做平行线，故④正确；⑤有公共顶点且有一条公共边，另一边互为反向延长线的两个角互为邻补角，⑤错误；错误的有①⑤故答案为：B【分析】根据平行线公理，可对①作出判断；过一点作已知直线的垂线，这点可能在直线上也可能在直线外，且只有一条，可对②作出判断；同一平面内，两条不同直线的位置关系只有相交、平行两种，可对③作出判断；根据平行线的定义，可对④作出判断；根据邻补角的定义，可对⑤作出判断。

信息安全数学基础信息安全是当今社会中非常重要的一个领域，随着互联网的发展和普及，信息安全问题也日益突出。

而要保障信息的安全，数学基础是至关重要的。

本文将从信息安全的数学基础入手，简要介绍一些与信息安全密切相关的数学概念和方法。

首先，我们要了解信息安全的基本概念。

信息安全是指在计算机系统中，对信息的保密性、完整性和可用性进行保护的一系列技术和措施。

而在实现这些目标的过程中，数学起着至关重要的作用。

其中，最基本的数学概念之一就是密码学。

密码学是研究如何在敌手存在的情况下，实现信息的保密性和完整性的科学。

在密码学中，数论和代数是两个非常重要的数学分支，它们为密码算法的设计和分析提供了重要的数学基础。

在密码学中，最基本的算法之一就是对称加密算法。

对称加密算法使用一个密钥来对信息进行加密和解密。

而在对称加密算法中，数学中的置换和替换运算是非常重要的。

通过置换和替换运算，可以使得加密后的信息在没有密钥的情况下难以被破解。

而在对称加密算法中，数学基础的坚实与否直接决定了算法的安全性。

除了对称加密算法外，公钥加密算法也是信息安全中非常重要的一部分。

公钥加密算法使用了数论中的大数分解和离散对数等数学问题，这些问题的复杂性使得公钥加密算法能够提供较高的安全性。

同时，公钥加密算法也是实现数字签名和数字证书的基础，这些技术在信息安全中起着至关重要的作用。

此外，信息安全中还涉及到随机数生成、哈希函数、消息认证码等数学概念和方法。

随机数的质量直接关系到密码算法的安全性，而哈希函数和消息认证码则是保证信息完整性的重要手段。

这些方法的设计和分析都需要数学的支持。

总之，信息安全的数学基础是非常重要的。

密码学、数论、代数、概率论等数学分支为信息安全提供了坚实的基础。

只有深入理解和熟练运用这些数学知识，才能更好地保障信息的安全。

希望本文的介绍能够对读者有所帮助，让大家对信息安全的数学基础有一个更清晰的认识。

信安初级中学2018-2019学年七年级下学期数学期中考试模拟试卷含解析班级__________ 座号_____ 姓名__________ 分数__________一、选择题1、（2分）下列各数是无理数的为（）A. B. C. 4.121121112 D.【答案】B【考点】无理数的认识【解析】【解答】根据无理数的定义可知，只有是无理数，﹣9、4.121121112、都是有理数，故答案为：B.【分析】利用无理数是无限不循环的小数，可解答。

2、（2分）如图，直线AB，CD交于O，EO⊥AB于O，∠1与∠3的关系是（）A. 互余B. 对顶角C. 互补D. 相等【答案】A【考点】余角、补角及其性质，对顶角、邻补角【解析】【解答】∵EO⊥AB于O，∴∠EOB=90°，∴∠1+∠3=90°，则∠1与∠3的关系是互余．故答案为：A．【分析】根据对顶角相等得到∠2=∠3，再由EO⊥AB于O，得到∠1与∠3的关系是互余.3、（2分）在“同一平面内”的条件下,下列说法中错误的有（）①过一点有且只有一条直线与已知直线平行;②过一点有且只有一条直线与已知直线垂直;③两条不同直线的位置关系只有相交、平行两种;④不相交的两条直线叫做平行线;⑤有公共顶点且有一条公共边的两个角互为邻补角.A. 1个B. 2个C. 3个D. 4个【答案】B【考点】对顶角、邻补角，垂线，平行公理及推论，平面中直线位置关系【解析】【解答】解：①同一平面内，过直线外一点有且只有一条直线与已知直线平行，故①错误；②同一平面内，过一点有且只有一条直线与已知直线垂直，故②正确；③同一平面内，两条不同直线的位置关系只有相交、平行两种，故③正确；④同一平面内，不相交的两条直线叫做平行线，故④正确；⑤有公共顶点且有一条公共边，另一边互为反向延长线的两个角互为邻补角，⑤错误；错误的有①⑤故答案为：B【分析】根据平行线公理，可对①作出判断；过一点作已知直线的垂线，这点可能在直线上也可能在直线外，且只有一条，可对②作出判断；同一平面内，两条不同直线的位置关系只有相交、平行两种，可对③作出判断；根据平行线的定义，可对④作出判断；根据邻补角的定义，可对⑤作出判断。