/Cryptography

Cryptography Book

密码学

###目录

##密码学和数据安全导论 密码编码学分为：密码使用学和密码分析学。

密码使用学指的是一种为了达到隐藏消息含义的目的而使用密文书写的科学。

密码使用学分为：对称密码、非对称密码、协议。

##公钥密码学简介

绝大多数公钥算法都基于数论函数。公钥算法的公共原理是单向函数。

单向函数的定义：
函数 f() 是一个单向函数，仅当：
1. y = f(x) 在计算上是容易的，且
2. x = f-1(y)(-1为上标) 在计算上是不可行的。

实际公钥方案中常使用两种单向函数。第一个是整数分解问题，它是 RSA 的基础。给定两个大素数，计算他们的乘积很容易，但是将他们的乘积分解因式却是相当困难的。另一个是离散对数问题。

###公钥密码学的实用性

公钥算法的主要功能：

  • 密钥建立 在不安全信道上建立密钥的协议有若干种，包括 Diffie-Hellman 密钥交换(DHKE)协议或 RSA 密钥传输协议。

  • 不可否认性 可以通过数字签名算法(比如 RSA、DSA、或 ECDSA)实现不可否认性和消息完整性。

  • 身份标识 利用质询—响应协议与数字签名相结合的方法识别实体。

  • 加密 可以使用类似 RSA 或 Elgamal 的算法对消息进行加密。

但是因为公钥加密非常慢，实际的数据加密都不使用公钥算法。

####重要的公钥算法 具有实用性的公钥算法只有三种，根据他们所依赖的底层计算问题分类如下：

  • 整数分解方案 该方案基于的事实是：对大整数进行因式分解是非常困难的。这类算法的突出代表是 RSA。

  • 离散对数方案 基于有限域内的离散对数问题。最典型的例子有 Diffie-Hellman 密钥交换、Elgamal加密、数字签名算法(DSA)。

  • 椭圆曲线方案 该方案是离散对数算法的一个推广。

####密钥长度与安全等级 如果已知最好的攻击需要 2n(n为上标，即2的n次方) 步才能破解某个算法，则这个算法称为拥有n位安全等级。安全等级为 n 的对称算法的密钥长度也是 n 位。但是非对称算法的安全等级和密钥长度之间的关系就没这么直观了。

###公钥算法的基本数论知识

  • 欧几里得算法

在求解大数的最大公约数(gcd)问题中，基于这样一个事实：r0 和 r1 的最大公约数等于 (r0 - r1) 和 r1 的最大公约数。(假设r0 > r1，且均为正整数)。使用公式表示为：

gcd(r0, r1) = gcd(r0 - r1, r1)   (r0 > r1 >0，且为整数)
  • 欧拉函数
  • 费马小定理与欧拉定理

##RSA密钥体制

RSA 实际中常用于：

  • 数据小片段的加密，尤其用于密钥传输
  • 数字签名，比如互联网上的数字证书

RSA 的主要用途就是安全地交换对称算法的密钥(密钥传输)。实际上，RSA 通常与类似 AES 的对称算法一起使用，其中真正用来加密大量数据的是对称算法。

RSA 的底层单向函数就是整数因式分解问题。

###加密与解密

###密钥生成与正确性验证 所有非对称算法的一个显著特征就是，它们都有一个计算公钥和私钥的握手阶段。

RSA 的核心是加密时，消息 x 首先要升高到 e 次幂，解密时密文 y 也要升高到 d 次幂，这样得到的结果也与消息 x 相等。

###加密与解密：快速计算指数

###RSA的加速技术

  • 使用短公开指数的快速加密
  • 使用**余数定理的快速加密

###寻找大素数

###实际中的 RSA：填充(padding)

###攻击 针对 RSA 的攻击主要有三种常见的类型：

  1. 协议攻击
  2. 数学分析攻击
  3. 旁道攻击

###软件实现与硬件实现

##基于离散对数问题的公钥密码体制

###一些代数知识

群指的是一个元素集合 G 以及联合 G 内两个元素的操作o 的集合。群具有以下属性：

  1. 群操作o 是封闭的
  2. 群操作是可结合的
  3. 存在单位元
  4. 一个元素存在逆元

有限群：一个群(G, o) 是有限的，仅当它拥有有限个元素。群 G 的基或阶可以表示为 |G|

##椭圆曲线密码体制

椭圆曲线密码学(ECC)使用较短的操作数，可提供与 RSA 或离散对数系统同等的安全等级(所需要的操作数的长度之比大概为 160256 位比 10243072位)。ECC在性能(更少的计算量)和带宽(更短的签名和密钥)上都比 RSA 和离散对数方案更具有优势。

###椭圆曲线的计算方式

####椭圆曲线上的群操作

已知 P = (x1, y1) 和 Q = (x2, y2) 是椭圆曲线上的两个点，现在需要计算第三个点 R 的坐标

  1. 相异点相加 P + Q： 主要是针对 R = P + Q 且 P != Q 的情形。具体做法：过 P 和 Q 画一条直线，与椭圆曲线相较与第三点，过这个第三点作关于 x 轴的映射，得到的点就是 R 点。
  2. 相同点相加 P + P： 具体做法：过 P 点做椭圆曲线的切线，与椭圆曲线交于第二点，过该点做关于 x 轴的映射，得到的就是 R 点。