数论与密码学教程

这是一套高级密码学课件,包括：高级密码学综述、单密钥密码体制、双密钥体制、密钥管理、身份验证、报文完整性鉴别、数字签名、数论初步。

第3部分数论初步

这是一套高级密码学课件,包括：高级密码学综述、单密钥密码体制、双密钥体制、密钥管理、身份验证、报文完整性鉴别、数字签名、数论初步。

3.1素 数定义2.1( 整除、倍数、因数) 设a、b为整数， 若存在整数c,使b=ac,则称a可整除b。 记作a|b。 b叫做a的倍数，a叫做b的因数。 若不存在这样的整数c,则称a不能整除b。 记作a b。 例如30=2×15=3×10=5×6 我 们有2,3,5分别整除30。 或30被2,3,5分别整除。 记作分别记为：2|30,3|30, 5|30。 2,3,5都是30的因数，30是2,3,5的倍数。

这是一套高级密码学课件,包括：高级密码学综述、单密钥密码体制、双密钥体制、密钥管理、身份验证、报文完整性鉴别、数字签名、数论初步。

又例如7|84,-7|84,5|20,19|171,13|0 3 8,5 12。 0是任何非零整数的倍数，1是任何整数的因数，任何非零 整数a是其自身的倍数。 由此我们可以得出这样的结论 如果a|1,则a=1

绪论

密码学的发展历史(1)

1.3 密码学的发展历史

密码学的发展历程大致经历了三个阶段：古代加密方法、古典密码和近代密码。

1.3.1 古代加密方法（手工阶段）

源于应用的无穷需求总是推动技术发明和进步的直接动力。存于石刻或史书中的记载表明，许多古代文明，包括埃及人、希伯来人、亚述人都在实践中逐步发明了密码系统。从某种意义上说，战争是科学技术进步的催化剂。人类自从有了战争，就面临着通信安全的需求，密码技术源远流长。

古代加密方法大约起源于公元前440年出现在古希腊战争中的隐写术。当时为了安全传送军事情报，奴隶主剃光奴隶的头发，将情报写在奴隶的光头上，待头发长长后将奴隶送到另一个部落，再次剃光头发，原有的信息复现出来，从而实现这两个部落之间的秘密通信。

密码学用于通信的另一个记录是斯巴达人于公元前400年应用Scytale加密工具在军官间传递秘密信息。Scytale实际上是一个锥形指挥棒，周围环绕一张羊皮纸，将要保密的信息写在羊皮纸上。解下羊皮纸，上面的消息杂乱无章、无法理解，但将它绕在另一个同等尺寸的棒子上后，就能看到原始的消息。

我国古代也早有以藏头诗、藏尾诗、漏格诗及绘画等形式，将要表达的真正意思或“密语”隐藏在诗文或画卷中特定

第一章

1.现代密码学技术仅用于实现信息通信保密的功能 ×

2.密码技术是一种古老的技术，所以，密码学发展史早于信息安全发展史 × 3.密码学是保障信息安全的核心技术，信息安全是密码学研究与发展的目的 √ 4.密码学是对信息安全各方面的研究，能够解决所有信息安全的问题 × 5.从密码学的发展史可以看出，整个密码学的发展史符合历史发展的规律和人类对客观事物的认识规律 √

6.信息隐藏技术其实也是一种信息保密技术 √ 7.传统密码系统本质上均属于对称密码学范畴 × 8.早期密码的研究基本上是秘密的进行的，而密码学的真正蓬勃发展和广泛应用源于计算机网络的普及和发展 √

9.1976年后，美国数据加密标准（DES）的公布使密码学的研究公开，从而开创了现代密码学的新纪元，是密码学发展史上的一次质的飞跃 ×

10.密码标准化工程是一项长期的艰巨的基础性工作，也是衡量国家商用密码发展水平的重要标志 √ 11、1949年，（A、Shannon）发表题为《保密系统的通信理论》的文章，为密码系统建立了理论基础，从此密码学成了一门科学。 12.在公钥密码思想提出约一年后1978年，美国麻省理工学院的ri

第一章

1.现代密码学技术仅用于实现信息通信保密的功能 ×

