RSA算法是当前最出名、应用最广泛的公钥系统,若它们除以正整数

可以先看看这一个录像:
RSA_Encryption_Algorithm

非对称加密(2)非对称加密算法

大旨流程很粗略,那么公钥加密,私钥解密的算法原理到底是何许呢?本节简要讲演RSA算法、DSA算法、ECC算法、Diffie-Hellman算法的基本原理,其中涉嫌众多数论、离散数学以及解析几何方面的数学知识,感兴趣的读者可以借此加强相关理论基础。

1、同余(合同式)

多个整数ab,若它们除以正整数m所得的余数相等,则称ab对于模m同余

记作图片 1

比如1≡13
(mod 12),可以了然为时钟上1点和13点的指针地点相同

关键性质

vcmFsbCBuIFxpbiBcbWF0aGJie1p9IFxcIGFebiBcZXF1aXYgYl5uIFxwbW9ke219LCBcZm9yYWxsIG4gXGluIFxtYXRoYmJ7Tn1eMFxlbmR7Y2FzZXN9″
class=”tex” src=”http://up.2cto.com/2011/1128/20111128043101835.png
style=”border-top-style: none; border-right-style: none;
border-left-style: none; border-bottom-style: none” />

例如1^5=1,13
^5=371293=30941*12+1

即1^5≡1≡13
^5(mod 12)

公开密钥

Perwork:
私钥:Sender和Receiver预先约定加密和解密方案,向其别人保密。
以此实现相比较难:向其旁人保密。即使你是个商店,很两人要和你联系,发送者可能和您或多或少关乎也不曾,怎么保密。
需求:Sender素不相识,发送音信需要保密,加密方案必须当众。【就和邮箱一样,所有人都足以向你公开的的信箱里投信件,可是唯有你才有钥匙(私有的)取信件】
公钥:加密方案向所有人公开,解密方案唯有Receiver知道,对任何所有人(包括Sender),Sender和除Receiver外所有人都是相同的,【Sender把信件放入Receive信箱了,Sender就不能够再来看信件内容啦】

这就要求加密很容易,可是解密很难的算法!从跳板里跳入水里容易,想跳回去就不是那么容易啊。

先用一下示范讲下流程:


  1. 概念一个消息集合

    Zset={0,1,2,3,…90}.

本条就是一定于26个英文字母,只要知道这26个假名,你就足以拼出任何想要的音信,只是咱们把26个扩展为了91个。

  1. Sender 要发送的音信为

    %%现实生活中:
    Msg = ”早上一头进餐”;
    %%等价为音信集合里是:只要Reciver得到的情节最后为{1,2,3,4,5,6}就足以精通是现实的“深夜联名吃饭”
    Msg ={1,2,3,4,5,6};

这边的Msg就是一个当着。

  1. Sender 把音信编码为明文后,还要举办加密!

把公开的每一个因素都映射为另一个唯一的值(密文:可以公开的值)

 

%%明文
Msg = {1,2,3,4,5,6};
%%使用加密:C = A^5(mod 91)
%%A^5 -->
NewMsg = {1,32,243,1024,3125,7776}
%%mod 91  对91取余得到密文
NewMsg = {1,32,61,23,32,41};

简易来说:加密过程为:

%%  明文             公式:5次方后对91取余         密文
     A -------------> A

5

 mod 91 -------------->C

说到底的承保:A和C相对是一对一映射关系。

Question1: 那么这么些密文怎么保证不被破解呢?

我们试下从那公开的加密公式和密文反推之

图片 2

可以观察,通过穷举,我们还是可以够拿到结果的,但这些计算次数也是指数增长的,且计量开根号得整数操作很要耗时,

一个算法最后逼得人只可以用穷举来解密,那么就是打响啦,

思考:一经公式里面不是5次方,而是三位数,四位数的次方,这总计量就更大。

3 . sender把这密文发给Receiver 加密工作形成

  1. 解密:Receive知道音信比Sender多的就是这一个91是怎么来的,那多少个是重中之重。

4.1 91 = 7*13
(实现利用中,会设定为2个可怜大的素数相乘,让Sender看不出是哪2个素数来,大家为了演示简单,假定Sender不会拿到91=7*13以此结果,唯有Receiver知道)

