当前位置：文档之家 › 密码学理论基础Foundations of Cryptography

密码学理论基础Foundations of Cryptography

  • 格式：ppt
  • 大小：108.00 KB
  • 文档页数：19

下载文档原格式

  / 19

合集下载

密码学理论基础Foundations of Cryptography

密码学理论基础Foundations of Cryptography

Definition
Def: Ensembles X & Y are (唬遍天下) (唬遍天下) indistinguishable in poly-time polyif ∀ poly-time 猜 ∀ P( ) poly|Pr[猜(Xn)=1] - Pr[猜(Yn)=1] | < 1/P(n) Pr[猜 Pr[猜 Def: statistical closeness X & Y are statistically close if ∆(n) = Σα|Pr[ Xn=α] - Pr[ Yn=α] | is negligible for large n.
Definition
Def: Probability ensemble: X={Xn} n∈N, where Xn∈{0,1}n n∈
Ensemble: 合奏 任何一個X 皆為長度n 任何一個Xn皆為長度n的string 在討論 pseudorandom generator 時, 都使用 ensemble 的概念, 很少使用一個bit. 的概念, 很少使用一個bit.
Behavioristic in nature
Behavioristic in nature: Xn is “random” if any efficient observer cannot random” distinguish it from Un. 分不出來 ≡ 相等 用客觀的角度來看, 用客觀的角度來看, 觀察者分不清楚即為 random.
Define 破f
3.For i = 1, 2…n compute xi = the majority of xiJ = bJ ⊕猜h(f(x), rJ⊕ei) over all nonempty J ⊆ {1,…,l} {1,…,l 4.Output x1x2x3…xn

密码学概览

密码学概览
keys[j/5][j%5]='A'+i; j++; } }
for(int i=0;i<5;i++){ for(int j=0;j<5;j++){ mp.insert(pair<char,WordPos>{keys[i][j],WordPos{i,j}}); }
} mp.insert(pair<char,WordPos>{'J',mp['I']}); }
密码学（Cryptography）
密码编码学
是在第三方存在的情况下进行安全通信的实践和研究
更一般地说，它是一个构建和分析以消除敌方影响，并多方面保护信息安全的协议,例：
保密性 真实性 权威性 防抵赖
典型的密码学
通常用于机密使用
A和B共享同一个秘密信息，以保证他们的通话
现代密码
涉及到更多的安全服务 保密性 真实性 权威性 防抵赖
} string ErrorTextCipher_Encode(const string& p, const string& k,const char matrix[26][26]) {
string key = ""; string res = ""; ErrorTextCipher_KeyExpand(key, k, p.size()); for (int j = 0; j < p.size(); j++) {
}
for(int i=0;i<group.size();i+=2){ char p_1=group[i]; char p_2=group[i+1]; WordPos pos_1=mp[p_1]; WordPos pos_2=mp[p_2]; char c_1,c_2; if(pos_1.x==pos_2.x){ pos_1.x=(pos_1.x+1)%5; pos_2.x=(pos_2.x+1)%5; }else if(pos_1.y==pos_2.y){ pos_1.y=(pos_1.y+1)%5; pos_2.y=(pos_2.y+1)%5; }else{ swap(pos_1.x,pos_2.x); } c_1=PlayfairCipher_GetKeyChar(keys,pos_1); c_2=PlayfairCipher_GetKeyChar(keys,pos_2); res+=c_1; res+=c_2;

[课件]第2讲 密码学的基本概念和理论基础PPT

[课件]第2讲 密码学的基本概念和理论基础PPT

20
（3）公元前50年，著名的恺撒大帝发明了一种密码叫做恺 撒密码。在恺撒密码中，每个字母都与其后第三位的字母 对应，然后进行替换。如果到了字母表的末尾，就回到开 始，如此形成一个循环。当时罗马的军队就用恺撒密码进 行通信。 恺撒密码明文字母表：A B C D E F G … X Y Z 恺撒密码密文字母表：D E F G H I J …A BC 26个字符代表字母表的26个字母，从一般意义上说，也可 以使用其它字符表，一一对应的数字也不一定要是3，可 以选其它数字。
3. 密码系统

一个好的密码系统应满足： 系统理论上安全，或计算上安全（从截获的密文或已知 的明文-密文对，要确定密钥或任意明文在计算上不可行 ）； 系统的保密性是依赖于密钥的，而不是依赖于对加密体 制或算法的保密； 加密和解密算法适用于密钥空间中的所有元素； 系统既易于实现又便于使用。
第2阶段：常规现代密码学,从1949年到1975年。
标志：1949年Shannon发表的《保密系统的信

息理论》一文。信息论为对称密码系统建立了理 论基础，从此密码学成为一门科学。
以及《破译者》的出版和美国数据加密标准DES
的实施，标志着密码学的理论与技术的划时代的 革命性变革，宣布了近代密码学的开始。
明文X 加密机 密文Y
原来的明文X
解密机
单钥密码的加密、解密过程
8

双密钥系统又称为非对称密码系统或公开密钥系统。双密钥 系统有两个密钥，一个是公开的，用K1表示，谁都可以使 用；另一个是私人密钥，用K2表示。
K1 明文X 加密算法 密文Y K2 解密算法
原来的明文X
双钥密码的加密、解密过程
双密钥系统的主要特点是将加密和解密密钥分开。即用公 开的密钥K1加密消息，发送给持有相应私人密钥K2的人， 只有持私人密钥K2的人才能解密；而用私人密钥K2加密的 消息，任何人都可以用公开的密钥K1解密，此时说明消息 来自持有私人密钥的人。前者可以实现公共网络的保密通 信，后者则可以实现对消息进行数字签名。

密码学基本介绍

密码学基本介绍

密码学基本介绍转自：鹏越网络空间安全研究院密码系统原理及数学背景下图是一个典型的密码系统，展示了密码技术的应用场景：明文：P 密文：C 加密密钥：K1 解密密钥：K2 加密方法：E 解密方法：D加密与解密的关系可以用公式简洁地表示：C = EK1(P)表示用加密密钥K1通过加密方法E对明文P进行加密得到密文C。

P = DK2(C)表示用解密密钥K2通过解密方法D对密文C进行解密得到明文P。

DK2(EK1(P))=P 由上面两个式子可以得到这个式子。

由此可见，实际上，密码算法E和D都是数学函数。

关于密码学，有两个基本原则：1) 消息必须包含一定的冗余度。

2) 必须采取措施对抗重放攻击。

