RSA算法之我见

发表于2018-09-19 作者 admin

一、缘起

8月份的时候，现网使用的某应用使用的RSA算法进行加解密（管理端使用公钥加密，被管理端使用私钥解密），而后被我通过一些技术手段取得了公钥信息，进而写出了一个可以对接的crack小程序，在告诉相应的开发人员以后，其让为RSA是不可能被破解的，其实其忽略了RSA算法的基础。本篇就总结下我所了解的RSA加密。

二、RSA的历史

<img src="https://www.361way.com/wp-content/uploads/2018/09/RSA-histroy.png" width="501" height="281" title="RSA-history" alt="RSA-history" />



RSA的算法历史我将其分为三个块：



<br />

理论基础块：最早源于1636年的费马小定理，几十年后的欧拉在验证费马小定理的基础上，提出了欧拉定理。而RSA算法就是在欧拉定理的基础上的应用。
军用阶段：1973年英国的一位在英国政府通讯总部工作的数学家Clifford Cocks提出了一种类RSA的非对称加密数法，不过该算法直到1997年才公布；
民用阶段：1976年美国的两位数学家提出了密钥交换算法，1977年三位在麻省理工学院工作的数学家一起研究出了RSA算法，而RSA的名称就是从三个人名字里各提了一个字母结合而成的。

<br />



殴拉定理如下：



<span><span class="eS"><strong>a</strong></span><sup><span class="eS"><strong>φ</strong></span><span class="mS"><strong>(</strong></span><span class="eS"><strong>n</strong></span><span class="mS"><strong>)</strong></span></sup><span class="mS"><strong>≡</strong></span><span class="mS"><strong>1</strong></span><span class="mS"><strong>(</strong></span><span class="mS"><strong>mod</strong></span><span class="eS"><strong>n</strong></span><span class="mS"><strong>)</strong></span></span>

三、涉及的数学概念

1、涉及的数学名词

公约数
质数
互质数
欧拉定理

2、6个数值

在很多编程语言里用到的有三个值n、e、d ，ne的组合为rsa的公钥，nd为私钥。服务器将公钥发给客户端。在以后的加密解密中，公钥用于加密和签名验证，私钥用于解密与签名。<span style="color:#E53333;">加密数字K：计算C=(K^e)%n，C即为加密后的数据 解密C得到K：K=(C^d)%n ,签名采用相反的方式，即服务器用私钥加密，客户端用公钥解密，验证解密后的数据</span>。



<br />

　　p
　　q
　　n  modulus   模
　　φ(n)
　　e  exponents 指数
　　d
公钥 (n,e) 用于加密
私钥 (n,d) 用于解密

相关计算公式如下：



<img src="https://www.361way.com/wp-content/uploads/2018/09/rsa-key.png" alt="" />

3、相关理念

<br />

私钥可以推导出公钥
RSA不是不可解的，只因取的整数比较大，进行因数分解比较难。

<br />



人类已经分解的最大整数（232个十进制位，768个二进制位），我们常用的1024和2048位都是指的二进制位。RSA相对还是安全的，768位的计算是在2010年左右公布的，是在上百台的计算机集群上运行了两年才解出的。RSA算法最大的杀手是量子计算，几百量子 的计算机，可以在数秒内解出1024位的因数分解。不过几百量子位算力的计算机能搞出来也不知道是什么时候的事了。

四、openssl rsa相关

<br />

# 生成私钥
openssl genrsa -out privatekey.txt 2048
# 由私钥导出公钥
openssl rsa -in privatekey.txt -pubout -out publickey.txt
# 以n d e p q格式查看
openssl pkey -in privatekey.txt -inform PEM -text

由于以n d e p q格式查看的输出转多，这里只输出部分。



<img src="https://www.361way.com/wp-content/uploads/2018/09/inform.png" width="428" height="355" title="inform.png" alt="inform.png" />



利用该命令查看到私钥格式如下：



<br />

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
}

在文档 RFC3447 中定义了 RSA 密钥的语法结构，私钥的语法结构如上所示。 version 是 RSA 的版本号，本文中使用的密钥版本号是 0，如果密钥是使用多素数（多于 2 个素数）版本号则为 1。



