密码学基本原理(下)

阅读量    61181 | 评论 1

分享到: QQ空间 新浪微博 微信 QQ facebook twitter

连载系列——It works,why?

在做密码学相关项目的时候,经常可以看到很多程序员,对密码学有哪些技术,每个技术怎么用一无所知。在选择合适的密码学技能来达成目标的时候,总是选择自己最熟悉的方案,这不一定是最好的方案,甚至不一定是合格的方案。后果往往有两个:一个是很多代码潜伏着安全隐患;另一个则是,很多算法并不如想象中那样工作。我们时时可以见到程序员对着电脑沉思,这个算法不能工作,Why?又时时可以见到,这个算法能工作,Why?因此我将在「It works,why?」系列文章中,论述常见的算法和常见应用,其中的“Why”。

《密码学基本原理(下)》本文简述了公钥密码学的常见算法和相关特征。

 

Public-key signature

公钥签署为三个函数:生成G,签署为S,校验为V。对任意数据d和密钥p:

  1. G可以生成私钥和公钥。即s,p=G(),其中s为私钥,p为公钥。公钥可以公开;
  2. 对于签署获得的v=S(d, s),可以用V(d, v, p)来检验d和v是否成对;
  3. 攻击者在得知S,V,v,d,p的情况下,无法反推s。

 

单向陷门函数与DH密钥交换问题

上面说了公钥密码系统的目标,下面我们说说公钥系统的一般规律。公钥系统的一般原则是,用户持有私钥s,公开公钥p,然后利用单向陷门函数完成特定密码学目标。

假定我们有一个集合G,是集合G上的一个运算,满足交换率和结合率,O是集合G上的一个特定元素(或更普遍的,一类元素),同时具有一个特点,求y=xO非常简单,求x使得对已知y有y=xO非常困难。

Kx的普遍算法,就是A和B各自随机生成一个元素ka和kb,计算pa=kaO和pb=kbO,再计算k=kbpa=kapb。由于kbpa=kb(kaO)=(kbka)O=(kakb)O和kapb=ka(kbO)=(kakb)O,因此k相等。同时由于*求逆非常困难,因此攻击者无法推出ka或kb,从而无法推出k。

Integrated Encryption Scheme

IES是一种基于Kx的加密算法,这种算法是非确定性的。

基于某种单项陷门函数,假设我们有某人A的公钥pa,如何利用pa加密数据,使得只有A能解开?

首先,生成随机密钥kb和公钥pb,而后计算k=kbpa,再用k生成密钥k’,用k’加密数据,并将pb和秘密数据c一同发送。接收者使用pb和ka计算k=kapb,进而可以得知密钥k’,从而可以解出明文。在IES体系中,用k获得k’的算法一般是某种KDF。

IES是一种非确定性加密,他很大程度上依赖于生成的随机密钥的安全,一旦有了随机密钥kb,就可以根据pa算出k,进而算出k’,如果随机密钥生成过程很容易被攻破,那么算法上再保障安全性也是没用的。

MQV

MQV是一种基于DH的带认证Kx算法。他首先假定Alice和Bob互相可信的持有对方的公钥,而后讨论如何在非可信信道上生成一个临时的公共秘密。注意这是一种非确定性算法(几乎所有的Kx都应该是非确定性算法,否则有被攻击导致前向安全性问题的可能性)。而且该算法不需要公钥系统带有签署能力(DH_RSA实际上是利用签署互信的非认证性Kx算法),验证能力在算法内部。

Diffie-Hellman key exchange

Diffie-Hellman算法是密钥交换算法中最典型的一个,其依赖的是求离散对数问题(DLP)的复杂性。抽象的说,就是设定集合G为正整数集合,运算为sg = g^s mod p,其中p为预先约定变量,具体算法如下:

通信双方 Alice 和 Bob 需要约定好算法参数:一个素数 p 作为模数,一个素数 g 作为基数(生成元),可对外公开。

对 Alice 来说,先想好一个自然数 a 作为私钥,然后计算 pa = g^a mod p 作为公钥;

对 Bob 来说,先想好一个自然数 b 作为私钥,然后计算 pb = g^b mod p 作为公钥。

之后互换公钥,然后

Alice 计算出 k = pb^a mod p;

Bob 计算出 k = pa^b mod p。

我们取wiki上的例子:

  1. Alice和Bob约定p=23,g=5;
  2. Alice选取a=4,计算pa=5^4mod23=4。Alice将4发送给Bob;
  3. Bob选取b=3,计算pb=5^3mod23=10。Bob将10发送给Alice;
  4. Alice计算k=10^4mod23=18;
  5. Bob计算k=4^3mod23=18。

