ToB企服应用市场:ToB评测及商务社交产业平台

标题: 公钥密码学算法类型综述 [打印本页]
作者: 惊雷无声    时间: 2024-5-14 03:41
标题: 公钥密码学算法类型综述
作者：网安新生研讨课第一小组
采用协议 CC BY-NC，原文链接 ：https://www.cnblogs.com/Multya/p/18072514
概念

公开密钥密码学（英语：Public-key cryptography）也称非对称式密码学（英语：Asymmetric cryptography）是密码学的一种算法，它需要两个密钥，一个是公开密钥，另一个是私有密钥；公钥用作加密，私钥则用作解密。
使用公钥把明文加密后所得的密文，只能用相对应的私钥才能解密并得到原本的明文，最初用来加密的公钥不能用作解密。由于加密息争密需要两个不同的密钥，故被称为非对称加密；不同于加密息争密都使用同一个密钥的对称加密。
公钥可以公开，可任意向外发布；私钥不可以公开，必须由用户自行严格秘密保管，绝不透过任何途径向任何人提供，也不会透露给被信托的要通信的另一方。
公钥密码，又称非对称密码，比较常见的是基于以下三种数学困难的公钥密码体制；
历史

公钥加密头脑最早由瑞夫·墨克在1974年提出，之后在1976年。惠特菲尔德·迪菲与马丁·赫尔曼两位学者以单向函数与单向暗门函数为基础，为发讯与收讯的两方创建密钥。
瑞夫·查尔斯·墨克（英语：Ralph Charles Merkle，1952年2月2日－），生于美国，盘算机科学家，对于公开密钥加密技能有重大贡献。1979年在斯坦福大学取得电机工程博士学位。博士论文主题为〈加密，授权与公开金钥系统〉（Secrecy, authentication and public key systems）。
惠特菲尔德·迪菲（Whitfield Diffie），1944年出生于美国华盛顿特区，当代密码学之父，公钥密码学先驱，2015年图灵奖得主，美国国家工程院院士，英国皇家学会外籍院士。
惠特菲尔德·迪菲于1965年获得麻省理工学院数学专业学士学位；1965年至1969年担任MITRE公司研究助理；2015年获得ACM图灵奖；2017年当选为美国国家工程院院士。
马丁·赫尔曼，密码学和网络安全技能专家，主要论文有《密码学新动向》（New Directions in Cryptography）。迪菲与赫尔曼1976年发表了论文《密码学新动向》，在此中论述了关于公开密钥加密算法的新构想，即在一个完全开放的信道内，人们无需事先约定，便可举行安全的信息传输。获得2015年度图灵奖。
单向函数 (One-way function)是一种具有下述特点的单射函数：对于每一个输入，函数值都容易盘算（多项式时间），但是给出一个随机输入的函数值，算出原始输入却比较困难（无法在多项式时间内使用确定性图灵机盘算）。 单向函数是否存在仍旧是盘算机科学中的一个开放性问题。
给定任意两个聚集X和Y。 函数f：X→Y称为单向的，如果对每一个x属于X，很容易盘算出函数f（x）的值，而对大多数y属于Y，要确定满意y=f（x）的x是盘算上困难的(假设至少有这样一个x存在)。留意，不能将单向函数的概念与数学意义上的不可逆函数的概念混同，由于单向函数大概是一个数学意义上可逆或者一对一的函数，而一个不可逆函数却不一定是单向函数。
还没有人能够从理论上证明单向函数是存在的。单向函数存在性的证明将意味着盘算机科学中一个最具挑战性的猜想P=NP，即NP完全问题的解决，而关于NP完全性的理论却不足以证明单向函数的存在。有幸的是，现实中却存在几个单向函数的“候选”。说他们是“候选”，是由于他们表现出了单向函数的性质，但还没有办法从理论上证明它们一定是单向函数。
一个最简单的、各人熟知的“侯选”单向函数就是整数相乘。众所周知，不管给定两个多大的整数，我们很容易盘算出它们的乘积，而对于一个300位左右的十进制整数，即使已知它是两个大小差不多（150位左右的十进制数）的素数之积，用世界上盘算能力最强的盘算机，也没有办法在一个合理的时间内分解出构成这个整数的两个素数因子来。这里讲的“合理的时间”是指一个可度量的相当长的时间，比如人类或者地球的寿命等。
单向函数不能直接用作密码体制，由于它的求逆困难，用它加密的信息谁都不能解密。但是，单向函数在密码学领域里却发挥着非常紧张的作用。
一个最简单的应用就是口令保护。我们熟知的口令保护方法是用对称加密算法举行加密。系统方只存放口令经单向函数运算过的函数值，验证是将用户口令重新盘算函数值与系统中存放的值举行比对。动态口令认证机制多是基于单向函数的应用来计划的。
单向函数的另一个应用是各人熟知的用于数字署名时产生信息摘要的单向散列函数。
有些学者把现实中使用的密码算法分成三类，单向散列函数就是此中很紧张的一类，别的两类分别是公开钥(或非对称、双钥)算法和秘密钥(或对称、单钥)算法。单向函数是这三类算法共同的基础。
发展和分类

