Yusa的密码学日常——PEM

发表于 阅读次数：

首先题目给了部分私钥，是pem格式文件给的，但是只给了部分

这里肯定不是直接用私钥读取的脚本一把梭的。但还是贴一个

1
2
3
4
5
6
7
8
from Crypto.PublicKey import RSA
with  open ("private.pem",'rb') as f:
    key = RSA.import_key(f.read())
    print('n = %d' % key.n)
    print('e = %d' % key.e)
    print('d = %d' % key.d)
    print('p = %d' % key.p)
    print('q = %d' % key.q)

所以只能从私钥文件入手，找到一篇文章
https://blog.csdn.net/he25819/article/details/119467334

按照文章，先给出的私钥内容进行编码转换

图片

可得到一些hex也就是十六进制表示的信息

在文章中可以知道

PKCS#1形式的私钥结构

在RFC 2347中，我们可以得到RSA私钥的ASN.1定义，如下：

1
2
3
4
5
6
7
8
9
10
11
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 
}

也就是说一个正常的私钥文件，其中应该会包含以上要素
那么这些元素所对应的hex应该是这样（举例）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
30 82 04 A2 
    02 01 
        00 
    02 82 01 01 
        00 9C B7 68 03 76 DA E7 B6 07 04 07 A7 61 B2 C6 4D C7 42 E3 C5 55 BD 55 43 5D 5E 8D FD 6F B5 17 3B 41 46 3B CD 3D 5D 43 30 E7 08 24 1A EF 79 39 60 2A E8 36 3C 25 72 9D A2 2D B5 A3 6A 97 AA 7F F8 19 B8 1B 8D 64 C9 96 32 ED 14 9A 50 26 89 DE BC A3 71 7B 0A 7C 29 6D 9C 6F 6F 0B 06 C8 37 E6 D5 72 1C 51 CE 3E F7 F7 32 00 D6 D0 47 9F DB F6 D8 F8 45 70 47 EC 48 0C B6 1B 61 30 33 86 D0 DF C9 F6 52 B3 2C 7B DC 1B 2D 41 93 D2 4C F2 AA EC 0F 42 CE EF AE 25 3E D5 70 64 AD DB 2C A0 0A 9B C2 05 B9 C9 4A B1 0E 8B 18 07 98 7B 0F 56 13 5B 4A 8A 90 9E 8F 3C D9 CB 5D B3 2F D8 C7 B2 8F 1A B5 B1 B5 A8 17 F9 BC B9 BA 1A 2A 49 6A 6A 5D 5E A7 95 2A 4E 9F 4E 14 D3 9A 4E B5 72 5D 8E 06 92 DE F0 AB 73 A8 36 F9 3D D9 C2 75 7C 7C FD C2 7A E2 1A 8F A8 36 EB 7D 81 0A F5 59 58 CE CD 19 00 C3 
    02 03 
        01 00 01 
    02 82 01 00 
        31 56 2C 10 AB 22 4F 40 27 05 45 C3 94 26 4B F7 C0 7B 76 69 71 8C A1 83 0B A9 F0 D9 90 89 5A 3E F5 55 BF 0D E5 FB AE 63 7E D8 39 45 A1 8E 70 59 AE 28 5C AA A2 BF 6A 90 DC 03 0A E7 4B C8 09 71 79 E7 54 05 37 6D 9F 33 79 1F BB 54 F0 4D 07 2A 2B EA 55 E9 FF 1C AB BD 4B F7 91 69 19 2F 40 24 82 40 18 20 EE 01 F2 78 73 7B 2D 26 DF 54 C8 69 95 FF 86 51 9E 39 30 87 44 27 5C 9D 5C 1B F5 D7 88 D4 9D E0 AD 0F 3C B0 A2 EC C8 A6 ED 60 CB DE 44 F9 B7 73 D8 29 4F 38 8C 24 91 29 56 B8 E0 94 0A E2 22 27 5B A4 51 90 BE A9 0E 66 EB A1 5C 68 93 D4 25 64 E3 97 B0 56 E1 9F 07 B6 AD 3F 5E 92 66 BB CC AC 4E 80 46 52 D7 3A 57 0D 52 E5 E9 49 37 62 F7 2E C0 0D C3 92 A6 A6 F6 0F D7 9F 1B 98 3E 20 8E F5 67 ED 19 A9 70 F0 82 F4 73 05 B8 30 01 5E 55 01 64 4E 29 BE 84 0A 38 BD EB F2 27 C1 
    02 81 81 
        00 D0 8E EF 5F F7 98 86 28 CC 96 71 53 0A 4D BB 84 02 68 0A E7 19 C6 82 7C 7F E4 F4 44 FB EF 6C 39 33 C1 33 F4 1A 28 72 A6 F3 32 09 6A 3A CD 25 3C A0 C1 28 96 87 2D 52 97 51 D5 9D 63 3A 74 73 D6 13 7B 60 A7 38 F3 84 D3 9D 2B 6E A4 71 DE 65 7F 5A 8F 0D 46 9F 2B F5 B0 64 83 F8 95 56 84 7B BF 04 DF 18 FD 0D DB 2A 55 15 2D 71 54 52 AC BD 19 45 2E 0B 84 AB BD 86 69 AE C0 BC 45 4C 31 4B CD 
    02 81 81 
        00 C0 5D 8A 29 17 C5 32 BF 92 B3 94 F1 B1 79 90 3E CE F1 B5 42 BB 4C F4 22 1B CF FB AD 46 92 9B AB 9E 60 73 12 EB 53 84 AC D5 58 7B F7 F7 56 63 FD 3B F1 18 8D 4B 67 BB 98 CB 4A D4 62 B8 5A 08 A0 38 E6 F4 74 7C 56 33 2C 99 38 A5 AB F0 83 C9 06 78 98 18 B9 F8 81 C9 5C 6F E1 82 A1 A1 D5 08 D6 BE 20 90 CA D6 E5 79 F9 DF E1 A7 A2 B0 1E D5 6F F9 3C 68 96 24 29 06 16 22 DA 2A 48 86 F5 8E CF 
    02 81 80 
        57 C2 EE 24 1A 12 8A D1 FC 55 8A 56 81 4D 78 8C F2 5E 49 C8 39 E6 78 DE 5F 0B 3F 67 10 05 0E 2B 7C 05 DF 10 E7 39 02 16 12 DC 89 6D B4 54 C3 48 A1 F4 E6 59 81 84 A6 EE 9A 37 23 C5 AF C1 75 45 2E 69 8A A0 93 AC 95 C6 5E AA FA 22 24 F0 8B 11 6E 50 28 2C 01 AB 03 F6 38 35 F8 93 0F 17 2C E3 92 EF 36 9A B6 0B F5 E2 5B C9 05 99 90 38 B4 52 3F F4 42 50 8F DC 6F 05 65 CE 20 EB A0 46 56 39 
    02 81 80 
        02 70 6D 33 0E 31 1A EE A0 EE 94 01 E8 8D 31 0E 0A D3 B7 C7 AB D6 52 F6 27 C2 20 5F D7 18 3E CF 13 48 07 CD 82 9C 61 7F 4B 89 3E B1 2B 3A B6 33 DC D1 B6 CC FB DA C9 DF 2B 1C BC CA AF A9 BC 98 43 80 72 33 13 EC 87 E3 95 E1 C9 00 00 21 BB A7 D0 59 A5 5E 9E 4F 0E FD 94 11 98 F5 71 B6 E0 D0 D0 42 5B 73 A6 FB EB EB 06 32 B7 4C 71 CD 42 49 94 30 76 E7 08 78 58 B2 69 28 B9 06 88 67 8E B3 
    02 81 80 
        0F 6D 4D 97 25 5A BC 9D F9 B4 4D FF AF 56 09 44 1A D6 CE 8D 27 AA B3 F8 D1 D3 E3 3B B2 77 D4 5A 45 6F DA 62 C3 1D B4 C9 AE 19 84 72 A4 91 A5 F1 5B F3 D6 BC 71 E9 FA 99 BD D5 03 E6 65 78 25 AE CD A8 5B 77 1F 15 60 AC 5F AA 7F C0 29 91 A1 9C 44 91 8B 82 9C 02 4C 4E 73 9A 6D 90 31 44 28 BA ED 5D 7D 1B 6E 4D E2 EB 66 C9 0B 49 FE A5 E7 7E 63 57 D9 BC 67 43 13 1D 26 CF 92 FD 17 74 77 5B 