算法可以确保以下几点:

Alice 与 Bob 计算出的 k 必定是一致的;

双方都无法根据已知的数来推算对方私钥;

第三方可以看到 p、g、pa、pb、但无法推算出 a 与 b ,因此也无法推算 k。

 

RSA系列算法

RSA是非对称密码算法中最著名的一项。这个算法包含了以下功能:

  1. 生成算法G
  2. 加密算法E
  3. 解密算法D
  4. 签署算法S
  5. 验证算法V
  6. 密钥交换算法

特别需要注意一点,RSA的加密算法并没有使用IES体制,RSA算法族里自带了加解密和签署。从某种意义上说,RSA其实和上面说的一般性单向陷门函数算法为基础的算法有所区别。

生成算法

  1. 首先有素数p和q,称为prime1和prime2;
  2. 计算n=p*q,称为modulus;
  3. 求n的Euler totient functionφ(n)=(p-1)*(q-1);
  4. 选择一个和φ(n)互素的数e,称为public exponent;
  5. 计算e对欧拉函数φ(n)的模反元素d,使得ed = 1 mod φ(n)。d称为private exponent。基于欧拉公式我们可知e^φ(n) = 1 mod φ(n),即e*e^(φ(n)-1) = 1 mod φ(n)。因此可以取d = e^(φ(n)-1) mod φ(n);
  6. 公开modulus和public exponent,为公钥。保留modulus和private exponent,作为私钥,其余需要保密(因为可以推出整套公私钥)。

