CHD7公开密钥密码系统

公开密钥密码系统

(Public-KeyCryptosystems)2本章内容7.1 公开密钥的基本概念7.2 RSA公开密钥密码机制7.3 ElGamal的公开密钥密码系统7.4 椭圆曲线密码系统7.5 混合式的加密机制7.6 机密分享7.7 量子密码学7.8 密码系统的评估37.1公开密钥的基本概念对称式密码系统有密钥的管理问题，例如要与N个人做秘密通讯，那么就必须握有N把秘密密钥为了改善对称式密码系统问题，于是便有公开密钥密码系统(Public-KeyCryptosystems)的产生4秘密密钥密码系统5秘密密钥密码系统秘密密钥密码系统(Secret-KeyCryptosystems)又称单密钥密码系统(One-KeyCryptosystems)也称对称密码系统(SymmetricCryptosystems)优点：加解密速度快缺点：有密钥管理的问题每位使用者需储存n-1把Keys

U1U2U5U3U467.1.1公开密钥加解密基本概念公开密钥密码系统(Public-KeyCryptosystems)又称双密钥密码系统(Two-KeyCryptosystems)也称非对称式密码系统(AsymmetricCryptosystems)7公开密钥加解密系统87.1.2数字签章的基本概念一般数字签章具有下列功能：验证性(Authentication)：可验证文件来源的合法性，而非经他人伪造。完整性(Integrity)：可确保文件内容不会被新增或篡改。不可否认性(Non-repudiation)：签章者事后无法否认曾签署过此文件。9数字签章的基本概念107.2

RSA公开密钥密码机制非对称式密码系统的一种。1978年美国麻省理工学院三位教授Rivest、Shamir及Adleman(RSA)所发展出来的。利用公开密钥密码系统作为数据加密的方式，可达到数据加密及数字签署的功能。Encryption:RSA加密算法，明文加密使用区块为每次加密的范围，使用对方公开密钥(PublicKey)将明文加密。Decryption:RSA解密算法，必须使用自己的私有金钥(PrivateKey)才能将密文解出。11RSA算法1.选两个大质数p和q

(至少100位数)，令N=p•q2.再计算Ø(N)=(p-1)(q-1)，并选一个与Ø(N)互质数eØ(N)为Euler’sTotient函数，其意为与N互质之个数3.(e,N)即为公开密钥

加密法为C=MemodN4.选一个数d，满足e•dmodØ(N)=15.d即为解密密钥(亦称私有密钥或秘密密钥)

解密法为M=CdmodNRSA之安全性取决于质因子分解之困难度要将很大的N因子分解成P跟Q之相乘，是很困难的12RSA算法例子1.接收方选p=3，q=11;此时N=p•q=332.找出1个与(p-1)x(q-1)=(3-1)(11-1)=2x10=20

互质数e=33. (e,N)=(3,33)即为接收方的公开密钥4.接收方选一个数d=7当作解密密钥， 满足e•d1mod20(7x31mod20)

令明文M=19

加密:C=MemodN=193mod33=28

解密:M=CdmodN=287mod33=1913相关的数学理论Ifpisaprime,andaisnotamultipleofp,thenFermat’slittletheoremsaysap-1modp=1

Ex.26mod7=1

费玛(Fermat)定理:若p为质数且(a,p)互质，则ap-1modp=1Fermat’sLittleTheorem14尤拉定理Ifgcd(a,n)=1,then

where()calledEulerphifunction.Euler定理:若a，n互质，则aØ(n)modn=1尤拉函数:Ø(P)=P-1若P为质数Ø(N)=Ø(PQ)=Ø(P)Ø(Q)=(P-1)(Q-1)Itisthenumberofpositiveintegerslessthannthatarerelativelyprimeton.

Ifnisaprime,(n)=n-1.Ifn=pq,wherepandqareprime,then(n)=(p-1)(q-1)Euler’sTheorem15模数系下的乘法反元素问题

找到一数x使得

(a×x)=1

x的解为x=a-1

一般的乘法反元素问题

找到一数x使得

1=(a×x)modN

x的解为x=a-1modN模数系的乘法反元素问题16若a与N互质，则x=a-1modn有唯一解若a与N不互质，则x=a-1modn无解例如：

