elgamal公钥密码体制

ElGamal公钥密码体制1、问题描述设计ElGamal公钥密码体制算法。

2、算法设计(1)选取大素数p和p的一个原根a，(a,p)=1,1<a<p(2)随机选取整数d，1<d<p-1，计算b≡ad (mod p)；p,a,b为公钥，d为私钥(3)加密：对0<m<p，秘密的随机选取整数k,1<k<p-1,加密后密文为c=(c1 ，c2 ),c1 ≡ak (mod p), c2 ≡ m bk (mod p)(4)解密：明文m ≡c2 ( c1 d) -1 (mod p)主要步骤3、算法分析该算法的基础是找到一个原根，大数的原根产生过程比较慢，本人目前也只能产生8位以内的素数的原根，还有待改进。

同时也涉及到模幂运算，选取的幂指数如果较大，时间复杂度也会相应的增加。

int inverse(int a,int m){long int c,d;int j;int q[100],r[100],t[100],s[100];c=a;d=m;r[0]=c;r[1]=d;s[0]=1;s[1]=0;t[0]=0;t[1]=1;for(j=1;r[j]!=0;j++){q[j]=(int)(r[j-1]/r[j]);r[j+1]=r[j-1]-q[j]*r[j];if(j>=2){s[j]=s[j-2]-q[j-1]*s[j-1];t[j]=t[j-2]-q[j-1]*t[j-1];}}return s[j-1];}int gcd(int a,int b){int c;if(a<b){c=b;b=a;a=c;}while(b!=0){c=b;b=a%b;a=c;}return a;}void main(){int p,g,k,s,x,r,t=1,i,j,f,y,m,M;cin>>p>>g>>k;s=2;for(i=1;i<=k;i++){t*=s;t=t%p;}while(t<0){t=t+p-1;}cout<<"public key is"<<"("<<t<<","<<g<<","<<p<<")"<<endl;cin>>r;if(gcd(p-1,r)!=1)cout<<"the data is not suitable"<<endl;x=1;for(j=1;j<=r;j++){x*=s;x=x%p;}cin>>m;f=inverse(r,p-1);y=(m-k*x)*f%(p-1);while(y<0){y=y+p-1;}cout<<"the signature is"<<"("<<x<<","<<y<<")"<<endl;for(i=1;i<=m;i++){g*=g;}g=g%p;for(i=1;i<x;i++){y*=y;}for(j=1;j<y;j++){x*=x;}M=x*y%p;if(M=p){cout<<"the signature is useful"<<endl;}else{cout<<"the signature is not useful"<<endl;}}运行结果。

ElGamal公钥密码体制是一种基于离散对数问题的非对称加密算法，由Tahir ElGamal 在1985年提出。

在ElGamal密码体制中，公钥包括一个大素数和该素数的一个本原元，私钥则是一个随机数。

通过公钥加密的消息可以使用私钥进行解密，而私钥签名的消息可以使用公钥进行验证。

ElGamal公钥密码体制的安全性基于离散对数问题的难解性，即在一个有限域中，给定元素g和h，找到整数x使得h=g^x在计算上是不可行的。

由于离散对数问题的难解性，ElGamal密码体制可以提供较高的安全性。

与RSA算法相比，ElGamal算法在加密和签名方面都具有较高的效率和灵活性。

此外，由于ElGamal算法是基于离散对数问题的，因此它可以用于构造其他密码学方案，如数字签名、密钥协商等。

需要注意的是，虽然ElGamal公钥密码体制具有较高的安全性，但在实际应用中仍需要注意密钥的生成、存储和使用安全，以避免潜在的安全风险。

下面我们首先计算
γ
2,0
=α
0×(p-1)/2
mod 29
= 20 mod 29 = 1, γ
2,1
=α
1×(p-1)/2mod
29
= 228/2 mod 29
= 28. 因为 = 28 =γ
2,1 ,
0
ß mod 29 = 1828/2 mod 29
所以 a = 1.令
ß = ß α 1 因为
0, 1 e i 1
i