那么些算法就是应用了这点:2个素数乘积的结果很容易,可是想转头把结果反推为哪2个素数相乘很难。所有公开密钥都是正着做容易,反过来就是很难

4.2
根据费马小定理:和折腾相除法可以拿到:

5d = 1+(13-1)*(7-1)*k

从以上方可“容易穷举出一个”k=2时 :5*29 = 1+(13-1)*(7-1)*2

4.3 接着我们对密文C再乘29次方后对91取余就足以一向拿到明文啦

图片 3

您只要了解相当29,就可以拿到破解啦!!!!!

是不是很神奇!!!!!!当然我们依然有众多迷惑的,比如:

为啥选5,91,这多少个数字有怎么样要求?接下去,大家先理一下方面的手续:

 

步骤 示例
取2个大质数:p,q p=7,q=13
密钥:n=p*q,h 是一个与(p-1)(q-1)互质的数, 公开n 和 h ,p,q不公开 n =91,h = 5(与72互质)
加密(公开)C = Ah (mod n) A = 明文,h=5,n=91,C= 密文
解密(保密)hd = 1+(p-1)(q-1)k—->A = C d mod 91 5d = 1+72*k, 当k=2时,d=29成立
解密完成 密文乘方29 再对91取模 得到明文

 

原理注解 :

  1. 取2个很大的不对等的质数p,q ;

  2. m = p*q

3.
根据欧拉函数:比m小的质数个数r
= φ(N) = φ(p)*φ(q) = (p-1)*(q-1)

  1. 选料一个与R互质的数e

5.
根据欧几里德(辗转相除)定理:2个互质的数一定餍足:e*x
– r*y =1;

  1. 上式等价为: e*d – r*k = 1;

7.密文c ,明文a , 加密 a e = c (mod m);

  1. 解密: c d = a (mod m),这一个结论是
    大家要证实的,

  2. cd = ae\*d = a 1+r\*k =a*a
    r\*k

所以要是表达: a*a r\*k = a(mod m) —->a
r\*k = 1
(mod m)

10
.根据费马小定理:

图片 4:

a r\*k = (a k)r = 1 (mod m).


数学真有意思…….

RSA算法

RSA算法是眼前最出名、应用最广大的公钥系统,1978年由美国麻省体育大学的Ron Rivest、 Adi Shamir
和雷纳德(Leonard) Adleman在舆论《得到数字签名和公开钥密码系统的方式》中指出的。这是一个按照数论的非对称(公开钥)密码体制,接纳分组加密方法。其名目来自于三个发明者的真名首字母。它的安全性是基于大整数素因子分解的困难性,而大整数因子分解问题是数学上的头面难题,至今从不行之有效的情势予以解决,由此得以确保RSA算法的安全性。RSA系统是公钥系统的最富有超人意义的点子,大多数选拔公钥密码举办加密和数字签名的成品和专业应用的都是RSA算法。

RSA算法是第一个既能用于数据加密也能用来数字签名的算法,因而它为公用网络上信息的加密和识别提供了一种基本的法子。它通常是举人成一对RSA 密钥,一个是保密密钥,由用户保存;另一个为公开密钥,可对爷爷开,甚至可在网络服务器中登记,人们用公钥加密文件发送给个人,个人就可以用私钥解密接收。为加强保密强度,RSA密钥一般为1024或者2048位。

RSA算法的做事原理如下:

步骤 1  随便选取五个例外的大质数p和q,总结乘积r=p*q。

步骤 2   任意接纳一个大整数e,e与(p-1)*(q-1)互质,整数e用做加密密钥。注意:e的挑三拣四是很容易的,所有大于p和q的质数都可用。

步骤 3  确定解密密钥d: d * e = 1 mod(p –
1)*(q – 1)依照e、p和q可以容易地测算出d。

步骤 4  当面整数r和e,但是不公开d。

步骤 5  将明文P(P是一个小于r的平头)加密为密文C,总计格局为C =
P^e  mod r 。

步骤 6  将密文C解密为明文P,总计方法为: P = C^d modulo r 。

而是只按照r和e(不是p和q)要总括出d是不容许的。因而,任何人都可对公开举办加密,但唯有授权用户(知道d)才可对密文解密。

倘使你对RSA算法的数学声明感兴趣的话,可以看增添阅读。

