作者:Jing Ling
博客:HackFun

0x04 Cryptography

Flip My Letters

problem

I dropped my alphabet on its head, can you help me reassemble it? easyctf{r_wlmg_vevm_mvvw_zm_zhxrr_gzyov}

solution

使用了简单的替换的加密方法，每个字母被对应另一个字母替换，使用基于字典的词频分析在线网站quipqiup解出flag。

Clear and Concise Commentary on Caesar Cipher

problem

The flag is in Commentary.pdf. Use lowercase.

solution

凯撒密码，给出的文档值得一看，找到文档中RNFLPGS{LBHTBGVG}，凯撒密码在线解密

最终flag为easyctf{yougotit}

RSA1

problem

I found somebody’s notes on their private RSA! Help me crack this.

solution

RSA算法原理

扩展欧几里得算法

libnum模块

import libnum
p = 33499881069427614105926941260008415630190853527846401734073924527104092366847259
q = 34311544767652906613104559081988349779622789386528780506962212898921316785995851
e = 65537
c = 43465248299278658712013216049003172427898782261990372316282214376041873514481386908793943532363461126240609464283533882761307749486816342864113338277082746552
n = p * q
phi = (p - 1) * (q - 1)
d = libnum.modular.invmod(e, phi)
print libnum.n2s(pow(c, d, n)) #easyctf{wh3n_y0u_h4ve_p&q_RSA_iz_ez_7829d89f}

Let Me Be Frank

problem

I was talking to one of my friends but I couldn’t quite understand what he was saying. I think it might be important so here it is: Nwh whdjwh qm uepen, T tjb fsmt tixgi jsrsh sigm gs mpzp xwqf iahxpv iw fslkt. pehgpxf{qtextz_glacz_elt_neinrw_qsg_bums_dcp}

solution

维吉尼亚密码解密

RSA2

problem

Some more RSA! This time, there’s no P and Q… this.

solution

yafu- Automated integer factorization

yafu-x64.exe factor(266965481915457805187702917726550329693157)
...snip...
***factors found***
P21 = 458070420083487550883
P21 = 582804455845022449879

import libnum

n = 266965481915457805187702917726550329693157
p = 458070420083487550883
q = 582804455845022449879
e = 65537
c = 78670065603555615007383828728708393504251

phi = (p - 1) * (q - 1)
d = libnum.modular.invmod(e, phi)
print libnum.n2s(pow(c, d, n)) #flag{l0w_n_0eb6}

Decode Me

problem

Someone I met today told me that they had a perfect encryption method. To prove that there is no such thing, I want you to decrypt this encrypted flag he gave me.

solution

import base64

with open('encrypted_flag.txt') as file:
    data = file.read()
    while True:
        if 'easyctf' not in data:
            data = base64.b64decode(data)
        else:
            break
    print(data) # easyctf{what_1s_l0v3_bby_don7_hurt_m3}

Hash on Hash

problem

There’s a lot of hex strings here. Maybe they’re hiding a message? hexstrings

solution

import hashlib

md5 = {}
string = ''

for x in xrange(0, 256):
    char = chr(x)
    md5_obj = hashlib.md5()
    md5_obj.update(char)
    md5_str = md5_obj.hexdigest()
    md5[md5_str] = char

with open('hexstrings.txt') as file:
    while True:
        line = file.readline().replace('\n', '')
        if len(line) == 0:
            break
        string += md5[line]
print string # easyctf{1_h0p3_y0u_d1dn7_d0_7h47_by_h4nd}

RSA 3

problem

We came across another message that follows the same cryptographic schema as those other RSA messages. Take a look and see if you can crack it.

solution

λ yafu-x64.exe factor(1172115235823606152023154654763747932660073385647694278339165126116107393252225152886841069176950866458540922555424233427042989493814327572078420 5110462278896087432260439082955593874915727686637956899)


