(译) SSH RSA的公钥和私钥面是什么

密码学, 翻译, | Comments

原文:What’s in a SSH RSA key pair?

你也许有自己被保护好的ssh密钥对,而且很可能是基于ssh-keygen的默认选项,RSA生成的。

RSA是一个非常简单却相当精彩的算法,这篇文章会说明SSH RSA密钥对里包含了什么,以及有了这些值你可以用来干嘛,还会教你怎样只用一个计算器来加密数据。

RSA算法是基于质数和大整数质数分解难的原理。这篇文章的目的不是为了介绍RSA,不过这里有一个快速回顾。大部分情况下我会使用和Wikipedia上一样的符号:首先你产生两个大的质数, p 和 q。φ = (p-1)(q-1)。选择一个e和φ互质,d ≡ e^-1 mod φ。

这样就能产生公钥(e, n)和私钥(d, n)。如果要加密一个数字或者消息m, 可以通过计算 c ≡ me mod n,得出加密后的c,计算m ≡ cd mod n来解密。

这是一个非常简单的取余运算,不过当你用ssh-keygen生成一组密钥对的时候,你得到的却是一些难以读懂而且看起来有点吓人的文件,id_rsaid_rsa.pub。这里是一些id_rsa文件里的内容(没设密码的):

1
2
3
4
5
6
-----BEGIN RSA PRIVATE KEY-----
MIIBygIBAAJhANj3rl3FhzmOloVCXXesVPs1Wa++fIBX7BCZ5t4lmMh36KGzkQmn
jDJcm+O9nYhoPx6Bf+a9yz0HfzbfA5OpqQAyC/vRTVDgHhGXY6HFP/lyWQ8DRzCh
tsuP6eq9RYHnxwIBIwJhAKdf+4oqqiUWOZn//vXrV3/19LrGJYeU
...
-----END RSA PRIVATE KEY-----

我们怎样才能从这一团糟中得到我们漂亮的RSA的参数呢?

简单的方式是通过openssl: (我先为下面文章中的垃圾数据道个歉)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
[email protected] ~/.ssh $ openssl rsa -text -noout < id_rsa
Private-Key: (768 bit)
modulus:
00:d8:f7:ae:5d:c5:87:39:8e:96:85:42:5d:77:ac:
54:fb:35:59:af:be:7c:80:57:ec:10:99:e6:de:25:
...
publicExponent: 35 (0x23)
privateExponent:
00:a7:5f:fb:8a:2a:aa:25:16:39:99:ff:fe:f5:eb:
57:7f:f5:f4:ba:c6:25:87:94:48:64:93:fb:3d:a7:
...
prime1:
...
prime2:
...
exponent1:
...
exponent2:
...
coefficient:
...

这里的modulus就是n, publicExponent是e, privateExponent是d, prime1和prime2是p和q,exponent1是这篇Wikipedia文章中提到的dP,exponent2是dQ,coefficient是qInv。

只有前三个是执行加密和解密必须的,剩下的三个是为了优化计算,而两个质数是用来验证的。

有趣的是要注意,尽管从RSA的视角来看私钥只是(d,n),OpenSSH的私钥还包含了e,p,q和剩下的几个。这样它就可以从私钥中生成公钥。否则给出(d,n)要找出e,和给出(e,n)要找出d一样困难,除非e是通常选择的一个非常小的数,这样可以很快的猜到。

如果我们把这些16进制的字符串放在一行,去掉冒号,并且改成大写,就可以用bc来处理和转换成十进制格式。

1
2
3
4
5
6
7
8
9
10
# If you don't want to do this yourself, see end for a script
[email protected] ~/.ssh $ { echo 'ibase=16'; cat | tr -d ':\n ' | tr a-f A-F; echo; } | bc

00:d8:f7:ae:5d:c5:87:39:8e:96:85:42:5d:77:ac:
54:fb:35:59:af:be:7c:80:57:ec:10:99:e6:de:25:
98:c8:77:e8:a1:b3:91:09:a7:8c:32:5c:9b:e3:bd:
....
Ctrl-d to end input
13158045936463264355006370413708684112837853704660293756254884673628\
63292...

我们还需要一个计算同余幂的函数,因为如果要通过计算be来计算be % m 会非常慢。幸运的是bc是可编程的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
[email protected] ~/.ssh $ bc
bc 1.06.94
Copyright 1991-1994, 1997, 1998, 2000, 2004, 2006 Free Software Foundation, Inc.
This is free software with ABSOLUTELY NO WARRANTY.
For details type `warranty'.

# Our powermod function:
define pmod(b,e,m) { if(e == 0 ) return 1; if(e == 1) return b%m; rest=pmod(b^2%m,e/2,m); if((e%2) == 1) return (b*rest)%m else return rest; }


#Define some variables (this time unabbreviated)
n=13158045936463264355006370413708684112837853704660293756254884673628\
63292777770859554071108633728590995985653161363101078779505801640963\
48597350763180843221886116453606059623113097963206649790257715468881\
4303031148479239044926138311

e=35

d=10150492579557375359576342890575270601332058572166512326253768176799\
23111571423234513140569517447770196903218153051479115016036905320557\
80231250287900874055062921398102953416891810163858645414303785372309\
5688315939617076008144563059



# Encrypt the number 12345
c=pmod(12345, e, n)

# Show the encrypted number
c
15928992191730477535088375321366468550579140816267293144554503305092\
03492035891240033089011563910196180080894311697511846432462334632873\
53515625


#Decrypt the number
pmod(c, d, n)

12345

耶,我们已经成功的用真实的RSA参数来加密和解密数据!

所以,公钥里面放的又是什么?

1
ssh-rsa AAAAB3NzaC1yc2EAAAABIwAAAGEA2PeuXcWHOY6WhUJdd6xU+zVZr758gFfsEJnm3iWYyHfoobORCaeMMlyb472diGg/HoF/5r3LPQd/Nt8Dk6mpADIL+9FNUOAeEZdjocU/+XJZDwNHMKG2y4/p6r1FgefH [email protected]

这是一个非常简单的文件格式,我不知道有什么现成的工具可以解码它。不过只要通过base64解码中间的字符串,就会发现它是4个字节的长度,跟着对应长度的数据。尝试三次以后就能得到密钥的类型,e和n。

我的是00 00 00 07,跟着7个字节的"ssh-rsa"。然后是 00 00 00 01跟着一个字节的0x23(35, 我们的e)。最后是00 00 00 61跟着0x61=97字节的模数n。

如果你想手动的解码私钥,可以用base64解码中间的部分,你会得到一个ASN.1编码的一串数字。

这是一部分注解后的解码的16进制私钥:

1
2
3
4
5
6
7
8
9
10
30 82 01 ca   - Sequence, 0x01CA bytes
02 01: Integer, 1 byte
00
02 61:    - Integer, 0x61 bytes (n).
00 d8 f7 ae 5d c5 87 39 8e 96 ... Same as from openssl!
02 01:  - Integer, 1 byte, 0x23=35 (e)
23
02 61  - Integer, 0x61 bytes (d)
00 a7 5f fb 8a 2a aa 25 16 39 ...
...

这里有个bash脚本可以用来解码私钥,输出给bc用的变量定义和函数,你可以自己试着自己玩一下。它会解码ASN.1,在密钥设密码时需要使用openssl。

在执行的时候,把输出粘贴到到bc,你就能得到n, e, d, p, q和一些其它变量,还有encrypt(m)和decrypt(c)加上一个verify()函数,它会在key是合法的时候返回1,这些函数都很简单直接。

玩的开心!

Comments