推而广之阅读   RSA算法的数学注解

定理  若 p, q 是相异质数, rm == 1 mod (p-1)(q-1); a 是自由一个正整数,b == a^m mod pq, c == b^r mod pq, 则 c == a mod pq 。

费马小定理    m 是任一质数, n 是任一整数, 则 n^m = = n mod m 。(或者一旦 n 和 m 互质, 则 n^(m-1) = = 1 mod m) 。
证明
因为 rm = = 1 mod (p-1)(q-1), 所以 rm = k(p-1)(q-1) + 1, 其中 k 是整数 。
因为在 modulo 中是 preserve 乘法的 

x = = y mod z  and  u = = v mod z  =>  xu =
= yv mod z

 所以 

c = = b^r = = (a^m)^r =
= a^(rm) = = a^(k(p-1)(q-1)+1) mod pq 
1. 尽管 a 不是 p 的翻番, 也不是 q 的倍数时,    则

 a^(p-1) =
= 1 mod p (费马小定理)  =>  a^(k(p-1)(q-1)) =
= 1 mod p 
       a^(q-1) =
= 1 mod q (费马小定理)  =>  a^(k(p-1)(q-1)) =
= 1 mod q 
   所以 p, q 均能整除

 a^(k(p-1)(q-1)) – 1  =>  pq | a^(k(p-1)(q-1)) – 1 
   即 

a^(k(p-1)(q-1)) == 1 mod pq    =>  c = = a^(k(p-1)(q-1)+1) =
= a mod pq 
2. 假使 a 是 p 的翻番, 但不是 q 的倍数时,    则 

a^(q-1) == 1 mod q (费马小定理) 
   =>  a^(k(p-1)(q-1)) =
= 1 mod q 
   =>  c = = a^(k(p-1)(q-1)+1) = = a mod q 
   =>  q | c – a 
   因 p | a 
   =>  c = = a^(k(p-1)(q-1)+1) = = 0 mod p 
   =>  p | c – a 
   所以

 pq | c – a  =>  c = = a mod pq 
3. 倘使 a 是 q 的翻番, 但不是 p 的倍数时, 表明同上 。
4. 假若 a 同时是 p 和 q 的翻番时, 则

 pq | a 
   =>  c = = a^(k(p-1)(q-1)+1) == 0 mod pq 
   =>  pq | c – a =>  c = = a mod pq 

在做编码解码时, 限制 0 <= a < n, 0 <= c < n, 这就是说 a =
=c, 所以这一个历程着实能一鼓作气编码解码的职能。

为了印证该算法的劳作经过,下边给出一个简易例子。分明,这里不得不取很小的数字,可是如上所述,为了保险安全,在实质上运用上所用的数字要大得多。

选取p=3,
q=5,则r=15,(p-1)*(q-1)=8。选取e=11(大于p和q的质数),通过d *
11 = 1 modulo 8,计算出d
=3。

一经明文为整数13。则密文C为 :

 C = P^e mod r

 = 1311 mod 15

 = 1,792,160,394,037 mod 15

 = 7

卷土重来明文P为:

 P = C^d mod r

= 73 mod 15

= 343 mod 15

= 13

因为e和d互逆,公开密钥加密方法也同意利用这样的章程对加密音讯举办”签名”,以便接收方能确定签名不是鱼目混珠的。

RSA算法解决了大量网络用户密钥管理的难题,这是公钥密码系统相对于对称密码系统最出色的优点。不过它同时也存在一定的弱项:

1)发生密钥很麻烦,受到素数暴发技术的范围,因此难以做到两遍一密。

2)安全性。RSA的安全性倚重于胎元的因子分解,但并从未从理论上证实破译RSA的难度与命局分解难度非常。近日,人们已能诠释140多少个十进制位的大素数,这就要求使用更长的密钥,速度更慢;此外,目前人们正在积极寻找攻击RSA的不二法门,如采用密文攻击,一般攻击者是将某消息伪装(Blind),让具有私钥的实业签署。然后,经过计量就可收获它所想要的音信。实际上,攻击利用的都是同一个通病,即存在这样一个事实:乘幂保留了输入的乘法结构:
( XM
)d =
Xd *Md mod n。前面早已关系,这多少个本来的题材来自于公钥密码系统的最实用的表征:每个人都能采纳公钥。但从算法上不能化解这一问题,重要方法有两条:一条是采纳好的公钥协议,保证工作经过中实体不对别的实体任意暴发的音讯解密,不对友好一无所知的音讯签名;另一条是永不对第三者送来的自由文档签名,签名时首先应用One-Way Hash Function对文档作HASH处理,或同时采用不同的签名算法。除了使用集体模数,人们还尝试一些运用解密指数或φ(n)等攻击。

