离散对数算法

A. 什么是ECC

ECC
ECC是“Error Checking and Correcting”的简写，中文名称是“错误检查和纠正”。ECC是一种能够实现“错误检查和纠正”的技术，ECC内存就是应用了这种技术的内存，一般多应用在服务器及图形工作站上，这将使整个电脑系统在工作时更趋于安全稳定。

要了解ECC技术，就不能不提到Parity（奇偶校验）。在ECC技术出现之前，内存中应用最多的是另外一种技术，就是Parity（奇偶校验）。我们知道，在数字电路中，最小的数据单位就是叫“比特（bit）”，也叫数据“位”，“比特”也是内存中的最小单位，它是通过“1”和“0”来表示数据高、低电平信号的。在数字电路中8个连续的比特是一个字节（byte），在内存中不带“奇偶校验”的内存中的每个字节只有8位，若它的某一位存储出了错误，就会使其中存储的相应数据发生改变而导致应用程序发生错误。而带有“奇偶校验”的内存在每一字节（8位）外又额外增加了一位用来进行错误检测。比如一个字节中存储了某一数值（1、0、1、0、1、0、1、1），把这每一位相加起来（1＋0＋1＋0＋1＋0＋1＋1=5）。若其结果是奇数，对于偶校验，校验位就定义为1，反之则为0；对于奇校验，则相反。当CPU返回读取存储的数据时，它会再次相加前8位中存储的数据，计算结果是否与校验位相一致。当CPU发现二者不同时就作出视图纠正这些错误，但Parity有个缺点，当内存查到某个数据位有错误时，却并不一定能确定在哪一个位，也就不一定能修正错误，所以带有奇偶校验的内存的主要功能仅仅是“发现错误”，并能纠正部分简单的错误。

通过上面的分析我们知道Parity内存是通过在原来数据位的基础上增加一个数据位来检查当前8位数据的正确性，但随着数据位的增加Parity用来检验的数据位也成倍增加，就是说当数据位为16位时它需要增加2位用于检查，当数据位为32位时则需增加4位，依此类推。特别是当数据量非常大时，数据出错的几率也就越大，对于只能纠正简单错误的奇偶检验的方法就显得力不从心了，正是基于这样一种情况，一种新的内存技术应允而生了，这就是ECC（错误检查和纠正），这种技术也是在原来的数据位上外加校验位来实现的。不同的是两者增加的方法不一样，这也就导致了两者的主要功能不太一样。它与Parity不同的是如果数据位是8位，则需要增加5位来进行ECC错误检查和纠正，数据位每增加一倍，ECC只增加一位检验位，也就是说当数据位为16位时ECC位为6位，32位时ECC位为7位，数据位为64位时ECC位为8位，依此类推，数据位每增加一倍，ECC位只增加一位。总之，在内存中ECC能够容许错误，并可以将错误更正，使系统得以持续正常的操作，不致因错误而中断，且ECC具有自动更正的能力，可以将Parity无法检查出来的错误位查出并将错误修正。

2 ECC(Elliptic Curve Cryptosystems )椭圆曲线密码体制