最开始的情况：信息明文传递
但是出现了缺陷：中心信息传递的过程中大概被人（中心人）截获，大概导致：
于是发送者和接受者找到一种方法，让中心人看不懂，这样就有效防止了机密、隐私信息被获取
由于即使传递的信息被获取，在被解密之前这个信息就是无用的信息
私钥密码产生的原因：
公钥密码产生的原因：
数据加密类型

背包算法

背包算法是由Merkle和Hellman开辟的背包算法。只能用于加密，后来由Shamir将它改进，使之也能用于数字署名；
背包算法的安全性起源于背包困难，他是一个NP完全问题，但后来发现该算法并不安全，但是由于它证明了怎样将NP完全问题用于公开秘钥密码学，因此，值得去学习。
RSA

一、历史

对称加密模式有一个最大弱点：甲方必须把加密规则告诉乙方，否则无法解密。保存和传递密钥，就成了最头疼的问题。
1976年，两位美国盘算机学家Whitfield Diffie 和 Martin Hellman，提出了一种崭新构思，可以在不直接传递密钥的情况下，完成解密。这被称为"Diffie-Hellman密钥交换算法"。这个算法开导了其他科学家。人们认识到，加密息争密可以使用不同的规则，只要这两种规则之间存在某种对应关系即可，这样就制止了直接传递密钥。
这种新的加密模式被称为"非对称算法"。
（1）乙方生成两把密钥（公钥和私钥）。公钥是公开的，任何人都可以获得，私钥则是保密的。
（2）甲方获取乙方的公钥，然后用它对信息加密。
（3）乙方得到加密后的信息，用私钥解密。
如果公钥加密的信息只有私钥解得开，那么只要私钥不泄漏，通信就是安全的。
1977年，三位数学家Rivest、Shamir 和 Adleman 计划了一种算法，可以实现非对称加密。这种算法用他们三个人的名字命名，叫做RSA算法。从当时直到现在，RSA算法一直是最广为使用的"非对称加密算法"。毫不浮夸地说，只要有盘算机网络的地方，就有RSA算法。
这种算法非常可靠，密钥越长，它就越难破解。根据已经披露的文献，现在被破解的最长RSA密钥是768个二进制位。也就是说，长度超过768位的密钥，还无法破解（至少没人公开公布）。因此可以认为，1024位的RSA密钥根本安全，2048位的密钥极其安全。
二、数学概念

任意给定正整数n，请问在小于等于n的正整数之中，有多少个与n构成互质关系？
盘算这个值的方法就叫做欧拉函数，以φ(n)表现。在1到8之中，与8形成互质关系的是1、3、5、7，所以 φ(n) = 4。
欧拉函数的用处，在于欧拉定理。"欧拉定理"指的是：
如果两个正整数a和n互质，则n的欧拉函数 φ(n) 可以让下面的等式建立：

