密码学

密码学
首页
文章

漏洞
SRC导航
内容精选

输入关键词搜索

APP 登录| 注册
密码学基本原理（下）
阅读量 20672 | 评论 1

分享到： QQ空间 新浪微博 微信 QQ facebook twitter
发布时间：2018-06-28 13:04:27

连载系列——It works,why?

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

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

Public-key signature
公钥签署为三个函数：生成G，签署为S，校验为V。对任意数据d和密钥p：

G可以生成私钥和公钥。即s,p=G()，其中s为私钥，p为公钥。公钥可以公开；
对于签署获得的v=S(d, s)，可以用V(d, v, p)来检验d和v是否成对；
攻击者在得知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上的例子：

Alice和Bob约定p=23，g=5；
Alice选取a=4，计算pa=5^4mod23=4。Alice将4发送给Bob；
Bob选取b=3，计算pb=5^3mod23=10。Bob将10发送给Alice；
Alice计算k=10^4mod23=18；
Bob计算k=4^3mod23=18。
算法可以确保以下几点：

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

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

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

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

生成算法G
加密算法E
解密算法D
签署算法S
验证算法V
密钥交换算法
特别需要注意一点，RSA的加密算法并没有使用IES体制，RSA算法族里自带了加解密和签署。从某种意义上说，RSA其实和上面说的一般性单向陷门函数算法为基础的算法有所区别。

生成算法
首先有素数p和q，称为prime1和prime2；
计算n=p*q，称为modulus；
求n的Euler totient functionφ(n)=(p-1)*(q-1)；
选择一个和φ(n)互素的数e，称为public exponent；
计算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)；
公开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上的例子：

p=61，q=53；
n=61*53=3233；
φ(n)=60*52=3120（原文里，取的是Carmichael函数，λ(n)=3120/gcd(61,53)=780）；
e=17（在实践中，这个值一般都是65537）；
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 编辑：少爷

本文由安全客原创发布
转载，请参考转载声明，注明出处： https://www.anquanke.com/post/id/149620
安全客 - 有思想的安全新媒体
密码学 技术分析 安全开发

饿了么安全应急响应中心 SRC 分享到： QQ空间 新浪微博 微信 QQ facebook twitter
|推荐阅读

2018安恒杯11月赛-Web&Crypto题解
2018-11-26 10:02:02

U2F安全协议分析
2018-11-24 10:00:48

二十年重回首——CIH病毒源码分析
2018-11-23 15:20:19

Cookie Maker：隐藏在Google Docs中的恶意网络
2018-11-23 14:30:40
|发表评论

发表你的评论吧
昵称
管理员
换一个
|评论列表
Naivete · 2018-08-31 14:06:07 回复
上下篇一起看完了，挺不错的文章，对于只在课上学过一些密码学的学生来说，这个文章真是太好了。。

饿了么安全应急响应中心
这个人太懒了，签名都懒得写一个
文章
10
粉丝
5
TA的文章
openssl基本密码学操作
2018-07-10 11:00:09
密码学基本原理（下）
2018-06-28 13:04:27
密码学基本原理（上）
2018-06-08 16:15:24
饿了么SRC奖励加倍，粽子免费领！
2018-06-07 17:30:09
10万＋！ESRC年终奖励很直接！
2017-12-23 18:15:30

输入关键字搜索内容
相关文章
当中国剩余定理邂逅RSA
Wi-Fi新标准-WPA3蜻蜓(Dragonfly)密钥交换协议分析
小记一类ctf密码题解题思路
悬镜安全招人了，各个岗位看过来
关于如何使用信用卡磁条阅读器读取酒店钥匙卡数据的分析
对 Hawkeye Keylogger - Reborn v8 恶意软件活动的深入分析
JOP代码复用攻击
热门推荐
文章目录
Public-key signature
单向陷门函数与DH密钥交换问题
Integrated Encryption Scheme
MQV
Diffie-Hellman key exchange
RSA系列算法
生成算法
加密解密算法
签署验证算法
密钥协商算法
最佳实践
ECC系列算法
ECDH
ECDSA
EdDSA
安全实践
最佳实践
random
安全客Logo
安全客
安全客
关于我们
加入我们
联系我们
用户协议
商务合作
合作内容
联系方式
友情链接
内容须知
投稿须知
转载须知
合作单位
安全客
安全客
Copyright © 360网络攻防实验室 All Rights Reserved 京ICP备08010314号-66
Loading...0daybank