第5章[第2部分]公钥密码及背包公钥密码算法
- 格式：ppt
- 大小：106.50 KB
- 文档页数：14
下载文档原格式
合集下载
密码学第五章 公钥密码 5.4 椭圆曲线公钥密码体制
2、椭圆曲线公钥密码算法
1）参数选取
选取有限域 F 上的椭圆曲线
E : y2 x3 ax b
和其上一个阶为素数 n 的点 P = ( xP，yP )。 在[1，n-1]内随机选取整数 d，计算Q = dP
用户公钥：点 Q 用户私钥：整数 d
三、椭圆曲线公钥密码体制
2）加脱密算法
加密： 用户A给用户B发送信息 m，m F
ECC标准：ANSI X9.62、IEEE P1363等。
二、有限域上的椭圆曲线
椭圆曲线指的是由Weierstrass方程
y2 a1xy a3 y x3 a2 x2 a4 x a6
所确定的曲线。
先从 y2 x3 ax c 来探讨椭圆曲线的图像。
二、有限域上的椭圆曲线
实数域 R 上的椭圆曲线 y2 x3 ax b
三、椭圆曲线公钥密码体制
1、安全性基础
定义3 设 E 是有限域 F 上的椭圆曲线，G 是 E 的一个循环子群，点 P 是 G 的一个生成元，即
G = { kP : k 1}，在已知 P， Q 的条件下，求解
整数n，使得 nP = Q 的问题，称为椭圆曲线 E 上 的离散对数问题。
三、椭圆曲线公钥密码体制
R=2P
x R’
二、有限域上的椭圆曲线
2、椭圆曲线上的加法运算
y
当P与Q关于x轴对称时,
P
定义P与Q的和为O ,即
P+Q=O
x
并称 O 为无穷远点
Q
二、有限域上的椭圆曲线
可以证明，有限域上的椭圆曲线在我们定义 的加法运算下构成群。
既然构成群，就必然有零元和负元，这里的 零元就为无穷远点O，P的负元就是它关于x轴的对
例：F23上的一个椭圆曲线为y2 = x3 + x ，
1）参数选取
选取有限域 F 上的椭圆曲线
E : y2 x3 ax b
和其上一个阶为素数 n 的点 P = ( xP，yP )。 在[1，n-1]内随机选取整数 d，计算Q = dP
用户公钥：点 Q 用户私钥：整数 d
三、椭圆曲线公钥密码体制
2）加脱密算法
加密： 用户A给用户B发送信息 m，m F
ECC标准：ANSI X9.62、IEEE P1363等。
二、有限域上的椭圆曲线
椭圆曲线指的是由Weierstrass方程
y2 a1xy a3 y x3 a2 x2 a4 x a6
所确定的曲线。
先从 y2 x3 ax c 来探讨椭圆曲线的图像。
二、有限域上的椭圆曲线
实数域 R 上的椭圆曲线 y2 x3 ax b
三、椭圆曲线公钥密码体制
1、安全性基础
定义3 设 E 是有限域 F 上的椭圆曲线，G 是 E 的一个循环子群，点 P 是 G 的一个生成元，即
G = { kP : k 1}，在已知 P， Q 的条件下，求解
整数n，使得 nP = Q 的问题，称为椭圆曲线 E 上 的离散对数问题。
三、椭圆曲线公钥密码体制
R=2P
x R’
二、有限域上的椭圆曲线
2、椭圆曲线上的加法运算
y
当P与Q关于x轴对称时,
P
定义P与Q的和为O ,即
P+Q=O
x
并称 O 为无穷远点
Q
二、有限域上的椭圆曲线
可以证明，有限域上的椭圆曲线在我们定义 的加法运算下构成群。
既然构成群，就必然有零元和负元，这里的 零元就为无穷远点O，P的负元就是它关于x轴的对
例：F23上的一个椭圆曲线为y2 = x3 + x ，
公钥密码算法
公钥密码算法
公钥密码算法是一种非对称加密算法，它使用一对公钥和私钥来加密和解密信息。
公钥密码算法的基本原理是：用户A将
要发送的信息使用用户B的公钥进行加密，然后发送给用户B，用户B收到信息后，使用自己的私钥进行解密，从而获得
原始信息。
公钥密码算法的安全性主要取决于公钥和私钥的安全性，因此，在使用公钥密码算法之前，需要先生成公钥和私钥。
一般来说，生成公钥和私钥的过程可以分为以下几个步骤：
1. 选择一个大质数p和一个小质数q，并计算出n=pq；
2. 选择一个大于1小于n的整数e，使得e与(p-1)(q-1)互质；
3. 计算出d，使得ed=1 mod (p-1)(q-1)；
4. 将公钥(n,e)和私钥(n,d)发布出去。
在使用公钥密码算法进行加密时，可以使用以下步骤：
1. 将要发送的信息m转换成一个整数M，使得0<M<n；
2. 计算出密文C，C=M^e mod n；
3. 将密文C发送给接收方。
在使用公钥密码算法进行解密时，可以使用以下步骤：
1. 接收方收到密文C后，计算出明文M，M=C^d mod n；
2. 将明文M转换成原始信息m。
公钥密码算法的安全性取决于公钥和私钥的安全性，因此，在使用公钥密码算法时，应该采取有效的措施来保护公钥和私钥，以防止被攻击者破解。
例如，可以采用数字签名技术来验证公钥和私钥的真实性，以及采用加密技术来保护公钥和私钥，以防止被攻击者窃取。
《应用编码与计算机密码学》 第5章 公钥密码体制
5.3 基于离散对数的公钥密码体制
5.3.2 离散对数Diffie-Hellman算法 设p是一个满足要求的大素数，0 < α < p, α是循环群Z p的生成元，α和p公开，它 们也将在一组用户中共用。 在两个用户Alice与Bob要通信时，他们可 通过下面的步骤协商通信时所使用的密钥：
5.3 基于离散对数的公钥密码体制
while r > 0
5.2 RSA 公钥密码体制
if b0 ≠ 1 then b 没有模a的逆 else return(t)
5.2 RSA 公钥密码体制
中国剩余定理及欧拉定理 定理 5.2.2(中国剩余定理)假设m1 ,…, mr是 两两互素的正整数，a1 ,…, ar为整数。那么 同余方程组 x ≡ ai ( mod mi ) (1≤ i ≤ m) 有模M = m1 m2 … , m 的唯一解，具体解表 r r 达式为 x = ∑ a i M i y i mod M i =1 −1 M 其中 M i = ，且 yi = Mi modmi ,1 ≤ i ≤ r。 mi
5.2 RSA 公钥密码体制
算法5.2.3 Multiplication Inverse(a , b)
a0 ← a b0 ← b t0 ← 0
t←1
5.2 RSA 公钥密码体制
⎧ temp ← ( t 0 − qt ⎪ ← t t 0 ⎪ ⎪ t ← temp ⎪ ⎪ a 0 ← b0 do ⎨ b0 ← r ⎪ ⎪ ⎢ a0 ⎥ ⎪ q← ⎢ ⎥ ⎪ ⎣ b0 ⎦ ⎪ ⎩ r ← a 0 − qb 0
5.2 RSA 公钥密码体制
算法5.2.1 Euclidean Algorithm(a ,b) r0 ←a ⎧ ⎢ rm − 1 ⎥ qm ← ⎢ r1 ←b ⎪ ⎥ rm ⎦ ⎣ ⎪ m ←1 ⎪ while rm ≠ 0 do ⎨ rm + 1 ← rm −1 − q m rm m ←m - 1 ⎪ m ← m +1 ⎪ return ( q1,…, qm, rm ) ⎪(a,b) Comment ： rm = gcd ⎩
密码学中的公钥密码算法及其应用
密码学中的公钥密码算法及其应用密码学是一门研究通信安全和信息保密的科学，而公钥密码学算法则是其中最为重要的一种算法。
公钥密码学算法是指在加密和解密过程中，使用不同的密钥来实现。
本文将介绍公钥密码学算法的基本概念和应用。
一、公钥密码学算法概述公钥密码学算法也称为非对称密码学算法，它是一种使用两个密钥来进行加密和解密的算法。
这两个密钥是一对，一个称为公钥，一个称为私钥。
其中，公钥是公开的，任何人都可以知道，私钥则是秘密的，只有拥有者才会知道。
公钥密码学算法的加密过程是这样的：发送方使用接收方的公钥对数据进行加密，接收方使用自己的私钥对加密数据进行解密。
这样，就可以保证通信内容的安全性和保密性。
二、公钥密码学算法的分类公钥密码学算法分为两种类型：基于离散对数问题的算法和基于椭圆曲线问题的算法。
1、基于离散对数问题的算法基于离散对数问题的算法包括RSA和DH两种算法。
RSA算法是由三位数学家Rivest、Shamir和Adleman于1977年发明的。
它主要是利用了大数分解的难度来保证信息的安全性，而公钥就是由两个大素数的乘积得出的。
DH算法是Diffie和Hellman在1976年提出来的，它主要是利用数论中离散对数问题的难度来保证信息的安全性，而公钥则是通过一定计算得出的。
2、基于椭圆曲线问题的算法基于椭圆曲线问题的算法包括ECIES和ECDSA两种算法。
ECIES算法是可扩展加密标准中的一种，它主要是利用椭圆曲线上的点运算来实现加密和解密，公钥就是椭圆曲线上的一个点。
ECDSA算法是可扩展数字签名算法中的一种，它主要是利用椭圆曲线上的点运算来实现数字签名的生成和验证。
三、公钥密码学算法的应用公钥密码学算法在信息安全领域有着广泛的应用，下面介绍几个常见的应用场景。
1、TLS/SSL协议TLS/SSL协议是一种用于保护互联网通信安全的协议。
在TLS/SSL协议中，使用公钥密码学算法来实现通信内容加密和身份认证的过程，从而保证通信的安全性和保密性。
大连理工大学网络安全与密码学 chap5-公钥密码
基于背包问题的公钥密码系统 ——MH公钥算法
• 加密 – 将明文分为长度为n的块X=(x1,…,xn) – 然后用公钥A ' = (a1 ', …, an ')，将明文变为密文 S = E(X) = ∑ai ' xi
• 解密 – 先计算S ' = w-1S mod m – 再求解简单背包问题 S ' = ∑aixi
Eaxmple-从私钥计算公钥
• 私钥{2,3,6,13,27,52} • N=31, m=105 2*31 mod 105= 62 3*31 mod 105=93 6*31 mod 105=81 13*31 mod 105= 88 27*31 mod 105=102 52*31 mod 105= 37 • 公钥{62,93,81,88,102,37}
• 涉及到各方：发送方、接收方、攻击者 • 涉及到数据：公钥、私钥、明文、密文 • 公钥算法的条件： – 产生一对密钥是计算可行的 – 已知公钥和明文，产生密文是计算可行的 – 接收方利用私钥来解密密文是计算可行的 – 对于攻击者，利用公钥来推断私钥是计算不可行的 – 已知公钥和密文，恢复明文是计算不可行的 – (可选)加密和解密的顺序可交换
公钥密码
一般要求： 1、加密解密算法相同，但使用不同 的密钥 2、发送方拥有加密或解密密钥，而 接收方拥有另一个密钥 安全性要求： 1、两个密钥之一必须保密 2、无解密密钥，解密不可行 3、知道算法和其中一个密钥以及若 干密文不能确定另一个密钥
对公钥密码算法的误解
• 公开密钥算法比对称密钥密码算法更安全？ – 任何一种算法都依赖于密钥长度、破译密码的工 作量，从抗分析角度，没有一方更优越 • 公开密钥算法使对称密钥成为过时了的技术？ – 公开密钥很慢，只能用在密钥管理和数字签名， 对称密钥密码算法将长期存在 • 使用公开密钥加密，密钥分配变得非常简单？ – 事实上的密钥分配既不简单，也不有效
公钥密码体制及典型算法课件
基于数学难题 • 标志性文献
W.Diffie and M.E.Hellman, New Directions in Cryptography, IEEE Transaction on Information Theory, V.IT-22.No.6, Nov 1976, PP.644-654
学习交流PPT
在计算上是容易的。 ② 发方A用收方的公开钥对消息m加密以产生密
文c，即c=EPKB[m] 在计算上是容易的。
③ 收方B用自己的秘密钥对c解密，即m=DSKB[c] 在计算上是容易的。
学习交流PPT
25
公钥密码算法应满足的要求
④ 敌手由B的公开钥PKB求秘密钥SKB在计算上是不 可行的。
⑤ 敌手由密文c和B的公开钥PKB恢复明文m在计算 上是不可行的。
• 密钥分配问题不是一个容易的问题(the key distribution problem )
学习交流PPT
6
公钥算法分类
• Public-Key Distribution Schemes (PKDS，公钥分配系统)
• 用于交换秘密信息(依赖于双方主体) • 常用于对称加密算法的密钥
• Public Key Encryption (PKE，公钥加密)
学习交流PPT
15
公钥密码体制的原理
• ③ A要想向B发送消息m，则使用B的公开钥加密m， 表示为c=EPKB[m],其中c是密文，E是加密算法。
• ④ B收到密文c后，用自己的秘密钥SKB解密，表示 为m=DSKB[c]，其中D是解密算法。
学习交流PPT
16
公钥密码体制认证框图
学习交流PPT
17
学习交流PPT
13
W.Diffie and M.E.Hellman, New Directions in Cryptography, IEEE Transaction on Information Theory, V.IT-22.No.6, Nov 1976, PP.644-654
学习交流PPT
在计算上是容易的。 ② 发方A用收方的公开钥对消息m加密以产生密
文c，即c=EPKB[m] 在计算上是容易的。
③ 收方B用自己的秘密钥对c解密，即m=DSKB[c] 在计算上是容易的。
学习交流PPT
25
公钥密码算法应满足的要求
④ 敌手由B的公开钥PKB求秘密钥SKB在计算上是不 可行的。
⑤ 敌手由密文c和B的公开钥PKB恢复明文m在计算 上是不可行的。
• 密钥分配问题不是一个容易的问题(the key distribution problem )
学习交流PPT
6
公钥算法分类
• Public-Key Distribution Schemes (PKDS，公钥分配系统)
• 用于交换秘密信息(依赖于双方主体) • 常用于对称加密算法的密钥
• Public Key Encryption (PKE，公钥加密)
学习交流PPT
15
公钥密码体制的原理
• ③ A要想向B发送消息m，则使用B的公开钥加密m， 表示为c=EPKB[m],其中c是密文，E是加密算法。
• ④ B收到密文c后，用自己的秘密钥SKB解密，表示 为m=DSKB[c]，其中D是解密算法。
学习交流PPT
16
公钥密码体制认证框图
学习交流PPT
17
学习交流PPT
13
chapter 5 公钥密码体制(ro)
• • • 线性筛选法 高斯整数法 数域筛选法
3. 计算离散对数不因数分解有着密切的关系，如果能成功解 决离散对数问题，则也能解决因子分解问题。（注：其逆命 题的正确性还有待证明）
主要内容
• • • • • • • 问题提出与公钥密码基本概念 公钥密码基本应用 陷门单向函数 RSA密码体制 DH密钥交换算法 离散对数密码体制 椭圆曲线密码体制
群
• 群的概念
– 是由一个非空集合G组成，在集合G中定义了一个二元运算符“· ”， – 并满足以下性质的代数系统，记为｛G, ·｝
离散对数问题
1. 设p是一大素数，a ＜ p，已知x，求解ax (mod p)的模指数 运 算比较容易。模指数运算的逆问题是找出某个数的离散对 数，即：已知y, a以及大素数p ，求x使得：ax = y (mod p)。 2. 在素数域中有三种计算离散对数的方法：
陷门单向函数
定义 陷门单向函数是一类满足下述条件的单向函数： (1) 正向计算容易。若已知Pk和消息x， y=f Pk(x) (2) 在不知密钥Sk (Sk是陷门信息)的情况下， 反向计算是不可行的。
(3) 在已知密钥Sk的情况下，反向计算是容易的。 即 x=f -1Sk(y)
（3） 公钥系统
在一个公钥系统中，所有用户共同选定一个陷门单 向函数，加密运算E。用户i从陷门集中选定zi，并 公开Ezi。
–传统加密算法无法实现抗抵赖的需求
公钥密码体制
• 公钥密码又称为双钥密码、非对称密码 • 公钥密码体制提出的标志性文献：
– W.Diffie and M.E.Hellman, New Directions in Cryptography, IEEE Transaction on Information Theory, V.IT-22.No.6, Nov 1976, PP.644-654
3. 计算离散对数不因数分解有着密切的关系，如果能成功解 决离散对数问题，则也能解决因子分解问题。（注：其逆命 题的正确性还有待证明）
主要内容
• • • • • • • 问题提出与公钥密码基本概念 公钥密码基本应用 陷门单向函数 RSA密码体制 DH密钥交换算法 离散对数密码体制 椭圆曲线密码体制
群
• 群的概念
– 是由一个非空集合G组成，在集合G中定义了一个二元运算符“· ”， – 并满足以下性质的代数系统，记为｛G, ·｝
离散对数问题
1. 设p是一大素数，a ＜ p，已知x，求解ax (mod p)的模指数 运 算比较容易。模指数运算的逆问题是找出某个数的离散对 数，即：已知y, a以及大素数p ，求x使得：ax = y (mod p)。 2. 在素数域中有三种计算离散对数的方法：
陷门单向函数
定义 陷门单向函数是一类满足下述条件的单向函数： (1) 正向计算容易。若已知Pk和消息x， y=f Pk(x) (2) 在不知密钥Sk (Sk是陷门信息)的情况下， 反向计算是不可行的。
(3) 在已知密钥Sk的情况下，反向计算是容易的。 即 x=f -1Sk(y)
（3） 公钥系统
在一个公钥系统中，所有用户共同选定一个陷门单 向函数，加密运算E。用户i从陷门集中选定zi，并 公开Ezi。
–传统加密算法无法实现抗抵赖的需求
公钥密码体制
• 公钥密码又称为双钥密码、非对称密码 • 公钥密码体制提出的标志性文献：
– W.Diffie and M.E.Hellman, New Directions in Cryptography, IEEE Transaction on Information Theory, V.IT-22.No.6, Nov 1976, PP.644-654
05_密码学基础(四)_公开密钥密码算法
密钥分配
使用对称密码算法 保密通信双方需共享密钥：A&B，B&C，C&A N个用户集需要N(N-1)/2个共享密钥 共享密钥需要经常更换，更换方式有
A选择密钥并手工传递给B 第三方C选择密钥分别手工传递给A,B 用A,B原有共享密钥传送新密钥 与A,B分别有共享密钥的第三方C传送新密钥给A和/ 或B
数论简介
欧拉定理 表述1： 将Z/(n）表示为 Zn，其中n=pq; p,q为素数且相异。 若Z*n={g∈ Zn|gcd(g,n)=1}，易见Z*n为(n)阶的乘 法群，且有 g(n)1(mod n)，而 (n)=(p-1)(q-1)。 表述2： 若整数g和n互素，则g(n) ≡1(mod n)；其中(n)为比 n小，但与n互素的正整数个数, 称为(n)的欧拉函数 表述3： 给定两个素数p和q，以及两个整数m、n，使得n=pq ，且0<m<n，对于任意整数k下列关系成立，
公钥密码学的历史
76年Diffie和Hellman发表了“密码学的新方向 ”，奠定了公钥密码学的基础 公钥技术是二十世纪最伟大的思想之一
改变了密钥分发的方式 可以广泛用于数字签名和身份认证服务
78年，RSA算法 PKI
公钥加密模型
公开密钥的加密
公开密钥密码的重要特性 加密与解密由不同的密钥完成 加密: X –>Y：Y = EKU(X) 解密: Y –>X: X = DKR(Y) = DKR(EKU(X)) 知道加密算法，从加密密钥得到解密密钥在计算上是 不可行的； 两个密钥中任何一个都可以用作加密而另一个用作解 密 X = DKR(EKU(X)) = EKU(DKR(X))
公钥密码算法举例
公钥密码算法举例公钥密码算法是一种基于不同密钥的加密技术，它与对称加密算法不同，后者使用相同的密钥来加密和解密数据。
因此，公钥密码算法也被称为非对称加密算法。
该算法中，加密和解密使用不同的密钥，其中一个被公开，称为公钥；另一个则称为私钥，仅保留在接收方手中。
由于私钥保密，因此即使公钥泄露，攻击者也无法解密数据。
公钥算法有许多的应用，比如加密电子邮件、文件传输和安全联网等方面。
公钥密码算法最重要的特点之一是数字签名。
在这个过程中，发送方使用其私钥生成一些数据，并将其公开给接收方。
接收方使用发送方的公钥验证数字签名的完整性，以确保发送方发送的数据未被篡改或替换。
因此，公钥密码算法可以为数字交流提供安全保障。
以下是一些最常见的公钥算法：RSA：RSA（Rivest-Shamir-Adleman）算法是最早公开的基于公钥的加密技术之一。
它是非对称加密的典型代表，可以用于加密大量数据。
该算法的安全基于大数分解问题，即寻找两个大素数的积的唯一分解。
举个例子，假设我想向我的同事发送一份敏感数据，使用RSA加密，并将其发送给他们。
首先，我会产生一对公钥和私钥。
然后，我将我的公钥发给我的同事，他们用这个公钥来加密数据。
接着，我使用我的私钥来解密数据。
这种方式确保了数据的安全性，因为即使公钥被泄露，也无法使用该密钥解密数据。
ECDSA：椭圆曲线数字签名算法（ECDSA）是一个数字签名协议，使用椭圆曲线的离散对数问题，利用数字签名来验证信息的完整性和真实性。
该算法是非对称加密的另一个代表。
相比RSA，它需要更少的计算能力和存储空间，同时提供了类似的安全性。
以支付应用为例，电子钱包通常使用ECDSA来验证支付交易的身份和总额。
由于支付交易通常是高安全性的，因此ECDSA成为了安全支付的一种重要方式。
总之，公钥密码算法是一种重要的加密技术，用于保护密码、交易和数字通信。
它提供了一种高度安全和可信的方式，使得敏感数据可以安全地传输和存储。
公钥密码系统及RSA公钥算法
公钥密码系统及RSA公钥算法公钥密码系统及RSA公钥算法07301910 张云霖随着电脑连网的逐步实现，Internet前景越来越美好，全球经济发展正在进入信息经济时代，知识经济初见端倪。
电脑信息的保密问题显得越来越重要，无论是个人信息通信还是电子商务发展，都迫切需要确保Internet网上信息传输的安全，需要确保信息安全。
信息安全技术是一门综合学科，他涉及信息论、电脑科学和密码学等多方面知识，他的主要任务是研究电脑系统和通信网络内信息的保护方法以实现系统内信息的安全、保密、真实和完整。
其中，信息安全的核心是密码技术。
密码技术是集数学、电脑科学、电子和通信等诸多学科于一身的交叉学科。
他不但能够确保机密性信息的加密，而且能够实现数字签名、身份验证、系统安全等功能。
是现代化发展的重要科学之一。
本文将对公钥密码系统及该系统中现在最广泛流行的RSA 算法做一些简单介绍。
公钥密码体制，突破性地解决了困扰着无数科学家的密钥分发问题，事实上，在这种体制中，人们甚至不用分发需要严格保密的密钥，这次突破同时也被认为是密码史上两千年来自单码替代密码发明以后最伟大的成就。
这一全新的思想是本世纪70年代，美国斯坦福大学的两名学者Diffie和Hellman提出的，该体制和单钥密码最大的不同是：在公钥密码系统中，加密和解密使用的是不同的密钥（相对于对称密钥，人们把他叫做非对称密钥），这两个密钥之间存在着相互依存关系：即用其中任一个密钥加密的信息只能用另一个密钥进行解密。
这使得通信双方无需事先交换密钥就可进行保密通信。
其中加密密钥和算法是对外公开的，人人都能够通过这个密钥加密文档然后发给收信者，这个加密密钥又称为公钥；而收信者收到加密文档后,他能够使用他的解密密钥解密，这个密钥是由他自己私人掌管的，并无需分发，因此又成称为私钥，这就解决了密钥分发的问题。
当前最著名、应用最广泛的公钥系统RSA是在1978年，由美国麻省理工学院(MIT)的Rivest、Shamir和Adleman在题为《获得数字签名和公开钥密码系统的方法》的论文中提出的。