\[a^{\phi(n)}\equiv_{1}(mod n)\]
也就是说，a的φ(n)次方被n除的余数为1。或者说，a的φ(n)次方减去1，可以被n整除。比如，3和7互质，而7的欧拉函数φ(7)等于6，所以3的6次方（729）减去1，可以被7整除（728/7=104）。
欧拉定理的证明比较复杂，这里就省略了。我们只要记住它的结论就行了。
欧拉定理可以大大简化某些运算。比如，7和10互质，根据欧拉定理，
已知 φ(10) 等于4，所以立刻得到7的4倍数次方的个位数肯定是1。
欧拉定理是RSA算法的核心。理解了这个定理，就可以理解RSA。
还剩下最后一个概念：
如果两个正整数a和n互质，那么一定可以找到整数b，使得 ab-1 被n整除，或者说ab被n除的余数是1。
这时，b就叫做a的模反元素，用于盘算私钥
比如，3和11互质，那么3的模反元素就是4，由于 (3 × 4)-1 可以被11整除。显然，模反元素不止一个， 4加减11的整数倍都是3的模反元素 {...,-18,-7,4,15,26,...}，即如果b是a的模反元素，则 b+kn 都是a的模反元素。
欧拉定理可以用来证明模反元素必然存在。
可以看到，a的 φ(n)-1 次方，就是a的模反元素。
好了，需要用到的数学工具，全部先容完了。RSA算法涉及的数学知识，就是上面这些，下一次我就来先容公钥和私钥到底是怎么生成的。
三、密钥的生成步骤

前面我先容了一些数论知识。 有了这些知识，我们就可以看懂RSA算法。这是现在地球上最紧张的加密算法。
第一步，随机选择两个不相等的质数p和q。
选择了61和53。（现实应用中，这两个质数越大，就越难破解。）p=61 q=53
第二步，盘算p和q的乘积n。
n = 61×53 = 3233
n的长度就是密钥长度。3233写成二进制是110010100001，一共有12位，所以这个密钥就是12bit。现实应用中，RSA密钥一样平常是1024位，紧张场合则为2048位。
第三步，盘算n的欧拉函数φ(n)。
根据公式：
φ(n) = (p-1)(q-1)
算出φ(3233)等于60×52，即3120。
第四步，在1和φ(n)之间随机选择一个整数e（e和φ(n)需要互质）
在1到3120之间，随机选择了17。（现实应用中，经常选择65537。）
第五步，盘算e对于φ(n)的模反元素d。
所谓模反元素就是指有一个整数d，可以使得ed被φ(n)除的余数为1。
ed ≡ 1 (mod φ(n))
这个式子等价于
ed - 1 = kφ(n)
于是，找到模反元素d，实质上就是对下面这个二元一次方程求解。
ex + φ(n)y = 1
已知 e=17, φ(n)=3120，
17x + 3120y = 1
算出一组整数解为 (x,y)=(2753,-15)，即 d=2753。
至此所有盘算完成。
第六步，将n（起初选择的两个质数的乘积）和e（1和φ(n)之间选择的数）封装成公钥，n和d封装成私钥。
在例子中，n=3233，e=17，d=2753，所以公钥就是 (3233,17)，私钥就是（3233, 2753）。
现实应用中，公钥和私钥的数据都采用ASN.1格式表达。
RSA算法的可靠性
回首上面的密钥生成步骤，一共出现六个数字：
p 　　q（选择的两个质数） 　　n（p*q） 　　φ(n)（n的欧拉函数值） 　　e（1和φn之间随机选择的，非φn因子的质数） 　　d（ex + φ(n)y = 1 x的整数解）
这六个数字之中，公钥用到了两个（n和e），其余四个数字都是不公开的。此中最关键的是d，由于n和d组成了私钥，一旦d泄漏，就等于私钥泄漏。
那么，有无大概在已知n和e（公钥）的情况下，推导出d（私钥）？
下面是盘算d的步骤
（1）ed≡1 (mod φ(n))（就是ed - 1 = kφ(n)）。只有知道e和φ(n)，才能算出d。
（2）φ(n)=(p-1)(q-1)。只有知道p和q，才能算出φ(n)。
（3）n=pq。只有将n因数分解，才能算出p和q。
结论：如果因数分解n得到pq，d就可以算出，也就意味着私钥被破解。
可是，大整数的因数分解，是一件非常困难的事变。现在，除了暴力破解，还没有发现别的有效方法。
你大概觉得：把一个数分解成质数的乘积不是很难
那么请你分解下面这个数：（逗号是分级）
1230，1866，8453，0117，7551，3049，4958，3849，6272，0772，8535，6959，5334，7921，9732，2452，1517，2640，0507，2636，5751，8745，2021，9978，6469，3899，5647，4942，7740，6384，5925，1925，5732，6303，4537，3154，8268，5079，1702，6122，1429，1346，1670，4292，1431，1602，2212，4047，9274，7377，9408，0665，3514，1959，7459，8569，0214，3413
事实上它等于这样两个质数的乘积：
33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489 × 36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917
事实上，这大概是人类已经分解的最大整数（232个十进制位，768个二进制位）。比它更大的因数分解，还没有被报道过，因此现在被破解的最长RSA密钥就是768位。
四、加密与解密