2002年，美国SUN公司将其开发的椭圆加密技术赠送给开放源代码工程
公钥密码体制根据其所依据的难题一般分为三类：大整数分解问题类、离散对数问题类、椭圆曲线类。有时也把椭圆曲线类归为离散对数类。
椭圆曲线密码体制来源于对椭圆曲线的研究，所谓椭圆曲线指的是由韦尔斯特拉斯（Weierstrass）方程：
y2+a1xy+a3y=x3+a2x2+a4x+a6 (1)
所确定的平面曲线。其中系数ai(I=1,2,…,6)定义在某个域上，可以是有理数域、实数域、复数域，还可以是有限域GF（pr），椭圆曲线密码体制中用到的椭圆曲线都是定义在有限域上的。
椭圆曲线上所有的点外加一个叫做无穷远点的特殊点构成的集合连同一个定义的加法运算构成一个Abel群。在等式
mP=P+P+…+P=Q (2)
中，已知m和点P求点Q比较容易，反之已知点Q和点P求m却是相当困难的，这个问题称为椭圆曲线上点群的离散对数问题。椭圆曲线密码体制正是利用这个困难问题设计而来。椭圆曲线应用到密码学上最早是由Neal Koblitz 和Victor Miller在1985年分别独立提出的。
椭圆曲线密码体制是目前已知的公钥体制中，对每比特所提供加密强度最高的一种体制。解椭圆曲线上的离散对数问题的最好算法是Pollard rho方法，其时间复杂度为，是完全指数阶的。其中n为等式(2)中m的二进制表示的位数。当n=234, 约为2117，需要1.6x1023 MIPS 年的时间。而我们熟知的RSA所利用的是大整数分解的困难问题，目前对于一般情况下的因数分解的最好算法的时间复杂度是子指数阶的，当n=2048时，需要2x1020MIPS年的时间。也就是说当RSA的密钥使用2048位时，ECC的密钥使用234位所获得的安全强度还高出许多。它们之间的密钥长度却相差达9倍，当ECC的密钥更大时它们之间差距将更大。更ECC密钥短的优点是非常明显的，随加密强度的提高，密钥长度变化不大。
德国、日本、法国、美国、加拿大等国的很多密码学研究小组及一些公司实现了椭圆曲线密码体制，我国也有一些密码学者做了这方面的工作。许多标准化组织已经或正在制定关于椭圆曲线的标准，同时也有许多的厂商已经或正在开发基于椭圆曲线的产品。对于椭圆曲线密码的研究也是方兴未艾，从ASIACRYPTO’98上专门开辟了ECC的栏目可见一斑。
在椭圆曲线密码体制的标准化方面，IEEE、ANSI、ISO、IETF、ATM等都作了大量的工作，它们所开发的椭圆曲线标准的文档有：IEEE P1363 P1363a、ANSI X9.62 X9.63、 ISO/IEC14888等。
2003年5月12日中国颁布的无线局域网国家标准 GB15629.11 中，包含了全新的WAPI(WLAN Authentication and Privacy Infrastructure)安全机制，能为用户的WLAN系统提供全面的安全保护。这种安全机制由 WAI和WPI两部分组成，分别实现对用户身份的鉴别和对传输的数据加密。WAI采用公开密钥密码体制，利用证书来对WLAN系统中的用户和AP进行认证。证书里面包含有证书颁发者(ASU)的公钥和签名以及证书持有者的公钥和签名，这里的签名采用的就是椭圆曲线ECC算法。
加拿大Certicom公司是国际上最着名的ECC密码技术公司,已授权300多家企业使用ECC密码技术，包括Cisco 系统有限公司、摩托罗拉、Palm等企业。Microsoft将Certicom公司的VPN嵌入微软视窗移动2003系统中。

B. RSA加密原理

RSA加密是一种非对称加密。可以在不直接传递密钥的情况下，完成解密。这能够确保信息的安全性，避免了直接传递密钥所造成的被破解的风险。是由一对密钥来进行加解密的过程，分别称为公钥和私钥。公钥加密--私钥解密，私钥加密--公钥解密

在 整数 中， 离散对数 是一种基于 同余 运算和 原根 的一种 对数 运算。而在实数中对数的定义 log _b a 是指对于给定的 a 和 b ，有一个数 x ，使得 b ^x = a 。相同地在任何群 G 中可为所有整数 k 定义一个幂数为 b ^K ，而 离散对数 log _b a 是指使得 b ^K = a 的整数 k 。

当3为17的 原根 时，我们会发现一个规律

对 正整数 n，欧拉函数是小于或等于n的正整数中与n 互质 的数的数目（因此φ(1)=1）。有以下几个特点

服务端根据生成一个随机数15，根据 3 ¹⁵ _mod 17 计算出6，服务端将6传递给客户端，客户端生成一个随机数13，根据 3 ¹³ _mod 17 计算出12后，将12再传回给服务端，客户端收到服务端传递的6后，根据 6 ¹³ _mod 17 计算出 10 ，服务端收到客户端传递的12后，根据 12 ¹⁵ _mod 17 计算出 10 ，我们会发现我们通过 迪菲赫尔曼密钥交换 将 10 进行了加密传递

说明：

安全性：
除了 公钥 用到 n 和 e ，其余的4个数字是 不公开 的（p1、p2、φ(n)、d）
目前破解RSA得到的方式如下：

缺点
RSA加密 效率不高 ，因为是纯粹的数学算法，大数据不适合RSA加密，所以我们在加密大数据的时候，我们先用 对称加密 算法加密大数据得到 KEY ，然后再用 RSA 加密 KEY ，再把大数据和KEY一起进行传递

因为Mac系统内置了OpenSSL（开源加密库），所以我们开源直接在终端进行RSA加密解密

生成RSA私钥，密钥名为private.pem,密钥长度为1024bit