2.密码技术是一种古老的技术，所以，密码学发展史早于信息安全发展史 × 3.密码学是保障信息安全的核心技术，信息安全是密码学研究与发展的目的 √ 4.密码学是对信息安全各方面的研究，能够解决所有信息安全的问题 × 5.从密码学的发展史可以看出，整个密码学的发展史符合历史发展的规律和人类对客观事物的认识规律 √

6.信息隐藏技术其实也是一种信息保密技术 √ 7.传统密码系统本质上均属于对称密码学范畴 × 8.早期密码的研究基本上是秘密的进行的，而密码学的真正蓬勃发展和广泛应用源于计算机网络的普及和发展 √

9.1976年后，美国数据加密标准（DES）的公布使密码学的研究公开，从而开创了现代密码学的新纪元，是密码学发展史上的一次质的飞跃 ×

10.密码标准化工程是一项长期的艰巨的基础性工作，也是衡量国家商用密码发展水平的重要标志 √ 11、1949年，（A、Shannon）发表题为《保密系统的通信理论》的文章，为密码系统建立了理论基础，从此密码学成了一门科学。 12.在公钥密码思想提出约一年后1978年，美国麻省理工学院的ri

《密码学原理与实践(第三版)》课后习题参考答案

(由华中科技大学信安09级提供)

第一章

1.1（李怡）

(a)51 (b)30 (c)81 (d)7422

1.2（贾同彬）

证明：令t1= (-a)mod m ,t2=m-(a mod m),则t1≡t2(mod m).

又 0

1.3 （张天翼） 证明充分性：

若a?b(modm)，则可得a?b?km，设b?jm?r，0?r?m，j?N，则有

a?(k?j)m?r，故有amodm?r,由假设得bmodm?r，故amodm?bmodm

证明必要性：

若amodm?bmodm，则可设amodm?bmodm?r，则有a?km?r，b?jm?r，其中j,k?N，因此a?b?(k?j)m，即ma?b，故a?b(modm) 综上，问题得证

1.4 （李怡）

令a?km?r,0?r?m,则r?amodm?a?而r?a?km,所以只需证明k???.

m??a?raa?a?因为k?,?m?-r?0,所以?1?k?,即k???mmm?m? 1.5 (李志远)

穷举密钥法来破解移位密码即将这个字符串每个字母移位1，2，3…26次，然后判断这26个字符串哪个符合英语规则。故我编写 如下的C++来实现如此功能 #

《密码学》教案

张焕国，唐明，伍前红 武汉大学计算机学院

一、 教学目的

本课程是计算机科学与技术、信息安全专业的专业选修课。开设本课程的目的是使学生了解并掌握计算机安全保密所涉及的基本理论和方法，具备保障信息安全的基本能力。

二、 教学要求

通过讲授、讨论、实践，使学生了解计算机安全的威胁、密码学算法、安全技术的发展，熟悉计算机安全保密的基本概念、操作系统安全和网络安全，掌握计算机密码学的基本理论、基本方法、常见加密算法及其实现技术、应用方法，重点掌握传统加密算法、DES算法、AES算法、背包算法、RSA算法、ECC算法、DSA算法等。

第一讲 密码学的基本概念

一、信息安全学科概论 1、信息安全学科建设

2001年经教育部批准武汉大学创建了全国第一个信息安全本科专业； 2007年全国信息安全本科专业已达70多所高校；

2003年经国务院学位办批准武汉大学建立信息安全硕士点、博士点、博士后流动站 2007年1月成立国家信息安全教指委

2006年武汉大学信息安全专业获湖北省“品牌专业”

武汉大学成为我国信息安全科学研究和人才培养的重要基地。 2、信息安全学科特点

? 信息安全学科是交叉学科：计算机、通信、数学、物理、生物、管理、法律等； ?

密码学入门

2010-10-08 23:38:17 来自: 阿嚏年糕.R(声色犬马，淡若天涯)

几种常见密码形式：

1、栅栏易位法。

即把将要传递的信息中的字母交替排成上下两行，再将下面一行字母排在上面一行的后边，从而形成一段密码。 举例：

TEOGSDYUTAENNHLNETAMSHVAED 解：

将字母分截开排成两行，如下 T E O G S D Y U T A E N N H L N E T A M S H V A E D