fac: factoring 11721152358236061520231546547637479326600733856476942783391651261161073932522251528868410691769508664585409225554242334270429894938143275720784205110462278896087432260439082955593874915727686637956899
fac: using pretesting plan: normal
fac: no tune info: using qs/gnfs crossover of 95 digits
div: primes less than 10000
fmt: 1000000 iterations
Total factoring time = 0.3556 seconds


***factors found***

P100 = 3423616853305296708261404925903697485956036650315221001507285374258954087994492532947084586412780871
P100 = 3423616853305296708261404925903697485956036650315221001507285374258954087994492532947084586412780869

ans = 1

import libnum

n = 11721152358236061520231546547637479326600733856476942783391651261161073932522251528868410691769508664585409225554242334270429894938143275720784205110462278896087432260439082955593874915727686637956899
p = 3423616853305296708261404925903697485956036650315221001507285374258954087994492532947084586412780871
q = 3423616853305296708261404925903697485956036650315221001507285374258954087994492532947084586412780869
e = 65537
c = 2907995727224121244474109148869412603986746589983095760953378907471772983106265015352351411281256847387789301815094608746590512178894738862276459859204020010443067567963450732279228357933677075986407

phi = (p - 1) * (q - 1)
d = libnum.modular.invmod(e, phi)
print libnum.n2s(pow(c, d, n)) # easyctf{tw0_v3ry_merrry_tw1n_pr1m35!!_417c0d}

推荐文章：CTF中RSA的常见攻击方法

Diffie-cult

problem

I just intercepted some odd messages.txt. It appears to be a Diffie-hellman protocol, but my math isn’t good enough to figure out what the final shared key is. Help! (The answer is a number. There is no easyctf{})
Hint: Wikipedia explains Diffie-hellman pretty well.

solution

g^a mod p = 421049228295820
g^b mod p = 105262307073955
p = 442101689710611

如果不知道Diffie-Hellman密钥交换算法可以先看：

Diffie-Hellman密钥交换算法

Diffie-Hellman密钥交换算法及其优化

题目的意思大概就是想让我们求出密钥K，Diffie-Hellman密钥交换算法的有效性依赖于计算离散对数的难度（知乎-离散对数为什么是难题？），这里p较小且这题给的g^a mod p和g^b mod p以及p都比较巧（g^a mod p即使A发送给B的值，而g^b mod p是B发送给A的值），为什么比较巧呢，我们在素数库找到他们的标准分解式。

g^a mod p = 421049228295820 = 2^2 · 5 · 17 · 19^3 · 37 · 47^4 
g^b mod p = 105262307073955 = 5 · 17 · 19^3 · 37 · 47^4
p = 442101689710611 = 3 · 7 · 17 · 19^3 · 37 · 47^4

现在令n = 17 · 19^3 · 37 · 47^4，那么就有：

g^a mod 21n = 20n
g^b mod 21n = 5n

我们把g^a mod 21n = 20n化简一下即：g^a mod 21n = -n，因为有20n mod 21n = -n，至于原理可以看一下密码学基础。

根据Diffie-Hellman密钥交换协议:

我们求的密钥K等于：K = (（g ^ a）mod p)^b mod p

也就是:K = (（g ^ a）mod 21n)^b mod 21n，而前面已求过g^a mod 21n = -n，所以K = (-n)^b mod 21n，现在只有b的值不知道，不过我们可以以b自变量的值为变量研究因变量K的变化情况：

n = 17 * (19 ** 3) * 37 * (47 ** 4)
p = 21 * n
for b in xrange(1,10):
    k = (-n) ** b % p
    print('k = (-n)^%d mod p = %d' %(b, k))

K = (-n)^b mod 21n
k = (-n)^1 mod p = 421049228295820
k = (-n)^2 mod p = 42104922829582
k = (-n)^3 mod p = 357891844051447
k = (-n)^4 mod p = 168419691318328
k = (-n)^5 mod p = 105262307073955
k = (-n)^6 mod p = 231577075562701
k = (-n)^7 mod p = 421049228295820
k = (-n)^8 mod p = 42104922829582
k = (-n)^9 mod p = 357891844051447

