存档

文章标签 ‘密码学’

ECC(Elliptic Curves Cryptography) 椭圆曲线加密原理

2018/09/07 116

ECC(Elliptic Curves Cryptography) 属于非对称加密算法的一个重要组成部分。
本文尽量简单地阐述椭圆曲线加密的原理,但需要读者有一些初级的数论与离散数学相关的知识,或者推荐简单地阅读《算法导论》第31章:数论算法。

椭圆曲线

首先需要明确的是,我们讨论的是什么样的曲线。
椭圆曲线有比较复杂的定义: https://en.wikipedia.org/wiki/Elliptic_curve .而我们讨论的椭圆曲线比这个简单,它是以下方程所描述的一条平滑曲线 :

$$y^2 = x^3 + ax + b, 4a^3 + 27b^2 \neq 0$$

它描述的并不是一个椭圆,之所以称它为”椭圆曲线方程”, 是因为它源自于求椭圆弧长的椭圆积分的反函数。椭圆曲线是无奇点的,即没有尖点,且不会自相交。当 $a,b$ 的值不同时,椭圆曲线会表现出不同的形态:

而当 $4a^3 + 27b^2 = 0$ 时, 它不是椭圆曲线:

从图中可以看到,椭圆曲线总是 沿 x 轴对称 的。这是因为 $y^2$ 的存在。特殊地,我们规定 无穷远点 也存在于椭圆曲线上。我们用 $0$ 或符号 $O$ 来表示无穷远点,则椭圆曲线在实数域上的定义如下:
$$\{ (x,y) \in \mathbb{R}^2 | y^2 = x^3 + ax + b, 4a^3 + 27b^2 \neq 0 \} \cup \{0\}$$

阅读全文…

国密之 sm4 分组密码算法

2018/08/23 211

SM4分组密码算法,原名SMS4,国家密码管理局于2012年3月21日发布,相关标准为“GM/T 0002-2012《SM4分组密码算法》(原SMS4分组密码算法)”。它是一种分组对称加密算法,分组长度和密钥长度均为 128bit ,加密算法与密码扩展算法均采用 32 轮非线性迭代结构, Sbox 为固定的 8bit 输入 8bit 输出的置换。 数据加/解密的算法结构相同,只是轮密钥的使用顺序相反,解密轮密钥是加密轮密钥的逆序。

SBox

在密码学中,Sbox(Substitution-box,替换盒)是对称密钥加密算法执行替换计算的基本结构。SBox接受一个特定位数的输入,通过查表将其转换为特定位数的输出。SM4 给定的 SBox 如下:

0 1 2 3 4 5 6 7 8 9 A B C D E F
0 D6 90 E9 FE CC E1 3D B7 16 B6 14 C2 28 FB 2C 05
1 2B 67 9A 76 2A BE 04 C3 AA 44 13 26 49 86 06 99
2 9C 42 50 F4 91 EF 98 7A 33 54 0B 43 ED CF AC 62
3 E4 B3 1C A9 C9 08 E8 95 80 DF 94 FA 75 8F 3F A6
4 47 07 A7 FC F3 73 17 BA 83 59 3C 19 E6 85 4F A8
5 68 6B 81 B2 71 64 DA 8B F8 EB 0F 4B 70 56 9D 35
6 1E 24 0E 5E 63 58 D1 A2 25 22 7C 3B 01 21 78 87
7 D4 00 46 57 9F D3 27 52 4C 36 02 E7 A0 C4 C8 9E
8 EA BF 8A D2 40 C7 38 B5 A3 F7 F2 CE F9 61 15 A1
9 E0 AE 5D A4 9B 34 1A 55 AD 93 32 30 F5 8C B1 E3
A 1D F6 E2 2E 82 66 CA 60 C0 29 23 AB 0D 53 4E 6F
B D5 DB 37 45 DE FD 8E 2F 03 FF 6A 72 6D 6C 5B 51
C 8D 1B AF 92 BB DD BC 7F 11 D9 5C 41 1F 10 5A D8
D 0A C1 31 88 A5 CD 7B BD 2D 74 D0 12 B8 E5 B4 B0
E 89 69 97 4A 0C 96 77 7E 65 B9 F1 09 C5 6E C6 84
F 18 F0 7D EC 3A DC 4D 20 79 EE 5F 3E D7 CB 39 48