另外，关于密码系统的设计，还有一个原则叫做Kerckhoff原则：“密码算法必须公开，只有密钥需要保密。

”这个原则体现了一个思想：让入侵者知道密码算法没有关系，所有的秘密都隐藏在密钥中。

对密码算法保密是不明智的，因为密码算法的设计很困难，一旦算法原理泄露了，必须得花费大量精力重新设计。

但密钥可以随时更换。

每个密码算法，都有其数学背景，依赖某一种数学理论。

下面是一些常见密码算法的数学理论依据：1)信息论由香农(Claude Elmwood Shannon)于1948年创立的现代信息论为安全的密码系统定义了一个精确的数学模型。

2)复杂性理论复杂性理论提供了分析密码算法的“计算复杂性”的方法。

它通过对密码算法进行比较，来确定一个密码算法的安全性。

密码算法的“计算复杂性”通常用时间复杂度和空间复杂度两个变量来度量。

3)数论数论中的模运算、素数、最大公因子、求模逆元、费尔马定理、中国剩余定理、迦罗瓦域理论等等，是很多密码学算法的数学基础。

4)因子分解对一个数进行因子分解就是找出它的素数因子。

因子分解是数论中最古老的问题，分解一个数很简单，却是一个耗时的过程。

一些经典的因子分解算法有：数域筛选法、二次筛选法、椭圆曲线法等。

5)计算有限域中的离散对数计算离散对数是数学中公认的难题。

公钥密码学的理论基础

公钥密码学的理论基础

公钥密码学的理论基础公钥密码学的理论基础—单向函数1976年，Diffie W.和Hellman M.E.在他们的《密码学的新方向》一文中提出了公钥密码的概念。

随后，在1978年，Rivest R.L.，Shamir A.和Adleman L.M.在其文《实现数字签名和公钥密码体制的一种方法》中最先提出了一种可行的实现方法，这就是我们现在广泛使用的RSA 体制。

RSA体制的提出真正使得互不相识的通信双方在一个不安全的信道上进行安全通信最终成为可能，也是我们今天CA服务的源泉。

然而，人们很少关心当前幸福生活的背后有一位默默的奉献者—单向函数。

