非对称加密算法与RSA详解

思考问题

  • 什么是非对称加密?相对于对称加密优点在哪?缺点在哪?针对这种缺点有什么解决方案?
  • RSA算法的可靠性是基于什么?如何破解RSA?目前秘钥安全位数是多少?

非对称加密

需要两个秘钥来进行加密和解密 。公开秘钥(public key)和私有秘钥(private key)。

公开密钥与私有密钥是一对,如果用公开密钥对数据进行加密,只有用对应的私有密钥才能解密;如果用私有密钥对数据进行加密,那么只有用对应的公开密钥才能解密。

工作过程:
* 1、乙方生成一对秘钥并将公钥公开。
* 2、甲方得到公钥使用该秘钥加密发送给乙方。
* 3、乙方再用保存的私钥对加密的信息进行解密。乙方只能用其私钥解密由公钥加密后的信息。

传输过程中即使截获密文、获得公钥,也无法破解密文,只有乙的私钥才能解密密文。

优缺点:
优点:安全性高,公私分开,不需要像对称加密那样先同步秘钥。
缺点:加解密花费时间长,只适合少量数据进行加密。

常见算法:
RSA、EIgamal、背包算法、Rabin、D-H、ECC(椭圆曲线加密算法)

RSA算法

1977年 R。S、A三人提出。RSA算法是第一个同时用于加密和数字签名的算法。能抵抗大多数密码攻击,秘钥越长越难破解,目前1024位基本安全,2048位秘钥极其安全

在公开密钥密码体制中,加密密钥(即公开密钥)PK是公开信息,而解密密钥(即秘密密钥)SK是需要保密的。加密算法E和解密算法D也都是公开的。虽然解密密钥SK是由公开密钥PK决定的,但却不能根据PK计算出SK。

算法基于: 将两个大质数相乘十分容易,但是想要对其乘积进行因式分解却极其困难。

缺点:
– 1、产生秘钥麻烦,受素数产生技术的限制,难以一次一密
– 2、依赖于大数的因子分解
– 3、速度太慢,n至少600以上,运算代价高 目前较多采用加密单钥,用RSA来给文件秘钥加密,极好的解决了单钥密码分发问题。

减少计算量的加密传输方案:
即使用DES或IDEA进行加密,使用RSA加密DES的秘钥和信息摘要。对方收到用不通的秘钥解密并可核对信息摘要。

RSA算法原理详解:

文章末有关于互质关系、欧拉函数、欧拉定理、模板元素的解释,可以先参考一下其概念。

秘钥生成步骤

  • 1、随机选择两个不相等的质数p和q
    如:选择了61和53

  • 2、计算p和q的乘积n
    如:  n = 61×53 = 3233 n的长度就是秘钥长度。3233二进制是110010100001,共有12位,秘钥长度就是12位,一般1024位,重要场合2048位。

  • 3、计算n的欧拉函数φ(n)
    如:  φ(n) = (p-1)(q-1) 算出φ(3233)等于60×52

  • 4、随机选择一个整数e,条件是1< e < φ(n),且e与φ(n) 互质。
    如:1到3120之间,随机选择了17。(实际应用中,常常选择65537。)

  • 5、计算e对于φ(n)的模反元素d。
    所谓”模反元素”就是指有一个整数d,可以使得ed被φ(n)除的余数为1。  ed ≡ 1 (mod φ(n)),算出一组整数解为 (x,y)=(2753,-15),即 d=2753

  • 6、将n和e封装成公钥,n和d封装成私钥。n=3233,e=17,d=2753,所以公钥就是 (3233,17),私钥就是(3233, 2753)

RSA可靠性

秘钥生成步骤,共出现了六个数字p、q、n、φ(n)、e、d ,公钥用到了两个(n和e),其余四个数字都是不公开的,最关键的是d,因为n和d组成了私钥,一旦d泄漏,就等于私钥泄漏。

如何推导出d?

  • 1、ed≡1 (mod φ(n))。只有知道e和φ(n),才能算出d。
  • 2、φ(n)=(p-1)(q-1)。只有知道p和q,才能算出φ(n)。
  • 3、n=pq。只有将n因数分解,才能算出p和q。

如果n可以被因数分解,d就可以算出,也就意味着私钥被破解。

大数因数分解的困难性代表了RSA算法的可靠性,目前只破解到了768位,而且只能暴力破解

加密解密

加密公式:  me ≡ c (mod n)
爱丽丝的公钥是 (3233, 17),鲍勃的m假设是65,那么65^17 ≡ 2790 (mod 3233),于是,c等于2790。

解密公式:  cd ≡ m (mod n)
爱丽丝拿到鲍勃发来的2790以后,就用自己的私钥(3233, 2753)进行解密,c的d次方除以n的余数为m。现在,c等于2790,私钥是(3233, 2753),2790^2753 ≡ 65 (mod 3233)原文就是65

公钥(n,e) 只能加密小于n的整数m,那么如果要加密大于n的整数,该怎么办?

  • 一种是把长信息分割成若干段短消息,每段分别加密;
  • 另一种是先选择一种”对称性加密算法”(比如DES),用这种算法的密钥加密信息,再用RSA公钥加密DES密钥。

附属基本概念

互质关系
定义:两个整数除1以外没有其他公因子
如:
– 1、任意两个质数构成互质关系
– 2、一个数是质数,另一个只要不是前者的倍数,两者构成互质关系
– 3、如果两个数之中,较大的那个数是质数,构成互质关系
– 4、1和任意数都是互质关系
– 5、p是大于1的整数,那么p和p-1构成互质关系
– 6、p是大于1的奇数,那么p和p-2构成互质关系

欧拉函数

任意给定正整数n,请问在小于等于n的正整数之中,有多少个与n构成互质关系?计算这个值就叫做欧拉函数
思考如下几种情况:
1、n为1 则 φ(1) = 1
2、n是质数 则 φ(1) = n-1
3、n是质数的某次方,即n = p^k 则比如 φ(8) = φ(2^3) =2^3 – 2^2 = 8 -4 = 4。
4、n可以分解成互质的整数之积  n = p1 × p2 则  φ(n) = φ(p1p2) = φ(p1)φ(p2)
5、因为任意一个大于1的正整数,都可以写成一系列质数的积。推到出欧拉函数公式!

欧拉定理
如果两个正整数a和n互质,则n的欧拉函数 φ(n) a的φ(n)次方被n除的余数为1。

模板元素
如果两个正整数a和n互质,那么一定可以找到整数b,使得 ab-1 被n整除,或者说ab被n除的余数是1。

致谢&参考资料:
在此致谢!

http://bank.hexun.com/2009-06-24/118958531.html
http://www.ruanyifeng.com/blog/2013/06/rsa_algorithm_part_one.html
http://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html

0条留言