例如,对于输入 EF, 通过查表输出为 第 E 行,第 F 列,84

阅读全文…

服务端用户密码的管理

2017/12/12 676

最近做了一些与密码学相关的工作,对于消息的加解密有了一些新的看法。结合之前项目中遇到的服务端密码存储的问题,在这里写一点自己的想法。

目前常见的一些密码存储方式

以下是一些常见的密码存储方式,其中一部分是自己用过的,一部分是见过别人使用的:

  1. 明文 pwd
  2. 经过MD5 哈希后存储 md5(pwd)
  3. 两次MD5后存储 md5(md5(pwd))
  4. 加盐md5存储 md5(pwd + salt)
  5. 密码扩展后存储 kdf(pwd)
  6. 慢哈希后存储 brypt(pwd)
  7. 以上多种算法组合后存储

哈希

很明显,第 1 种是最不安全的。存储在数据库中的密码可以轻易地被管理员看到。一旦服务器被拖库,这些密码就轻易地被别人窃取,并可以根据账号和密码在其它网站上试探(大部分用户在多个网站上使用相同的用户名和密码)。尽管人人都知道这种存储方式是极不安全的,但仍然有很多网站使用它。如前几年震惊中外的 CSDN 拖库事件 。在这一事件中,有600万用户的信息被泄漏。
第 2 种 方式比较古老,管理员和黑客无法看到用户的明文密码。但如我们所知,MD5 是不安全的。如 MD5 碰撞算法。而在此之前,查表法一直做为破解 MD5 密码的重要手段 。 所谓 查表法 ,就是对字典(密码集) 进行 MD5 运算,将哈希值预存储在一个或多个表里。

当需要破解某密码时,根据服务器存储的哈希值在预计算的哈希值表中查找对应的值。而 反向查表法 ,攻击者可以同时对多个重合密码进行攻击。

如果用户使用了弱密码,这种使用反向查表法来破解密码简直不要太轻松。
使用查表法需要存储字典与哈希值,对存储空间有较高的要求。后来进化出了 彩虹表 法,在算法的空间和时间上进行了优化。

加盐

第 3、4 种方式针对上述攻击方法做了改进。其实第 3 种方式并大的改进, 因为算法和参数是固定的。而第 4 种的改进比较好。所谓 加盐(salt) ,即在消息的任意固定位置添加附加消息。它使攻击者的字典变得更加复杂,攻击者计算预存储值的难度大大增加了;每个密码都混入了不同的盐,所以使得反向查表法去批量匹配密码变得难以施行。在加盐存储的实践中,有部分人使用了错误的实现:如盐值过短,或盐值重复。
盐值过短 无法对攻击者造成足够的困扰,一个好的盐值的长度起码要和哈希值的长度一至。而 盐值重复 则和未加盐没有区别:两个相同的密码加相同的盐,得到的哈希值是一样的。特别是对于那些将盐值硬编码到代码里的,简直是在为攻击者提供帮助。类似地,也不要使用用户名、用户id、创建时间等字段做为盐值–盐值应该是随机的,且并用户修改密码时应该给出新的盐值。
阅读全文…

计算信息的指纹–哈希函数

2017/09/20 1,027

1 XCodeGhost 风波

2015年9月17日左右,知名程序员唐巧发布微博声称Xcode有可能被第三方代码注入,而在社交平台上引起轩然大波。乌云网后续发布相关的知识库文章。而在此之前,腾讯安全应急响应中心在跟踪某app的bug时发现异常流量,解析后上报了国家互联网应急中心(CNCERT),后者随即在9月14日发布了预警消息。之后也有国外信息安全组织跟进调查。 受影响的应用程序包括微信、网易云音乐、滴滴打车、高德地图、12306、同花顺、中信银行动卡空间、简书等76种。而事情的起因,是有人将被添加了恶意代码的 XCode 放在百度云盘上,供开发者下载,在使用感染后的XCode发布的App都带有后门,会在最终客户端运行时将隐私信息提交给第三方。 这一事件被称为 “XCodeGhost 事件”。