有了公钥和密钥，就能举行加密息争密了。
（1）加密要用公钥 (n,e)

假设鲍勃要向爱丽丝发送加密信息m，他就要用爱丽丝的公钥 (n,e) 对m举行加密。这里需要留意，m必须是整数（字符串可以取ascii值或unicode值），且m必须小于n。
所谓"加密"，就是算出下式的c：

\[m^e ≡ c (mod n)\]
爱丽丝的公钥是 (3233, 17)，鲍勃的m假设是65，那么可以算出下面的等式：

\[65^{17} ≡ 2790 (mod 3233)\]
于是，c等于2790，鲍勃就把2790发给了爱丽丝。
（2）解密要用私钥 (n,d)

爱丽丝拿到鲍勃发来的2790以后，就用自己的私钥(3233, 2753) 举行解密。可以证明，下面的等式一定建立：

\[c^d ≡ m (mod n)\]
也就是说，c的d次方除以n的余数为m。现在，c等于2790，私钥是(3233, 2753)，那么，爱丽丝算出

\[2790^{2753} ≡ 65 (mod 3233)\]
因此，爱丽丝知道了鲍勃加密前的原文就是65。
至此，"加密--解密"的整个过程全部完成。
我们可以看到，如果不知道d，就没有办法从c求出m。而前面已经说过，要知道d就必须分解n，这是极难做到的，所以RSA算法保证了通信安全。
你大概会问，公钥(n,e) 只能加密小于n的整数m，那么如果要加密大于n的整数，该怎么办？有两种解决方法：一种是把长信息分割成若干段短消息，每段分别加密；另一种是先选择一种"对称性加密算法"（比如DES），用这种算法的密钥加密信息，再用RSA公钥加密DES密钥。
Rabin

Rabin是RSA算法的一种特例，它使用的是平方剩余问题（Quadratic Residuosity Problem）而不是RSA算法中使用的欧拉函数（Euler's Totient Function）。
在Rabin算法中，公钥和私钥都是一个大素数。加密过程如下：

\[C = P^2 mod N\]
此中：
解密过程如下：

\[P = C^{0.5} mod N\]
此中：
Rabin算法的安全性依赖于平方剩余问题，即很难确定一个数是否是一个大素数的平方剩余。
Rabin算法的长处是盘算速度快，缺点是安全性不如RSA算法。
ElGamal

EIGamal产生的原因：
ElGamal算法是一种非对称加密算法，在1985年由塔希尔•盖莫尔提出，主要用于加密和数字署名。它的产生源于对RSA算法的补充和拓展。具体来说，ElGamal算法的产生主要有以下几个原因：
ElGamal算法的产生是为了满意安全性需求增长、提供多样性和选择、满意数字署名需求以及推动密码学理论研究等多方面原因。它的出现丰富了密码学领域的算法选择，为信息安全提供了更多的保障。
EIGamal算法先容：

Ecc

