RSA总结

前言

最近做了一些 RSA 的题目,比赛时也发现了不少问题,自己的基础还不牢固,因此在此对 RSA 进行总结。


基础

RSA概要

  1. 随机选择两个不同大质数 $p$ 和 $q$,计算 $n = p \times q$。
  2. 根据欧拉函数,求得 $\varphi (n) = (p-1)(q-1)$。
  3. 选择一个小于 $\varphi (n)$ 的整数 $e$,使 $e$ 和 $\varphi (n)$ 互质,即 $gcd(e, \varphi (n)) = 1$。
  4. 求得 $e$ 关于 $\varphi (n)$ 的模逆元 $d$,有 $ed \equiv 1 \bmod \varphi (n)$。
  5. 将 $p$ 和 $q$ 的记录销毁。$(n,e)$ 是公钥对,$(n,d)$ 是私钥对。
  6. 加解密:$c = m^e \bmod n$, $m = c^d \bmod n$。其中 $m$ 为明文,$c$ 为密文,要求 $0 \leq m < n$


简单RSA解密

分析pem公钥文件

有的题目不会直接给出公钥对 $(n,e)$,而是会给出 pem 公钥文件,这时就需要分析公钥文件了。例如有public.key

1
2
3
4
-----BEGIN PUBLIC KEY-----
MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhANmelSKWptlg38JQSrpUW5RC1gp7npMK
/0UceOxV1VXrAgMBAAE=
-----END PUBLIC KEY-----

pycrypto 库直接得到公钥对:

1
2
3
4
5
from Crypto.PublicKey import RSA
with open('public.key', 'r') as f:
key = RSA.importKey(f)
print 'n =', key.n
print 'e =', key.e

1
2
n = 98432079271513130981267919056149161631892822707167177858831841699521774310891
e = 65537

分析密文

同样的,有的题也不会直接给出密文 $c$,而是给出加密后的文件,我们需要将之转换为整数。例如有encrypted.message1,按字节输出:

1
b'\x0b9\xcc\x1ba'\xd3\xbb\xed+\xc0E\x14\x8c\x91\x1dFy\x85\xa9K\x14~\xde\x80u\x0f\x95\xa3`\xd4z'

可以看到是字节与 ascii 码混合的形式。将之转换为整数:

1
2
3
4
from Crypto.Util.number import *

c = bytes_to_long(open('encrypted.message1', 'rb').read())
print 'c =', c

1
c = 5077560311513279671817430508125151837396585328082180175253360345086848717946

分解n

最简单的情况是可以直接分解 $n$ 得到 $p$ 和 $q$。
查询已知的 $n$ 的可分解情况:
http://factordb.com/
当 $p$ 和 $q$ 相差较大或较小时可使用yafu快速分解:

1
$ yafu-x64.exe factor(12345)

此处要注意 Status,判断是否成功分解。具体含义如下:

Status Meaning
C Composite, no factors known
CF Composite, factors known
FF Composite, fully factored
P Definitely prime
Prp Probably prime
U Unknown
Unit Just for “1”

将之前的 $n$ 分解可得到:

1
2
p = 302825536744096741518546212761194311477
q = 325045504186436346209877301320131277983

计算私钥d并求得明文

利用 gmpy2 库进行大数精确计算

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

n = 98432079271513130981267919056149161631892822707167177858831841699521774310891
p = 302825536744096741518546212761194311477
q = 325045504186436346209877301320131277983
# 检验 n == p * q
assert p * q == n
e = 65537
d = gmpy2.invert(e, (p - 1) * (q - 1))
c = 5077560311513279671817430508125151837396585328082180175253360345086848717946
# 计算 m
m = pow(c, d, n)
print 'd =', d
print 'm =', m
# 将整数明文转换为字符串
print long_to_bytes(m)

1
2
3
d = 1958518567680136759381316911808879057130620824462099039954817237801766103617
m = 4158303007256248428645717132056961048040890469299157691939817852236882442
flag{3b6d3806-4b2b

可以得到部分 flag。将三个密文按此解密后,可得到完整flag:flag{3b6d3806-4b2b-11e7-95a0-000c29d7e93d}


常见攻击方式

待将这篇博客的内容消化完之后再做补充。
https://xz.aliyun.com/t/2446#toc-16