公钥密码讲座.pdf

本科生课程

刘建伟

2010-10-14
第8讲：公钥密码技术（一）

公钥密码体制的基本概念
构造公钥密码的困难问题
–离散对数、整数分解、椭圆曲线、…
主要的几种公钥算法
–RSA公钥算法
–Diffie-Hellman密钥交换
–ElGamal公钥算法
–Rabin算法
–椭圆曲线公钥算法(ECC)
一、双钥密码体制的基本概念
1、公钥密码的历史

在对称密钥密码体制中，加密运算与解密运算
使用同样的密钥。但是，在公开的计算机网络
上安全地传送和保管密钥是一个严峻的问题。
1976年，Diffie和Hellman在奠基性论文“密码
学的新方向”中提出公开密钥密码体制的概念：
使密钥交换、管理容易，并可实现数字签名。
–NewDirectionsinCryptography,IEEEIT-22,1976
公钥密码体制的基础，是计算复杂度理论。
–单向函数/单向陷门函数
–计算上困难问题/NP完全问题
2、公钥密码学

WhitefieldDiffie，MartinHellman，《NewDirections
inCryptography》，1976。
公钥密码学的出现使大规模的安全通信得以实现–解
决了密钥分发问题；
公钥密码学还可用于另外一些应用：数字签名、防抵
赖等；
公钥密码体制的基本原理–陷门单向函数(trapdoor
one-wayfunction)
公钥密码是密码学历史上一个伟大的革命性成果。
3、理论基础——单向函数

定义1：令函数f是集A到集B的映射，用f:A→B表示。若

对于任意x1≠x2，x1,x2∈A，有f(x1)≠f(x2)，则称f为单射，
或1-1映射，或可逆的函数。
定义2：一个可逆函数f:A→B，若它满足：
(1)对所有x∈A，易于计算f(x)；
(()2)对“几乎所有x∈A”，由f(x)求x极为困难，以
至于几乎是不可能的，则称f是一个单向函数。
注意：定义中的“极为困难”是相对现有的计算机资源
和算法而言。
4、理论基础——陷门单向函数
定义3：陷门单向函数是一类满足下述条件的单向函数：

fz:Az→Bz，z∈Z，Z是陷门信息集合。

(1)对所有z∈Z，在给定z下容易找到一对算法Ez和Dz，使对
所有x∈A，易于计算fz及其逆，即：

fz(x)Ez(x)

Dz(fz(x))x

(2)对所有z∈Z，当只给定Ez和Dz时，对所有x∈A，“很难
”从y=fz(x)计算出x。
区别：单向函数是求逆困难的函数，而陷门单向函数
(trapdooronewayfunction)是在不知道陷门信息下求逆困
难的函数。当知道陷门信息后，求逆易于实现。
5、用于构造双钥密码的单向函数

1.多项式求根
2.离散对数DL(DiscreteLogarithm)
3.大整数分解FAC(FactorizationProblem)
4.背背问题包问题((pKnapsackproblem)
5.Diffie-Hellman问题DHP
6.二次剩余问题QR(QuadraticResidue)
7.模n的平方根问题(SQROOT)
公钥密码体制的原理
公钥密码技术，又称非对称密码技术或双钥密码
技术（Public-key/Two-key/Asymmetric），其加密
和解密数据使用不同的密钥。

不同

abc#@&abc

加密器解密器
明文密文明文
公钥密钥体制的密钥管理

公钥密钥体制解决了密钥的发布和管理问题，通
信双方可以公开其公开密钥，而保留私有密钥。

发送方可以用人人皆知的接受方公开密钥对发送
的信息进行加密，安全的传送给该接受方，然后
由接受方用自己的私有密钥进行解密。
公钥密码体制的特点
包括两个密钥：
–公开密钥(public-key)，可以被任何人知道，用于加密
或验证签名
–私钥(private-key)，只能被消息的接收者或签名者知
道，用于解密或签名
由私钥及其他密码信息容易计算出公开密钥；
而由公钥及算法描述，计算私钥却非常困难。
公钥加密方案
公钥算法的用途
用于公公分发钥分发（Public-KeyDistributionSchemes—PKDS）
–用于交换秘密信息，常用于交换对称加密算法的密钥
用于公钥加密((yypPublicKeyEncryption—PKE)
–用于加密任何消息
–任何人可以用公钥加密，私钥的拥有者可以解密
–任何公钥加密方案能够用于密钥分配方案PKDS
–许多公钥加密方案也是数字签名方案
用于数字签名（SignatureSchemes）
–用于生成对某消息的数字签名
–私钥的拥有者生成数字签名
–任何人可以用公钥验证签名
公钥的安全性

依赖于数学上足够大的困难性。
类似