3)速度慢。由于RSA
的分主任度太大,使运算代价很高,尤其是速度较慢,较对称密码算法慢几个数据级;且随着大数分解技术的提升,这多少个尺寸还在追加,不便民数据格式的准绳。近日,SET(Secure Electronic Transaction)协议要求CA采取2048比特的密钥,其他实体使用1024比特的密钥。为了速度问题,近来人们广泛运用单、公钥密码组合使用的主意,优缺点互补:单钥密码加密速度快,人们用它来加密较长的文件,然后用RSA给文件密钥加密,极好地解决了单钥密码的密钥分发问题。

2、欧拉函数(Euler’s totient function)

 

欧拉函数 φ(n)是个别或等于n的数中与n互质的数的多少,例如φ(9) = 6,因为比9小的数中与9互质的有1,
2, 4, 5, 7,8两个数,所以9的欧拉函数为6。

总括办法:

将n分解为质数相乘的花样

图片 5,每个p*i*都是质数

则欧拉函数

 

 

图片 6

图片 7

例如

图片 8

两条结论

若n为质数,则φ(n)=n-1

若m与n互质,则 φ(mn) = φ(m)φ(n)

DSA算法

DSA(Digital Signature
Algorithm,数字签名算法)是Schnorr和ElGamal签名算法的变种,被美利坚联邦合众国NIST作为DSS(DigitalSignature Standard,数字信号标准)。DSA算法是基于整数有限域离散对数难题的,其安全性与RSA相似。DSA的一个最紧要特点是六个素数公开,这样,当使用别人的p和q时,尽管不亮堂私钥,也能确认它们是否是随机暴发的,依然作了手脚。RSA算法却做不到。

(1) 
DSA算法参数

p:L
bits长的素数。L是64的倍数,范围是512到1024;

q:p – 1的160bits的素因子;

g:g = h^((p-1)/q) mod
p,h满足h < p – 1, h^((p-1)/q) mod
p > 1;

x:x < q,x为私钥;

y:y = g^x mod p ,(
p, q, g, y )为公钥;

H( x ):One-Way Hash函数。DSS中选用SHA( Secure Hash Algorithm
)。

里面,p、 q、g可由一组用户共享,但在骨子里运用中,使用集体模数可能会带来一定的胁迫。

(2) 
签名及表明协议

1)        p爆发随机数k,k < q。

2)        p计算:

r = ( g^k mod p ) mod
q

s = ( k^(-1)(H(m) + xr))
mod q

签名结果是( m, r, s )。

3)        证实时统计:

w = s^(-1)mod
q

u1 = ( H( m
) * w ) mod q

u2 = ( r * w ) mod
q

v = (( g^u1 * y^u2 ) mod
p ) mod q

若v =
r,则认为签名有效。

(3) 
安全性

DSA首要倚重于整数有限域离散对数难题。素数 P 必须丰硕大,且p-1至少含有一个大素数因子以抵御Pohlig & Hellman算法的抨击。M一般都应利用音信的HASH值(官方推荐为SHA算法)。DSA的安全性关键倚重于p和g,若采用不当则签名容易伪造,应保证g对于p-1的大素数因子不可约。个人认为:DSA的安全性要次于ECC, 与RSA连镳并驾。可是,在DSA算法的求证过程中,
R和S
是以公开格局现身的,这一点很容易被恶意攻击者利用。

DSA算法在破解时首要的参数就是X,按照 Y = G^X mod P ,只要了解P,G,Y,Q 且能表达出 X
,就可以伪造R、S,从而写出KeyGen了。

3、费马小定理与欧拉定理

 

费马小定理

若a为整数,p为质数则

图片 9

如果a不是p的倍数,可写为

 

图片 10

 

推广:欧拉定理