椭圆曲线密码学（英语：Elliptic Curve Cryptography，缩写：ECC）是一种基于椭圆曲线数学的公开密钥加密算法。
CC 的主要优势是它相比 RSA 加密算法使用较小的密钥长度并提供相当等级的安全性。ECC 的另一个优势是可以定义群之间的双线性映射，基于Weil 对或是Tate 对；双线性映射已经在密码学中发现了大量的应用，例如基于身份的加密。
数字署名类型

RSA 数字署名

原理雷同于 RSA 加密，只是这里使用私钥举行加密，将加密后的结果作为署名。
DSA

数字署名算法（DSA）是用于数字署名的联邦信息处理尺度之一，基于模算数和离散对数的复杂度。DSA是Schnorr和ElGamal署名方案的变体。
美国国家尺度技能研究所（NIST）于1991年提出将DSA用于其数字署名尺度（DSS），并于1994年将其作为FIPS 186采用。已对初始规范举行了四次修订。DSA已获得专利，但NIST已将此专利在全球范围内买断式授权。
DSA的椭圆曲线密码学版本是ECDSA。
DSA算法工作在框架公钥加密、模算数和离散对数问题，这被认为是难解问题。该算法使用由公钥和私钥组成的密钥对。私钥用于生成消息的数字署名，并且可以通过使用署名者的相应公钥来验证这种署名。数字署名提供信息鉴定（接收者可以验证消息的来源），完整性（接收方可以验证消息自署名以来未被修改）和不可否认性（发送方不能错误地声称它们没有签署消息）。
DSA（Digital Signature Algorithm）是一种基于整数分解困难的数字署名算法，其原理依赖于离散对数问题的难解性。DSA是Schnorr署名算法的一个变种，被计划用来提供数字署名的安全性。
ECDSA

ECDSA是Elliptic Curve Digital Signature Algorithm的简称，主要用于对数据（比如一个文件）创建数字署名，以便于你在不粉碎它的安全性的条件下对它的真实性举行验证。可以将它想象成一个现实的署名，你可以识别部分人的署名，但是你无法在别人不知道的情况下伪造它。而ECDSA署名和真实署名的区别在于，伪造ECDSA署名是根本不大概的。
你不应该将ECDSA与用来对数据举行加密的AES（高级加密尺度）相混淆。ECDSA不会对数据举行加密、或阻止别人看到或访问你的数据，它可以防止的是确保数据没有被篡改。
原理非常简单，有一个数学方程，在图上画了一条曲线，然后你在这条曲线上面随机选取了一个点作为你的原点(point of origin)。接着你产生了一个随机数，作为你的私钥(Private key)，最后你用上面的随机数和原点通过一些复杂的魔法数学方程得到该条曲线上面的第二个点，这是你的公钥(Public key)。
当你想要对一个文件举行署名的时候，你会用这个私钥（随机数）和文件的哈希（一串独一无二的代表该文件的数）组成一个魔法数学方程，这将给出你的署名。署名本身将被分成两部分，称为R和S。为了验证署名的精确性，你只需要公钥（用私钥在曲线上面产生的点）并将公钥和署名的一部分S一起代入别的一个方程，如果这个署名是由私钥精确署名过的数字署名，那么它将给出署名的别的一部分R。简单来说，一个数字署名包含两个数字，R和S，然后你使用一个私钥来产生R和S，如果将公钥和S代入被选定的魔法数学方程给出R的话，这个署名就是有效的。仅仅知道公钥是无法知道私钥或者创建出数字署名
身份基加密

公钥身份化
该定义是传统公钥加密的演变，在身份基加密中直接将用户的身份（唯一标识特征）作为公钥。这样一来，每个人只需要保存一个私钥即可。
基于身份的加密方案（IBE）的头脑，最早是由Shamir在1984年提出。方案中不必使用证书，直接将用户的身份（唯一标识特征）作为公钥，这样简化了公钥基础办法（PKI）中基于证书的密钥管理。该头脑提出之后一直没有合适工具实现，成为一个公开问题。直到2001年，Dan Boneh和Matt Franklin利用椭圆曲线上的双线性映射（即Weil对和Tate对）实现了第一个实用的身份基加密方案，这为身份基加密的研究开启了新的篇章。身份基加密主要由以下四个算法构成：

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4