BUUCTF-Crypto系列[17-32]WP

信息化时代的步伐

点开附件，密文如下：

606046152623600817831216121621196386

一看到密文，我的第一想法是诺基亚键盘密码，但是诺基亚键盘上的”0”并没有字母，所以这不是诺基亚键盘密码。搜索发现这是中文电码（又学到新知识了），和摩斯电码类似。由于字典的元素过多，且映射的原理和摩斯密码类似，就不再搞脚本了。

通过在线解密工具，明文如下：

6060：计
4615：算
2623：机
6008：要
1783：从
1216：娃
1216：娃
2119：抓
6386：起

传统知识 + 古典密码

点开附件，题目如下：

小明某一天收到一封密信，信中写了几个不同的年份
          辛卯，癸巳，丙戌，辛未，庚辰，癸酉，己卯，癸巳。
          信的背面还写有“+甲子”，请解出这段密文。

key值：CTF{XXX}

找到甲子表，八个不同的年份对应的数字分别是28 30 23 8 17 10 16 30。根据“ + 甲子”这个线索（一甲子 = 60），八个数字变为 88 90 83 68 77 70 76 90。再利用古典密码：Caesar密码进行解密，解得密文为：

SHUANGYU

按照题目格式提交即可。

凯撒？替换？呵呵！

题目如下：

前四个字母与flag没有传统凯撒密码的替换规律，使用了线上暴力破解工具。

圈出的部分就是flag。

RSA1

点开附件，题目如下：

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

要求得m，这里的话需要进行公式推导：

m ≡ c ^ d mod n，n = p * q

m = c ^ d + k p q

两边同除以q，令m1 = m / q，得：

m1 = c ^ d + k * p

m1 ≡ c ^ d mod p —————————-①

同理，两边同除以p，得：

m2 = c ^ d + k * q

m2 ≡ c ^ d mod q —————————-②

由①得：c ^ d = k * p + m1 —————————-③

③式代入②式得：

m2 ≡ (k*p + m1) mod q

m2 - m1 ≡ kp mod q

因为gcd(p, q) = 1

所以(m2 - m1) * invp ≡ k mod q （其中invp是p关于q的乘法逆元）

k ≡ ((m2 - m1) * invp) mod q ————————-④

把④式代入③式得：

c ^ d = (((m2 - m1) invp) mod q) p + m1

现在问题变为如何得到m1和m2，还有一个条件没用上，那就是dp ≡ d mod (p - 1)、dq ≡ d mod (q - 1)：

d ≡ dp mod (p - 1) ————————⑤

把⑤式代入①式得：

m1 ≡ c ^ (dp mod (p - 1)) mod p

m1 ≡ c ^ (dp + k*(p - 1)) mod p

m1 ≡ c ^ dp mod p * c ^ k (p - 1) mod p ————————-⑥

由费马小定理可知，存在质数p，如果有gcd(k,p) = 1，则k ^ (p - 1) ≡ 1 mod p。

所以⑥式可以简化为 m1 ≡ c ^ dp mod p，同理m2 ≡ c ^ dq mod q。这样可求得c ^ d，进步可求得m。

脚本部分：

import gmpy2
from Crypto.Util.number import *

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

m1 = pow(c,dp,p)
m2 = pow(c,dq,q)
n = p * q
d = gmpy2.invert(dp, (p - 1))
invp = gmpy2.invert(p,q)
m = ((((m2 - m1) * invp)%q) * p + m1)%n
#把数字对应的字节转换为字符
flag = long_to_bytes(m)
print("flag{}".format(flag))

即可得到flag。

flag{W31c0m3_70_Ch1n470wn}

萌萌哒的八戒

题目如下：

这是一道猪圈密码，猪圈密码的编码规则如下：

将图片中的图形与编码规则一一对应就是flag：

flag{whenthepigwanttoeat}

old-fashion

点开附件，题目如下：

Os drnuzearyuwn, y jtkjzoztzoes douwlr oj y ilzwex eq lsdexosa kn pwodw tsozj eq ufyoszlbz yrl rlufydlx pozw douwlrzlbz, ydderxosa ze y rlatfyr jnjzli; mjy gfbmw vla xy wbfnsy symmyew (mjy vrwm qrvvrf), hlbew rd symmyew, mebhsymw rd symmyew, vbomgeyw rd mjy lxrzy, lfk wr dremj. Mjy eyqybzye kyqbhjyew mjy myom xa hyedrevbfn lf bfzyewy wgxwmbmgmbrf. Wr mjy dsln bw f1_2jyf-k3_jg1-vb-vl_l

这是一道英文字符频率分析题，线上工具直接破解吧：

答案就是框出来的部分。

权限获得的第一步

点开附件，题目如下：

