当前位置：文档之家 › 第3章 密码学的复杂性理论基础

第3章 密码学的复杂性理论基础

  • 格式：ppt
  • 大小：822.00 KB
  • 文档页数：21

下载文档原格式

  / 21

合集下载

密码学的计算复杂性理论

密码学的计算复杂性理论
间算法.
例如：Hanoi塔问题算法的时间复杂度，可以用一个指数函数O(2n)来表示， 显然，当n很大（如10000）时，计算机是无法处理的。相反，当算法的时间 复杂度的表示函数是一个多项式，如O(n2)时，则可以处理。因此，一个问 题求解算法的时间复杂度大于多项式（如指数函数）时，算法的执行时间将 随n的增加而急剧增长，以致即使是中等规模的问题也不能求解出来，于是 在计算复杂性中，将这一类问题称为难解性问题。人工智能领域中的状态图 搜索问题（解空间的表示或状态空间搜索问题）就是一类典型的难解性问题。
当n很大时，问题很难。 对于n=8,现已知此问题共有92种解，但只有12种是独立的，其 余的都可以由这12种利用对称性或旋转而得到。 设n=4，试一试。
编程试一试，看能解到n多大？
3）SAT问题
使可以得判(形定x1(式0一) , 化x个2(0地)n,元表,布x示n(0尔)为) 函：数。称为f (可x1(y0满) ,x足2(f0)(性,x1,问,xx2题n,(0) )（,xS1n a) tisfiab，il是ity否）存，在简一称组SA赋T,它值
启发式求解： • 子句检测：如果当前取值使得某个子句为假，则立即回溯 • 纯符号启发：所谓纯符号是指在所有子句中以同样形式出现的变量。例如
（A∨~B）∧（~B∨~C）∧（A∨C）中，A和~B是纯符号。对于所有的纯符号 都可以设它们的值为真。因为对于任何一种满足整个CNF的变量取值来说，如果 某个纯符号为假，把它变成真不会影响整个CNF的值。特别地，在判断纯符号时 可以忽略某些已经为真的子句。 • 单元子句启发：单元子句是指只有一个变量的子句。单元子句的符号取值必须为 真。特别地，如果某个子句中除了一个符号之外的所有符号值都为假，则这个子 句也是单元子句。

现代密码学第三讲(二)：复杂性理论

现代密码学第三讲(二)：复杂性理论

算法复杂度的定义
定义 假设一个算法的计算复杂度为O(nt)，其 中t为常数，n为输入问题的长度，则称这算 法的复杂度是多项式的。具有多项式时间复 杂度的算法为多项式时间算法.
函数g(n)=O(nt)表示存在常数c>0和n0>=0，对一切 n> n0均有|g(n)|<=c|nt| 成立，也就是说，当n足 够大时，g(n)存在上界.
7
算法复杂度的定义
时间（计算）复杂性：考虑算法的主要操作 步骤，计算执行中所需的总操作次数. 空间复杂性：执行过程中所需存储器的单元 数目. 数据复杂性：信息资源. 计算模型----确定性图灵机（有限带符号集合， 有限状态集，转换函数）（读写头，读写带） .
8
算法复杂度的定义
不同的编程语言，不同的编译器导致执行一 次操作的时间各不相同，为了方便不同算法 比较，通常假定所有计算机执行相同的一次 基本操作所需时间相同，而把算法中基本操 作执行的最大次数作为执行时间. 基本操作数量 运行时间= 机器速度
为NP完全的.
17
π ∈NP，都有π ∝ π ′ ，则称 π ′ 属于NPC类，或称
规约思想与NPC类 规约思想与NPC类 NPC
主要知识点小结
算法的复杂度定义及分类 密码算法的计算复杂度
作业
1 求冒泡排序法的计算复杂度, 该算法是否为多项 式的？ 2 超递增背包问题：
设A=(a1,a2,…,an)是由n个不同的正整数构 j −1 n 成的n元组，且 a j > ∑ ai j = 2,L ,， i =1 S是另一已知的正整数。 求A的子集A’，使 ∑ a i = S. a ∈A ' (1) 给出该问题的求解算法； (2) 求算法的计算复杂度.

第2讲 密码学的复杂性理论基础

第2讲 密码学的复杂性理论基础
它通常含有若干个参数。
对于一个问题进行描述应该包括两方面的内容：必须对
问题的所有给定参数给出一般性描述；必须描述该问题 的答案（或解）应该满足的性质。
当问题的所有参数都有了确定的取值时，我们称得到了
该问题的一个实例（instance）。
算法（algorithm）