可以看到当b = 7又开始循环，所以K的可能值有6个，最后提交验证K为421049228295820。

Security Through Obscurity

problem

I’ve never seen such a cryptosystem before! It looks like a public key cryptosystem, though… Could you help me crack it?

encrypt.sage
publickey and ciphertext.txt

solution

SageMath 是一个基于GPL协议的开源数学软件。它使用Python作为通用接口，将现有的许多开源软件包整合在一起，构建一个统一的计算平台。
我们的目标：创建一个有活力的自由开源软件以替代Magma，Maple，Mathematica和Matlab。

中文版的SageMath入门手册

sage代码在线运行

信息安全数学基础-有限域

nth root algorithm

encrypt.sage：

p = 196732205348849427366498732223276547339
primelist = [2,3,5,7,11,13,17,19,23,29,31,37,43,47,53,59]
secret = REDACTED

def calc_root(num, mod, n):
    f = GF(mod)
    temp = f(num)
    return temp.nth_root(n)

def gen_v_list(primelist, p, secret):
    a = []
    for prime in primelist:
        a.append(calc_root(prime, p, secret))
    return a

def decodeInt(i, primelist):
    pl = sorted(primelist)[::-1]
    out = ''
    for j in pl:
        if i%j == 0:
            out += '1'
        else:
            out += '0'
    return out

def bin2asc(b):
    return hex(int(b,2)).replace('0x','').decode('hex')


message = REDACTED
chunks = []
for i in range(0,len(message),2):
    chunks += [message[i:i+2]]

vlist = gen_v_list(primelist,p,secret)
print(vlist)
for chunk in chunks:
    binarized = bin(int(chunk.encode('hex'),16)).replace('0b','').zfill(16)[::-1] #lsb first
    enc = 1
    for bit in range(len(binarized)):
        enc *= vlist[bit]**int(binarized[bit])
    enc = enc%p
    print(enc)

publickey and ciphertext.txt：

p = 196732205348849427366498732223276547339
vlist = [186290890175539004453897585557650819247, 75402298316736094226532182518108134406, 125495142022496378270547998225256386407, 97774267687164931514953833940936099082, 101991197227908059637463567354647370660, 153833851791059142883915934225837717549, 57404874013093467650483424580890463792, 21385179362692238453302681296928238570, 73119997627509808412069264512026243174, 187307466063352771786747395191866088255, 99696708971915885525739992181010504930, 35400960589917132410614021764179554582, 165004028169785856134522269878963539096, 23921651712221317415895203722083962980, 101282552285744196401422074083408273639, 36527324251768098978171373433957274016]
ciphertext = [10804437392992369932709952388461430442, 176193785024128365464527424154073333243, 149270645998191619421663334736314262928, 84083279828403258970202482839973583723, 105542809657403162156368566034837560781, 170535468317794277192003839288646533914, 1709561989051017137832962458645802494, 30208132812353075834728747743616689590, 179552149608863037880916374596103803214, 146319871444551859531557724256502213689, 94266034977624098660397183255753485858, 59624105602644297614582310044425417646, 150207980679551836987813576795479579005, 47189940152625174480564945084004798024, 60923399917552243674613186036841652885, 56060552313063913798237738953734149992, 153365453785043472981157196787373992079, 97439800863356756323659264743487719966, 105572255903480949865247928773026019148, 47189940152625174480564945084004798024, 32547907449246015626932936731350157592, 97471053149217334376536988401195572824, 156999991149661497460742185971412527182, 97705058765750947378422286408948780428, 56123764944636237849915747435965967337, 180380146745295930385428990214293723238, 178014626944341285289827069179285260436, 99504741454750536629756505680249931430]

大致看一下程序，理一下代码逻辑，message就是我们要求的明文，然后被分成每2个字符为一组添加到chunks列表：

message = REDACTED
chunks = []
for i in range(0,len(message),2):
    chunks += [message[i:i+2]]

vlist已经给了，所以不用再去求secret，接下来就是每2个字符简单的二值化处理再倒序，之后就是16次循环加密处理。