<br />

modulus 是 RSA 的合数模 n。
publicExponent 是 RSA 的公开幂 e。
privateExponent 是 RSA 的私有幂 d。
prime1 是 n 的素数因子 p。
prime2 i 是 n 的素数因子 q。
exponent1 等于 d mod (p − 1)。
exponent2 等于 d mod (q − 1)。
coefficient 是 CRT 系数 q–1 mod p。
otherPrimeInfos 按顺序包含了其它素数 r3，……，ru 的信息。如果 version 是 0 ，它应该被忽略；而如果 version 是 1，它应该至少包含 OtherPrimeInfo 的一个实例。

RSA 公钥的语法结构如下所示，可见公钥所需的因子信息都包含在私钥中：



<br />

RSAPublicKey ::= SEQUENCE {
 modulus INTEGER, -- n
 publicExponent INTEGER -- e
}

OpenSSH 的 RSA 密钥的文件体使用 DER 编码，JDK 提供了 DerInputStream 来解析 DER 编码的字符串。所以 OpenSSH 密钥的解析很简单，首先读取密钥，过滤掉开始和结束标志，文件头（如果是加密的密钥则需要根据文件头信息来确定解密方式，因本文使用未加密的密钥故去掉文件头），然后使用 DER inputstream 来解析密钥。

五、openssl与ssh-keygen

ssh-keygen就可以直接生成密钥认证对的，而openssl生成的密钥对能不能给ssh用呢？（因为大家都是走的RSA认证。）



答案是私钥可以直霎，公钥不可以直接用，通过转化可以用。因为openssl命令导出的公钥格式为PKCS8格式，而ssh key认证使用格式为RFC4716格式。



具体可以参看 <a href="https://tools.ietf.org/html/rfc4716" target="_blank" rel="noopener">https://tools.ietf.org/html/rfc4716</a>



<br />

ssh-keygen -f publickey.txt -e -m pkcs8 > key.pub
From the ssh-keygen man page:
-m key_format
         Specify a key format for the -i (import) or -e (export) conversion
         options.  The supported key formats are:
         ``RFC4716'' (RFC 4716/SSH2 public or private key),
         ``PKCS8'' (PEM PKCS8 public key) or
         ``PEM'' (PEM public key).
         The default conversion format is ``RFC4716''.

-m参数在<strong>RHLE7</strong>版本里有，在此之前的版本里没有该参数，即openssh-7.4版本里发现有。



上面在相关理念里有提到私钥可以推导出公钥，哪ssh生成的公钥如果丢了或者删除了，只有私钥能不能生成公钥呢？



这个是当然可以的，而且ssh-keygen命令已经帮我们实现了：



<br />

# ssh-keygen -y -f mykey.pem > mykey.pub
# ssh-keygen -y [-f input_keyfile]
-y This option will read a private OpenSSH format file and print an OpenSSH public key to stdout.

<a href="use-rsa-private-key-to-generate-public-key" target="_blank" rel="noopener">use-rsa-private-key-to-generate-public-key</a>



同时通过openssl 命令还可以直接查看模的值（输出太多了，这里也只是取了modules的一部分）：



<br />

# openssl rsa  -modulus -in id_rsa
Modulus=C6BC3A3968B61B1AB571783BDB325FE0430AD9EA3FFC10C03C6C4FAA64CDE6F10534F2B534C88C9689B2315BA6B88F33223FB4265B3F9C926F1F8E1

六、进制转换

在很多编程语言里，会发现，上面提到的n d e都是在代码里会以十进制形式存在，而上面的命令我们查看到的是十六进制，JAVA引用代码如下:



<br />

PublicKey publicKey = Testclient.getPublicKey("98290099109057374932919249469161865256641935155149738301916331467469001708103109836087", "65537");
encrypted = Testclient.encrypt(content, publicKey);

这个处理其实非常简单，将上面openssl 查看得到的值，通过十六进制和十进制之间的转换即可。

<br />

>>> int('0x10001', 16)
65537
>>> int('BEB90F8AF5D8A7C7DA8CA74AC43E1', 16)
61893117520429489358314352530965473L

<br />

发表回复取消回复