根据目前的计算能力，只有当p-1 的素因子是小素数时，才 能有效分解 p-1求得 。因此，Pohlig-Hellman 算法适用于p1 的素因子是小素数的情况。 例5.8 设p = 29, 则 p-1= 28 = 22×7.设α = 2, ß 18. = 求log 。令log a .
s ( p 1 ) qi
mod p
qi ,s
· ,k, · ·
s = 0, 1,2, ·· i －1. 将这些 q ·
ei i
排成一个
下面利用表L求 a mod q
a mod q
ei i
, i= 1,2,
1 i
· ,k. · ·
e i 1
设
q
ei 1 i
a a q a
0
ß=αd mod p,
所以
k c2(c1d)–1≡mß (α
dk
)
–1
(mod p)
–1(mod
≡mα
dk
(α
dk
)
p) α ∈zp*
≡m(mod p). 因此，解密变换能正确的从密文恢复相应的明文。
5.4.2. ElGamal公钥密码体制的安全性

实例解析： p=19； a=13,d=10,a与d均小于 p,符合条件； y = 13^10(mod19)=6; 公钥：y=6 a=13 p=19 私钥：d=10





签名过程： 1.随机选取一个数k，1< k<p-1，且k和p-1互质 2、计算r，r满足：r≡a^k (mod p) 3、待签名信息为m， 计算s≡(m-dr)*(k^(1)) (mod p-1) （r，s）构成对m的签名

一个群被称为有限群，如果它有有限个元素。元素 的数阶叫做群 G 的阶 例如，模19下7的阶为3，[1, 7, 49, 343, 2401, 16807, 117649, 823543, 5764801...]={1,7,11,1,7,11,1,7,11...}这里的 1,7,11循环，实际只有3个元素





群是一个集合G，连同一个运算 "· "，它结合任何两个元素 a 和 b 而形成另一个元素，记为 a · b。符号 "· " 是对具体给出的运算，比如加 法的一般的占位符。要具备成为群的资格，这个集合和运算 (G, · ) 必须 满足叫做群公理的四个要求： 1.封闭性。 对于所有 G 中 a, b，运算 a · b 的结果也在G 中。 2.结合性。 对于所有 G 中的 a, b 和 c，等式 (a · b) · c = a · (b · c) 成立。 3.单位元。 存在 G 中的一个元素 e，使得对于所有 G 中的元素 a，等式 e · a = a · e = a 成立。 4.反元素。 对于每个 G 中的 a，存在 G 中的一个元素 b 使得 a · b = b · a = e， 这里的 e 是单位元。

一一、是非判断题（10分）1.差分分析是一种攻击迭代密码体制的选择明文攻击方法，所以，对于DES和AES都有一定的攻击效果。

（对）2.反馈移位寄存器输出序列生成过程中，抽头位对输出周期长度的影响起着决定性的作用，而初态对输出周期长度没影响。

（对）二、选择题（15分）1.公钥密码体制至少能抵御的攻击是（C.选择明文攻击）2.适合文件加密，而且有少量错误时不会造成同步失败，是软件加密的最好选择，这种分组密码的操作模式是指（D.输出反馈模式）3.按目前的计算能力，RC4算法的密钥长度至少应为（C.128）位才能保证安全强度。

4.密钥在其生命生命周期中处于不同的状态，每种状态包含若干时期，那么密钥备份时期是密钥处于（B.使用状态）5.量子密码更适合实现下面哪项密码技术。

（D.密钥分发）6.当用户收到一个证书是，应当从（C.CRL）中检查证书是否已经被撤销。

（CRL：证书撤销列表）A.在PKI中，关于RA的功能，下面说法正确的是（B.验证申请者身份）。

7.数字水印是信息隐藏技术研究领域的重要分支，现主要应用领域是（A.版权保护）8.在DES算法中，如果给定初始密钥K，经子密钥产生器产生的各个子密钥都相同，则称该密钥K为弱密钥，DES算法中弱密钥的个数为（B.4个）。