即求解某个问题的一系列具体步骤（通常被理解为求解所需
的通用计算程序）。
算法总是针对具体问题而言的，求解一个问题的算法通
常不止一个。
当某个算法能够回答一个问题的任何实例时，我们称该
算法能够回答这个问题。
当一个问题至少有一个能够回答该问题的算法时，我们
称该问题可解（resolvable），否则称该问题不可解 （unresolvable）。
算法复杂性
GMR模型； FFS模型。

非交互零知识证明 ：用一个短随机串代替交互过程并实现 了零知识证明 。 20世纪80年代末，Blum等人进一步提出
成员（或定理）的非交互零知识证明系统；
知识（或身份）的非交互零知识证明系统。
交互图灵机

交互图灵机指的是一个具有一条只读输入带、一条工作带、 一条随机带、一条只读通信带和一条只写通信带的图灵机。 其中，随机带上包含一条无限长的随机比特序列，并且只能
2
12
11.6天
32,000年
宇宙年龄的10
2 3
301006
18
O (2 )
n
10
301 , 030
O(1) O(log
n) O(n) O(nlog 2
n) O(n ) O(n ) O(2 ) 2
n
问题复杂性

密码学理论基础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

3.密码学基础PPT课件

3.密码学基础PPT课件
25
明文 vs.密文
• 明文(Plaint或密报(Cryptogram)：明文经密码变换而成 的一种隐蔽形式。 • 加密员或密码员(Cryptographer)：对明文进行加密操作的人 员。
26
加密 vs.解密
加密（Encryption）：将明文变换为密文的过程。把可懂的 语言变换成不可懂的语言，这里的语言指人类能懂的语言和 机器能懂的语言。
31
对称密码算法 vs.非对称密码算法
•对称密码算法（Symmetric cipher）：加密密钥和解密密钥相同， 或实质上等同，即从一个易于推出另一个。又称传统密码算法 （Conventional cipher)、秘密密钥算法或单密钥算法。
– DES、3DES、IDEA、AES
•非对称密码算法（Asymmetric cipher） ：加密密钥和解密密钥 不同，从一个很难推出另一个。又叫公钥密码算法（Public-key cipher)。其中的加密密钥可以公开，称为公开密钥（public key)， 简称公钥；解密密钥必须保密，称为私人密钥（private key)，简 称私钥。
14
现代密码学
Shannon
1949～1975年：
– 1949年，Shannon的论文“The Communication Theory of Secret Systems” 。
– 1967年，David Kahn的专著《The Code breakers》。
– 1971年～1973年，IBM Watson实验室的Horst Feistel等人发表的几篇技术报告。
5
古典密码学分类
Substitution cipher
Stream cipher
代替密码

现代密码学_第三讲 密码学基本知识

现代密码学_第三讲 密码学基本知识

Pr[ p]Pr[c | p] { k : p d ( c )} Pr[ p | c] Pr[k ]Pr[ p d k (c)] Pr[c] { k :cC ( k )}
k
Pr[ p ]

Pr[ k ]
密 钥
Pr[c | p ]
解密算法
{k : p d k ( c )}
Pr( y
j 1
m
j
) 1
16
密码体制组成部分熵的基本关系
设(P，C，K，E，D)是一个密码体制，那么，
H(K|C)=H(K)+H(P)-H(C) 证明：首先，有H(K,P,C)=H(C|K,P)+H(K,P)。因为密钥和明 文唯一决定密文，所以，H(C|K,P)=0。又K和P是统计独立的，
所以，H(K,P)=H(P)+H(K)。 可得， H(K,P,C)=H(K,P)=H(P)+H(K) 。 同样，密钥和密文唯一决定明文，得H(P|K,C)=0，因此有
H(K,P,C)=H(K,C)。 所以，H(K|C)=H(K,C)-H(C) =H(K,P,C)-H(C) =H(K)+H(P)-H(C)
可得， H(K|C)= H(K)+ H(P) - H(C) ≈ 0.46
18
相关性(举例)
猜字母。假设收到便条“I lo_e you”，请问残缺的字母应 该是什么？在英语中符合lo_e结构的所有单词，其部分如下：
lobe lode loge lone lope lore lose love
17
举例说明(续)
根据题意，易得：
假设P={a,b}满足Pr[a]=1/4,Pr[b]=3/4。设 K={k1,k2,k3} 满足Pr[k1]=1/2, Pr[k2]=1/4, Pr[k3]=1/4。设C={1,2,3,4}，加密函数定义 为ek1(a)=1, ek1(b)=2, ek2(a)=2, ek2(b)=3, ek3(a)=3, ek3(b)=4。