5模14的乘法反元素为3，但2模14的乘法反元素就不存在。这也就是为何在RSA密码系统中，使用者所选择的公开密钥e必须与Ø(N)互质的原因。一般来说有两种方法可以用来解乘法反元素的问题-利用尤拉定理-利用扩展欧几理德算法ModularInverseProblem模数系下的乘法反元素问题(续)17如何找到模数系下的乘法反元素方法一：利用尤拉定理(Euler’sTheorem)

x=a-1modna×xmodn=1

x=a(n)-1modn理由是依据尤拉定理：Ifgcd(a,n)=1,thena(n)

modn=1例如：5模7的乘法反元素如何求得?56-1

mod7=55

mod7=3where(n)=6Note:若n为质数，则(n)可以很轻易求得；但若n为一很大的非质数，则要求的(n)相当于解质因子分解的困难度

18方法2：扩展欧几理德算法(ExtendedEuclideanAlgorithm)欧几理德算法(EuclideanAlgorithm)常被用在解最大公因子的问题上Findgcd(a,n)Letr0=n,r1=a,wegetr0=r1g1+r2

,r1=r2g2+r3,...,rj-2=rj-1gj-1+rj,...,rm-4=rm-3gm-3+rm-2,rm-3=rm-2gm-2+rm-1,rm-2=rm-1gm-1+rm,rm-1=rmgm

如何找到模数系下的乘法反元素(续)19根据扩展欧几理德算法，若a与n两数互质，一定可以找到两个整数s与t，使得

gcd(a,n)=sa+tn=1.其作法如下：Ifgcd(a,n)=1,wegetsa+tn=1.Wecanfindsandtbyusing

rm=gcd(a,n)=rm-2-rm-1gm-1becauserm-1=rm-3–rm-2gm-2sogcd(a,n)=rm-2-(rm-3–rm-2gm-2)gm-1=(1+gm-1gm-2)rm-2–gm-1rm-3

andsoon.sa+tn=1sa+tnmodn=1samodn=1

s=a-1modn如何找到模数系下的乘法反元素(续)20RSA密码系统的正确性C=E(M)=MemodnM=D(C)=CdmodnCd=(Me)d=Medmodnsinceed=1mod(p-1)(q-1)soMed=Ma(p-1)(q-1)+1=MMa(p-1)(q-1)=MMa(n)

modn根据尤拉定理(Euler’sTheorem)，得到M

×

1=M

21因式分解的问题FactoringProblem

FactoringanumbermeansfindingitsprimenumberEx:10=2×5;60=2

×2×3×5但是解一个大数的值因子分解问题是很困难的。请试着分解:

3337RSA的安全性便是植基于解因式分解的难题上22RSA算法指数运算：计算x=ABmodN?a1:=A;b1:=B;x:=1;whileb1

0dobeginwhileb1mod2=0dobeginb1:=b1div2;a1:=(a1

×a1)modN;end

b1:=b1-1;x:=(x×a1)modNend

计算x

=A17modN=A10001modN=A•(((A2)2)2)2

计算x=A13modN=A1101modN=A•((A2)2)•((A2)2)2

计算x=A7modN=A111modN=A•(A2)•(A2)2

23Public-KeyCryptosystems之特性1.D(d,E(e,M))=M，可还原性2.d和e很容易求得3.若公开(e,n)，别人很难从(e,n)求得d，即只有自己知道如何解密(以e加密)4.E(e,D(d,M))=MPublic-keyCryptosystems一定要能忍受Chosen-PlaintextAttack24Public-KeyCryptosystems之特性(续)．满足1~3项称之为trap-doorone-wayfunction．“one-way”因易加密而不易解密．“trap-door”若知一些特别信息即可解密．满足1~4项称之为trap-doorone-waypermutation．1~3项为public-keycryptosystems之要求．若同时满足第4项要求，则该保密法可用来制作数字签章。25RSA数位签章S=Md张modN张

M=?Se张modN张张丰使用自己的秘密密钥对文件M

做数位签章S张丰李良李良使用张丰的公开密钥确认数字签章及文件传送M及S一般使用时会先将文件M作HASH函数处理，使得HASH(M)比N小26数位签章法MHE||MHD比较是否相等SKaPKaESKa[H(M)]为M之签章DPKa[ESKa[H(M)]]=H(M)512位27RSA数位签章+加密C=(Md张modN张)e李modN李M=(Cd李modN李)e张modN张

