文章目录

• 概述
• 题目
• • 解题思路
  • 解题代码

概述

Brainy’s Cipher是HackTheBox密码学的题目，题目地址https://app.hackthebox.eu/challenges/brainys-cipher，主要考点是RSA。

关于RSA的基础知识，可参考文章HackTheBox-Weak RSA

题目

下载附件并解压缩，得到如下文本

为brainfuck编码，访问https://www.splitbrain.org/services/ook，复制文本内容并解码得到

{p:7901324502264899236349230781143813838831920474669364339844939631481665770635584819958931021644265960578585153616742963330195946431321644921572803658406281,q:12802918451444044622583757703752066118180068668479378778928741088302355425977192996799623998720429594346778865275391307730988819243843851683079000293815051,dp:5540655028622021934429306287937775291955623308965208384582009857376053583575510784169616065113641391169613969813652523507421157045377898542386933198269451,dq:9066897320308834206952359399737747311983309062764178906269475847173966073567988170415839954996322314157438770225952491560052871464136163421892050057498651,c:62078086677416686867183857957350338314446280912673392448065026850212685326551183962056495964579782325302082054393933682265772802750887293602432512967994805549965020916953644635965916607925335639027579187435180607475963322465417758959002385451863122106487834784688029167720175128082066670945625067803812970871}

即

p = 7901324502264899236349230781143813838831920474669364339844939631481665770635584819958931021644265960578585153616742963330195946431321644921572803658406281
q = 12802918451444044622583757703752066118180068668479378778928741088302355425977192996799623998720429594346778865275391307730988819243843851683079000293815051
dp = 5540655028622021934429306287937775291955623308965208384582009857376053583575510784169616065113641391169613969813652523507421157045377898542386933198269451
dq = 9066897320308834206952359399737747311983309062764178906269475847173966073567988170415839954996322314157438770225952491560052871464136163421892050057498651
c = 62078086677416686867183857957350338314446280912673392448065026850212685326551183962056495964579782325302082054393933682265772802750887293602432512967994805549965020916953644635965916607925335639027579187435180607475963322465417758959002385451863122106487834784688029167720175128082066670945625067803812970871

解题思路

通过计算可知p与q互素

In [1]: p = 7901324502264899236349230781143813838831920474669364339844939631481665770635584819958931021644
   ...: 265960578585153616742963330195946431321644921572803658406281

In [2]: q = 1280291845144404462258375770375206611818006866847937877892874108830235542597719299679962399872
   ...: 0429594346778865275391307730988819243843851683079000293815051

In [3]: from gmpy2 import gcd

In [4]: gcd(p,q)
Out[4]: mpz(1)

dp≡d mod (p−1)
dq≡d mod (q−1)

现在要想得到明文m，就要得到 c^d

从m≡c^d (mod n)，可得 m = c^d + k * n = c^d + k * p * q，同时取余p和q，可以分别得到

m1≡c^d (mod p)
m2≡c^d (mod q)

带入上面的公式，可以得到c^d=kp+m1

把这个带入m2可以得到m2≡(kp+m1) (mod q)，两边同时减去m1

(m2−m1)≡kp (mod q)

可以计算p的逆元，得到 (m2−m1)*p⁻¹ ≡ k (mod q)

可以得到如下推导

k≡(m2 − m1) * p⁻¹ (mod q)
c^d = kp + m1

公式合并得到c^d=(m2 − m1) * p⁻¹ (mod q) * p + m1

解题代码

import gmpy2  
from Crypto.Util.number import long_to_bytes  

p = 7901324502264899236349230781143813838831920474669364339844939631481665770635584819958931021644265960578585153616742963330195946431321644921572803658406281
q = 12802918451444044622583757703752066118180068668479378778928741088302355425977192996799623998720429594346778865275391307730988819243843851683079000293815051
dp = 5540655028622021934429306287937775291955623308965208384582009857376053583575510784169616065113641391169613969813652523507421157045377898542386933198269451
dq = 9066897320308834206952359399737747311983309062764178906269475847173966073567988170415839954996322314157438770225952491560052871464136163421892050057498651
c = 62078086677416686867183857957350338314446280912673392448065026850212685326551183962056495964579782325302082054393933682265772802750887293602432512967994805549965020916953644635965916607925335639027579187435180607475963322465417758959002385451863122106487834784688029167720175128082066670945625067803812970871

InvQ=gmpy2.invert(q,p)  
mp=pow(c,dp,p)  
mq=pow(c,dq,q)  
m=(((mp-mq)*InvQ)%p)*q+mq  

print(long_to_bytes(m))