CSAW2018_Lowe

I personally prefer Home Depot.

XOR Passes are the easiest way to use numbers to encrypt!

By Kris Kwiatkowski, Cloudflare

题目提供了三个文件：file.enc, key.enc, pubkey.pem 可以在我的GitHub中找到。

TL;DR

运用了RSA公钥中的小公钥指数e，如果明文m的e次方小于n，则用e开方密文m可以得到明文。参考：https://ctftime.org/writeup/11328

---

关于RSA加密和破解的参考：https://bitsdeep.com

因式分解数据库：http://factordb.com

先查看三个文件的内容，pubkey.pem 明显是RSA的公钥，用openssl的命令解析它：

sunhaiwendeMacBook-Pro:LoweCrypto sun$ openssl rsa -inform PEM -text -noout -pubin < pubkey.pem

Public-Key: (1536 bit)

Modulus:

    00:cf:70:7e:ed:97:90:17:b7:f6:f4:76:ff:3b:a6:

    55:59:ad:b1:82:e0:7c:fa:23:33:b1:ec:05:6b:7f:

    7b:96:12:40:54:f1:f5:74:8b:04:c3:69:4e:90:f0:

    d9:9f:ee:05:84:a8:7a:70:81:75:80:d4:93:93:32:

    1b:b2:08:07:ff:de:25:a4:c8:ab:d4:6d:95:c1:e3:

    74:0d:9e:64:1f:e7:7f:9b:96:ce:ca:e9:18:e6:7a:

    24:89:52:b5:da:81:ae:77:42:bd:ae:51:b1:29:24:

    59:73:41:50:57:ae:75:df:b7:5a:78:e8:24:37:9e:

    52:50:65:92:c3:75:0e:9a:1c:7e:70:1b:ee:8d:df:

    c7:a9:ca:72:53:4c:d3:b0:95:79:f8:7a:4e:b3:76:

    f9:26:7c:d1:a1:6e:1e:57:90:95:c5:b8:6f:4b:8f:

    24:fb:61:3f:08:a7:e0:e4:75:d2:55:56:ae:41:c8:

    ce:e2:48:e9:0d:ac:96:5d:c4:7d:db:b4:c5

Exponent: 3 (0x3)

可以看到这个公钥用了一个很小的指数e，根据Wikipedia对于攻击RSA的描述，我们可以将密文用e开方来得到明文。

文件file.enc内容如下：

kStoynmN5LSniue0nDxli9csSrBgexZ/YOo5e+MUkfJKwvht8hHsYyMGVYzMlOp9sAFBrPCbm4UA4n7oMr2zlg==

用Base64解码：

其内容肯定加密过，将加码后的内容存在file.bin中。

文件key.enc的内容如下：

219135993109607778001201845084150602227376141082195657844762662508084481089986056048532133767792600470123444605795683268047281347474499409679660783370627652563144258284648474807381611694138314352087429271128942786445607462311052442015618558352506502586843660097471748372196048269942588597722623967402749279662913442303983480435926749879440167236197705613657631022920490906911790425443191781646744542562221829319509319404420795146532861393334310385517838840775182

这是一个大整数，可能是RSA中的某个数。

因为公钥指数是3，如果密文c的e次方小于大数n，我们可以对c开e次方来得到明文。尝试对key.enc中的数进行开方。用python的gmpy2库来做大数的开方运算：

>>> import gmpy2

>>> e=gmpy2.mpz(3)

>>> c=gmpy2.mpz(219135993109607778001201845084150602227376141082195657844762662508084481089986056048532133767792600470123444605795683268047281347474499409679660783370627652563144258284648474807381611694138314352087429271128942786445607462311052442015618558352506502586843660097471748372196048269942588597722623967402749279662913442303983480435926749879440167236197705613657631022920490906911790425443191781646744542562221829319509319404420795146532861393334310385517838840775182)

将密文和公钥指数以mpz的格式存储。mpz是Multiple-precision Integers，用来存储任意精度整数。对c进行开方：

>>> gmpy2.iroot(c, e)

(mpz(6028897571524104587358191144119083924650151660953920127739581033174354252210219577997969114849529704172847232120373331804620146706030387812427825026581462), False)

第二个返回值false代表这个结果不是精确的，说明c被e开方不是整数。

回忆RSA加密公式：c=m^e mod n. 如果m^e比n大，那么就会进行mod n的计算。 我们尝试把密文c加上一个n的大小再次开方：

>>> n=gmpy2.mpz(0x00cf707eed979017b7f6f476ff3ba65559adb182e07cfa2333b1ec056b7f7b96124054f1f5748b04c3694e90f0d99fee0584a87a70817580d49393321bb20807ffde25a4c8abd46d95c1e3740d9e641fe77f9b96cecae918e67a248952b5da81ae7742bdae51b129245973415057ae75dfb75a78e824379e52506592c3750e9a1c7e701bee8ddfc7a9ca72534cd3b09579f87a4eb376f9267cd1a16e1e579095c5b86f4b8f24fb613f08a7e0e475d25556ae41c8cee248e90dac965dc47ddbb4c5) #导入公钥中的n

>>> gmpy2.iroot(c+n,e)

(mpz(12950973085835763560175702356704747094371821722999497961023063926142573092871510801730909790343717206777660797494675328809965345887934044682722741193527531), True)

开方得到的结果是整数！说明解密成功！

把整数转换为hex：

>>> plain = int(gmpy2.iroot(c + n, e)[0])

>>> hex(plain)

'0xf74709ad02fe85d8d3f993d5ff5716eabb5829df0d12624a048e0a4bd726a6c428a3cd5ac6248900113733effdf1dc4b8837209c92a9a3e161d0478d04dbd0eb'

但这依然不是flag。

题目中有提示运用XOR运算。尝试将我们得到的结果和file.binXOR：

>>> key = bytes.fromhex(hex(plain)[2:])

>>> data = open("file.bin", "rb").read()

>>> bytes([ k ^ d for (k, d) in zip(key, data) ])

b'flag{saltstacksaltcomit5dd304276ba5745ec21fc1e6686a0b28da29e6fc}'

得到flag！！！