因为在iOS中是无法使用 .pem 文件进行加密和解密的，需要进行下面几个步骤

生成一个10年期限的crt证书

crt证书格式转换成der证书

C. 非对称加密算法包括哪些

以下是几种常见的非对称加密算法：

1、RSA算法：RSA算法是最早被广泛使用的非对称加密算法之一，它利用质数分解的困难性，通过生成公钥和私钥来实现加密和解密。

4、ElGamal算法：ElGamal算法是一种基于离散对兆竖数问题的加密算法，它被广泛应用于数字签名和加密通信等领域。

这些算法都是非对称加密算法的代表性算法，它们在不同的场景下谈族有着各自的优缺点，应根据实际需求选择合适的族侍大算法来进行数据加密和解密。

D. 公钥密码→RSA详解

在对称密码中，由于加密和解密的密钥是相同的，因此必须向接收者配送密钥。用于解密的密钥必须被配送给接收者，这一问题称为 密钥配送问题 ，如果使用公钥密码，则无需向接收者配送用于解密的密钥，这样就解决了密钥配送问题。可以说公钥密码是密码学历史上最伟大的发明。

解决密钥配送问题的方法

在人数很多的情况下，通信所需要的密钥数量会增大，例如：1000名员工中每一个人都可以和另外999个进行通信，则每个人需要999个通信密钥，整个密钥数量：
1000 x 999 ÷ 2 = 499500
很不现实，因此此方法有一定的局限性

在Diffic-Hellman密钥交换中，进行加密通信的双方需要交换一些信息，而这些信息即便被窃听者窃听到也没有问题（后续文章会进行详解）。

在对称密码中，加密密钥和解密密钥是相同的，但公钥密码中，加密密钥和解密密钥却是不同的。只要拥有加密密钥，任何人都可以加密，但没有解密密钥是无法解密的。

公钥密码中，密钥分为加密密钥（公钥）和解密密钥（私钥）两种。

公钥和私钥是一一对应的，一对公钥和私钥统称为密钥对，由公钥进行加密的密文，必须使用与该公钥配对的私钥才能够解密。密钥对中的两个密钥之间具有非常密切的关系——数学上的关系——因此公钥和私钥是不能分别单独生成的。

发送者：Alice      接收者：Bob      窃听者：Eve
通信过程是由接收者Bob来启动的

公钥密码解决了密钥配送的问题，但依然面临着下面的问题

RSA是目前使用最广泛的公钥密码算法，名字是由它的三位开发者，即Ron Rivest、Adi Shamir和Leonard Adleman的姓氏的首字母组成的（Rivest-Shamir-Adleman）。RSA可以被使用公钥密码和数字签名（此文只针对公钥密码进行探讨，数字签名后续文章敬请期待）1983年在美国取得了专利，但现在该专利已经过期。

在RSA中，明文、密钥和密文都是数字，RSA加密过程可以用下列公式来表达

密文 = 明文 ^E mod N

简单的来说，RSA的密文是对代表明文的数字的 E 次方求mod N 的结果，换句话说：将明文和自己做 E 次乘法，然后将结果除以 N 求余数，这个余数就是密文。

RSA解密过程可以用下列公式来表达

明文 = 密文 ^D mod N
对表示密文的数字的 D 次方求mod N 就可以得到明文，换句话说：将密文和自己做 D 次乘法，在对其结果除以 N 求余数，就可以得到明文
此时使用的数字 N 和加密时使用的数字 N 是相同的，数 D 和数 N 组合起来就是RSA的解密密钥，因此 D 和 N 的组合就是私钥 。只要知道 D 和 N 两个数的人才能够完成解密的运算

根据加密和解密的公式可以看出，需要用到三个数—— E 、 D 和 N 求这三个数就是 生成密钥对 ，RSA密钥对的生成步骤如下：

准备两个很大的质数 p 和 q ，将这两个数相乘，结果就是 N
N = p x q

L 是 p-1 和 q-1 的最小公倍数，如果用lcm( X , Y )来表示 “ X 和 Y 的最小公倍数” 则L可以写成下列形式
L = lcm ( p - 1， q - 1)

E 是一个比1大、比 L 小的数。 E 和 L 的最大公约数必须为1，如果用gcd( X , Y )来表示 X 和 Y 的最大公约数，则 E 和 L 之间存在下列关系：
1 < E < L
gcd( E , L ) = 1 （是为了保证一定存在解密时需要使用的数 D ）

1 < D < L
E x D mod L = 1