Administrator:500:806EDC27AA52E314AAD3B435B51404EE:F4AD50F57683D4260DFD48AA351A17A8:::

这题和上篇博客中的Windows密码是一样的，用在线工具解决吧：

flag就是查询结果。

世上无难事

点开附件，题目如下：

VIZZB IFIUOJBWO NVXAP OBC XZZ UKHVN IFIUOJBWO HB XVIXW XAW VXFI X QIXN VBD KQ IFIUOJBWO WBKAH NBWXO VBD XJBCN NKG QLKEIU DI XUI VIUI DKNV QNCWIANQ XN DXPIMKIZW VKHV QEVBBZ KA XUZKAHNBA FKUHKAKX XAW DI VXFI HBN QNCWIANQ NCAKAH KA MUBG XZZ XEUBQQ XGIUKEX MUBG PKAWIUHXUNIA NVUBCHV 12NV HUXWI XAW DI XUI SCQN QB HZXW NVXN XZZ EBCZW SBKA CQ NBWXO XAW DI DXAN NB NVXAP DXPIMKIZW MBU JIKAH QCEV XA BCNQNXAWKAH VBQN HKFI OBCUQIZFIQ X JKH UBCAW BM XLLZXCQI XAW NVI PIO KQ 640I11012805M211J0XJ24MM02X1IW09

这题考察的还是替换密码，暴力破解，根据题目提示，可以将”PIO”替换为”key”：

框出来的部分就是flag。

RSA3

题目给的信息如下：

c1=22322035275663237041646893770451933509324701913484303338076210603542612758956262869640822486470121149424485571361007421293675516338822195280313794991136048140918842471219840263536338886250492682739436410013436651161720725855484866690084788721349555662019879081501113222996123305533009325964377798892703161521852805956811219563883312896330156298621674684353919547558127920925706842808914762199011054955816534977675267395009575347820387073483928425066536361482774892370969520740304287456555508933372782327506569010772537497541764311429052216291198932092617792645253901478910801592878203564861118912045464959832566051361

n=22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801

e1=11187289

c2=18702010045187015556548691642394982835669262147230212731309938675226458555210425972429418449273410535387985931036711854265623905066805665751803269106880746769003478900791099590239513925449748814075904017471585572848473556490565450062664706449128415834787961947266259789785962922238701134079720414228414066193071495304612341052987455615930023536823801499269773357186087452747500840640419365011554421183037505653461286732740983702740822671148045619497667184586123657285604061875653909567822328914065337797733444640351518775487649819978262363617265797982843179630888729407238496650987720428708217115257989007867331698397

e2=9647291

这题考察的是RSA共模攻击，什么是RSA共模攻击呢？这里引用了大佬博客中的一个例子：

假设有一家公司COMPANY，在员工通信系统中用RSA加密消息。COMPANY首先生成了两个大质数P,Q，取得PQ乘积N。并且以N为模数，生成多对不同的公钥及其相应的私钥。COMPANY将所有公钥公开。而不同的员工获得自己的私钥，比如，员工A获得了私钥d1，员工B获得了私钥d2。现在，COMPANY将一条相同的消息，同时经过所有公钥加密，发送给所有员工。此时，就可能出现共模攻击。
共模攻击
也称同模攻击，英文原名是 Common Modulus Attack 。
同模攻击利用的大前提就是，RSA体系在生成密钥的过程中使用了相同的模数n。假设COMPANY用所有的公钥加密了明文，即：

c1= m ^ e1 mod n，c2 = m ^ e2 mod n。那么员工A和员工B就可以分别通过私钥d1和d2来获取明文了。如果，此时有一个攻击者，同时监听了A和B接收到的密文c1,c2，因为模数不变，以及所有公钥都是公开的，那么利用同模攻击，他就可以在不知道d1，d2的情况下解密得到消息m。why？以下是推导过程：

首先引入一个定理——裴蜀定理

裴蜀定理：裴蜀定理或贝祖定理得名于法国数学家艾蒂安·裴蜀，说明了对任何整数a、b和它们的最大公约数d，关于未知数x和y的线性不定方程（称为裴蜀等式）：若a,b是整数,且gcd(a,b)=d，那么对于任意的整数x,y,ax+by（①）都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。它的一个重要推论是：a,b互质的充分必要条件是存在整数x,y使ax+by=1。

这边做一个小小的推导：

因为a和b分别是它们最大公约数d的倍数，记a = k d, b = j d，代入①式得 k x d + j y d，其中x和y是任意的整数，所以k x d是d的倍数同理j y d也是d的倍数，得证。

现在我们假设e1和e2互质，即gcd(e1,e2) = 1，此时引用裴蜀定理有e1 s1 + e2 s2 = 1。