再将第二行字母分别放入第一行中，得到以下结果 THE LONGEST DAY MUST HAVE AN END.

课后小题：请破解以下密码

Teieeemrynwetemryhyeoetewshwsnvraradhnhyartebcmohrie

2、恺撒移位密码。

也就是一种最简单的错位法，将字母表前移或者后错几位，例如： 明码表：ABCDEFGHIJKLMNOPQRSTUVWXYZ 密码表：DEFGHIJKLMNOPQRSTUVWXYZABC

这就形成了一个简单的密码表，如果我想写frzy（即明文），那么对照上面密码表编成密码也就是iucb（即密文）了。密码表可

《现代密码学》第七讲

公钥密码(一)

上讲内容回顾

单向函数 Hash函数的定义 MD5算法 SHA-256算法 SHA-512和SHA-384算法 消息鉴别码简介 CBC-MAC算法 HMAC算法

本章主要内容

公钥密码体制的提出及分类 公钥密码体制的基本概念 单向陷门函数的概念 设计公钥加密算法--背包密码体制 RSA算法及攻击方法 ElGmal算法及椭圆曲线密码体制

公钥密码体制的提出

密钥分配：加密者指定一个密钥后，必须得 想方设法把密钥分发出去给解密者，同时还 得小心翼翼确保密钥不被泄露。这是对称密 码算法固有的一个矛盾，如何解决呢？

对称密码进行密钥分配的要求：

已经共享一个密钥： 利用密钥分配中心：

第一个密钥如何获得

和KDC之间的密钥如何获得

公钥密码体制的提出

密钥管理：在有多个用户的网络中，任何两 个用户之间都需要有共享的秘密钥，当网络 中的用户n很大时，需要管理的密钥数目是n (n-1)/2 无签名功能 当主体A收到主体B的电子文挡 (电子数据)时，无法向第三方证明此电子 文档确实来源于B。

公钥加密体制的原理邮箱的例子 任何人可以向邮箱投举报信 用户(审计人员)才能打开邮箱，读信的内容

公钥加密体制的原理公

今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？ x mod 3 = 2 x mod 5 = 3 x mod 7 = 2 解法：

令a1=2 ，a2=3 ，a3=2 ，p1=3 ，p2=5 ，p3=7 ， n=p1 ? p2 ? p3=3 ? 5 ? 7=105 ， M1=n/p1=35, M2=n/p2=21, M3=n/p3=15 求解 35 · x1 mod 3=1, 得x1=2 求解 21 · x2 mod 5=1, 得x2=1 求解 15 · x3 mod 7=1, 得x3=1

则 x = (M1 · x1 · a1+M2 · x2 · a2+M3 · x3 · a3 ) mod n = (35 ? 2 ? 2+21 ? 1 ? 3+15 ? 1 ? 2) mod 105 = 233 mod 105 同余：如果a = b + kn，k为整数，则

a ? b（mod n）含义：b是a除以n的余数； b为a模n的余数； a与b模n同余。 a mod n ：a模n操作，表示a除以n的余数，为 0到n － 1之间的整数。

例如：(7＋8) mod 12 = 15 mod

一、单项选择题（每题2分，共40分）

（1） 假设加密函数为y?6x?2mod13，如果密文?6，请问以下哪个是明文x（ ） (a)8 (b) 1 (c)9 (d)5

（2）假设Hill密码的加密函数为

?72?y?x??23??mod7

??如果消息x??12?，以下哪个是对应密文y（ ）

(a) y??10? (b) y??41? (c) y??12? (d) y??01? （3）假设置换密码的消息x?decrypt，密钥为如下的置换?：

1234567??x???(x)2351746?? ??请问以下哪个是密文y（ ）

(a)ecydptr (b)ecydptt (c)ecdyprt (d)ecydtrp

（4）差分密码分析属于什么攻击类型（ ）

(a) 已知明文攻击 (b)唯密文攻击 (c)选择明文攻击 (d)选择密文攻击 (5)以下哪些关于分组密码的说法是错误的（ ） (a) 加密函数和解密函数都按照同样顺序使用轮密钥 (b)轮密钥由密钥编排方案生成 (c)分组密码一般采用迭代加密方式 (d)AES是代换-置换网络结构，DES是Feistel结构。 (6)Kercho