安徽工程大学 信息安全原理及应用 第3讲 密码学的复杂性理论基础


或其解法的任何信息；
（4）V要求P：（a）证明新、旧难题同构；或者（b）公布P在 （2）中提交解法并证明该解法的确为新难题的解法； （5）P答应V的要求； （6）重复步骤（1）~（5）次。

图灵机是一种具有无限读写存储带的有限状态机，可以被当
作一个实际可用的计算模型 。
确定性图灵机。
非确定性图灵机：能够进行猜测。求解一个问题分两个
阶段：猜测阶段和验证阶段。
问题分类

易处理的（tractable） ：确定性图灵机上能够在多项式时间
内得到处理的问题。称易处理问题的全体为“多项式时间可
第3章
密码学的复杂性 理论基础
1
密码技术和算法复杂性

计算复杂性：研究密码分析对于计算量的需求和密码分析的
困难程度 ，从而得出这些密码技术和算法在现有可行的条
件下是否具有足够的安全性：
算法复杂性； 问题复杂性。

密码协议、方案和体制的安全性证明：零知识证明理论。
问题（problem）

即需要回答的一般性提问:
则称f (n)与h (n)为同数量级的，记为f(n)=O(h(n))。容易
证明，当f(n)是n的k次多项式时，则f(n)=O(nk)，即所有低阶
项与常数项可忽略不计。
多项式时间算法：f(n)=O(nk) 指数时间算法：f(n)=O(αh(n))(α>1)
O
算法复杂性
计算复杂性的表示符号为“ O ”（称为“大O ”），表示 计算复杂性的数量级。 好处：
给定一组物品，每种物品都有自己的重量和价格，在限定的总
重量内，我们如何选择，才能使得物品的总价格最高
给定n个整数的集合A和一个整数N，决定是否存在一个子集S，

第4章密码学的计算复杂性理论基础

*
r
• 定义 4.14 称一个多项式时间概率算法M可解 一个语言L的成员识别问题，若对任一输入数 据 x 0,1*，有 （1）若 x L，则 Prb( x) 1 2 / 3 （2）若 x L ，则 Prb( x) 0 2 / 3 称一个语言L的成员识别问题属于BPP类，若 存在一个可解该问题的多项式时间概率算法。 所有BPP类问题构成的集记作BPP。
4.1.2 算法与图灵机
有限状态控制器 读写头
…. -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 …无限长 磁带
图4.1 确定性单带图灵机示意图
• 定义 4.4 一个确定性单带图灵机由下列集和函数构成。 1. 1）带中所用字符集B，通常可设 B 0,1, ，其中 表示空。 2）读写头所处的可能状态集S，其中包含一个初始状态 和若干个停机状态 。 s0 TS 3）读写头所处状态的转移函数 ，它是读写头现在所处状 态s和所读字符b的函数，表示为 。 :SB S 4）读写头动作的指令函数 ，它也是读写头现在所处状态 s 和所读字符b的函数，表示为 ，其中 :S B B l , r l代替 r b， 且都不属于B。若 ，则读写头写字符 ' ' (s, b) b B b 且保持原位不动。若 ，则原字符b保持不变， (s, b) l (或r ) 读写头向左（或向右）移动一个小方格。 2. 磁带上的每个小方格用一个整数坐标i表示。小方格i中的字 符记作t(i)，磁带表示为函数 。
K ( x) K ( x)
K ( x)
K ( x)
f M (n) maxK ( x)
x; x n
• 定义 4.6 设f(n)和g(n)为两个正整数函数， nn n0 c使当 若存在正整数 和常数 时 有 f (n) cg(n)，则记作 f (n) ( g (n)) ； 若 f (n) ( g (n)) ， g (n) ( f (n)) ，则记作

密码学的理论基础


RSA算法介绍:
设p、q为两个大素数，n=pq
令φ(n)=(p-1)(q-1) 寻找一对e,d，使ed≡1 mod φ(n) 加密：E(X)=xemod n, x∈Zn 解密：E(y)=ydmod n, X∈Zn
• 非对称密码体（Asymmetric Encryption）
– 非对称密码体制也叫公开密钥密码体制、双密钥密码体制。其原 理是加密密钥与解密密钥不同，形成一个密钥对，用其中一个密 钥加密的结果，可以用另一个密钥来解密 。 – 目前普遍使用的对称加密算法主要有RSA、Elgamal（离散对数） 、ECC（椭圆曲线）等。
明文（64bits）
DES
IP置换（64bits）
算 法
L0(32bits)
R0(32bits)
+
f
ki
结
构
L1=R0
R1=L0 + f(R0,k1) 16轮同样运算…
L16
R16=L15 + f(R15,ki)
IP-1置换（64bits）
DES：IP置换
IP置换表
58 60
50 52
42 44
• 密码学的理论基础
– 密码学的理论基础之一是1949年Claude Shannon发表 的“保密系统的通信理论”（The Communication Theory of Secrecy Systems），这篇文章发表了30年 后才显示出它的价值。1976年W.Diffie和M.Hellman发 表了“密码学的新方向”（New Directions in Cryptography）一文，提出了适应网络上保密通信的公 钥密码思想，开辟了公开密钥密码学的新领域，掀起 了公钥密码研究的序幕。受他们的思想启迪，各种公 钥密码体制被提出，特别是1978年RSA公钥密码体制 的出现，成为公钥密码的杰出代表，并成为事实标准 ，在密码学史上是一个里程碑。

