RSA 算法

上一篇文章简单介绍了下加密算法,接下来具体介绍下项目中采用的非对称加密算法– RSA 算法。

RSA 算法是三位数学家 Rivest、Shamir 和 Adleman 设计了一种算法,算法由他们三个的名字命名。该算法的安全性取决于密钥的长度,密钥越长越难破解。根据已有报道,1024 位的 RSA 密钥已有人宣布破解(项目中用的就是 1024 位的密钥  ̄□ ̄)。

在开始介绍下 RSA 算法原理前,先回顾下一些数论知识。

数论知识

互质

两个或两个以上整数除 1 外,没有其他共同的公约数,那么这些数为互质关系。

欧拉函数

欧拉函数 φ(n) 是在小于或等于正整数 n 的正整数中找到和 n 构成互质关系的整数数量。

  • n = 1 时,φ(n) = 1
  • n 为质数时,φ(n) = n -1;因为质数与小于它的每一个书都为互质关系
  • n 为质数的某个一次方,即 n = p^k (p 为质数,k 为大于等于 1 的整数), φ(n) = p^k - p^(k-1)
  • n 为两个互质的整数a、b之积,φ(n) = φ(ab) = φ(a)φ(b) = (a-1)(b-1)
  • n 为大于 1 的正整数(可以写成一系列质数的积),φ(n) 的通用公式为:

​ 举个例子 1323 的欧拉函数计算过程如下:

欧拉定理

如果正整数 m 和 n 互质,那么 n 的欧拉函数可以让等式 a^φ(n) ≡ 1 (mod φ(n))成立。

也就是,a 的 φ(n) 次方减 1,可以被 n 整除。如 3 和 7 互质,且欧拉函数 φ(7) = 6

那么 3^6 - 1 = 729 -1 = 728 可以被 7 整除。

模反元素

如果正整数 m 和 n 互质,那么一定可以找到整数 b,使得 mb - 1 可以被 n 整除。换句话说,m、n、b 三者满足等式 mb ≡ 1 (mod φ(n))

生成密钥步骤

  • 随机选两个不相等的质数 p、q,且 n = p * q

  • 计算 φ(n)

  • 随机选一整数 e,e 满足 1 < e < φ(n),且 e 与 φ(n) 构成互质关系

  • 通过 e 计算 φ(n) 的模反元素 d(ed ≡ 1 (mod φ(n))

    ed ≡ 1 (mod φ(n)) <==> ed - 1 ≡ kφ(n) <==> ed - kφ(n) ≡ 1

  • 通过扩展欧几里得算法计算出 d 和 k 的值

  • 将(n, e)封装为公钥,(n, d)封装为私钥

加密

使用公钥(n, e)对信息 m 进行加密,m 为整数(字符串取其 ascii 值或 unicode 值)且 m < n。

m^e ≡ c (mod n)

其中 c 就是加密后的信息。

解密

通过私钥(n,d)对加密数据 c 就行解密。

c^d ≡ m (mod n)

也就是说,c 的 d 次方除以 n 的余数为 m。即能得到加密原文 m。

私钥和公钥

公私钥语法

  • RSA 公钥在 pkcs#1 中的语法

    1
    2
    3
    4
    RSAPublicKey ::= SEQUENCE {
    modulus INTEGER, -- n
    publicExponent INTEGER -- e
    }
  • RSA 私钥在 pkcs#1 中的语法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    RSAPrivateKey ::= SEQUENCE {
    version Version,
    modulus INTEGER, -- n
    publicExponent INTEGER, -- e
    privateExponent INTEGER, -- d
    prime1 INTEGER, -- p
    prime2 INTEGER, -- q
    exponent1 INTEGER, -- d mod (p-1)
    exponent2 INTEGER, -- d mod (q-1)
    coefficient INTEGER, -- (inverse of q) mod p
    otherPrimeInfos OtherPrimeInfos OPTIONAL
    }
  • RSA 私钥在 pkcs#8 中的语法

    pkcs#8 全称为 Private-Key Information Syntax Standard,即私钥信息语法标准,是专门为私钥设计的规范。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    PrivateKeyInfo ::= SEQUENCE {
    version Version,
    algorithm AlgorithmIdentifier,
    PrivateKey OCTET STRING
    }

    AlgorithmIdentifier ::= SEQUENCE {
    algorithm OBJECT IDENTIFIER,
    parameters ANY DEFINED BY algorithm OPTIONAL
    }

公私钥互相推导

根据上面公私钥生成的步骤可以知道,ed ≡ 1 (mod φ(n))n=pq。如果只知道公钥(n, e)的前提下,是否能推导出私钥(n, d)呢?

从理论上来讲,n 可以被因数分解,那么就可以求出 d,也就是可以推导出私钥(n, d)。因此推导过程取决于 n 的因数分解难度。也就是,n 越大,那么对 n 做因数分解越困难,RSA 算法越可靠

但是在 pkcs 标准(Public-Key Cryptography Standards,公开秘钥加密标准)中规定,私钥包含(n, d, e, p, q),公钥包含(n, e)。

根据标准,私钥中包含了公钥,能够通过私钥生成公钥;但是却无法通过公钥颓然出私钥。因为虽然能通过公钥推导出(n, d),但却无法推导出(n, d, e, p, q)。

这也是为什么实例应用中,我们通过密钥生成工具生成的私钥比公钥长的原因了。

生成公私钥

生成公私钥需要用到 openssl 库,如果未安装,需要提前安装好,具体的 openssl 语法参考这篇文档

  • 安装 openssl

    1
    yum install -y openssl
  • 生成 RSA 私钥

    1
    openssl genrsa -out rsa_1024_priv.pem 1024

    密钥长度一般为 1024、2048、4096等,长度不同,可加解密明文长度也不同;如 1024 位私钥表示私钥为 1024bit,也就是 1024/8 = 128 Bytes,一次可加密的明文长度为 128 - 11 = 117 Bytes

    密钥长度增长一倍,公钥操作所需时间增加约 4 倍,私钥操作所需时间增加约 8 倍,公私钥生成时间约增长 16 倍

  • 将 RSA 私钥转换为 PKCS8 格式

    私钥从语法层面上分 PKCS1 和 PKCS8 两种,默认情况下生成的是 PKCS1 格式的私钥,如果需要 PKCS8 格式的私钥,则需要使用以下命令转换:

    1
    openssl pkcs8 -topk8 -inform pem -in rsa_1024_priv.pem -outform pem -nocrypt -out rsa_1024_priv_pkcs8.pem

    通过 PHP、.NET 使用的是 PKCS1 格式的私钥,JAVA 采用的是 PKCS8 格式的私钥,两种格式的私钥生成的公钥内容是一样的。

    另外,如果需要将 PKCS8 格式转换为 PKCS1 格式,可以采用以下命令:

    1
    openssl rsa -in rsa_1024_priv_pkcs8.pem -out rsa_1024_priv.pem
  • 根据私钥生成 RSA 公钥

    公钥没有语法格式之分,只有一种格式。

    1
    openssl rsa -in rsa_1024_priv.pem -pubout -out rsa_1024_pub.pem

实践

项目中前端通过工具 jsencrypt 对敏感信息进行加密,然后传输给后端。

另外做了个小 Demo,私钥和公钥都提前生成好了,只是提供基础的加密解密功能。

参考