张丰对文件M做数位签章后用李良的公用密钥将签章加密张丰李良李良使用私有密钥解开密文C再用张丰的公开密钥确认数字签章传送密文C28非对称式密码系统的一种。1985年由ElGamal所发展出来的。安全性导因于离散对数(DiscreteLogarithm)之困难度。相同明文可得到不相同的密文。RSA密码系统则是相同明文得到相同密文。

7.3ElGamal的公开密钥密码系统离散对数(DiscreteLogarithm)的问题：若p为很大之质数；g为p之原根(primitiveroot)y=gxmodp虽已知y,g,p，但要导出x值是很困难的29

什么是原根？原根generators:ifpisaprime,andgislessthanp,thengisageneratormodpifforeachbfrom1top-1,thereexistssomeawherega

b(modp).galsocalledprimitiverootofmodp

21mod11=222mod11=423mod11=824mod11=525mod11=1026mod11=927mod11=728mod11=329mod11=6210mod11=12isageneratormodulo11Ex:3不是模11下的一个原根，因为3amod11=2中，a为无解30解离散对数的问题已知a、b与n三数，要找到一个数x，使得x满足

axmodn=b是一个很难解的问题。Ex.If3xmod17=15,thenx=6

Note:并非所有离散对数的问题均有解Ex.3xmod13=7,nosolution!!31张丰将明文M以李良之公开密钥加密：1.张丰选一个随机数r2.计算b=grModPc=M•yrmodP张丰送(b,c)给李良4.李良收到(b,c)后计算c•(bx)-1modP=M7.3.1ElGamal的加解密机制李良之密钥产生：y=gxmodPy为李良之公开密钥x为李良之秘密密钥P为很大之质数g为与P互质之原根32李良将明文M以李良之秘密密钥制作签章：1.李良选一个随机数k使得gcd(k,p-1)=12.计算r=gkmodp3.李良计算s使得M=(xr+ks)mod(p-1)4.李良送(M,r,s)给验证者(张丰)5.M,r,s)后验证gM=yrrsmodP上式若相等表示M确定为李良所签署7.3.2ElGamal的数位签章机制李良之密钥产生：

y=gxmodPy为李良之公开密钥x为李良之秘密密钥P为很大之质数g为与P互质之原根33

7.4椭圆曲线密码系统RSA或ElGamal密码系统最为人诟病的问题就是在加解密或是签章的时候需要庞大的运算量，所以需要较长的运算时间。为了改善其效率（较少之运算量），因此提出椭圆曲线的密码系统(EllipticCurveCryptosystem,ECC)，它的安全性必须相当于RSA或ElGamal的密码系统。34

椭圆曲线上的有限加法群所使用的椭圆曲线方程式为y2=x3+ax+b此曲线刚好对称于y=0这条直线参数a及b必需满足4a3+27b2≠0，才能确保没有重根，具有唯一解加法单位元素O为一无穷远的点，并满足O=-O此加法单位元素亦需满足：椭圆曲线上某三点共线其合为O35

椭圆曲线上不同坐标点相加36作法先找出A与B这两点所构成的直线。接着找出这个直线与椭圆曲线的交点R。由于A、B及R这三点共线，根据椭圆曲线加法的定义可知A+B+R=0，因此可求得A+B=-R，这里的-R表示坐标点R对y=0这条直线镜射，也就是R对称于y轴的坐标点。

椭圆曲线上不同坐标点相加(续)37范例：假设一椭圆曲线为y2=x3+73，求A坐标点(-4,3)与B坐标点为(2,9)相加的结果。求出A与B两点所构成的直线方程式（二个坐标点可以画一直线）为y=x+7。将此直线方程式y=x+7代入椭圆曲线方程式y2=x3+73中，得知此直线与椭圆曲线的交点坐标R为(3,0)。把R坐标对y轴做镜射，可得到-R的坐标为(3,-10)，因此可得知A与B两点做相加，其值等于(-4,3)+(2,9)=(3,-10)。

椭圆曲线上不同坐标点相加(续)38