那我们可以发现028181以及028180这两者是分隔符，放到我们的题目来说
可以发现这些信息

根据私钥文件格式，从下到上依次为： q在modp意义下的逆元，dq，dp ，q

也就是

1
2
3
4
5
q=0xd46083c954cc3e6dda2135c2b3adcdea4e08218d9937a825c900aebb0e58145b27b53de45272f69cfb6de1261fc5297e08ed12b1d74402cbcde2a1aca7f5f27b0783662cbcae73483d78f60fa23e12f524f8bfc7606775c60c801ba270c47b799e7d8c356cef6b042cbfb9b6cba752cbeee7554768d8be27044b1cc39ed96819
dp=0x29b09a5194750e2b76ce488891e83b59009d69d167546a3214e18d94360b481e25044e6daa75df533422a93ccc9d89b29e3d5584168e177bb0e20296c73901686bc3860955a362ec32b70431072ff2ea91619ff9d18e320dcc9ab35461b0327c3eb54939ea26ef17f93ff1970a520e9ad9a21679daf8dcee09d7b1b4566713e1
dq=0xcdf941375d57ad608b42d44a1e4b7dbf35a8eb29d2a4c91ec4603616d32597b084c561de741c6d93f8c22baff6f61874d52160953cab086f33220f1d4dd4da347a27f54b843f492d91f923e42bbd3a53a964db52f9ebbdacb3e8f764472c3878cebf02e1b9e2460f497b3519d550559bd5fb64991a55c3ae419abbadf9fceed9
inv_q_mode=0x8272ad1401043aae94a928336d84933ec8291e5432f19033241661ba97af0715c54328e5e940832927834af8e0a479e021511dae99bcc46987a5a60685dbd4057dd1985bf9c20fcb85be58fda32edd3a6fda1872b26bf5b610f9b6ce68448c0aae5d1996b40fc9b9d82c7322c64cb947d249a2146ff039a0a75e5a7c9e0f1077
c=0x6ffb2c1a544f98759c74b74b048188484ca5c9ba0b10c1e4c8c40020b99d171a6f2c9b9cb830f73359f286e584f87e03936af0e7b13ed48c3792e8d696b0e376360a749f688ec58aef5992e6a64c7f94873b6dc4852c8c80102a077c432116965da6abe637ac147a9aa32e3c21b56bf4f4eabf26d85200874c5a2421a638ed6797d4c453c9cd241f934a989d7fbae72bbf1807a96bb6d6163ed837e4d446a433bb1d9d0294c84d505497c87767c6f961080b7c1cc15e6b937f6f7fe113e5c48c224e62cf4e45c4e899c075a17b4d66b49472a8eea20d2dac7be8154563df231228c531080bcd054491cbdbd8f1c5a5e73d779753a87cce46c872592079b543d0