vlist = gen_v_list(primelist,p,secret)
print(vlist)
for chunk in chunks:
    binarized = bin(int(chunk.encode('hex'),16)).replace('0b','').zfill(16)[::-1] #lsb first
    enc = 1
    for bit in range(len(binarized)):
        enc *= vlist[bit]**int(binarized[bit])
    enc = enc%p
    print(enc)

加密结果已经给了，一共28组，所以能推出明文长度为56，我们知道ASCII字符的范围0-255，再从上面的加密代码分析可知，chunk最多就只有256*256=65536种组合，再做16次循环加密处理，也就是说最多1048576（256*256*16）次就能把一组明文穷举出来，计算机对1048576这个次数简直毫无压力，所以上代码：

p = 196732205348849427366498732223276547339
vlist = [186290890175539004453897585557650819247, 75402298316736094226532182518108134406, 125495142022496378270547998225256386407, 97774267687164931514953833940936099082, 101991197227908059637463567354647370660, 153833851791059142883915934225837717549, 57404874013093467650483424580890463792, 21385179362692238453302681296928238570, 73119997627509808412069264512026243174, 187307466063352771786747395191866088255, 99696708971915885525739992181010504930, 35400960589917132410614021764179554582, 165004028169785856134522269878963539096, 23921651712221317415895203722083962980, 101282552285744196401422074083408273639, 36527324251768098978171373433957274016]
ciphertext = [10804437392992369932709952388461430442, 176193785024128365464527424154073333243, 149270645998191619421663334736314262928, 84083279828403258970202482839973583723, 105542809657403162156368566034837560781, 170535468317794277192003839288646533914, 1709561989051017137832962458645802494, 30208132812353075834728747743616689590, 179552149608863037880916374596103803214, 146319871444551859531557724256502213689, 94266034977624098660397183255753485858, 59624105602644297614582310044425417646, 150207980679551836987813576795479579005, 47189940152625174480564945084004798024, 60923399917552243674613186036841652885, 56060552313063913798237738953734149992, 153365453785043472981157196787373992079, 97439800863356756323659264743487719966, 105572255903480949865247928773026019148, 47189940152625174480564945084004798024, 32547907449246015626932936731350157592, 97471053149217334376536988401195572824, 156999991149661497460742185971412527182, 97705058765750947378422286408948780428, 56123764944636237849915747435965967337, 180380146745295930385428990214293723238, 178014626944341285289827069179285260436, 99504741454750536629756505680249931430]
plaintext = ''

for i in ciphertext:
    find = False
    for j in xrange(256):
        if find:
            break
        for k in xrange(256):
            chunk = chr(j) + chr(k)
            binarized = bin(int(chunk.encode('hex'),16)).replace('0b','').zfill(16)[::-1]
            enc = 1
            for bit in range(len(binarized)):
                enc *= vlist[bit]**int(binarized[bit])
            enc = enc%p
            if enc == i:
                find = True
                plaintext += chunk
                break
print(plaintext) 

flag{i_actu4lly_d0nt_know_th3_name_of_th15_crypt0sy5tem} 
used time:18.040904s

Lost Seed

problem

Every time I encrypt a flag with this program, it gives me something different.

solution

int __cdecl main(int argc, const char **argv, const char **envp)
{
  char v3; // bl@2
  int result; // eax@4
  __int64 v5; // rcx@4
  char v6; // [sp+Bh] [bp-85h]@2
  int v7; // [sp+Ch] [bp-84h]@1
  int v8; // [sp+10h] [bp-80h]@1
  int v9; // [sp+14h] [bp-7Ch]@2
  FILE *stream; // [sp+18h] [bp-78h]@1
  char ptr[88]; // [sp+20h] [bp-70h]@1
  __int64 v12; // [sp+78h] [bp-18h]@1

  v12 = *MK_FP(__FS__, 40LL);
  stream = fopen("flag.in", "r");
  fread(ptr, 1uLL, 0x50uLL, stream);
  fclose(stream);
  stream = fopen("flag.out", "wb");
  seed = realrand("flag.out", "wb");
  v7 = 0;
  v8 = strlen(ptr);
  while ( v7 < v8 )
  {
    v3 = ptr[v7];
    v9 = pseudorand();
    v6 = v3 ^ v9;
    fwrite(&v6, 1uLL, 1uLL, stream);
    ++v7;
  }
  fclose(stream);
  result = 0;
  v5 = *MK_FP(__FS__, 40LL) ^ v12;
  return result;
}