对其它两互质正整数am图片 11,有

ECC**算法**

ECC(Elliptic Curve
Cryptosystem,椭圆曲线密码体制)算法中,椭圆曲线指的是由韦尔丝特拉斯(Weierstrass)方程所规定的平面曲线。如下:

 y2+a1xy+a3y=x3+a2x2+a4x+a6
(1)                                               
    

若F是一个域(ai
∈F,i=1,2,…,6),且满足式(1)的数偶(x,y)称为F域上的椭圆曲线E的点。F域可以是合理合法数域,还足以是有限域GF(Pr)。椭圆曲线平时用E表示。除了曲线E包含的点,还有一个无穷远点O。

在ECC中,利用了概念在有限域上的椭圆曲线。其方程如下:

y2=x3+ax+b(mod p)(4a3+27b2(mod p)≠0 其中,x,y,a,b
∈Fp)(2)                  

这边p是素数,a和b为四个小于p的非负整数。满意式(2)的点(x,y)和一个无穷点O就整合了椭圆曲线E。

椭圆曲线离散对数问题ECDLP定义如下:

给定素数p和椭圆曲线E,对 Q=kP,在已知P,Q的气象下求出小于p的正整数k。

可以印证,已知k和P总结Q相比便于,而由Q和P统计k则相比较困难,至今从不实用的方法来化解那个题目,这就是ECC原理之所在。

ECC与RSA相比,有以下的独到之处:

q  安全性能更高。如160位ECC与1024位RSA、DSA有一样的张家界强度。

q  总计量小,处理速度快。在私钥的处理速度上(解密和签约),ECC远 比RSA、DSA快得多。

q  存储空间占据小。ECC的密钥尺寸和序列参数与RSA、DSA相比要小得多, 所以占用的仓储空间小得多。

q  带宽要求低。

4、模反

图片 12

图片 13

或写成

 

图片 14

例如

 

 

图片 15

图片 16

当x=4时上式创立,所以4是3的模反,

在意:4并不是唯一的解,在4的底子上添加模(11)的翻番依旧满意上式,例如15,26,37,48等

可是寻找那样的x并不是侦破,可以用上面的壮大欧几里得算法。

 
 
5、扩充欧几里得算法
用作欧几里得算法的恢弘,寻找的是满意ax + by = gcd(a,b)的x和y。

 

当a,b互质时,可以看出x是a在b模下的反(ax=1(mod y))
;可以看出y是b在a模下的反(by=1(mod x))

本人用python写了一个递归实现
 

 

def extended_gcd(a, b): 
    if (b == 0): 
        return (1, 0) 
    else: 
        q, r = a/b,a%b 
        s, t = extended_gcd(b, r) 
        return (t, s – q * t) 
         

运行实例,如故拿地点的例子,求3在模11下的反

 

 

 

print extended_gcd(3,11) 

取得结果:

(4, -1) 

 

意即4*3+(-1)*11=1

为此可得的解为4

 

 

 

 

 

6、密钥生成
分选五个素数p和q

计算n=pq

总结φ(n) = (p – 1)(q – 1)  (可由2中的六个结论推出)

接纳e使得 1 < e < φ(n)且e与φ(n)互质,e和n作为公钥

计量 d = e–1 mod φ(n); d和n作为密钥

 

7、加密
将公钥(n,e)传送给对方,自己保留密钥。对方对公开举办加密。

明文m,密文c,由密钥(n,e)可得

c = me (mod n).

8、解密
接收对方传过来的密文c后方可用密钥(d,n)举行解密,得到明文m

m = cd (mod n).

 

9、实现
用python把流程走一次

 

 

 

>>> from Euclid_Ex import extended_gcd 
#导入下面定义的扩大欧几里得算法 
>>> p,q=61,53 
#定义p,q,并求得n和phi 
>>> n=p*q 
>>> n 
3233 
>>> phi=(p-1)*(q-1) 
>>> phi 
3120 
#慎选17看作公钥 
>>> e=17 
#计量密钥 
>>> extended_gcd(e,phi) 
(-367, 2) 
#算算得到的是负数,不是我们所想要的,遵照事先提过的,只要添加模就足以了 
>>> -367+phi 
2753 
#获取了密钥为2753 
>>> d=2753 
#在此已经拿到了加密和解密所急需的密钥(d,n)和公钥(e,n)了,下边对明文m实行加解密 
>>> m=65 
>>> c=m**e%n 
>>> c 
2790L 
#公然由公钥加密后拿走密文2790 
>>> m=c**d%n 
>>> m 
65L 
#密文由密钥解密后得到明文65,与前边的音信一致 