椭圆曲线上相同坐标点相加39作法：先找出A点在椭圆曲线上的切线。接着找出这条切线与椭圆曲线的交点R。同样地，我们可以看成A、A'、R这三点共线，根据椭圆曲线加法的定义可得知A+A'+R=O，因此可求得A+A=-R。

椭圆曲线上不同坐标点相加(续)40

椭圆曲线上一坐标点与一无穷远点相加41

椭圆曲线上两对称点相加A＋B=A+(-A)=O

B42

7.4.2在有限体内的椭圆曲线运算

在此椭圆曲线上可能出现的点有(0,1)、(0,4)、(2,1)、(2,4)、(3,1)、(3,4)、(4,2)、(4,3)、(∞,∞)任取椭圆曲线上两点，无论作加法、减法或乘法，其结果永远为上述坐标点中的一点椭圆曲线中的离散对数难题：给订一参数K及一点A，要求得另一点B，使得B=KA是很容易的。例如：5A=A+A+A+A+A但若给定A及B要求得K则很困难437.4.3椭圆曲线的公开密钥加密机制447.4.4椭圆曲线的数字签章45

7.5混合式的加密机制混合式加密机制顾名思义就是同时采用对称式密码机制及公开密钥密码机制的加密系统，截长补短，使它可以同时拥有这两种密码机制的优点。46

7.5.1数位信封Sender:AliceReceiver:BobC=ESK(M)密文V=EPU(SK)信封SK:SessionKey(交谈密钥)ESK:秘密密钥密码系统(Key:SK)PU:Bob之公开密钥EPU:公开密钥密码系统(Key:PU)PR:Bob之秘密密钥M=DSK(C)明文SK=DPR(V)交谈密钥密文及信封477.5.2Diffie-Hellman的密钥协议与交换机制Diffie和Hellman在1976年最早提出公开密钥密码系统的概念。没有真正地利用公开密钥去对讯息做加解密，而是利用公开密钥的概念来帮助通讯双方可以安全地协议出一把共同的交谈密钥(SessionKey)。真正的加解密工作是利用所协议出来的这把交谈密钥，透过DES或AES等对称式的密码系统来完成。48Diffie-Hellman的密钥协议方法注:

p为很大之质数

g为与p互质之原根(primitive)49Diffie-Hellman的密钥交换方法子机密密钥Ki产生方法如下：分派者决定主机密密钥K任选K1、K2、…、Kn-1等n-1把子机密密钥由下列方程式求出第n把子机密密钥Kn

Kn=K1⊕K2⊕…⊕Kn-1⊕Kn当n个成员均拿出其子机密密钥Ki，即可推导出煮机密密钥K： K=K1⊕K2⊕…⊕Kn507.6机密分享(t,n)门坎机密分享技术Shamir在1979年提出(t,n)门坎机密分享技术(ThresholdSecretSharing)门坎机密分享技术之两重要参数： t：门坎值 n：机密分享数目机密分派者将机密信息K打造成n份不同的子机密(Shadow)，每位成员都可得到一子机密讯息Ki51(t,n)门坎机密分享技术(续)(t,n)门坎机制的两个主要法则：当子机密讯息的数目等于或大于门坎值t时，便可以导出主机密信息。当子机密讯息的数目小于门坎值t时，就无法导出主机密信息。52分派者任选t-1次多项式 F(X)=K+a1X+a2X2+…+at-1Xt-1

modP K：主机密信息

P：为大值数并满足P≧K a1,a2,…,at-1：值介于0~P-1间分派者给每位成员唯一的公开识别码IDi，及依IDi产生不同的子机密信息Ki=F(IDi)

i=1,2,…,n (IDi,Si)：可视为多项式F(X)上的一个坐标点53(t,n)门坎机密分享技术(续)假设有大于等于t个成员拿出所持有的子机密信息(IDi,Ki)，可得到下列t条方程式：