Listen Closely

problem

We intercepted a secret message, but we can’t tell what it’s saying. Maybe you can help? super secret message
hint: 1, 16, 8000. After you use those, the problem is strictly crypto.

solution

writeup

Genius

problem

Your boss told you that this team has come up with the cryptographic hash of the future, but something about their operation just seems a little fishy.

solution

8a7fca9234d2f19c8abfcd812971a26c8c510dcaefd5061b191ad41d8b57d0ce631f5074f94b32730d0c025f1d7aacd7
be1ab1632e4285edc3733b142935c60b90383bad42309f7f6850d2b4250a713d0b2d7a97350465a02554d29d92bfefaf
d64ddd0de1b187cd670783f5e28d681dd401ed3009d05ce4ef600d364a2c953e4cc801b880dddef59829a5ad08bd8a63
73d559bc117f816333174e918d0587de5cca214701dbe9f7f42da7bccf074b811292b9d4dc398866ef95869b22b3941e
78635bc95eaa7662a2ddf3e3d45cf1084f4233d6c396e8a0e6fbf597d07b88178d03f3f7757bdbdaaed60729d08bb180
b42dad5453b2128a32f6612b13ea5d9fef843bee79633652a6d6ae08e964609f00e883ab809346226dff6887080fb68b

给了6组哈希值，每组96个字符，还提示到了MD5，于是丢crackstation跑一下：

简单验证一下：

md5(like) = be1ab1632e4285edc3733b142935c60b
md5(ly_s) = d64ddd0de1b187cd670783f5e28d681d
md5(ng_2) = 73d559bc117f816333174e918d0587de
md5(have) = b42dad5453b2128a32f6612b13ea5d9f

推测每组就是三个MD5组合的，于是将所有的MD5换行拆分再进行一次查找：

还有7个没有破解，从上面的都是4位简单的消息，于是把未找出的7个扔MD5库：

按顺序组合一下：OMG_it_took_like_LITerally_s0oO00_long_2_MAK3_md5_werrk_you_have_no_id34
提交给了flag：easyctf{OUR_3nCRYpti0n_is_N0T_br0k3n_Ur_brok3n_6c5a390d}

py优雅解决方式：

import hashlib

hashs = '8a7fca9234d2f19c8abfcd812971a26c8c510dcaefd5061b191ad41d8b57d0ce631f5074f94b32730d0c025f1d7aacd7be1ab1632e4285edc3733b142935c60b90383bad42309f7f6850d2b4250a713d0b2d7a97350465a02554d29d92bfefafd64ddd0de1b187cd670783f5e28d681dd401ed3009d05ce4ef600d364a2c953e4cc801b880dddef59829a5ad08bd8a6373d559bc117f816333174e918d0587de5cca214701dbe9f7f42da7bccf074b811292b9d4dc398866ef95869b22b3941e78635bc95eaa7662a2ddf3e3d45cf1084f4233d6c396e8a0e6fbf597d07b88178d03f3f7757bdbdaaed60729d08bb180b42dad5453b2128a32f6612b13ea5d9fef843bee79633652a6d6ae08e964609f00e883ab809346226dff6887080fb68b'

def get_md5_list(hashs):
    md5_list = []
    for x in xrange(0, len(hashs), 32):
        md5_list.append(hashs[x:x+32])
    return md5_list