密码学的计算复杂性理论


从前，有一个酷爱数学的年轻国王向邻国一位聪明美丽的公主求婚。 公主出了这样一道题：求出48 770 428 433 377 171的一个真因子。若国王 能在一天之内求出答案，公主便接受他的求婚。国王回去后立即开始逐个 数地进行计算，他从早到晚，共算了三万多个数，最终还是没有结果。国 王向公主求情，公主将答案相告：223 092 827是它的一个真因子。国王很 快就验证了这个数确能除尽48 770 428 433 377 171。公主说：“我再给你 一次机会，如果还求不出，将来你只好做我的证婚人了。”国王立即回国， 并向时任宰相的大数学家求教，大数学家在仔细地思考后认为这个数为17 位，则最小的一个真因子不会超过9位，于是他给国王出了一个主意：按自 然数的顺序给全国的老百姓每人编一个号发下去，等公主给出数目后，立 即将它们通报全国，让每个老百姓用自己的编号去除这个数，除尽了立即 上报，赏金万两。最后，国王用这个办法求婚成功。
– 当将一个问题分解到多个处理器上解决时，由于算法中不可避 免地存在必须串行执行的操作，从而大大地限制了并行计算机 系统的加速能力。
•设f为求解某个问题的计算存在的必须串行执行的操作占整 个最计大算 的的 加百 速分 能比 力，，则p为处理器的数目，Sp为并行计算机系统
设f=1%，p→，则Sp=100。（阿达尔定律） 串行执行操作仅占全部操作1%，解题速度最多也只能提高 一百倍。 对难解性问题而言，提高计算机系统的速度是远远不够的， 而降低算法复杂度的数量级才是最关键的问题。
读写头
状态 控制器 q
图灵在1936年提出了著名的图灵机模型(计算模型)： ▪图灵机由一个无限长的带子（被划分成均匀的方格） 、一个磁带读/写头 和一个有限状态控制器组成。 ▪在每一步计算中，图灵机从磁带上读出一个符号，并由有限状态控制器决 定是否在当前的磁带区上写入不同的符号，然后决定是否需要将磁带读/写 头向前或向后移动一位。 当前的计算机，在理论上都是可以被图灵机模拟的，其原理和图灵机是相同 的，甚至还包含了存储程序的思想。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
10
NP问题
意义：能够通过非确定性的多项式时间算法对许多对称密钥算法 和所有公钥算法进行攻击。
NP完全问题 ：指NP中的任何一个问题都可以通过多项式时间转 化为该问题 。NP完全问题的全体被记为NPC 。
NP Hard问题?
11
零知识证明
证明者能够在不向验证者提供任何有用的信息的情况下，使验证 者相信某个论断是正确的。
9
问题分类
易处理的（tractable） ：确定性图灵机上能够在多项式时间内得 到处理的问题。称易处理问题的全体为“多项式时间可解类”， 记为P。
非确定性图灵机上能够在多项式时间内得到处理的问题被称为 “非确定性多项式时间可解问题”，简称NP问题。NP问题的全体 被称为“非确定性多项式时间可解类”，记为NP。
实质上是一种涉及两方或更多方的协议，即两方或更多方完成一 项任务所需采取的一系列步骤。
12
零知识“洞穴”
13
零知识“洞穴”
（1）V站在A处； （2）P走进洞穴，到达C处或D处； （3）当P消失在洞穴中时，V走到B处； （4）V呼叫P，要求P：（a）从左通道出来；或者（b）从右通道出
来； （5）P答应V的呼叫，并在有必要的情况下用咒语打开C与D之间的
对于输入I和语言L，判断I∈L是否成立。 由于这一过程向验证者泄露了1b信息（即I∈L），所以基于GMR
模型的零知识证明并非真正的零知识证明。这种交互零知识证明 通常被称为“成员（或定理）的零知识证明（zero knowledge proofs of membership or theorem）。
非交互零知识证明 ：用一个短随机串代替交互过程并实现了零知 识证明 。 20世纪80年代末，Blum等人进一步提出 成员（或定理）的非交互零知识证明系统； 知识（或身份）的非交互零知识证明系统。
16
交互图灵机
交互图灵机指的是一个具有一条只读输入带、一条工作带、一条 随机带、一条只读通信带和一条只写通信带的图灵机。其中，随 机带上包含一条无限长的随机比特序列，并且只能从左向右读入。 “一个交互图灵机投一个硬币”指该图灵机从自己的随机带上读 取1bit。
好处： 使算法复杂性度量与处理器的运行速度和指令运行时 间无关； 明确地揭示了输入的数据长度对算法复杂性的影响。
6
算法复杂性
算法的分类及其运行时间
类别 常数
多项 线性 式
二次
三次
指数
复杂性
O(1) O(n) O(n2 ) O(n3 ) O(2n )
运算次数 n 106
1
时间 1微妙
106
1秒
秘密之门； （6）重复步骤（1）~（5）次。
14
基本的零知识协议过程
假设P知道一部分信息，并且该信息是一个难题的解法 ： （1）P用自己的信息和一个随机数将这个难题转变为与之同构的
新难题，然后用自己的信息和这个随机数这个新难题； （2）P利用位承诺方案提交对于这个新难题的解法； （3）P向V透漏这个新难题，V无法通过新难题得到关于原难题或
4
算法复杂性
即度量该算法所需的计算能力 ，包括： 时间复杂性T（time complexity）； 空间复杂性S（space complexity）； 随机位数目； 信道带宽； 数据总量； ……
5
O
算法复杂性
计算复杂性的表示符号为“ O ”（称为“大O ”），表示计算 复杂性的数量级
第3章 密码学的复杂性理论基础
1
密码技术和算法复杂性
计算复杂性 ：研究密码分析对于计算量的需求和密码分析的困难 程度 ，从而得出这些密码技术和算法在现有可行的条件下是否具 有足够的安全性： 算法复杂性； 问题复杂性。
密码协议、方案和体制的安全性证明：零知识证明理论。
2
问题（problem）
即需要回答的一般性提问: 它通常含有若干个参数。 对于一个问题进行描述应该包括两方面的内容：必须对问题 的所有给定参数给出一般性描述；必须描述该问题的答案 （或解）应该满足的性质。 当问题的所有参数都有了确定的取值时，我们称得到了该问 题的一个实例（instance）。
3
算法（algorithm）
17
交互协议
即满足以下两个条件的有序图灵机（A,B），其中，A具有无限的 计算能力，B具有多项式时间的计算能力： （a）A与B共享同一输入带； （b）B的只写通信带是A的只读通信带，同时，B的只读通信带是 A的只写通信带。
18
GMR模型
假设证明者具有无限的计算能力，并且验证者具有多项式时间的 计算能力。
19
FFS模型
假设证明者与验证者具有多项式时间的计算能力。 证明者向验证者证明的不是I∈L成立与否，而是证明自己知道输
入I关于语言L的状况。由于在这个证明过程中，验证者相信这个 证明，但是又无法得知任何信息（包括I∈L是否成立）。 基于FFS模型的零知识证明是真正的零知识证明。这种交互零知 识证明通常被称为“知识（或身份）的零知识证明（zero knowledge proofs of knowledge or identity）”。
其解法的任何信息； （4）V要求P：（a）证明新、旧难题同构；或者（b）公布P在
（2）中提交解法并证明该解法的确为新难题的解法； （5）P答应V的要求； （6）重复步骤（1）~（5）次。
15
交互与非交互
交互零知识证明 ：证明者和验证者之间必须进行交互 。由 Goldwasser等人在20世纪80年代初提出 GMR模型； FFS模型。
即求解某个问题的一系列具体步骤（通常被理解为求解所需的通 用计算程序）。 算法总是针对具体问题而言的，求解一个问题的算法通常不 止一个。 当某个算法能够回答一个问题的任何实例时，我们称该算法 能够回答这个问题。 当一个问题至少有一个能够回答该问题的算法时，我们称该 问题可解（resolvable），否则称该问题不可解 （unresolvable）。
1012 1018 10301,030
11.6天 32,000内在复杂性，即在图灵机上解决最难的问题实例所需 的最小时间和空间条件。
8
图灵机
实际可用的计算模型 。 确定性图灵机。 非确定性图灵机 ：能够进行猜测。求解一个问题分两个阶段：
猜测阶段和验证阶段。