PS: 3中说是Euler function,实际上Carmichael function(https://en.wikipedia.org/wiki/Carmichael_function)就行,欧拉函数总是其整数倍,因此也能工作,就是数字比较大。Carmichael函数λ(n)=lcm(p-1, q-1)=(p-1)*(q-1)/gcd(p-1, q-1)=φ(n)/gcd(p-1, q-1)。

例如取wiki上的例子:

  1. p=61,q=53;
  2. n=61*53=3233;
  3. φ(n)=60*52=3120(原文里,取的是Carmichael函数,λ(n)=3120/gcd(61,53)=780);
  4. e=17(在实践中,这个值一般都是65537);
  5. d = 17^(3120-1) mod 3120 = 2753(原文取d=413)。

在这里,n和d为私钥,n和e为公钥,通过n和e无法构造e。这里可能会引起一个误解:既然e和d两者对称,一个加密一个就能解密,一个签署一个就能验证,所以公开一个隐藏另一个就行,具体是哪个是都可以的,但是实践中,e经常取65537,是一个相对比较小的数,如果公开比较长的数d,那么通过猜测计算e(即使不是65537)将不会是一个太难的事,因此实践中总是固定并公开e,保留比较复杂的数d。

同时我们可以看到,一般来说,通过n和d也无法构造e。即通过私钥无法推导出公钥(e能够被猜出来是另一回事)。要构造e和d,正常方法就是使用p和q计算Eular function。

加密解密算法

对于数据m,密文c的计算方法为:

c = (m^e) mod n

解密算法则为:

m = (c^d) mod n

由mod n可以看出,密文最大长度和n同数量级,因此modulus又被称为RSA算法的块长度,注意上面求d的时候用的是Euler function,现在用的是Modulus,两者不一致。

实例还是用wiki,m=65。

c = 65^17 mod 3233 = 2790
m = 2790^413 mod 3233 = 2790^2753 mod 3233 = 65

可以看到,d有多个合法值,而且使用Carmichael函数还是Euler函数并无关系。

签署验证算法

和加解密算法类似,对消息m,先使用私钥d进行运算的结果v,可以用公钥运算得到原始数据d。

例如m=65,我们来验证签署。

v = 65^413 mod 3233 = 588
m = 588^17 mod 3233 = 65

注意,这个签署算法实际可以解出原始数据,这和普通的验证算法很不一样。一般而言,签署算法根本没必要,或者无法解出原始数据。

密钥协商算法

根据这里:https://security.stackexchange.com/questions/8343/what-key-exchange-mechanism-should-be-used-in-tls,RSA为基础的交换算法有三种:

RSA: 客户端随机选择一个秘密s,用服务器的公钥加密,服务器用私钥解密;

DH_RSA: 服务器给出一个静态DH公钥,同时这个公钥使用服务器cert对应的私钥签署以防篡改;

DHE_RSA: 类似于DH_RSA,但是服务器动态生成一个DH公钥。E是ephemeral的意思。

由于服务器DH公钥被签署了,因此MITM的攻击者无法给用户一个自己控制了私钥的DH公钥。因而无法冒充服务器端。

当然,我们可以根据密码学常识推断出,DH_RSA和DHE_RSA是前向安全的,而RSA本身是前向非安全的。

最佳实践

RSA目前来看还是最经久耐用的非对称密码系统,他支持的能力极为全面,包含了加解密,签署,Kx等领域,相比起来,ECC的加解密就不是很强。有ECIES,但是很多地方没有实现。

正确使用RSA有一定的困难,因为数论领域(准确说是number field sieve)的飞速发展,所以RSA长度也是飞速增加。目前1024位的RSA已经不安全了,建议值是2048,计算一下就知道,这需要256字节。虽然选用4096更有保证,但是在密集计算的时候选用4096,会导致消耗大量CPU,因此只建议在长期使用的密钥上使用4096位(例如gpg私钥)。

TODO: RSA-OAEP

还有就是RSA受量子计算机的威胁,量子计算机算法中最具备代表性的shor算法就是用来解决大质数分解问题的。

 

ECC系列算法

ECC是非对称密码体系中的一个大类(其实总共就两个大类,一个RSA一个ECC),基本原理比较复杂,这里就不展开了,基本涉及的算法有:

ECDH: 密钥交换算法

ECIES: 加密算法,IES加密算法的ECC版本

ECDSA: 签署算法

EdDSA: 签署算法

ECMQV: 密钥交换算法

ECDH

ECDH是基于ECC和DH的Kx算法。

首先确定曲线E(q)和基点G(注意这是一个数,但是使用大写),这两个的选取过程是通过一定的设计得出的,不同的设计得出的被称为不同的曲线,而后,每个人确定自己的私钥k,并且计算p=k*G。

我们还是用Alice和Bob来分析,对Alice来说,pa=kaG,对Bob来说,pb=kbG,最后双方运算p=kapb=kbpa=kakbG,因此双方得到同样的p。

和DHE类似的,ECDH存在一个动态生成k的算法变形ECDHE。

ECDSA

ECDSA(https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm )是基于ECC的签署算法,是一种非确定性算法。具体算法请看wiki,或者进一步找一本ECC密码学的书看。

EdDSA

EdDSA(https://en.wikipedia.org/wiki/EdDSA)也是一个基于ECC的签署算法,和ECDSA最大的区别是,EdDSA是一种确定性算法,不需要借助随机数。

安全实践

ECC系列的密码长度非常短,同时,算法量要比RSA低非常多。一般来说ECC的密钥是攻击量的一倍。例如攻击量是2^80(这是一个常见的值),那么密钥长度最低需要160。NIST的推荐值是用224,合28bytes。具体可以查看这里:https://www.keylength.com/en/compare/

 

最佳实践

密码学里一个很反直觉的东西就是,千万不要因为标准库慢就自己实现,标准库中很多算法都是常数时间算法,具体可以看看时间攻击和侧信道攻击这两种脑洞大开的东西,包括安全界赫赫有名的Meltdown,也是一种侧信道攻击。请在理解原理的基础上,务必使用强大可靠的开源库(注意开源是一个必要条件)。

 

random

随机数关系到整个系统的安全,请不要随意处理,尤其是不要拿time作为seed设定一下random然后就施施然用了。很多时候random被调用的时刻是固定的,可以被回朔到1-2秒的范围内,time的精度在10^-3到10^-6这个量级上。综合起来可以知道,对随机数进行穷举攻击的开销最高只有2E6而已,这个量级甚至不能作为有效的阻碍。

要获得随机数,比较合理的方法是使用/dev/random和/dev/urandom,以及getrandom调用。/dev/random和urandom的区别在于,random会返回随机数,而urandom返回伪随机数(准确的说,在新版内核上,生成函数是chacha20),因此random会因为耗尽而阻塞,urandom不会。不知为何,这份指南(https://www.cnblogs.com/windydays/p/2015_modern_crypto_practice.html)推荐大家避开random。

无论如何,如果你觉得随机性不够,还可以加入random.org的数据来增强随机性。


【It works,why?】后期预告:

《openssl基本密码学操作》

《openssl证书相关》

作者介绍:Shell,一个普通程序员。有的时候写写程序,有的时候潜潜水,大部分时候,他都在发呆。


更多【技术分享】内容
请至ESRC平台“博客”

https://security.ele.me/blog-list.html

 

审核人:yiwang   编辑:少爷

分享到: QQ空间 新浪微博 微信 QQ facebook twitter
|推荐阅读
|发表评论
|评论列表
加载更多