def gen_char_list():
    char_list = []
    for x in xrange(48, 58): # 0 ~ 9
        char_list.append(chr(x))
    for x in xrange(65, 91): # A ~ Z
        char_list.append(chr(x))
    for x in xrange(97, 123): # a ~ z
        char_list.append(chr(x))
    char_list.append('_') # _
    return char_list

def brute_force_md5(char_list, md5_list):
    plain_dict = {}
    for c1 in char_list:
        for c2 in char_list:
            for c3 in char_list:
                for c4 in char_list:
                    chars = c1 + c2 + c3 + c4
                    md5_obj = hashlib.md5()
                    md5_obj.update(chars)
                    md5_str = md5_obj.hexdigest()
                    if md5_str in md5_list:
                        plain_dict[md5_str] = chars
    return plain_dict

def get_plain(md5_list, plain_dict):
    plain = ''
    for md5 in md5_list:
        plain += plain_dict[md5]
    return plain

def main():
    md5_list = get_md5_list(hashs)
    char_list = gen_char_list()
    plain_dict = brute_force_md5(char_list, md5_list)
    plain = get_plain(md5_list, plain_dict)
    print(plain)

if __name__ == '__main__':
    main()

RSA 4

problem

After doing so much RSA, I finally messed up…. pls help. I encrypted my secret message but the decryption isn’t working!!

solution

writeup

Premium RSA

problem

My RSA is the greatest. It’s so strong, in fact, that I’ll even give you d! file

hint: You thought it’d be that simple?

solution

writeup

Paillier Service

problem

My friend made some sort of encryption service using the Paillier cryptosystem. Can you get him to encrypt the string easyctf{3ncrypt_m3!} for me? Your flag will be a base 10 integer.

Access his encryption service at paillier.tcp.easyctf.com 8570

solution

writeup

# Paillier.py
import binascii

#Gathered from connecting manually
# m = 1, r = 1
g = 76148136246979412868353192826161253341403849263254887278017187958514513340458179944731332795505616407225022188597713956679924138156737337560391522285190471306102238935856085554943425316921717217530405444795878376547349107664015741971592178799088766898531556269231518219697725522509132047243753064371633643298

# m = 2, r = 1
g2 = 152296272493958825736706385652322506682807698526509774556034375917029026680916359889462665591011232814450044377195427913359848276313474675120783044570380942612204477871712171109886850633843434435060810889591756753094698215328031483943184357598177533797063112538463036439395451045018264094487506128743267286595

expectedG2 = g*g

#Using Factordb, we find that expectedG2-g2 is a perfect square of a prime, which is below
#http://factordb.com/index.php?id=1100000000882961502
n = 76148136246979412868353192826161253341403849263254887278017187958514513340458179944731332795505616407225022188597713956679924138156737337560391522285190471306102238935856085554943425316921717217530405444795878376547349107664015741971592178799088766898531556269231518219697725522509132047243753064371633643297
n2 = n*n
m2r2 = 642704871773304452155778596282877892451871980828477596157415930594972102473171707034871466334408214634990379265334519095544245651795310239071984348465353456082430791507322024283077057140015173791209040404351064470318177893091562745760770981747716308255111472933684059218100124906239297276402113587510274467857526915676715307055889593001002210535184406398178516901311847346979934161946287183599368736554797730366291587740218078384204696550286009123986874335424671114430592617561047352470044247529967986001239137580719442869043114141323570567593427242451750466586033713111304296116982128148631354597378733690535403149
#check for no errors
assert (pow(g,2,n2)*pow(2,n,n2))%n2 == m2r2
assert (pow(g,2,n2))%n2 == g2

# get int of string easyctf{3ncrypt_m3!}
goal = b'easyctf{3ncrypt_m3!}'
hexGoal = str(binascii.hexlify(goal),'utf-8')
goal = int(hexGoal,16)
#print(goal)
#goal is divisible by 5, so use that for Homomorphic property
m5r1 = pow(g,5,n2)
goalDiv5 = goal // 5
# Now use the Homomorphic property :)
flagInt = pow(m5r1,goalDiv5,n2)
print(flagInt)