9.生日攻击是针对于下面哪种密码算法的分析方法（D.MD5）。

10.指数积分法是针对下面哪种密码算法的分析方法（C.ElGamal）11.密钥存档是密钥处于（C.过期状态）三、填空题（15分）1.关于DES算法的安全性，若Ek（m）=Dk（m），则这样的密钥称为弱密钥，又其互补性使DES在选择明文攻击下所需的工作量减半。

2.选择合适的n级线性反馈移位寄存器可使序列的周期达到最大值2^n-1，这样序列称为m 序列，但敌手知道这序列中一段长为 n 的明密文对即能破译其后序列的密文。

3.密钥分配和协商的最大区别是：密钥分配是通信双方中一方或密钥分配中心选取一个秘密密钥发给双方，而密钥协商是保密通信双方（或更多方）通过公开信道的通信来共同形成秘密密钥的过程。

ElGamal加密算法原理ElGamal加密算法是一种公钥密码体制，由Taher Elgamal在1985年提出。

它基于离散对数问题的困难性，被广泛应用于保护数据的机密性和安全通信。

ElGamal加密算法涉及到两个关键方面：密钥生成和加解密过程。

在下面的内容中，我们将详细介绍这些方面的基本原理。

1. 密钥生成ElGamal加密算法使用一对相关联的公钥和私钥来进行加解密操作。

下面是生成这些密钥的步骤：1.选择一个大素数p作为有限域，以及一个生成元g。

2.随机选择一个整数x（0 < x < p-1），作为私钥。

3.计算y = g^x mod p，并将(x, y, p, g)作为公钥，(x)作为私钥。

在这个过程中，p和g是公开信息，而x是保密的。

2. 加解密过程加密假设Alice想要向Bob发送一条消息m。

下面是Bob使用ElGamal加密算法对消息进行加密的步骤：1.Alice首先获取Bob的公钥信息(y, p, g)。

2.Alice选择一个随机整数k（0 < k < p-1）。

3.Alice计算c1 = g^k mod p，并发送给Bob。

4.Alice计算c2 = (y^k * m) mod p，并发送给Bob。

在这个过程中，c1和c2是加密后的消息，Alice只需要将它们发送给Bob即可。

解密Bob接收到加密后的消息(c1, c2)后，可以使用ElGamal加密算法进行解密。

下面是解密的步骤：1.Bob使用自己的私钥x计算s = c1^x mod p。

2.Bob计算m’ = (s^(-1) * c2) mod p。

最终，Bob可以得到原始消息m’。

3. 安全性分析ElGamal加密算法基于离散对数问题的困难性，具有较高的安全性。

攻击者需要解决离散对数问题才能成功破解加密文本。

然而，在实际应用中，ElGamal加密算法存在一些安全性问题和限制：•密文扩张：加密后的消息长度为明文长度的两倍或更多。

14
Diffie-Hellman密钥交换算法 密钥交换算法
Diffie和Hellman在其里程碑意义的文章中， 虽然给出了密码的思想，但是没有给出真正意 义上的公钥密码实例，也既没能找出一个真正 带陷门的单向函数 然而，他们给出单向函数的实例，并且基于此 提出Diffie-Hellman密钥交换算法
13
常用的公开密钥算法
公钥算法的种类很多，具有代表性的三种密码： 公钥算法的种类很多，具有代表性的三种密码： 基于整数分解难题（IFP）的算法体制 基于整数分解难题（IFP）的算法体制(RSA) 基于离散对数难题（DLP）算法体制 基于离散对数难题（DLP）算法体制(ElGamal) 基于椭圆曲线离散对数难题（ ECDLP ） 的算法体制 基于椭圆曲线离散对数难题 （ ECDLP） (ECC)
3
4.1 公钥密码体制的基本原理
对称算法的不足
（1）密钥管理量的困难 传统密钥管理：两两分别用一个密钥时， 传统密钥管理：两两分别用一个密钥时，则n个用户需 C(n,2)=n(n-1)/2个密钥 当用户量增大时， 个密钥， 要C(n,2)=n(n-1)/2个密钥，当用户量增大时，密钥空 间急剧增大。 间急剧增大。如: n=100 时， C(100,2)=4,995 n=5000时 n=5000时， C(5000,2)=12,497,500 （2）密钥必须通过某一信道协商，对这个信道的安全 密钥必须通过某一信道协商， 性的要求比正常的传送消息的信道的安全性要高
7
公开密钥密码的重要特性
฀
加密与解密由不同的密钥完成 Y: X: Y = EKU(X) X = DKR(Y) = DKR(EKU(X))
加密: X฀ 解密: Y฀
฀ 知道加密算法,从加密密钥得到解密密钥在计算上 , 是不可行的 ฀ 两个密钥中任何一个都可以用作加密而另一个用 作解密(不是必须的) X = DKR(EKU(X))