单向和陷门单向函数的概念是公钥密码学的核心，可以说公钥密码体制的设计就是陷门单向函数的设计。

那么什么是单向函数？什么是陷门单向函数？他们的密码学意义何在？本文试图作一个初浅的介绍。

1 单向函数给定任意两个集合X和Y。

函数f：X Y 称为单向的，如果对每一个x属于X，很容易计算出函数f(x)的值，而对大多数y属于Y，要确定满足y=f(x)的x是计算上困难的(假设至少有这样一个x存在)。

注意，不能将单向函数的概念与数学意义上的不可逆函数的概念混同，因为单向函数可能是一个数学意义上可逆或者一对一的函数，而一个不可逆函数却不一定是单向函数。

目前，还没有人能够从理论上证明单向函数是存在的。

单向函数存在性的证明将意味着计算机科学中一个最具挑战性的猜想P=NP，即NP完全问题的解决，而关于NP完全性的理论却不足以证明单向函数的存在。

有幸的是，现实中却存在几个单向函数的“候选”。

说他们是“候选”，是因为他们表现出了单向函数的性质，但还没有办法从理论上证明它们一定是单向函数。

一个最简单的、大家熟知的“侯选”单向函数就是整数相乘。

众所周知，不管给定两个多大的整数，我们很容易计算出它们的乘积，而对于一个300位左右的十进制整数，即使已知它是两个大小差不多(150位左右的十进制数)的素数之积，用世界上计算能力最强的计算机，也没有办法在一个合理的时间内分解出构成这个整数的两个素数因子来。

《密码学基础》课程教学大纲

《密码学基础》课程教学大纲

《密码学基础》课程教学大纲（Fundamentals of Cryptography）课程编号: 1223527课程性质：专业课适用专业：计算机科学与技术先修课程：线性代数、概率论与数理统计、离散数学后续课程：总学分：2学分一、教学目的与要求1. 教学目的密码学包含两个密切相关的方面，其一是密码编码学，研究编写出好的密码系统的方法；其二是密码分析学，研究攻破一个密码系统的途径，恢复被隐蔽信息的本来面目。

通过本课程的学习使学生初步掌握密码编码学的知识、了解密码分析学的基本概念和方法。

2. 教学要求通过本课程的学习，要求学生能初步掌握密码学的主要内容，包括：公钥密码，分组密码，伪随机序列发生器，序列密码，数字签名等等。

要求重点掌握各种密码算法和密码协议及其设计原理，掌握密钥管理、数字签名、身份认证、散列函数等核心技术。

二、课时安排三、教学内容1. 密码学的基本概念(2学时)(1)教学基本要求了解：信息安全模型；信息安全与密码学的关系；密码学的发展方向。

理解：密码学的发展与分类；密码学的基本概念；现代密码学的理论基础。

(2)教学内容①对安全威胁的被动攻击（截获）与主动攻击（中断、篡改、伪造）；②信息安全的三个特性（保密性Confidentiality、完整性Integrity、可用性Availability）；③密码学的分类（密码编码学、密码分析学、密码密钥学）；④密码编码学的分类（对称密码与非对称密码）；⑤密码分析及对密码系统攻击能力等级。

2. 分组密码(4学时)(1)教学基本要求了解：DES；对DES的攻击方法；分组密码设计的一般原理；IDEA；Double-DES，Triple-DES；AES的产生背景。

理解：DES算法；分组密码(DES)的使用模式；IDEA的总体结构；AES算法；逆元的计算；分组密码的工作模式。

(2)教学内容①DES算法的整体结构(重点)；②初始置换、逆初始置换、乘积变换、16轮迭代、函数f、S-盒、P置换；③子密钥的生成及DES的解密过程；④DES的雪崩效应、DES的弱密钥及半弱密钥、对DES的攻击；⑤Double-DES与Triple-DES；⑥分组密码设计的一般原理及分组密码的工作模式（ECB、CBC、CFB、OFB）；⑦IDEA的总体结构，8轮迭代、输出变换、密钥调度、乘积运算；⑧逆元的计算；⑨DES，Double-DES，Triple-DES，IDEA的安全性；⑩AES分组密码算法（轮变换、加轮密钥、密钥调度、密钥扩展等）。

密码学理论基础25页PPT文档