p = 17
q = 19
N = p x q = 17 x 19 = 323

L = lcm ( p - 1， q - 1) = lcm (16,18) = 144

gcd( E , L ) = 1
满足条件的 E 有很多：5，7，11，13，17，19，23，25，29，31...
这里选择5来作为 E ,到这里我们已经知道 E = 5    N = 323 这就是公钥

E x D mod L = 1
D = 29 可以满足上面的条件，因此：
公钥： E = 5     N = 323
私钥： D = 29    N = 323

要加密的明文必须是小于 N 的数，这是因为在加密运算中需要求 mod N 假设加密的明文是123
明文 ^E mod N = 123 ⁵ mod 323 = 225（密文）

对密文225进行解密
密文 ^D mod N = 225 ²⁹ mod 323 = 225 ¹⁰ x 225 ¹⁰ x 225 ⁹ mod 323 = (225 ¹⁰ mod 323) x (225 ¹⁰ mod 323) x (225 ⁹ mod 323) = 16 x 16 x 191 mod 323 = 48896 mod 323 = 123（明文）

如果没有mod N 的话，即：

明文 = 密文 ^D mod N

通过密文求明文的难度不大，因为这可以看作是一个求对数的问题。
但是，加上mod N 之后，求明文就变成了求离散对数的问题，这是非常困难的，因为人类还没有发现求离散对数的高效算法。

只要知道 D ，就能够对密文进行解密，逐一尝试 D 来暴力破译RSA，暴力破解的难度会随着D的长度增加而加大，当 D 足够长时，就不能再现实的时间内通过暴力破解找出数 D

目前，RSA中所使用的 p 和 q 的长度都是1024比特以上， N 的长度为2048比特以上，由于 E 和 D 的长度可以和N差不多，因此要找出 D ，就需要进行2048比特以上的暴力破解。这样的长度下暴力破解找出 D 是极其困难的

E x D mod L = 1           L = lcm ( p - 1， q - 1)
由 E 计算 D 需要使用 p 和 q ，但是密码破译者并不知道 p 和 q

对于RSA来说，有一点非常重要，那就是 质数 p 和 q 不能被密码破译这知道 。把 p 和 q 交给密码破译者与把私钥交给密码破译者是等价的。

p 和 q 不能被密码破译者知道，但是 N = p x q 而且 N 是公开的， p 和 q 都是质数，因此由 N 求 p 和 q 只能通过 将 N 进行质因数分解 ，所以说：
一旦发现了对大整数进行质因数分解的高效算法，RSA就能够被破译

这种方法虽然不能破译RSA，但却是一种针对机密性的有效攻击。

所谓中间人攻击，就是主动攻击者Mallory混入发送者和接收者的中间，对发送者伪装成接收者，对接收者伪装成发送者的攻击，在这里，Mallory就是“中间人”

这种攻击不仅针对RSA，而是可以针对任何公钥密码。在这个过程中，公钥密码并没有被破译，所有的密码算法也都正常工作并确保了机密性。然而，所谓的机密性并非在Alice和Bob之间，而是在Alice和Mallory之间，以及Mallory和Bob之间成立的。 仅靠公钥密码本身，是无法防御中间人攻击的。

要防御中间人攻击，还需要一种手段来确认所收到的公钥是否真的属于Bob，这种手段称为认证。在这种情况下，我们可以使用公钥的 证书 (后面会陆续更新文章来进行探讨)

网络上很多服务器在收到格式不正确的数据时都会向通信对象返回错误消息，并提示“这里的数据有问题”，然而，这种看似很贴心的设计却会让攻击者有机可乘。 攻击者可以向服务器反复发送自己生成的伪造密文，然后分析返回的错误消息和响应时间获得一些关于密钥和明文的信息。

为了抵御这种攻击，可以对密文进行“认证”，RSA-OAEP(最优非对称加密填充)正是基于这种思路设计的一种RSA改良算法。

RSA-OAEP在加密时会在明文前面填充一些认证信息，包括明文的散列值以及一定数量的0，然后用RSA进行加密，在解密的过程中，如果解密后的数据的开头没有找到正确的认证信息，则可以判定有问题，并返回固定的错误消息（重点是，不能将具体的错误内容告知开发者）
RSA-OAEP在实际应用中，还会通过随机数使得每次生成的密文呈现不同的排列方式，从而进一步提高安全性。

随着计算机技术的进步等，以前被认为是安全的密码会被破译，这一现象称为 密码劣化 ，针对这一点：