接着引入扩展的欧几里得算法：扩展欧几里得算法是欧几里得算法（又叫辗转相除法）的扩展。除了计算a、b两个整数的最大公约数，此算法还能找到整数x、y（其中一个很可能是负数）。通常谈到最大公因子时, 我们都会提到一个非常基本的事实: 给予二整数 a 与 b, 必存在有整数 x 与 y 使得ax + by = gcd(a,b)。有两个数a,b，对它们进行辗转相除法，可得它们的最大公约数——这是众所周知的。然后，收集辗转相除法中产生的式子，倒回去，可以得到ax+by=gcd(a,b)的整数解。

然后我们就可以通过扩展的欧几里得算法求得一组解[s1,s2]。

c1 = m^e1 mod n，c2 = m ^ e2 mod n

c1 ^ s1 c2 ^ s2 = m ^ (e1 s1) mod n m ^ (e2 * s2) mod n

c1 ^ s1 c2 ^ s2 = m ^ (e1 s1 + e2 * s2) mod n

因为e1 s1 + e2 s2 = 1，所以上式变为 c1 ^ s1 * c2 ^ s2 = m ^ (1) mod n = m mod n = m。

推导系数：

有一点要说明，s1 和 s2其中有一个是负数。数论模运算中，要求一个数的负数次幂，先计算c的模反元素cr，然后求cr的-s次幂。

推到完毕，代码部分：

from Crypto.Util.number import inverse
import libnum