密码学理论基础25页PPT文档
Classic : information theory based Modern : complexity theory based
Classic
Classic : information theory based
目標 : perfect security, 使竊聽者絕對無法猜到 plain text, 其描述為 : eavesdropper所能猜到的最 好情況, 使 eavesdropper竊聽到 ciphertext之前和 之後皆是相同情況.
Illustration
Alice要送一封信給Bob,但是Carol想要偷看, 如何防止被偷看或偷聽則是1970年代之前, 密碼學的重要課題.
Sender : Alice
Receiver : Bob
Key (K)
Key (K)
Ciphertext (M*)
Plain
Plain
text (M)
Encryption
還要強
Fault-tolerant protocol
Fault-tolerant protocol有三個問題可以討論
Coin toss over phone (兩人在電話中,如何丟一公 正錢幣)
Simultaneous exchange of secrets (兩人如何能同時 交換所持有的秘密,當一方反悔時,雙方皆無法成 功取得對方的資料)
Example : RSA, base on 因數分解是很難的
Part III : Three basic tools
Basic tools
Three basic tools :
One way function (OWF) –chapter 2 Pseudorandom generator (PRG) –chapter 3 Zero knowledge proof –chapter 4

密码学基础ppt课件

密码学基础ppt课件
于对密钥的保密。
2019
29
对称密码算法 vs.非对称密码算法
对称密码算法（Symmetric cipher）：加密密钥和解 密密钥相同，或实质上等同，即从一个易于推出另一 个。又称传统密码算法（Conventional cipher)、秘密密 钥算法或单密钥算法。
DES、3DES、IDEA、AES
16
密码学
密码学（Cryptology）
• 研究信息系统安全保密的科学。由两个 相互对立、相互斗争，而且又相辅相成 、相互促进的分支科学所组成的，分别 称为密码编码学（Cryptography）和密码 分析学（Cryptanalysis）。
2019
17
密码编码学 Vs. 密码分析学
密码编码学（Cryptography） • 主要研究对信息进行编码，实现对信息的隐 蔽。 密码分析学（ Cryptanalysis ） • 主要研究加密消息的破译或消息的伪造。
加密和解密算法的操作通常都是在一组密钥的控制下进 行的,分别称为加密密钥(Encryption Key) 和解密密钥 (Decryption Key)。
2019 23
密码算法
密码算法（Cryptography Algorithm）：用于加密 和解密操作的数学函数。 加密算法（Encryption Algorithm）：发送者对明 文进行加密操作时所采用的一组规则。 解密算法（Decryption Algorithm）：接收者对密 文进行解密操作时所采用的一组规则。
90年代，逐步出现椭圆曲线等其他公钥算法。
公钥密码使得发送端和接收端无密钥传输的保密通 信成为可能！
2019 14
什么是密码学
密码学基本概念 密码体制分类 密钥管理

密码学基本概念

密码学基本概念
7
近代密码学
20世纪初到1949年： ▪ 主要标志是机械密码/机电密码，用机电代替手 工。 ▪ 近代密码体制是用机械或电动机械实现的，最 著名的就是转轮机（Rotor Machine）。
8
转轮机 Germany: ENIGMA（1919）
转轮密码机ENIGMA， 由Arthur Scherbius于 1919年发明。在二次世 界大战期间, Enigma曾 作为德国陆、海、空三军 最高级密码机。
21
加密 vs.解密
加密（Encryption）：将明文变换为密文的过程。
▪ 把可懂的语言变换成（人类/机器）不可懂的语言。
解密（Decryption）：由密文恢复出原明文的过程。
▪ 加密的逆过程 ▪ 即把不可懂的语言变换成可懂的语言。
明文
密文
加密算法
密文
明文
解密算法
密
密
钥
钥
加密和解密算法的操作通常都是在一组密钥的控制下进 行的,分别称为加密密钥(Encryption Key) 和解密密钥 (Decryption Key)。
Polygram Substitution cipher 多表代替密码
Monoalphabetic Substitution cipher Ployalphabetic Substitution cipher
6
举例：密码广播
❖代替？置换？
❖测试：余则成接受广播 呼叫所使用的密码本是（）
▪A 红楼梦 ▪B 朱子家训 ▪C 蝴蝶梦 ▪D 康熙字典
19
密码通信模型
非法 主动攻击 入侵者
被动攻击 窃听者
M’
C’
明文 M
加密器 （Encrypter）来自C=EK1(M)E