对于任何一个rsa，只要有p,q,e,c就能够解题，但这里并没有给出p，所以没法利用dq.dp去进行获取p，这里给了我一个提示

1
Yusa把信息都提取出来了，你能帮Yusa把Bob发给Alice的flag给恢复出来嘛？她只知道flag的长度应该是40字节

flag的长度只有40字节，很明显小于q。根据原理n=pq phi=(p - 1)(q - 1)还有m=pow(c,d,n),d=invert(e,phi).flag的长度远小于q，所以对于n=p*q,可以把p忽略，同理d=invert(e,phi)也可以把p-1忽略。
重新构造一个rsa公式，可以得到n=q phi=q-1 d=invert(e,q-1)，m=pow(c,d,q)

思路理清了，写脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import gmpy2
from Crypto.Util.number import * 
import libnum

q=0xd46083c954cc3e6dda2135c2b3adcdea4e08218d9937a825c900aebb0e58145b27b53de45272f69cfb6de1261fc5297e08ed12b1d74402cbcde2a1aca7f5f27b0783662cbcae73483d78f60fa23e12f524f8bfc7606775c60c801ba270c47b799e7d8c356cef6b042cbfb9b6cba752cbeee7554768d8be27044b1cc39ed96819
dp=0x29b09a5194750e2b76ce488891e83b59009d69d167546a3214e18d94360b481e25044e6daa75df533422a93ccc9d89b29e3d5584168e177bb0e20296c73901686bc3860955a362ec32b70431072ff2ea91619ff9d18e320dcc9ab35461b0327c3eb54939ea26ef17f93ff1970a520e9ad9a21679daf8dcee09d7b1b4566713e1
dq=0xcdf941375d57ad608b42d44a1e4b7dbf35a8eb29d2a4c91ec4603616d32597b084c561de741c6d93f8c22baff6f61874d52160953cab086f33220f1d4dd4da347a27f54b843f492d91f923e42bbd3a53a964db52f9ebbdacb3e8f764472c3878cebf02e1b9e2460f497b3519d550559bd5fb64991a55c3ae419abbadf9fceed9
inv_q_mode=0x8272ad1401043aae94a928336d84933ec8291e5432f19033241661ba97af0715c54328e5e940832927834af8e0a479e021511dae99bcc46987a5a60685dbd4057dd1985bf9c20fcb85be58fda32edd3a6fda1872b26bf5b610f9b6ce68448c0aae5d1996b40fc9b9d82c7322c64cb947d249a2146ff039a0a75e5a7c9e0f1077
c=0x6ffb2c1a544f98759c74b74b048188484ca5c9ba0b10c1e4c8c40020b99d171a6f2c9b9cb830f73359f286e584f87e03936af0e7b13ed48c3792e8d696b0e376360a749f688ec58aef5992e6a64c7f94873b6dc4852c8c80102a077c432116965da6abe637ac147a9aa32e3c21b56bf4f4eabf26d85200874c5a2421a638ed6797d4c453c9cd241f934a989d7fbae72bbf1807a96bb6d6163ed837e4d446a433bb1d9d0294c84d505497c87767c6f961080b7c1cc15e6b937f6f7fe113e5c48c224e62cf4e45c4e899c075a17b4d66b49472a8eea20d2dac7be8154563df231228c531080bcd054491cbdbd8f1c5a5e73d779753a87cce46c872592079b543d0
e = 65537

d = gmpy2.invert(e,q - 1)
m = pow(c,d,q)
print(libnum.n2s(int(m)))