事件的背后折射出的,是计算机网络信息中的安全问题。 互联网中的大部分用户,都缺乏基本的安全意识,其中就包括计算机重度使用者:程序员。 如何确保我们下载使用的软件是没有经过污染的软件呢?首先确保我们从正规的渠道获取软件,其次,我们需要对软件进行校验。比较常用的方法,是使用哈希函数进行校验。 如 Eclipse.org 为我们提供了 SHA-512 校验码

2 什么是哈希函数

哈希函数,也叫单向散列函数 (one-way hash function) ,有一个输入和一个输出,输入称为 消息 ,输出称为 散列值 ,函数根据消息计算出散列值,可以用来检验消息的完整性。它也称作 消息摘要函数 (Message Digest Function)  ,或者 杂凑函数 。消息也被称作 原像 ,散列值也被称作 哈希值 或 指纹 。哈希函数具有以下的特性:

  1. 散列值长度与消息长度无关
  2. 散列值与消息内容密切相关,即消息不同,散列值也不同
  3. 单向性 在给出散列值 H(M) 的情况下,无法计算出消息 M 的值。
  4. 抗碰撞性 如果有消息 M1,散列值 H(M1), H(M2) ,且 H(M1) = H(M2) ,很难找出消息 M2 令 M2 ≠ M1

3 常见的几种哈希函数

3.1 MD5

MD5 能够产生 128 bit 的散列值(RFC1321)。 MD5 的强抗碰撞性已经于 2005 年被攻破,也就是说,现在已经能够产生具备相同散列值的两条不同的消息,因此它是不安全的。
阅读全文…

对称密码的模式(MODE)

2017/07/16 1,000

1 科谱:密码学中的常见概念

1.1 密钥

根据密钥的使用方法,可以将密钥分为两种:

  • 对称密钥 是指在加密和解密时使用同一密钥的方式
  • 公钥 加密和解密使用的不是同一种密钥,也称 非对称密钥

1.2 单向散列

单向散列是由单向散列函数计算出来的一组数值。它不能保证数据的机密性,是用来保证数据的完整性的。例如,有安全意识的软件发布者会向用户公布软件的散列值,一般是 MD5. 可以通过检验软件的 MD5 散列值,判断软件是否被篡改过。

1.3 随机数

随机数可以通过硬件生成,也可以通过软件来生成。通过硬件生成的随机数列,是根据传感器收集的热量、声音的变化等事实上无法预测和重现的自然现象信息来生成的,可以称为 真随机数 . 而一般由软件生成的随机数是可以周期性重现的,这种随机数称为 伪随机数 。生成随机数的软件叫做 伪随机数生成器

2 对称加密

常用的对称加密方法有 DES 与 AES 两种。

2.1 DES

DES 是一种将 64bit 的明文加密成 64bit 密文的对称密钥算法,它是密钥长度也是 64bit,但是它的密钥每隔 7bit 会设置一个用于错误检查的 bit, 所以实质上其密钥长度是 56bit . 因为 DES 每次只能加密 64bit 明文,所以需要对超过 64bit 的明文进行分组。以分组为单位进行处理的密码算法也称为 分组密码 。分组后的明文以什么样的方式进行加密,我们称之为 模式(mode) 。 DES 的基本结构以其设计者的名字(Horst Feistel)命名,也称 Feistel 网络可 Feistel结构。在 Feistel 结构中,将 64bit 明文再分作两部分,每部分 32bit。假如标记为 A B 两部分,那么有如下步骤:

  1. 对 B 使用子密钥 subkey 进行加密运算,生成 Bf(B,subkey) = B'
  2. B~ 与 A 进行异或运算,生成 C : B' XOR A = C
  3. C 与 B 组合,生成密文 D : C # B = D

这三个步骤称为一个 轮(round) .可以看到,密文D的后半部分 B 没有被加密。我们将组成 D 的 C 与 B 部分进行互置,即令 A = B, B = C,再重复上面的步骤 1 ~ 3 ,这样明文的每一个部分都被加密了。 DES 就是一种由 16 个轮循环组成的 Feistel 网络。每一轮都会生成一个不同的密钥,所以称为子密钥。

阅读全文…