密码学基础介绍

密码学基础介绍
ABCDEFGH I J KLM X N Y A H P OG Z QWB T NOPQR S T U VWX Y Z S F L RCVMUEK J D I
明文 HELLO
密文 GHBBF
7
置换密码
在置换密码中，保持明文的所有字母不变，只是利 用置换打乱了明文字母的位置。
x
1
2
3
4
5
π(x)
密码学基本概念 对称密码 密钥分发技术 非对称密码 数字签名 公共密钥基础设施
还是送信问题
Bob终于打开了箱子，并且看到了信件，在信件的末尾，Bob 看到了Alice的签名，但Bob又有疑虑了。
Alice以前的签名都用钢笔，这次怎么是圆 珠笔签名呢？到底是不是Alice本人签的？
Alice
Mallory
Bob
25
目录
密码学基本概念 对称密码 密钥分发技术 非对称密码 数字签名 公共密钥基础设施
继续送信问题
假设Bob有一把锁和两个钥匙K1和K2，其中K1用于将锁锁上， 而K2用于将锁打开，K1和K2这两个钥匙是不一样的。 那么Alice和Bob怎么安全传递这封信件呢？
最终K1=K2=gab mod n就是共享密钥。
24
中间人攻击
DH密钥交换容易被中间人攻击(man-in-themiddle)所破坏： 第三方Mallory插在Alice和Bob的中间，侦听Alice 和Bob之间的通信。当Alice向Bob发起通信时扮演 Bob；当Bob向Alice发起通信时扮演Alice。Alice 和Bob都与Mallory协商了一个密钥，然后Mallory 就可以监听和传递Alice和Bob之间的通信，而 Alice和Bob全然不知。

法国数学家 密码学基础

法国数学家 密码学基础

法国数学家密码学基础
密码学是一门旨在保障信息安全的学科，它研究如何设计和使用密码来保护通信、计算机系统、电子商务和数字身份等方面的信息。

密码学的基本原理涉及加密算法、密钥管理、认证和数字签名等。

其中，加密算法是保障信息机密性的核心，它将原始信息转换为密文，使得未经授权的人员无法读取原始信息。

密码学常用的加密算法包括对称密钥加密和非对称密钥加密。

对称密钥加密使用同一个密钥进行加密和解密，而非对称密钥加密则使用不同的公钥和私钥进行加密和解密。

对称密钥加密的速度快，但需要在通信双方之间安全地共享密钥；非对称密钥加密则不需要共享密钥，但加密解密速度较慢。

因此，在实际应用中，常常将两种加密方法结合使用，以达到更好的保密效果。

密码学在现代社会中扮演着十分重要的角色，它不仅应用于军事、政府等领域，也广泛运用于商业、金融、医疗、互联网等各个领域。

- 1 -。

第2讲 密码学的基本概念和理论基础

第2讲 密码学的基本概念和理论基础
因此，july的加密是DELW。
同理，可使用K-1进行解密。
Vigenè re密码
构成 明文：每个字符惟一对应一个0~25间的数字。 密钥：一个字符串，其中每个字符同明文一样对应一 个数字，代表位移值，如a 表示位移 0，b 表示位移 1， c 表示位移 2，...... ）。
加密过程：
Caesar密码
公元前50年，著名的恺撒大帝发明了一种密码叫做恺撒密 码。在恺撒密码中，每个字母都与其后第三位的字母对应， 然后进行替换。如果到了字母表的末尾，就回到开始，如 此形成一个循环。当时罗马的军队就用恺撒密码进行通信。


恺撒密码明文字母表：A B C D E F G … X Y Z


“****-/*----/----*/****-/****-/*----/---**/*----/****-/*----/-****/***-/****-/*----/----*/**---/-****/**---/**---/***--/--***/****-/”

“她唯一给我的提示就是这个是5层加密的密码，也就是说要破解5 层密码才是答案。最终语言是英语。 ” 网友贴出了莫尔斯密码对照表，然后发现相应密码对应的数字组 合和英文字母组合分别是：“4194418141634192622374”、 “daiddahadafcdaibfbbcgd”
将明文数字串依据密钥长度分段，并逐一与密钥数字 串相加（模26），得到密文数字串；
最后，将密文数字串转换为字母串。