#扩展欧几里得算法，求得a与b的系数
def exgcd(a , b):
    #当a % b == 0时表示已求得最大公约数和两个系数
    if (b == 0):
        #返回的第一个参数最大公约数，第二个参数a的系数，第三个参数是b的系数
        #这里0和任何数的最大公约数是这个数的本身
        return (b, 1, 0)
    else:
        #将函数返回的结果依次赋值给d, x, y
        d, x, y = exgcd(b, a % b)
        return (d, y, x - (a // b) * y)

c1=22322035275663237041646893770451933509324701913484303338076210603542612758956262869640822486470121149424485571361007421293675516338822195280313794991136048140918842471219840263536338886250492682739436410013436651161720725855484866690084788721349555662019879081501113222996123305533009325964377798892703161521852805956811219563883312896330156298621674684353919547558127920925706842808914762199011054955816534977675267395009575347820387073483928425066536361482774892370969520740304287456555508933372782327506569010772537497541764311429052216291198932092617792645253901478910801592878203564861118912045464959832566051361
n=22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801
e1=11187289
c2=18702010045187015556548691642394982835669262147230212731309938675226458555210425972429418449273410535387985931036711854265623905066805665751803269106880746769003478900791099590239513925449748814075904017471585572848473556490565450062664706449128415834787961947266259789785962922238701134079720414228414066193071495304612341052987455615930023536823801499269773357186087452747500840640419365011554421183037505653461286732740983702740822671148045619497667184586123657285604061875653909567822328914065337797733444640351518775487649819978262363617265797982843179630888729407238496650987720428708217115257989007867331698397
e2=9647291

s = exgcd(e1, e2)
s1 = s[1]
s2 = s[2]

#当s是负数的时候，一个数的负数次幂，先计算c的模反元素cr，然后求cr的-s次幂。
if (s1 < 0):
    s1 = -s1
    c1 = inverse(c1, n)

elif (s2 < 0):
    s2 = -s2
    c2 = inverse(c2, n)

m = pow(c1,s1,n) * pow(c2,s2,n) % n
#数字转字符串
print(libnum.n2s(m))

解得flag为：

flag{49d91077a1abcb14f1a9d546c80be9ef}

RSA2

题目如下：

e = 65537
n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657
c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751

这题考查的是dp泄露，推导如下：

d ≡ dp mod (p - 1)，两边同乘e，e d ≡ (e dp) mod (p - 1) —> e d = k1 e (p - 1) + e dp ——————①。

e d = 1 mod Φ(n)，Φ(n) = (p - 1) (q - 1) —> e d = k2 (p - 1) ** (q - 1) + 1 —————②。

由①和②得k1 e (p - 1) + e dp = k2 (p - 1) (q - 1) + 1 —> e dp = (p - 1) (k2 (q - 1) - k1) + 1。记(k2 * (q - 1) - k1) = x，则

e dp = (p - 1) x + 1。因为dp < p - 1，所以1 < x < e。遍历e就可以求得p，代码如下：

from Crypto.Util.number import inverse
import libnum

e = 65537
n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657
c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751

y = dp * e
for x in range(1,e):
    if ((y - 1) % x == 0):
        p = (y - 1) // x + 1
        if (n % p == 0):
            q = n // p
            phin = (p - 1) * (q - 1)
            d = inverse(e, phin)
            m = pow(c, d, n)
            print(libnum.n2s(m))

接着就可以得到flag。

异性相吸

题目如下，包含两个文件，一个是key.txt，还有一个是密文.txt：

key.txt:
asadsasdasdasdasdasdasdasdasdasdqwesqf
密文.txt:
ἇ̀Ј唒ဃ塔屋䩘卖剄䐃堂ن䝔嘅均ቄ䩝ᬔ

考察的是二进制的异或，代码：

miwen = open("D:\\密文.txt",'rb').read()
key = open("D:\\key.txt",'rb').read()
flag = ''
for i in range(0, len(miwen)):
    str = list(miwen)[i] ^ list(key)[i]
    flag += chr(str)
print(flag)

即可得到flag。

还原大师

题目如下：

我们得到了一串神秘字符串：TASC?O3RJMV?WDJKX?ZM,问号部分是未知大写字母，为了确定这个神秘字符串，我们通过了其他途径获得了这个字串的32位MD5码。但是我们获得它的32位MD5码也是残缺不全，E903???4DAB????08?????51?80??8A?,请猜出神秘字符串的原本模样，并且提交这个字串的32位MD5码作为答案。 注意：得到的 flag 请包上 flag{} 提交

这题让我想到了上一篇博客里的“丢失的MD5“，发现其原理相似，而且MD5的字符串中有些字符是一样的，可以引用它的代码：

import hashlib   
for i in range(32,127):
    for j in range(32,127):
        for k in range(32,127):
            #生成MD5加密对象
            m=hashlib.md5()
            #在加密之前要对数据进行编码
            m.update(('TASC'+chr(i)+'O3RJMV'+chr(j)+'WDJKX'+chr(k)+'ZM').encode())
            #生成MD5摘要信息
            des=m.hexdigest()
            if 'e903' in des and '4dab' in des and '08' in des and '51' in des and '80' in des and '8a' in des:
                print (des)

RSA

题目里面有flag.enc和pub.key，通过在线分解工具获得n和e：

分解n，可以得到p = 285960468890451637935629440372639283459, q = 304008741604601924494328155975272418463

。有了p, q, e就可以得到d，有d可以解密文：

import gmpy2
import rsa

e = 65537
n = 86934482296048119190666062003494800588905656017203025617216654058378322103517
p = 285960468890451637935629440372639283459
q = 304008741604601924494328155975272418463

phin = (p - 1) * (q - 1)
d = gmpy2.invert(e, phin)

prikey = rsa.PrivateKey(n, e, int(d), p, q)

with open("flag.enc","rb") as f:
    f = f.read()
    print(rsa.decrypt(f, prikey))

uuencode

题目如下：

89FQA9WMD<V1A<V1S83DY.#<W3$Q,2TM]

这题考查的是uuencode，什么是uuencode?

通过在线解密工具，就可以得到flag：

flag{dsdasdsa99877LLLKK}

[AFCTF2018]Morse

题目如下：

-..../.----/-..../-..../-..../...--/--.../....-/-..../-..../--.../-.../...--/.----/--.../...--/..---/--.../--.../....-/...../..-./--.../...--/...--/-----/...../..-./...--/...--/...--/....-/...--/...../--.../----./--.../-..

其中”/“是间隔，其余的就是数字和字符，进行翻译就是：

61666374667B317327745F73305F333435797D

这些是16进制数，转化成ASCII码就可以得到flag：

afctf{1s’t_s0_345y}

换成flag格式就可以了。

RSAROLL

题目如下：

题目.txt:
RSA roll！roll！roll！
Only number and a-z
（don't use editor
which MS provide）
data.txt:
{920139713,19}

704796792
752211152
274704164
18414022
368270835
483295235
263072905
459788476
483295235
459788476
663551792
475206804
459788476
428313374
475206804
459788476
425392137
704796792
458265677
341524652
483295235
534149509
425392137
428313374
425392137
341524652
458265677
263072905
483295235
828509797
341524652
425392137
475206804
428313374
483295235
475206804
459788476
306220148

初步分析可知n = 920139713, e = 19。思路就是由n求p，q，然后由Φ(n)，e求得d，再根据密文求得明文：

脚本如下：

import gmpy2
import rsa

e = 19
n = 920139713
p = 18443
q = 49891

phin = (p - 1) * (q - 1)
d = gmpy2.invert(e, phin)

phainer = []

with open("data.txt","rb") as f:
    for cipher in f.readlines():
        phainer.append(chr(pow(int(cipher), d, n)))

for i in phainer:
    print(i, end='')

即可得到flag。

参考：

https://www.cnblogs.com/rainbowcloud/p/10141301.html

https://baike.baidu.com/item/%E8%A3%B4%E8%9C%80%E5%AE%9A%E7%90%86/5186593