摘自 boksic的专栏

Diffie-Hellman算法

是因为该算法本身限于密钥互换的用途,许多商用产品用做密钥交流技术,因而该算法平时号称Diffie-Hellman密钥交流算法。这种密钥交换技术的意在使得六个用户安全地互换一个神秘密钥以便用于将来的报文加密。

Diffie-Hellman密钥互换算法的灵光依赖于总结离散对数的难度。离散对数的定义如下:

第一定义一个素数p的原根,为其各次幂发生从1
到p-1的拥有整数根,也就是说,倘若a是素数p的一个原根,那么数值

                 
a mod p, a2 mod p, …, ap-1 mod p

是各不相同的平头,并且以某种排列模式结合了从1到p-1的享有整数。

对于一个整数b和素数p的一个原根a,可以找到惟一的指数i,使得

                 
b = ai mod p     其中0
≤ i ≤(p-1)

指数i称为b的以a为基数的模p的离散对数或者指数。该值被记为inda ,p(b)。

遵照此背景知识,可以定义Diffie-Hellman密钥交流算法。该算法描述如下:

1)有两个全局公开的参数,一个素数q和一个平头aaq的一个原根。

2)假设用户A和B希望互换一个密钥,用户A选用一个当做个人密钥的妄动数XA<q,并盘算公开密钥YA=aXA
mod q。A对XA的值保密存放而使YA能被B公开拿到。类似地,用户B采用一个民用的自由数XB<q,并盘算公开密钥YB=aXB
mod q。B对XB的值保密存放而使YB能被A公开拿到。

3)用户A暴发共享秘密密钥的总结方法是K = (YBXA mod q。同样,用户B发生共享秘密密钥的计量是K = (YAXB mod q。这五个总结暴发同样的结果:

              K = (YBXA mod q

                =
aXB mod qXA mod q

                = (aXBXA mod q

                = aXBXA mod q

                = (aXAXB mod q

                = (aXA mod qXB mod q

                = (YAXB mod q

从而一定于双边一度交换了一个同一的私房密钥。

4)  因为XA和XB是保密的,一个敌对方能够利用的参数唯有qa、YA和YB。因此敌对方被迫取离散对数来规定密钥。例如,要收获用户B的机密密钥,敌对方必须先总计

               XB = inda\ ,q(YB

下一场再利用用户B采纳的一律方法总括其地下密钥K。

Diffie-Hellman密钥互换算法的安全性依赖于如此一个事实:即使总结以一个素数为模的指数相对容易,但总计离散对数却很不便。对于大的素数,统计出离散对数几乎是无法的。下边以一个概括的例证来表明。

密钥交流基于素数q = 97和97的一个原根a =
5。A和B分别选用个人密钥XA = 36和XB =
58。每人统计其公开密钥:

                YA = 536 = 50 mod 97

                YB = 558 = 44 mod 97

它们相互获取了公开密钥之后,各自通过总结拿到双方共享的机密密钥如下:

                    K =
(YBXA mod 97 = 4436
= 75 mod 97

                    K = (YAXB mod 97 = 5058
= 75 mod 97

从|50,44|出发,攻击者要总结出75很不容易。实际应用环境类似下边的始末。

近期假设有一组用户(例如一个局域网上的有所用户),每个人都暴发一个经久的民用密钥XA,并总括一个当面密钥YA。这多少个公开密钥数值连同全局公开数值qa都存储在密钥管理基本。在任哪一天刻,用户B都能够访问用户A
的当众数值,总结一个诡秘密钥,并使用这些密钥发送一个加密报文给A。因为只有A和B可以确定这多少个密钥,其他用户都爱莫能助解读报文。接收方A知道只有用户B才能动用此密钥生成那些报文。鉴于此,ECC加密算法既可确保加密特色又可实现鉴别效能。

———————–注:本文部分情节改编自《.NET 安全揭秘》

 

相关文章