例 设m＝6，且密钥字是k=CIPHER,这相应于密钥。假定 明文串是 this cryptosystem is not secure 首先将明文串转化为数字串，按6个一组分段，然后模26“加” 上密钥字得：

密码学理论基础Foundations of Cryptography

密码学理论基础Foundations of Cryptography

Proof: Claim 2
Define 破fp (y) as follows:
Uniformly select 零頭 string y’ with |y’|=|y| Let zx = 破gp (y’y) Return x;
Goal: ∀ polynomial q( ), ∃ 破*fq , s.t. Pr[破*fq inverts f(Un)] ≥ 1-(1/q(n)) Pr[破 1-
Claim 1: g is not strongly one-way. oneClaim 2: g is still weakly one-way. one-
Definition
Def: A string z is 零頭字串, if the first log2|z| 零頭字串, bits of z are all zero.
Q1: All OWFs are strong? (i.e. 會不會 f ∈ strong OWF↔ f ∈ weakly OWF?) OWF?) Q2: All OWFs are weak? (i.e. 會不會不存在 strong OWF, 而只有 weakly OWF?) OWF?) Q3: Universal OWF?
Proof way
Approach:利用反證法證明,先假設g Approach:利用反證法證明,先假設g is not a strongly OWF, 推出 f也不是weakly OWF,和前 也不是weakly OWF,和前 提不合產生矛盾. 提不合產生矛盾. 由g is not strongly one-way此句話可寫為 one-way此句話可寫為 ∃破g s.t. ∃ polynomial q( ), Pr [破g inverts g(Un²p(n))] ≥ 1/(q(n²p(n))) [破

密码学基础知识

密码学基础知识

20 17 4 2 8 15 22 25 19
相应的密文串将是:
VPXZGIAXIVWPUBTTMJPWIZITWZT
解密过程与加密过程类似,不同的只是进行模26减,而不是模26 加。
使用Vigenère表可以方便地进行加密和解密。
Example -V
• Nomenclator 代码本 c.1400
➢ 字母、符号、单词、短语
代码
➢ 代码
字母、符号、单词、短语
➢ 应用：World War II
Example –Con’t
• 网格加密法：中国 – 例：密文：
王先生： 来信收悉，你的盛情难以报答。我已在昨天抵
达广州。秋雨连绵，每天需备伞一把。大约本月 中旬即可返回，再谈。
• 信息安全的其他方面 – 信息的不可否认性Non-repudiation ： 要求无论发送方还是接收方都不能抵赖所进 行的传输
– 鉴别Authentication 鉴别就是确认实体是它所声明的。适用于用
户、进程、系统、信息等
– 审计Accountability • 确保实体的活动可被跟踪
– 可靠性Reliability • 特定行为和结果的一致性
• 接收者对密文解密所采用的一组规则称为解密算法 (Decryption Algorithm).
密钥
密钥
密文
明文 加密算法
解密算法
明文
加解密过程示意图
• 加密和解密算法的操作通常都是在一组密钥的 控制下进行的,分别称为加密密钥(Encryption Key) 和解密密钥(Decryption Key).
Beale密码
古典密码
(1) When, in the course of human events, it becomes necessary (11) For one people to dissolve the political bands which have (21) Connected them with another, and to assume among the Powers (31) Of the earth the separate and equal station to which (41) The Laws of Nature and of Nature’s God entitle them, (51) A decent respect to the opinions of mankind requires that (61) They should declare the causes which impel them to the (71) separation. We hold these truths to be self-evident, that (81) All men are created equal, that they are endowed by (91) Their Creator with certain unalienable rights, that among (99) These are Life, Liberty, and the pursuit of Happiness.

第二部分密码学基础-.ppt

第二部分密码学基础-.ppt
密码分析员(Cryptanalyst)：从事密码分析的人。
被动攻击(Passive attack)：对一个保密系统采取截获 密文进行分析的攻击。
主动攻击(Active attack)：非法入侵者(Tamper)、攻 击者(Attcker)或黑客(Hacker)主动向系统窜扰，采用删 除、增添、重放、伪造等窜改手段向系统注入假消息， 达到利已害人的目的。
2021/1/3
2
。
几个概念（一）
明文(消息)(Plaintext) ：被隐蔽消息。
密文(Ciphertext)或密报(Cryptogram)：明文经密码 变换成的一种隐蔽形式。
加密(Encryption)：将明文变换为密文的过程。
解密(Decryption)：加密的逆过程，即由密文恢复出 原明文的过程。
双钥体制(Two key system)：
加密密钥和解密密钥不同。
2021/1/3
11
密码体制分类 单钥体制
明文
加密器 EK
K
密钥产生器
密文
解密器 DK
K
明文
2021/1/3
12
密码体制分类 单钥体制
单钥体制主要研究问题：
密钥产生(Key generation)， 密钥管理(Key management)。
防止消息被窜改、删除、重放和伪造的一种有效方法, 使发送的消息具有被验证的能力，使接收者或第三者能够 识别和确认消息的真伪。实现这类功能的密码系统称作认 证系统
保密性
保密性是使截获者在不知密钥条件下不能解读密文的 内容。
认证性
使任何不知密钥的人不能构造一个密报，使意定的接收
者解密成一个可理解的消息(合法的消息)。
每个用户都有一对选定的密钥(公钥k1；私钥 k2)，公开的密钥k1可以像电话号码一样进行注
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

Two trivial inverting algorithm
明牌 “破f = 明牌” (每次都猜相同的號碼) 明牌” 每次都猜相同的號碼)
中獎機率: 中獎機率: Pr [ f ( 牌 (f(Un),1n) ) = f (Un) ] = Pr [ f (0n) = f (Un) ] ≥ (1/2n )
n
Version 2 & 3
為了改進Version 1的問題,因此推出Version 為了改進Version 1的問題,因此推出Version 2 Pr [ 破f inverts f(Un) ] = Pr [ 破f (f(Un),1n) = Un ] 但是真正使用的為Version 3,如下: 但是真正使用的為Version 3,如下: Pr [ 破f inverts f(Un) ] = Pr [ f ( 破f (f(Un),1n) ) = f (U? 電腦選號和明牌法哪一個中獎機率高?
若 m = n, 則 (1/2m ) = (1/2n ) 若 m ≥ n, 則 (1/2m ) ≤ (1/2n ) 若 m ≤ n, 則 (1/2m ) ≥ (1/2n )
Ask more about f
Can we ask more about f for the def of OWF?
Observable
Observable 1:
g( ) is length-regular, because |g(x)|=1+P(|x|) length-
Observable 2:
If |x|=|x’| and g(x)=g(x’) then f(x)=f(x’). |x|=|x’ g(x)=g(x’ f(x)=f(x’ 因為g(x)和g(x’ 相等,為了對齊string中的1,則將觀 因為g(x)和g(x’)相等,為了對齊string中的1,則將觀 察出 f(x)=f(x’). f(x)=f(x’
Proof lemma
Q1: g is easy to evaluate?
Yes! Because f is easy to evaluate.
Q2:g-1 is hard to evaluate? (Is it hard to invert g?)
Yes! Because f is hard to invent. Proof way: f -1 ∉ BPP → g -1 ∉ BPP
Length regular
If |x|=|x’|, then |f(x)|=|f(x’)| |x|=|x’ |f(x)|=|f(x’
Length preserving
|f(x)|=|x|, ∀ x
Defined only for some length
f(x) is defined only if |x| ∈ I ⊆ N
OWF definition
For any 1. prob. poly-time algorithm “破f” poly2. polynomial P( ) 3. sufficiently large n, we have Pr [ 破f inverts f (Un) ] < 1/P(n) PS. Un是長度為n的任意字串 Un是長度為n
Version 1
Pr [ 破f inverts f(Un) ] 等號前後的 Un是同一個 = Pr [ 破f (f(Un)) = Un ] = Σx ∈{0,1} (1/2n) Pr [ 破f (f(x)) = x ] 上式有一個很大的問題, 上式有一個很大的問題,那即是很容易依此 公式造出OWF,但是並不是因為很困難而無 公式造出OWF,但是並不是因為很困難而無 法解,而是沒時間解, 法解,而是沒時間解,讓 |f(x)| = O ( log|x| ) ∀ x ∈ {0,1}* ,可以滿足上式所要求的條件,但 ,可以滿足上式所要求的條件, 這樣的function並不難,而且與OWF所要求之 這樣的function並不難,而且與OWF所要求之 prob. poly-time algorithm 的條件1不合. poly的條件1不合.
白話: 上面的三個對OWF的要求, 白話: 上面的三個對OWF的要求,並不會影響 OWF的一般性. OWF的一般性.
Lemma
Lemma: If there exists an OWF f, then there exists a length-regular OWF g. length白話: OWF多要求 length白話: 對OWF多要求 length-regular 的性質,並 性質, 不會讓 OWF 的存在更困難. 的存在更困難. Proof: since f is one-way, there exists a onepolynomial P( ), such that |f(x)| ≤ P(|x|), ∀ x, let g: {0,1}*→ {0,1}* be as follow P(|x|)g(x) = f(x)10P(|x|)-|f(x)|
Two trivial inverting algorithm
電腦選號 “破f = 瞎猜” (每次號碼皆不同) 瞎猜” 每次號碼皆不同)
中獎機率: 中獎機率: Pr [ f ( 猜 (f(Un),1n) ) = f (Un) ] = Pr [ f (Un’) = f (Un) ] = Σ y ∈{0,1}m Pr [f (Un)=y ]* Pr [f (Un’)=y ] = Σ y ∈{0,1}m ( Pr [f (Un)=y ] )² ≥ (1/2m ) m = max |f(x)|, x ∈{0,1}n Σ i=1 ~ 2m ai = 1, Σ i=1 ~ 2m (ai) ² ≥ (1/2m )
Q: success prob. ≥ ⅔的條件會不會要求太低?? 的條件會不會要求太低?? Ans : No!! 因為若成功機率為1/n,則失敗機 因為若成功機率為1/n,則失敗機 率為(1-(1/n)),且(1率為(1-(1/n)),且(1-(1/n))n < 1/e ∀ n ≥ 1,所以 1/e 1,所以 只要經過2n的時間,則失敗機率會小於(1/e 只要經過2n的時間,則失敗機率會小於(1/e)² < ⅓,因此此要求並不會太低. ⅓,因此此要求並不會太低.
Strongly OWF = weakly OWF?
Lemma: If there is a weak/strong OWF f, then there is a weak OWF g that is not strongly oneoneway. Strongly OWF ≠ weakly OWF Example: g is not strong, but a weak. g(px)= px if the log2|x|-bit prefix of p |x|is not all zero. pf(x) otherwise
OWF definition
OWF definition: A function f is (strongly) oneoneway if ( f: {0,1}*→ {0,1}* ) 1. f ∈P [easy to evaluate] 2. ≈ f-1 ∉ BPP [hard to invert] 白話: 白話: Any probabilistic poly-time algorithm for polyinverting f has negligible success probability.
P(|x|)Step 1: 算出 g(x) = f(x)10P(|x|)-|f(x)| Step 2: call 破g (g(x), 1n), return the output of 破g
所以g 所以g -1 ∉ BPP.
By Obs2, 若 g(x)=g(x’) 則 f(x)=f(x’) 所以可知 Pr [f (破f (f(Un),1n ) )= f(Un)] (破 ≥ Pr [g (破g (g(Un),1n ) )= g(Un)] (破 因為f 因為f -1 ∉ BPP
Conclusion: If there exists an OWF f, then there exists a length-regular OWF g. length-
Proof Q2
Assume there is an invert algorithm 破g for g ≡ Pr [g (破g (g(Un),1n ) )= g(Un)] 夠大 (破 Def: 破f (f(x), 1n)
密碼學理論基礎 Foundations of Cryptography
呂學一 (中央研究院 資訊科學所) 資訊科學所) .tw/~hil/
Today
One way function
Last time OWF definition Three versions Two trivial inverting algorithm Ask more about f
Weakly OWF
Part I : One way function
Last time
One way function
f:
EASY f(x) ∈ P
x
HARD f -1 ∉ BPP
f(x)
OWF
考慮OWF的條件: 考慮OWF的條件: “f -1 ∉ BPP” BPP” BPP:
Polynomial time Success prob. ≥ ⅔
Part II : Weakly OWF
Weakly OWF
Weakly OWF definition: A function f is weakly oneone-way if ( f: {0,1}*→ {0,1}* ) 1. f ∈P [easy to evaluate] 2. ≈ f-1 ∉ BPP [slightly hard to invert] ∃ a poly P( ), s.t. ∀ 1. prob. poly-time algorithm “破f” poly2. sufficiently large n, we have Pr [ 破f inverts f (Un) ] < 1- (1/P(n)) 1-