信息安全与密码学院：数学与统计学院专业: 数学与应用数学班级：12级数应(3)班姓名：田佳学号： 20121010357信息安全与密码知识点总结第一章信息安全概论§1 信息安全的目标§1.1 信息系统中的主要安全问题1、网络可靠性问题（备份,网络管理，计费等)2、系统本身的缺陷（芯片、操作系统,数据库后门等)3、恶意攻击和破坏（黑客攻击,病毒破坏等)4、信息安全问题（信息窃取,假冒,抵赖等)网络与信息安全的主要任务（1）网络安全的任务：保障各种网络资源稳定可靠的运行，受控合法的使用。

（2）信息安全的任务：保证：机密性、完整性、不可否认性、可用性（3）其他方面：病毒防治，预防内部犯罪§1.2 我国信息安全的现状§1.3 信息安全威胁信息安全威胁：指某个人、物、事件或概念对信息资源的保密性、完整性、可用性或合法使用性等等所造成的危险。

虽然人为因素和非人为因素都可以对通信安全构成威胁，但是精心设计的人为攻击威胁最大。

网络安全性威协：（1）截获(interception)（2）中断(interruption)（3）篡改(modification）（4）伪造(fabrication)主动与被动攻击被动攻击：目的是窃听、监视、存储数据，但是不修改数据。

很难被检测出来，通常采用预防手段来防止被动攻击，如数据加密。

主动攻击：修改数据流或创建一些虚假数据流。

常采用数据加密技术和适当的身份鉴别技术。

网络安全攻击截获：以保密性作为攻击目标，表现为非授权用户通过某种手段获得对系统资源的访问，如搭线窃听、非法拷贝等中断：以可用性作为攻击目标，表现为毁坏系统资源，切断通信线路等篡改：以完整性作为攻击目标，非授权用户通过某种手段获得系统资源后，还对文件进行窜改，然后再把篡改过的文件发送给用户。

伪造：以完整性作为攻击目标，非授权用户将一些伪造的、虚假的数据插入到正常系统中§1.4 常见的安全威胁信息泄露，破坏完整性，拒绝服务，非法使用，窃听，业务流分析，假冒，旁路控制，授权侵犯，特洛伊木马，陷阱门，抵赖，重放，计算机病毒安全威胁分类物理环境：自然灾害 ,电源故障、设备被盗通信链路：安装窃听装置或对通信链路进行干扰网络系统：互联网的开放性、国际性操作系统：系统软件或硬件芯片中的植入威胁应用系统：木马、陷阱门、逻辑炸弹管理系统：管理上杜绝安全漏洞§1.5 信息安全基本要素机密性，完整性，可用性，可控性，可审查性§1.6 信息安全的目标安全工作的目的就是为了在安全法律、法规、政策的支持与指导下，通过采用合适的安全技术与安全管理措施，完成：1，使用访问控制机制，阻止非授权用户进入网络，即“进不来”，从而保证网络系统的可用性。

ElGamal离散对数介绍ElGamal是一种基于离散对数问题的公钥密码体制。

它由塞尔弗·埃尔加马尔在1985年提出，是非对称密钥加密算法中的一种重要算法。

ElGamal算法具有安全性高、可证明安全等特点，在实际应用中得到广泛使用。

离散对数问题在介绍ElGamal算法之前，首先需要了解离散对数问题（Discrete Logarithm Problem）。

离散对数问题是指给定一个有限群G和元素g，找到满足g^x ≡ h (mod p)的整数x。

其中p是一个大素数，g是群G的生成元，h是群G中的一个元素。

离散对数问题被认为是计算复杂度非常高的问题，目前没有有效的算法可以在多项式时间内解决。

这使得离散对数成为了很多公钥密码体制的基础。

ElGamal加密算法ElGamal加密算法利用了离散对数问题来实现公钥加密和解密过程。

它包括了密钥生成、加密和解密三个主要步骤。

密钥生成1.选择一个大素数p作为模，并选择一个生成元g。

2.随机选择一个整数a，满足1 ≤ a ≤ p-2。

3.计算h = g^a (mod p)。

4.公钥为(p, g, h)，私钥为a。

加密假设要加密的明文为m，加密过程如下： 1. 随机选择一个整数k，满足1 ≤ k ≤ p-2。

2. 计算c1 = g^k (mod p)。

3. 计算c2 = m * h^k (mod p)。

4. 密文为(c1, c2)。

解密解密过程如下： 1. 根据私钥a计算s = c1^a (mod p)。

2. 计算m’ = c2 * s^-1 (mod p)。

其中s^-1是s的模p的逆元素。

3. 明文为m’。

安全性分析ElGamal算法的安全性基于离散对数问题的困难性。

在大素数p和合适的参数选择下，破解ElGamal加密需要计算离散对数，这是一个非常耗时的任务。

然而，在实际应用中，需要注意一些安全性问题。

例如，如果相同的随机数k被重复使用来加密不同的明文，则可以通过观察两个密文之间的关系来推导出私钥a。

Elgamal算法ElGamal算法，是一种较为常见的加密算法，它是基于1984年提出的公钥密码体制和椭圆曲线加密体系一．ElGamal算法定义：ElGamal算法，是一种较为常见的加密算法，它是基于1984年提出的公钥密码体制和椭圆曲线加密体系。

既能用于数据加密也能用于数字签名，其安全性依赖于计算有限域上离散对数这一难题。

在加密过程中，生成的密文长度是明文的两倍，且每次加密后都会在密文中生成一个随机数K。

二．密钥产生方法密钥对产生办法。

首先选择一个素数p，获取一个素数p的一个原根g(若g模p的阶等于φ(m)，则称a为模m的一个原根。

（其中φ(m)表示m的欧拉函数）) 和一个随机数x，且g和x 均小于p, 计算y = g^x ( mod p )，则其公钥为y, g 和p。

私钥是x。

g和p 可由一组用户共享。

ElGamal用于数字签名。

被签信息为M，首先选择一个随机数k, k与p - 1互质，计算a = g^k ( mod p )再用扩展Euclidean 算法对下面方程求解b：M = xa + kb ( mod p - 1 )签名就是( a, b )。

随机数k须丢弃。

验证时要验证下式：y^a * a^b ( mod p ) = g^M ( mod p )同时一定要检验是否满足1<= a < p。

否则签名容易伪造。

ElGamal用于加密。

被加密信息为M，首先选择一个随机数k，k与p - 1互质，计算a = g^k ( mod p )b = y^k M ( mod p )( a, b )为密文，是明文的两倍长。

解密时计算M = b / a^x ( mod p )ElGamal签名的安全性依赖于乘法群(IFp)* 上的离散对数计算。

素数p必须足够大，且p-1至少包含一个大素数因子以抵抗Pohlig & Hellman算法的攻击。

M一般都应采用信息的HASH值(如SHA 算法)。

ElGamal的安全性主要依赖于p和g，若选取不当则签名容易伪造，应保证g对于p-1的大素数因子不可约。

EIGamal公钥密码体制 公钥密码体制 公钥密码
数学基础
本原元(原根 : 为素数, 本原元 原根):设p为素数,若存在一个整数 , 原根 为素数 若存在一个整数a, 使得a, 关于模p互不同 使得 ,a2,a3,……,ap-1,,关于模 互不同 , - ,,关于模 则称模p的本原元 或原根). 的本原元( 余,则称模 的本原元(或原根). 离散对数问题: 离散对数问题:Y=logaX 计算Y是容易的 由X计算 是容易的,至多需要 ×log2p次运 计算 是容易的,至多需要2× 算就可以. 但是根据Y计算 就是困难的, 计算X就是困难的 算就可以 . 但是根据 计算 就是困难的 , 利用 目前最好的算法, 对于小心选择的p将至少需要 目前最好的算法 , 对于小心选择的 将至少需要 p 1/2 次以上的运算 , 只要 足够的大 , 求解离散 次以上的运算, 只要p足够的大 足够的大, 对数就是相当困难的. 对数就是相当困难的.
EIGamal公钥密码体制 公钥密码体制
设计过程: 设计过程 Z * 的一个本原 Step1 选取大素数p,再选取 p 元a,并将p和a公开. Step2 随机选取整数 d : 1 ≤ d ≤ p 2 ,并计 算出 β = α d mod p 并将 β 作为公开的加密 密钥,将d作为保密的脱密密钥.
实现方法
(1) 大素数的选择与构造 将大素数p选为安全素数,即使p=2q+1且q为 素数. 实验表明,平均100个随机数中可选出1个素 数, 平均100素数中可选出1个安全素数.
(2)安全素数条件下本原元的判断方法 安全素数条件下本原元的判断方法
由Fermat定理知 α mod p = 1 ,即 因而如果 w = min{t > 0 : α t mod p = 1} 则有w 整除p-1=2q,因而由q是素数知,w只能 是2或q. 此时是 α 本原元等价于 α 2 mod p ≠ 1 且 α q mod p ≠ 1

摘要随着网络的发展，人们之间的各种交流变得越来越来方便，但同时也对信息传递的安全提出了新的要求，数字签名随之广泛的深入到了人们的日常生活中。

ELGamal作为目前应用比较广泛的数字签名算法，其信息安全性，以及可实现程度，在很大程度上决定了它的应用范围。

本文主要对ELGamal数字签名体制中的签名和认证过程中所需的模块，以及用户如何由离散对数难题保证了签名的正确性进行了必要的描述。

接下来对ELGamal数字签名安全性以及他在基于身份认证中的应用做了一定介绍。

论文重点是对密码算法前提的大整数运算算法做了进一步研究，对大素数的生成，其中包括素性测试和随机数生成算法原理做了一定介绍，然后介绍了乘法群的生成元的生成原理，论文最后将系统介绍签名过程。

关键词：ELGamal数字签名验证大整数运算大素数生成元ABSTRACTWith the development of network, the communions between people become more and more convenient, but also it brings forward the new security requirements of in-formation transfer. Digital Signature goes into the people's daily life along with these processes.As one of the most widely used Digital Signature, the application of the ELGamal Signature is largely depend on his information security and the operation process. In this paper, we will discuss the process of the ELGamal Signature and the attestation. One can check his authorization of the sign which rely on the problem of the discrete logarithm. And then we will analyze the security of the signature. The application the ELGamal signature in the ID-BASE system will also be discussed. The key part of this paper is to introduce the concept the large integer. The arithmetic of the large in-teger is crucial in most cryptosystems.As to the construction of a large prime inte-ger,we will discuss the method to construct a Random Number and the primality test.Then the high-order-cycle generator method for the formation of the foundation will introduced too.In the last part of the paper,we will go through the process of the ELGamal Signature.keywords: ELGamal Digital Signature authorization large Integer large Prime Number generator目录错误！未定义书签。

16
ELGamal公钥密码

1985年，El Gamal 在Differ-Hellman密钥交换协议基础上改 进而来 依赖数学难题：DLP (Discrete Logarithm Problem)
17
ELGamal公钥密码

算法
生成密钥对GenKeyPair 加密Encrypt 解密Decrypt
离散对数问题
（备注）算法复杂度：
例如：
离散对数问题

离散对数问题 (Discrete Logarithm Problem)，简称 DLP
Given α, y , p, to find x s.t. αx=y (mod p) e.g.


α=2 , y=3 , p=23 , x=？ α=2 , y=97206 , p=136943 , x=？
24
ELGamal公钥密码

算法可还原性证明
C2 V-1 mod p ＝(UM)V-1 mod p ＝UM（C1 d）-1 mod p ＝UM（（αk）d）-1 mod p ＝UM（（αd）k）-1 mod p ＝UM（（y）k）-1 mod p ＝UM（U）-1 mod p ＝M mod p
25
27
ELGamal公钥密码

安全性


针对k重复使用的攻击方法
攻击1（假设攻击者掌握k）如果 k不是一次性的，时间长了 就可能被攻击者获得。又因y是公开密钥，攻击者自然知道。 于是攻击者就可以根据 U＝y k mod p计算出U，进而利 用Euclid算法求出U－1。又因为攻击者可以获得密文C2，于是 可根据式C2＝UM mod p通过计算U－1C2得到明文M。 攻击2 设用同一个k加密两个不同的明文M和M’，相应的密文 为（C1 ，C2）和（C1’，C2’）。因为y k 不变，所以C2∕C2’＝ M∕M’，如果攻击者知道M，则很容易求出M’。

利用推广的欧几里德算法简化计算：

其计算原理依赖于下面的定理：
定理 ：gcd(a,b) = gcd(b,a mod b) ② 定理：a存在模p的乘法逆元的充要条件 是 gcd(a,p) = 1 如果gcd(a,b)=d，则存在m,n，使得d = ma + nb， 称呼这种关系为a、b组合整数d，m，n称为组 合系数。当d=1时，有 ma + nb = 1 ，此时可以 看出m是a模b的乘法逆元，n是b模a的乘法逆元

公钥和私钥必须相关，而且从公钥到私钥不可
推断


必须要找到一个难题，从一个方向走是容易的，从 另一个方向走是困难的 如何把这个难题跟加解密结合起来
计算可行和不可行的界与计算复杂性理论密
切相关
计算复杂性理论可以提供指导

但是需求不尽相同

计算复杂性通常针对一个孤立的问题进行研究 而公钥密码学往往需要考虑一些相关的问题 比如，密码分析还需要考虑已知明文、选择明文等相关的情形 计算复杂性考虑最坏的情形 而对于公钥密码学则是不够的
二、密钥的选取
①
挑选大素数p 和 q 。 选择 e 或 d ，并计算另外一个。
②
选取一个素数的过程如下：
①随机选一个奇数n; ②随机选一个整数a<n; ③完成素性检测，如下面的Miller-Rabin算法 ④如果n没有通过检验，舍弃n并转向步骤(1)，如果n
通过了足够多次的检验，就接受它为素数，否则转 向步骤(2)
ElGamal：安全性基于有限域内计算离散对
数的困难性。
– 数字签名 – 加密
基础知识
若p是素数，则0,1……,p-1
构成一个有限域 本原元定义：若(a,m)=1，以m为模a的指数φ (m) 为使ad=1 mod m成立的最小的正整数d，则a叫 做模m的原根或本原元。 本原元α ：α 满足α p-1=1 mod p且p-1是使此关 系式成立的最小正整数,p为素数

2020/10/1
西安电子科技大学计算机学院
2
2020/10/1
西安电子科技大学计算机学院
3
Diffie - Hellman密钥交换
是一个公钥分配方案
不能用于交换任意的消息 只限于进行公共密钥的建立 只对通信的双方已知
密钥的值依赖于通信的参与者 (以及他们的 私钥和公钥信息）
有限域中的指数运算（模一个素数）是相对 容易的，而离散对数的计算是相对困难的。
《计算机与网络安全》
Chapter 10
密钥管理和其它公钥密码体制
§10.1 Diffie-Hellman密钥交换
第一个公钥算法 1976由Diffie 和 Hellman 提出 DH算法是一个实用的密钥公开交换的算法 算法本身只限于进行密钥交换 已应用在许多商业产品中
“New directions in cryptography ”
会话密钥KAB 作为A和B两个用户在传统密码体制中的 共享密钥来使用的
可以一直使用前面产生的会话密钥，直到想重新选择新 的会话密钥为止。
攻击者需要解出x, 必须求解离散对数。
2020/10/1
西安电子科技大学计算机学院
7
Diffie-Hellman 举例
用户 Alice 和 Bob 想交换密钥:
双方同意使用全局参数 q = 353 和α=3
随机选择一个保密的私钥:
A 选择 xA = 97, B 选择 xB = 233
分别计算各自的公钥:
yA=397 mod 353 = 40 (Alice) yB=3233 mod 353 = 248 (Bob)
计算共享的会话密钥:
KAB= yBxA mod 353 = 24897 = 160 KAB= yAxB mod 353 = 40233 = 160

15
13 密钥建立



密钥生成： 选取一个大素数p及本原元a mod p 接收者 Bob有一个密秘钥 xB 计算 yB = axB mod p
16
14. El Gamal 加密



为加密 M 发送者选择随机数k, 0<=k<=p-1 计算消息密钥 K : K = yBk mod p 计算密文对: C = {C1,C2} C1 = ak mod p C2 = K.M mod p 发送到接收者 k 需要永久保密

29
Finding Prime Numbers


Given a list of numbers (say from 1 to 30) determine which in the list are prime SOLUTION: Sieve of Eratosthenes
write all the numbers between a and b cross out all the multiples of 2 except 2 cross out all the multiples of 3 except 3 continue2until there is nothing left to cross out 1 3 4 5 6 7 8 9 10
10
RSA Operation

加密过程：


将明文分成若干个信息块，每块用一个整数来表示，比 如第一块对应的整数位M 根据m,e和n计算得到密文c c = Me mod n

解密过程：


计算M= cd mod n 只有 d 的拥有者才能解开密文，要想找出d，必须知道 p 与q，找出p 与q的唯一方法是将n分解因子 因此RSA的安全性依赖于n分解因子的难度

Exercises
3、Illustrate the operation of RSA, given the following parameters: System modulus n=119 (7x17) encryption exp e=11 Determine the decryption exponent d, and hence details the public and private keys for this user. Then show how a message M=20 would be encrypted and decrpyted.
Diffie-Hellman 密钥分配方案 公钥密码问世 Diffie & Hellman in 1976: 密钥交换的实际方法 公钥方案概念的提出
W Diffie, M E Hellman, "New directions in Cryptography", IEEE Trans. Information Theory, IT-22, pp644-654, Nov 1976
α b ， 并 计 算 (α b ) a α a ， 并 计 算 (α a ) b αb
，并把计算
此 时 ， A 和 B 已 有 了 共 享 的 群 元 素 α ab （ 可 作 为 共 享 密 钥 ） （ 此 。 协议是没有认证的交换协议，但可以通过第三方对交换的消息认
证、签名）
改进措施
使用STS协议时，A与B都提供自己的公 协议时， 与 都提供自己的公 使用 协议时 密钥对和共钥的证书， 根据一些消 钥/密钥对和共钥的证书，A根据一些消 密钥对和共钥的证书 息来计算一个签名， 息来计算一个签名，其中包括公共值 g^a mod p，B也做类似的运算。即使 p，B也做类似的运算 也做类似的运算。 C仍然能够截取 C仍然能够截取A与B之间的信息，但他 仍然能够截取A与B之间的信息 之间的信息， 并不能在没有A和 的密钥的情况下伪造 并不能在没有 和B的密钥的情况下伪造 签名，因此，这个增强的协议抵挡了中 签名，因此， 间人攻击。 间人攻击。