[2021铁人赛 Day23] Cryptography 密码学题目 01

引言
我们前几天已经把 General Skills 完成了，所以今天开始 (已经没剩几天了
就至少会把六大领域各做一题以上，不过这个密码学领域应该只会出现一天，也就是今天，
因为今天会做两题 (有一题较简单) ，那就开始吧～

Cryptography / Mod 26

题目给了一段乱码，但是很明显可以看出这是 flag 格式，底线、大括号都没有变，
然後说要用 ROT13 解决，关於 ROT13 可以看看这里 (维基百科)，
其实简单来讲它就只是把每个字母往前往後推算几个字母，超过 z 则回到 a 的概念，
可以算是密码学中最简单的方法之一了，因为一共 26 个字母，
ROT13 的移动量刚好一半，所以你对一个字母做两次 ROT13 会回到本身。

这题有两种解法，其一是用线上翻译器破解，另一个是自己写程序。
我两个都提供给大家：

1. rot13.com 线上 ROT13 加密/解密器
   你丢明文会跑出密文，丢密文会跑出明文，它们是互相对称的。
2. 写个 Python 程序
   其实就是从原理下手去写，程序贴在下方：

   s = input()
   for c in s:
       oc = ord(c)
       if oc >= ord('A') and oc <= ord('Z'):  # 大写
           coc = chr((((oc-ord('A'))+13)%26)+ord('A'))
           print(coc, end='')
       elif oc >= ord('a') and oc <= ord('z'):  # 小写
           coc = chr((((oc-ord('a'))+13)%26)+ord('a'))
           print(coc, end='')
       else:
           print(c, end='')
   print()
   

   只有英文大小写需要转换，其他符号记得要忽略。

Cryptography / Mind your Ps and Qs

这题稍微难一点点，是考 RSA 加密，这是一种非对称加密，
简单来说就是加密与解密需要的钥匙不是同一把，
加密用的叫公钥 (e) ，会公开，解密用的叫私钥 (d) ，不会公开，
细节可以看看维基百科的说明，这边简单讲一下如何取得两把钥匙：

<从维基百科 RSA 撷取>

1. 随意选择两个大的质数 p 和 q ， p 不等於 q ，计算 N=pq 。
2. 根据欧拉函数，求得
3. 选择一个小於 r 的整数 e ，使 e 与 r 互质。并求得 e 关於 r 的乘法反元素，命名为 d（求 d 令 ）。（乘法反元素存在，若且唯若 e 与 r 互质）
4. 将 p 和 q 的记录销毁。

好，说简单讲其实也不简单对吧，你只要先知道有 N, p, q, r, e, d 这些数就够了，
其中 N, r 是由 p, q 产生，而 e 根据 r 产生， d 是 e, r 产生的。
所以其实 p, q 才是大家的父母，也就是说想破解的人找到 p, q 是至关重要的。

下面讲一下如何加密与解密：
首先，明文以 n 表示，密文以 c 表示。

1. 将 n 加密成 c ：
   
   「n 的 e 次方」 除以 「N」 的余数是 「c」
2. 将 c 解密回 n ：
   
   「c 的 d 次方」 除以 「N」 的余数是 「n」

先回到题目，题目给了我们一个档案，我们打开它：

Decrypt my super sick RSA:
c: 964354128913912393938480857590969826308054462950561875638492039363373779803642185
n: 1584586296183412107468474423529992275940096154074798537916936609523894209759157543
e: 65537

总之就是请你用 RSA 解密，题目给你 c, n, e ，这里的 n 当然是大写 N ，不然你就直接有答案了。
所以我改一下变成这样 (n 改 N)：

Decrypt my super sick RSA:
c: 964354128913912393938480857590969826308054462950561875638492039363373779803642185
N: 1584586296183412107468474423529992275940096154074798537916936609523894209759157543
e: 65537

我们从上面看到解密需要 c, d, N ，但是题目给 c, e, N ，缺 d 。
大家往上看到我写的拿到密钥的 4 点，你要 d 必须有 e, r ， e 有了，
我们缺的是 r ，而 r 从 (p-1) * (q-1) 来，所以需要 p, q 。

这就验证了最重要的数字是 p, q 两人，你唯一有的资讯是由他们俩乘起来的 N ，
意思就是你必须对 N 做质因数分解才能得到 p, q ，但你可以看看 N 到底多大...
基本上一般情况你用一般电脑是没办法对那麽大的数做质因数分解的，
数字太大几万年都做不到，这也是 RSA 相对安全的地方。

但是这题的 N 我们可以马上解出来，归功於 factordb 这个工具！
这个字直翻其实就是因数资料库 (factor database) ，
它纪录着许多已知的质因数分解，包括非常大的数在内。

这题没有为难你，因为题目给的 N 是可以在 factordb 查到分解结果的，
factordb 连进网站，贴上 N：

N 就等於
2434792384523484381583634042478415057961
x
650809615742055581459820253356987396346063
而这两个数就是 p, q 。

要记得这件事绝没那麽容易，这是题目给你刚好有分解资料的，否则几乎不可能解出。

有了 p, q 其实答案就呼之欲出了，但我们需要动手写程序：

c = 964354128913912393938480857590969826308054462950561875638492039363373779803642185
N = 1584586296183412107468474423529992275940096154074798537916936609523894209759157543
p = 2434792384523484381583634042478415057961  # factordb 找到的
q = 650809615742055581459820253356987396346063  # factordb 找到的
e = 65537
r = (p-1) * (q-1)
d = pow(e, -1, r)  # 求 e mod r 的乘法反元素 d
ans = pow(c, d, N)  # 求 c 的 d 次方 mod N 就是原本的明文

b = bin(ans)[2:]  # 明文转成二进位表示
b = '0' + b  # 可以由二进制字串长度发现长度不是 8 的倍数，前面要补 0
i = 0  # 下面准备每八个切成一组表示成字元
for i in range(len(b)//8):
    j = i*8
    print(chr(int(b[j:j+8], base=2)), end='')
print()

其中 pow() 的用法呢，求乘法反元素的部份需要在 Python 3.8 以後才能使用，
而 pow(a, b, c) 的格式代表「 a 的 b 次方 mod c 」，如果是乘法反元素，
「求 e mod r 的乘法反元素 d」数学上会表示成「 d = e 的 -1 次方 mod r 」，
才会写成 pow(e, -1, r) 。

最後 print 出 picoCTF{sma11_N_n0_g0od_73918962} 。 ( 你的 flag 跟我不一样 )