BUUCTF 每日打卡 2021-4-2

引言

啊，假期就要开始了，好耶！ 明天还有虎符CTF要打（TTK，一直摸TTK）

信息化时代的步伐

打开附件，只见一串数字：”606046152623600817831216121621196386“ 我直接“？？？” 再看题目描述： 还是摸不着头脑 只好搜题解 说是中文电码，又是没见过的密码[捂脸] “也许中国可以早早进入信息化时代，但是被清政府拒绝了”： 自摩尔斯电码在1835年发明后，一直只能用来传送英语或以拉丁字母拼写的文字。1873年，法国驻华人员威基杰（S·A·Viguer）参照《康熙字典》的部首排列方法，挑选了常用汉字6800多个，编成了第一部汉字电码本《电报新书》。后由任上海电报局首任总办的郑观应将其改编成为《中国电报新编》。（摘自wiki） flag 为：flag{计算机要从娃娃抓起} 这句话是1984年邓小平同志说的：数十年后一位伟人说的话 中文电码加密解密：http://code.mcdvisa.com/

RSA1

dp dq 泄露的题没做过（别问，问就是看wp） 当然，剽窃别人的答案是可耻的，我们还要“剽窃”别人的知识（嘿嘿嘿） 参考博客：RSA之拒绝套路(2) 这篇博客讲得很详细，但仍有地方可以细化和纠错 作为一个数理基础不扎实的数院学生，花了老半天才看明白 下面，让我来逐步推导（也当练习 \(Latex\)了）： 首先，什么是 \(dp\) 和 \(dq\)： \[ \begin{cases} dp \equiv d\space mod\space (p-1)\\dq \equiv d\space mod\space (q-1) \end{cases} \] 然后，由 RSA 加密算法可得： \[ \begin{cases} n = p*q\\c \equiv m^{e}\space mod\space n\\m \equiv c^{d}\space mod\space n \end{cases} \] 因此，要求出密文 \(m\) ，我们必须求出 \(c^{d}\) 由 \(m \equiv c^{d}\space mod\space n\) 可得 \(\exists\space k_{1} \in\mathbb{Z}, \space s.t.\) \[ m=c^{d}+k_{1}*n=c^{d}+k_{1}*p*q \] 再对等式两边分别模 \(p, q\) ，含 \(p, q\) 的项在模 \(p, q\) 时为 \(0\) 得 \[ \begin{cases} m_{1} \equiv c^{d}\space mod\space p\cdots\cdots (1)\\m_{2} \equiv c^{d}\space mod\space q \cdots\cdots (2)\end{cases} \] (原文此处标注错误) 由 \((1)\) 式可得 \(\exists\space k_{2} \in\mathbb{Z}, \space s.t.\) \[ c^{d}=k_{2}*p+m_1 \] 代入 \((2)\) 式可得 \[ m_{2} \equiv (m_{1}+k_{2}*p)\space mod\space q \] 可得 \(\exists\space k_{3} \in\mathbb{Z}, \space s.t.\) \[ m_{2}=m_{1}+k_{2}*p+k_{3}*q \] 移项，两边模 \(q\) 可得 \[ (m_{2}-m{1})\equiv k_{2}*p\space mod\space q \] 由于 \[ gcd(p, q)=1 \] 由裴蜀定理，\(\exists\space u,v \in\mathbb{Z}, \space s.t.\) \[ u*p+v*q=1 \] 两边模 \(q\) 得 \[ u*p\equiv 1\space mod \space q \] 故可以求p的逆元，且上式中的 \(u\) 即为 \(p\) 的逆元，即 \(p^{-1}(mod\space q)\) ，得到 \[ (m_{2}-m_{1})*p^{-1}\equiv k_{2}\space mod\space q \] 将以下三式 \[ \begin{cases} k_{2}\equiv (m_{2}-m_{1})*p^{-1}\space mod\space q\\c^{d}=k_{2}*p+m_1\\m \equiv c^{d}\space mod\space n \end{cases} \] 合并可得 \[ m \equiv (((m_{2}-m_{1})*p^{-1}\space mod\space q)*p+m_1)\space mod\space n \] 最后求 \(m_{1},m_{2}\) 因为有 \[ \begin{cases} d \equiv dp\space mod\space (p-1)\\d \equiv dq\space mod\space (q-1) \end{cases} \] 又 \[ \begin{cases} m_{1} \equiv c^{d}\space mod\space p\\m_{2} \equiv c^{d}\space mod\space q \end{cases} \] 代入得 \[ \begin{cases} m_{1} \equiv c^{dp\space mod\space (p-1)}\space mod\space p\\m_{2} \equiv c^{dq\space mod\space (q-1) }\space mod\space q \end{cases} \] 以 \(dp\) 为例，由 \(d \equiv dp\space mod\space (p-1)\) 可得 \(\exists\space k \in\mathbb{Z}, \space s.t.\) \[ d = dp+k*(p-1) \] 代入得 \[ m_{1} \equiv c^{dp+k*(p-1)} \space mod \space p\equiv c^{dp}*c^{k*(p-1)} \space mod \space p \] 由费马小定理，因为 \(p\) 是素数，且 \(gce(p, c) = 1\)（由于 \(p\) 是大素数，而 \(c\) 是偶数），则 \[ c^{(p-1)} \equiv 1\space mod\space p \] 故 \(\exists\space k_{4} \in\mathbb{Z}, \space s.t.\) \[ c^{k*(p-1)} = (c^{p-1})^{k} = (1+k_{4}*p)^{k} \] 对右式二项式展开再模 \(p\) 可得 \[ c^{k*(p-1)} \equiv 1 \space mod \space p \] 故 \[ m_{1} \equiv c^{dp} \space mod \space p \] 同理可得 \[ m_{2} \equiv c^{dq} \space mod \space q \] 最终得方程组 \[ \begin{cases} m_{1} \equiv c^{dp} \space mod \space p\\m_{2} \equiv c^{dq} \space mod \space q\\m \equiv (((m_{2}-m_{1})*p^{-1}\space mod\space q)*p+m_1)\space mod\space n \end{cases} \] 代码实现如下：

from Crypto.Util.number import *
import libnum

p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852

def decrypt(dp, dq, p, q, c):
    n = p*q
    InvQ = inverse(p, q)
    m1 = pow(c, dp, p)
    m2 = pow(c, dq, q)
    m = ((((m2 - m1)*InvQ) % p) * p + m1) % n
    print(libnum.n2s(m))

decrypt(dp, dq, p, q, c)

结语

终于肝完了，已经燃尽了（躺） 明天还要打比赛 希望能继续坚持