Ki=K+a1IDi+a2IDi2+…+at-1IDit-1modP,i=1,2,…,t上式t个未知数(K,a1,a2,…,at-1)可用下列方法解出：解联立方程式利用下列Lagrange插值多项式解出机密值K：54(t,n)门坎机密分享技术(续)范例：(t,n)=(3,4)门坎机密分享技术如下分派者任选2次多项式：F(X)=6+3X+4X2mod11分派者给每位成员识别码IDi，并计算出各成员的机密信息Ki假设三成员(ID1,ID2,ID3)拿出所持有的子机密信息(IDi,Ki)，可得到下列三条方程式： 2=K+a1(1)+a2(12)mod11 6=K+a1(2)+a2(22)mod11 7=K+a1(3)+a2(32)mod1155(t,n)门坎机密分享技术(续)可用Lagrange插值多项式解出机密值K：代入公式得：

56(t,n)门坎机密分享技术(续)577.7量子密码学前使用的密码系统中，不论DES、RSA、ElGamal或椭圆曲线密码系统，其安全程度都仅属于计算安全(ComputationalSecure)。量子计算机的出现，使得现存的密码系统都将不再安全。有机会利用量子计算机来发展出无条件安全的密码系统587.7.1量子计算机的基本概念量子计算机(QuantumComputer)是利用量子物理的法则所设计的一种计算机。与传统计算机最大的差别在于量子计算机可以同步地处理同一件工作，因此可大幅缩减在运算上所需花费的时间。量子计算机的基本元素称之为量子位(QuantumBits)，简称为qubits。59迭加性(Superposition)假设每一个量子位都可能会有两种状态，不是顺时针旋转就是逆时针旋转，若我们把一个粒子放到一个暗箱里，然后打进一个微弱的脉冲，此时箱子内的粒子可能是顺时针，也可能是逆时针，若不打开箱子看，我们无法得知这个粒子旋转的方向。这种所有状态都可能出现的情况就称为迭加性。测量性(Measurement)在箱子打开之前，量子是以迭加的状态存在，也就是顺时针旋转或逆时针旋转都有可能。一旦箱子被打开后，答案就公布了，量子的迭加性也随之消失。量子计算机的特性量子计算机的特性(续)可逆性(Reversing)在量子运算中，所有运算在未经测量前都是可逆的。不可复制性(No-cloning)无法对处于迭加状态中的量子进行复制。纠缠性(Entanglement)无法分解成任意两个量子态的乘积。617.7.2量子计算机对传统密码学的威胁以猜数字游戏为例，一方从0到9的数字中任选四个不同的数字，由另一方来猜，总共有10×9×8×7=5040种可能的答案。若把这个猜谜游戏交给传统计算机来执行，就算计算机依序测试各种可能的答案，例如，先猜0123，若不对，接着就猜0124，如此不断地猜下去，彻底尝试过5040种可能的答案，也只需要几秒钟的时间就可以找到正确的答案。62由于量子计算机可以对同一个问题的不同状态进行同步的处理，所以量子计算机可以更有效率地来执行这个猜谜游戏。其作法如下：我们可以用14个位来表示任何由4个数字所组成的十进制数，例如「00000001111011」就相当于十进制的「0123」，「00000001111100」相当于十进制的「0124」。然后将每一个位用一个量子位来表示，再将这14个量子位同时放到一个箱子中。7.7.2量子计算机对传统密码学的威胁(续)7.7.2量子计算机对传统密码学的威胁(续)打入弱脉冲，使之旋转方线产生变化，此时这14个量子就进入迭加状态了，它同时代表214种可能发生的状态，然后把这些处于迭加状态的粒子放入量子计算机中执行。由于量子计算机可以同时尝试所有可能的答案，一个单位时间后，量子计算机就会告诉我们正确的谜底为何，而传统计算机可能需要5040个单位时间，才能完成所有可能答案的搜查。647.7.3量子密码学概念是利用光子的偏震方向来代表「0」或「1」。偏震方向的定义有两种，分别是直线方案(Rectilinear)与斜线方案(Diagonal)。直线方案中偏振方向「|」代表「1」，偏振方向「－」代表「0」。斜线方案中偏振方向「\」代表「1」，偏振方向「/」代表「0」。而用来测量偏振方向的侦测器也可分为两种，分别为直线型「＋」，与斜线型「×」，「＋」型侦测器可用来判定「|」及「－」偏振的光子；同理，「×」型侦测器可用来判定「\」及「/」偏振的光子。65利用量子密码进行秘密通讯春娇随意用直线或斜线方案来传送一连串可代表0或1位的光子给志明。由于志明不知道春娇依序用了哪些方案来传送这些光